Yacc

Yacc — Yet Another Compiler-Compiler — is a parser generator: a program that reads a declarative description of a context-free grammar and writes out C source code for a parser that recognizes that grammar. Created by Stephen C. Johnson at Bell Labs in the early 1970s and canonically described in his 1975 technical report, Yacc turned parsing — once the hardest, most theory-laden part of writing a compiler — into something a working programmer could specify in an afternoon. Paired with Lex (its lexical-analyzer companion), it became one of the most influential software tools ever shipped: a standard Unix utility, a POSIX-specified interface, and the ancestor of a whole family of generators — GNU Bison, Berkeley Yacc, PLY, ocamlyacc, and many more — that still build the parsers inside today’s databases, shells, and languages.

History & Origins

Yacc was born from a small, concrete itch. Around 1971, Stephen Johnson wanted to add an exclusive-or operator to Dennis Ritchie’s B compiler and found hand-modifying the parser painful. His colleague Alfred Aho — co-author of the “dragon book” and a leading figure in parsing theory — suggested building on Donald Knuth’s LR parsing work from 1965, then still considered impractical for real machines. Their collaboration produced a generator that mechanically converted grammar rules into efficient table-driven parsers, and Aho and Johnson’s 1974 Computing Surveys article “LR Parsing” helped carry the underlying theory to practitioners.

The tool circulated inside Bell Labs early: versions of Yacc appear in the Research Unix manuals by 1973 (Version 3 Unix), though the language’s conventional birth year is 1975, when Johnson published “Yacc: Yet Another Compiler-Compiler” as Bell Labs Computing Science Technical Report No. 32. The self-deprecating name was a nod to the era’s proliferation of “compiler-compilers.” The same year, Mike Lesk and Eric Schmidt wrote Lex, a generator for the tokenizing front half of the job, and the lex & yacc pairing became the standard recipe for building language processors on Unix.

When Version 7 Unix shipped in 1979 with Yacc as a standard utility and Johnson’s paper in the manual, the tool rode Unix into universities and industry worldwide. Johnson himself used it to build the Portable C Compiler, demonstrating that generated parsers were good enough for production compilers — a genuinely contested question at the time.

Design Philosophy

Yacc’s core idea is separation of specification from implementation:

• Grammar as the program. You write what the language is — a set of BNF-style production rules — not how to parse it. Yacc computes the LALR(1) parse tables, handles the state machine, and lets you attach a fragment of C to each rule that runs when the rule is recognized.
• Theory made practical. Knuth’s full LR(1) tables were too large for 1970s memories; Yacc used the LALR(1) subset, which handles nearly all practical programming-language grammars with dramatically smaller tables. Yacc is arguably the single biggest reason LALR parsing dominated compiler construction for decades.
• Pragmatism over purity. Real grammars are ambiguous. Rather than reject them, Yacc offers declarations like %left, %right, and %nonassoc to resolve operator precedence and associativity declaratively — the famous if-then-else ambiguity is resolved by a sensible default rather than a demand that the user refactor the grammar.
• Host-language embedding. Yacc generates C and embeds user-written C actions, so the generated parser links into ordinary programs. This “generator + host language” architecture became the template for practically every parser generator since.

What a Yacc Grammar Looks Like

A grammar file has three sections — declarations, rules, and support code — separated by %%. A tiny calculator:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

%{
#include <stdio.h>
int yylex(void);
void yyerror(const char *s) { fprintf(stderr, "%s\n", s); }
%}

%token NUMBER
%left '+' '-'
%left '*' '/'

%%
input : /* empty */
      | input line
      ;

line  : expr '\n'        { printf("= %d\n", $1); }
      ;

expr  : NUMBER
      | expr '+' expr    { $$ = $1 + $3; }
      | expr '-' expr    { $$ = $1 - $3; }
      | expr '*' expr    { $$ = $1 * $3; }
      | expr '/' expr    { $$ = $1 / $3; }
      | '(' expr ')'     { $$ = $2; }
      ;
%%

The $$ and $1/$3 pseudo-variables refer to the semantic values of the rule’s left-hand side and its right-hand-side symbols; the %left declarations resolve what would otherwise be dozens of shift/reduce conflicts. Running yacc -d calc.y produces y.tab.c (the parser, exposing yyparse()) and y.tab.h (token definitions shared with the Lex-generated scanner), which are then compiled with an ordinary C compiler.

Key Features

Evolution: The Yacc Family

The original AT&T Yacc was encumbered by Unix licensing, and its very success invited reimplementation:

• GNU Bison grew out of an independent LALR generator Robert Corbett wrote in 1985 (originally “Byson”); made Yacc-compatible with Richard Stallman’s involvement, it became the free software world’s standard and has long since surpassed the original, adding reentrant parsers, better diagnostics, GLR parsing for grammars beyond LALR, and output in additional languages. Bison retains a strict Yacc-compatibility mode (bison -y), and its 3.x line — begun with Bison 3.0 in 2013, currently at 3.8.2 (2021) — is what most “yacc” builds actually run today.
• Berkeley Yacc (byacc), also by Corbett, was released into the public domain in 1989. Contemporary accounts note that, being unencumbered and faster than the AT&T version, it quickly became the most popular Yacc; Thomas E. Dickey has maintained it since 2002 and still publishes regular releases.
• Ports and reimplementations carried the format everywhere: ocamlyacc (OCaml), PLY — Python Lex-Yacc — by David Beazley, Racc and more recently Lrama (Ruby), goyacc (Go), and CUP-style tools on the JVM. Even parser generators that rejected Yacc’s algorithm, such as ANTLR’s LL-based line, defined themselves in reaction to it.

Standardization sealed the interface: POSIX.2 (IEEE Std 1003.2-1992) specified the yacc utility, its options, and its input format, and the current POSIX.1-2024 standard still includes yacc in its C-Language Development Utilities option — the POSIX specification itself even describes its own shell grammar in yacc notation.

Current Relevance

Half a century on, remarkably little production parsing has moved away from Yacc’s lineage. PostgreSQL, MySQL, and MariaDB define their SQL dialects in Bison grammars; Bash parses every command line through one; Brian Kernighan’s original awk still carries its Yacc grammar; and Ruby — whose grammar is among the most complex in mainstream use — moved in version 3.3 from Bison to Lrama, a new Yacc-compatible generator written in Ruby, precisely so it could keep its decades-old parse.y format. On most Unix-like systems a yacc command is still part of the standard development toolchain, typically provided by byacc or by Bison’s compatibility mode.

Yacc has competition it never had in 1975 — hand-written recursive-descent parsers (chosen by GCC and Clang for better error messages), PEG-based tools, and combinator libraries — and for new projects it is one option among many rather than the default. But as a POSIX-specified utility with two actively maintained implementations and an enormous installed base of grammars, it remains entirely alive: Active status earned the hard way, by being load-bearing infrastructure.

Why It Matters

Yacc is one of the clearest success stories of theory becoming a tool. Knuth’s LR parsing was elegant mathematics that looked computationally hopeless; within a decade, Yacc had packaged it so effectively that “write a grammar, generate the parser” became the ordinary way to build a language. It demystified compiler construction for a generation — the reason universities could ask undergraduates to build real compilers — and its grammar format became a lingua franca that outlived the original program, reimplemented in every era’s languages. Beyond parsing, Yacc stands as an early and enduring argument for declarative, generative programming: describe the what, let a tool derive the how. Every developer who has written a grammar file, and every user whose SQL query or shell command was parsed by one, is living downstream of Johnson’s itch to add one operator to the B compiler.