Lexing and Parsing: Tokenization, Grammars, and Syntax Analysis

Compilers Compilers 8 min read 1573 words Beginner ExcellentWiki Editorial Team

Lexing (lexical analysis) and parsing (syntax analysis) are the first two phases of the classic compiler pipeline. Together, they transform raw source code — a stream of characters — into a structured representation (the abstract syntax tree, or AST) that the compiler’s later phases can analyze and transform. The lexer groups characters into tokens, discarding whitespace and comments. The parser arranges those tokens into a parse tree according to the language’s grammar. This article covers both phases in depth, including regular expressions for token definition, BNF grammars, recursive descent parsing, and practical issues like error handling and performance.

Lexical Analysis (Lexing)

The lexer, also called a tokenizer or scanner, reads the source character by character and groups them into tokens. Each token is a meaningful unit: a keyword, identifier, literal, operator, or delimiter.

Regular Expressions for Token Patterns

Lexers define token patterns using regular expressions. A regular expression describes a set of strings — the set of character sequences that form a given token type. Common patterns include:

Identifiers: [a-zA-Z_][a-zA-Z0-9_]*
Integer literals: [0-9]+
Floating-point literals: [0-9]+\.[0-9]+([eE][+-]?[0-9]+)?
String literals: "[^"]*"
Comments: //.* (single-line), /\*.*?\*/ (multi-line, using non-greedy match)

The lexer compiles these patterns into a deterministic finite automaton (DFA) using the subset construction algorithm described in the Dragon Book. The DFA runs in O(n) time, processing each input character exactly once. For each state, the DFA table lists the next state for each possible input character.

Lexer Generators

Writing lexers by hand is common for simple languages, but most production compilers use a lexer generator. Lex and its GNU counterpart Flex take a specification file with regular expression patterns and actions, and generate a C or C++ lexer. The generated code includes a DFA table and a simulation loop.

A Flex specification looks like:

%%
"if"        { return IF; }
"while"     { return WHILE; }
[a-zA-Z_]+  { yylval = strdup(yytext); return IDENTIFIER; }
[0-9]+      { yylval = atoi(yytext); return INTEGER_LITERAL; }
.           { /* skip whitespace */ }
%%

The generated lexer reads input, matches the longest possible token (maximal munch rule), and calls the action code. Maximal munch ensures that <= is recognized as a single token (less-than-or-equal) rather than < followed by =.

Hand-Written Lexers

Hand-written lexers are common in modern compilers. They are easier to debug, produce better error messages, and avoid the code-generation dependency. A hand-written lexer typically uses a large switch statement or a lookup table. Clang’s lexer is hand-written in C++ and processes over 100 MB of source per second, making it one of the fastest C/C++ lexers available.

Syntax Analysis (Parsing)

The parser takes the token stream from the lexer and builds a parse tree according to the language’s grammar. The grammar is defined in Backus-Naur Form (BNF) or Extended BNF (EBNF).

BNF Grammars

A BNF grammar consists of productions of the form:

<nonterminal> ::= <sequence of terminals and nonterminals>

For a simple expression language:

expression ::= term ('+' term | '-' term)*
term       ::= factor ('*' factor | '/' factor)*
factor     ::= INTEGER | '(' expression ')'

This grammar encodes operator precedence: multiplication binds tighter than addition because term appears before '+' in the expression production.

Recursive Descent Parsing

Recursive descent is the most intuitive parsing technique. For each nonterminal in the grammar, you write a function that consumes the corresponding tokens. The function calls other functions for sub-nonterminals, creating a call tree that mirrors the parse tree.

def parse_expression():
    left = parse_term()
    while peek() in ('+', '-'):
        op = consume()
        right = parse_term()
        left = AST.BinaryOp(op, left, right)
    return left

Recursive descent parsers are straightforward to write, produce excellent error messages (you can report exactly what was expected vs. found at each call site), and support arbitrary lookahead for disambiguation. Most production compilers with hand-written parsers use recursive descent: GCC (C/C++), Clang, rustc, Go, and many others.

The main limitation is that direct left recursion causes infinite recursion: A ::= A 'x' | 'y' would call parse_A() forever. The solution is to rewrite left-recursive rules using right recursion with iteration (EBNF’s * operator), which the recursive descent code handles with while loops.

Lookahead and Ambiguity

Recursive descent parsers typically use LL(1) or LL(k) lookahead. LL(1) means the parser looks at one token ahead to decide which production to apply. If the grammar requires more lookahead, the parser can peek further, but the code becomes more complex.

