Syntax-Directed Definition-Example2 Production Semantic Rules E→E1+T E.loc=newtempO,E.code E.code ll T.code ll add E1.loc,T.loc,E.loc E→T E.loc T.loc,E.code=T.code T→T1*F T.loc=newtemp(,T.code Ti.code ll F.code ll mult T1.loc,F.loc,T.loc T→F T.loc F.loc,T.code=F.code F→(E) F.loc =E.loc,F.code=E.code F→id F.loc id.name,F.code=4 Symbols E,T,and F are associated with synthesized attributes loc and code. The token id has a synthesized attribute name (it is assumed that it is evaluated by the lexical analyzer). It is assumed that is the string concatenation operator. CS308 Compiler Theory 11
Syntax-Directed Definition – Example2 Production Semantic Rules E → E T E l () E d E d || T d || dd E l Tl El 1 + T E.loc=newtemp(), E.co de = E1.co de || T.co de || add E1.loc, T.loc, E.loc E → T E.loc = T.loc, E.code=T.code T → T1 * F T.loc=newtemp(), T.code = T1.code || F.code || mult T1.loc,F.loc,T.loc 1 p(), 1 || || 1 , , T → F T.loc = F.loc, T.code=F.code F → ( E ) F.loc = E.loc, F.code=E.code F → id F l. oc = id.name, F d “” .co de=“” • Symbols E T and F are associated with synthesized attributes Symbols E, T, and F are associated with synthesized attributes loc and code. • The token id has a synthesized attribute name (it is assumed that it is evaluated by the lexical analyzer). • It is assumed that || is the string concatenation operator. CS308 Compiler Theory 11
Syntax-Directed Definition-Inherited Attributes Production Semantic Rules D→TL L.in =T.type T→int T.type integer T→real T.type real L→L1id L.in =L.in,addtype(id.entry,L.in) L→id addtype(id.entry,L.in) Symbol T is associated with a synthesized attribute type. Symbol L is associated with an inherited attribute in. CS308 Compiler Theory
Syntax-Directed Definition – Inherited Attributes Production Semantic Rules D → T L L.in = T.type T → int T.type = integer T → real T.type = real L → L1 id L1.in = L.in, addtyp e (id.entry,L.in ) 1 1 yp ( y ) L → id addtype(id.entry,L.in) • Symbol T is associated with a synthesized attribute type. • Symbol L is associated with an inherited attribute in. CS308 Compiler Theory 12
A Dependency Graph-Inherited Attributes Input:real p q L.in=real T T.type=real Li.in=real addtype(q,real) real id addtype(p,real) id.entry-q id id.entry-p parse tree dependency graph CS308 Compiler Theory 13
A Dependency Graph – Inherited Attributes Input: real p q D L.in=real T L T.type=real L1.in=real addtype(q,real) real L id addtype(p,real) id.entry=q id id.entry=p parse tree dependency grap h CS308 Compiler Theory 13 p p yg p
S-Attributed Definitions Syntax-directed definitions are used to specify syntax-directed translations. To create a translator for an arbitrary syntax-directed definition can be difficult. We would like to evaluate the semantic rules during parsing (i.e.in a single pass,we will parse and we will also evaluate semantic rules during the parsing). We will look at two sub-classes of the syntax-directed definitions: - S-Attributed Definitions:only synthesized attributes used in the syntax-directed definitions. L-Attributed Definitions:in addition to synthesized attributes,we may also use inherited attributes in a restricted fashion. To implement S-Attributed Definitions and L-Attributed Definitions are easy (we can evaluate semantic rules in a single pass during the parsing). Implementations of S-attributed Definitions are a little bit easier than implementations of L-Attributed Definitions CS308 Compiler Theory 4
S-Attributed Definitions • Syntax-directed definitions are used to specify syntax-directed translations. • T l f bi To create a trans lator for an arbitrary syntax-di d d fi i i b diffi l directe d d efi nition can be difficu lt. • We would like to evaluate the semantic rules during parsing (i.e. in a single pass, we will p g p g) arse and we will also evaluate semantic rules durin g the parsing). • We will look at two sub-classes of the syntax-directed definitions: – S-Attributed Definitions: only synthesized attributes used in the syntax-directed definitions. – L-Attributed Definitions: in addition to synthesized attributes, we may also use inherited attributes in a restricted fashion. • To implement S-Attributed Definitions and L-Attributed Definitions are easy (we can evaluate semantic rules in a single pass during the parsing). • Implementations of S Implementations of S -attributed Definitions are a little bit easier than implementations attributed Definitions are a little bit easier than implementations of L-Attributed Definitions CS308 Compiler Theory 14
Bottom-Up Evaluation of S-Attributed Definitions We put the values of the synthesized attributes of the grammar symbols into a parallel stack. When an entry of the parser stack holds a grammar symbol X(terminal or non-terminal), the corresponding entry in the parallel stack will hold the synthesized attribute(s)of the symbol X. We evaluate the values of the attributes during reductions A→XYZ A.a-f(X.x,Y.y,Z.z)where all attributes are synthesized. stack parallel-stack top→z Z.z Y Yy X.x → top→ A A.a CS308 Compiler Theory 15
Bottom-Up Evaluation of S-Attributed Definitions • We put the values of the synthesized attributes of the grammar symbols into a parallel stack. – When an entry of the parser stack holds a grammar symbol X (terminal or non-terminal), the corresponding entry in the parallel stack will hold the synthesized attribute(s) of the symb lX o X. • We evaluate the values of the attributes during reductions. A → XYZ A.a=f(X.x,Y.y,Z.z) where all attributes are synthesized. stack parallel-stack top → Z Z.z Î top → Y X Y.y X.x A A.a CS308 Compiler Theory 15 . . .