Bottom Up Parsing Questions and Answers

Answer: C

Correct answer: True

LR parsing is incremental: actions run as reductions occur, so a translator can emit code, build tree fragments or write output long before the end of the input is reached. This is what makes single-pass compilation possible and why an LR parser can be used on a stream.

Answer: D

The parser may shift several times in a row or reduce several times in a row. There is no required alternation, and the counts of the two actions are generally different. The shift count equals the token count while the reduction count does not.

Answer: A

Every token is shifted exactly once, so ten shifts occur. The number of reductions depends on the grammar and is unrelated to the token count in any simple way. A grammar full of unit productions performs many more reductions than shifts.

Answer: B

Correct answer: reduces the augmented start production with the input exhausted

The grammar is augmented with a production from a new start symbol to the original one precisely so that acceptance has a definite marker: reducing that production with the end-of-input marker as lookahead is the accept action. An empty stack or a merely exhausted input is not the test.

Answer: C

Nothing in the grammar constrains what may be combined with what. An expression joining a string to the name of a function reduces without any complaint at all, and only the type checker holds the information needed to object to it. Form and meaning are separate questions, settled by separate phases of the compiler.

Answer: D

Correct answer: less specific, since the table knows states rather than constructs

A recursive descent parser fails inside a procedure named for the construct it was parsing, so it can say what it expected in the language’s own terms. An LR parser knows only that state 147 had no action on this token, and turning that into a message about a missing semicolon requires deliberate extra work.

Answer: A

Coverage and table size together are what settled the matter. Diagnostics are a known weakness, addressed by error productions rather than by the parsing method itself. A carefully written set of error rules narrows the gap considerably.

Answer: C

G is LALR(1), not SLR(1).

Follow(A) = {a, c}, because A is followed by a in S → Aa and by c in S → bAc. Consider the state reached after b then d. It contains A → d. (from S → b.Ac) and S → bd.a.

SLR(1) reduces A → d on every symbol in Follow(A), including a, but the item S → bd.a shifts a: a shift-reduce conflict, so G is not SLR(1).

With LR(1) lookaheads, A → d. in that state carries only the lookahead c (from S → bAc), so there is no conflict with shifting a. The state reached by d alone has A → d. with lookahead a and S → d.c shifting c, again without conflict. No two LR(1) states with the same core have clashing lookaheads, so merging them for LALR(1) introduces no conflict: G is LALR(1), and therefore CLR(1) too. That rules out the other three options.

Answer: D

The LR(0) ACTION table has 5 shift-reduce conflicts.

LR(0) reduces on every terminal whenever a state contains a complete item, so a state with both a complete item and an item that shifts a terminal has a conflict. Building the canonical LR(0) collection:

1. I₀ holds S′ → .S, S → .ACB, A → .aA and the complete item A → . (from A → ε): shift on a against reduce A → ε.
2. After a: A → a.A, A → .aA, A → . : the same conflict on a.
3. After A from I₀: S → A.CB, C → .cC, C → . : shift on c against reduce C → ε.
4. After c: C → c.C, C → .cC, C → . : the same conflict on c.
5. After b from S → AC.B: B → b.B, B → b., B → .bB, B → .b : shift on b against reduce B → b.

The remaining states (S → AC.B, the states with a single complete item such as A → aA., C → cC., B → bB., S → ACB., and the accept state) have no conflict. That makes 5, not 2, 3 or 4.