3.1 Tokens, Lexemes, Patterns, and Token Streams

Lexical analysis is the first compiler phase that turns raw source text into a structured representation. The input is a sequence of characters. The output is a sequence of tokens. That sounds simple, but the boundary is an important engineering contract: every later frontend phase depends on the lexer to preserve enough information for syntax, diagnostics, formatting, IDE features, and source mapping.

A token kind is a category such as IDENT, INT, IF, PLUS, LPAREN, or EOF. A lexeme is the exact source substring matched for a token. A pattern describes the set of lexemes that belong to a token kind. A token is usually a record that combines the kind, lexeme, source location, and sometimes extra metadata.

For example, in:

let total = price + tax;

the lexeme total may produce token IDENT("total"), while the lexeme let may produce token LET("let"). Both are alphabetic strings, but the lexer policy classifies one as a keyword and the other as an identifier. That policy must be deterministic because the parser will not re-interpret raw characters.

Token Records

A production token record often contains more than a kind:

type Token = {
  kind: TokenKind;
  lexeme: string;
  startOffset: number;
  endOffset: number;
  line: number;
  column: number;
  channel: "default" | "trivia" | "error";
};

The kind is what the parser primarily consumes. The lexeme keeps the original text. The offsets support tooling and source maps. The line and column support human-readable diagnostics. The channel tells whether the token is parser-visible, trivia such as whitespace/comment, or an error token.

If a lexer emits only token kinds, it may be enough for a toy parser, but not for a serious compiler. A diagnostic cannot underline the exact bad character if the lexer discarded offsets. A formatter cannot preserve comments if the lexer threw them away. An IDE cannot implement "go to token under cursor" if tokens do not know their ranges.

Patterns Define Token Languages

Each token kind has a language: the set of lexemes that may produce that token. Some languages are finite. LET may be exactly {let}. PLUS may be exactly {+}. Other languages are infinite. IDENT might be every string that begins with a letter or underscore and continues with letters, digits, or underscores. INT might be every non-empty digit sequence.

Typical token patterns for a small language:

IDENT  = [A-Za-z_][A-Za-z0-9_]*
INT    = [0-9]+
FLOAT  = [0-9]+ "." [0-9]+
STRING = "..." with escape handling
WS     = [ \t\r\n]+

The formal regular expression can describe most of the shape, but the implementation may still carry policy. Are Unicode identifiers allowed? Are leading zeroes legal? Does 2. mean FLOAT(2.), or INT(2) followed by DOT? Are comments skipped or preserved as trivia? These are language-design decisions, not accidents.

The Token Stream Is a Phase Boundary

The lexer-parser boundary should be boring in the best possible way. The parser should not need to know how comments are recognized, how escape sequences are scanned, or whether the lexer came from a generator. It should receive a stable token stream and make grammar decisions from token kinds and values.

For the source:

if x == 10 // ok

a useful default-channel token stream could be:

IF       "if"    line 1, col 1
IDENT    "x"     line 1, col 4
EQEQ     "=="    line 1, col 6
INT      "10"    line 1, col 9
EOF      ""      line 1, col 17

Whitespace and the line comment may be skipped for parsing, but they should not necessarily disappear from the compiler ecosystem. Formatters, refactoring tools, documentation extractors, and IDEs often need trivia. Many compilers therefore keep parser-visible tokens and trivia in related streams, or attach leading/trailing trivia to nearby tokens.

EOF deserves special attention. It is not a character in the source file, but it is a token-like sentinel for the parser. It should carry a location so the parser can report precise messages such as "expected } before end of file."

A Token Is a Contract, Not Just a String

A robust token commonly stores kind, original lexeme, a half-open byte/character range [start, end), line/column data or a line map, and an optional decoded value. For "a\\n", the lexeme includes quotes and escape spelling while the decoded string value contains two characters: a and newline. Keeping both prevents diagnostic and semantic code from fighting over what “the token text” means.

Use token kinds for grammar decisions and payloads for later meaning. INT("0042", value=42) lets the parser recognize INT without caring how the integer was spelled; the AST can preserve the original text for formatting or warning policies. EOF should be an explicit zero-width token at the end of the file, not a special null pointer; that makes parser acceptance and unterminated-construct diagnostics uniform.

Stream Invariants

• Token ranges must be monotonic and non-overlapping, except intentional synthetic recovery tokens.

• Whitespace/comments are either discarded consistently or emitted as trivia consistently; mixing the two causes formatter and parser bugs.

• Every lexer iteration consumes at least one source unit or returns EOF/error. This simple invariant prevents hangs.