A grammar includes the rule: Expr → Expr + Term. A recursive descent (LL) parser encounters this rule and fails to parse. An LR parser handles it correctly. Why?
ARecursive descent parsers cannot handle the + operator; LR parsers have built-in support for arithmetic
BRecursive descent parsers guess the rule before reading input, so Expr → Expr + Term causes infinite recursion trying to expand Expr; LR parsers work bottom-up and have already parsed the left operand before deciding about the rule
CLR parsers use a larger lookahead window than recursive descent parsers, which is why they resolve left recursion
DRecursive descent parsers use a stack, which cannot represent left-recursive derivations
Left recursion is fatal for top-down parsers. When a recursive descent parser tries to parse Expr, it checks if this context matches Expr → Expr + Term — which immediately requires parsing another Expr, causing infinite recursion before reading any input. LR parsers avoid this because they are bottom-up: they shift tokens onto the stack, accumulating evidence, and reduce only when the right-hand side of a rule is fully assembled on top of the stack. By the time the parser recognizes Expr → Expr + Term, it has already parsed and reduced the left Expr — no recursion involved. This is the primary reason real language parser generators like yacc and bison produce LR parsers rather than LL parsers.
Question 2 Multiple Choice
During LR parsing of an expression, the parser has the state stack [..., Expr, +] and the next input token is a number. What does the parser do?
AReduce immediately — Expr + is enough to recognize a pattern
BShift the number token onto the stack, because more input is needed before a reduction is possible
CReport an error — a number cannot follow the + operator in this grammar
DReduce Expr + to a partial expression using a default rule
LR parsing is driven entirely by the parsing table, which encodes the correct action for each (state, lookahead) pair. With Expr and + on the stack and a number as lookahead, the parser has not yet assembled enough to complete a rule — it still needs to parse the right operand. The table will specify 'shift': push the number token and transition to a new state. Once enough tokens are shifted and the right-hand side of a rule appears on top of the stack, the table will specify 'reduce.' The shift/reduce decision is never guessed — it is determined deterministically by the precomputed table, which is why LR parsing is called deterministic.
Question 3 True / False
LR parsers, like recursive descent parsers, predict which grammar rule to apply by examining the next token before any input has been consumed.
TTrue
FFalse
Answer: False
False. This describes top-down parsing (LL), not LR. Recursive descent parsers try to predict which production to expand based on the current lookahead token, before reading the right-hand side. LR parsers are bottom-up: they read tokens left to right, shifting them onto a stack and waiting until the stack contains a complete right-hand side of some grammar rule — then reducing. LR parsers never predict; they accumulate evidence and recognize patterns after the fact. This fundamental difference is what allows LR parsers to handle left recursion and a larger class of grammars.
Question 4 True / False
LR parsers can handle left-recursive grammar rules (like Expr → Expr + Term) without requiring any rewriting of the grammar.
TTrue
FFalse
Answer: True
True. Left recursion is a natural and convenient way to express left-associative operators (a + b + c groups as (a + b) + c), and LR parsers handle it directly because their bottom-up approach has already reduced the left Expr before encountering the recursive rule. Top-down (LL) parsers require the grammar to be rewritten to eliminate left recursion, often at the cost of obscuring the intended associativity and precedence. This is a major reason why parser generators for real programming languages (yacc, bison, LALR tools) produce LR parsers.
Question 5 Short Answer
What does 'bottom-up' mean in the context of LR parsing, and why does this allow LR parsers to handle left-recursive grammars that top-down parsers cannot?
Think about your answer, then reveal below.
Model answer: Bottom-up parsing means building the parse tree from the leaves (input tokens) up toward the root (the start symbol). An LR parser reads tokens left to right, shifting each token onto a stack. When the top of the stack matches the right-hand side of a grammar rule, the parser reduces — popping those elements and pushing the left-hand side nonterminal. Because the left operand is shifted and reduced before the parser ever needs to decide about a left-recursive rule (like Expr → Expr + Term), there is no infinite regress. A top-down parser works the opposite direction — it starts from the start symbol and tries to derive input tokens — so it must expand Expr immediately when it encounters Expr → Expr + Term, causing infinite recursion before any input is consumed.
The stack is used in both approaches, but to do opposite things: a top-down parser uses the stack to track pending expansions (rules to apply to future input), while an LR parser uses the stack to accumulate already-consumed tokens and partial reductions. This reversal of direction is what enables LR parsers to handle the full class of deterministic context-free languages.