Chapter 18 of 33

Yacc & Bison

Building an LALR(1) table by hand for a 4-production grammar takes half an hour. A real programming language has hundreds of productions. Nobody builds those tables by hand: we write the grammar down and let a parser generator do the work.

Yacc ("Yet Another Compiler-Compiler"), written by Stephen C. Johnson at Bell Labs in the 1970s, was the first widely used one. GNU Bison is its free, upward-compatible successor and the one you will actually install today. Both read a grammar with C code attached to each production and produce a C file containing an LALR(1) parser, the same kind of parser we built in LALR Parsing.

Yacc/Bison takes a context-free grammar with semantic actions and generates a C function yyparse() that parses its input with an LALR(1) table, calling yylex() for tokens and running each production's action when that production is reduced.

Everything in this chapter was built and run with flex 2.6.4, bison 3.8.2 and gcc on Linux. The outputs shown are the real outputs.


Where Yacc Fits

In Lex & Flex we generated a scanner, yylex(), that returns one token per call. Yacc generates the parser that calls it:

   calc.l ──► flex ──► lex.yy.c ───────────┐
                                           ├──► gcc ──► calc (executable)
   calc.y ──► bison -d ──► calc.tab.c ─────┘
                       └─► calc.tab.h  (token codes, #included by calc.l)

At run time:
   yyparse()  ──"next token?"──►  yylex()
              ◄── token code ───  (and its value in yylval)

Lex / Flex

Yacc / Bison

Phase

Lexical analysis

Syntax analysis (plus actions for translation)

Input specification

Regular expressions

Context-free grammar

Generated machine

DFA

LALR(1) shift-reduce parser (a pushdown automaton)

Generated function

yylex()

yyparse()

Output file

lex.yy.c

y.tab.c (Yacc) or name.tab.c (Bison)


Structure of a Yacc File

A Yacc file has the same three-part layout as a Lex file, separated by %%:

%{
    C declarations (copied to the top of the output)
%}
    Yacc declarations: %token, %left, %right, %nonassoc, %start, %type ...
%%
    Grammar rules with actions
%%
    User C code (main, yyerror, helper functions ...)

Writing rules

nonterminal : body1    { action1 }
            | body2    { action2 }
            ;
  • Names declared with %token are terminals; any other name that appears on a left side is a nonterminal. The first rule's left side is the start symbol unless %start says otherwise.

  • A single character in quotes, such as '+', is a terminal whose token code is that character's code. Named tokens get codes from 258 upward.

  • An empty body (written as nothing, or %empty in Bison) is an ε-production.

Semantic values: $$ and $n

Every symbol on the parser stack carries a value. In an action, $1, $2, … are the values of the body symbols, and $$ is the value of the left-hand side being created.

expr : expr '+' expr   { $$ = $1 + $3; }   /* $2 would be the '+' token */
  • For a token, the value is whatever the scanner stored in yylval before returning it.

  • If a rule has no action, the default is $$ = $1.

  • By default values are int (YYSTYPE). Real parsers use %union with %token <type> / %type <type> to store different kinds of values (numbers, strings, tree nodes).

Actions run at the moment the production is reduced. Since an LR parser reduces in bottom-up order, the values of all children are ready before the parent's action runs. This is exactly how synthesized attributes work, which we will study in Syntax-Directed Definitions.


Example 1: Watching the LR Parser Work

This first program has no scanner file. It contains a tiny hand-written yylex() and uses the familiar expression grammar. Each action just prints the production being reduced.

%{
#include <stdio.h>
#include <ctype.h>
int yylex(void);
void yyerror(const char *msg);
%}

%token ID

%%
E : E '+' T   { printf("reduce E -> E + T\n"); }
  | T         { printf("reduce E -> T\n"); }
  ;
T : T '*' F   { printf("reduce T -> T * F\n"); }
  | F         { printf("reduce T -> F\n"); }
  ;
F : '(' E ')' { printf("reduce F -> ( E )\n"); }
  | ID        { printf("reduce F -> id\n"); }
  ;
%%

/* A hand-written scanner: letters are identifiers, the rest are single-char tokens. */
int yylex(void) {
    int c;
    while ((c = getchar()) == ' ' || c == '\t')
        ;
    if (c == EOF || c == '\n') return 0;      /* 0 means end of input */
    if (isalpha(c)) {
        while (isalnum(c = getchar()))
            ;
        ungetc(c, stdin);
        return ID;
    }
    return c;
}

void yyerror(const char *msg) { printf("error: %s\n", msg); }

int main(void) {
    if (yyparse() == 0) printf("accepted\n");
    return 0;
}

Build and run:

$ bison -v expr.y            # creates expr.tab.c (and expr.output, because of -v)
$ gcc -Wall expr.tab.c -o expr
$ echo 'a * b + c' | ./expr
reduce F -> id
reduce T -> F
reduce F -> id
reduce T -> T * F
reduce E -> T
reduce F -> id
reduce T -> F
reduce E -> E + T
accepted

This is the same sequence of reductions as the SLR trace of id * id + id in SLR Parsing: a rightmost derivation in reverse. Now a wrong input:

$ echo 'a + * b' | ./expr
reduce F -> id
reduce T -> F
reduce E -> T
error: syntax error

The parser reduced a all the way to E, shifted +, then found no action for * and called yyerror.

Reading the .output file

With -v, Bison writes a human-readable description of every state. Here are two of them:

State 4

    2 E: T •
    3 T: T • '*' F

    '*'  shift, and go to state 9

    $default  reduce using rule 2 (E)


State 5

    4 T: F •

    $default  reduce using rule 4 (T)

State 4 is our old friend { E → T •, T → T • * F }. Two things to notice:

  • Bison numbers the states in its own order, and adds a rule 0 $accept: E $end plus one extra state for shifting $end. So this grammar has 13 Bison states instead of the 12 in our hand-built table.

  • $default reduce. Instead of listing r2 under +, ) and $, Bison makes the most common reduction the default for every token without a shift. This shrinks the table. The cost is the one we saw in LALR Parsing: on a bad token the parser may reduce before reporting the error, but it still never shifts the bad token.


