COMPILER CONSTRUCTION
Principles and Practice
Kenneth C,Louden
6,Semantic Analysis
PART ONE
Semantic Analysis Phase
– Purpose,compute additional information needed for
compilation that is beyond the capabilities of Context-
Free Grammars and Standard Parsing Algorithms
– Static semantic analysis,Take place prior to execution
(Such as building a symbol table,performing type
inference and type checking)
Classification
– Analysis of a program required by the rules of the
programming language to establish its correctness and
to guarantee proper execution
– Analysis performed by a compiler to enhance the
efficiency of execution of the translated program
Description of the static semantic analysis
– Attribute grammar
identify attributes of language entities that must be computed
and to write attribute equations or semantic rules that
express how the computation of such attributes is related to the
grammar rules of the language
– Which is most useful for languages that obey the
principle of Syntax-Directed Semantics
– Abstract syntax as represented by an abstract syntax
tree
Implementation of the static semantic analysis,
– Not as clearly expressible as parsing algorithms
because of the addition problem caused by the timing of
the analysis during the compilation process
– Multi-pass (more common) or single pass lead to totally
different process
Emphasis:
– Attributes and attribute grammars
– Algorithms for attribute computation
– The symbol table
– Data types and type checking
– A semantic analyzer for the TINY language
Contents
Part One
6.1 Attributes and Attribute Grammars
6.2 Algorithms for Attribute Computation
Part Two
6.3 The Symbol Table
6.4 Data Types and Type Checking
6.5 A Semantic Analyzer for the TINY Language
6.1 Attributes and Attribute
Grammars
Attributes
– Any property of a programming language construct such as
The data type of a variable
The value of an expression
The location of a variable in memory
The object code of a procedure
The number of significant digits in a number
Binding of the attribute
– The process of computing an attribute and associating its computed
value with the language construct in question
Binding time
– The time during the compilation/execution process when the
binding of an attribute occurs
– Based on the difference of the binding time,attributes is divided
into Static attributes (be bound prior to execution) and Dynamic
attributes (be bound during execution)
Example,The binding time and significance
during compilation of the attributes,
– Attribute computations are extremely varied
– Type checker
In a language like C or Pascal,is an important part of semantic
analysis;
While in a language like LISP,data types are dynamic,LISP
compiler must generate code to compute types and perform
type checking during program execution,
– The values of expressions
Usually dynamic and the be computed during execution;
But sometime can also be evaluated during compilation
(constant folding),
Example,the binding time and significance
during compilation of the attributes,
– Attribute computations are extremely varied
– The allocation of a variable,
Either static (such as in FORTRAN77 ) or dynamic (such as in
LISP),
Sometimes it is a mixture of static and dynamic (such as in C
and Pascal) depending on the language and properties of the
variable itself.
– Object code of a procedure,
A static attribute,which is computed by the code generator
– Number of significant digits in a number,
Often not explicitly treated during compilation,
6.1.1 Attribute Grammars
X.a means the value of ‘a’ associated to ‘X’
– X is a grammar symbol and a is an attribute associated
to X
Syntax-directed semantics,
– Attributes are associated directly with the grammar
symbols of the language,
– Given a collection of attributes a1,…,ak,it implies
that for each grammar rule X0?X1X2… Xn (X0 is a
nonterminal),
– The values of the attributes Xi.aj of each grammar
symbol Xi are related to the values of the attributes of
the other symbols in the rule.
An attribute grammar for attributes a1,a2,…,
ak is the collection of all attribute equations or
semantic rules of the following form,
– for all the grammar rules of the language.
Xi.aj = fij(X0.a1,…,X0.ak,…,X1.al,…,Xn-1.a1,… Xn.ak)
Where fij is a mathematical function of its arguments
Typically,attribute grammars are written in
tabular form as follows:
Grammar Rule Semantic Rules
Rule 1 Associated attribute equations
...
Rule n Associated attribute equation
Example 6.1 consider the following simple grammar for
unsigned numbers:
Number?number digit | digit
Digit?0|1|2|3|4|5|6|7|8|9
The most significant attribute,numeric value (write as val),
and the responding attribute grammar is as follows:
Gr a mm a r Rule S e mantic Rul e s
Numbe r1? number 2 di g i t number 1.va l = numbe r2.v a l*10 + dig it,va l
Numbe r? dig it number,va l= di g it,va l
dig it? 0 dig it,va l = 0
dig it? 1 dig it,va l = 1
dig it? 2 dig it,va l = 2
dig it? 3 dig it,va l = 3
dig it? 4 dig it,va l = 4
dig it? 5 dig it,va l = 5
dig it? 6 dig it,va l = 6
dig it? 7 dig it,va l = 7
dig it? 8 dig it,va l = 8
dig it? 9 dig it,va l = 9
table 6.1
The parse tree showing attribute computations for the
number 345 is given as follows
number
( v a l = 3 4 * 1 0 + 5 = 3 4 5 )
n u m b e r d i g i t
(va l = 3 *10+ 4 = 3 4) (va l = 5 )
number dig it 5
(va l=3) (va l=4)
dig it 4
3
F ig 6.1
Example 6.2 consider the following grammar for simple integer
arithmetic expressions:
Exp? exp + term | exp-term | term
Term?term*factor | factor
Factor?(exp)| number
The principal attribute of an exp (or term or factor) is its
numeric value (write as val) and the attribute equations for the
val attribute are given as follows
Gr a mm a r Rule S e mantic Rul e s
e x p1? e x p2 + ter m e xp1.va l=e x p2.va l+te rm.va l
e x p1? e x p2 - ter m e x p 1.va l=e x p2.va l - e rm.va l
e x p1? ter m e x p 1.va l= te rm.va l
ter m1? ter m2*fa c tor ter m1.val= ter m2.v a l*f a c tor,v a l
ter m? fa c tor t e r m,v a l = f a c t o r,v a l
fa c tor? ( e x p) fa c t or,va l= e x p.va l
fa c tor? numbe r fa c tor,va l=numbe r,v a l
table 6.2
Given the expression (34-3)*42,the computations implied by
this attribute grammar by attaching equations to nodes in a
parse tree is as follows
F ig 6.2
Ex p
(v a l = 1 3 0 2 )
term
(v a l = 3 1 * 4 2 = 1 3 0 2 )
term
(v a l = 3 1 )
f a c to r
(v a l = 4 2 )
Ex p
( (v a l = 3 4 - 3 = 3 1 ) )
Ex p
(v a l = 3 4 )
term
(v a l = 3 )
f a c to r
(v a l = 3 1 )
n u m b e r
(v a l = 4 2 )
term
(v a l = 3 4 )
f a c to r
(v a l = 3 )
f a c t or
(v a l = 3 4 )
n u m b e r
(v a l = 3 )
n u m b e r
(v a l = 3 4 )
-
*
Example 6.3 consider the following simple grammar of variable
declarations in a C-like syntax:
Decl? type var-list
Type?int | float
Var-list?id,var-list |id
Define a data type attribute for the variables given by the
identifiers in a declaration and write equations expressing how
the data type attribute is related to the type of the declaration as
follows:
(We use the name dtype to distinguish the attribute from the
nonterminal type)
Gr a mm a r Rule S e mantic Rul e s
de c l? t y p e va r - li st va r - li st.dt y pe = t y pe,dt y pe
t y pe? int t y pe,dt y pe = int e g e r
t y pe? f lo a t t y pe,dt y pe = r e a l
va r - li st1? id,var - li st2 id.dt y p e = va r - li st1.dt y pe
v a r - li st2.dt y pe = v a r - li st1.dt y p e
va r - li st? id id.t y pe = va r - li st.dt y pe
table 6.3
Note that there is no equation involving the dtype of the
nonterminal decl,
It is not necessary for the value of an attribute to be specified
for all grammar symbols
Parse tree for the string float x,y showing the dtype attribute
as specified by the attribute grammar above is as follows:
F ig 6.3
At tr ib u te gr a m m ar s m ay in volve se ve r al i n te r d e p e n d e n t at tr ib u te s,
decl
T y pe
( dt y pe = r eal )
V ar - l i st
( dt y pe = r eal )
V ar - l i st
( dt y pe = r eal )
Id
( x)
( dt y pe = r eal )
Id
( y )
( dt y pe = r eal )
f l oat,
Example 6.4 consider the following grammar,where
numbers may be octal or decimal,suppose this is
indicated by a one-character suffix o(for octal) or d(for
decimal):
Based-num?num basechar
Basechar? o|d
Num? num digit | digit
Digit? 0|1|2|3|4|5|6|7|8|9
In this case num and digit require a new attribute
base,which is used to compute the val attribute,The
attribute grammar for base and val is given as follows.
Gr a mm a r Rule S e mantic Rul e s
B a se d - num? num base c ha r B a se d - num.val = num.v a l
B a se d - num.bas e = ba s e c ha r,ba se
B a se c ha r? o B a se c ha r,b a se = 8
B a se c ha r? d B a s e c h a r,b a s e = 1 0
Num1? num2 di g it num1.val =
I f di gi t,v al = er r or or num 2.val = er r or
Th en er r o r
Els e n um 2.v al * nu m 1.bas e+ di gi t,v al
N u m 2,b a s e = n u m 1,b a s e
D i g i t,b a s e = n u m 1,b a s e
Num? dig it num.val = dig it,va l
D i g i t,b a s e = num.b a se
Dig it? 0 dig it,va l = 0
Dig it? 1 dig it,va l = 1
… …
Dig it? 7 dig it,va l = 7
Dig it? 8 dig it,va l = if dig it,ba s e = 8 then e r ror e lse 8
Dig it? 9 dig it,va l = if dig it,ba s e = 8 then e r ror e lse 9
T a b 6.4
F ig 6.4
num
(v a l = 3 )
(b a se = 8 )
d ig it
(v a l = 3 )
(b a se = 8 )
3
Ba se d - num
(v a l = 2 2 9 )
num
(v a l = 2 8 * 8 + 5 = 2 2 9 )
(b a se = 8 )
b a se c h a r
(b a se = 8 )
num
(v a l = 3 * 8 + 4 = 2 8 )
(b a se = 8 )
d ig it
(v a l = 4 )
(b a se = 8 )
o
4
d ig it
(v a l = 5 )
(b a se = 8 )
5
6.1.2 Simplifications and
Extensions to Attribute Grammars
Meta-language for the attribute grammar,
– The collection of expressions allowable in an attribute
equation,
Arithmetic,logical and a few other kinds of expressions,
Together with an if-then-else expression and occasionally a
case or switch expression
Functions can be added to the meta-language
whose definitions may be given elsewhere
– For instance,digit? D (D is understood to be one of
the digits) digit.val = numval(D)
here,numval is a function which is defined as,
Int numval(char D)
{return (int)D – (int)’0’;}
Simplifications,
Using ambiguous grammar,
(all ambiguity will have been dealt with at the parser stage)
exp?exp + exp| exp – exp | exp * exp|(exp)|number
Gr a mm a r Rule S e mantic Rul e s
e x p1? e x p2+ e x p3 e xp1.va l=e x p2.va l+e x p3.va l
e x p1? e x p2 - e x p3 e x p 1.va l=e x p2.va l - e x p3.va l
e x p1? e x p2*e x p3 e xp1.va l=e x p2.va l*ex p3.va l
e x p1? (e x p2) e x p 1.va l=e x p2.va l
e x p? number e x p,va l=numbe r,va l
table 6.5
Simplifications,
Using abstract syntax tree instead of parse tree,
(34-3)*42
F ig 6.5
3
(v a l = 3 )
*
(v a l = 3 1 * 4 2 = 1 3 0 2 )
-
(v a l = 3 4 - 3 = 3 1 )
42
(v a l = 4 2 )
34
(v a l = 3 4 )
Example 6.5 define an abstract syntax tree for simple integer
arithmetic expressions by the attribute grammar as follows:
Gr a mm a r Rule S e man ti c R ules
e x p1? e x p2+ ter m e x p1.tre e = mkOpNode ( +,e x p2.tre e,ter m.t re e )
e x p1? e x p2 - ter m e x p1.tre e = mkOpNode ( -,e x p2.tre e,ter m,tre e )
e x p1? ter m e x p 1.tre e = te rm.tre e
ter m1? ter m2*fa c tor ter m1.t re e = mkOpNo de (*,te rm2.tre e,fa c tor,tre e )
ter m? fa c tor ter m.t re e = f a c to r,tre e
fa c tor? ( e x p) fa c t or,tre e = e x p.tre e
fa c tor? numbe r fa c to r,tre e = mkNumNode (numbe r,le x va l)
table 6.6
Syntax tree itself is specified by an attribute
grammar.
– mkOpNode,construct a new tree node whose operator
label is the first parameter,whose children are the
second and third parameter.
– mkNumNode,constructs a leaf node representing a
number with that value.
One question that is central to the specification of
attributes using attribute grammars is,
– How can we be sure that a particular attribute grammar
is consistent and complete?
– That is,that it uniquely defines the give attributes?
– (the simple answer is that so far we cannot.)
6.2 Algorithms for Attribute
Computation
Purpose,study the ways an attribute grammar can
be used as basis for a compiler to compute and use
the attributes defined by the equations of the
attribute grammar.
– Attribute equations is turned into computation rules
– Xi.aj = fij(X0.a1,…,X0.ak,…,X1.al,…,Xn-
1.a1,… Xn.ak)
– is viewed as an assignment of the value of the
functional expression on the right- hand side to the
attribute Xi.aj.
The attribute equations indicate the order
constraints on the computation of the attributes,
– Attribute at the right-hand side must be computed
before that at the left-hand side,
– The constraints is represented by directed graphs —
dependency graphs.
6.2.1 Dependency graphs and
evaluation order
Dependency graph of the string:
The union of the dependency graphs of the
grammar rule choices representing each
node (nonleaf) of the parse tree of the string
– Xi.aj = fij(…,Xm.ak,… )
– An edge from each node Xm.ak to Xi.aj the
node expressing the dependency of Xi.aj on
Xm.ak.
Example 6.6 Consider the grammar of Example 6.1,with the
attribute grammar as given in tab 6.1,for each symbol there is
only one node in each dependency graph,corresponding to its
val attribute
Grammar rule attribute equation
Number1?number2 digit number1.val = number2.val * 10 +digit.val
The de pe nd e nc y g r a ph fo r this g ra mm a r r ule c hoic e is
Nu m 1,v a l
Nu m 2,v a l
Dig it,v a l
The subscr ipt s for r e pe a ted s y mbol s will be omi tt e d
Numbe r? dig it number,va l = dig it,va l
The string 345 h a s the f o ll owing de pe nd e nc y g r a p h,
Nu m 1,v a l
Dig it,v a l
Nu m,v a l
Nu m b e r,v a l
Dig it,v a l
n u m b e r,v a l
Dig it,v a l
Dig it,v a l
E xam p le 6.7 c onsi de r the gra mm a r o f e x a mpl e 6.3
va r - li st1? id,var li st2
id.dt y pe = v a r - li st1.dt y p e
va r - li st2.dt y pe = va r - li st1.dt y pe
a nd the de pe nd e nc y g r a p h
sim il a rl y va r - li st? id re spond t o
V a r - li st.d ty p e
Id,d ty p e
V a r - li st.d ty p e
V a r - lis t,d ty p e
Id,ty p e
De c l? t y p e va rlist
T y p e,d t y p e —— > v a r - li st.dt y pe
I t c a n a lso be d ra wn a s,
S o,the f irst g r a ph in t his ex a mpl e c a n be dr a wn a s,
d e c l
T y p e,d ty p e
Dt y p e v a r - li st
d ty p e
d ty p e
d ty p e
V a r - li st
Id
V a r - li st
,
F inall y,the de p e nde n c y g r a ph fo r the st ring floa t x,y is
d ty p e
d ty p e
d ty p e
V a r - li st
Id (x )
V ar - li st
,
Id (y ) d ty p e
d e c l
T y p e d ty p e
f lo a t
Example 6.8 consider the grammar of based
number of example 6.4
based-num?num basechar
Num?num digit
Num?digit
Digit?9
…
F or strin g 345o,the c or re spondi ng de pe nd e nc y
g r a ph is a s follows,
num
d ig it
3
Ba se d - num
num b a se c h a r
num
d ig it
o
4
d ig it
5
v a l
v a l
v a l
v a l b a se
v a l
v a l
v a l
b a se
b a se
b a se
b a se
b a se
b a se
Any algorithm must compute the attribute at each
node in the dependency graph before it attempts to
compute any successor attributes
– A traversal order of the dependency graph that obeys
this restriction is called a topological sort
– Requiring that the graph must be acyclic,such graphs
are called directed acyclic graphs Or DAGs
E xam p le 6.9
The de pe nd e nc y of F i g 6,6 is a D AG,whic h g ives a s follows,
F ig 6.7
Anothe r topolog ic a l sort is g iven b y the or d e r
12 6 9 1 2 1 1 3 8 4 5 7 10 13 14
B as e( 4)
B as e( 5)
V al ( 14)
V a l ( 1 4 )
V al ( 13)
V al ( 10)
V al ( 7)
V al ( 6)
V al ( 12)
V al ( 9)
B as e( 2)
B as e( 3)
B as e( 8)
B as e( 1)
B as e( 1 1)
One question,how attribute values are found at
the roots of the graph (root of the graph mean that
has no predecessors)
Attribute values at these nodes is often in the form
of tokens,and should be computed before any
other attribute values
Parse tree method,
– Construction of the dependency graph is based on the
specific parse tree at compile time,add complexity,and
need circularity detective
Rule based method,
– Fix an order for attribute evaluation at compiler
construction time
6.2.2 Synthesized and Inherited
Attributes
Classification of the attributes,
1,Synthesized attributes
2,Inherited attributes
Definition,
– An attribute is synthesized if all its
dependencies point form child to parent in the
parse tree,
– Equivalently,an attribute a is synthesized if,
given a grammar rule A?X1X2… Xn,the only
associated attribute equation with an ‘a’ on the
left-hand side is of the form:
A.a = f(X1.a1,… X1.ak,… Xn.a1,… Xn.ak)
An S-attributed grammar
– An attribute grammar in which all the attributes are
synthesized
The attribute values of an S-attributed grammar
can be computed by
– a single bottom-up,or post-order,traversal of the
parse or syntax tree,Just as follows:
Procedure PostEval (T,treenode);
Begin
For each child C of T do
PostEval(C);
Compute all synthesized attributes of T;
End
Example 6.11 Consider the attribute grammar for simple
arithmetic expressions (example 6.2),with the synthesized
attribute val
Given the following structure for a syntax tree:
Typedef enum {Plus,Minus,Times} opkind;
Typedef enum {opkind,constkind} expkind;
Typedef struct streenode
{expkind kind;
opkind op;
struct streenode *lchild,*rchild;
int val;
} Streenode;
Typedef Streenode *Syntaxtree;
The PostEval pseudocode would translate into the C code as follows:
Void postEval(Syntaxtree t)
{int temp;
if (t->kind == opkind)
{postEval(t->lchild);
postEval(t_rchild);
switch (t->op)
{ case Plus:
t->val = t->lchild->val + t->rchild->val;
break;
case Minus:
t->val = t->lchild->val - t->rchild->val;
break;
case Times:
t->val = t->lchild->val * t->rchild->val;
break;
}
}
}
De f in ition,
An a tt ribute that is not s y nthesiz e d is ca ll e d a n in h e r ite d a tt ribute,
S u c h as d type in t h e e xam p le b e low,
De c l? t y pe va r - li st
T y p e? int | flo a t
V a r - li st? id,var - li st | id
T wo ba sic kinds of de p e n de nc y of inhe rited a tt ribu tes,
(a ) I nh e ritanc e f or m p a r e nt t o si bli ng s (b) I nh e ritanc e f rom sibl ing t o si bli ng
a A
a B
a C
A
a B
a C
I f some stru c ture s in a s y ntax tre e a re im ple mente d via sibl in g poin ter s,then
sibl ing inher it a nc e c a n p r oc e e d dir e c tl y a lon g a sib li ng c ha in,a s follows,
(c ) Si bli ng inher it a n c e vi a sibl ing point e rs
inher it e d a tt ribute s c a n be c omput e d b y a pr e or de r tra v e rsa l,or c ombi ne d
pr e or de r/inorde r tr a ve rs a l of the pa rse o r s y ntax tre e,r e pr e se nted b y the f oll owing
pseud oc ode,
P roc e dure P r e Eva l(T,t r e e node );
B e g in
F or e a c h c hil d C o f T do
C omput e a ll inher it e d a tt ribute s of T ;
P re Eva l(C);
End;
a B
A
a C
The order in which the inherited attributes
of the children are computed is important
– It must adhere to any requirements of the
dependencies
Example 6.12 consider the grammar with
the inherited attribute dtype and its
dependency graphs as illustrated
Decl?type var-list
Type?int|float
Var-list?id,var-list|id
P roc e dure Ev a lT y pe ( T,t re e node );
B e g in
C a se node kind of T o f
De c l,
Eva lT y p e (t y pe c hil d of T );
Assig n dt y pe of t y p e c hil d of T to var - li st chil d of T ;
Eva lT y p e (va r - li st chil d of T) ;
T y p e,
I f c hil d of T = int then T,dt y pe,= inte ge r
Else T,dt y pe,= re a l;
V a r - li st,
Assig n T,dt y pe to first ch il d of T ;
I f thi rd c hil d of T is no t n il then
Assig n T,dt y pe to t hird c hil d;
Eva lT y p e (third c hil d of T );
End c a se ;
End Eva lT y p e ;
I n the p roc e dure a bove,p re or de r a nd inord e r ope ra ti ons a re mi x e d,
I no rde r,de c l node
P re or de r,va r - li st nod e
F ig 6.10
d ty p e
d ty p e
V a r - li st(2 )
Id (x )(3 )
V a r - li st(4 )
,
Id (y )(5 ) d ty p e
d e c l
1 )T y p e d ty p e
f lo a t
I f us e the a c tual C c ode,a ssum e that a s y ntax tre e ha s be e n c onst ruc ted,in
whic h var - li st is r e p r e s e n te d b y a si b l in g li st o f i d n od e s as f oll o w s,
The s y nt a x tre e struc ture is,
T y p e de f e num {dec l,t y p e,id} nodekind;
T y p e de f e num {i ntege r,r e a l} t y p e kind;
T y p e de f stru c t t re e nod e
{node kind ki nd;
struc t t re e node *l c hil d,*rc hil d,* si bli ng ;
t y pe kind dt y pe ;
c ha r *na m e ;
} *S y ntax tre e ;
d e c l
T y p e (d t y p e
= re a l)
Id (x ) Id (y )
The EvalType procedure now has the corresponding C code:
void evaltype (syntaxtree t)
{ switch (t->kind)
{case decl:
t->rchild->dtype = t->lchild->dtype
evaltype(t->rchild);
break;
case id:
if(t->sibling != NULL)
{ t->sibling->dtype = t->dtype;
evaltype(t->sibling);
}
break;
}
}
The code above can be simplified to the following
non-recursive procedure:
void evaltype(syntaxtree t)
{ if(t->kind = = decl)
{ syntaxtree p = t->rchild;
p->dtype = t->lchlild->dtype;
while (p->sibling !=NULL)
{ p->sibling->dtype = p->dtype;
p = p->sibling;
}
}
}
Example 6.13 Consider the following grammar
which has the inherited attribute base.
Based-num?num basechar
Basechar?o|d
Num?num digit | digit
Digit?0|1|2|3|4|5|6|7|8|9
Features,
– Two attributes include synthesized attribute val and
inherited attribute base,on which val depends;
– The base attribute is inherited from the right child to the
left child of a based-num,
B a se is c omput e d in pre o rde r a nd v a l i n p ostorde r during a sin g le p a ss as f o ll ows,
num
d ig it
3
Ba se d - num
num ba se c h a r
num
d ig it
o
4
d ig it
5
v a l
v a l
v a l
v a l b a se
v a l
v a l
v a l
b a se
b a se
b a se
b a se
b a se
b a se
P roc e dure Ev a lW it hB a se (T,t re e node );
B e g in
C a se node kind of T o f
B a se d - num,
Eva lW it hB a se (r i g ht child of T) ;
Assig n ba s e of r i g ht chil d of T to base o f le ft c hil d;
Eva lW it hB a se ( lef t c hil d of T) ;
Assig n va l of l e ft c hil d o f T to T,va l;
Num,
As sig n T,ba se to b a se of lef t child of T ;
Eva lW it h B a se (le ft c hil d of T) ;
I f r i g ht child of T is no t n il then
Assig n T,ba se to b a se of rig ht child of T ;
Eva lW it hB a se (r i g ht child of T) ;
I f va ls of lef t a nd ri g ht ch il dr e n != e rr or then
T,va l,= T,ba se *(va l of l e ft c hil d) + v a l of r i g ht c hil d
Else T,va l,= e rr o r;
Else T,va l,= va l of le ft c hil d;
B a se c ha r,
I f c hil d of T = o then T,b a se,=8;
Else T,ba se,=10;
Dig it,
I f T,ba se = 8 a nd c hil d of T = 8 or 9 then T,va l,= e rr or
Else T,va l,= numval( c hil d of T) ;
End c a se ;
End Eva lW it hB a se ;
To compute all the attributes in a single pass over the
parse or syntax tree,the inherited attributes shouldn’t
depend on any synthesized attributes
The synthesized attributes could depend on the inherited
attributes (as well as other synthesized attributes).
Procedure CombinedEval(T:treenode);
Begin
For each child C of T do
Compute all inherited attributes of C;
CombinedEval(C);
Compute all synthesized attributes of T.
End;
When inherited attributes depend on synthesized attributes,
it requires more than one pass over the parse or syntax tree
Example 6.14 consider the following simple
version of an expression grammar:
Exp?exp/exp|num|num.num
Operations may be interpreted differently
depending on whether they are floating-point or
strictly integer operations,
For instance,5/2/2.0 = 1.25
5/2/2 = 1
The attributes to express corresponding semantic:
– isFloat,boolean,indicates if any part of an expression
has a floating-point value (synthesized)
– etype,gives the type of each subexpression and
depends on isFloat (inherited),here is int or float
– val,gives the numeric value of each subexpression,
depends on etype.
Gr a mm a r Rule S e mantic Rul e s
S? e x p e x p.e t y pe = if e x p.isF loat then f loat e lse int
S,va l = e x p.va l
Ex p1? e x p2/ex p3 e x p1.isF loat = e x p2.isF loat or e x p3.isF loat
E x p2.e t y p e = e x p1.e t y p e
E x p 3,e t y p e = e x p 1,e t y p e
Ex p1.va l = if e x p1.e t y p e = int then e x p2.va l di v e xp3.va l
e l s e e x p 2,v a l / e x p 3,v a l
e x p? num e x p.isF loat = f a ls e
e x p,v a l = i f e x p,e t y p e = i n t t h e n n u m,v a l
e lse F loat(n um.v a l)
e x p? num.num e x p.isF loat = true
e x p.va l = num.num.val
T a b,6.7
The a tt ribute s ca n b e c o mput e d b y two pa ss e s ov e r the pa rse or s y ntax tre e,
F irst pass,s y nth e siz e d a tt ribute isF loat,b y post or de r tr a v e rsa l
S e c ond pa ss,inher it e d a tt ribute e t y pe a nd s y nthes iz e d a tt ribute va l in a c o mbi ne d
tra ve rsa l (pr e /post orde r),
6.2.3 Attributes as Parameters
and Returned Values.
Many attributes are the same or are only used
temporarily to compute other attribute values,
– needn’t be stored as fields in a syntax tree record
structure
Inherited attributes,
– be computed in preorder,often be treated as
parameters of the call
Synthesized attributes,
– be computed in postorder,often be treated as returned
values of the call
Example 6.15 consider the recursive procedure
EvalWithBase of example 6.13,we can turn base
into a parameter and val into a returned val,
Function EvalWithBase(T,treenode; base:integer):integer;
Var temp,temp2,integer;
Begin
Case nodekind of T of
Based-num:
Temp,= EvalWithBase(right child of T,0);
Return EvalWithBase(left child of T,temp);
Num:
Temp:= EvalWithBase(left child of T,base);
If right child of T is not nil then
Temp2,= EvalWithBase(right child of T,base);
If temp != error and temp2 !=error then
Return base*temp + temp2
Else return error;
Else return temp;
Basechar:
If child of T = o then retur 8
Else return 10;
Digit:
If base = 8 and child of T = 8 or 9 then return error
Else return numbal(child of T);
End case;
End EvalWithBase;
To start the computation,one would have to make a call
such as
– EvalWithBase(rootnode,0)
To distinguish three cases,it’s more national to write three
separate procedures as follows:
Function EvalBasedNum(T,treenode),integer;
(/*only called on root node */)
– begin
– return EvalNum(left child of T,EvalBase(right child of T));
– end ;
function EvalBase(T,treenode),integer;
(/*only called on basechar node*/)
– begin
– if child of T = o then return 8
– else return 10;
– end
function EvalNum(T:treenode; base,integer),integer;
var temp,temp2,integer;
begin
case nodekond of T of
Num:
Temp:= EvalWithBase(left child of T,base);
If right child of T is not nil then
Temp2,= EvalWithBase(right child of T,base);
If temp != error and temp2 !=error then
Return base*temp + temp2
Else return error;
Else return temp;
Digit:
If base = 8 and child of T = 8 or 9 then return error
Else return numbal(child of T);
End case;
End.
6.2.4 The Use of External Data
Structures to Store Attributes Values
Applicability:
– When not suitable to the method of parameters and
returned values
particularly when the attribute values have significant structure
and may be needed at arbitrary points during translation
– and not reasonable to be stored in the syntax tree nodes,
Ways:
– Use external data structures such as table,graphs and
other data structures to store the corresponding attribute
values;
one of the prime examples is the symbol table
– Replace attribute equations by calls to procedures
representing operations on the appropriate data structure
used to maintain the attribute values
function EvaWithBase(T:treenode),integer;
var temp,temp2,integer;
begin
case nodekond of T of
based-num:
SetBase( right child of T);
Return EvalWithBase(left child of T);
Num:
Temp:= EvalWithBase(left child of T);
If right child of T is not nil then
Temp2,= EvalWithBase(right child of T);
If temp != error and temp2 !=error then
Return base*temp + temp2
Else return error;
Else return temp;
Digit:
If base = 8 and child of T = 8 or 9 then return error
Else return numval(child of T);
End case;
End.
Procedure SetBase(T:treenode);
Begin
If child of T = o then base,=8
Else base,=10
End
W e c a n a lso c ha ng e the se mantic rule s to re fle c t the use o f the nonloc a l ba se
va ria ble,
Gr a mm a r Rule S e mantic Rul e s
B a se d - num? num base c ha r ba se d - num.val = num.bv a l
B a se c ha r? o ba se = 8
B a se c ha r? d ba se = 10
Num1? num2 di g it n u m 1,v a l =
I f di gi t,v al = er r or or num 2.val = er r or
Th en er r o r
Els e n um 2.v al * bas e+ di gi t,v al
Etc,E t c,
B ase is n o lon ge r an at t r ib u te,the se m an ti c r u l e s n o lon ge r f or m an at tr ib u te
gr a m m a r as b e f or e,
E xam p le 6.17 c onsi de r t he a tt ribute gr a mm a r of sim ple de c lar a ti ons g ive n
in e x a mpl e 6.12,tr e a t th e dt y pe a s a nonloca l v a r iable,use s y mbol tabl e t o
store the dt y p e va lues,
Gr a mm a r Rule S e mantic Rul e s
de c l? t y p e va r - li st
t y pe? int dt y pe = int e g e r
t y pe? f lo a t dt y pe = r e a l
va r - li st1? id,var - li st2 inser t(id.na me,dt y p e )
va r - li st? id inser t(id.na me,dt y p e )
P roc e dure inser t(n a me:st ring ; dt y pe,t y p e kind) is a func ti on whic h stor e th e
identifie r na me to g e the r with i ts dec lar e d da t a t y p e int o the s y mbol table,
The corresponding pseudocode for an attribute evaluation
procedure EvalType is as follows:
Procedure EvalType(T,treenode);
Begin
Case nodekind of T of
Decl:
EvalType(type child of T)
EvalType(var-list child of T)
Type:
If child of T = int then dtype,= integer;
Else dtype,=real;
Var-list:
Insert (name of first child of T,dtype)
If third child of T is not nil then
EvalType(third child of T);
End case
End
6.2.5 The Computation of Attributes
during Parsing
What extent attributes can be computed successfully at
the same time as the parsing stage depends on the power
and properties of the parsing method employed
All the major parsing methods process the input
program from left to right (LL,or LR),
– require the attribute be capable of evaluation by a left-to-right
traversal of the parse tree (synthesized attributes will always
be OK)
Definition:
– An attribute grammar for attribute a1,…,ak is L-attributed
if,for each inherited attribute aj and each grammar rule:
– X0?X1X2… Xn
The associated equations for aj are all of the form:
– Xi.aj = fij(X0.a1,…,X0.ak,…,X1.al,…,Xi-1.a1,… Xi-1.ak)
– That is,the value of aj at Xi can only depend on attribute of the
symbols X0,… Xi-1 that occur to the left of Xi in the grammar
rule
S-attributed grammar is L-attributed grammar.
Given an L-attributed grammar in which the inherited
attributes do not depend on the synthesized attributes:
– Top-down parser,a recursive-descent parser can evaluate all the
attributes by turning the inherited attributes into parameters and
synthesized attributes into returned values,
– Bottom-up parser,LR parsers are suited to handling primarily
synthesized attributes,but are difficult for inherited attributes.
1) C omput ing s y nthesiz e d a tt ribute s during L R pa rsi ng
V alu e stac k,s tore s y nt he siz e d a tt ribute s,be ma nipul a ted in pa ra ll e l with the pa rsing
stac k,F or e x a mpl e,
P a rsing sta c k input pa rsing a c ti on va lue stac k se m a nti c a c ti on
1 $ 3*4+ 5$ S hift $
2 $n *4+ 5$ R e duc e E? n $n E.va l = n.va l
3 $E *4+ 5$ S hift $3
4 $E* 4+ 5$ S hif t $3*
5 $E*n + 5$ R e duc e E? n $3*n E.va l =n.va l
6 $E*E + 5$ R e duc e E? E*E $3*4 E1.va l=E 2.va l*E3.va l
7 $E + 5$ S hift $12
8 $E+ 5$ S hift $12+
9 $E+ n $ R e duc e E? n $12+ n E.va l = n.va l
10 $E+ E $ R e duc e E? E+ E $12+ 5 E1.va l=E 2.va l +E 3.v a l
11 $E $ $17
1) I n h e riting a pre vious l y c omput e d s y nthesiz e d a tt r ibut e s during L R pa rsin g
A n ac tion associat e d to a n on te r m in al in the r igh t - h an d sid e of a r u le c an
m ak e u se of syn thesiz e d att r ib u te s of t h e sym b o ls to t h e lef t of it in t h e r u le,
F or inst a nc e,
A? B C
C,i = f (B,s) s is a s y nth e siz e d a tt ribute,
The que sti on c a n b e settl e d through a n ε – pr odu c ti on a s follows
Gr a mm a r Rule S e mantic Rul e s
A? BD C
B? … { c o m p u t e r B,s }
D? ε s a v e d _ i = f( va lst a c k[ top] )
C? … { n o w s a v e d _ i is ava il a ble}
T h e str at e gy c an b e O K w ithou t ε - p r od u c tio n when the p osition o f a p r e viou sly
c o m p u te d syn thesiz e d att r ib u te in t h e valu e stac k c an alw ays b e p r e d ic te d,
F or inst a nc e,t he f oll owing a tt ribute gr a mm a r s a ti sf y the a bove re que st
Gr a mm a r Rule S e mantic R ules
de c l? t y p e va r - li st va r - li st.dt y pe = t y pe,dt y p e
t y pe? int t y pe,dt y pe = int e g e r
t y pe? f lo a t t y pe,dt y pe = r e a l
va r - li st1? id,var - li st2 inser t(id.na me,dt y p e ),
va r - li st2.dt y pe = v a r - li st1.dt y p e
va r - li st? id inser t(id.na me,dt y p e )
it c a n be c omput e d witho ut ε - pr oduc ti on a s follo ws,
Gr a mm a r Rule S e mantic Rul e s
de c l? t y p e va r - li st
t y pe? int t y pe,dt y pe = int e g e r
t y pe? f lo a t t y pe,dt y pe = r e a l
va r - li st1? id,va r - li st2 inser t(id.na me,va lst a c k[ top - 3] ),
va r - li st? id inser t(id.na me,va lst a c k[ top - 1] )
P roble ms,
1,re quire the pr o g r a mm e r t o dire c tl y a c c e ss the va lu e stac k durin g a pa rse,is risk y
in automatica ll y g e n e r a te d pa rse rs;
2,onl y wor ks if the posi ti on of the pr e vious l y c o mput e d a tt ribute is pr e dicta ble
fr om t he g ra mm a r,
B y f ar the b e s t t e c h n iq u e f or d e ali n g w ith in h e r ite d a tt r ib u te s in L R p ar sin g
is to u se e x te r n al d at a str u c tur e s,to h old in h e r ite d at t r ib u te valu e s an d to
ad d ε _ p r od u c tion (m ay ad d p ar sin g c on f l ict s,
6.2.6 The Dependence of Attributes
Computation on the Syntax
Theorem:
– Given an attribute grammar,all inherited attributes can
be changed into synthesized attributes by suitable
modification of the grammar,without changing the
language of the grammar
Example 6.18 how an inherited attribute can be
truned into a synthesized attribute by modification
of the grammar
Consider the grammar as follows:
Decl? type var-list
Type?int|float
Var-list?id,var-list|id
The dt y p e a tt ribute is i nhe rited,we c a n r e wr it e the g r a mm a r a s follows
De c l? va r - li st i d
V a r - li st? va r - li st i d,| t y p e
T y p e? int | f lo a t
W e c a n then tr une d the in he rit attribute into s y nthe siz e d a tt ribute a s follows,
Gr a mm a r Rule S e mantic Rul e s
de c l? va r - li st i d id.dt y pe = va r - li st.dt y pe
va r - li st1? va r - li st2 i d,va rl ist 1.dt y p e = va rlist 2.dt y p e
i d,d t y p e = v a r l i s t 1,d t y p e
va r - li st? t y pe va r - li st.dt y pe = t y pe,dt y pe
t y pe? int t y pe,dt y pe = int e g e r
t y pe? f lo a t t y pe,dt y pe = r e a l
The c ha n g e in the gr a m mar a f f e c ts the pa rse tr e e a nd the dt y p e a tt ribute c omput a ti on a s
foll ows,S tring f loat x,y
F ig 6,1 1
Dt y p e = re a l
Dt y p e = re a l y p e
d ty p e
V a r - li st
V a r - li st
,
Id
(x )
Id (y ) Dt y p e = re a l
d e c l
ty p e
f lo a t
Dt y p e = re a l
End of Part One
THANKS
Principles and Practice
Kenneth C,Louden
6,Semantic Analysis
PART ONE
Semantic Analysis Phase
– Purpose,compute additional information needed for
compilation that is beyond the capabilities of Context-
Free Grammars and Standard Parsing Algorithms
– Static semantic analysis,Take place prior to execution
(Such as building a symbol table,performing type
inference and type checking)
Classification
– Analysis of a program required by the rules of the
programming language to establish its correctness and
to guarantee proper execution
– Analysis performed by a compiler to enhance the
efficiency of execution of the translated program
Description of the static semantic analysis
– Attribute grammar
identify attributes of language entities that must be computed
and to write attribute equations or semantic rules that
express how the computation of such attributes is related to the
grammar rules of the language
– Which is most useful for languages that obey the
principle of Syntax-Directed Semantics
– Abstract syntax as represented by an abstract syntax
tree
Implementation of the static semantic analysis,
– Not as clearly expressible as parsing algorithms
because of the addition problem caused by the timing of
the analysis during the compilation process
– Multi-pass (more common) or single pass lead to totally
different process
Emphasis:
– Attributes and attribute grammars
– Algorithms for attribute computation
– The symbol table
– Data types and type checking
– A semantic analyzer for the TINY language
Contents
Part One
6.1 Attributes and Attribute Grammars
6.2 Algorithms for Attribute Computation
Part Two
6.3 The Symbol Table
6.4 Data Types and Type Checking
6.5 A Semantic Analyzer for the TINY Language
6.1 Attributes and Attribute
Grammars
Attributes
– Any property of a programming language construct such as
The data type of a variable
The value of an expression
The location of a variable in memory
The object code of a procedure
The number of significant digits in a number
Binding of the attribute
– The process of computing an attribute and associating its computed
value with the language construct in question
Binding time
– The time during the compilation/execution process when the
binding of an attribute occurs
– Based on the difference of the binding time,attributes is divided
into Static attributes (be bound prior to execution) and Dynamic
attributes (be bound during execution)
Example,The binding time and significance
during compilation of the attributes,
– Attribute computations are extremely varied
– Type checker
In a language like C or Pascal,is an important part of semantic
analysis;
While in a language like LISP,data types are dynamic,LISP
compiler must generate code to compute types and perform
type checking during program execution,
– The values of expressions
Usually dynamic and the be computed during execution;
But sometime can also be evaluated during compilation
(constant folding),
Example,the binding time and significance
during compilation of the attributes,
– Attribute computations are extremely varied
– The allocation of a variable,
Either static (such as in FORTRAN77 ) or dynamic (such as in
LISP),
Sometimes it is a mixture of static and dynamic (such as in C
and Pascal) depending on the language and properties of the
variable itself.
– Object code of a procedure,
A static attribute,which is computed by the code generator
– Number of significant digits in a number,
Often not explicitly treated during compilation,
6.1.1 Attribute Grammars
X.a means the value of ‘a’ associated to ‘X’
– X is a grammar symbol and a is an attribute associated
to X
Syntax-directed semantics,
– Attributes are associated directly with the grammar
symbols of the language,
– Given a collection of attributes a1,…,ak,it implies
that for each grammar rule X0?X1X2… Xn (X0 is a
nonterminal),
– The values of the attributes Xi.aj of each grammar
symbol Xi are related to the values of the attributes of
the other symbols in the rule.
An attribute grammar for attributes a1,a2,…,
ak is the collection of all attribute equations or
semantic rules of the following form,
– for all the grammar rules of the language.
Xi.aj = fij(X0.a1,…,X0.ak,…,X1.al,…,Xn-1.a1,… Xn.ak)
Where fij is a mathematical function of its arguments
Typically,attribute grammars are written in
tabular form as follows:
Grammar Rule Semantic Rules
Rule 1 Associated attribute equations
...
Rule n Associated attribute equation
Example 6.1 consider the following simple grammar for
unsigned numbers:
Number?number digit | digit
Digit?0|1|2|3|4|5|6|7|8|9
The most significant attribute,numeric value (write as val),
and the responding attribute grammar is as follows:
Gr a mm a r Rule S e mantic Rul e s
Numbe r1? number 2 di g i t number 1.va l = numbe r2.v a l*10 + dig it,va l
Numbe r? dig it number,va l= di g it,va l
dig it? 0 dig it,va l = 0
dig it? 1 dig it,va l = 1
dig it? 2 dig it,va l = 2
dig it? 3 dig it,va l = 3
dig it? 4 dig it,va l = 4
dig it? 5 dig it,va l = 5
dig it? 6 dig it,va l = 6
dig it? 7 dig it,va l = 7
dig it? 8 dig it,va l = 8
dig it? 9 dig it,va l = 9
table 6.1
The parse tree showing attribute computations for the
number 345 is given as follows
number
( v a l = 3 4 * 1 0 + 5 = 3 4 5 )
n u m b e r d i g i t
(va l = 3 *10+ 4 = 3 4) (va l = 5 )
number dig it 5
(va l=3) (va l=4)
dig it 4
3
F ig 6.1
Example 6.2 consider the following grammar for simple integer
arithmetic expressions:
Exp? exp + term | exp-term | term
Term?term*factor | factor
Factor?(exp)| number
The principal attribute of an exp (or term or factor) is its
numeric value (write as val) and the attribute equations for the
val attribute are given as follows
Gr a mm a r Rule S e mantic Rul e s
e x p1? e x p2 + ter m e xp1.va l=e x p2.va l+te rm.va l
e x p1? e x p2 - ter m e x p 1.va l=e x p2.va l - e rm.va l
e x p1? ter m e x p 1.va l= te rm.va l
ter m1? ter m2*fa c tor ter m1.val= ter m2.v a l*f a c tor,v a l
ter m? fa c tor t e r m,v a l = f a c t o r,v a l
fa c tor? ( e x p) fa c t or,va l= e x p.va l
fa c tor? numbe r fa c tor,va l=numbe r,v a l
table 6.2
Given the expression (34-3)*42,the computations implied by
this attribute grammar by attaching equations to nodes in a
parse tree is as follows
F ig 6.2
Ex p
(v a l = 1 3 0 2 )
term
(v a l = 3 1 * 4 2 = 1 3 0 2 )
term
(v a l = 3 1 )
f a c to r
(v a l = 4 2 )
Ex p
( (v a l = 3 4 - 3 = 3 1 ) )
Ex p
(v a l = 3 4 )
term
(v a l = 3 )
f a c to r
(v a l = 3 1 )
n u m b e r
(v a l = 4 2 )
term
(v a l = 3 4 )
f a c to r
(v a l = 3 )
f a c t or
(v a l = 3 4 )
n u m b e r
(v a l = 3 )
n u m b e r
(v a l = 3 4 )
-
*
Example 6.3 consider the following simple grammar of variable
declarations in a C-like syntax:
Decl? type var-list
Type?int | float
Var-list?id,var-list |id
Define a data type attribute for the variables given by the
identifiers in a declaration and write equations expressing how
the data type attribute is related to the type of the declaration as
follows:
(We use the name dtype to distinguish the attribute from the
nonterminal type)
Gr a mm a r Rule S e mantic Rul e s
de c l? t y p e va r - li st va r - li st.dt y pe = t y pe,dt y pe
t y pe? int t y pe,dt y pe = int e g e r
t y pe? f lo a t t y pe,dt y pe = r e a l
va r - li st1? id,var - li st2 id.dt y p e = va r - li st1.dt y pe
v a r - li st2.dt y pe = v a r - li st1.dt y p e
va r - li st? id id.t y pe = va r - li st.dt y pe
table 6.3
Note that there is no equation involving the dtype of the
nonterminal decl,
It is not necessary for the value of an attribute to be specified
for all grammar symbols
Parse tree for the string float x,y showing the dtype attribute
as specified by the attribute grammar above is as follows:
F ig 6.3
At tr ib u te gr a m m ar s m ay in volve se ve r al i n te r d e p e n d e n t at tr ib u te s,
decl
T y pe
( dt y pe = r eal )
V ar - l i st
( dt y pe = r eal )
V ar - l i st
( dt y pe = r eal )
Id
( x)
( dt y pe = r eal )
Id
( y )
( dt y pe = r eal )
f l oat,
Example 6.4 consider the following grammar,where
numbers may be octal or decimal,suppose this is
indicated by a one-character suffix o(for octal) or d(for
decimal):
Based-num?num basechar
Basechar? o|d
Num? num digit | digit
Digit? 0|1|2|3|4|5|6|7|8|9
In this case num and digit require a new attribute
base,which is used to compute the val attribute,The
attribute grammar for base and val is given as follows.
Gr a mm a r Rule S e mantic Rul e s
B a se d - num? num base c ha r B a se d - num.val = num.v a l
B a se d - num.bas e = ba s e c ha r,ba se
B a se c ha r? o B a se c ha r,b a se = 8
B a se c ha r? d B a s e c h a r,b a s e = 1 0
Num1? num2 di g it num1.val =
I f di gi t,v al = er r or or num 2.val = er r or
Th en er r o r
Els e n um 2.v al * nu m 1.bas e+ di gi t,v al
N u m 2,b a s e = n u m 1,b a s e
D i g i t,b a s e = n u m 1,b a s e
Num? dig it num.val = dig it,va l
D i g i t,b a s e = num.b a se
Dig it? 0 dig it,va l = 0
Dig it? 1 dig it,va l = 1
… …
Dig it? 7 dig it,va l = 7
Dig it? 8 dig it,va l = if dig it,ba s e = 8 then e r ror e lse 8
Dig it? 9 dig it,va l = if dig it,ba s e = 8 then e r ror e lse 9
T a b 6.4
F ig 6.4
num
(v a l = 3 )
(b a se = 8 )
d ig it
(v a l = 3 )
(b a se = 8 )
3
Ba se d - num
(v a l = 2 2 9 )
num
(v a l = 2 8 * 8 + 5 = 2 2 9 )
(b a se = 8 )
b a se c h a r
(b a se = 8 )
num
(v a l = 3 * 8 + 4 = 2 8 )
(b a se = 8 )
d ig it
(v a l = 4 )
(b a se = 8 )
o
4
d ig it
(v a l = 5 )
(b a se = 8 )
5
6.1.2 Simplifications and
Extensions to Attribute Grammars
Meta-language for the attribute grammar,
– The collection of expressions allowable in an attribute
equation,
Arithmetic,logical and a few other kinds of expressions,
Together with an if-then-else expression and occasionally a
case or switch expression
Functions can be added to the meta-language
whose definitions may be given elsewhere
– For instance,digit? D (D is understood to be one of
the digits) digit.val = numval(D)
here,numval is a function which is defined as,
Int numval(char D)
{return (int)D – (int)’0’;}
Simplifications,
Using ambiguous grammar,
(all ambiguity will have been dealt with at the parser stage)
exp?exp + exp| exp – exp | exp * exp|(exp)|number
Gr a mm a r Rule S e mantic Rul e s
e x p1? e x p2+ e x p3 e xp1.va l=e x p2.va l+e x p3.va l
e x p1? e x p2 - e x p3 e x p 1.va l=e x p2.va l - e x p3.va l
e x p1? e x p2*e x p3 e xp1.va l=e x p2.va l*ex p3.va l
e x p1? (e x p2) e x p 1.va l=e x p2.va l
e x p? number e x p,va l=numbe r,va l
table 6.5
Simplifications,
Using abstract syntax tree instead of parse tree,
(34-3)*42
F ig 6.5
3
(v a l = 3 )
*
(v a l = 3 1 * 4 2 = 1 3 0 2 )
-
(v a l = 3 4 - 3 = 3 1 )
42
(v a l = 4 2 )
34
(v a l = 3 4 )
Example 6.5 define an abstract syntax tree for simple integer
arithmetic expressions by the attribute grammar as follows:
Gr a mm a r Rule S e man ti c R ules
e x p1? e x p2+ ter m e x p1.tre e = mkOpNode ( +,e x p2.tre e,ter m.t re e )
e x p1? e x p2 - ter m e x p1.tre e = mkOpNode ( -,e x p2.tre e,ter m,tre e )
e x p1? ter m e x p 1.tre e = te rm.tre e
ter m1? ter m2*fa c tor ter m1.t re e = mkOpNo de (*,te rm2.tre e,fa c tor,tre e )
ter m? fa c tor ter m.t re e = f a c to r,tre e
fa c tor? ( e x p) fa c t or,tre e = e x p.tre e
fa c tor? numbe r fa c to r,tre e = mkNumNode (numbe r,le x va l)
table 6.6
Syntax tree itself is specified by an attribute
grammar.
– mkOpNode,construct a new tree node whose operator
label is the first parameter,whose children are the
second and third parameter.
– mkNumNode,constructs a leaf node representing a
number with that value.
One question that is central to the specification of
attributes using attribute grammars is,
– How can we be sure that a particular attribute grammar
is consistent and complete?
– That is,that it uniquely defines the give attributes?
– (the simple answer is that so far we cannot.)
6.2 Algorithms for Attribute
Computation
Purpose,study the ways an attribute grammar can
be used as basis for a compiler to compute and use
the attributes defined by the equations of the
attribute grammar.
– Attribute equations is turned into computation rules
– Xi.aj = fij(X0.a1,…,X0.ak,…,X1.al,…,Xn-
1.a1,… Xn.ak)
– is viewed as an assignment of the value of the
functional expression on the right- hand side to the
attribute Xi.aj.
The attribute equations indicate the order
constraints on the computation of the attributes,
– Attribute at the right-hand side must be computed
before that at the left-hand side,
– The constraints is represented by directed graphs —
dependency graphs.
6.2.1 Dependency graphs and
evaluation order
Dependency graph of the string:
The union of the dependency graphs of the
grammar rule choices representing each
node (nonleaf) of the parse tree of the string
– Xi.aj = fij(…,Xm.ak,… )
– An edge from each node Xm.ak to Xi.aj the
node expressing the dependency of Xi.aj on
Xm.ak.
Example 6.6 Consider the grammar of Example 6.1,with the
attribute grammar as given in tab 6.1,for each symbol there is
only one node in each dependency graph,corresponding to its
val attribute
Grammar rule attribute equation
Number1?number2 digit number1.val = number2.val * 10 +digit.val
The de pe nd e nc y g r a ph fo r this g ra mm a r r ule c hoic e is
Nu m 1,v a l
Nu m 2,v a l
Dig it,v a l
The subscr ipt s for r e pe a ted s y mbol s will be omi tt e d
Numbe r? dig it number,va l = dig it,va l
The string 345 h a s the f o ll owing de pe nd e nc y g r a p h,
Nu m 1,v a l
Dig it,v a l
Nu m,v a l
Nu m b e r,v a l
Dig it,v a l
n u m b e r,v a l
Dig it,v a l
Dig it,v a l
E xam p le 6.7 c onsi de r the gra mm a r o f e x a mpl e 6.3
va r - li st1? id,var li st2
id.dt y pe = v a r - li st1.dt y p e
va r - li st2.dt y pe = va r - li st1.dt y pe
a nd the de pe nd e nc y g r a p h
sim il a rl y va r - li st? id re spond t o
V a r - li st.d ty p e
Id,d ty p e
V a r - li st.d ty p e
V a r - lis t,d ty p e
Id,ty p e
De c l? t y p e va rlist
T y p e,d t y p e —— > v a r - li st.dt y pe
I t c a n a lso be d ra wn a s,
S o,the f irst g r a ph in t his ex a mpl e c a n be dr a wn a s,
d e c l
T y p e,d ty p e
Dt y p e v a r - li st
d ty p e
d ty p e
d ty p e
V a r - li st
Id
V a r - li st
,
F inall y,the de p e nde n c y g r a ph fo r the st ring floa t x,y is
d ty p e
d ty p e
d ty p e
V a r - li st
Id (x )
V ar - li st
,
Id (y ) d ty p e
d e c l
T y p e d ty p e
f lo a t
Example 6.8 consider the grammar of based
number of example 6.4
based-num?num basechar
Num?num digit
Num?digit
Digit?9
…
F or strin g 345o,the c or re spondi ng de pe nd e nc y
g r a ph is a s follows,
num
d ig it
3
Ba se d - num
num b a se c h a r
num
d ig it
o
4
d ig it
5
v a l
v a l
v a l
v a l b a se
v a l
v a l
v a l
b a se
b a se
b a se
b a se
b a se
b a se
Any algorithm must compute the attribute at each
node in the dependency graph before it attempts to
compute any successor attributes
– A traversal order of the dependency graph that obeys
this restriction is called a topological sort
– Requiring that the graph must be acyclic,such graphs
are called directed acyclic graphs Or DAGs
E xam p le 6.9
The de pe nd e nc y of F i g 6,6 is a D AG,whic h g ives a s follows,
F ig 6.7
Anothe r topolog ic a l sort is g iven b y the or d e r
12 6 9 1 2 1 1 3 8 4 5 7 10 13 14
B as e( 4)
B as e( 5)
V al ( 14)
V a l ( 1 4 )
V al ( 13)
V al ( 10)
V al ( 7)
V al ( 6)
V al ( 12)
V al ( 9)
B as e( 2)
B as e( 3)
B as e( 8)
B as e( 1)
B as e( 1 1)
One question,how attribute values are found at
the roots of the graph (root of the graph mean that
has no predecessors)
Attribute values at these nodes is often in the form
of tokens,and should be computed before any
other attribute values
Parse tree method,
– Construction of the dependency graph is based on the
specific parse tree at compile time,add complexity,and
need circularity detective
Rule based method,
– Fix an order for attribute evaluation at compiler
construction time
6.2.2 Synthesized and Inherited
Attributes
Classification of the attributes,
1,Synthesized attributes
2,Inherited attributes
Definition,
– An attribute is synthesized if all its
dependencies point form child to parent in the
parse tree,
– Equivalently,an attribute a is synthesized if,
given a grammar rule A?X1X2… Xn,the only
associated attribute equation with an ‘a’ on the
left-hand side is of the form:
A.a = f(X1.a1,… X1.ak,… Xn.a1,… Xn.ak)
An S-attributed grammar
– An attribute grammar in which all the attributes are
synthesized
The attribute values of an S-attributed grammar
can be computed by
– a single bottom-up,or post-order,traversal of the
parse or syntax tree,Just as follows:
Procedure PostEval (T,treenode);
Begin
For each child C of T do
PostEval(C);
Compute all synthesized attributes of T;
End
Example 6.11 Consider the attribute grammar for simple
arithmetic expressions (example 6.2),with the synthesized
attribute val
Given the following structure for a syntax tree:
Typedef enum {Plus,Minus,Times} opkind;
Typedef enum {opkind,constkind} expkind;
Typedef struct streenode
{expkind kind;
opkind op;
struct streenode *lchild,*rchild;
int val;
} Streenode;
Typedef Streenode *Syntaxtree;
The PostEval pseudocode would translate into the C code as follows:
Void postEval(Syntaxtree t)
{int temp;
if (t->kind == opkind)
{postEval(t->lchild);
postEval(t_rchild);
switch (t->op)
{ case Plus:
t->val = t->lchild->val + t->rchild->val;
break;
case Minus:
t->val = t->lchild->val - t->rchild->val;
break;
case Times:
t->val = t->lchild->val * t->rchild->val;
break;
}
}
}
De f in ition,
An a tt ribute that is not s y nthesiz e d is ca ll e d a n in h e r ite d a tt ribute,
S u c h as d type in t h e e xam p le b e low,
De c l? t y pe va r - li st
T y p e? int | flo a t
V a r - li st? id,var - li st | id
T wo ba sic kinds of de p e n de nc y of inhe rited a tt ribu tes,
(a ) I nh e ritanc e f or m p a r e nt t o si bli ng s (b) I nh e ritanc e f rom sibl ing t o si bli ng
a A
a B
a C
A
a B
a C
I f some stru c ture s in a s y ntax tre e a re im ple mente d via sibl in g poin ter s,then
sibl ing inher it a nc e c a n p r oc e e d dir e c tl y a lon g a sib li ng c ha in,a s follows,
(c ) Si bli ng inher it a n c e vi a sibl ing point e rs
inher it e d a tt ribute s c a n be c omput e d b y a pr e or de r tra v e rsa l,or c ombi ne d
pr e or de r/inorde r tr a ve rs a l of the pa rse o r s y ntax tre e,r e pr e se nted b y the f oll owing
pseud oc ode,
P roc e dure P r e Eva l(T,t r e e node );
B e g in
F or e a c h c hil d C o f T do
C omput e a ll inher it e d a tt ribute s of T ;
P re Eva l(C);
End;
a B
A
a C
The order in which the inherited attributes
of the children are computed is important
– It must adhere to any requirements of the
dependencies
Example 6.12 consider the grammar with
the inherited attribute dtype and its
dependency graphs as illustrated
Decl?type var-list
Type?int|float
Var-list?id,var-list|id
P roc e dure Ev a lT y pe ( T,t re e node );
B e g in
C a se node kind of T o f
De c l,
Eva lT y p e (t y pe c hil d of T );
Assig n dt y pe of t y p e c hil d of T to var - li st chil d of T ;
Eva lT y p e (va r - li st chil d of T) ;
T y p e,
I f c hil d of T = int then T,dt y pe,= inte ge r
Else T,dt y pe,= re a l;
V a r - li st,
Assig n T,dt y pe to first ch il d of T ;
I f thi rd c hil d of T is no t n il then
Assig n T,dt y pe to t hird c hil d;
Eva lT y p e (third c hil d of T );
End c a se ;
End Eva lT y p e ;
I n the p roc e dure a bove,p re or de r a nd inord e r ope ra ti ons a re mi x e d,
I no rde r,de c l node
P re or de r,va r - li st nod e
F ig 6.10
d ty p e
d ty p e
V a r - li st(2 )
Id (x )(3 )
V a r - li st(4 )
,
Id (y )(5 ) d ty p e
d e c l
1 )T y p e d ty p e
f lo a t
I f us e the a c tual C c ode,a ssum e that a s y ntax tre e ha s be e n c onst ruc ted,in
whic h var - li st is r e p r e s e n te d b y a si b l in g li st o f i d n od e s as f oll o w s,
The s y nt a x tre e struc ture is,
T y p e de f e num {dec l,t y p e,id} nodekind;
T y p e de f e num {i ntege r,r e a l} t y p e kind;
T y p e de f stru c t t re e nod e
{node kind ki nd;
struc t t re e node *l c hil d,*rc hil d,* si bli ng ;
t y pe kind dt y pe ;
c ha r *na m e ;
} *S y ntax tre e ;
d e c l
T y p e (d t y p e
= re a l)
Id (x ) Id (y )
The EvalType procedure now has the corresponding C code:
void evaltype (syntaxtree t)
{ switch (t->kind)
{case decl:
t->rchild->dtype = t->lchild->dtype
evaltype(t->rchild);
break;
case id:
if(t->sibling != NULL)
{ t->sibling->dtype = t->dtype;
evaltype(t->sibling);
}
break;
}
}
The code above can be simplified to the following
non-recursive procedure:
void evaltype(syntaxtree t)
{ if(t->kind = = decl)
{ syntaxtree p = t->rchild;
p->dtype = t->lchlild->dtype;
while (p->sibling !=NULL)
{ p->sibling->dtype = p->dtype;
p = p->sibling;
}
}
}
Example 6.13 Consider the following grammar
which has the inherited attribute base.
Based-num?num basechar
Basechar?o|d
Num?num digit | digit
Digit?0|1|2|3|4|5|6|7|8|9
Features,
– Two attributes include synthesized attribute val and
inherited attribute base,on which val depends;
– The base attribute is inherited from the right child to the
left child of a based-num,
B a se is c omput e d in pre o rde r a nd v a l i n p ostorde r during a sin g le p a ss as f o ll ows,
num
d ig it
3
Ba se d - num
num ba se c h a r
num
d ig it
o
4
d ig it
5
v a l
v a l
v a l
v a l b a se
v a l
v a l
v a l
b a se
b a se
b a se
b a se
b a se
b a se
P roc e dure Ev a lW it hB a se (T,t re e node );
B e g in
C a se node kind of T o f
B a se d - num,
Eva lW it hB a se (r i g ht child of T) ;
Assig n ba s e of r i g ht chil d of T to base o f le ft c hil d;
Eva lW it hB a se ( lef t c hil d of T) ;
Assig n va l of l e ft c hil d o f T to T,va l;
Num,
As sig n T,ba se to b a se of lef t child of T ;
Eva lW it h B a se (le ft c hil d of T) ;
I f r i g ht child of T is no t n il then
Assig n T,ba se to b a se of rig ht child of T ;
Eva lW it hB a se (r i g ht child of T) ;
I f va ls of lef t a nd ri g ht ch il dr e n != e rr or then
T,va l,= T,ba se *(va l of l e ft c hil d) + v a l of r i g ht c hil d
Else T,va l,= e rr o r;
Else T,va l,= va l of le ft c hil d;
B a se c ha r,
I f c hil d of T = o then T,b a se,=8;
Else T,ba se,=10;
Dig it,
I f T,ba se = 8 a nd c hil d of T = 8 or 9 then T,va l,= e rr or
Else T,va l,= numval( c hil d of T) ;
End c a se ;
End Eva lW it hB a se ;
To compute all the attributes in a single pass over the
parse or syntax tree,the inherited attributes shouldn’t
depend on any synthesized attributes
The synthesized attributes could depend on the inherited
attributes (as well as other synthesized attributes).
Procedure CombinedEval(T:treenode);
Begin
For each child C of T do
Compute all inherited attributes of C;
CombinedEval(C);
Compute all synthesized attributes of T.
End;
When inherited attributes depend on synthesized attributes,
it requires more than one pass over the parse or syntax tree
Example 6.14 consider the following simple
version of an expression grammar:
Exp?exp/exp|num|num.num
Operations may be interpreted differently
depending on whether they are floating-point or
strictly integer operations,
For instance,5/2/2.0 = 1.25
5/2/2 = 1
The attributes to express corresponding semantic:
– isFloat,boolean,indicates if any part of an expression
has a floating-point value (synthesized)
– etype,gives the type of each subexpression and
depends on isFloat (inherited),here is int or float
– val,gives the numeric value of each subexpression,
depends on etype.
Gr a mm a r Rule S e mantic Rul e s
S? e x p e x p.e t y pe = if e x p.isF loat then f loat e lse int
S,va l = e x p.va l
Ex p1? e x p2/ex p3 e x p1.isF loat = e x p2.isF loat or e x p3.isF loat
E x p2.e t y p e = e x p1.e t y p e
E x p 3,e t y p e = e x p 1,e t y p e
Ex p1.va l = if e x p1.e t y p e = int then e x p2.va l di v e xp3.va l
e l s e e x p 2,v a l / e x p 3,v a l
e x p? num e x p.isF loat = f a ls e
e x p,v a l = i f e x p,e t y p e = i n t t h e n n u m,v a l
e lse F loat(n um.v a l)
e x p? num.num e x p.isF loat = true
e x p.va l = num.num.val
T a b,6.7
The a tt ribute s ca n b e c o mput e d b y two pa ss e s ov e r the pa rse or s y ntax tre e,
F irst pass,s y nth e siz e d a tt ribute isF loat,b y post or de r tr a v e rsa l
S e c ond pa ss,inher it e d a tt ribute e t y pe a nd s y nthes iz e d a tt ribute va l in a c o mbi ne d
tra ve rsa l (pr e /post orde r),
6.2.3 Attributes as Parameters
and Returned Values.
Many attributes are the same or are only used
temporarily to compute other attribute values,
– needn’t be stored as fields in a syntax tree record
structure
Inherited attributes,
– be computed in preorder,often be treated as
parameters of the call
Synthesized attributes,
– be computed in postorder,often be treated as returned
values of the call
Example 6.15 consider the recursive procedure
EvalWithBase of example 6.13,we can turn base
into a parameter and val into a returned val,
Function EvalWithBase(T,treenode; base:integer):integer;
Var temp,temp2,integer;
Begin
Case nodekind of T of
Based-num:
Temp,= EvalWithBase(right child of T,0);
Return EvalWithBase(left child of T,temp);
Num:
Temp:= EvalWithBase(left child of T,base);
If right child of T is not nil then
Temp2,= EvalWithBase(right child of T,base);
If temp != error and temp2 !=error then
Return base*temp + temp2
Else return error;
Else return temp;
Basechar:
If child of T = o then retur 8
Else return 10;
Digit:
If base = 8 and child of T = 8 or 9 then return error
Else return numbal(child of T);
End case;
End EvalWithBase;
To start the computation,one would have to make a call
such as
– EvalWithBase(rootnode,0)
To distinguish three cases,it’s more national to write three
separate procedures as follows:
Function EvalBasedNum(T,treenode),integer;
(/*only called on root node */)
– begin
– return EvalNum(left child of T,EvalBase(right child of T));
– end ;
function EvalBase(T,treenode),integer;
(/*only called on basechar node*/)
– begin
– if child of T = o then return 8
– else return 10;
– end
function EvalNum(T:treenode; base,integer),integer;
var temp,temp2,integer;
begin
case nodekond of T of
Num:
Temp:= EvalWithBase(left child of T,base);
If right child of T is not nil then
Temp2,= EvalWithBase(right child of T,base);
If temp != error and temp2 !=error then
Return base*temp + temp2
Else return error;
Else return temp;
Digit:
If base = 8 and child of T = 8 or 9 then return error
Else return numbal(child of T);
End case;
End.
6.2.4 The Use of External Data
Structures to Store Attributes Values
Applicability:
– When not suitable to the method of parameters and
returned values
particularly when the attribute values have significant structure
and may be needed at arbitrary points during translation
– and not reasonable to be stored in the syntax tree nodes,
Ways:
– Use external data structures such as table,graphs and
other data structures to store the corresponding attribute
values;
one of the prime examples is the symbol table
– Replace attribute equations by calls to procedures
representing operations on the appropriate data structure
used to maintain the attribute values
function EvaWithBase(T:treenode),integer;
var temp,temp2,integer;
begin
case nodekond of T of
based-num:
SetBase( right child of T);
Return EvalWithBase(left child of T);
Num:
Temp:= EvalWithBase(left child of T);
If right child of T is not nil then
Temp2,= EvalWithBase(right child of T);
If temp != error and temp2 !=error then
Return base*temp + temp2
Else return error;
Else return temp;
Digit:
If base = 8 and child of T = 8 or 9 then return error
Else return numval(child of T);
End case;
End.
Procedure SetBase(T:treenode);
Begin
If child of T = o then base,=8
Else base,=10
End
W e c a n a lso c ha ng e the se mantic rule s to re fle c t the use o f the nonloc a l ba se
va ria ble,
Gr a mm a r Rule S e mantic Rul e s
B a se d - num? num base c ha r ba se d - num.val = num.bv a l
B a se c ha r? o ba se = 8
B a se c ha r? d ba se = 10
Num1? num2 di g it n u m 1,v a l =
I f di gi t,v al = er r or or num 2.val = er r or
Th en er r o r
Els e n um 2.v al * bas e+ di gi t,v al
Etc,E t c,
B ase is n o lon ge r an at t r ib u te,the se m an ti c r u l e s n o lon ge r f or m an at tr ib u te
gr a m m a r as b e f or e,
E xam p le 6.17 c onsi de r t he a tt ribute gr a mm a r of sim ple de c lar a ti ons g ive n
in e x a mpl e 6.12,tr e a t th e dt y pe a s a nonloca l v a r iable,use s y mbol tabl e t o
store the dt y p e va lues,
Gr a mm a r Rule S e mantic Rul e s
de c l? t y p e va r - li st
t y pe? int dt y pe = int e g e r
t y pe? f lo a t dt y pe = r e a l
va r - li st1? id,var - li st2 inser t(id.na me,dt y p e )
va r - li st? id inser t(id.na me,dt y p e )
P roc e dure inser t(n a me:st ring ; dt y pe,t y p e kind) is a func ti on whic h stor e th e
identifie r na me to g e the r with i ts dec lar e d da t a t y p e int o the s y mbol table,
The corresponding pseudocode for an attribute evaluation
procedure EvalType is as follows:
Procedure EvalType(T,treenode);
Begin
Case nodekind of T of
Decl:
EvalType(type child of T)
EvalType(var-list child of T)
Type:
If child of T = int then dtype,= integer;
Else dtype,=real;
Var-list:
Insert (name of first child of T,dtype)
If third child of T is not nil then
EvalType(third child of T);
End case
End
6.2.5 The Computation of Attributes
during Parsing
What extent attributes can be computed successfully at
the same time as the parsing stage depends on the power
and properties of the parsing method employed
All the major parsing methods process the input
program from left to right (LL,or LR),
– require the attribute be capable of evaluation by a left-to-right
traversal of the parse tree (synthesized attributes will always
be OK)
Definition:
– An attribute grammar for attribute a1,…,ak is L-attributed
if,for each inherited attribute aj and each grammar rule:
– X0?X1X2… Xn
The associated equations for aj are all of the form:
– Xi.aj = fij(X0.a1,…,X0.ak,…,X1.al,…,Xi-1.a1,… Xi-1.ak)
– That is,the value of aj at Xi can only depend on attribute of the
symbols X0,… Xi-1 that occur to the left of Xi in the grammar
rule
S-attributed grammar is L-attributed grammar.
Given an L-attributed grammar in which the inherited
attributes do not depend on the synthesized attributes:
– Top-down parser,a recursive-descent parser can evaluate all the
attributes by turning the inherited attributes into parameters and
synthesized attributes into returned values,
– Bottom-up parser,LR parsers are suited to handling primarily
synthesized attributes,but are difficult for inherited attributes.
1) C omput ing s y nthesiz e d a tt ribute s during L R pa rsi ng
V alu e stac k,s tore s y nt he siz e d a tt ribute s,be ma nipul a ted in pa ra ll e l with the pa rsing
stac k,F or e x a mpl e,
P a rsing sta c k input pa rsing a c ti on va lue stac k se m a nti c a c ti on
1 $ 3*4+ 5$ S hift $
2 $n *4+ 5$ R e duc e E? n $n E.va l = n.va l
3 $E *4+ 5$ S hift $3
4 $E* 4+ 5$ S hif t $3*
5 $E*n + 5$ R e duc e E? n $3*n E.va l =n.va l
6 $E*E + 5$ R e duc e E? E*E $3*4 E1.va l=E 2.va l*E3.va l
7 $E + 5$ S hift $12
8 $E+ 5$ S hift $12+
9 $E+ n $ R e duc e E? n $12+ n E.va l = n.va l
10 $E+ E $ R e duc e E? E+ E $12+ 5 E1.va l=E 2.va l +E 3.v a l
11 $E $ $17
1) I n h e riting a pre vious l y c omput e d s y nthesiz e d a tt r ibut e s during L R pa rsin g
A n ac tion associat e d to a n on te r m in al in the r igh t - h an d sid e of a r u le c an
m ak e u se of syn thesiz e d att r ib u te s of t h e sym b o ls to t h e lef t of it in t h e r u le,
F or inst a nc e,
A? B C
C,i = f (B,s) s is a s y nth e siz e d a tt ribute,
The que sti on c a n b e settl e d through a n ε – pr odu c ti on a s follows
Gr a mm a r Rule S e mantic Rul e s
A? BD C
B? … { c o m p u t e r B,s }
D? ε s a v e d _ i = f( va lst a c k[ top] )
C? … { n o w s a v e d _ i is ava il a ble}
T h e str at e gy c an b e O K w ithou t ε - p r od u c tio n when the p osition o f a p r e viou sly
c o m p u te d syn thesiz e d att r ib u te in t h e valu e stac k c an alw ays b e p r e d ic te d,
F or inst a nc e,t he f oll owing a tt ribute gr a mm a r s a ti sf y the a bove re que st
Gr a mm a r Rule S e mantic R ules
de c l? t y p e va r - li st va r - li st.dt y pe = t y pe,dt y p e
t y pe? int t y pe,dt y pe = int e g e r
t y pe? f lo a t t y pe,dt y pe = r e a l
va r - li st1? id,var - li st2 inser t(id.na me,dt y p e ),
va r - li st2.dt y pe = v a r - li st1.dt y p e
va r - li st? id inser t(id.na me,dt y p e )
it c a n be c omput e d witho ut ε - pr oduc ti on a s follo ws,
Gr a mm a r Rule S e mantic Rul e s
de c l? t y p e va r - li st
t y pe? int t y pe,dt y pe = int e g e r
t y pe? f lo a t t y pe,dt y pe = r e a l
va r - li st1? id,va r - li st2 inser t(id.na me,va lst a c k[ top - 3] ),
va r - li st? id inser t(id.na me,va lst a c k[ top - 1] )
P roble ms,
1,re quire the pr o g r a mm e r t o dire c tl y a c c e ss the va lu e stac k durin g a pa rse,is risk y
in automatica ll y g e n e r a te d pa rse rs;
2,onl y wor ks if the posi ti on of the pr e vious l y c o mput e d a tt ribute is pr e dicta ble
fr om t he g ra mm a r,
B y f ar the b e s t t e c h n iq u e f or d e ali n g w ith in h e r ite d a tt r ib u te s in L R p ar sin g
is to u se e x te r n al d at a str u c tur e s,to h old in h e r ite d at t r ib u te valu e s an d to
ad d ε _ p r od u c tion (m ay ad d p ar sin g c on f l ict s,
6.2.6 The Dependence of Attributes
Computation on the Syntax
Theorem:
– Given an attribute grammar,all inherited attributes can
be changed into synthesized attributes by suitable
modification of the grammar,without changing the
language of the grammar
Example 6.18 how an inherited attribute can be
truned into a synthesized attribute by modification
of the grammar
Consider the grammar as follows:
Decl? type var-list
Type?int|float
Var-list?id,var-list|id
The dt y p e a tt ribute is i nhe rited,we c a n r e wr it e the g r a mm a r a s follows
De c l? va r - li st i d
V a r - li st? va r - li st i d,| t y p e
T y p e? int | f lo a t
W e c a n then tr une d the in he rit attribute into s y nthe siz e d a tt ribute a s follows,
Gr a mm a r Rule S e mantic Rul e s
de c l? va r - li st i d id.dt y pe = va r - li st.dt y pe
va r - li st1? va r - li st2 i d,va rl ist 1.dt y p e = va rlist 2.dt y p e
i d,d t y p e = v a r l i s t 1,d t y p e
va r - li st? t y pe va r - li st.dt y pe = t y pe,dt y pe
t y pe? int t y pe,dt y pe = int e g e r
t y pe? f lo a t t y pe,dt y pe = r e a l
The c ha n g e in the gr a m mar a f f e c ts the pa rse tr e e a nd the dt y p e a tt ribute c omput a ti on a s
foll ows,S tring f loat x,y
F ig 6,1 1
Dt y p e = re a l
Dt y p e = re a l y p e
d ty p e
V a r - li st
V a r - li st
,
Id
(x )
Id (y ) Dt y p e = re a l
d e c l
ty p e
f lo a t
Dt y p e = re a l
End of Part One
THANKS
