Chapter 20 of 33

Syntax-Directed Translation Schemes

A recipe that says "the cake is flour plus eggs plus sugar, baked" tells you what the result is made of, but not when to crack the eggs. In the previous chapter, Syntax-Directed Definitions, we wrote rules like E.val = E1.val + T.val. Those rules say what each attribute equals, but not when the computation happens while the parser is running.

A real compiler cannot afford to parse the whole program, build a full parse tree, draw a dependency graph and only then compute things. It wants to do the work during parsing, at exactly the right moment. To say "at exactly this moment", we write the actions directly inside the productions.

A syntax-directed translation scheme (SDT) is a context-free grammar with program fragments, called semantic actions, embedded within the production bodies. An action is written in braces, and it is executed as soon as all the grammar symbols to its left have been matched.

In this chapter we will see how the position of an action fixes when it runs, implement postfix SDTs on an LR parser stack, see how Bison handles actions in the middle of a production, remove left recursion from an SDT without breaking it, and turn an L-attributed SDD into a working recursive-descent translator. The traces and outputs below were produced by real programs (a small SLR parser in Python, a C translator compiled with GCC, and Bison 3.8.2).


Actions Inside Productions

Here is a translation scheme that converts infix expressions with + and - into postfix (operands first, then the operator):

E → E1 + T    { print('+') }
E → E1 - T    { print('-') }
E → T
T → digit     { print(digit.lexval) }

The braces are part of the production body. A good way to understand an SDT is to imagine each action as an extra leaf in the parse tree, placed where it appears in the body. Then perform a depth-first, left-to-right traversal and execute each action when you reach its leaf. For the input 9 - 5 + 2:

E
├── E
│   ├── E
│   │   └── T
│   │       ├── 9
│   │       └── {print(9)}
│   ├── -
│   ├── T
│   │   ├── 5
│   │   └── {print(5)}
│   └── {print('-')}
├── +
├── T
│   ├── 2
│   └── {print(2)}
└── {print('+')}

Actions met in left-to-right order:  print(9)  print(5)  print('-')  print(2)  print('+')
Output:  9 5 - 2 +

The output 95-2+ is the postfix form of (9 − 5) + 2. Notice that the left associativity of the grammar is preserved: the subtraction is done first.

The position of an action is everything. Take the production B → X { a } Y:

  • In a top-down parser, a runs after X has been fully expanded and matched, and just before we try to match Y.

  • In a bottom-up parser, a runs as soon as X appears on top of the stack.

Either way, the meaning is the same: "do a right after X". Move the action and you change the translation, as one of the solved problems below shows.

SDD vs SDT

Point

Syntax-Directed Definition (SDD)

Syntax-Directed Translation Scheme (SDT)

What is attached

Semantic rules, attached to whole productions

Actions, placed at specific positions in a body

Order of evaluation

Not specified; found from the dependency graph

Fixed by the position of each action

Style

Specification: "what"

Implementation: "what and when"

Notation

Table of production / rule

A → X { action } Y

Typical use

Reasoning, exam derivations

Writing the translator (Yacc/Bison, recursive descent)


Postfix SDTs: All Actions at the End

A postfix SDT is an SDT in which every action is at the right end of its production body.

Any S-attributed SDD can be turned into a postfix SDT by putting each production's rules, as one action, at the end of the production. For the desk calculator:

L → E n          { print(E.val) }
E → E1 + T       { E.val = E1.val + T.val }
E → T            { E.val = T.val }
T → T1 * F       { T.val = T1.val × F.val }
T → F            { T.val = F.val }
F → ( E )        { F.val = E.val }
F → digit        { F.val = digit.lexval }

Why is "at the end" so convenient? In a bottom-up parser, the end of a production is the moment of reduction. At that moment, all the symbols of the body are sitting on top of the stack, together with their attributes, so the action has everything it needs.

Implementing It on the LR Stack

An LR parser keeps a stack of states. We simply give each stack entry a second field that holds the attribute value of the grammar symbol that the state represents. When the parser reduces by T → T1 * F:

  1. The top three entries hold F (top), *, and T1, with their values.

  2. Run the action using those values: val = stack[top−2].val × stack[top].val.

  3. Pop three entries, push the state for T, and store the computed value in it.

Here is the full trace for 3 * 5 + 4, produced by an SLR parser built from the grammar above (without the L → E n line). For readability, the stack column shows grammar symbols with their values in brackets instead of state numbers.

Step

Stack (symbol[val])

Input

Action

1

(empty)

3 * 5 + 4 $

shift

2

digit[3]

* 5 + 4 $

reduce F → digit, val = 3

3

F[3]

* 5 + 4 $

reduce T → F, val = 3

4

T[3]

* 5 + 4 $

shift

5

T[3] *

5 + 4 $

shift

6

T[3] * digit[5]

+ 4 $

reduce F → digit, val = 5

7

T[3] * F[5]

+ 4 $

reduce T → T * F, val = 3 × 5 = 15

8

T[15]

+ 4 $

reduce E → T, val = 15

9

E[15]

+ 4 $

shift

10

E[15] +

4 $

shift

11

E[15] + digit[4]

$

reduce F → digit, val = 4

12

E[15] + F[4]

$

reduce T → F, val = 4

13

E[15] + T[4]

$

reduce E → E + T, val = 15 + 4 = 19

14

E[19]

$

accept

Each "reduce" line is one action being executed, and the actions run in exactly the postorder of the annotated parse tree from the previous chapter. No tree was built. This is precisely what Yacc and Bison do: in an action, $1, $2, ... are the values of the body symbols on the stack, and $$ is the value of the head (see Yacc & Bison).


Actions in the Middle: Marker Nonterminals

What if an action is not at the end, as in B → X { a } Y? A bottom-up parser only "does" things at reductions, and there is no reduction between X and Y. The trick is to create one:

B → X { a } Y          becomes          B → X M Y
                                        M → ε   { a }

M is a new marker nonterminal that derives the empty string. The parser reduces M → ε right after X is on the stack, and that reduction runs a. Every SDT can be made postfix this way.

There is a catch: the new ε-production can introduce parsing conflicts. The parser must decide to reduce M → ε before it has seen Y, and if another production could also continue after X, it may not know whether this M belongs here. So an SDT that is easy to write may become impossible to parse with LR once mid-rule actions are added.

Bison Does Exactly This

Bison allows mid-rule actions and converts them into marker nonterminals automatically, naming them $@1, $@2, and so on. Here is a small infix-to-postfix translator with a mid-rule action at the very start of line:

%{
#include <stdio.h>
#include <ctype.h>
int yylex(void);
void yyerror(const char *s) { fprintf(stderr, "error: %s\n", s); }
%}
%token NUM
%left '+' '-'
%left '*' '/'
%%
lines : lines line
      | %empty
      ;
line  : { printf("postfix: "); } expr '\n'   { printf("\n"); }
      ;
expr  : expr '+' expr    { printf("+ "); }
      | expr '-' expr    { printf("- "); }
      | expr '*' expr    { printf("* "); }
      | expr '/' expr    { printf("/ "); }
      | '(' expr ')'
      | NUM              { printf("%d ", $1); }
      ;
%%
int yylex(void) {
    int c = getchar();
    while (c == ' ' || c == '\t') c = getchar();
    if (isdigit(c)) {
        int v = 0;
        while (isdigit(c)) { v = v * 10 + (c - '0'); c = getchar(); }
        ungetc(c, stdin);
        yylval = v;
        return NUM;
    }
    if (c == EOF) return 0;
    return c;
}
int main(void) { return yyparse(); }

Build and run it (here in WSL, with Bison 3.8.2 and GCC):

$ bison -v -o postfix.tab.c postfix.y
$ gcc -std=c17 -Wall postfix.tab.c -o postfix
$ printf '3 + 4 * 2\n(3 + 4) * 2\n10 - 4 - 3\n' | ./postfix
postfix: 3 4 2 * +
postfix: 3 4 + 2 *
postfix: 10 4 - 3 -

