Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 61 ยท Parsing

Parser Generators and Tools

Compare Yacc and Bison, ANTLR, PEG parsers and parser combinators, then write a working parser-combinator calculator in Python from scratch.

You have now written a parser by hand (recursive descent) and seen how tables for a bottom-up parser are built (LR parsing). In practice, many projects do not code either of these directly. They describe the grammar in a compact notation and let a tool write the parser. That tool is a parser generator, and the idea goes back to the 1970s with the original Yacc.

This lesson tours the main kinds of tools: LALR generators such as Yacc and Bison, LL-style generators such as ANTLR, PEG parsers, and parser combinators, which are libraries rather than generators. You will implement a small parser-combinator library in Python, which is the best way to see how the pieces fit. The generators themselves cannot run on this site, so their examples are shown read-only.

What a parser generator does

A generator reads a grammar file with the rules and some semantic actions (small bits of code attached to rules) and writes a parser in a host language such as C, Java or Python. You still need a lexer: many generators come with a partner for that (Lex and Flex for Yacc and Bison), or integrate both (ANTLR).

flowchart LR
    G["Grammar file<br/>rules + actions"] --> T["Generator<br/>Bison, ANTLR, ..."]
    T --> P["Generated parser source"]
    P --> B["Compile with your project"]
    S["Source text"] --> L["Lexer"] --> B
    B --> R["Syntax tree or<br/>action results"]

The grammar is the specification. The generated parser is build output, usually not edited by hand.

The benefits are real: the grammar is the documentation, the generator checks it for ambiguity and conflicts, and changing the language means editing a few lines rather than rewriting functions. The costs are an extra build step, error messages that can be hard to customize, and a learning curve for the tool's conflict reports.

Yacc and Bison: LALR(1)

Yacc ("yet another compiler compiler") was written at Bell Labs in the 1970s. Bison is the GNU implementation and the one used today, together with the lexer generator Flex. They produce LALR(1) parsers in C (and other languages). A Bison file has three parts separated by %%: declarations, grammar rules, and extra code. Here is a calculator grammar, shown read-only:

TEXT
%define api.value.type {double}
%token NUMBER
%left '+' '-'
%left '*' '/'

%%
input : %empty
      | input line
      ;
line  : expr '\n'          { printf("%g\n", $1); }
      ;
expr  : expr '+' expr      { $$ = $1 + $3; }
      | expr '-' expr      { $$ = $1 - $3; }
      | expr '*' expr      { $$ = $1 * $3; }
      | expr '/' expr      { $$ = $1 / $3; }
      | '(' expr ')'       { $$ = $2; }
      | NUMBER
      ;
%%

Three things are worth noticing.

  • Actions are C code in braces. $$ is the value of the rule being reduced and $1, $3 are the values of its right-hand-side symbols. This is the syntax-directed translation idea in practice: values are computed during reductions.
  • The grammar expr : expr '+' expr | ... is ambiguous, which would produce shift/reduce conflicts. The %left lines resolve them. Operators on later lines bind tighter, and %left makes them left-associative. Without them, Bison would report conflicts and choose shift by default.
  • Bison prints a report of conflicts when it cannot decide, and you can ask for the state machine (--report=all). The item sets in that report are exactly the ones you built in the previous lesson.

ANTLR: adaptive LL

ANTLR (ANother Tool for Language Recognition) generates parsers in Java, Python, JavaScript, C# and other languages. Its lexer and parser rules live in one file. Parser rules begin with a lowercase letter, lexer rules with an uppercase letter:

TEXT
grammar Calc;

expr : expr ('*' | '/') expr
     | expr ('+' | '-') expr
     | NUMBER
     | '(' expr ')'
     ;

NUMBER : [0-9]+ ('.' [0-9]+)? ;
WS     : [ \t\r\n]+ -> skip ;

Compare this to the Bison file. The same ambiguous-looking rule is used, but ANTLR resolves it by alternative order: earlier alternatives bind tighter. It also accepts that direct left recursion, by rewriting it internally into a precedence-climbing loop, much like the techniques in Pratt parsing. ANTLR's algorithm, ALL(*), is a top-down method with adaptive, unbounded lookahead, so it accepts more grammars than a plain LL(1) parser. Instead of calling your actions inside the grammar, ANTLR builds a parse tree and gives you a listener or visitor to walk it, which keeps the grammar language-neutral. The tree walking pattern is the same as the visitor you will meet in abstract syntax trees.

PEG parsers

A parsing expression grammar looks like a context-free grammar but behaves differently: it describes a recognizer rather than a generator of strings. The key difference is the ordered choice operator /. In A / B, the parser tries A first, and if A succeeds, B is never tried. There is no ambiguity, because the first match always wins, and there is no separate lexer step: PEGs usually work directly on characters.

PEGs also provide lookahead predicates (&e succeeds if e matches without consuming, !e succeeds if it does not) and repetition built into the notation (e*, e+, e?). Most PEG implementations use packrat parsing: they memoize the result of each rule at each input position, which guarantees linear time at the cost of memory. CPython itself has used a PEG-based parser since Python 3.9.

