Raw source code is a character string, but the grammar of a programming language operates on meaningful syntactic units (keywords, identifiers, operators). Without a token abstraction, the parser would need to match individual characters, making grammar rules exponentially more complex.
A token is a pair consisting of a token class (or token type) and an optional attribute value. A lexeme is the actual character sequence matched from the source. For example, in count = 42, the lexeme count maps to token class <id> with attribute value pointing to the symbol table entry for count.
The lexer groups characters into lexemes by matching patterns (regular expressions). Each lexeme is classified into a token class. Keywords have dedicated token classes (IF, WHILE). Identifiers all share the <id> class but carry different attribute values. The token stream is the parser’s input alphabet.
- Two components: Token class (type) + attribute value (optional)
- Lexeme vs Token: Lexeme is the character string; token is the classified pair
- Token classes: Keywords, identifiers, operators, delimiters, literals
- Attribute values: Symbol table pointers, constant values, or null
- Parser alphabet: The parser reads tokens, not characters
- Built from: Lexical Analysis — the lexer produces the token stream
- Builds into: Syntax Analysis — the parser consumes tokens as terminal symbols
- Related: Symbol Table — identifier token attributes point to symbol table entries
- Related: Phases of a Compiler — token generation is the output of phase 1
- Keywords vs Identifiers: In most languages, keywords are reserved and not usable as identifiers — the lexer checks this
- Maximal munch:
>=is one token, not>then= - Semicolons and delimiters: Even single characters like
;are tokens — the parser needs them for grammar structure