GATE CS 2015 Set 3 Q16 — Parsing (LL, LR)

To identify the correct pair, let's compare the three bottom-up parsing methods: Simple LR (SLR), Canonical LR (CLR), and Look-Ahead LR (LALR).

1. Ease of Implementation (Easiest): SLR
   • SLR parsers use the simple $LR(0)$ state machine.
   • The parsing table is constructed by placing reduce actions in the row of a state for all terminals in the $FOLLOW$ set of the non-terminal being reduced.
   • This makes SLR the simplest and easiest to implement among the three.
2. Parsing Power (Most Powerful): Canonical LR (CLR)
   • CLR (or $LR(1)$) uses explicit lookahead symbols within its states, preventing many shift-reduce and reduce-reduce conflicts that occur in SLR and LALR.
   • It can parse the largest class of deterministic context-free grammars (all $LR(1)$ grammars).
   • Therefore, CLR is the most powerful parser among the three.

Thus, the pair identifying the method that is very easy to implement and the method that is the most powerful, in that order, is SLR, canonical LR.