Syntax-Directed Translation

1
 Syntax-Directed Translation

1. We associate information with the programming language constructs by attaching

attributes to grammar symbols.

2. Values of these attributes are evaluated by the semantic rules associated with the
production rules.

3. Evaluation of these semantic rules:

– may generate intermediate codes
– may put information into the symbol table
– may perform type checking
– may issue error messages
– may perform some other activities
– in fact, they may perform almost any activities.

4. An attribute may hold almost any thing.

– a string, a number, a memory location, a complex record.

2
Syntax-Directed Definitions and Translation Schemes
1. When we associate semantic rules with productions, we use two
notations:
– Syntax-Directed Definitions
– Translation Schemes

A. Syntax-Directed Definitions:
– give high-level specifications for translations
– hide many implementation details such as order of evaluation of semantic actions.
– We associate a production rule with a set of semantic actions, and we do not say when they
will be evaluated.

B. Translation Schemes:
– indicate the order of evaluation of semantic actions associated with a production rule.
– In other words, translation schemes give a little bit information about implementation
details.
3
 Syntax-Directed Translation
• Conceptually with both the syntax directed translation and translation
scheme we
– Parse the input token stream
– Build the parse tree
– Traverse the tree to evaluate the semantic rules at the parse tree nodes.

Input string parse tree dependency graph evaluation order for

semantic rules

Conceptual view of syntax directed translation

4
 Syntax-Directed Definitions
1. A syntax-directed definition is a generalization of a context-free
grammar in which:
– Each grammar symbol is associated with a set of attributes.
– This set of attributes for a grammar symbol is partitioned into two subsets called
• synthesized and
• inherited attributes of that grammar symbol.
– Each production rule is associated with a set of semantic rules.

2. The value of an attribute at a parse tree node is defined by the semantic rule
associated with a production at that node.
3. The value of a synthesized attribute at a node is computed from the values of
attributes at the children in that node of the parse tree
4. The value of an inherited attribute at a node is computed from the values of
attributes at the siblings and parent of that node of the parse tree
5. Terminals can have synthesized attributes, but not inherited attributes.
5
Syntax-Directed Definitions

6
 Syntax-Directed Definitions
Examples:
Synthesized attribute : E→E1+E2 { [Link] =[Link] + [Link]}
Inherited attribute :A→XYZ {[Link] = 2 * [Link]}

1. Semantic rules set up dependencies between attributes which can be

represented by a dependency graph.

2. This dependency graph determines the evaluation order of these

semantic rules.

3. Evaluation of a semantic rule defines the value of an attribute. But a

semantic rule may also have some side effects such as printing a value.
7
 Annotated Parse Tree
1. A parse tree showing the values of attributes at each node is called
an annotated parse tree.
2. Values of Attributes in nodes of annotated parse-tree are either,
– initialized to constant values or by the lexical analyzer.
– determined by the semantic-rules.

3. The process of computing the attributes values at the nodes is called

annotating (or decorating) of the parse tree.

4. Of course, the order of these computations depends on the

dependency graph induced by the semantic rules.

8
 Syntax-Directed Definition
In a syntax-directed definition, each production A→α is associated
with a set of semantic rules of the form:
b=f(c1,c2,…,cn)
where f is a function and b can be one of the followings:

➔ b is a synthesized attribute of A and c1,c2,…,cn are attributes of the

grammar symbols in the production ( A→α ).
OR
➔ b is an inherited attribute one of the grammar symbols in α (on the
right side of the production), and c1,c2,…,cn are attributes of the
grammar symbols in the production ( A→α ).

9
 Attribute Grammar
• So, a semantic rule b=f(c1,c2,…,cn) indicates that the attribute b
depends on attributes c1,c2,…,cn.

• In a syntax-directed definition, a semantic rule may just evaluate

a value of an attribute or it may have some side effects such as
printing values.

• An attribute grammar is a syntax-directed definition in which the

functions in the semantic rules cannot have side effects (they can only
evaluate values of attributes).

