Principles of Compiler Design
Chapter 5: Syntax-Directed Translation
Contents
Syntax directed definitions
Construction of syntax trees
Syntax-directed translation schemes
Bottom-up evaluation of S-attributed definitions
L-attributed definitions
Implementation of syntax-directed translators
Syntax-directed translation(SDT)
• Syntax-directed translation refers to a method of compiler
implementation where the source language translation is
completely driven by the parser.
– the parsing process and parse trees are used to direct semantic
analysis and the translation of the source program.
• SDT - is a Context Free Grammar together with semantic rules.
» SDT = Grammar + semantic Rules
– Semantic analysis involves adding information to the symbol table
and performing type checking.
Syntax-directed translation
• With each production in a grammar
– the semantic rules (actions) describe how to compute the
attribute values associated with each grammar symbol in a
production.
• There are two ways to represent the semantic rules associated
with grammar symbols.
– Syntax-Directed Definitions (SDD)
– Syntax-Directed Translation Schemes (SDT)
Syntax-directed Definition
• A syntax-directed definition (SDD) is a context-free grammar
together with attributes and rules.
• Attributes are associated with grammar symbols and rules are
associated with productions.
• An attribute has a name and an associated value: string,
number, type, memory location, an assigned register.
• If X is a symbol and a is one of its attributes, then we write X.a
to denote the value of a at a particular parse-tree node labeled X.
Translation Schemes -
• Translation Schemes indicate the order of evaluation of semantic
actions associated with a production rule.
• Translation schemes give a little bit information about implementation
details.
• Example:
Syntax Directed Definitions vs. Syntax Directed Translation
Schemes
Between the two notations
– syntax-directed definitions can be more readable, and
hence more useful for specifications.
– However, translation schemes can be more efficient, and
hence more useful for implementation
Example SDD ………..
Attributes
• In Syntax Directed Definition, there are two types of
attributes;
– Inherited Attributes and
– Synthesized Attributes
Synthesized Attributes
• A synthesized attribute is an attribute that is passed up a parse tree,
i.e, the left-side attribute is computed from the right-side attributes.
• A synthesized attribute at node N is defined only in terms of attribute
values at the children of N and at N itself.
• Example: In the production A →BCD, A is the parent node while
BCD are children nodes.
• We could then have A.S = B.S,
A.S = C.S, or
A.S = D.S,
where the parent nodes takes on values from its children B, C or D.
Synthesized Attributes
• An SDD with only
synthesized attributes
is called S-attributed.
Attribute grammar is a the generalization of context Free Grammar(CFG) ,
where each grammar symbols(terminals, non-terminals) has an associated
set of attributes.
Inherited Attributes
• An inherited attribute is an attribute in which the right-side attribute
is derived from the left-side attribute (or other right-side attributes).
• An inherited attribute at node N is defined only in terms of attribute
values at N's parent, N itself, and N's siblings.
• Example: If A → BCD, then
– C.val = A.val (parent node),
– C.val = B.val (sibling node,
– C.val = D.val (sibling node).
Evaluating an SDD at the Nodes of a Parse Tree
• Parse tree helps us to visualize the translation specified by SDD.
• The rules of an SDD are applied by first constructing a parse tree
and then using the rules to evaluate all of the attributes at each of
the nodes of the parse tree.
• A parse tree, showing the value(s) of its attribute(s) is called an
annotated parse tree.
• Since, for synthesized annotations parents can depend on children,
and for inherited annotations children can depend on parents.
Example - Evaluating an SDD at the Nodes of a Parse Tree
Annotated Parse Tree
Write SDD for the following grammar:
S En S.Val =26
E E + T|T
T T*F|F
E.Val =26
F (E)|digit
Input: 4*5+6
E.Val T.Val =6
=20 +
F.Val 3. SDD
T.Val =20
=6
T.Val =4 F.Val
* =5 digit.lexval =6
F.Val =4
digit.lexval =5
digit.lexval =4
2. Annotated parse tree
1. Parse tree
Example - annotated Parse Tree
Example Syntax-directed Definition
Annotated Parse Trees
Evaluating an SDD at the Nodes of a Parse Tree
• Evaluation of Semantic Rules may:
– Generate Code;
– Insert information into the Symbol Table;
– Perform Semantic Check;
– Issue error messages;
• Consider the following left-recursive grammar for
multiplication of numbers, and the parse tree below for 3*5*4.
Evaluating an SDD at the Nodes of a Parse Tree
• Consider the following left-recursive grammar for
multiplication of numbers, and the parse tree below for 3*5*4.
Evaluation Orders for SDD's
• The graph just drawn is called the dependency graph.
– It represents the flow of information within the parse tree.
– In addition to being generally useful in recording the
relations between attributes,
– It shows the evaluation order(s) that can be used.
Dependency Graphs
• Topological orders of DAG – 1, 2, 3, 4, 5, 6, 7, 8, 9.
– 1, 3, 5, 2, 4, 6, 7, 8, 9.
Implementation of Syntax directed translation
• Syntax direct translation is implemented by constructing a
parse tree and performing the actions in a left to right depth
first order.
• SDT is implementing by parsingSemantic
Production the input
Rulesand produce a parse
tree as a result. S→E$ { print (E.VAL); }
E→E+E {E.VAL := E.VAL + E.VAL }
E→E*E {E.VAL := E.VAL * E.VAL }
E → (E) {E.VAL := E.VAL }
E→I {E.VAL := I.VAL }
I → I digit {I.VAL := 10 * I.VAL + LEXVAL }
I → digit { I.VAL:= LEXVAL}
Implementation of Syntax directed translation
Parse tree for SDT:
