Lexical analysis: tokens, automata and longest match
Goal and conventions
Separate characters, lexemes, tokens and attributes; simulate a scanner without confusing it with a parser. A token is a category such as ID or NUM. A lexeme is the actual source substring, such as count or 42. An attribute can hold a numeric value or a symbol-table reference. We ignore whitespace and comments only when the stated language permits it. EOF marks the end of input and is not a source character.
1. Compiler phases and what the scanner can decide
A typical front end scans characters into tokens, parses tokens using a context-free grammar, and performs semantic checks such as declaration and type consistency. A syntactically valid expression can still have a type error. Finding an identifier token does not prove that the identifier has been declared. The symbol table can be shared across phases; lexical recognition and scope resolution are different jobs.
For our miniature language let letter=[A-Za-z], digit=[0-9], ID=letter(letter|digit)* and NUM=digit+. Add keyword IF for the exact spelling if, and operators =, ==, +, ++, <, <= and ;. In this lesson identifiers cannot begin with an underscore, numeric literals have no decimal point, and comments are absent unless explicitly introduced. These are example rules, not claims about every language.
2. Longest match, then priority
At the current input position, select the longest prefix recognized by any token rule. Only when two rules recognize the same maximum-length prefix use their priority order. Put IF before ID, so if becomes IF but if2 becomes one ID. Choosing a high-priority rule before checking length would incorrectly split if2. If no nonempty prefix is recognized, report a lexical error under these rules; do not silently discard an unknown character.
Worked trace for if2<=10++x;:
- Starting at i, ID accepts i, if, if2; IF accepts if. Longest accepted prefix is if2, so emit ID(if2).
- At <, both < and <= are possible. <= is longer, so emit LE.
- At 1, NUM accepts 1 and 10, then stops before +. Emit NUM(10).
- At +, ++ beats +. Emit INC.
- x becomes ID(x), and ; becomes SEMI.
There are six tokens. The scanner can produce this stream even if the parser later rejects the arrangement of operators. Token counts count occurrences, not distinct token categories. Whitespace is not required between tokens when boundaries can be inferred from the rules.
3. Automata and the last accepting position
Regular expressions specify token patterns. One construction builds an epsilon-NFA for the union of patterns, tags accepting states with token identities, and applies subset construction to obtain a DFA. A DFA state is a set of NFA states; include epsilon-closure when starting and after each character transition. Several accepting token tags in one DFA state are resolved by the given priority.
A scanner must remember its most recent accepting state and input position, not merely stop at the first accepting state. Example rules are A=ab and B=abcd. On input abcx, states after a and abc are nonaccepting, after ab accepts A, and after abcd would accept B. Reading x fails. Rewind to the position after ab and emit A(ab); scanning then restarts at c, which is an error if no token begins with c. The unsuccessful lookahead characters were not part of token A.
For the simpler ID rule, after reading the first letter the DFA is accepting; later letters/digits loop in an accepting state. A delimiter ends the run but is left for the next token. Buffering implementations may use sentinels and retract operations; those are implementation details, not extra tokens.
4. Scope limits and common traps
Finite automata suffice for ordinary regular token patterns. Arbitrarily balanced nested parentheses are normally handled by parsing, not a finite-state scanner alone. Similarly, unrestricted nested comments require more than a plain finite automaton; do not infer regularity merely because the construct is called a comment. Some scanners use extra counters or modes beyond their basic DFA.
- Maximal munch can produce a token sequence that fails syntax checking; it does not search for the tokenization that makes the whole program valid.
- Keywords can be priority rules or identifier-table lookups after matching the complete identifier.
- The empty string must not be an ordinary repeatedly emitted token: it would prevent progress.
- Under the declared rules, @ is an error, whereas an undeclared but well-formed identifier is a later semantic issue.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. With IF before ID and maximal munch, if2 is:
A. IF then NUM B. One ID C. Three IDs D. Lexical error
Answer: B
A: Priority does not override a longer match.
B: The ID pattern consumes all three characters.
C: Longest match joins the letters and digit.
D: The declared ID pattern permits a trailing digit.
P02. How many token occurrences are in if2<=10++x; under the lesson rules?
A. 5 B. 6 C. 7 D. 11
Answer: B
A: The semicolon is also a token.
B: ID, LE, NUM, INC, ID, SEMI are six occurrences.
C: Neither <= nor ++ splits.
D: Character count is not token count.
P03. For rules ab and abcd, scanning abcx first emits:
A. abc B. abcd C. ab D. Nothing, even though ab matched
Answer: C
A: abc is not an accepted token.
B: The input does not contain abcd.
C: Return to the last accepting position after ab.
D: The earlier accepted prefix remains available.
P04. Which is a lexeme rather than a token category?
A. ID B. NUM C. The source substring count D. The class of all identifiers
Answer: C
A: ID names a category.
B: NUM names a category.
C: count is a particular matched substring.
D: A class is not a particular occurrence.
P05. Which task normally needs semantic information beyond token recognition?
A. Recognize ++ B. Skip a permitted space C. Recognize digits D. Check whether x is declared in scope
Answer: D
A: A finite pattern identifies ++.
B: Whitespace can have a lexical rule.
C: Digits fit a regular pattern.
D: Declaration and scope require context beyond this scanner.
P06. A plain finite automaton alone cannot recognize which language?
A. All digit strings B. Identifiers from the given regular expression C. The finite keyword set D. Arbitrarily deeply balanced parentheses
Answer: D
A: Digit strings are regular.
B: This pattern is regular by construction.
C: Every finite language is regular.
D: Unbounded nesting requires memory not supplied by finitely many states.
Sources and scope
Aligned to the official 2026 course. This lesson covers a bounded topic slice; no claim of 2027 completeness. All examples and exercises are original.
Sign in to keep your progress. Sign in