Past exam question: 2082 Chaitra (Regular), Q15
Open in the Padhaiko appQuestion
How the tokens are generated by the lexical analyzer. Explain.
Solution
Role and Token Generation Process of Lexical Analyzer: The lexical analyzer (scanner) is the first phase of a compiler. Its primary role is to convert the stream of source characters into a stream of meaningful atomic units called tokens:
- Lexical Specifications (Regular Expressions): Language constructs (keywords, identifiers, constants, operators) are specified using regular expressions (e.g.,
id = [a-zA-Z][a-zA-Z0-9]*,num = [0-9]+). - DFA Implementation: The regular expressions are compiled into finite automata (Thompson's construction subset construction DFA minimization).
- Buffering and Scanning: The scanner buffers input characters and advances a forward pointer to trace transitions in the DFA.
- Longest Match (Maximal Munch): The scanner continues reading characters until no further valid transition exists, selecting the longest matching prefix that reaches an accepting state.
- Token Output and Symbol Table: Upon recognizing a valid lexeme, whitespace and comments are discarded, and a token of the form
⟨token_name, attribute_value⟩(e.g.,⟨id, pointer_to_symbol_table⟩,⟨num, 42⟩,⟨assign_op, =⟩) is emitted to the parser.
Answer:
The lexical analyzer converts the source character stream into tokens by simulating a DFA constructed from regular expressions. Using the maximal munch principle, it recognizes the longest matching lexeme, strips whitespace/comments, and emits ⟨token_name, attribute_value⟩ pairs to the syntax analyzer.