C++ is notoriously hard to parse because of the “most vexing parse” ambiguity: T x(a) can be a variable declaration or a function declaration depending on whether a is a type. Clang’s parser resolves this using several techniques: semantic information (whether a is known as a type at that point), disambiguation rules, and backtracking in ambiguous cases.

Parser Generators

Parser generators like Yacc, Bison, and ANTLR generate parsers from grammar specifications. Yacc and Bison generate LALR(1) parsers, which are bottom-up shift-reduce parsers. ANTLR generates LL(*) parsers, which are top-down with unlimited lookahead.

Bottom-up parsers (LALR) can handle a larger class of grammars than LL(1), but produce harder-to-read error messages. Top-down parsers (LL) handle a smaller grammar class but produce more intuitive error messages.

Error Handling During Parsing

When the parser encounters a syntax error, it must recover and continue to find additional errors. The standard techniques — panic mode, phrase-level recovery, and error productions — are covered in detail in Compiler Errors.

Performance Considerations

Lexing and parsing performance matters for developer productivity. A compiler that spends 50% of its time in the frontend directly impacts edit-compile-debug cycles.

Lexer Performance

Table-driven DFAs — fast but memory-intensive for large character sets. Optimized Flex output uses compressed DFA tables
Hand-written lexers — typically faster because they avoid the DFA dispatch overhead for common tokens. Clang’s lexer uses explicit character tests for fast paths
Memory-mapped input — avoiding read() system calls by memory-mapping the source file improves throughput

Parser Performance

Recursive descent overhead — function call overhead for every nonterminal is significant. Some parsers inline common rules
Goto-based generated parsers — Bison generates a goto-driven LALR parser that is very fast, at the cost of error message quality
Parallel parsing — GCC experimented with parallel frontend parsing but found that IO and lexing are the bottlenecks, not parsing

FAQ

What is the maximal munch rule? The lexer always matches the longest possible token. For example, >> is matched as a right-shift token (or two greater-than tokens in C++03 context), not as two > tokens. This rule prevents ambiguity in tokenization.

Can a lexer and parser be combined? Yes, this is called scannerless parsing. It avoids the overhead of separate phases but requires more complex grammars. PEG parsers (e.g., LPeg) often integrate tokenization into the grammar.

Why does C++ parsing require a symbol table? C++ is context-sensitive: T * x; could be a dereference of variable T times x, or a declaration of pointer x of type T. The parser needs the symbol table to know whether T is a type name. This interactivity between parsing and semantic analysis makes C++ particularly challenging.

What is the fastest parser generator? For most use cases, hand-written recursive descent is fastest for languages with simple grammars. For complex grammars like C++, Bison-generated LALR parsers perform well. ANTLR-generated LL(*) parsers are competitive for most practical grammars.

Incremental Parsing

Modern IDEs require incremental parsing — re-parsing only the parts of a file that changed after an edit, rather than re-parsing the entire file. Incremental parsing is essential for responsive code completion, syntax highlighting, and live error checking in editors.

Clang’s incremental parsing infrastructure reuses the existing AST and re-parses only the modified range and any regions whose parse depends on it. The Lexer supports “pre-lexing” tokens before the edited region to establish the correct lexer state. The Parser reuses existing AST nodes for unchanged regions and replaces only affected subtrees.

Parser generators rarely support incremental parsing directly. Hand-written recursive descent parsers are easier to adapt for incremental use because the parsing state is explicit in function calls and local variables, making it feasible to suspend and resume parsing at arbitrary points.

Error Recovery in Parsers

When a syntax error is detected, the parser must recover to continue finding errors in the same compilation. The three main recovery strategies each have tradeoffs:

Panic mode skips tokens until a synchronizing token (;, }, end) is found. It is simple, robust, and prevents cascading errors. Yacc/Bison use panic mode by default. The downside is that some errors after the recovery point may be missed.

Phrase-level recovery performs local corrections — inserting a missing semicolon, deleting an extraneous token, or replacing a token with a similar one. This produces better diagnostics (the compiler can say “missing semicolon”) but risks cascading errors if the correction is wrong.

Error productions extend the grammar with rules that match common mistakes. For example, a C grammar might include statement: error ';' to match any erroneous statement followed by a semicolon. This gives precise control over recovery behavior.

Clang uses a combination: panic mode for severe errors, phrase-level recovery for common patterns, and error productions for known frequent mistakes. The result is that Clang typically reports 5-10 errors per compilation where GCC reports 1-2 — Clang finds more real issues because it recovers better.