CD Notes

YACC: Original Parser Generator

Historical context and usage of YACC, comparison with Bison

Introduction and Historical Context

YACC — "Yet Another Compiler Compiler" — is one of the most influential tools in the history of computer science. Created by Stephen C. Johnson at Bell Labs in 1975, YACC made it practical for ordinary programmers to build parsers for complex languages without needing to understand the intricate details of LR parsing table construction. Before YACC, building a parser meant writing thousands of lines of hand-crafted code. After YACC, you could specify a grammar in a readable format and automatically get a working parser.

The name "Yet Another Compiler Compiler" was somewhat tongue-in-cheek — there were already several parser generators in existence — but YACC became the standard due to its inclusion in Unix. Understanding YACC is important today for two reasons: it helps you maintain legacy systems that still use YACC-generated parsers, and its philosophy directly influenced modern tools like GNU Bison, which is essentially YACC with improvements.

How YACC Works

YACC takes a grammar specification file (with a .y extension) and produces C source code implementing an LALR(1) parser. The process works like this:

Grammar specification (calculator.y) │ ▼ ┌─────────────────┐ │ YACC │ Reads grammar rules and semantic actions └────────┬────────┘ │ ▼ ┌─────────────────┐ │ y.tab.c │ Generated parser (C source code) │ y.tab.h │ Token definitions (shared with lexer) └─────────────────┘ │ ▼ ┌─────────────────┐ │ gcc y.tab.c │ Compile to executable └─────────────────┘

The generated parser contains the LALR(1) parsing tables (encoded as arrays) and the driver code that uses these tables to shift, reduce, and execute semantic actions.

YACC File Structure

A YACC specification file has three sections separated by %%:

Example

%{ /* Section 1: C declarations — #includes, global variables */ #include <stdio.h> #include <stdlib.h> int result; %} /* Token and type declarations */ %token NUMBER PLUS MINUS TIMES DIVIDE LPAREN RPAREN %left PLUS MINUS /* Left-associative, lowest precedence */ %left TIMES DIVIDE /* Left-associative, higher precedence */ %% /* Section 2: Grammar rules with semantic actions */ expr : expr PLUS expr { $$ = $1 + $3; } | expr MINUS expr { $$ = $1 - $3; } | expr TIMES expr { $$ = $1 * $3; } | expr DIVIDE expr { $$ = $1 / $3; } | LPAREN expr RPAREN { $$ = $2; } | NUMBER { $$ = $1; } ; %% /* Section 3: User code — main(), yyerror(), yylex() */ int yylex() { int c = getchar(); if (isdigit(c)) { ungetc(c, stdin); scanf("%d", &yylval); return NUMBER; } switch (c) { case '+': return PLUS; case '-': return MINUS; case '*': return TIMES; case '/': return DIVIDE; case '(': return LPAREN; case ')': return RPAREN; case '\n': return 0; /* End of input */ } return c; } void yyerror(const char *s) { fprintf(stderr, "Parse error: %s\n", s); } int main() { printf("Enter expression: "); yyparse(); printf("Result: %d\n", result); return 0; }

Understanding Semantic Actions

The key innovation of YACC is semantic actions — C code embedded in grammar rules that executes when a production is reduced. The special variables $$, $1, $2, etc. refer to the semantic values of grammar symbols:

yacc example

expr : expr PLUS term    { $$ = $1 + $3; }
       ^^   ^^   ^^
       $1   $2   $3         $$ = result of this rule

When the parser reduces expr PLUS term to expr, it executes the action $$ = $1 + $3, taking the value of the left expr, adding it to the value of term, and storing the result as the value of the new expr.

Let us trace parsing of 3 + 4 * 2:

Step 1	Shift 3 (as NUMBER) Stack: [3]
Step 2: Reduce NUMBER	expr Stack: [expr(3)]
Step 3	Shift + Stack: [expr(3), +]
Step 4	Shift 4 (as NUMBER) Stack: [expr(3), +, 4]
Step 5: Reduce NUMBER	expr Stack: [expr(3), +, expr(4)]
Step 6	Shift * Stack: [expr(3), +, expr(4), *]
Step 7	Shift 2 (as NUMBER) Stack: [expr(3), +, expr(4), *, 2]
Step 8: Reduce NUMBER	expr Stack: [expr(3), +, expr(4), *, expr(2)]
Step 9: Reduce expr*expr	expr Stack: [expr(3), +, expr(8)] {$$=4*2}
Step 10: Reduce expr+expr	expr Stack: [expr(11)] {$$=3+8}

Notice that YACC correctly handles precedence — multiplication reduces before addition because of the %left declarations.

Conflict Resolution in YACC

YACC handles two types of parsing conflicts:

Shift-Reduce Conflict: The parser cannot decide whether to shift the next token or reduce the current stack. YACC resolves this in favor of shifting (which handles the "dangling else" problem correctly).

Reduce-Reduce Conflict: The parser cannot decide which production to reduce by. This usually indicates a grammar design problem and should be fixed by rewriting the grammar.

yacc example

/* Dangling else — YACC resolves correctly via shift preference */
stmt : IF expr THEN stmt
     | IF expr THEN stmt ELSE stmt
     ;
/* Parser shifts ELSE rather than reducing — associates else with nearest if */

YACC vs Bison: A Detailed Comparison

Feature	YACC (Original)	GNU Bison
Creator	Stephen Johnson, Bell Labs	Robert Corbett, GNU Project
Year	1975	1988
License	Proprietary (Unix)	GPL (free)
Parser type	LALR(1)	LALR(1), GLR, IELR(1)
Error messages	Cryptic	Descriptive, with locations
Debugging	Limited	`--report`, `-v` flags
Reentrant	No	Yes (with `%define api.pure`)
C++ support	No	Yes (`%language "C++"`)
Unicode	No	Yes
Active development	Abandoned	Actively maintained
Position tracking	Manual	Automatic (`@1`, `@2` syntax)

When You Encounter YACC Today

You will encounter YACC in several contexts:

Legacy codebases: Many Unix system utilities (awk, bc, expr) were built with YACC in the 1970s-80s and still use YACC-generated parsers. Maintaining these requires understanding the YACC format.

Academic coursework: Many compiler courses use YACC/Bison examples from classic textbooks. The Dragon Book's examples are in YACC format.

Embedded systems: Some embedded platforms lack Bison but include a basic YACC implementation.

Understanding Bison: Since Bison is backward-compatible with YACC, learning YACC format means you can also write Bison grammars.

Building a Complete YACC Project

Here is the workflow for compiling a YACC-based project:

bash example

# Step 1: Generate parser from grammar
yacc -d calculator.y        # Produces y.tab.c and y.tab.h

# Step 2: Compile the generated parser
gcc -c y.tab.c              # Compile parser

# Step 3: If using Lex for the lexer
lex calculator.l            # Produces lex.yy.c
gcc -c lex.yy.c            # Compile lexer

# Step 4: Link everything
gcc -o calculator y.tab.o lex.yy.o -ll -ly

# Step 5: Test
echo "3 + 4 * 2" | ./calculator

Common YACC Pitfalls

Forgetting -d flag: Without yacc -d, no header file is generated, and the lexer cannot use token definitions.

Grammar ambiguity without precedence: If you write expr : expr '+' expr | expr '*' expr without %left declarations, you get shift-reduce conflicts.

No error recovery: Without error tokens in your grammar, the parser terminates on the first syntax error. Add error productions for robustness:

yacc example

statement : expression ';'
          | error ';'   { yyerrok; printf("Skipping to next statement\n"); }
          ;

Key Takeaways

YACC pioneered the concept of automatic parser generation from grammar specifications, making compiler construction accessible to a wider audience. While Bison has replaced YACC for new projects, the file format, concepts (semantic actions, precedence declarations, conflict resolution), and workflow remain the same. Understanding YACC gives you both historical perspective and practical skills for working with parser generators in any context.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for YACC: Original Parser Generator.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, parser, generators, yacc, introduction

Continue learning this concept

Parser GeneratorsLex: Original Lexical AnalyzerIntroduction to Lex, comparison with Flex, and historical context Parser GeneratorsBison: LALR Parser GeneratorDetailed guide to Bison parser generation, grammar rules, LALR parsing, and compiler construction Parser GeneratorsFlex: Lexical Analyzer GeneratorComprehensive guide to Flex tool, regular expressions, state machines, and DFA generation Parser GeneratorsParser Generator WorkflowComplete guide to using Flex and Bison together, build systems, debugging, and best practices Parser GeneratorsPractical Parser ProjectsReal-world parser implementation guide with AST construction, symbol tables, and code generation Code GenerationIntroduction to Code Generation in Compiler DesignComprehensive introduction to the code generation phase of compilation covering objectives, challenges, target code forms, and the interface between intermediate representation and machine code.

PreviousPractical Parser Projects NextBytecode and Virtual Machines

CD Notes

YACC: Original Parser Generator

Historical context and usage of YACC, comparison with Bison

Introduction and Historical Context

How YACC Works

YACC takes a grammar specification file (with a .y extension) and produces C source code implementing an LALR(1) parser. The process works like this:

The generated parser contains the LALR(1) parsing tables (encoded as arrays) and the driver code that uses these tables to shift, reduce, and execute semantic actions.

YACC File Structure

A YACC specification file has three sections separated by %%:

Example

Understanding Semantic Actions

yacc example

expr : expr PLUS term    { $$ = $1 + $3; }
       ^^   ^^   ^^
       $1   $2   $3         $$ = result of this rule

Let us trace parsing of 3 + 4 * 2:

Step 1	Shift 3 (as NUMBER) Stack: [3]
Step 2: Reduce NUMBER	expr Stack: [expr(3)]
Step 3	Shift + Stack: [expr(3), +]
Step 4	Shift 4 (as NUMBER) Stack: [expr(3), +, 4]
Step 5: Reduce NUMBER	expr Stack: [expr(3), +, expr(4)]
Step 6	Shift * Stack: [expr(3), +, expr(4), *]
Step 7	Shift 2 (as NUMBER) Stack: [expr(3), +, expr(4), *, 2]
Step 8: Reduce NUMBER	expr Stack: [expr(3), +, expr(4), *, expr(2)]
Step 9: Reduce expr*expr	expr Stack: [expr(3), +, expr(8)] {$$=4*2}
Step 10: Reduce expr+expr	expr Stack: [expr(11)] {$$=3+8}

Notice that YACC correctly handles precedence — multiplication reduces before addition because of the %left declarations.

Conflict Resolution in YACC

YACC handles two types of parsing conflicts:

Reduce-Reduce Conflict: The parser cannot decide which production to reduce by. This usually indicates a grammar design problem and should be fixed by rewriting the grammar.

yacc example

/* Dangling else — YACC resolves correctly via shift preference */
stmt : IF expr THEN stmt
     | IF expr THEN stmt ELSE stmt
     ;
/* Parser shifts ELSE rather than reducing — associates else with nearest if */

YACC vs Bison: A Detailed Comparison

Feature	YACC (Original)	GNU Bison
Creator	Stephen Johnson, Bell Labs	Robert Corbett, GNU Project
Year	1975	1988
License	Proprietary (Unix)	GPL (free)
Parser type	LALR(1)	LALR(1), GLR, IELR(1)
Error messages	Cryptic	Descriptive, with locations
Debugging	Limited	`--report`, `-v` flags
Reentrant	No	Yes (with `%define api.pure`)
C++ support	No	Yes (`%language "C++"`)
Unicode	No	Yes
Active development	Abandoned	Actively maintained
Position tracking	Manual	Automatic (`@1`, `@2` syntax)

When You Encounter YACC Today

You will encounter YACC in several contexts:

Legacy codebases: Many Unix system utilities (awk, bc, expr) were built with YACC in the 1970s-80s and still use YACC-generated parsers. Maintaining these requires understanding the YACC format.

Academic coursework: Many compiler courses use YACC/Bison examples from classic textbooks. The Dragon Book's examples are in YACC format.

Embedded systems: Some embedded platforms lack Bison but include a basic YACC implementation.

Understanding Bison: Since Bison is backward-compatible with YACC, learning YACC format means you can also write Bison grammars.

Building a Complete YACC Project

Here is the workflow for compiling a YACC-based project:

bash example

# Step 1: Generate parser from grammar
yacc -d calculator.y        # Produces y.tab.c and y.tab.h

# Step 2: Compile the generated parser
gcc -c y.tab.c              # Compile parser

# Step 3: If using Lex for the lexer
lex calculator.l            # Produces lex.yy.c
gcc -c lex.yy.c            # Compile lexer

# Step 4: Link everything
gcc -o calculator y.tab.o lex.yy.o -ll -ly

# Step 5: Test
echo "3 + 4 * 2" | ./calculator

Common YACC Pitfalls

Forgetting -d flag: Without yacc -d, no header file is generated, and the lexer cannot use token definitions.

Grammar ambiguity without precedence: If you write expr : expr '+' expr | expr '*' expr without %left declarations, you get shift-reduce conflicts.

No error recovery: Without error tokens in your grammar, the parser terminates on the first syntax error. Add error productions for robustness:

yacc example

statement : expression ';'
          | error ';'   { yyerrok; printf("Skipping to next statement\n"); }
          ;

Key Takeaways

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for YACC: Original Parser Generator.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, parser, generators, yacc, introduction

Continue learning this concept

PreviousPractical Parser Projects NextBytecode and Virtual Machines