Operator-precedence parsing (brief); YACC conflict resolution with precedence and associativity; panic-mode error recovery (brief)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Classify S → x A y | x B z, A → q, B → q. from Lesson 2.4.6
• In a CLR table, on which columns does [A → α•, a] reduce? from Lesson 2.4.4
• What does panic-mode recovery do in a lexer? from Lesson 1.3

1 · The Story

📖

Shortcuts and tie-breaks

Budget speeches are mostly arithmetic. Kabir sets up a small, fast desk just for them, run by a simple table that only compares operators: “when the top of my pile is +, and * comes next, * goes first; when the top is * and + comes next, finish the * first”.

For the main desk, Kabir buys a machine that builds LALR walls from a rulebook: the House’s parser builder. Sometimes it reports a clash because the rulebook is two-faced, like E → E + E | E * E. Kabir does not rewrite the rules; he gives the machine tie-break instructions: “* is stronger than +; equal operators group to the left”. The machine then fills every clashing cell with one action.

And when a speech has a broken sentence, the desk does not give up: it throws away words until it reaches a full stop, reports one complaint, and starts again at the next sentence.

2 · Predict First

🤔

A parser builder resolves every shift/reduce conflict of E → E + E | E * E | n by shifting, and every reduce/reduce conflict by the earlier rule. What is the value of 2 + 3 * 4 + 5? Write your guess down. The answer is in the vault.

3 · Core Concept

Operator-precedence parsing

An operator grammar has no ε-productions and no right side with two adjacent nonterminals (E → E + E is fine; E → E E is not). For such grammars a very small parser works by comparing terminals only, using three precedence relations:

• a <· b: a yields precedence to b (b’s phrase is reduced first);
• a ·> b: a takes precedence over b (reduce a’s phrase first);
• a =· b: same phrase (like ( and )).

Algorithm: stack starts with $; if top <· a or top =· a, shift a; if top ·> a, pop until the terminal on top is <· the last terminal popped (that popped part is the handle), then reduce. Accept when the stack is $ and the input is $.

Precedence relations and functions

• ·> + (left associative), + <· * (* higher), * ·> +. The table can often be replaced by two precedence functions f and g with f(a) < g(b) iff a <· b and f(a) > g(b) iff a ·> b; for this table f = { + : 2, * : 4, id : 4, $ : 0 } and g = { + : 1, * : 3, id : 5, $ : 0 } (checked against every cell). Operator-precedence parsers are small but handle only a narrow class of grammars and cannot treat unary minus well.

YACC and conflict resolution

YACC (and Bison) builds an LALR(1) parser from a grammar with action code. It reports conflicts and resolves them automatically:

• default: a shift/reduce conflict is resolved in favour of shift; a reduce/reduce conflict in favour of the production listed first;
• with declarations %left '+' '-', %left '*' '/', %right '^' (later lines = higher precedence): a production gets the precedence of its last terminal; in a S/R conflict between reducing A → α and shifting a: reduce if prec(rule) > prec(a), shift if prec(a) > prec(rule); if equal, %left reduces, %right shifts, %nonassoc reports an error.

Panic-mode recovery in parsers

On an error, the parser pops states until one has a GOTO on a chosen nonterminal A (for example a statement), then discards input tokens until one in a synchronizing set (typically FOLLOW(A), such as ; or }) appears, pushes GOTO on A, and continues. LL parsers do the same with FOLLOW of the nonterminal on top. Simple and never loops, but skips some input. YACC offers this with its error token.

Story → compiler term

4 · Visual

Operator-precedence parse of id + id * id with the relation table (computed). Reductions happen when top ·> next.

5 · Worked Examples

Example 1 Easy

Parse id + id * id with the operator-precedence table.

Solution

See the trace above: 11 rows, 5 reductions. The * phrase is reduced before the + phrase because + <· * but * ·> $, exactly Kabir’s “* goes first”.

Example 2 Medium

E → E + E | E * E | ( E ) | n is given to YACC with %left '+' then %left '*'. Evaluate 2 + 3 * 4 + 5 and 3 * 2 + 4 * 2.

Solution

• binds tighter, both left associative: (2 + (3 * 4)) + 5 = 19; (3 * 2) + (4 * 2) = 14. Computed by resolving the LALR table with these rules, parsing and evaluating.

Example 3 GATE

Same grammar, but the declarations are reversed: %left '*' then %left '+' (+ now higher). Evaluate 2 + 3 * 4 + 5. Then evaluate it with no declarations at all (default: always shift).

Solution

• higher, left associative: (2 + 3) * (4 + 5) = 45.

No declarations: YACC shifts on every S/R conflict, which makes all operators right associative with equal precedence: 2 + (3 * (4 + 5)) = 29. The tie-break instructions decide the meaning.

6 · Shortcuts

⚡

Default YACC = always shift ⇒ evaluate the expression from the right: all operators right associative, same precedence. Valid when: questions that give an ambiguous expression grammar and say conflicts are resolved by shifting.

⚡

With %left/%right: later declaration = higher precedence; %left groups left, %right groups right. Bracket the expression accordingly, then evaluate. Valid when: questions with precedence declarations.

7 · GATE Traps

⚠️

• In YACC, operators declared on a later line have higher precedence.
• Default S/R resolution is shift, which happens to be right for the dangling else.
• Default R/R resolution is the earlier production in the file.
• Operator grammars forbid ε-productions and adjacent nonterminals.
• Panic mode skips input; it never adds tokens.

8 · Memory Hook

🧠

YACC: later line = stronger; left reduces, right shifts; silent default = shift.

9 · Connect the Dots

Phase 2 is complete: the parser can check structure and build parse trees. Phase 3 attaches meaning to that structure: values, types and code computed alongside parsing, by rules attached to productions.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksYACC

E → E + E | E * E | ( E ) | n is given to a parser generator that resolves every shift/reduce conflict by shifting. What is the value of 3 * 2 + 4 * 2?

Numerical answer: ________

Q2NAT2 marksYACC

With %left '-' on the first line and %left '/' on the second, what does E → E − E | E / E | n compute for 16 - 8 / 2 / 2?

Numerical answer: ________

Q3MCQ1 markDefaults

By default, YACC resolves a reduce/reduce conflict by:

• (A) shifting
• (B) reducing by the production that appears first in the grammar
• (C) reporting a fatal error
• (D) reducing by the longer production

Q4MSQ1 markOperator grammar

Which productions are allowed in an operator grammar?

• (A) E → E + E
• (B) E → E E
• (C) E → ( E )
• (D) E → ε

Q5MCQ1 markPrecedence relations

In the operator-precedence table for +, * (usual precedence, left associative), the relation between + on top of the stack and + as the next token is:

• (A) + <· +
• (B) + =· +
• (C) + ·> +
• (D) no relation

11 · Rule Card

• Operator grammar: no ε, no adjacent nonterminals. Relations <·, =·, ·> between terminals.
• Shift if top <· a or =·; reduce if top ·> a (pop until <·).
• Precedence functions f, g can encode the table.
• YACC: LALR(1); default S/R → shift, R/R → earlier production.
• %left/%right/%nonassoc: later = higher; equal precedence: left reduces, right shifts.
• Panic mode: pop to a state with GOTO on A, skip input to FOLLOW(A).

12 · Concept Ledger

operator grammarprecedence relations <·, =·, ·>operator-precedence parserprecedence functions f, gYACC / Bison%left / %right / %nonassocdefault conflict resolutionpanic mode in parserssynchronizing tokens

13 · Answer Vault