Example 2: A Calculator with Flex and Bison

Now a realistic setup: a Flex scanner plus a Bison parser that evaluates expressions line by line. The grammar is ambiguous on purpose (expr '+' expr), and precedence declarations tell Bison how to resolve it.

The parser: calc.y

%{
#include <stdio.h>
int yylex(void);
void yyerror(const char *msg);
%}

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

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

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

expr  : expr '+' expr    { $$ = $1 + $3; }
      | expr '-' expr    { $$ = $1 - $3; }
      | expr '*' expr    { $$ = $1 * $3; }
      | expr '/' expr    {
                           if ($3 == 0) { yyerror("division by zero"); $$ = 0; }
                           else $$ = $1 / $3;
                         }
      | '-' expr %prec UMINUS { $$ = -$2; }
      | '(' expr ')'     { $$ = $2; }
      | NUMBER           { $$ = $1; }
      ;
%%

void yyerror(const char *msg) {
    fprintf(stderr, "error: %s\n", msg);
}

int main(void) {
    return yyparse();
}

The scanner: calc.l

%{
#include <stdlib.h>
#include "calc.tab.h"
%}
%option noyywrap noinput nounput

%%
[0-9]+      { yylval = atoi(yytext); return NUMBER; }
[ \t]+      ;                      /* skip blanks */
\n          { return '\n'; }
.           { return yytext[0]; }  /* + - * / ( ) and anything else */
%%

The scanner includes calc.tab.h, which Bison generates with -d; it defines the token code NUMBER and declares yylval. %option noyywrap means we don't need to supply yywrap() or link with -lfl, and noinput nounput just suppresses unused-function warnings.

Build and run

$ bison -d calc.y          # → calc.tab.c, calc.tab.h
$ flex calc.l              # → lex.yy.c
$ gcc -Wall calc.tab.c lex.yy.c -o calc
$ ./calc < input.txt

input.txt:

2 + 3 * 4
(2 + 3) * 4
10 - 4 - 3
-5 + 2
8 / 0
7 + * 2
100 / 7

Output (stdout and stderr together):

= 14
= 20
= 3
= -3
error: division by zero
= 0
error: syntax error
= 14

Line by line:

  • 2 + 3 * 4 = 14: * was declared on a later line than +, so it has higher precedence.

  • 10 - 4 - 3 = 3: %left makes - left-associative, (10 − 4) − 3.

  • -5 + 2 = -3: %prec UMINUS gives unary minus the highest precedence, so it applies to 5 only.

  • 7 + * 2: a syntax error. The error rule discards input up to the newline and yyerrok resumes normal parsing, so the next line still works.

  • 100 / 7 = 14: integer division in C.


Conflicts: What Bison Tells You

If the LALR(1) table has conflicts, Bison does not stop. It reports them, resolves each one with a fixed rule, and still produces a parser. You must understand those reports.

Shift-reduce conflicts in an ambiguous grammar

%token ID
%%
E : E '+' E
  | E '*' E
  | ID
  ;
%%
$ bison ambig.y
ambig.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr]
ambig.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples

