Translation schemes and semantic actions

Why it exists

An SDD (syntax-directed definitions) lists the rules but leaves the schedule open. Compilers usually want the work done during parsing, in the order the parser meets the input: print an instruction as soon as it is known, add a name to the symbol table when it is declared. A syntax-directed translation scheme (SDT) writes this schedule down: semantic actions (program fragments in braces) are placed inside the right sides of the productions, and an action runs when the parser reaches its position.

Prerequisites

You need S-attributed and L-attributed definitions and the way they are evaluated (evaluation orders).

Precise definitions

Syntax-directed translation scheme. A context-free grammar with semantic actions embedded in the right sides of productions, for example $E \to E_1 + T\ \{\text{print } +\}$. An action may be anywhere: at the start, in the middle, or at the end. Think of the action as an extra node of the parse tree (a leaf with no children); the actions are executed in the order they are met in a depth-first, left-to-right traversal of that tree, which is the order in which a parser can execute them.

Postfix translation scheme. An SDT in which every action is at the right end of its production. Postfix schemes work with bottom-up parsing: the action of a production is executed when the parser reduces by it (the action is run right after the symbols of the right side have been recognised). Every S-attributed SDD can be turned into a postfix scheme by writing each rule as an action at the end of its production: E → E1 + T { E.val = E1.val + T.val }. In an LR parser the attribute values are kept on the value stack beside the symbols.

Actions inside productions. A bottom-up parser cannot run an action in the middle of a production at the moment it passes it, because it does not yet know which production it is in. Two cures: (1) use a top-down parser, which knows the production when it expands the symbol; (2) for an LR parser, replace the action by a marker nonterminal $M \to \varepsilon\ \{\text{action}\}$ placed where the action was, so that the action becomes a postfix action of the production $M \to \varepsilon$, executed by a reduction of the empty string. (Markers may introduce parsing conflicts.)

Turning an L-attributed SDD into an SDT (the rules of placement):

1. An action that computes an inherited attribute of a symbol $X$ is placed immediately before $X$ in the right side.
2. An action that computes a synthesized attribute of the left-hand symbol is placed at the end of the production.
3. An action must never refer to an attribute of a symbol that lies to its right (it has not been parsed yet), and when it refers to an inherited attribute of the left-hand symbol that must already have been computed (by an action before this production was entered).

For the declaration example:

D -> T { L.in = T.type } L
T -> int { T.type = int }
T -> float { T.type = float }
L -> { L1.in = L.in } L1 , id { addtype(id.entry, L.in) }
L -> id { addtype(id.entry, L.in) }

(Here addtype is a side effect: it records the type of the identifier in the symbol table, which is exactly why one writes a scheme and not a definition.)

Left recursion in schemes. When left recursion is removed from the grammar of an SDT that prints or computes, the actions have to be moved with the symbols. The infix-to-postfix scheme on the left recursive grammar,

E -> E1 + T { print('+') }
E -> T
T -> T1 * F { print('*') }
T -> F
F -> ( E )
F -> num { print(num.val) }

becomes, after left recursion removal, a scheme in which the action follows the operand it belongs to:

E -> T R
R -> + T { print('+') } R | epsilon
T -> F S
S -> * F { print('*') } S | epsilon
F -> ( E ) | num { print(num.val) }

Both print the postfix form of the expression: operands in input order, each operator after its operands.

Where actions print. For $S \to a\ S\ \{\text{print}\} \mid \dots$ an action at the end runs after the nested $S$ finished, so with recursion the outputs appear in the reverse of the order of the input symbols (the innermost first); an action at the start runs before the nested $S$ is entered, so the output follows the input order. This is the key to the common GATE question "what does this SDT print?"

How it works

First the postfix scheme on the LR parser: print + after E + T, print * after T * F, print the value after num. The animation parses 3 + 4 * 5. Nothing is printed on a shift. At each reduction the action of that production runs: the 3 is printed when F → num is reduced, the * when T → T * F is reduced (after both operands have been printed), the + last. The output grows as 3, 3 4, 3 4 5, 3 4 5 *, 3 4 5 * +.

The same translation with a top-down parser and the scheme with actions inside the productions. The actions are pushed on the stack with the grammar symbols; when an action reaches the top of the stack it is executed. The tree shows the action nodes as leaves (dashed until executed).

Worked examples

Cheat box

Traps and GATE patterns

Connections

A scheme is the executable form of an SDD; S-attributed and L-attributed definitions give the two standard shapes (evaluation orders). The parsers are LR and LL(1); the left-recursion transformation is in grammar transformations. The main use is the generation of intermediate code while parsing.

PYQs

Which of the following statements is/are FALSE?

Consider the following grammar (that admits a
series of declarations, followed by expressions) and
the associated syntax directed translation (SDT)
actions, given as pseudo-code:

P → D* E*
 D → int ID {record that ID.lexeme is of type int}
 D → bool ID {record that ID. lexeme is of type bool}
 E → E1 + E2 {check that E1.type = E2.type = int;
set E.type := int}
E → !E1 {check that E1.type = bool; set E.type =
bool}

E → ID {set E.Type := int}

With respect to the above grammar, which one of
the following choices is correct?

Consider the following grammar and the semantic
actions to support the inherited type declaration
attributes. Let X1, X2, X3, X4, X5 and X6 be the
placeholders for the non-terminals D, T, L or L1 in
the following table :
Production Rule
Semantic Action
D → TL
X1.type = X2.type
T → int
T.type = int
T →float
T.type = float
L →  L1, id
X3.type = X4.type
addType(id.entry,
X5.type)
L → id
addType(id.entry,
X6.type)
     Which one of the following are the appropriate choices
for X1, X2, X3 and X4?

Consider
the
following
Syntax
Directed
Translation Scheme (SDTS), with non-terminals
{S, A} and terminals {a,b}.
                       S → aA   { print 1 }
                       S → a    { print 2 }
                       A → Sb   { print 3 }

Using the above SDTS, the output printed by a
bottom-up parser, for the input aab is:

Self-check

Revision card

References