Bottom-up parsing

ACompressed recap

🧾

Bottom-up parsers shift tokens and reduce handles, tracing a rightmost derivation in reverse; stack contents are viable prefixes, recognised by the LR(0) automaton built from items with CLOSURE and GOTO. LR(0) reduces in all columns; SLR only on FOLLOW; CLR on item lookaheads computed from FIRST(βa); LALR merges CLR states with equal cores (same size as LR(0); merging can add R/R conflicts only). LR(0) ⊂ SLR ⊂ LALR ⊂ LR(1); LL(1) ⊂ LR(1). YACC uses LALR and resolves conflicts by precedence declarations (default: shift; earlier production).

BMerged rule card

2.4.1 Shift-reduce parsing; handles; viable prefixes; shift/reduce and reduce/reduce conflicts

• Bottom-up = leaves to root = rightmost derivation in reverse.
• Actions: shift, reduce A → β (β on top), accept ($S, $), error.
• Handle: the right side to reduce next; always on top of the stack.
• Viable prefix: stack content that can still lead to a handle; the set is regular.
• Conflicts: shift/reduce, reduce/reduce; ambiguous grammars always have them.
• Reduces = interior nodes; shifts = tokens.

2.4.2 LR(0) items, CLOSURE, GOTO, the canonical collection and the LR(0) table

• Item: production with a dot; |rhs| + 1 items per production; A → ε gives A → •.
• Augment: S′ → S.
• CLOSURE: A → α•Bβ adds B → •γ.
• GOTO(I, X): advance the dot over X, then CLOSURE.
• LR(0) table: shift on terminals after the dot; complete item reduces in all columns; S′ → S• accepts on $.
• LR(0) conflict: complete item with another complete item (R/R) or with a terminal-after-dot item (S/R).

2.4.3 SLR(1)

• SLR(1) = LR(0) automaton + reduce A → α only on FOLLOW(A).
• S/R conflict: A → α• and B → β•aγ with a ∈ FOLLOW(A).
• R/R conflict: A → α•, B → β• with FOLLOW(A) ∩ FOLLOW(B) ≠ ∅.
• LR(0) ⊂ SLR(1); same number of states.
• Weakness: FOLLOW is global (false conflicts, e.g. L = R).

2.4.4 Canonical LR(1) (CLR) items with lookaheads

• LR(1) item [A → α•β, a].
• CLOSURE: [A → α•Bβ, a] ⇒ [B → •γ, b] for b ∈ FIRST(βa).
• GOTO keeps lookaheads.
• Reduce [A → α•, a] only on a; accept [S′ → S•, $].
• CLR (canonical LR(1)) ⊇ SLR; states ≥ LR(0) states; S → CC: 10 vs 7.

2.4.5 LALR(1): merging states and which conflicts merging can create

• Core = LR(0) part of an LR(1) state.
• LALR(1): merge CLR states with equal cores; union lookaheads.
• LALR states = LR(0) states ≤ CLR states.
• Merging can create R/R conflicts, never S/R.
• LR(0) ⊂ SLR ⊂ LALR ⊂ LR(1).

2.4.6 Power and state-count comparison of LL(1), LR(0), SLR, LALR, CLR; grammar-classification drills

• LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1); LL(1) ⊂ LR(1); LL(1) and SLR/LALR overlap without inclusion.
• States: LR(0) = SLR = LALR ≤ CLR.
• Ambiguous ⇒ in no class.
• Classify in order: ambiguity, LL(1), LR(0), SLR, LALR, CLR.

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

• 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).

CInterleaved GATE-style questions

Q1NAT1 markItems

How many LR(0) items does the augmented expression grammar E → E + T | T, T → T * F | F, F → ( E ) | id have?

Numerical answer: ________

Q2MCQ1 markSLR vs LR(0)

The LR(0) and SLR(1) tables of a grammar differ only in:

• (A) the number of states
• (B) the shift entries
• (C) the reduce entries
• (D) the GOTO entries

Q3NAT2 marksStates

How many states does the canonical LR(1) collection of E → E + T | T, T → T * F | F, F → ( E ) | id have?

Numerical answer: ________

Q4MCQ2 marksClassification

Which grammar is SLR(1) but not LR(0)?

• (A) S → A A, A → a A | b
• (B) S → a S | a
• (C) S → ( L ) | a, L → L , S | S
• (D) S → L = R | R, L → * R | id, R → L

Q5MCQ1 markLALR

Compared with CLR, an LALR(1) parser for the same grammar:

• (A) has at most as many states
• (B) accepts more grammars
• (C) can have new shift/reduce conflicts
• (D) needs FOLLOW sets

Q6MSQ2 marksViable prefixes

For the expression grammar, which stack contents are viable prefixes?

• (A) E + ( id
• (B) T * F +
• (C) ( ( E
• (D) E )

Q7NAT2 marksYACC

E → E + E | E * E | ( E ) | n with %right '+' on line 1 and %right '*' on line 2. Value of 3 * 2 + 4 * 2?

Numerical answer: ________

Q8MCQ1 markHandles

In the right-sentential form E + T * id of the expression grammar, the handle is:

• (A) E + T
• (B) T
• (C) id
• (D) T * id

Q9MCQ2 marksMerging

A grammar is CLR(1) and its LALR(1) table has a conflict. That conflict is:

• (A) shift/reduce
• (B) reduce/reduce
• (C) either
• (D) impossible

Q10NAT1 markMoves

An LR parser accepts a a b b with S → A A, A → a A | b. How many reduce moves does it make?

Numerical answer: ________