The -v option writes the grammar Bison really used into postfix.output, and there is our marker nonterminal:

    3 $@1: ε

    4 line: $@1 expr '\n'

The mid-rule action became the action of rule 3, $@1 → ε. Also notice that the expr rules are written with an ambiguous grammar; %left resolves the conflicts so that * binds tighter and operators are left associative, which is why 10 - 4 - 3 becomes 10 4 - 3 -.


The General Method: Build the Tree First

Some SDTs cannot be run during parsing at all, because the parser would need to execute an action before it knows which production it is in. For example, an action at the very start of a body, E → { print('+') } E1 + T, wants to run before any part of E1 has been seen, but an LR parser does not know yet that it is inside this production.

Such SDTs can always be implemented in two passes:

  1. Parse the input and build the parse tree, ignoring the actions.

  2. Add each action as an extra leaf child at its position in the body.

  3. Do a preorder (depth-first, left-to-right) traversal, executing each action leaf when it is visited.

This always works but costs time and memory for the whole tree. The two special cases below, postfix SDTs on LR parsers and L-attributed SDTs on LL parsers, avoid building the tree.


Eliminating Left Recursion from an SDT

A top-down parser cannot handle left recursion (Ambiguity, Left Recursion & Left Factoring). If our SDT is left recursive, we must transform the grammar while keeping the actions in the right order. The rule is simple:

When eliminating left recursion from an SDT, treat each action as if it were a terminal symbol and apply the usual transformation. The actions then stay in the same relative order.

The usual transformation turns A → A α | β into A → β R and R → α R | ε. Applying it to the postfix SDT with α1 = + T { print('+') }, α2 = - T { print('-') } and β = T:

E → T R
R → + T { print('+') } R
  | - T { print('-') } R
  | ε
T → digit { print(digit.lexval) }

This version is LL(1) and prints exactly the same thing. We checked both versions on two inputs:

Input

Left-recursive SDT (bottom-up)

Transformed SDT (top-down)

9 - 5 + 2

95-2+

95-2+

8 - 3 - 1 + 6

83-1-6+

83-1-6+

This works for actions that only print. If the actions compute attribute values, removing left recursion also changes which values are available where, and we need inherited attributes to carry the left operand into R. That is the next section.


SDTs for L-Attributed SDDs

An L-attributed SDD can be converted to an SDT that runs in one top-down pass. The placement rules follow directly from "compute everything just in time":

  1. Inherited attributes of a nonterminal X: put the action that computes them immediately before X in the body. (If several inherited attributes depend on each other, order the actions so each value is computed before it is needed.)

  2. Synthesized attributes of the head: put the action that computes them at the end of the body.

Applying these rules to the expression SDD with inherited attributes (from the previous chapter, extended with + and -):

E  → T       { E'.inh = T.val }
     E'      { E.val = E'.syn }

E' → + T     { E1'.inh = E'.inh + T.val }
     E1'     { E'.syn = E1'.syn }
   | - T     { E1'.inh = E'.inh - T.val }
     E1'     { E'.syn = E1'.syn }
   | ε       { E'.syn = E'.inh }

T  → F       { T'.inh = F.val }
     T'      { T.val = T'.syn }

T' → * F     { T1'.inh = T'.inh × F.val }
     T1'     { T'.syn = T1'.syn }
   | ε       { T'.syn = T'.inh }

F  → ( E )   { F.val = E.val }
   | digit   { F.val = digit.lexval }

Recursive-Descent Implementation

The translation to code is mechanical, and worth remembering for interviews:

  • Each nonterminal becomes a function.

  • Its inherited attributes become the function's parameters.

  • Its synthesized attributes become the function's return value.

  • Actions become ordinary statements, placed where they appear in the SDT.

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

static const char *p;              /* next input character */

static void skip(void) { while (*p == ' ') p++; }

static int F(void);
static int Eprime(int inh);
static int Tprime(int inh);

/* E -> T { E'.inh = T.val } E' { E.val = E'.syn } */
static int E(void)  { int t = F(); t = Tprime(t); return Eprime(t); }

