CD Notes

Bison: LALR Parser Generator

Detailed guide to Bison parser generation, grammar rules, LALR parsing, and compiler construction

Bison is the GNU version of YACC (Yet Another Compiler Compiler). It automatically generates parsers from grammar specifications, eliminating tedious hand-coded parser logic.

What is Bison?

Bison is a parser generator that takes an LALR(1) grammar specification and automatically generates C code implementing a parser. It's the standard tool for building the syntax analysis phase of compilers.

Grammar Specification (.y file) ├─ Token definitions ├─ Grammar rules └─ Semantic actions ↓ Bison processes ↓ Parser C Code (y.tab.c) Token Header (y.tab.h) ↓ Compile & Link ↓ Executable Parser

Bison File Structure

A .y file (or .bison) has sections:

┌────────────────────────────────────┐ │ PROLOGUE (C declarations) │ │ %{ │ │ #include statements │ │ Global variables │ │ %} │ ├────────────────────────────────────┤ │ DECLARATIONS │ │ %token IDENTIFIER NUMBER │ │ %type <val> expr │ │ %precedence rules │ ├────────────────────────────────────┤ │ %% GRAMMAR RULES %% │ │ start : expr NEWLINE │ │ ; │ │ expr : expr PLUS expr │ │ | NUMBER │ │ ; │ ├────────────────────────────────────┤ │ EPILOGUE (C code) │ │ %% │ │ int main() { ... } │ └────────────────────────────────────┘

Complete Calculator Example

File: calc.y

bison example

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

%token NUMBER
%left PLUS MINUS
%left MULTIPLY DIVIDE

%%

start : expr   { result = $1; }
      ;

expr  : expr PLUS expr     { $$ = $1 + $3; }
      | expr MINUS expr    { $$ = $1 - $3; }
      | expr MULTIPLY expr { $$ = $1 * $3; }
      | expr DIVIDE expr   { $$ = $1 / $3; }
      | NUMBER             { $$ = $1; }
      | LPAREN expr RPAREN { $$ = $2; }
      ;

%%

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

int main() {
    yyparse();
    printf("Result: %d\n", result);
    return 0;
}

Bison Grammar Rules

Grammar rules define the language syntax:

Example

production_name : symbol1 symbol2 ... { action } | alternative1 { action } ;

Example:

bison example

statement : assignment
          | if_statement
          | while_loop
          ;

assignment : IDENTIFIER ASSIGN expr  { process_assignment($1, $3); }
           ;

Semantic Actions

Actions are C code executed when a rule is matched:

bison example

expr : NUMBER        { $$ = $1; }
     | expr PLUS expr { $$ = $1 + $3; }
     ;

Symbols:

$$: Result value of this rule
$1: Value of first symbol
$2: Value of second symbol
$n: Value of nth symbol

Bison Values and Types

Associate semantic values with tokens/nonterminals:

bison example

%union {
    int intval;
    char *strval;
    struct ASTNode *node;
}

%token <intval> NUMBER
%token <strval> IDENTIFIER
%type <node> expr
%type <intval> statement

Precedence and Associativity

Define how operators interact:

bison example

%left PLUS MINUS       /* Left-associative */
%left MULTIPLY DIVIDE  /* Higher precedence than +/- */
%right POWER           /* Right-associative */

/* Example resolution:
   5 - 3 - 2  = (5 - 3) - 2 = 0  (left-assoc)
   2^3^2 = 2^(3^2) = 512          (right-assoc)
*/

Shift/Reduce and Reduce/Reduce Conflicts

Bison detects ambiguities:

bison example

/* Shift/Reduce Conflict: */
if_stmt : IF expr THEN stmt
        | IF expr THEN stmt ELSE stmt
        ;

/* When parser sees "else", should it:
   SHIFT it (reduce first if)
   or REDUCE immediately?
   Resolution: Usually shift (else binds to nearest if)
*/

/* Reduce/Reduce Conflict: More serious
   Usually indicates grammar ambiguity
   Should be fixed by rewriting grammar
*/

LALR(1) Parsing

Bison generates LALR(1) parsers:

L: Left-to-right scanning
A: Rightmost derivation
LR: Build parse tree bottom-up
(1): 1 token lookahead

Advantages

✓ Handles large grammars

✓ Efficient parsing

✓ Good error detection

Limitations

✗ Cannot handle all context-free grammars

✗ Some ambiguous grammars not supported

Parse Table Generation

Bison generates parse tables from grammar:

Parsing Table

Rows: Parser states

Columns: Symbols (terminals & nonterminals)

Entries: Action (shift, reduce, accept, error)

Example

NUMBER PLUS $

State 0: shift - -

State 1: reduce shift -

State 2: - - accept

Compilation Workflow

bison		flex
calc.y		calc.l

Error Handling

Bison provides error recovery:

bison example

statement : expr NEWLINE    { execute($1); }
          | IDENTIFIER ASSIGN expr NEWLINE  { assign($1, $3); }
          | error NEWLINE   { yyerrok; printf("Resync\n"); }
          ;

yyerrok: Resynchronize parser after error

Real-World Applications

C Compiler: GCC frontend uses Bison
Java Parser: Used in many Java tools
JavaScript Engines: Parser generation
SQL Databases: Query language parsing
Configuration Parsers: Config file parsing

Bison vs Hand-Written Parsers

Hand-Written (Complex)

Example

// Recursive descent - lots of code int parse_expr() { int left = parse_term(); while (current_token == PLUS || current_token == MINUS) { // Parse operator // Parse right side // Combine results } return left; }

With Bison (Concise)

bison example

expr : expr PLUS expr   { $$ = $1 + $3; }
     | expr MINUS expr  { $$ = $1 - $3; }
     | NUMBER           { $$ = $1; }
     ;

Much simpler and less error-prone!

Interview Q&A

Q: What does Bison do? A: Bison is a parser generator that takes a context-free grammar specification and automatically generates an LALR(1) parser in C, eliminating tedious hand-coded parsing logic.

Q: What is an LALR(1) parser? A: LALR (Look-Ahead LR) uses shift/reduce parsing with 1 token lookahead. It can parse most practical programming languages and is efficient in time and space.

Q: What do $$, $1, $2 mean? A: These are semantic values. $$ is the value of the current production, $n is the value of the nth symbol in the rule.

Q: How do Flex and Bison work together? A: Flex generates the lexical analyzer that tokenizes input. Bison generates the parser that calls yylex() to get tokens and builds the parse tree.

Q: What are shift/reduce conflicts? A: A conflict occurs when the parser doesn't know whether to shift the next token or reduce the current production. Bison warns about these and makes default decisions.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Bison: LALR 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, bison, tool

Continue learning this concept

Parser GeneratorsFlex: Lexical Analyzer GeneratorComprehensive guide to Flex tool, regular expressions, state machines, and DFA generation Parser GeneratorsLex: Original Lexical AnalyzerIntroduction to Lex, comparison with Flex, and historical context 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 Parser GeneratorsYACC: Original Parser GeneratorHistorical context and usage of YACC, comparison with Bison Lexical AnalysisLex Tool - Lexical Analyzer GeneratorComplete guide to the Lex tool for automatic generation of lexical analyzers from regular expression specifications, including syntax, rules, and examples.

PreviousPeephole Optimization in Compiler Design NextFlex: Lexical Analyzer Generator

CD Notes

Bison: LALR Parser Generator

Detailed guide to Bison parser generation, grammar rules, LALR parsing, and compiler construction

Bison is the GNU version of YACC (Yet Another Compiler Compiler). It automatically generates parsers from grammar specifications, eliminating tedious hand-coded parser logic.

What is Bison?

Bison File Structure

A .y file (or .bison) has sections:

Complete Calculator Example

File: calc.y

bison example

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

%token NUMBER
%left PLUS MINUS
%left MULTIPLY DIVIDE

%%

start : expr   { result = $1; }
      ;

expr  : expr PLUS expr     { $$ = $1 + $3; }
      | expr MINUS expr    { $$ = $1 - $3; }
      | expr MULTIPLY expr { $$ = $1 * $3; }
      | expr DIVIDE expr   { $$ = $1 / $3; }
      | NUMBER             { $$ = $1; }
      | LPAREN expr RPAREN { $$ = $2; }
      ;

%%

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

int main() {
    yyparse();
    printf("Result: %d\n", result);
    return 0;
}

Bison Grammar Rules

Grammar rules define the language syntax:

Example

production_name : symbol1 symbol2 ... { action } | alternative1 { action } ;

Example:

bison example

statement : assignment
          | if_statement
          | while_loop
          ;

assignment : IDENTIFIER ASSIGN expr  { process_assignment($1, $3); }
           ;

Semantic Actions

Actions are C code executed when a rule is matched:

bison example

expr : NUMBER        { $$ = $1; }
     | expr PLUS expr { $$ = $1 + $3; }
     ;

Symbols:

$$: Result value of this rule
$1: Value of first symbol
$2: Value of second symbol
$n: Value of nth symbol

Bison Values and Types

Associate semantic values with tokens/nonterminals:

bison example

%union {
    int intval;
    char *strval;
    struct ASTNode *node;
}

%token <intval> NUMBER
%token <strval> IDENTIFIER
%type <node> expr
%type <intval> statement

Precedence and Associativity

Define how operators interact:

bison example

%left PLUS MINUS       /* Left-associative */
%left MULTIPLY DIVIDE  /* Higher precedence than +/- */
%right POWER           /* Right-associative */

/* Example resolution:
   5 - 3 - 2  = (5 - 3) - 2 = 0  (left-assoc)
   2^3^2 = 2^(3^2) = 512          (right-assoc)
*/

Shift/Reduce and Reduce/Reduce Conflicts

Bison detects ambiguities:

bison example

/* Shift/Reduce Conflict: */
if_stmt : IF expr THEN stmt
        | IF expr THEN stmt ELSE stmt
        ;

/* When parser sees "else", should it:
   SHIFT it (reduce first if)
   or REDUCE immediately?
   Resolution: Usually shift (else binds to nearest if)
*/

/* Reduce/Reduce Conflict: More serious
   Usually indicates grammar ambiguity
   Should be fixed by rewriting grammar
*/

LALR(1) Parsing

Bison generates LALR(1) parsers:

L: Left-to-right scanning
A: Rightmost derivation
LR: Build parse tree bottom-up
(1): 1 token lookahead

Advantages

✓ Handles large grammars

✓ Efficient parsing

✓ Good error detection

Limitations

✗ Cannot handle all context-free grammars

✗ Some ambiguous grammars not supported

Parse Table Generation

Bison generates parse tables from grammar:

Parsing Table

Rows: Parser states

Columns: Symbols (terminals & nonterminals)

Entries: Action (shift, reduce, accept, error)

Example

NUMBER PLUS $

State 0: shift - -

State 1: reduce shift -

State 2: - - accept

Compilation Workflow

bison		flex
calc.y		calc.l

Error Handling

Bison provides error recovery:

bison example

statement : expr NEWLINE    { execute($1); }
          | IDENTIFIER ASSIGN expr NEWLINE  { assign($1, $3); }
          | error NEWLINE   { yyerrok; printf("Resync\n"); }
          ;

yyerrok: Resynchronize parser after error

Real-World Applications

C Compiler: GCC frontend uses Bison
Java Parser: Used in many Java tools
JavaScript Engines: Parser generation
SQL Databases: Query language parsing
Configuration Parsers: Config file parsing

Bison vs Hand-Written Parsers

Hand-Written (Complex)

Example

With Bison (Concise)

bison example

expr : expr PLUS expr   { $$ = $1 + $3; }
     | expr MINUS expr  { $$ = $1 - $3; }
     | NUMBER           { $$ = $1; }
     ;

Much simpler and less error-prone!

Interview Q&A

Q: What is an LALR(1) parser? A: LALR (Look-Ahead LR) uses shift/reduce parsing with 1 token lookahead. It can parse most practical programming languages and is efficient in time and space.

Q: What do $$, $1, $2 mean? A: These are semantic values. $$ is the value of the current production, $n is the value of the nth symbol in the rule.

Q: How do Flex and Bison work together? A: Flex generates the lexical analyzer that tokenizes input. Bison generates the parser that calls yylex() to get tokens and builds the parse tree.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Bison: LALR 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, bison, tool

Continue learning this concept

PreviousPeephole Optimization in Compiler Design NextFlex: Lexical Analyzer Generator