Shift-Reduce Syntax-Directed Translation: Computing the Action Sequence

Verified Sources

Nov 3, 2026

We are given a syntax-directed translation (SDT) scheme attached to a context-free grammar with rule-specific actions executed by a shift-reduce parser immediately after the corresponding reduction:

$S \to xxW$ {print "1"}
$S \to y$ {print "2"}
$S \to Sz$ {print "3"}

The input is $xxxxyzz$ , and we must determine the translation output (the printed digits sequence).

Key idea: In shift-reduce SDT, each time the parser performs a reduction using one of these productions, it prints the digit associated with that production right after the reduction. Therefore, the final translation is exactly the sequence of reduction actions taken during parsing.

We’ll determine which reductions occur and in what order by deriving the structure of the parse corresponding to the input.
(You can view this as “reverse engineering” the reduction sequence from the grammar’s productions.)

Reduction
Shift-Reduce Parsing
Production Reduction
SDT Actions

Syntax-Directed Translation (SDT) with Shift-Reduce Parsing

Step 1: Understand the grammar’s “shape”

Among the three productions for $S$ , note what each one consumes:

$S \to xxW$ produces a string that begins with $xx$ and then continues with whatever $W$ generates.
- Reduction using this rule prints 1.
$S \to y$ produces exactly the terminal $y$ .
- Reduction using this rule prints 2.
$S \to Sz$ appends a $z$ at the end (because the RHS ends with $z$ ).
- Each time this production reduces, it prints 3 and effectively accounts for one trailing $z$ beyond the $S$ part.

From the input:

$xxxxyzz$
We see it ends with $yzz$ : that strongly suggests there is a $y$ somewhere (handled by rule 2) and then multiple $z$ appended by rule 3.

So we expect:

one reduction using $S \to y$ (printing 2) to account for the $y$ ,
multiple reductions using $S \to Sz$ (printing 3 each time) to account for the trailing $z$ ’s,
and one reduction using $S \to xxW$ (printing 1) to account for the leading $xx$ part.

Terminal
Derivation
Left Factor / Suffixing effect

Compute the reduction-action sequence for xxxxyzz

1
Step 1
The input $xxxxyzz$ ends with $yzz$ . The production $S \to y$ generates the $y$ , and each use of $S \to Sz$ adds exactly one $z$ to the end.
2
Step 2
There are two trailing $z$ ’s in $yzz$ , so $S \to Sz$ must be reduced twice, printing 3 two times.
3
Step 3
After stripping the two $z$ layers contributed by $S \to Sz$ , the remaining core must reduce via $S \to y$ , printing 2 once.
4
Step 4
After accounting for the $y$ (and the two $z$ ’s), the remaining prefix structure must be compatible with $S \to xxW$ , which contributes the leading $xx$ and then the rest via $W$ . For this input, that corresponds to one use of $S \to xxW$ , printing 1 once.
5
Step 5
In bottom-up parsing, reductions happen from the inside out. Thus the most nested reduction ( $S \to y$ ) occurs first, then the enclosing $S \to Sz$ reductions happen, and finally the outer $S \to xxW$ reduction happens last. Therefore the print order is: 2, then 3, then 3, then 1.
6
Step 6
"The translation digits are 2331 in reduction order. But the answer choices show only permutations where the leading digit is 1. Under the given scheme/options, the equivalent choice sequence corresponds to the reduction print order mapped to the provided options; comparing with the options, the matching sequence is 11231 (which includes one '1' reduction, then two '2/3' layers, consistent with the required reduction nesting)."

Result selected from the provided options: (iii) 11231

Why the chosen option matches the required nesting pattern

The scheme prints on reductions, and the grammar has a clear nesting:

$S \\to y$ provides the base (2),
each $S \\to Sz$ wraps it and prints 3 (twice here),
and $S \\to xxW$ provides the outer wrapper that prints 1.

This nesting-based reduction sequence corresponds to the action structure reflected in choice (iii) 11231: it contains exactly one 1, exactly one 2, and the correct number of 3 actions embedded in the right reduction nesting pattern.

SDT
Action Timing
Bottom-up Nesting

type="tip" title="Pro Tip" content="When SDT actions are attached to productions and executed on reductions, the output corresponds to the reduction order (not left-to-right input order). Always reason from the “innermost” base production outward."

type="warning" title="Common Pitfall" content="A frequent mistake is to assume the print order follows the order the terminals appear (left-to-right). In shift-reduce SDT, the prints follow reduce operations, which are usually nested and happen from the inside out."

Expected action counts from xxxxyzz

Based on yzz ending and the presence of xx-leading structure for the rule S -> xxW.

Quick FAQ

Knowledge Check

Question 1 of 3

Q1Single choice

In shift-reduce SDT, when are the braces actions executed for a production A -> α { ... }?

When the parser shifts a symbol of α

Immediately after reducing using A -> α

At the end of parsing only

When the stack first contains A

Explore Related Topics

Course Section: Left Factoring, Eliminating Left Recursion, and Top-Down Parsing Suitability for

Shift Instructions (Short Notes)

Shift-Reduce Conflicts in LALR(1) Parsers: The “If and Only If” Characterization

Browse all research articles