/* E' -> + T { E1'.inh = E'.inh + T.val } E1' { E'.syn = E1'.syn }
       | - T { E1'.inh = E'.inh - T.val } E1' { E'.syn = E1'.syn }
       | epsilon { E'.syn = E'.inh }                              */
static int Eprime(int inh) {
    skip();
    if (*p == '+' || *p == '-') {
        char op = *p++;
        int t = Tprime(F());                 /* T -> F T' */
        int newinh = (op == '+') ? inh + t : inh - t;
        return Eprime(newinh);
    }
    return inh;
}

/* T' -> * F { T1'.inh = T'.inh * F.val } T1' { T'.syn = T1'.syn }
       | epsilon { T'.syn = T'.inh }                              */
static int Tprime(int inh) {
    skip();
    if (*p == '*') {
        p++;
        int f = F();
        return Tprime(inh * f);
    }
    return inh;
}

/* F -> digit { F.val = digit.lexval } | ( E ) { F.val = E.val } */
static int F(void) {
    skip();
    if (isdigit((unsigned char)*p)) return *p++ - '0';
    if (*p == '(') { p++; int v = E(); skip(); if (*p++ != ')') exit(1); return v; }
    fprintf(stderr, "syntax error at '%c'\n", *p); exit(1);
}

int main(void) {
    const char *tests[] = { "3*5+4", "8-3-2", "2*(7-4)*3", "9-2*3-1" };
    for (int i = 0; i < 4; i++) {
        p = tests[i];
        printf("%-10s = %d\n", tests[i], E());
    }
    return 0;
}