Four conflicts, exactly the four you find if you build the LR table for this grammar by hand: two states contain a complete item (E → E + E • and E → E * E •), and in each of them both + and * can either be shifted or trigger the reduction. This is the same ambiguity we met in Bottom-Up Parsing & Shift-Reduce Parsing. From ambig.output:

State 6

    1 E: E • '+' E
    1  | E '+' E •
    2  | E • '*' E

    '+'  shift, and go to state 4
    '*'  shift, and go to state 5

    '+'       [reduce using rule 1 (E)]
    '*'       [reduce using rule 1 (E)]
    $default  reduce using rule 1 (E)

The entries in square brackets are the losers. Bison's default rules:

Conflict

Default resolution (no precedence declared)

Shift-reduce

Shift

Reduce-reduce

Reduce by the production that appears first in the grammar

Here "always shift" makes both operators right-associative with equal precedence, so 2 * 3 + 4 would be computed as 2 * (3 + 4). Not what we want, which is why the calculator declares precedence.

How precedence declarations resolve a conflict

  • %left, %right and %nonassoc give tokens a precedence level. Tokens on the same line share a level; later lines bind tighter.

  • A rule gets the precedence of its last terminal, unless you override it with %prec TOKEN.

  • On a shift-reduce conflict, Bison compares the rule (reduce) with the lookahead token (shift): higher rule precedence → reduce; higher token precedence → shift; equal → use associativity: %left reduces, %right shifts, %nonassoc makes it a syntax error.

A test of all three kinds of associativity:

%{
#include <stdio.h>
#include <ctype.h>
int yylex(void);
void yyerror(const char *msg);
%}
%token NUM
%nonassoc '<'
%left '-'
%right '^'
%%
lines : %empty | lines line ;
line  : e '\n'      { printf("= %d\n", $1); }
      | error '\n'  { yyerrok; }
      ;
e : e '<' e   { $$ = $1 < $3; }
  | e '-' e   { $$ = $1 - $3; }
  | e '^' e   { int r = 1; for (int i = 0; i < $3; i++) r *= $1; $$ = r; }
  | NUM
  ;
%%
int yylex(void) {
    int c;
    while ((c = getchar()) == ' ') ;
    if (c == EOF) return 0;
    if (isdigit(c)) { int v = c - '0'; while (isdigit(c = getchar())) v = v*10 + c - '0'; ungetc(c, stdin); yylval = v; return NUM; }
    return c;
}
void yyerror(const char *m) { printf("error: %s\n", m); }
int main(void) { return yyparse(); }

Input and output:

2 ^ 3 ^ 2
9 - 4 - 3
1 < 2
1 < 2 < 3
5 - 1 < 2
= 512
= 2
= 1
error: syntax error
= 0
  • 2 ^ 3 ^ 2 = 29 = 512, because %right groups it as 2 ^ (3 ^ 2).

  • 9 - 4 - 3 = 2, left-associative.

  • 1 < 2 < 3 is a syntax error, because %nonassoc forbids chaining.

  • 5 - 1 < 2 = 0: - is declared after <, so it binds tighter: (5 − 1) < 2 is false.

The dangling else

%token IF THEN ELSE OTHER COND
%%
stmt : IF COND THEN stmt
     | IF COND THEN stmt ELSE stmt
     | OTHER
     ;
%%
$ bison -Wcounterexamples dangle.y
dangle.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
dangle.y: warning: shift/reduce conflict on token ELSE [-Wcounterexamples]
  Example: IF COND THEN IF COND THEN stmt • ELSE stmt
  Shift derivation
    stmt
    ↳ 1: IF COND THEN stmt
                      ↳ 2: IF COND THEN stmt • ELSE stmt
  Reduce derivation
    stmt
    ↳ 2: IF COND THEN stmt                     ELSE stmt
                      ↳ 1: IF COND THEN stmt •

The -Wcounterexamples option shows the actual ambiguity: the ELSE can belong to the inner IF (shift) or the outer IF (reduce first). The default "shift" attaches the ELSE to the nearest IF, which is the rule in C, Java and most languages. Since this is the intended behaviour, you can tell Bison to expect it by adding %expect 1 to the declarations. Bison then stays silent unless the number of shift-reduce conflicts changes (we checked: with %expect 1 it prints nothing).

A reduce-reduce conflict

The grammar from LALR Parsing that is CLR(1) but not LALR(1):

%token a b c d e
%%
S : a A d | b B d | a B e | b A e ;
A : c ;
B : c ;
%%
rr.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
rr.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
rr.y:5.5: warning: rule useless in parser due to conflicts [-Wother]
    5 | B : c ;
      |     ^

Exactly the two reduce-reduce conflicts we predicted by merging states. Bison resolved them in favour of the earlier rule A : c, so B : c can now never be reduced, which is why it is reported as useless. We built it to check: the parser accepts a c d and b c e but rejects the valid inputs a c e and b c d with "syntax error".

