Translation schemes with embedded actions; tracing what an SDT prints or computes

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Which parser evaluates an S-attributed SDD during parsing, and how? from Lesson 3.2
• Under default YACC rules, what is 2 + 3 * 4 + 5 for E → E + E | E * E | n? from Lesson 2.4.7
• Which actions does a shift-reduce parser perform? from Lesson 2.4.1

1 · The Story

📖

Read-aloud instructions

For a children’s show, Mrs. Desai asks Anaya to turn arithmetic phrases into a form a calculator can read: numbers first, then the operator. Anaya writes tiny instructions inside Kabir’s rules, between the parts: “after reading the second number of a plus-phrase, say ‘plus’”.

Where an instruction sits decides when it is said. Put “say plus” before the second number and the audience hears “9 minus 5 plus 2”; put it after and they hear “9 5 minus 2 plus”, calculator order.

The audience hears instructions in exactly the order of a walk around Kabir’s chart: down the left side first, each instruction spoken when the walk passes its position.

2 · Predict First

🤔

With E → T R, R → + T {print('+')} R | − T {print('−')} R | ε, T → num {print(num.val)}, what is printed for 9 − 5 + 2? Write your guess down. The answer is in the vault.

3 · Core Concept

Translation schemes

A syntax-directed translation scheme (SDT) is a grammar with semantic actions (program fragments in braces) embedded anywhere in production bodies, for example R → + T {print('+')} R. An action is executed when everything to its left in the body has been recognised.

Equivalently: build the parse tree, add each action as an extra leaf at its position, and do a depth-first, left-to-right walk executing actions when the walk reaches them.

Postfix translation schemes

When every action is at the right end of its production (a postfix SDT), each action runs exactly at the reduction. That is how an S-attributed SDD is implemented on an LR parser.

From an L-attributed SDD to a scheme

• Put the action computing an inherited attribute of X immediately before X.
• Put the action computing a synthesized attribute of the head at the end of the production.

Example: D → T {L.inh = T.type} L.

Actions in the middle and LR parsers

An LR parser executes code only at reductions. An action in the middle of a body, A → α {act} β, is handled by a fresh marker nonterminal: A → α M β, M → ε {act}. Markers can create new conflicts, which is one reason middle actions are used sparingly with LR parsers.

How to trace an output (method)

• Build the parse tree from the grammar (ignore the actions).
• Insert each action as a leaf at its position in its production.
• Walk depth-first, left to right; print as you reach actions.

Story → compiler term

4 · Visual

Parse tree of 9 − 5 + 2 with the actions inserted as pink leaves. Walking left to right prints 95-2+ (computed).

5 · Worked Examples

Example 1 Easy

Trace the infix-to-postfix scheme on 9 − 5 + 2.

Solution

Walk the tree above: T → 9 prints 9; inside R → − T R: T prints 5, then print('−'); inside the next R → + T R: T prints 2, then print('+'); R → ε prints nothing. Output 95-2+, the calculator order of Anaya’s show.

Example 2 Medium

Move each print to just after the operator: R → + {print('+')} T R. What is printed now?

Solution

Now each operator is printed before its right operand: 9-5+2. Same grammar, same tree: only the instruction positions changed.

Example 3 GATE

S → a a W {print 1} | b {print 2}; W → S c {print 3}. What is printed for a a a a b c c?

Solution

Tree: S → a a W, W → S c, S → a a W, W → S c, S → b. Walk: the innermost S → b prints 2; then its W prints 3, then that S prints 1; then the outer W prints 3, then the outer S prints 1. Output 23131 (computed by running the scheme on the parse tree).

6 · Shortcuts

⚡

End-of-production actions = postorder: for a postfix scheme, the output is the sequence of reductions; list them bottom-up. Valid when: schemes whose actions are all at the right end.

⚡

Recursive grammars print in nesting order: in S → x S {act}, the innermost act prints first; in S → x {act} S, the outermost prints first. Valid when: right-recursive and left-recursive patterns.

7 · GATE Traps

⚠️

• Build the tree from the grammar first; actions do not change the parse.
• An action prints when the walk reaches its position, not when the production starts.
• ε-productions with actions still execute them (once per ε node).
• Moving an action from the end to the middle can turn postfix output into infix or prefix.
• Middle actions need markers in LR parsers.

8 · Memory Hook

🧠

Actions are leaves: walk the tree left to right and say them as you pass.

9 · Connect the Dots

Translation schemes can do more than print: they can build data structures. The next lesson builds a compact outline of the program for later phases and checks types, the main jobs of the Meaning Desk.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksTrace

S → A S {print 1} | A {print 2}; A → a {print 3} | b {print 4}. What is printed for a b b a? (Enter the digits as one number.)

Numerical answer: ________

Q2NAT2 marksTrace

Same grammar with actions moved: S → A {print 1} S | {print 2} A; A → {print 3} a | b {print 4}. What is printed for a b b a?

Numerical answer: ________

Q3MCQ1 markPostfix

With E → E + T {print('+')} | E − T {print('−')} | T, T → num {print(num.val)}, the output for 9 − 5 + 2 is:

• (A) 9-5+2
• (B) 95-2+
• (C) +-952
• (D) 952-+

Q4MCQ1 markPrefix

Moving the operator prints to the start, E → {print('+')} E + T | {print('−')} E − T | T, the output for 9 − 5 + 2 is:

• (A) +-952
• (B) -+952
• (C) 95-2+
• (D) 9-5+2

Q5MSQ1 markFacts

Which are true about translation schemes?

• (A) An action runs when everything to its left in the body has been recognised.
• (B) A postfix scheme can be executed by an LR parser at reductions.
• (C) Actions change the parse tree.
• (D) A middle action in an LR parser can be implemented with a marker nonterminal.

11 · Rule Card

• 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.

12 · Concept Ledger

translation scheme (SDT)semantic actionpostfix SDTmarker nonterminalinfix → postfix translation

13 · Answer Vault