Lexical analysis

Compiler front end and lexical analysis

Definition. A compiler translates a source program into a target form through stages such as scanning, parsing, semantic analysis, intermediate representation, optimization, and code generation. The lexical analyzer, or scanner, groups characters into tokens and reports lexical errors.

Example. The character sequence count<=limit can produce identifiers, a relational operator, and another identifier.

Exam point. Scanning recognizes token structure; grammar-based syntax is handled by parsing.

Solved example

Example — classify front-end work. For a = b + 12;, identify the scanner output and a parser task.

1. The scanner emits ID(a), ASSIGN, ID(b), PLUS, NUM(12), SEMICOLON.
2. It may attach the lexeme and numeric value to tokens.
3. The parser checks whether those tokens fit an assignment-statement production.
4. Token recognition is lexical; grouping tokens into a statement is syntactic.

Tokens, lexemes, and patterns

Definition. A token is a category such as ID or NUM. A lexeme is the actual character sequence matched, and an attribute carries extra information such as symbol-table pointer or numeric value. A token pattern describes the lexemes belonging to a category.

Example. In rate=7, rate is the lexeme of token ID and 7 is the lexeme of token NUM.

Exam point. Two different lexemes may map to the same token category but have different attributes.

Solved examples

Example 1 — token stream with attributes. Scan x12 + 004 assuming identifiers begin with a letter and continue with letters or digits, and integers are digit sequences.

1. x12 matches ID; its lexeme is stored, often with a symbol-table reference.
2. + matches PLUS.
3. 004 matches NUM; its lexeme is the text 004, while its numeric value may be 4.
4. Token sequence: ID(x12), PLUS, NUM(004,value=4).

Example 2 — keyword versus identifier. Why does while often need special treatment when the general identifier pattern also matches it?

1. The character pattern for an identifier may accept every letter sequence.
2. The scanner can first recognize the lexeme, then consult a reserved-word table.
3. If while is reserved, emit WHILE rather than ID.
4. Longest-match recognition alone does not distinguish reserved words from identifiers with the same spelling.

Regular expressions for token patterns

Definition. Regular expressions specify regular sets of lexemes using union, concatenation, and repetition. A scanner can implement these patterns with finite automata. Typical patterns cover identifiers, integer literals, whitespace, and operators.

Example. [A-Za-z][A-Za-z0-9]* describes identifiers beginning with a letter.

Exam point. A regular expression for a token pattern is not the same as a regular expression describing the whole programming-language syntax.

Solved examples

Example 1 — identifier membership. Under pattern [A-Za-z][A-Za-z0-9]*, classify Ab9, _x, and x_2.

1. Ab9 begins with a letter and all remaining symbols are allowed: valid.
2. _x begins with underscore, not a letter: invalid under this pattern.
3. x_2 contains underscore after the first character, also invalid.
4. Only Ab9 matches.

Example 2 — integer with optional sign. Give a pattern for an optional sign followed by at least one digit.

1. The sign is optional: [+-]?.
2. A digit is [0-9].
3. Require one digit, then allow more: [0-9]+.
4. Pattern: [+-]?[0-9]+.

Example 3 — longest operator. Patterns include =, ==, and ===. What token should the scanner emit for input === when all are valid operators?

1. At the current position, all three patterns match a prefix.
2. Maximal munch selects the longest match, length 3.
3. Emit the === token, unless language-specific rules say otherwise.

Finite automata implementation

Definition. Regular-expression token patterns can be compiled to NFAs and then to DFAs. A DFA scanner updates one state per input character; accepting states record the token class. If several token patterns accept, priority rules resolve ties after longest-match selection.

Example. A small DFA can recognize decimal integers by requiring one digit and then looping on digits.

Exam point. Lexer generator construction and runtime scanning are different activities: DFA construction is usually compile-time.

Solved examples

Example 1 — integer DFA trace. DFA states q0 (start), q1 (one-or-more digits, accepting), and dead. Digit from q0→q1, digit from q1→q1, other symbols leave the integer pattern. Trace 507.

1. q0 reads 5 and enters q1.
2. q1 reads 0 and stays q1.
3. q1 reads 7 and stays q1.
4. The lexeme 507 is accepted as NUM.

Example 2 — maximal munch with lookahead. Input is a<=b, with operators < and <=.

1. Starting at <, the scanner checks whether a longer token can continue.
2. The next character is =, so <= is the longest valid operator.
3. It emits LE and resumes at b.
4. The token sequence is ID(a), LE, ID(b).