Parsing & Applications of Grammars

a token

When you read, you do not process each letter on its own, you perceive whole words: 'the', 'cat', '42'. A token is the compiler's version of a word: the smallest meaningful unit the parser works with. The scanner's job is to turn a flood of characters into a tidy sequence of these tokens, so that the parser never has to look at individual letters again.

A token usually has two parts: a kind (its category) and sometimes an attached value. The kind is what the grammar cares about, IDENTIFIER, NUMBER, PLUS, LPAREN, the IF keyword, and so on. The actual characters that produced the token, called the lexeme, are remembered as the value when they matter: the token NUMBER carries the value 42, the token IDENTIFIER carries the name count. The grammar is written in terms of token kinds, never raw characters, so a rule like Stmt -> IF ( Expr ) Stmt talks about the IF token, not the three letters i, f. Keywords are usually just identifiers that the scanner recognizes as reserved and relabels.

Tokens are the interface contract between the scanner and the parser, and that clean boundary is why the two-stage design works. The scanner absorbs all the messy spelling details, decimal points, escape sequences, whitespace, comments, and presents the parser with a short, uniform alphabet of token kinds. In effect, the tokens become the terminal symbols of the grammar the parser uses, which is why the parser's input alphabet is so small even though the source text alphabet is huge.

From price = 9.99 the scanner emits four tokens: IDENTIFIER(price), ASSIGN, NUMBER(9.99), and end-of-line. The parser later sees only the kinds IDENTIFIER ASSIGN NUMBER; the literal text 9.99 rides along as the NUMBER token's value for later use.

A token = a kind (what the grammar sees) plus an optional value (the lexeme it matched).

A token kind is not the same as the exact text. Two different identifiers, foo and bar, are both the single token kind IDENTIFIER to the parser; only their attached value differs. The grammar reasons about kinds, not spellings.

Also called
lexeme classlexical token詞符詞法單元