Lecture# 06

Compiler Construction
A Simple Syntax-Directed Translator,
(Part-II)

by Safdar Hussain

Topics
• Syntax-Directed Translation (Postfix Notation, Synthesized Attributes, Inherited Attributes
• Translation, Infix to postfix Translation, Attributed Grammars, Depth-First Traversals, SDD
• Translation Schemes, SDT Questions/Tasks)
 Overview
• This chapter contains introductory material
• Building a simple compiler
– Syntax Definition
– Syntax-Directed Translation
– Parsing
– A Translator for Simple Expressions
– The Lexical Analyzer

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 2

Syntax Directed Translation (SDT)
Grammar + Semantic Rule = SDT

Informal Notations

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 3

Syntax Directed Translation (SDT)
Grammar + Semantic Rule = SDT

Informal Notations

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 4

 Syntax Directed Translation (SDT)

SDT uses a CFG to specify the syntactic structure of the language &
associates a set of attributes with (non)terminals.
Further, with each production, associates a set of semantic rules for
computing values for the attributes.
The attributes contain the translated form of the input after the
computations are completed.
In SDT, every non-terminal can get 0 or more attributes.
In semantic rule, attribute can be a value (string, memory location,
number, etc.)
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 5
 Syntax for Statements
stmt  id:= expr
|if expr then stmt
|if expr then stmt else stmt
|while expr do stmt
|begin opt_stmts end

Ambiguous Grammar?

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 6

 Syntax-Directed Translation
• Associate Attributes With Grammar Rules and Translate as
Parsing occurs
• The translation will follow the parse tree structure (and as a
result the structure and form of the parse tree will affect the
translation).
• First example: Inductive Translation.
• Infix to Postfix Notation Translation for Expressions
– Translation defined inductively as: Postfix(E) where E is an
Expression.
Rules
1. If E is a variable or constant then Postfix(E) = E
2. If E is E1 op E2 then Postfix(E)
= Postfix(E1 op E2) = Postfix(E1) Postfix(E2) op
3. If E is (E1) then Postfix(E) = Postfix(E1)
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 7
 Examples
Postfix( ( 9 – 5 ) + 2 )
= Postfix( ( 9 – 5 ) ) Postfix( 2 ) +
= Postfix( 9 – 5 ) Postfix( 2 ) +
= Postfix( 9 ) Postfix( 5 ) - Postfix( 2 ) +
=95–2+

Postfix(9 – ( 5 + 2 ) )
= Postfix( 9 ) Postfix( ( 5 + 2 ) ) -
= Postfix( 9 ) Postfix( 5 + 2 ) –
= Postfix( 9 ) Postfix( 5 ) Postfix( 2 ) + –
=952+–

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 8

 Synthesized and Inherited Attributes
• An attribute is said to be …
– synthesized if its value at a parse-tree node is
determined from the attribute values at the
children of the node
– inherited if its value at a parse-tree node is
determined by the parent (by enforcing the
parent’s semantic rules) & its siblings

Synthesized

Inherited
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 9
 Attributed Grammar
(SDD for infix to postfix translation)
Infix: 9-5+2 & Postfix: 95-2+
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”

Note: expr and expr1 are same. // is concatenation, t is

used for string valued
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 10
 Infix: 9-5+2 & Postfix: 95-2+ Example Annotated
Production Semantic Rule Parse Tree Continued
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”
expr.t = 95-2+
expr
expr.t = 95- term.t = 2
expr1 term
expr.t = 9 term.t = 5
expr1 term
term.t = 9
term 9 - 5 + 2
11
9 - 5 + 2
 Depth-First Traversals
procedure visit(n : node);
begin
for each child m of n, from left to right do
visit(m);
evaluate semantic rules at node n
end

Note:
Synthesized attributes are evaluated after visiting and
Inherited attributes are evaluated at first occurrence

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 12

 Depth-First Traversals (Example)
Semantic Rule
expr.t := expr1.t // term.t // “+” expr.t = 95-2+
expr.t := expr1.t // term.t // “-”
expr.t := term.t
term.t := “0” expr.t = 95- term.t = 2
term.t := “1”
… expr.t = 9 term.t = 5
term.t := “9”

term.t = 9

9 - 5 + 2

Note: all attributes are

of the synthesized type
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 13
 Translation Schemes
• A translation scheme is a CF grammar embedded
with semantic actions

rest  + term { print(“+”) } rest

Embedded
semantic action
rest

+ term { print(“+”) } rest

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 14

 Example Translation Scheme
Translation scheme is used to translate infix to postfix

expr  expr + term { print(“+”) }

expr  expr - term { print(“-”) }
expr  term
term  0 { print(“0”) }
term  1 { print(“1”) }
… …
term  9 { print(“9”) }

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 15

 Example Translation Scheme (cont’d)
expr { print(“+”) }

expr +
term { print(“2”) }
{ print(“-”)}
- term 2
expr
{ print(“5”) }
term 5
{ print(“9”) }
9
Translates 9-5+2 into postfix 95-2+

The implementation of a translation scheme ensures that semantic actions

are performed in the order they would appear during a postorder traversal of
a parse tree
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 16
Translation scheme is used to translate infix to postfix Example Translation Scheme
expr  expr + term { print(“+”) } (cont’d)
expr  expr - term { print(“-”) }
expr  term
term  0 { print(“0”) }
term  1 { print(“1”) } expr
… … { print(“+”) }
term  9 { print(“9”) }
expr + term

