LALR(1) Parser Generator (Yacc, Bison)
1. What It Does
Yacc / Bison generates a LALR(1) bottom-up parser in C from a grammar + semantic actions. Input .y → y.tab.c with yyparse(); linked with Lex scanner (yylex() supplies tokens).
2. Yacc File Structure
%{ C headers %}
%token IF ELSE NUM ID
%left '+' '-'
%left '*' '/'
%%
stmt : IF '(' expr ')' stmt { $$ = mk_if($3,$5); }
| expr ';' { $$ = $1; }
;
expr : expr '+' expr { $$ = mk_add($1,$3); }
| NUM { $$ = mk_num($1); }
;
%%
yylex(){ ... } yyerror(char *s){ fprintf(stderr,"err:%s",s); }
Sections: declarations / rules / code, separated by %%. `
` = LHS value, `$1,$2..` = RHS values.
### 3. Conflict Handling in Yacc
- **Shift-reduce** (dangling else): defaults to **shift** (else binds inner) — with warning.
- **Reduce-reduce**: earlier rule wins — fix grammar.
- Directives: `%left` (left-assoc), `%right` (e.g. `=`), `%nonassoc`, `%prec` override.
Build: `yacc -d calc.y` → `y.tab.h/.c` + `flex calc.l` → `gcc y.tab.c lex.yy.c` → `./a.out`
### 4. Yacc vs Lex
Lex = **tokens (regular)**; Yacc = **structure (context-free)**. Together: chars → Lex → tokens → Yacc → tree + actions.
### 5. Exam Points
- **Yacc file structure + small expr example — 7 marks, very frequent**.
- **
, $1, %token, %left** meanings — 3-5 marks, frequent.
- Shift-reduce default + precedence directives — 3 marks, frequent.