(To keep the code short, the call T() is written inline as Tprime(F()): F's value becomes T'.inh and T' returns T.val.) Output with gcc -std=c17 -Wall:

3*5+4      = 19
8-3-2      = 3
2*(7-4)*3  = 18
9-2*3-1    = 2

Look at 8-3-2 = 3. The grammar is now right recursive, which would naturally group the input as 8 − (3 − 2) = 7, the wrong answer. The inherited attribute fixes that: it carries the running value 8, then 8 − 3 = 5, then 5 − 2 = 3 down the chain, so the computation is done left to right. Inherited attributes are how a top-down translator keeps left associativity.

L-attributed SDTs can also be run on an LR parser, by using marker nonterminals to compute inherited attributes and keep them on the stack (Bison exposes this through $0 and mid-rule values), but that is more delicate and is rarely asked in exams.


Solved Problems

Problem 1: What Does It Print?

Consider the SDT below and assume a bottom-up parser (or, equivalently, a depth-first left-to-right walk of the parse tree).

S → a T   { print("1") }
S → b     { print("2") }
T → S c   { print("3") }
T → d     { print("4") }

What is printed for the input aaadcc?

Solution. First find the parse. Every S starts with a (then T) or is just b; every T is S c or d. Matching from the outside in:

S → a T                    a  [ a a d c ]  c   ... T must be "aadcc"
    T → S c                    S = "aadc"
        S → a T                a [ a d c ]     T = "adc"
            T → S c                S = "ad"
                S → a T            a [ d ]     T = "d"
                    T → d

Tree:
S(1)
├── a
└── T(3)
    ├── S(1)
    │   ├── a
    │   └── T(3)
    │       ├── S(1)
    │       │   ├── a
    │       │   └── T(4)
    │       │       └── d
    │       └── c
    └── c

Each action runs when its production is reduced, which is when the subtree below it is complete (postorder). The innermost reduction is T → d, then the S above it, then the T above that, and so on outward:

T → d   prints 4
S → a T prints 1
T → S c prints 3
S → a T prints 1
T → S c prints 3
S → a T prints 1

Answer: 413131. (For comparison, aabcc prints 23131 and b prints 2.)

Problem 2: Moving an Action

In the transformed SDT from the left-recursion section, move each print of an operator to before its operand:

E → T R
R → + { print('+') } T R
  | - { print('-') } T R
  | ε
T → digit { print(digit.lexval) }

What is printed for 9 - 5 + 2?

Solution. Walk left to right: T prints 9; R sees - and prints - before calling T, which prints 5; the next R prints +, then 2. The output is 9-5+2, the original infix string. Same grammar, same actions, different positions, different translation.

Problem 3: An S-Attributed Postfix SDT with an ε-Production

Write a postfix SDT that computes the maximum nesting depth of a balanced parenthesis string generated by S → ( S ) S | ε, and find the depth of (()(())).

Solution.

S → ( S1 ) S2    { S.d = max(S1.d + 1, S2.d) }
S → ε            { S.d = 0 }

The first S1 is inside one more pair of parentheses, hence the + 1; S2 is a following sibling group at the same level. For (()(())): the outer pair encloses ()(()), whose depth is max(1, 2) = 2, so the total is 2 + 1 = 3. (Checked by evaluating the parse tree: ()() gives 1 and ((()))() gives 3.)


Common Mistakes

  • Ignoring the position of an action. A → X {a} Y and A → X Y {a} are different translations.

  • Executing actions in preorder of nonterminals instead of at their actual positions. An action at the end of a production runs only after the whole subtree is finished.

  • Forgetting that marker nonterminals can cause conflicts. Adding a mid-rule action can make an LALR grammar non-LALR.

  • Removing left recursion and leaving actions in the wrong place. Treat actions as terminals during the transformation.

  • Computing an inherited attribute after the nonterminal it belongs to. It must be computed immediately before that nonterminal.

  • Assuming right recursion gives right associativity in the result. With inherited attributes, a right-recursive grammar can still compute a left-associative result.


Interview and Exam Questions

Q1. What is the difference between an SDD and an SDT?

An SDD attaches semantic rules to productions without fixing an evaluation order. An SDT embeds actions at specific positions in production bodies, so the order of execution is fixed by those positions.

Q2. What is a postfix SDT and why is it easy to implement with an LR parser?

An SDT whose actions are all at the right end of productions. An LR parser reaches the end of a production exactly when it reduces, and at that moment all body symbols and their attribute values are on top of the stack, so the action can run and its result replaces them.

Q3. How does a bottom-up parser execute an action in the middle of a production?

The action is moved into a new marker nonterminal M → ε, and M is placed where the action was. Reducing M → ε runs the action. Bison does this automatically (the markers are named $@1, $@2, ...).

Q4. Where should the action computing an inherited attribute of X be placed?

Immediately before X in the production body. Actions computing synthesized attributes of the head go at the end of the body.

Q5. In a recursive-descent translator, what do inherited and synthesized attributes become?

Inherited attributes become function parameters; synthesized attributes become return values (or output parameters).

Q6. For the SDT S → x W { print "1" } | y { print "2" }, W → S z { print "3" }, what is printed for xxyzz?

The parse is S → x W, W → S z, S → x W, W → S z, S → y. Reductions happen innermost first: S → y prints 2, then W → S z prints 3, S → x W prints 1, W → S z prints 3, S → x W prints 1. Output: 23131.

Q7. Can every SDT be implemented during parsing?

No. Some actions must run before the parser knows which production applies. Such SDTs can still be implemented by building the parse tree first and then executing the actions in a preorder traversal.


Summary

  • An SDT embeds actions in production bodies; an action runs as soon as everything to its left has been matched.

  • Postfix SDTs (actions at the end) run on an LR parser at each reduction, with attribute values kept on the parser stack. Every S-attributed SDD gives a postfix SDT.

  • Mid-rule actions are implemented with marker nonterminals M → ε, which may cause conflicts. Bison names them $@1, $@2, ...

  • To remove left recursion from an SDT, treat actions as terminals.

  • For an L-attributed SDD, put inherited-attribute actions just before their nonterminal and synthesized ones at the end; in recursive descent, inherited attributes are parameters and synthesized attributes are return values.

  • Any SDT can be run by building the parse tree and executing actions in preorder.

With attributes and actions in hand we can now check whether a program makes sense. The next chapter, Semantic Analysis & Type Checking, uses exactly these tools to compute and check types.