Translates 9-5+2 into postfix 95-2+

The implementation of a translation scheme ensures that semantic actions

are performed in the order they would appear during a postorder traversal of
a parse tree
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 17
Translation scheme is used to translate infix to postfix Example Translation Scheme
expr  expr + term { print(“+”) } (cont’d)
expr  expr - term { print(“-”) }
expr  term
term  0 { print(“0”) }
term  1 { print(“1”) } expr
… … { print(“+”) }
term  9 { print(“9”) }
expr +
term
{ print(“-”)}
-
expr term

Translates 9-5+2 into postfix 95-2+

The implementation of a translation scheme ensures that semantic actions

are performed in the order they would appear during a postorder traversal of
a parse tree
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 18
Translation scheme is used to translate infix to postfix Example Translation Scheme
expr  expr + term { print(“+”) } (cont’d)
expr  expr - term { print(“-”) }
expr  term
term  0 { print(“0”) }
term  1 { print(“1”) } expr
… … { print(“+”) }
term  9 { print(“9”) }
expr +
term
{ print(“-”)}
-
expr term

term
{ print(“9”) }
9
Translates 9-5+2 into postfix 95-2+

The implementation of a translation scheme ensures that semantic actions

are performed in the order they would appear during a postorder traversal of
a parse tree
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 19
Translation scheme is used to translate infix to postfix Example Translation Scheme
expr  expr + term { print(“+”) } (cont’d)
expr  expr - term { print(“-”) }
expr  term
term  0 { print(“0”) }
term  1 { print(“1”) } expr
… … { print(“+”) }
term  9 { print(“9”) }
expr +
term
{ print(“-”)}
- term
expr
{ print(“5”) }
term 5
{ print(“9”) }
9
Translates 9-5+2 into postfix 95-2+

The implementation of a translation scheme ensures that semantic actions

are performed in the order they would appear during a postorder traversal of
a parse tree
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 20
Translation scheme is used to translate infix to postfix Example Translation Scheme
expr  expr + term { print(“+”) } (cont’d)
expr  expr - term { print(“-”) }
expr  term
term  0 { print(“0”) }
term  1 { print(“1”) } expr
… … { print(“+”) }
term  9 { print(“9”) }
expr +
term { print(“2”) }
{ print(“-”)}
- term 2
expr
{ print(“5”) }
term 5
{ print(“9”) }
9
Translates 9-5+2 into postfix 95-2+

The implementation of a translation scheme ensures that semantic actions

are performed in the order they would appear during a postorder traversal of
a parse tree
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 21
Translation scheme is used to translate infix to postfix Example Translation Scheme
expr  expr + term { print(“+”) } (cont’d)
expr  expr - term { print(“-”) }
expr  term
term  0 { print(“0”) }
term  1 { print(“1”) } expr
… … { print(“+”) }
term  9 { print(“9”) }
expr +
term { print(“2”) }
{ print(“-”)}
- term 2
expr
{ print(“5”) }
term 5
{ print(“9”) }
9
Translates 9-5+2 into postfix 95-2+

The implementation of a translation scheme ensures that semantic actions

are performed in the order they would appear during a postorder traversal of
a parse tree
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 22
 SDT Question-1
• Construct a syntax-directed translation scheme that
translates arithmetic expressions from infix notation
into prefix notation in which an operator appears
before its operands; e.g. , -xy is the prefix notation
for x - y. Give annotated parse trees for the inputs 9-
5+2 and 9-5*2.

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 23

 SDT Solution-1
• Construct a syntax-directed translation scheme that translates
arithmetic expressions from infix notation into prefix notation
in which an operator appears before its operands; e.g. , -xy is
the prefix notation for x - y. Give annotated parse trees for the
inputs 9-5+2 and 9-5*2.
Productions Translation Schemes
expr -> expr + term expr -> {print("+")} expr + term
| expr - term | {print("-")} expr - term
| term | term
term -> term * factor term -> {print("*")} term * factor
| term / factor | {print("/")} term / factor
| factor | factor
factor -> digit | (expr) factor -> digit {print(digit)}
| (expr)

NOTE: Construct annotated parse trees for the inputs 9-5+2 and 9-5*2 by yourself

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 24

 SDT Question-2
• Construct a syntax-directed translation scheme that
translates arithmetic expressions from postfix
notation into infix notation. Give annotated parse
trees for the inputs 95-2 and 952-.

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 25

 SDT Solution-2
• Construct a syntax-directed translation scheme that
translates arithmetic expressions from postfix
notation into infix notation. Give annotated parse
trees for the inputs 95-2 and 952-.
Productions Translation Schemes
expr -> expr expr + expr -> expr {print("+")} expr +
| expr expr – | expr {print("-")} expr –
| expr expr * | {print("(")} expr {print(")*(")} expr {print(")")} *
| expr expr / | {print("(")} expr {print(")/(")} expr {print(")")} /
| digit | digit {print(digit)}

NOTE: Construct annotated parse trees for the inputs 9-5+2 and 9-5*2 by yourself

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 26

 SDT Question-3
• Construct a syntax-directed translation scheme that
translates arithmetic expression from postfix
notation into equivalent prefix notation.

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 27

 SDT Questions-3
• Construct a syntax-directed translation scheme that
translates arithmetic expression from postfix
notation into equivalent prefix notation.

Productions Translation Schemes

expr -> expr expr op expr -> {print(op)} expr expr op
| digit | digit {print(digit)}

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 28

The End

29