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.
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
Syntax-Directed Definitions
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 RULE
expr → expr1 + term expr.t : = expr1.t + | | term.t | | '+' expr → expr1 - term expr.t : = expr1.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:
Diagram
Ex. 2.8
REVISION: SYNTAX-DIRECTED TRANSLATION
Step1: Syntax-directed definition for translating infix expression to postfix form.
PRODUCTION
SEMANTIC RULE
expr → expr1 + term expr.t : = expr1.t + | | term.t | | '+' expr → expr1 - term expr.t : = expr1.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.
