A shift-reduce parser carries out the actions specified within braces…
2009
A shift-reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of the grammar.
S → x x W [print “1”]
S → y [print “2”]
W → S z [print “3”]What is the translation of “x x x x y z z”?
Answer: C. 2 3 1 3 1 — Concept In a syntax-directed translation attached to a bottom-up (shift-reduce) parser, each semantic action written in braces after a production fires at the…
- A.
1 1 2 3 1
- B.
1 1 2 3 3
- C.
2 3 1 3 1
- D.
2 3 3 2 1
Attempted by 46 students.
Show answer & explanation
Correct answer: C
Concept
In a syntax-directed translation attached to a bottom-up (shift-reduce) parser, each semantic action written in braces after a production fires at the instant that production REDUCES a completed handle on the parse stack — not when its symbols are shifted. Because a bottom-up parser builds a rightmost derivation in reverse, the innermost (earliest-completed) handle always reduces first, so an action on a nested construct fires before the action on the production that encloses it.
Application
Shift the terminals x, x, x, x, y onto the stack (no right-hand side is complete yet); once y is on top it alone is the full right-hand side of S → y, so reduce it to S and fire print "2" — action 1. Stack: x x x x S.
Shift the next terminal, z; the top of the stack is now S z, the complete right-hand side of W → S z. Reduce it to W and fire print "3" — action 2. Stack: x x x x W.
The rightmost two x's together with this W form x x W, the complete right-hand side of S → x x W. Reduce it to S and fire print "1" — action 3. Stack: x x S.
Shift the final terminal, z; the top of the stack is again S z, matching W → S z. Reduce it to W and fire print "3" — action 4. Stack: x x W.
The remaining two x's together with this W again form x x W, matching S → x x W. Reduce it to S and fire print "1" — action 5. Stack: S, the start symbol — the whole input is accepted.
Cross-check
Rebuilding the parsed string bottom-up from this same trace confirms it is the only valid parse: the innermost S is "y", so the first W = "y"+"z" = "yz"; the next S = "x x"+"yz" = "xxyz"; the next W = "xxyz"+"z" = "xxyzz"; the outer S = "x x"+"xxyzz" = "xxxxyzz" — exactly the given input.
A second, structural check: every application of S → x x W needs exactly one W beneath it, and every W comes from exactly one W → S z reduction, so a valid translation always has an equal count of "1"s and "3"s, plus exactly one extra "2" from the single base-case S → y that starts the chain. The sequence 2, 3, 1, 3, 1 has two 1's, two 3's, and one 2, satisfying both checks.
The translation printed, in the order the reductions fire, is 2, 3, 1, 3, 1 — i.e., "2 3 1 3 1".