GATE CS 1999 Q1.17 — Parsing (LL, LR)

The power of a parsing method is determined by the class of context-free grammars it can successfully parse without conflicts.

The hierarchy of parsing power among the standard top-down and bottom-up parsers is as follows:

$$\text{LL}(1) \subset \text{SLR}(1) \subset \text{LALR}(1) \subset \text{LR}(1) \text{ (Canonical LR)}$$

• Canonical LR (LR(1)): It uses the complete lookahead information for each state, allowing it to resolve the maximum number of shift-reduce and reduce-reduce conflicts. Thus, it can parse the largest class of deterministic context-free languages.
• LALR(1): It merges states in the LR(1) parser that have the same core items but different lookaheads, which reduces the table size but can introduce reduce-reduce conflicts, making it less powerful than LR(1).
• SLR(1): It uses the simple FOLLOW set of non-terminals to make reduction decisions, which is less precise than the specific lookaheads used in LALR(1) and LR(1).
• LL(1): It is a top-down parsing method and is significantly less powerful than bottom-up parsers.

Hence, Canonical LR is the most powerful parsing method among the given options.