Lexical Analysis

The lexical analyser (scanner, lexer) is the first phase of a compiler. It reads the source text character by character, groups the characters into meaningful units called lexemes, and passes one token per lexeme to the parser. It also removes comments and whitespace, keeps track of line numbers for error messages, and enters identifiers into the symbol table.

The patterns that describe tokens are regular, so the scanner is a deterministic finite automaton with actions attached to its accepting states. Scanner generators such as Lex and Flex build that automaton automatically from a list of regular expressions. In examination questions the scanner appears mostly through token counting, the longest-match rule, and the classification of errors.

The token name is what the grammar of the parser uses as a terminal symbol. Typical token classes are: keywords (one token name per keyword, or one shared name with an attribute), identifiers, constants (numbers, character constants), string literals, operators, and punctuation such as parentheses, commas and semicolons.

One token per lexeme. A token is one occurrence. The statement count = count + 10; has 6 tokens (count, =, count, +, 10, ;) even though count appears twice; both occurrences become tokens with the same symbol-table attribute.

At each point the scanner takes the longest prefix of the remaining input that matches some pattern. If two patterns match the same longest prefix, the pattern listed first wins. These two rules settle every token-counting question.

Token patterns are written as regular definitions, names for regular expressions that may use earlier names:

A scanner generator converts each pattern to an NFA, joins them under a new start state, and applies the subset construction (see Deterministic Finite Automata). Each accepting DFA state is labelled with the first-listed pattern among those it accepts. To find the longest match, the scanner keeps running the DFA until it has no move, remembering the last accepting state it passed and the input position at that moment; it then retracts the input to that position and returns that token.

Example with three patterns, listed in this order: the keyword if, identifiers [a-z][a-z0-9]*, and numbers [0-9]+. The combined DFA has five live states:

On input ifx the DFA passes 0, 1, 2, 3 and stops at the end of the lexeme in state 3, so it returns one identifier. On input if( it reaches state 2 and has no move on (, so it returns the keyword if. On i9 it returns one identifier. These five states are all distinguishable (states 1 and 3 accept the same token but differ on f), so the DFA is minimal.

Hand-written scanners use transition diagrams: a state per prefix seen, edges labelled by characters, and accepting states marked with the token to return. Some accepting states are marked "retract": the scanner has read one character beyond the lexeme (to be sure the lexeme has ended) and must push it back. For relop:

Reading one character at a time from a file is slow, and the scanner must sometimes look ahead before it knows where a lexeme ends. The standard scheme uses a buffer of two halves (each of $N$ characters, typically one disk block) and two pointers: lexemeBegin marks the start of the current lexeme, and forward scans ahead. When forward reaches the end of one half, the other half is reloaded.

Without help, each advance of forward needs two tests: "end of this half?" and "which character is it?". A sentinel (a special end-of-file character placed at the end of each half) folds both into one: the scanner tests only for the sentinel, and only on seeing it does it check whether the half ended or the input ended. A lexeme longer than the buffer cannot be handled; in practice a lexeme is limited to well under $N$ characters.

A lexical error occurs when no pattern matches any prefix of the remaining input: an illegal character such as @ or ` `` in C source outside a literal, or a string literal or comment that never ends. The simplest recovery is panic mode: delete characters from the remaining input until a well-formed token can be found. Other single-character repairs are deleting one character, inserting a missing one, replacing one, or transposing two adjacent characters.

A Lex specification has three parts separated by %%: declarations (regular definitions and C declarations), translation rules (pattern followed by an action in braces), and auxiliary functions. The generated function yylex() returns one token per call; yytext points to the lexeme and yyleng holds its length. Conflicts are resolved by the two rules above: longest prefix, then earliest rule. The lookahead operator / in a pattern r1/r2 matches r1 only when it is followed by r2, without consuming r2.

Counting convention: one token per lexeme; comments, whitespace and preprocessor lines produce none; a string literal (including its quotes and any escaped quotes inside) is one token.

More fragments that test the rules at their edges:

A comment opened by accident. Without the blank, x=y/*p; does not divide by *p: longest match reads /* as the start of a comment. If no */ follows anywhere later in the file, the scanner reports an unterminated comment, a lexical error. If a */ does appear later, everything up to it silently disappears, and the parser reports whatever error results. The blank in y/ *p (or parentheses, y/(*p)) gives the intended 7 tokens.

A larger one:

Tokens: int main ( ) { int a = 10 , * p = & a ; return a ++ + * p ; }, a total of 24. This is a token-count exercise only: evaluating a+++*p has undefined behaviour in C because p aliases a, and the modification by a++ is unsequenced relative to the read through *p. It is not an output-prediction example. The comment contributes nothing, a+++*p splits as a, ++, +, *, p, and the * in *p is one token whether it means multiplication or dereference; the scanner does not decide which.

Escaped quote. In char *s = "a\"b"; the literal "a\"b" is one token, because \" does not end the string: 6 tokens in all.