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, callingyylex()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 |
|
|
Output file |
|
|
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
%tokenare terminals; any other name that appears on a left side is a nonterminal. The first rule's left side is the start symbol unless%startsays 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
%emptyin 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
yylvalbefore returning it.If a rule has no action, the default is
$$ = $1.By default values are
int(YYSTYPE). Real parsers use%unionwith%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' | ./exprreduce 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
acceptedThis 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' | ./exprreduce F -> id
reduce T -> F
reduce E -> T
error: syntax errorThe 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 $endplus one extra state for shifting$end. So this grammar has 13 Bison states instead of the 12 in our hand-built table.$defaultreduce. 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.txtinput.txt:
2 + 3 * 4
(2 + 3) * 4
10 - 4 - 3
-5 + 2
8 / 0
7 + * 2
100 / 7Output (stdout and stderr together):
= 14
= 20
= 3
= -3
error: division by zero
= 0
error: syntax error
= 14Line by line:
2 + 3 * 4 = 14:*was declared on a later line than+, so it has higher precedence.10 - 4 - 3 = 3:%leftmakes-left-associative, (10 − 4) − 3.-5 + 2 = -3:%prec UMINUSgives unary minus the highest precedence, so it applies to 5 only.7 + * 2: a syntax error. Theerrorrule discards input up to the newline andyyerrokresumes 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 counterexamplesFour 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,%rightand%nonassocgive 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:
%leftreduces,%rightshifts,%nonassocmakes 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
= 02 ^ 3 ^ 2= 29 = 512, because%rightgroups it as 2 ^ (3 ^ 2).9 - 4 - 3= 2, left-associative.1 < 2 < 3is a syntax error, because%nonassocforbids 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 |
|---|---|
| Generated parser. Returns 0 on success, 1 on a syntax error it could not recover from (2 if memory runs out). |
| Scanner, supplied by Flex or by you. Returns a token code; 0 (or a negative value) means end of input. |
| Global through which the scanner passes a token's value to the parser. |
| Error routine you must define. Called by the parser on a syntax error. |
| Value of the left side and of the body symbols in an action. |
| Declares terminal names. |
| Declare tokens with associativity and precedence (later = higher). |
| Gives a rule the precedence of a named token (e.g. unary minus). |
| Declare value types for tokens and nonterminals. |
| Choose the start symbol (default: left side of the first rule). |
| Error recovery token and the macro that ends recovery. |
| Bison options: write the header file / write the .output state description. |
Common Mistakes
Forgetting
-d. Withoutcalc.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(ormain). The generated parser callsyyerror; you must provide it.Link errors about
yywrap. Either add%option noyywrapto 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 throughyylval.Actions run on reduction;
$$is the left side's value and$nis the n-th body symbol's value.Conflicts are reported, not fatal: shift wins S/R, the earlier rule wins R/R.
%left,%right,%nonassocand%preclet you use a small ambiguous expression grammar safely.-v(the .output file) and-Wcounterexamplesare your tools for understanding conflicts.
Write the grammar, attach the actions, declare the precedences; Bison builds the LALR(1) table for you.