Tokens and Lexemes
Sixteen characters become six tokens — longest match, discarded whitespace, and a symbol table.
Skip to the animationLexical analysis groups characters into the smallest meaningful units — tokens — discarding whitespace and comments, and recording identifiers in the symbol table.
Token, lexeme, pattern
- Token
- The category the parser sees —
id,num,assign. The grammar is written entirely in terms of these. - Lexeme
- The actual characters matched —
rate,60. Kept as an attribute, because the parser does not need it but later phases do. - Pattern
- The rule describing which lexemes belong to a token. Always a regular expression, which is what makes the scanner a finite automaton.
rate and pos are different lexemes and the same token. That collapsing is the point: the grammar cannot enumerate every possible identifier, so the scanner reduces infinitely many strings to one category.
The two disambiguating rules
- Longest match. Having started a lexeme, keep consuming while the result is still valid.
posis one identifier, not three.<=is one operator, not two. Without this rule almost every pattern would be ambiguous. - Rule priority. When two patterns match the same longest string, the one listed first wins. This is how
ifbecomes a keyword rather than an identifier — though most scanners instead match it as an identifier and then look the lexeme up in a table of reserved words, which keeps the automaton much smaller.
Why this phase is a DFA
Every token pattern — identifiers, numbers, operators, string literals, comments — is regular. So the scanner is exactly a finite automaton, generated from the patterns by the standard pipeline: regular expression → NFA → DFA → minimise.
That is what lex and flex do, and it is why lexical analysis is the fastest phase in the compiler: one table lookup per character, no backtracking, linear in the size of the source.
It also explains the limits. A regular language cannot count, so a scanner cannot match nested comments — that is why /* /* */ ends the comment early in C.
What it catches, and what it cannot
The scanner only detects errors local to a single lexeme: an illegal character, an unterminated string, a malformed number. It has no notion of whether the tokens make sense together — = = pos * ; scans perfectly into five valid tokens.
Structure is the parser's job and meaning is the semantic analyser's. Each phase catches exactly the errors its formalism can express, which is why the phases exist in this order.
Advantages and disadvantages
Advantages
- Simplifies every later phase — the parser never sees whitespace, comments or raw characters.
- Linear time, one table lookup per character, no backtracking.
- Generated automatically from regular expressions rather than written by hand.
Disadvantages
- Cannot express anything non-regular, so nested comments are out of reach.
- Longest match occasionally fights the language design — C's
>>in nested templates is the classic case. - Error messages are necessarily local and often unhelpful on their own.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.