GATE CS Mastery
My library

Compiler Design · topic

Bottom-up parsing: LR(0), SLR, LALR and CLR

Handles and shift-reduce parsing, operator precedence, LR(0) items and automata, SLR, CLR(1) and LALR(1) tables, shift-reduce and reduce-reduce conflicts, state counts, and which grammar falls in which class.

Cheat sheets

CD-07Cheat sheet1 pageIn a paid pack

Shift-Reduce Parsing and Handles

Bottom-up parsing as a rightmost derivation in reverse: handles, handle pruning and viable prefixes. A full SLR-driven trace of id * id + id with states, input and action, counted shifts and reductions, the four actions, and the two kinds of conflict with their usual causes. Operator-precedence parsing in brief: operator grammars, the precedence relations computed from LEADING and TRAILING sets, and the limits of the method. All tables and traces come from a script.

Get the full pack
Partial preview

A partial preview of the top of the sheet. The full sheet is in the Compiler Design cheat sheet pack.

Partial preview

CD-08Cheat sheet1 pageIn a paid pack

LR(0) Automaton and SLR Tables

LR(0) items, closure and goto, and the canonical collection built step by step, with the seven-state automaton of S → AA, A → aA | b drawn and its LR(0) and SLR tables in full. How to count items versus states, when a state is free of LR(0) conflicts, why the expression grammar fails LR(0) on * and passes SLR, how ε-productions create complete items in the start state, and a solved past question that counts LR(0) shift-reduce conflicts cell by cell. Every set, table and count comes from a script.

Get the full pack
Partial preview

A partial preview of the top of the sheet. The full sheet is in the Compiler Design cheat sheet pack.

Partial preview

Diagrams from CD-08

LR(0) automaton for S → AA, A → aA | b with seven item sets I0 to I6 and goto edges on S, A, a and b; I1, I4, I5 and I6 hold complete items; I3 loops to itself on a.
Seven states; double borders mark states with a complete item. Source: sheet CD-08.

CD-09Cheat sheet1 pageIn a paid pack

CLR(1) and LALR(1) Parsing

LR(1) items and the closure rule that computes lookaheads from FIRST(βa). The ten canonical LR(1) states of S → AA, A → aA | b and how equal cores merge into the seven LALR(1) states. Why S → L = R | R is LALR(1) but not SLR(1), why a grammar can be CLR(1) but not LALR(1) (merging creates reduce-reduce conflicts, never shift-reduce ones), state-count facts for the standard grammars, LALR error detection, and a solved past question. Every state, lookahead and count comes from a script.

Get the full pack
Partial preview

A partial preview of the top of the sheet. The full sheet is in the Compiler Design cheat sheet pack.

Partial preview

CD-10Cheat sheet1 pageIn a paid pack

Which Parser Accepts Which Grammar

A master comparison of LL(1), LR(0), SLR(1), LALR(1) and CLR(1) parsers: direction, items, where reductions go, state counts and the conflicts each can have. A class map with seven script-checked separating grammars, including an LL(1) grammar that is not LALR(1), an ordered conflict-detection routine, statements about grammar classes that hold and those that do not, and the difference between grammar classes and language classes.

Get the full pack
Partial preview

A partial preview of the top of the sheet. The full sheet is in the Compiler Design cheat sheet pack.

Partial preview

Diagrams from CD-10

Nested boxes LR(0) inside SLR(1) inside LALR(1) inside CLR(1); a dashed LL(1) box lies inside CLR(1) and overlaps the other three. Points G1 to G7 mark the example grammars of the table on the same sheet.
G1 to G7 are the grammars in the table beside the diagram. Source: sheet CD-10.