Parsing Techniques: Recursive Descent, LR, PEG, and Parser Generators

Compilers Compilers 7 min read 1446 words Beginner ExcellentWiki Editorial Team

Parsing is the process of analyzing a sequence of tokens (produced by a lexer) to determine its grammatical structure according to a formal grammar. The choice of parsing algorithm affects the class of languages you can parse, the speed of parsing, the quality of error messages, and the maintainability of the parser. This article provides a detailed comparison of the major parsing techniques: recursive descent, LL, LR/LALR, PEG, and parser combinators. We cover each algorithm’s strengths and weaknesses, the grammar classes they support, and the production parsers that use them.

Recursive Descent Parsing

Recursive descent is the most widely used parsing technique for hand-written parsers. Each nonterminal in the grammar corresponds to a function that consumes the appropriate tokens and returns a parse tree node or boolean indicating success.

How Recursive Descent Works

For the grammar:

expr ::= term ('+' term)*
term ::= INTEGER

The parser functions are:

def parse_expr():
    left = parse_term()
    while peek() == '+':
        consume('+')
        right = parse_term()
        left = AST.BinaryOp('+', left, right)
    return left

def parse_term():
    return AST.Literal(consume(INTEGER))

Each function directly implements one production. The call stack at runtime mirrors the parse tree structure, making the code easy to debug and understand.

Handling Left Recursion

Direct left recursion — where a production starts with a recursive call to the same nonterminal — causes infinite recursion. For example, expr ::= expr '+' term | term would call parse_expr() recursively without consuming any input.

The fix is to rewrite the grammar: eliminate left recursion by using repetition (EBNF’s * or + operators) and convert to iterative code, as shown in the example above. This transformation is mechanical and well-documented in the Dragon Book.

Lookahead and Backtracking

Basic recursive descent is LL(1) — it decides which production to use based on a single lookahead token. If the grammar requires more lookahead, the parser can peek further (LL(k)) or backtrack on failure. Backtracking recursive descent calls a production speculatively; if it fails, the parser resets the input position and tries the next alternative.

Backtracking is powerful but can be exponential in worst case without memoization. Packrat parsing uses memoization to guarantee linear time for PEG grammars (discussed below).

LL Parsing

LL parsing (Left-to-right, Leftmost derivation) is the algorithmic foundation of recursive descent. An LL parser uses a parsing table built from the grammar to predict which production to apply given the current nonterminal and lookahead token.

LL(1) Parse Tables

The LL(1) parsing table is a matrix: rows are nonterminals, columns are terminals, and entries are production rules. The table is constructed by computing FIRST and FOLLOW sets for each nonterminal:

FIRST(A) — the set of terminals that can begin a string derived from A
FOLLOW(A) — the set of terminals that can appear immediately after A in a derivation

If every entry in the table has at most one production, the grammar is LL(1). Conflicts indicate ambiguity or insufficient lookahead.

Strengths and Limitations

LL(1) parsers are simple, fast, and produce clear error messages (you know exactly which terminal was expected). However, many practical grammars are not LL(1) — particularly those with left recursion, common prefixes (the “dangling else” problem), or operator precedence.

LL(k) extends the lookahead to k tokens, resolving more conflicts but producing much larger parse tables. ANTLR uses LL(*) — arbitrary lookahead with DFA-based prediction — which handles most C++-level grammar complexity.

LR and LALR Parsing

LR parsing (Left-to-right, Rightmost derivation in reverse) is a bottom-up technique that can handle a larger class of grammars than LL. LR parsers are generated from the grammar by tools like Yacc and Bison.

Shift-Reduce Parsing

An LR parser maintains a stack of grammar symbols and uses a state machine to decide between two actions:

Shift — push the next input token onto the stack and transit to a new state
Reduce — pop the right-hand side of a production off the stack, push the left-hand side nonterminal, and transit to a new state

The parser’s action and goto tables encode the transitions. These tables are built algorithmically from the grammar — a process that may produce conflicts (shift-reduce or reduce-reduce) that the grammar author must resolve.

SLR, LALR, and Full LR

