Modern compilers use syntax-directed translation to interleaves the actions of the compiler phases.

The syntax analyzer directs the whole process during the parsing of the source code.

- Calls the lexical analyzer whenever syntax analyzer wants another token.
- Perform the actions of semantic analyzer.
- Perform the actions of the intermediate code generator.

The actions of the semantic analyzer and the intermediate code generator require the passage of information up and/or down the parse tree.

We think of this information as attributes attached to the nodes of the parse tree and the parser moving this information between parent nodes and children nodes as it performs the productions of the grammar.

**Postfix Notation**

Postfix notation also called reverse polish notation or RPN places each binary
arithmetic operator after its two operands instead of between them.

Infix Expression : (9 - 5) + 2 = (95 -) + 2 = (95-) 2 + = 95 - 2 + : Postfix Notation Infix Expression : 9 - (5 + 2) = 9 - (52+) = 9 (52+) - = 9 5 2 + - : Postfix Notation

Why postfix notation?

There are two reasons

- There is only one interpretation
- We do not need parenthesis to disambignate the grammar.

**Syntax-Directed Definitions**

- A syntax-directed definition uses a CFG to specify the syntatic structure of the input.
- A syntax-directed definition associates a set of attributes with each grammar symbol.
- A syntax-directed definition associates a set of semantic rules with each production rule.

For example, let the grammar contains the production:

X → Y Z

And also let that nodes X, Y and Z have associated attributes X.a, Y.a and Z.a respectively.

The annotated parse tree looks like:

diagram

If the semantic rule

{X.a := Y.a + Z.a}

is associated with the production

X →
Y Z

then parser should add the attribute 'a' of node Y and attribute 'a' of node Z
together and set the attribute 'a' of node X to their sum.

**Synthesized Attributes**

An attribute is synthesized if its value at a parent node can be determined from
attributes of its children.

diagram

Since in this example, the value of a node X can be determined from 'a'
attribute of Y and Z nodes attribute 'a' in a synthesized attribute.

Synthesized attributes can be evaluated by a single bottom-up traversal of the
parse tree.

**Example 2.6:** Following figure shows the syntax-directed definition of
an infix-to-postfix translator.

Figure 2.5 Pg. 34

PRODUCTION

SEMANTIC RULEexpr → expr _{1}+ termexpr.t : = expr _{1}.t + | | term.t | | '+'expr → expr _{1}- termexpr.t : = expr _{1}.t + | | term.t | | '-'expr → term expr.t : = term.t term → 0 term.t : = '0' term → 1 term.t : = '1' : : : : term → 9 term.t : = '9'

**Parse tree corresponds to Productions**

Diagram

Annotated parse tree corresponds to semantic rules.

Diagram

The above annotated parse tree shows how the input infix expression 9 - 5 + 2 is translated to the prefix expression 95 - 2 + at the root.

**Depth-First Traversals**

A depth-first traversal of a parse tree is one way of evaluating attributes.

Note that a syntax-directed definition does not impose any particular order as
long as order computes attribute of parent after all its children's attributes.

PROCEDURE visit (n: node)

BEGIN

FOR each child m of n, from left to right

Do visist (m);

Evaluate semantic rules at node n

END

Diagram

**Translation Schemes**

A translation scheme is another way of specifying a syntax-directed translation.
This scheme is a CFG in which program fragments called semantic actions are
embedded within the right sides of productions.

For example,

rest →
+ term {primt ( ' + ' )} rest,

indicates that a '+' sign should be printed between:

- depth-first traversal of the term node, and
- depth first traversal of the rest, node.

Diagram

Ex. 2.8

**REVISION: SYNTAX-DIRECTED TRANSLATION**

Step1: Syntax-directed definition for translating infix expression to postfix form.

PRODUCTION

SEMANTIC RULEexpr → expr _{1}+ termexpr.t : = expr _{1}.t + | | term.t | | '+'expr → expr _{1}- termexpr.t : = expr _{1}.t + | | term.t | | '-'expr → term expr.t : = term.t term → 0 term.t : = '0' term → 1 term.t : = '1' : : : : term → 9 term.t : = '9'

Step 2: A translation scheme derived from syntax-direction definition is :

Figure 2.15 on pg. 39

expr → expr + term {print( ' + ' )} expr → expr - term {print( ' - ')} expr → term term → 0 {print( ' 0 ' )} term → 1 {print( ' 1 ' )} : : : : term → 9 {print( ' 9 ' )}

Step 3: A parse tree with actions translating 9 - 5 + 2 into 95 - 2 +

Figure 2.14 on pg. 40

Note that it is not necessary to actually construct the parse tree.