ACompressed recap
🧾
A translation scheme embeds actions in production bodies. To trace it: build the parse tree from the grammar, insert actions as leaves at their positions, and walk depth-first left to right. Actions at the ends give a postfix scheme, executed at reductions by an LR parser. Moving an action changes the output (postfix ↔ infix ↔ prefix). Middle actions in LR parsers need marker nonterminals.
BMerged rule card
3.3 Translation schemes with embedded actions; tracing what an SDT prints or computes
- SDT = grammar + actions {…} inside bodies.
- Execution = depth-first left-to-right walk; action runs when reached.
- Postfix SDT (actions at ends) = S-attributed on LR.
- L-attributed → SDT: inherited before the symbol, synthesized at the end.
- Middle actions in LR: marker M → ε {act}.
- Trace: tree first, insert actions as leaves, walk.
CInterleaved GATE-style questions
Q1NAT2 marksTrace
S → a a W {print 1} | b {print 2}; W → S c {print 3}. Output for a a b c?
Numerical answer: ________
Q2NAT2 marksTrace
S → ( {print 1} S ) {print 2} S | {print 0}. Output for ( ( ) ) ( )? (digits as one number)
Numerical answer: ________
Q3MCQ2 marksTrace
S → A {print 'S'} B; A → a {print 'x'} A | a {print 'y'}; B → b B {print 'z'} | {print 'w'} b. Output for a a b b b?
- (A) xySwzz
- (B) xySzzw
- (C) yxSwzz
- (D) xyswzz
Q4MCQ1 markPostfix
A translation scheme whose actions are all at the right end of productions:
- (A) cannot be run by an LR parser
- (B) is executed at reductions by an LR parser
- (C) must have inherited attributes
- (D) prints in prefix order
Q5NAT1 markTrace
E → T R, R → + T {print('+')} R | − T {print('−')} R | ε, T → num {print(num.val)}. How many characters are printed for 9 − 5 + 2?
Numerical answer: ________
Q6MSQ1 markMarkers
Which are true about A → α {act} β in an LR parser?
- (A) It can be rewritten A → α M β, M → ε {act}.
- (B) The marker can introduce new conflicts.
- (C) The action must be moved to the start.
- (D) LR parsers execute code only at reductions.
Q7MCQ2 marksInfix
With E → T R, R → + {print('+')} T R | − {print('−')} T R | ε, T → num {print(num.val)}, the output for 9 − 5 + 2 is:
- (A) 95-2+
- (B) 9-5+2
- (C) +-952
- (D) 9-+52
Q8MCQ1 markMethod
To find what a translation scheme prints, the first step is:
- (A) execute actions in the order written in the grammar
- (B) build the parse tree from the grammar
- (C) convert to a dependency graph
- (D) count the actions
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 2312 marks
S → b prints 2, W prints 3, outer S prints 1: 231.
Re-read: Lesson 3.3 — Translation schemes with embedded actions; tracing what an SDT prints or computes
Q2 Answer: 11020210202 marks
Computed by walking the parse tree: 1102021020.
Re-read: Lesson 3.3 — Translation schemes with embedded actions; tracing what an SDT prints or computes
Q3 Answer: (A)2 marks
Computed: xySwzz. A prints x then y; then S; B prints w at the innermost b first, then z twice on the way back.
- (B) is wrong: w is printed before the zs (innermost B first).
- (C) is wrong: x comes before y.
- (D) is wrong: Upper-case S.
Re-read: Lesson 3.3 — Translation schemes with embedded actions; tracing what an SDT prints or computes
Q4 Answer: (B)1 mark
Each action runs when its production is reduced.
- (A) is wrong: It is the easiest case for LR.
- (C) is wrong: It implements S-attributed definitions.
- (D) is wrong: Output order is postorder.
Re-read: Lesson 3.3 — Translation schemes with embedded actions; tracing what an SDT prints or computes
Q5 Answer: 51 mark
95-2+ has 5 characters.
Re-read: Lesson 3.3 — Translation schemes with embedded actions; tracing what an SDT prints or computes
Q6 Answer: (A) (B) (D)1 mark
The action keeps its position; the marker carries it.
Re-read: Lesson 3.3 — Translation schemes with embedded actions; tracing what an SDT prints or computes
Q7 Answer: (B)2 marks
Operators print between operands now (computed).
- (A) is wrong: That is the end-of-production placement.
- (C) is wrong: Prefix needs actions before the left operand.
- (D) is wrong: Order of operators preserved.
Re-read: Lesson 3.3 — Translation schemes with embedded actions; tracing what an SDT prints or computes
Q8 Answer: (B)1 mark
Output order follows the tree walk.
- (A) is wrong: Grammar order is not execution order.
- (C) is wrong: Not needed for schemes.
- (D) is wrong: Counting does not give order.
Re-read: Lesson 3.3 — Translation schemes with embedded actions; tracing what an SDT prints or computes