Parsing
Parsing MCQs
Q1. Which of the following statements about top-down parsing is true?
A. It starts with the input symbols and tries to reach the start symbol.
B. It uses rightmost derivation in reverse.
C. It can be implemented using recursive procedures.
D. It handles left recursion efficiently.
Answer: C
Solution: Top-down parsers (like recursive descent or LL) expand from the start symbol and can be implemented using recursive procedures. They cannot handle left recursion.
Q2. Which parsing technique does not require backtracking?
A. Recursive descent parsing
B. LL(1) parsing
C. Operator precedence parsing
D. Both B and C
Answer: D
Solution: LL(1) and operator precedence parsers use lookahead to predict production rules — hence no backtracking is needed.
Q3. For a grammar to be LL(1), which of the following must hold?
A. No ambiguity and no left recursion
B. Left recursion allowed, ambiguity removed
C. Only left factoring required
D. Grammar must be right-linear
Answer: A
Solution: LL(1) grammars must be unambiguous, left recursion–free, and left-factored so that a single lookahead can decide the next production.
Q4. Consider the grammar:
S → aSb | εWhich of the following strings is not generated by this grammar?
A. ε
B. ab
C. aabb
D. abab
Answer: D
Solution: This grammar generates strings with equal numbers of a and b in proper nesting (like parentheses). abab violates this nesting.
Q5. In shift-reduce parsing, a handle is:
A. A substring that matches the right-hand side of a production and whose reduction represents one step along a reverse rightmost derivation
B. A substring that represents a valid prefix
C. Always the first symbol on the stack
D. A substring derived from the start symbol directly
Answer: A
Solution: Handles represent a point in the rightmost derivation during bottom-up parsing where a reduction is valid.
Q6. The parsing table for an LR(0) parser has 15 states and 5 terminals. What is the maximum number of shift entries possible?
A. 15
B. 20
C. 75
D. 60
Answer: C
Solution: Each of 15 states can have up to 5 terminal transitions → 15 × 5 = 75 possible shift entries.
Q7. Which of the following is a characteristic of SLR(1) parsing?
A. Uses FOLLOW sets to decide reduce actions
B. Uses lookahead symbols and item sets with closure
C. More powerful than canonical LR(1)
D. Cannot detect shift-reduce conflicts
Answer: A
Solution: SLR uses FOLLOW sets to resolve reduce actions, while LR(1) uses specific lookaheads in item sets.
Q8. Consider the grammar:
E → E + T | T
T → T * F | F
F → (E) | idThis grammar is:
A. LL(1)
B. LR(1)
C. Ambiguous
D. Operator-precedence grammar
Answer: C
Solution: This is the classic ambiguous expression grammar due to lack of precedence and associativity enforcement.
Q9. A parser reports a shift-reduce conflict. What does it mean?
A. Parser cannot decide whether to shift or reduce at a certain step
B. Parser found more than one production for the same non-terminal
C. Parser failed to compute FOLLOW sets
D. Parser encountered left recursion
Answer: A
Solution: In LR parsing, a shift-reduce conflict occurs when both actions are possible for the same parser state and lookahead.
Q10. Predictive parsing uses lookahead of:
A. 0
B. 1
C. 2 or more
D. Unlimited
Answer: B
Solution: Predictive parsers (LL(1)) use one lookahead symbol to make decisions — hence the name LL(1).
- For the grammar
S → Aa | b
A → bWhich derivation produces the string ba?
A. S ⇒ Aa ⇒ ba
B. S ⇒ b (no further production)
C. S ⇒ Aa ⇒ b a (invalid)
D. None of the above
Answer: A
Solution: S ⇒ Aa, A ⇒ b gives ba. Option B gives b only, not ba.
- Left factoring is primarily used to:
A. Eliminate left recursion
B. Make grammar suitable for LL(1) parsing by removing common prefixes
C. Make grammar LR(1)
D. Increase ambiguity
Answer: B
Solution: Left factoring rewrites productions with common prefixes so a single lookahead can choose the correct alternative.
- The FIRST set of a string
αin grammar analysis returns:
A. All tokens that can appear immediately to the right of α in some sentential form
B. All nonterminals that derive α
C. The set of terminals that can appear at the beginning of strings derived from α
D. FOLLOW set of α
Answer: C
Solution: FIRST(α) is the set of terminals that can start strings derived from α (including ε if α can derive empty).
- For LL(1) grammar decision, if
A → α | β, what must hold?
A. FIRST(α) ∩ FIRST(β) = ∅ and if ε ∈ FIRST(α) then FIRST(β) ∩ FOLLOW(A) = ∅ (and symmetric)
B. FOLLOW(α) = FOLLOW(β)
C. Both α and β must start with different nonterminals
D. α and β must both be terminal-only strings
Answer: A
Solution: LL(1) requires non-overlapping FIRST sets and conflict-free handling when ε is possible.
- Consider grammar:
S → AB
A → a | ε
B → bWhat is FIRST(S)?
A. {a}
B. {a, b}
C. {b}
D. {ε}
Answer: B
Solution: A can be a or ε. If A ⇒ a, FIRST includes a. If A ⇒ ε, FIRST(S) includes FIRST(B) = b. So {a,b}.
- A grammar with production
A → A α | βis:
A. Right-recursive
B. Left-recursive
C. LL(1) friendly
D. Ambiguous only
Answer: B
Solution: A appears on the left of right-hand side immediately → left recursion; needs elimination for top-down parsing.
- In bottom-up parsing, which derivation does the parser simulate?
A. Leftmost derivation in reverse
B. Rightmost derivation in reverse
C. Leftmost derivation forward
D. Rightmost derivation forward
Answer: B
Solution: Shift-reduce (LR) parsers conceptually perform reductions corresponding to steps of the rightmost derivation in reverse.
- Which of these is true about LR(1) vs SLR(1)?
A. SLR(1) uses individual lookahead tokens per item like LR(1)
B. LR(1) is more powerful; SLR(1) may have spurious conflicts due to coarse FOLLOW-based reduces
C. SLR(1) is always more powerful than LR(1)
D. Both are identical in power
Answer: B
Solution: LR(1) stores lookaheads per item, preventing many conflicts that SLR (which uses FOLLOW) cannot avoid.
- For grammar:
S → Aa | b
A → cWhich parsing action sequence (shift/reduce) leads to ca?
A. shift c, reduce A → c, shift a, reduce S → Aa
B. shift c, shift a, reduce S → Aa
C. reduce A before shift c
D. impossible
Answer: A
Solution: Shift c then reduce A→c gives A, then shift a, then reduce S→Aa.
- Which grammar type is required to express matched parentheses nesting of arbitrary depth?
A. Regular grammar
B. Context-free grammar
C. Context-sensitive grammar only
D. Finite automaton
Answer: B
Solution: Matched nesting is context-free (e.g., S → (S)S | ε) and cannot be handled by regular grammars.
- For LR(0) items, the dot (
·) signifies:
A. End-of-input marker
B. Current position in right-hand side showing what has been recognized so far
C. A special terminal
D. Lookahead symbol
Answer: B
Solution: · indicates progress in an item—symbols left of dot are recognized in that state.
- A grammar is ambiguous if:
A. There exists at least one string with two distinct parse trees (or derivations)
B. FIRST and FOLLOW sets overlap
C. It has left recursion
D. It has right recursion only
Answer: A
Solution: Ambiguity means at least one string can be derived in more than one way (different parse trees).
- Consider grammar for arithmetic with precedence:
E → E + T | T
T → T * F | F
F → (E) | idWhich method eliminates ambiguity and enforces precedence?
A. Use left-factored grammar only
B. Rewrite grammar with separate nonterminals for precedence (as shown actually does this if associativity specified) or use operator precedence parsing
C. Make grammar right-recursive only
D. Use lexical tricks only
Answer: B
Solution: The grammar as written actually imposes precedence (T over E); enforcing associativity/precedence or using operator precedence parsing resolves ambiguity.
- In LR parsing, a reduce-reduce conflict means:
A. The parser can choose any reduction; both are equivalent
B. There are two possible reductions in same state for same lookahead and parser cannot decide
C. Shift and reduce both available
D. The grammar must be regular
Answer: B
Solution: Reduce-reduce conflict indicates ambiguity in which production to reduce—parser generator must resolve or grammar modified.
- For grammar:
S → 0 S 1 | 0 1What language does it generate?
A. Balanced zeros and ones in nesting like 0^n 1^n, n ≥ 1
B. Any string of 0s and 1s
C. Only 01
D. Strings with more ones than zeros
Answer: A
Solution: Each recursive step adds matching 0 and 1 around S, producing 0^n 1^n for n≥1.
- LL(1) parsing table for nonterminal
Aand terminalacontains which production?
A. If a ∈ FIRST(α), then A → α is placed at (A,a)
B. If a ∉ FIRST(α)
C. Only if a ∈ FOLLOW(A)
D. Always empty
Answer: A
Solution: LL(1) table uses FIRST sets to guide placement; if α can derive ε, FOLLOW(A) entries considered too.
- Which of the following grammars is not LL(1) without transformation?
A.S → a A | bandA → c
B.S → a A | a B
C.S → A Bwith disjoint FIRST sets
D.S → a
Answer: B
Solution: S → aA | aB has same FIRST token a for two productions → conflict, needs left factoring.
- Which property allows LR parsers to handle a larger class of grammars than LL parsers?
A. Use of left recursion only
B. Using bottom-up recognition and lookahead allowing shift/reduce decisions based on context
C. Fewer table entries
D. No need for FIRST/FOLLOW sets
Answer: B
Solution: Bottom-up LR parsers can make decisions based on entire right context via item sets and lookaheads, handling many left-recursive grammars LL cannot.
- Consider a grammar with nullable nonterminal
A(A ⇒ ε). In LL(1) table filling, what additional terminals are used besides FIRST(A)?
A. FOLLOW(A) are used for entries when ε ∈ FIRST(A)
B. No additional terminals used
C. Only $ (EOF) used
D. FIRST of other nonterminals
Answer: A
Solution: If A can derive ε, productions for A must be placed in table cells for terminals in FOLLOW(A).
- Which is true about canonical LR(1) parser compared to LALR(1)?
A. LALR(1) is strictly more powerful than LR(1)
B. Canonical LR(1) distinguishes lookahead per item and thus may have more states than LALR(1) which merges states with identical cores
C. LR(1) and LALR(1) always produce identical tables
D. LALR(1) never has conflicts if LR(1) doesn’t
Answer: B
Solution: LR(1) keeps lookaheads per item, producing potentially more states; LALR merges states, possibly introducing conflicts but often smaller tables.
- For the grammar
S → AB
A → aA | ε
B → bB | εWhat is FOLLOW(A)? (Assume $ is end marker and S is start)
A. {a}
B. {b, $}
C. {a, b}
D. {$ only}
Answer: B
Solution: A is followed by B in S→AB. FIRST(B) includes b and ε; because B can be ε, FOLLOW(A) includes FOLLOW(S) which is {$}. So {b, $}.
- Which algorithm is used to construct LR(0) automaton states?
A. Compute FIRST sets directly
B. Closure and goto operations over LR(0) items via subset / canonical collection construction
C. Thompson construction only
D. KMP algorithm
Answer: B
Solution: LR(0) automaton built by taking closure of items and computing goto (state transitions) to form canonical collection.
- For grammar
E → E + E | E * E | id, is this grammar suitable for precedence-rule parsing?
A. Yes, ambiguous but precedence and associativity rules can be applied in parser generator
B. No, impossible to parse
C. LL(1) as is
D. Regular grammar
Answer: A
Solution: Grammar is ambiguous; parser generator can use precedence/associativity declarations to resolve conflicts (e.g., prefer * over +).
- In an LR parser, the parser stack stores:
A. Only tokens
B. States and grammar symbols (terminals/nonterminals) alternately
C. Only states
D. Only semantic values
Answer: B
Solution: Stack stores states and grammar symbols—usually state on top, enabling shift/reduce actions.
- For grammar
S → (S) | SS | ε, which parsing method is natural?
A. LL(1) easily
B. Bottom-up (LR) handles it; grammar is ambiguous but left-most derivable forms exist
C. Regular expression-based scanning only
D. None
Answer: B
Solution: This grammar is ambiguous (for concatenation), but LR parsers can handle many ambiguous-looking grammars with appropriate disambiguation or prefer leftmost reductions.
- Left recursion elimination of
A → A α | βproduces:
A.A → β A'andA' → α A' | ε
B.A → A αonly
C. Grammar becomes ambiguous
D. Not possible
Answer: A
Solution: Standard transformation: factor out left recursion by introducing new nonterminal A’.
- Which of these is a typical cause of shift-reduce conflict in expression grammars?
A. Missing precedence/associativity declarations for operators
B. Left-factoring needed
C. Presence of only terminals
D. Empty grammar
Answer: A
Solution: Without precedence/associativity, parser may not know whether to shift (read further operator) or reduce (complete a subexpression), causing conflicts.
- When computing FOLLOW(A), if A appears in production
B → α A, what is included?
A. FIRST(α)
B. FOLLOW(B)
C. FIRST(A)
D. Nothing
Answer: B
Solution: If A is last symbol of production, FOLLOW(A) includes FOLLOW(B).
- The LR(1) item
[A → α · β, a]means:
A. Lookaheadais allowed after this item and parser expects β next
B.ais the dot symbol
C. It’s identical to LR(0) item always
D. This item indicates reduction ready
Answer: A
Solution: LR(1) item tracks lookahead a that will be valid after α β derivation; the dot indicates scanning next symbol β.
- Which grammar is LL(1) after left factoring?
A.S → if E then S else S | if E then S
B.S → a S | b S
C.S → (S) | S S | ε
D.S → a | ab
Answer: A (after left factoring)
Solution: The if-then-else classic needs left factoring to resolve if E then S vs if E then S else S by factoring common prefix if E then S and considering lookahead to disambiguate else.
- For LR parsing, which of the following reduces the parser’s table size with minimal loss of power?
A. Convert to LL(1)
B. Use LALR(1) which merges LR(1) states with same cores
C. Use LR(0) always
D. Use regular expressions
Answer: B
Solution: LALR(1) merges LR(1) states with identical cores, significantly reducing table size while often preserving parsing power.
- Which is a distinguishing feature of GLR (Generalized LR) parsing?
A. Only handles regular languages
B. Can parse all context-free grammars, including ambiguous ones, by exploring multiple parse alternatives in parallel
C. Equivalent to LL(1) always
D. Only deterministic grammars
Answer: B
Solution: GLR explores multiple parse possibilities simultaneously and produces parse forests for ambiguous inputs.
- A predictive parser uses what data structure to decide on production selection?
A. Stack for nonterminals and parser table indexed by nonterminal and lookahead terminal
B. Queue only
C. Tree only
D. No structure — pure recursion
Answer: A
Solution: Predictive (LL(1)) parser uses a stack with top nonterminal and a parsing table dictating production based on lookahead.
- Which grammar transformation may change the language if done incorrectly?
A. Left factoring always safe
B. Left recursion elimination must preserve language; incorrect steps can change generated strings
C. Computing FIRST sets changes language
D. FOLLOW sets alter parsing language
Answer: B
Solution: Left recursion elimination has standard correct method; incorrect restructuring (e.g., incorrect factoring) can change language.
- Consider grammar
S → a S b | a bWhich strings are generated?
A. ab, aabb, aaabbb, … (a^n b^n, n≥1)
B. All ab repetitions and interleavings
C. Only ab
D. None
Answer: A
Solution: Recursion wraps a and b producing equal numbers in proper nesting: a^n b^n for n≥1.
- In parsing theory, what is a “sentential form”?
A. A string in the language only
B. Any string of terminals and nonterminals reachable from start symbol by some derivation
C. Only the start symbol
D. Only sequences of terminals
Answer: B
Solution: Sentential form includes mixtures of terminals/nonterminals generated during derivations.
- SLR parsing uses which set to decide reduce actions?
A. FIRST sets only
B. FOLLOW sets of corresponding nonterminals
C. The grammar’s terminals only
D. No sets are used
Answer: B
Solution: SLR uses FOLLOW sets for reduce actions (coarser than LR(1)’s lookaheads).
- For LL(1) parser, table cell conflict indicates:
A. Grammar is not LL(1) and needs transformation (left-factoring, remove left recursion) or it’s ambiguous
B. Parser is fine
C. Reduce-reduce conflict only
D. EOF error
Answer: A
Solution: Conflicts show that single lookahead is insufficient; transformations or other parser types required.
- What is the purpose of the augmented grammar
S' → Swhen building LR parsers?
A. To add more productions
B. To provide unique start production and allow detecting acceptance whenS' → S ·is reduced and lookahead is$
C. To make grammar ambiguous
D. To remove left recursion
Answer: B
Solution: Augmented grammar adds new start S’ to detect successful parse when S is fully reduced and EOF seen.
- Which parsing technique can naturally handle indentation-sensitive languages (e.g., Python) by receiving INDENT/DEDENT tokens from lexer?
A. LL(1) predictive parser with lexer cooperation
B. LR parsers with lexer that emits INDENT/DEDENT; parser handles them like ordinary tokens
C. Both A and B (lexer cooperation needed)
D. None — indentation must be ignored
Answer: C
Solution: Both parser types can handle indentation if lexer generates INDENT/DEDENT tokens; cooperation needed.
- A grammar
S → a S b | bis changed to remove left recursion — is it necessary?
A. Left recursion not present; no change needed
B. Must transform to right recursion
C. Grammar is ambiguous
D. Cannot parse
Answer: A
Solution: Grammar is right-recursive (a S b) not left-recursive; no elimination needed for top-down parsing.
- For grammar
A → B c | dandB → ε, FIRST(A) includes:
A.conly
B.dandc
C.donly
D.εonly
Answer: B
Solution: B can be ε so A → c effectively possible, giving c; also d directly possible. So {c,d}.
- Which parsing method uses a parse table indexed by nonterminals and terminals and a stack?
A. Shift-only parser
B. Predictive LL(1) parsing
C. Regex parser
D. GLR only
Answer: B
Solution: LL(1) predictive parser uses table lookups to decide productions based on top nonterminal and lookahead terminal.
- Which is an advantage of table-driven parsing over recursive descent?
A. Table-driven can be generated automatically (e.g., LR table generators) and handles more grammars (LR) than straightforward recursive descent (LL)
B. Recursive descent handles all grammars better
C. Table-driven requires less memory always
D. Recursive descent uses tables internally
Answer: A
Solution: Table-driven parsers (LR) can handle left recursion and larger grammar classes; recursive descent needs manual coding and transformations.
- For grammar with production
A → α B β, how is FOLLOW(B) influenced?
A. Include FIRST(β) except ε; if β ⇒ ε, include FOLLOW(A)
B. Include FIRST(A) always
C. FOLLOW not affected by surrounding symbols
D. Include only terminals of β
Answer: A
Solution: Standard rule: FOLLOW(B) includes FIRST(β) minus ε; if β nullable, include FOLLOW(A).
- What does “leftmost derivation” mean?
A. At each step the rightmost nonterminal is replaced
B. Always replace the leftmost nonterminal in the current sentential form at each derivation step
C. Replace both ends simultaneously
D. Only terminals are replaced
Answer: B
Solution: Leftmost derivation expands the leftmost nonterminal at every step.
- Which grammar property ensures that a DFA-based lexical analyzer is sufficient?
A. Grammar is context-free
B. Tokens described by regular languages — lexical analysis is regular-language based
C. Grammar must be LL(1)
D. Grammar uses indentation
Answer: B
Solution: Lexical tokens are regular; DFAs (regular language recognizers) are sufficient for lexing.
- In an LR parse table, what does an entry
s5typically represent?
A. Shift and go to state 5 (push state 5) for the input terminal
B. Reduce using production 5
C. Accept
D. Error
Answer: A
Solution: s5 denotes shift action and transition to state 5.
- What does an entry
r3in shift-reduce table indicate?
A. Shift using rule 3
B. Reduce by production number 3
C. Restart parsing at state 3
D. Reject input
Answer: B
Solution: r3 is reduce action applying production 3.
- Consider grammar
S → 'a' S 'b' | 'a' 'b' | ε. Is it ambiguous?
A. No — unique parses exist for each string
B. Yes —abmay have multiple derivations because ε could be used differently
C. Yes — some strings have multiple parse trees
D. None of the above
Answer: A
Solution: This grammar generates nested balanced a’s and b’s including empty; derivations are unique due to strict nesting—no ambiguity.
- Which parser strategy is most commonly used by modern compiler generators (e.g., Bison) for general purpose?
A. LL(1) only
B. LALR(1) historically (Bison), now GLR option for ambiguous grammars; LR-family favored for robustness
C. RE-based parsing
D. Handwritten parser only
Answer: B
Solution: Bison uses LALR(1) by default and supports GLR; LR-family parsers handle many practical programming languages.
- In operator-precedence parsing, what is required between terminals to decide actions?
A. Precedence relation table indicating<·,=·,>·relationships between terminals
B. FIRST sets only
C. FOLLOW sets only
D. No table, just associativity
Answer: A
Solution: Operator-precedence parsing uses precedence relations between terminals to decide shift/reduce.
- Which grammar cannot be parsed by an LL(1) parser even after left factoring?
A. One that is inherently left-recursive and cannot be right-factored easily
B. One that requires more than 1 lookahead to distinguish alternatives (not LL(k) for k=1)
C. Both A and B could be reasons
D. All grammars are LL(1) after transformations
Answer: C
Solution: Some grammars require more lookahead than 1 or need transformations that change language; they cannot be LL(1).
- A parser that builds the parse tree as it recognizes the input and uses explicit stack operations is most likely:
A. Top-down recursive descent
B. Bottom-up shift-reduce (LR) style
C. Regular expression matcher
D. None of the above
Answer: B
Solution: Shift-reduce parsers operate via stack actions and perform reductions that correspond to constructing subtrees.
- The canonical collection of LR(0) items has 10 states. Adding lookahead to make LR(1) may produce:
A. The same number of states always
B. More states (possibly many more) since lookaheads differentiate otherwise identical cores
C. Fewer states
D. No effect on tables
Answer: B
Solution: LR(1) distinguishes items by lookahead, possibly expanding states dramatically compared to LR(0).
- Which of these is true for ambiguous grammars when using GLR parser?
A. GLR fails on ambiguous grammars
B. GLR returns a shared-packed parse forest representing all possible parses
C. GLR discards ambiguity silently
D. GLR converts grammar to LL(1) first
Answer: B
Solution: GLR generates a compact parse forest containing all parse trees for ambiguous inputs.
- A grammar has FIRST(A) containing ε. For LL(1) table, what must be done for terminal
a∈ FOLLOW(A)?
A. Place A → α in table cell (A, a) when ε ∈ FIRST(α)
B. Ignore FOLLOW sets in LL(1)
C. Always place error
D. Put arbitrary production
Answer: A
Solution: When α can be ε, LL(1) places the production under terminals in FOLLOW(A) to allow choosing ε-production.
- Which parsing conflict is resolved by declaring operator associativity (e.g., left-assoc)?
A. Shift-reduce conflicts involving occurrence of same precedence operator consecutively (e.g.,a - b - c)
B. Reduce-reduce conflicts always
C. Missing tokens only
D. None
Answer: A
Solution: Associativity resolves whether to reduce or shift when operators of same precedence appear (left-assoc means reduce).
- For grammar
S → A | B, where FIRST(A) ∩ FIRST(B) ≠ ∅, the grammar:
A. Is LL(1)
B. Is not LL(1) unless transformed (left-factored or otherwise)
C. Is regular
D. Is unconditionally LR(0)
Answer: B
Solution: Overlapping FIRST sets cause LL(1) conflicts; transformations needed or use a more powerful parser.
- In bottom-up parsing, which of the following identifies a handle?
A. The leftmost derivable substring to be reduced corresponding to the rightmost derivation in reverse
B. Rightmost prefix only
C. Nonterminal only
D. Terminal only
Answer: A
Solution: Handle is the substring that matches RHS of a production and whose reduction does one step in reverse of rightmost derivation.
- Which grammar requires left recursion elimination to be used with recursive descent parser?
A.A → A α | βtypes (direct left recursion)
B.A → α A | β(right recursion fine)
C. Regular grammars only
D. None
Answer: A
Solution: Direct left recursion causes infinite recursion in naive top-down parsers; eliminate it.
- For grammar rules producing many nullable symbols causing FIRST sets to include ε, complexity of computing FIRST/FOLLOW is:
A. O(1) always
B. Requires careful iterative fixed-point computation until convergence; complexity proportional to grammar size and dependencies
C. Not computable
D. Depends on token count only
Answer: B
Solution: FIRST/FOLLOW computed iteratively until stable; worst-case proportional to grammar size but practical.
- The LR parser reduces by
A → αwhen:
A. Top of stack matches α and lookahead is in FOLLOW(A) (depending on parser type)
B. Always when α appears anywhere
C. Only at end of input
D. Never
Answer: A
Solution: Reduction done when α is on stack and lookahead permits reduction (SLR uses FOLLOW(A), LR(1) uses item-specific lookaheads).
- Which parser can handle arbitrary lookahead tokens easily at the cost of state explosion?
A. LL(1)
B. LR(k) for large k (canonical LR(k))
C. Recursive descent easily
D. None of the above
Answer: B
Solution: Canonical LR(k) with large k increases discriminator power but causes state explosion in practice.
- In many parser generators,
%precdirective is used to:
A. Assign precedence to grammar productions to resolve shift-reduce conflicts
B. Compute FIRST sets
C. Remove left recursion
D. Define start symbol
Answer: A
Solution: %prec attaches precedence to reduce actions, influencing conflict resolution for ambiguous operator grammar.
- Which grammar simplification does NOT change the language?
A. Removing useless symbols and productions (symbols that never derive terminal strings or are unreachable)
B. Randomly merging productions
C. Adding extra productions that produce ε improperly
D. Changing terminals
Answer: A
Solution: Removing unreachable or non-generating symbols preserves the language.
- A
"dangling else"problem arises because:
A. Grammar forif-then-elseallows two parses forif E1 then if E2 then S else S— ambiguity between matchingelsewith nearestifor outerif.
B. Lexical ambiguity only
C. Only in LR parsers
D. Caused by parser tables only
Answer: A
Solution: The classic dangling-else ambiguity is typically resolved by grammar rewrite or preference rules (attach else to innermost if).
- Which of these is a parsing expression for nullable production?
A.A → ε
B.A → aonly
C.A → a | b
D. None
Answer: A
Solution: A → ε explicitly produces empty string; nullable means can derive ε.
- In building LL(1) table, if production
A → αand FIRST(α) contains ε, then table entries for A include:
A. FIRST(α) minus ε and also entries for terminals in FOLLOW(A) mapping toA → α
B. Only terminals in FOLLOW(A)
C. Nothing
D. All terminals
Answer: A
Solution: Standard LL(1) table construction rule.
- Which parser type uses parse actions generated from LR automaton and is robust for programming languages?
A. Recursive descent only
B. LR-family parsers (LR(0), SLR(1), LALR(1), LR(1))
C. Regex-based only
D. None
Answer: B
Solution: LR-family parsers are widely used for programming languages due to robustness and power.
- Which of the following can simplify a grammar for parsing but may increase parse table size?
A. Duplicating productions to remove common prefixes (unfolding)
B. Minimizing productions always
C. Converting terminals to nonterminals only
D. Removing start symbol
Answer: A
Solution: Unfolding can make grammar easier for LL parsing but increases number of productions and table entries.
- For canonical LR(1), each item includes a lookahead token. Why is that useful?
A. It allows finer reduction decisions preventing spurious conflicts compared to LR(0) or SLR(1)
B. It’s unnecessary overhead always
C. It decreases correctness
D. It is used for lexical analysis only
Answer: A
Solution: Lookaheads help decide whether a reduction applies in context, eliminating some conflicts.
- Which of the following is NOT part of parse tree construction?
A. Creating interior nodes for nonterminals corresponding to applied productions
B. Attaching terminals as leaves in correct order
C. Executing semantic actions during reductions (optional)
D. Generating bytecode directly in lexing phase
Answer: D
Solution: Bytecode generation happens later (codegen); lexing doesn’t produce parse tree nodes.
- A grammar with
A → B CandB → εrequires what in FIRST/FOLLOW computations?
A. FIRST(A) includes FIRST(B) excluding ε and FIRST(C) if B nullable; FOLLOW(B) includes FIRST(C) etc.
B. FIRST and FOLLOW unaffected
C. FOLLOW(B) includes only terminals of B
D. FIRST(C) ignored
Answer: A
Solution: When B nullable, FIRST(C) contributes to FIRST(A) and FOLLOW relations consider FOLLOWs appropriately.
- Which of these is necessary to verify if a grammar is LR(0)?
A. Build LR(0) items and canonical collection; check for shift/reduce or reduce/reduce conflicts without lookahead
B. Only inspect FIRST sets
C. Only inspect FOLLOW sets
D. Convert grammar to regular expression
Answer: A
Solution: LR(0) determination requires canonical item construction; conflicts indicate not LR(0).
- Which parser is good when grammar contains many ambiguities but you want all parse possibilities?
A. LL(1)
B. GLR (Generalized LR) which returns parse forest of all parses
C. LR(0) only
D. None
Answer: B
Solution: GLR explores multiple parses concurrently and is suited for ambiguous grammars.
- For grammar
S → 'a' S | 'b' S | ε, what language is described?
A. All strings over {a,b} (including empty)
B. Onlyabstrings
C. Only nonempty strings
D. Strings of alternating letters only
Answer: A
Solution: This grammar allows any number of a or b in any order including empty → Σ*.
- Which of the following is required to compute LL(1) parsing table entries correctly?
A. FIRST and FOLLOW sets for all nonterminals
B. LR(1) items only
C. Token frequency counts
D. Lexeme lengths
Answer: A
Solution: FIRST and FOLLOW are fundamental to LL(1) table construction.
- In SLR parsing, a reduce action for
A → αis placed in state i for lookaheadaif:
A. Item[A → α·]is in state i anda ∈ FOLLOW(A)
B.a ∈ FIRST(α)
C.ais any token
D. Only if state i is start state
Answer: A
Solution: SLR uses FOLLOW(A) to decide reduce lookaheads when the item is complete.
- What is the main idea behind Earley parsing?
A. Compute all possible parses in O(n^3) general CFG time, O(n^2) for unambiguous, O(n) for certain grammars using dynamic programming with states called Earley items
B. Use regex only
C. It is a form of LL(1)
D. Only for regular grammars
Answer: A
Solution: Earley algorithm handles all CFGs with dynamic programming, efficient for many grammar classes.
- Which of the following grammars is suitable for operator precedence parsing?
A. Grammars where precedence relations can be placed between terminals and no productions are ε or unit productions only
B. Any grammar automatically
C. Only regular grammars
D. None
Answer: A
Solution: Operator-precedence parsing requires that grammar be operator-precedence (no ε or ambiguous operator contexts) to define relations between terminals.
- Which transformation preserves language and makes grammar right-recursive?
A. Converting left recursionA → A α | βintoA → β A'withA' → α A' | ε(right recursion)
B. Left-factoring always
C. Randomly swapping symbols
D. Removing terminals
Answer: A
Solution: Standard left recursion elimination yields right-recursive form preserving language.
- Which parser error recovery strategy attempts to continue parsing after encountering an error?
A. Panic-mode recovery: discard input tokens until a synchronizing token found (e.g.,;) and resume
B. Abort immediately always
C. Return partial parse tree only
D. Ignore errors silently
Answer: A
Solution: Panic-mode is a common simple recovery; more sophisticated methods attempt local repairs.
- When is a grammar LR(1) but not LALR(1)?
A. When merging LR(1) states with identical cores would cause lookahead sets to combine and create conflicts that canonical LR(1) avoids
B. Always identical
C. Never possible
D. Only for regular grammars
Answer: A
Solution: LALR merges states by core causing lookahead mixes that can introduce conflicts absent in full LR(1).
- Which of these is a correct reduction action for production
A → X Yin bottom-up parsing?
A. Pop symbols corresponding toX Yfrom stack and pushA(and goto next state)
B. PushX Yonly
C. PopAonly
D. Do nothing
Answer: A
Solution: Reduction removes RHS and replaces with LHS nonterminal on stack, with state transition via goto.
- Which of the following is true for a deterministic context-free language?
A. Can be parsed by deterministic pushdown automaton (DPDA) and often by LR parsers
B. Equivalent to regular languages only
C. All CFLs are deterministic
D. Only by nondeterministic PDA
Answer: A
Solution: Deterministic CFLs recognized by DPDA and commonly parseable by LR-family parsers.
- In LALR(1) parsing table construction, why might conflicts appear that canonical LR(1) avoided?
A. Because LALR merges states with same cores thus combining their lookahead sets which can create ambiguous reduce entries
B. Because LALR uses less lookahead than LR(0)
C. Because LALR ignores FOLLOW sets always
D. None of the above
Answer: A
Solution: Merging items with identical cores unifies lookaheads, potentially introducing conflicts.
- For grammar
E → E + T | T, left recursion elimination yields:
A.E → T E'andE' → + T E' | ε
B.E → E + Tonly
C.E → Tonly
D. Not transformable
Answer: A
Solution: Standard elimination produces E followed by tail E’ capturing repeated + T occurrences.
- Which of the following is true about parse forests?
A. Represent multiple parse trees compactly for ambiguous inputs (shared substructures)
B. Always a single tree only
C. Only used in LR(0)
D. Not useful
Answer: A
Solution: Parse/packed forests combine common subtrees to represent all parses without exponential blowup.
- A grammar with productions
A→ a A b | a bis parsed by which of the following?
A. Both top-down (after transformation) and bottom-up; bottom-up naturally handles it, top-down needs care for left recursion (none here)
B. Only LL(1) without change
C. Only LR(0)
D. Not parseable
Answer: A
Solution: The grammar is right-recursive nested pattern a^n b^n; bottom-up handles it naturally; top-down can parse as-is since no left recursion.
About the Author
