What is the output of a lexical analyzer?
Sequence of tokens
Understanding the Output of a Lexical Analyzer
A lexical analyzer, also known as a lexer or scanner, is the first phase of a compiler. Its main task is to read the input character stream and group characters into meaningful sequences called tokens.
Let's break down what a lexical analyzer does:
- It takes the source code as a sequence of raw characters.
- It identifies patterns in these characters that correspond to language constructs like identifiers, keywords, operators, numbers, etc.
- Each recognized pattern is classified into a token.
- The output is a stream or sequence of tokens.
Consider a simple statement in a programming language:
int count = 0;
A lexical analyzer would process this character by character and produce the following sequence of tokens:
| Characters | Token Type | Lexeme (Value) |
|---|---|---|
| int | KEYWORD | int |
| <space> | (ignored) | - |
| count | IDENTIFIER | count |
| <space> | (ignored) | - |
| = | ASSIGN_OP | = |
| <space> | (ignored) | - |
| 0 | INTEGER_LITERAL | 0 |
| ; | SEMICOLON | ; |
The output is the list of tokens: KEYWORD, IDENTIFIER, ASSIGN_OP, INTEGER_LITERAL, SEMICOLON. This is the sequence of tokens that the next phase, the parser, will use.
Why Other Options Are Incorrect
- Search tree: A data structure used for searching, not the output of a lexical analyzer.
- String character: The input to the lexical analyzer is a stream of characters, not the output.
- Syntax tree: This is the output of the parser (syntactic analyzer), which takes the sequence of tokens as input.
Therefore, the correct output of a lexical analyzer is a sequence of tokens.
Revision Table: Compiler Phases
| Compiler Phase | Input | Output |
|---|---|---|
| Lexical Analyzer | Source Code (Character Stream) | Sequence of Tokens |
| Syntax Analyzer (Parser) | Sequence of Tokens | Syntax Tree (Parse Tree/Abstract Syntax Tree) |
| Semantic Analyzer | Syntax Tree | Annotated Syntax Tree |
| Intermediate Code Generator | Annotated Syntax Tree | Intermediate Code |
| Code Optimizer | Intermediate Code | Optimized Intermediate Code |
| Code Generator | Optimized Intermediate Code | Target Machine Code |
Additional Information: Lexical Analysis Details
Lexical analysis involves several key tasks:
- Scanning: Reading the input characters.
- Identifying Lexemes: Finding sequences of characters that form potential tokens.
- Tokenization: Classifying lexemes into specific token types (e.g., identifier, keyword, operator) and often associating value information (the lexeme itself).
- Handling Whitespace and Comments: Usually, these are ignored and discarded during lexical analysis as they are not significant for the syntax of the program (though their presence separates tokens).
- Error Detection: Reporting errors like illegal characters.
The sequence of tokens produced by the lexical analyzer is fundamental for the subsequent phases of the compiler, especially the parser.
Important Questions from Lexical Analysis
Which of the following are applications of symbol table ?
(A) Storage allocation
(B) Checking type compatability
(C) Suppressing duplicate error messages
Choose the correct answer from the options given below:
Arrange the given compilation process in the correct order.
a. Linking
b. Assembling
c. Compiling
d. Pre-processing
Which ONE of the following statements is FALSE regarding the symbol table?
- A lexical analyzer uses the following token definitions
- $letter \rightarrow [A-Z a-z]$
- $digit \rightarrow [0-9]$
- $id \rightarrow letter(letter \mid digit)^*$
- $number \rightarrow digit^+$
- $ws \rightarrow (blank \mid tab \mid newline)^+$
For the string given below,
$x1 \quad 23mm \quad 78 \quad y \quad 7z \quad zz5 \quad 14A \quad 8H \quad AaYcD$
the number of tokens (excluding $ws$) that will be produced by the lexical analyzer is __________. (answer in integer)