10
 Syntax-Directed Definition -- Example

Production Semantic Rules

L→En print([Link])
E → E1 + T [Link] = [Link] + [Link]
E→T [Link] = [Link]
T → T1 * F [Link] = [Link] * [Link]
T→F [Link] = [Link]
F→(E) [Link] = [Link]
F → digit [Link] = [Link]
1. Symbols E, T, and F are associated with a synthesized attribute val.
2. The token digit has a synthesized attribute lexval (it is assumed that it is evaluated by
the lexical analyzer).
3. Terminals are assumed to have synthesized attributes only. Values for attributes of
terminals are usually supplied by the lexical analyzer.
4. The start symbol does not have any inherited attribute unless otherwise stated.
11
Annotated Parse Tree

12
 S-attributed definition
• A syntax directed translation that uses synthesized attributes exclusively
is said to be a S-attributed definition.

• A parse tree for a S-attributed definition can be annotated by evaluating

the semantic rules for the attributes at each node, bottom up from leaves
to the root.

13
 Annotated Parse Tree -- Example
Input: 5+3*4 L

[Link]=17 n

[Link]=5 + [Link]=12

[Link]=5 [Link]=3 * [Link]=4

[Link]=5 [Link]=3 [Link]=4

[Link]=5 [Link]=3

14
 Dependency Graph
Input: 5+3*4 L

[Link]=17 n

[Link]=5 + [Link]=12

[Link]=5 [Link]=3 * [Link]=4

[Link]=5 [Link]=3 [Link]=4

[Link]=5 [Link]=3

15
 Inherited attributes
• An inherited value at a node in a parse tree is defined in terms of
attributes at the parent and/or siblings of the node.

• Convenient way for expressing the dependency of a programming

language construct on the context in which it appears.

• We can use inherited attributes to keep track of whether an identifier

appears on the left or right side of an assignment to decide whether the
address or value of the assignment is needed.

• Example: The inherited attribute distributes type information to the

various identifiers in a declaration.
16
 Syntax-Directed Definition – Inherited Attributes

Production Semantic Rules

D→TL [Link] = [Link]
T → int [Link] = integer
T → real [Link] = real
L → L1 id [Link] = [Link], addtype([Link],[Link])
L → id addtype([Link],[Link])

1. Symbol T is associated with a synthesized attribute type.

2. Symbol L is associated with an inherited attribute in.

17
 Annotated parse tree
Input: real p,q,r annotated parse tree
parse tree D
D

T L [Link]=real [Link]=real

real L , id3 real [Link]=real , id3

L , id2 [Link]=real , id2

id1 id1

18
 Dependency Graph
• Directed Graph
• Shows interdependencies between attributes.
• If an attribute b at a node depends on an attribute c, then the semantic rule for b at that
node must be evaluated after the semantic rule that defines c.
• Construction:
– Put each semantic rule into the form b=f(c1,…,ck) by introducing dummy
synthesized attribute b for every semantic rule that consists of a procedure call.
– E.g.,
• L→En print([Link])
• Becomes: dummy = print([Link])

– The graph has a node for each attribute and an edge to the node for b from the
node for c if attribute b depends on attribute c.

19
 Dependency Graph Construction
for each node n in the parse tree do
for each attribute a of the grammar symbol at n do
construct a node in the dependency graph for a

for each node n in the parse tree do

for each semantic rule b = f(c1,…,cn)
associated with the production used at n do
for i= 1 to n do
construct an edge from
the node for ci to the node for b

20
 Dependency Graph Construction
• Example
• Production Semantic Rule
E→E1 + E2 [Link] = [Link] + [Link]

E . val

E1. val + E2 . Val

• [Link] is synthesized from [Link] and [Link]
• The dotted lines represent the parse tree that is not part of the
dependency graph.

21
 Dependency Graph
D→TL [Link] = [Link]
T → int [Link] = integer
T → real [Link] = real
L → L1 id [Link] = [Link],
addtype([Link],[Link])

