Questions: Lookahead in Parsing and Grammar Classes
5 questions to test your understanding
Score: 0 / 5
Question 1 Multiple Choice
An LL(1) parser and an LR(1) parser both use exactly one token of lookahead. Why is LR(1) strictly more powerful?
ALR(1) parsers read tokens from right to left, gaining more context about the input structure
BLR(1) parsers encode the complete left context (everything already parsed) in their state, so the same single lookahead token carries more disambiguating information in combination with that accumulated context
CLR(1) parsers use a stack of tokens rather than a single lookahead, effectively seeing multiple symbols ahead
DLR(1) parsers can backtrack and try alternative parses when a conflict occurs
The key insight is that 'one token of lookahead' means different things for LL and LR parsers. An LL(1) parser decides which production to expand based on: the current nonterminal + one lookahead token. An LR(1) parser decides based on: its current state (which encodes the *entire* left context — all input already parsed) + one lookahead token. The LR state contains far more information than just the current nonterminal, which is why LR(1) grammars strictly include all LL(1) grammars.
Question 2 Multiple Choice
A grammar has an LL(1) conflict because two productions for nonterminal A both can follow the same FIRST token. Which approach will NOT genuinely resolve the conflict?
ALeft-factor the grammar to share the common prefix in a single production before branching
BSwitch to an LR(1) parser generator, since LR(1) can handle this grammar class
CIncrease the lookahead to LL(2), which may resolve the conflict if the second token disambiguates
DUse a Yacc/PLY parser, since it automatically resolves all conflicts via default shift/reduce rules
Yacc/PLY-style LALR parsers 'resolve' conflicts by applying default rules (prefer shift over reduce, prefer earlier rule over later), which silently produces a parser that may accept incorrect programs. This is not a real fix — it hides the conflict rather than resolving it. Left-factoring (option A) is the correct grammar-rewriting approach. Switching to LR (option B) works if the grammar is LR(1). Increasing to LL(2) (option C) may genuinely resolve some conflicts. Option D is the trap: automatic conflict resolution is not the same as correctly handling the grammar.
Question 3 True / False
Every grammar that is LL(1) is also LR(1), but not every LR(1) grammar is LL(1).
TTrue
FFalse
Answer: True
The parsing power hierarchy is strict: LL(1) ⊂ LR(1). Any grammar an LL(1) parser can handle can also be handled by an LR(1) parser. The converse is false: many LR(1) grammars — including those with left recursion — cannot be handled by LL(1) parsers at all, because LL parsers must predict which production to expand before consuming input, while LR parsers defer the decision until the full left context is accumulated.
Question 4 True / False
An LR(1) parser examines more tokens of lookahead than an LL(1) parser, which is why it can handle more grammars.
TTrue
FFalse
Answer: False
Both LL(1) and LR(1) examine exactly one token of lookahead — the '1' in each name means one token. LR(1)'s greater power comes from its state, not from seeing further ahead. The LR automaton's state encodes the complete left context of the parse, providing far more disambiguating information than just the current nonterminal. The single lookahead token is combined with this rich state to make decisions impossible for a top-down parser seeing only the current nonterminal and one token ahead.
Question 5 Short Answer
Why can't an LL parser handle left-recursive grammars, even with increased lookahead?
Think about your answer, then reveal below.
Model answer: An LL parser works top-down: it selects a production to expand by looking ahead in the input. With a left-recursive production like A → A α | β, expanding A via A → A α immediately requires expanding A again — an infinite loop. The parser consumes no input while recursing, so no amount of lookahead resolves the problem; the issue is structural, not informational. LR parsers avoid this by building bottom-up: they recognize the 'A' subexpression from actual input tokens before deciding it is an A, with no need to predict the recursive structure upfront.
Left recursion is the clearest example of a structural grammar property that prevents LL parsing regardless of lookahead amount. It can be eliminated by grammar transformation (replacing left recursion with right recursion and iteration), but this changes the grammar's structure and can complicate semantic action embedding.