Bison can build a more powerful parser instead of LALR(1):

%define lr.type ielr           /* IELR(1): LR(1) power, near-LALR size */
%define lr.type canonical-lr   /* canonical LR(1)                       */

With either line added, Bison reports no conflicts for this grammar, and the IELR parser we built accepts a c e correctly. In practice, a reduce-reduce conflict usually means the grammar itself should be rewritten.


Error Recovery with the error Token

By default yyparse() calls yyerror("syntax error") and returns 1 at the first error. To keep going, add rules containing the special token error, as the calculator does:

line : error '\n'   { yyerrok; }

On an error, the parser pops states until it finds one that can shift error, shifts it, then discards input tokens until it can continue (here, until it sees a newline). yyerrok tells it that recovery is complete, so new errors are reported immediately. This is a form of panic-mode recovery with synchronizing tokens.


Important Names to Remember

Name

Meaning

yyparse()

Generated parser. Returns 0 on success, 1 on a syntax error it could not recover from (2 if memory runs out).

yylex()

Scanner, supplied by Flex or by you. Returns a token code; 0 (or a negative value) means end of input.

yylval

Global through which the scanner passes a token's value to the parser.

yyerror(const char *)

Error routine you must define. Called by the parser on a syntax error.

$$, $1, $2 …

Value of the left side and of the body symbols in an action.

%token

Declares terminal names.

%left, %right, %nonassoc

Declare tokens with associativity and precedence (later = higher).

%prec

Gives a rule the precedence of a named token (e.g. unary minus).

%union, %type

Declare value types for tokens and nonterminals.

%start

Choose the start symbol (default: left side of the first rule).

error, yyerrok

Error recovery token and the macro that ends recovery.

-d, -v

Bison options: write the header file / write the .output state description.


Common Mistakes

  • Forgetting -d. Without calc.tab.h, the scanner doesn't know the token codes and fails to compile.

  • Ignoring conflict warnings. Bison still produces a parser, but it may not accept the language you intended (the reduce-reduce example rejects valid input). Read the .output file or use -Wcounterexamples.

  • Getting precedence order backwards. In Yacc, the operator declared last has the highest precedence.

  • Not defining yyerror (or main). The generated parser calls yyerror; you must provide it.

  • Link errors about yywrap. Either add %option noyywrap to the Flex file or link with -lfl.

  • Assuming actions run left to right as tokens are read. An action at the end of a rule runs when the rule is reduced, i.e. after all its children have been parsed.


Practice Questions

Q1. Which parsing technique does Yacc use?

LALR(1) bottom-up (shift-reduce) parsing. Bison also uses LALR(1) by default and can optionally generate IELR(1), canonical LR(1) or GLR parsers.

Q2. How does Yacc resolve a shift-reduce conflict and a reduce-reduce conflict when no precedence is given?

Shift-reduce: it shifts. Reduce-reduce: it reduces by the production listed earlier in the grammar. Both are reported as warnings.

Q3. Given %left '+' '-' followed by %left '*' '/', how is 8 - 2 * 3 - 1 evaluated?

* has higher precedence, and - is left-associative: (8 − (2 * 3)) − 1 = 1.

Q4. What is the role of %prec in expr : '-' expr %prec UMINUS?

The rule's precedence would normally be that of its last terminal, binary -. %prec UMINUS gives it the (higher) precedence of the pseudo-token UMINUS, so -a * b is parsed as (-a) * b.

Q5. In what order do the actions run for the input a * b + c in the expression grammar?

In the order of reductions: F → id, T → F, F → id, T → T * F, E → T, F → id, T → F, E → E + T, the reverse of the rightmost derivation (see Example 1).

Q6. What files are produced by bison -d calc.y and flex calc.l?

calc.tab.c (the parser), calc.tab.h (token codes and the yylval declaration) and lex.yy.c (the scanner). Classic Yacc names them y.tab.c and y.tab.h.


Summary

  • Yacc/Bison generates an LALR(1) parser, yyparse(), from a grammar file with three sections separated by %%.

  • The parser gets tokens from yylex() (usually from Flex) and values through yylval.

  • Actions run on reduction; $$ is the left side's value and $n is the n-th body symbol's value.

  • Conflicts are reported, not fatal: shift wins S/R, the earlier rule wins R/R.

  • %left, %right, %nonassoc and %prec let you use a small ambiguous expression grammar safely.

  • -v (the .output file) and -Wcounterexamples are your tools for understanding conflicts.

Write the grammar, attach the actions, declare the precedences; Bison builds the LALR(1) table for you.