A grammar has no ε-productions or unit productions (the source gives types A→ε and A→a). What is the maximum number of bottom-up reduce moves when parsing n tokens?
Under the source’s intended restriction every reduction replaces at least two stack symbols with one, reducing stack length by at least one. Reducing n input symbols to the start symbol therefore needs at most n−1 reductions, achievable with binary productions. Thus B. The printed “unit production” example uses a terminal-looking a; the intended length-one exclusion is what makes this bound hold.
More Parsing and Syntax Analysis questions
GATE 2013 CS (CS1) Q50– Two LR(1) item sets share core X→c·X, X→·cX, X→·d. Their lookaheads are respectively c,d…
GATE 2011 CS (CS1) Q37– Binary operator ↓ has lower precedence than ↑. Operator ↑ is right-associative and ↓…