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 ??