1
A Simple One-Pass Compiler
Chapter 2
2
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)
3
Example Attribute Grammar
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
4
Example Annotated Parse Tree
expr.t = 95-2+
expr.t = 95- term.t = 2
expr.t = 9 term.t = 5
term.t = 9
9 - 5 + 2
5
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
6
Depth-First Traversals (Example)
expr.t = 95-2+
expr.t = 95- term.t = 2
expr.t = 9 term.t = 5
term.t = 9
9 - 5 + 2 Note: all attributes are
of the synthesized type
7
Translation Schemes
• A translation scheme is a CF grammar
embedded with semantic actions
rest + term { print(“+”) } rest
Embedded
semantic action
rest
+ term { print(“+”) } rest
8
Example Translation Scheme
Translation schema 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”) }
9
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+
10
Parsing
• Parsing = process of determining if a string of
tokens can be generated by a grammar
• For any CF grammar there is a parser that takes at
most O(n3) time to parse a string of n tokens
• Linear algorithms suffice for parsing
programming language
• Top-down parsing “constructs” parse tree from
root to leaves
• Bottom-up parsing “constructs” parse tree from
leaves to root
11
Predictive Parsing
• Recursive descent parsing is a top-down parsing
method
– Every nonterminal has one (recursive) procedure
responsible for parsing the nonterminal‟s syntactic
category of input tokens
– When a nonterminal has multiple productions, each
production is implemented in a branch of a selection
statement based on input look-ahead information
• Predictive parsing is a special form of recursive
descent parsing where we use one lookahead
token to unambiguously determine the parse
operations
12
Example Predictive Parser
(Grammar)
type simple
| ^ id
| array [ simple ] of type
simple integer
| char
| num dotdot num
13
Example Predictive Parser (Program Code)
procedure match(t : token);
procedure simple();
begin
begin
if lookahead = t then
if lookahead = „integer‟ then
lookahead := nexttoken()
match(„integer‟)
else error()
else if lookahead = „char‟ then
end;
match(„char‟)
else if lookahead = „num‟ then
procedure type();
match(„num‟);
begin
match(„dotdot‟);
if lookahead in { „integer‟, „char‟, „num‟ } then
match(„num‟)
simple()
else error()
else if lookahead = „^‟ then
end;
match(„^‟); match(id)
else if lookahead = „array‟ then
match(„array‟); match(„[„); simple();
match(„]‟); match(„of‟); type()
else error()
end;
Tracing
Input: array [ num dotdot num ] of integer
To initialize the parser:
set global variable : lookahead = array
call procedure: type
Procedure call to type with lookahead = array results in the actions:
match( array ); match(„[„); simple; match(„]‟); match(of); type
Procedure call to simple with lookahead = num results in the actions:
match (num); match (dotdot); match (num)
Procedure call to type with lookahead = integer results in the actions:
simple
Procedure call to simple with lookahead = integer results in the actions:
match ( integer )
15
Example Predictive Parser
(Execution Step 1)
Check lookahead
type()
and call match
match(„array‟)
Input: array [ num dotdot num ] of integer
lookahead
16
Example Predictive Parser
(Execution Step 2)
type()
match(„array‟) match(„[‟)
Input: array [ num dotdot num ] of integer
lookahead
17
Example Predictive Parser
(Execution Step 3)
type()
match(„array‟) match(„[‟) simple()
match(„num‟)
Input: array [ num dotdot num ] of integer
lookahead
18
Example Predictive Parser
(Execution Step 4)
type()
match(„array‟) match(„[‟) simple()
match(„num‟) match(„dotdot‟)
Input: array [ num dotdot num ] of integer
lookahead
19
Example Predictive Parser
(Execution Step 5)
type()
match(„array‟) match(„[‟) simple()
match(„num‟) match(„dotdot‟) match(„num‟)
Input: array [ num dotdot num ] of integer
lookahead
20
Example Predictive Parser
(Execution Step 6)
type()
match(„array‟) match(„[‟) simple() match(„]‟)
match(„num‟) match(„dotdot‟) match(„num‟)
Input: array [ num dotdot num ] of integer
lookahead
21
Example Predictive Parser
(Execution Step 7)
type()
match(„array‟) match(„[‟) simple() match(„]‟) match(„of‟)
match(„num‟) match(„dotdot‟) match(„num‟)
Input: array [ num dotdot num ] of integer
lookahead
22
Example Predictive Parser
(Execution Step 8)
type()
match(„array‟) match(„[‟) simple() match(„]‟) match(„of‟) type()
match(„num‟) match(„dotdot‟) match(„num‟) simple()
match(„integer‟)
Input: array [ num dotdot num ] of integer
lookahead
Limitations
• Can we apply the previous technique to every grammar?
• NO:
type simple
| array [ simple ] of type
simple integer
| array digit
digit 0|1|2|3|4|5|6|7|8|9
consider the string “array 6”
the predictive parser starts with type and lookahead= array
apply production type simple OR type array digit ??