L → id addtype([Link],[Link])

22
 Evaluation Order
• A topological sort of a directed acyclic graph is any ordering
m1,m2…mk of the nodes of the graph such that edges go from nodes
earlier in the ordering to later nodes.
. i.e if there is an edge from mi to mj them mi appears before mj in the ordering
• Any topological sort of dependency graph gives a valid order for
evaluation of semantic rules associated with the nodes of the parse tree.
• The dependent attributes c1,c2….ck in b=f(c1,c2….ck ) must be available before f
is evaluated.

• Translation specified by Syntax Directed Definition

• Input string parse tree dependency graph evaluation order for

semantic rules

23
Evaluation Order

• a4=real;
• a5=a4;
• addtype([Link],a5);
• a7=a5;
• addtype([Link],a7);
• a9=a7;
• addtype([Link],a5);

24
 Evaluating Semantic Rules
• Parse Tree methods
– At compile time evaluation order obtained from the topological sort of dependency
graph.
– Fails if dependency graph has a cycle
• Rule Based Methods
– Semantic rules analyzed by hand or specialized tools at compiler construction
time
– Order of evaluation of attributes associated with a production is pre-determined at
compiler construction time
• Oblivious Methods
– Evaluation order is chosen without considering the semantic rules.
– Restricts the class of syntax directed definitions that can be implemented.
– If translation takes place during parsing order of evaluation is forced by parsing
method.

25
 Syntax Trees

Syntax-Tree
– an intermediate representation of the compiler’s input.
– A condensed form of the parse tree.
– Syntax tree shows the syntactic structure of the program while
omitting irrelevant details.
– Operators and keywords are associated with the interior nodes.
– Chains of simple productions are collapsed.
Syntax directed translation can be based on syntax tree as well as
parse tree.

26
 Syntax Tree-Examples
Expression: if B then S1 else S2
+ if - then - else

5 * B S1 S2
Statement:
3 4 • Node’s label indicates what kind
• Leaves: identifiers or constants of a statement it is
• Internal nodes: labelled with • Children of a node correspond to
operations the components of the statement
• Children: of a node are its
operands
27
 Constructing Syntax Tree for Expressions
• Each node can be implemented as a record with several fields.
• Operator node: one field identifies the operator (called label of the node) and
remaining fields contain pointers to operands.
• The nodes may also contain fields to hold the values (pointers to values) of
attributes attached to the nodes.

• Functions used to create nodes of syntax tree for expressions with binary
operator are given below.
– mknode(op,left,right)
– mkleaf(id,entry)
– mkleaf(num,val)

Each function returns a pointer to a newly created node.

28
 Constructing Syntax Tree for Expressions-

Example: a-4+c
+
1. p1:=mkleaf(id,entrya);
2. p2:=mkleaf(num,4);
- id
3. p3:=mknode(-,p1,p2)
4. p4:=mkleaf(id,entryc);
to entry for c
5. p5:= mknode(+,p3,p4); num
id 4

• The tree is constructed bottom to entry for a

up.

29
 A syntax Directed Definition for Constructing
Syntax Tree
1. It uses underlying productions of the grammar to schedule the calls of
the functions mkleaf and mknode to construct the syntax tree
2. Employment of the synthesized attribute nptr (pointer) for E and T to
keep track of the pointers returned by the function calls.
PRODUCTION SEMANTIC RULE
E → E1 + T [Link] = mknode(“+”,[Link] ,[Link])
E → E1 - T [Link] = mknode(“-”,[Link] ,[Link])
E→T [Link] = [Link]
T → (E) [Link] = [Link]
T → id [Link] = mkleaf(id, [Link])
T → num [Link] = mkleaf(num, [Link])

30
 Annotated parse tree depicting construction of
syntax tree for the expression a-4+c
[Link]

[Link] + [Link]

[Link] - [Link] id
+
[Link] num
- id
id
Entry for c
id nu
m
Entry for a 31