SLR (Simple LR) — uses FOLLOW sets for reduce decisions. Weakest LR variant, fewest grammars supported.
LALR(1) (Look-Ahead LR) — merges similar states from the full LR(1) automaton, producing smaller tables. Supports most programming language grammars. Yacc and Bison generate LALR(1) parsers.
Full LR(1) — most powerful table-based LR variant. Produces large tables (thousands of states). Used when LALR conflicts cannot be resolved.

When to Use LR

LR parsers are ideal for generated parsers where grammar correctness is more important than error message quality. Bison-generated parsers are used in many production compilers (parts of GCC, PHP, Ruby). The main disadvantage is that LR parse errors are harder to translate into helpful diagnostics — you get “syntax error” at the point where the parser has no valid action, which may be far from the actual mistake.

PEG (Parsing Expression Grammar)

PEG parsing, introduced by Bryan Ford in 2004, takes a fundamentally different approach. A PEG grammar describes a recursive descent parser with ordered choice — the alternative that matches first wins, rather than the alternative that would eventually lead to a valid parse.

PEG Syntax

Expr      <- Term ( '+' Term )*
Term      <- Factor ( '*' Factor )*
Factor    <- INTEGER / '(' Expr ')'
INTEGER   <- [0-9]+

The / operator is ordered choice: try the left alternative first; if it fails, try the right one. Unlike CFG grammars (used by LL/LR), PEGs are unambiguous by construction — there is no ambiguity because the ordered choice always picks the first match.

Packrat Parsing

Packrat parsing memoizes parse results for each position and nonterminal pair. This guarantees linear-time parsing for any PEG grammar, at the cost of O(n * |nonterminals|) memory. LPeg (Lua) and Rust’s pest are popular PEG parser implementations.

PEGs are increasingly popular for DSLs and configuration languages. They eliminate the grammar conflicts that plague LR parsers and produce better error messages than table-driven approaches.

Parser Combinators

Parser combinators are higher-order functions that compose smaller parsers into larger ones. Each combinator takes one or more parsers as arguments and returns a new parser.

val expr: Parser[AST] = term ~ (plus ~ term).* ^^ { ... }
val term: Parser[AST] = integerLiteral | parens(expr)

Parser combinators are available as libraries in many languages: Parsec (Haskell), Nom (Rust), Pyparsing (Python), and FastParse (Scala). They provide the readability of recursive descent with the composability of function combinators.

Advantages include:

Embedded in a host language — no code generation step, no separate grammar file
Type-safe — the parser return type is checked by the host language’s type system
Composable — parsers are first-class values that can be passed to combinators

The main disadvantage is parsing speed: combinator-based parsers are typically slower than table-driven or hand-written parsers because of function call overhead and intermediate data structures.

Choosing the Right Technique

Criteria	Recursive Descent	LR/LALR	PEG	Parser Combinators
Grammar class	LL(k)	LR(k)	PEG (any deterministic)	LL(∞) with backtracking
Implementation	Hand-written	Generated	Generated or hand	Library
Error messages	Excellent	Poor	Good	Good
Speed	Very fast	Very fast	Fast	Moderate
Maintainability	Good	Poor	Good	Good
Left recursion	Must eliminate	Supported	Not supported	Must eliminate

FAQ

What is the “dangling else” problem? In languages where if-then-else has optional else, the grammar stmt ::= if expr then stmt | if expr then stmt else stmt is ambiguous: an else clause could attach to either the inner or outer if. LL parsers resolve this by preferring shift (matching the else to the innermost if); Bison uses %prec to declare the shift preference.

Can I use LR parsing for a DSL? Yes. If you need to handle complex expressions with infix operators and precedence, LR parsing is well-suited. Yacc/Bison are proven tools for DSL grammars. However, PEG parsing is now more popular for new DSLs because it avoids LR conflicts.

How do I handle operator precedence in recursive descent? Write separate nonterminals for each precedence level. For standard arithmetic: expr ::= term (('+' | '-') term)*, term ::= factor (('*' | '/') factor)*, factor ::= INTEGER | '(' expr ')'. Each level handles one precedence, and the parser naturally respects the ordering.

What parser does Clang use? Clang uses a hand-written recursive descent parser with extensive backtracking and semantic disambiguation. This gives Clang the best error messages of any C++ compiler, at the cost of code complexity.