The trade-offs:

  • Because of ordered choice, "a" / "ab" never matches ab completely. The order of alternatives is part of the meaning of the grammar, and a silent mistake is easy to make.
  • Plain left recursion (expr <- expr "+" term) loops forever in a simple implementation. Some tools rewrite it or use a special technique; otherwise you write it as repetition.
  • The language PEG defines can be hard to relate to its context-free grammar. There is no ambiguity report, since the grammar is deterministic by construction.

Parser combinators

A parser combinator library has no generator and no separate grammar file. A parser is just a function, and combinators are functions that build larger parsers from smaller ones. The grammar is written as ordinary code in the host language, so you can use loops, helper functions and the debugger. This style is popular in functional languages (Haskell's Parsec, Rust's nom, and many others), and it is simple enough to build in a page.

Our representation: a parser takes the text and a position, and returns either (value, new_position) or None for failure. The combinators are:

Combinator Meaning PEG notation
seq(a, b, ...) all in order a b
alt(a, b, ...) first that succeeds a / b
many(a) zero or more a*
apply(a, fn) transform the result semantic action
lazy(...) forward reference for recursion rule name
Python A parser combinator calculator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The grammar at the bottom reads like the grammar on paper: factor is a number or a parenthesized expression, term is a factor followed by any number of * factor or / factor, and so on. The apply calls attach the semantic action: fold collapses the list of operators and operands from left to right, which gives left associativity. We used repetition instead of left recursion, exactly the transformation from eliminating left recursion.

Note lazy: paren refers to expr, which is not defined yet when paren is created. Wrapping it in a function delays the lookup until parse time.

PEG behaviour you must know

The combinator library behaves like a PEG, so it inherits PEG's characteristics. The next example demonstrates three of them: ordered choice, the left-recursion trap, and why packrat memoization matters.

Python Ordered choice, left recursion and memoization

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first result is the one to remember: the order of alternatives changes what the grammar accepts. The second shows why you rewrite left-recursive rules as loops. The third shows memoization at work: the three alternatives all start with the same digit parser at position 0, and the cache turns three runs of that parser into one. In a real packrat parser every rule is cached at every position.

Choosing a tool

Tool type Parsing method Grammar class Typical use
Yacc / Bison LALR(1) most practical grammars; conflicts reported C and C++ projects, older language tools
ANTLR adaptive LL (ALL(*)) very wide; direct left recursion language tooling, many target languages
PEG generators packrat, ordered choice deterministic by construction modern small languages, Python's own parser
Parser combinators recursive descent in a library whatever the host code does embedded DSLs, config and data formats
Hand-written recursive descent one function per rule whatever you code GCC, Clang, Go, Rust compilers

Large production compilers often choose hand-written recursive descent despite the existence of generators. They want full control over error messages and error recovery, and good performance. For a small language, a DSL or a data format, a generator or combinator library saves time. Knowing how the tools work inside lets you read their conflict reports and decide sensibly.

Whatever tool you use, keep the grammar and the AST separate. Let the parser build a clean tree (see abstract syntax trees) and do the real work in later passes, rather than packing the whole compiler into semantic actions.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a parser generator like Bison take as input and produce?

    A generator reads a grammar description (with optional semantic actions) and writes the source code of a parser, which you then compile with your project.
  2. 2. In the Bison example, what is the job of the %left declarations?

    An ambiguous expression grammar has shift/reduce conflicts. Precedence declarations tell the generator which action to choose; later declarations bind tighter.
  3. 3. Why does the PEG choice alt(lit('a'), lit('ab')) fail to match the input 'ab' completely?

    In a PEG the first successful alternative wins and the parser does not go back to try the others. The order of alternatives is part of the grammar's meaning.
  4. 4. What does packrat parsing add to a PEG parser?

    Packrat parsers cache the result of every rule at every input position, so no work is repeated. The price is memory.
  5. 5. Which describes parser combinators?

    Combinators are ordinary functions that combine parser functions (sequence, choice, repetition), so the grammar is written as code in the host language.

Summary

  • A parser generator turns a grammar (with semantic actions) into parser source code; the grammar becomes the single source of truth for the syntax.
  • Yacc and Bison build LALR(1) parsers and use %left/%right declarations to settle ambiguity; ANTLR generates adaptive top-down parsers with walkers over a parse tree.
  • PEGs use ordered choice, so the order of alternatives matters and plain left recursion is a trap; packrat parsing memoizes for linear time.
  • Parser combinators are libraries where parsers are functions; sequence, choice, repetition and mapping are enough to write real grammars, as the calculator showed.
  • Large compilers often prefer hand-written recursive descent for control over errors, while generators and combinators suit smaller languages and data formats.
  • Keep the grammar separate from later compiler passes, and build a clean tree in the parser.

Next: Syntax-Directed Translation