A grammar rule is left-recursive: Expr → Expr + Term. Which parser type handles this correctly, and why?
ATop-down (LL) parsers, because they predict rules before consuming input
BBoth equally well, since left recursion is handled by all modern parsers
CBottom-up (LR/shift-reduce) parsers, because they accumulate tokens and defer reduction decisions
DNeither; left-recursive grammars must always be refactored before parsing
Left recursion causes LL (top-down) parsers to loop infinitely: when trying to match Expr, the parser predicts Expr → Expr + Term, which immediately requires matching another Expr, ad infinitum. Shift-reduce parsers handle this naturally because they never predict — they simply shift tokens onto the stack and reduce only when the top of the stack matches a rule's right-hand side. When parsing '3 + 5', the parser shifts '3', reduces to Factor, then Term, then Expr. When it shifts '+' and '5' and reduces those, it has 'Expr + Term' on the stack, which matches the left-recursive rule and reduces to Expr. The deferral of decisions is what makes this work.
Question 2 Multiple Choice
During shift-reduce parsing of the expression '3 * 5 + 2', the parser has Expr on the stack and '+' as the next token. What should it do?
AImmediately reduce Expr to a higher-level nonterminal
BShift '+' onto the stack, because reducing now would discard context needed for precedence
CReport a shift-reduce conflict and halt
DBacktrack to try a different reduction sequence
This is a shift-reduce conflict: the parser must decide whether to reduce what's on the stack or shift the next token. Resolving it correctly requires knowing operator precedence. In a properly constructed parsing table for standard arithmetic grammar, '+' has lower precedence than '*', so after computing '3 * 5' = a Term, the parser shifts '+' rather than prematurely reducing — it needs to accumulate the right-hand side of the '+' operator. The correct answer demonstrates that shift-reduce parsers use lookahead and state information (not guessing or backtracking) to resolve conflicts deterministically.
Question 3 True / False
Shift-reduce parsers discover the rightmost derivation of an input, but in reverse order.
TTrue
FFalse
Answer: True
A rightmost derivation expands the rightmost nonterminal at each step, building the parse tree top-down. A shift-reduce parser processes input left-to-right and performs reductions that correspond to the last step of a rightmost derivation first (i.e., the deepest leaves get reduced first). At any point in parsing, the stack contains a prefix of a right-sentential form — a state that could appear in the middle of a rightmost derivation. Reductions peel away the last applied rule, effectively running the derivation backward from the leaves to the root.
Question 4 True / False
A shift-reduce parser can backtrack when it makes a wrong shift or reduce decision.
TTrue
FFalse
Answer: False
Shift-reduce parsers as implemented by LR parsing algorithms are deterministic — they make exactly one decision (shift or reduce) at each step based on the current parser state and a fixed lookahead token, with no backtracking. The parsing tables (ACTION and GOTO) are constructed to resolve conflicts in advance so that every state/lookahead combination has a unique action. If the grammar has genuine ambiguities that cannot be resolved, the parser reports a conflict at table construction time, not at parse time. This determinism is what gives LR parsing its linear O(n) time complexity.
Question 5 Short Answer
Explain why bottom-up (shift-reduce) parsing is described as 'more powerful' than top-down (LL) parsing.
Think about your answer, then reveal below.
Model answer: Bottom-up parsers handle a strictly larger class of grammars because they defer reduction decisions until sufficient context has accumulated on the stack. They naturally handle left-recursive rules (which break LL parsers) and ambiguities in operator associativity and precedence. LL parsers must predict which production to apply based only on the current input token and a small lookahead, which forces grammar transformations (elimination of left recursion, left factoring) that aren't always natural. LR parsers can also use more right-context before committing to a reduction.
The power difference comes from when decisions are made. An LL(k) parser must commit to an expansion by looking at k tokens ahead from the current position. An LR(k) parser can look at k tokens of lookahead *after* accumulating an entire handle on the stack — giving it the full left context (the stack) plus some right context (lookahead). This means LR parsing can distinguish situations that look identical to a top-down parser. In practice, most programming language grammars are LALR(1) — parseable by bottom-up parsers with just 1 token of lookahead — while many require grammar surgery to fit LL(1) constraints.