Sdt

Syntax Directed Definitions

1. Section5.1
Attributes
Informationassociatedwithagrammarsymbol Computedusingsemanticrulesassociatedwithgrammar
rules
Example:
PRODUCTION
SEMANTICRULES
L!Enn
printE.val
E!E
1
+T
E.val=E1.val+T.val
E!T
E.val=T.val
T!T
1
F
T.val=T1.val*F.val
T!F
T.val=F.val
F!(E)
F.val=E.val
F!num
F.val=num.val
CompilerConstruction:SyntaxDirectedTranslation–p.1/16

2. Attributes
Synthesizedattribute:attributeofanode(non-terminal)that
dependsonthevalueofattributesofchildrennodesintheparse
tree
Inheritedattribute:attributeofanode(non-terminal)that
dependsonthevalueofattributesofsiblingsandparentnodein
theparsetree
Example:
PRODUCTION
SEMANTICRULES
D!TL
L.in=T.type
T!int
T.type=INT
T!oat
T.type=FLOAT
L!L
1
;id
L1.in=L.in addtype(L.in,id.entry)
L!id
addtype(L.in,id.entry)
CompilerConstruction:SyntaxDirectedTranslation–p.2/16

3. Syntax-directeddenitions
Denition:aCFGwhereeachgrammarproduction
A!
is
associatedwithasetofsemanticrulesoftheform
b=f(c1,c2,...,ck);
where: b
isasynthesizedattributeof
A
oraninheritedattributeofone
ofthegrammarsymbolsin

c1,c2,...
areattributesofthesymbolsusedinthe
production
Translationscheme:CFGalongwithsemanticrulesinserted
atappropriatepositionsintheRHSofeachgrammarproduction
CompilerConstruction:SyntaxDirectedTranslation–p.3/16

4. Dependencygraph
Directedgraphshowingthedependenciesbetweenattributesat
variousnodesintheparsetree
Algorithm:
foreachnode
n
intheparsetree
foreachattribute
a
ofthegrammarsymbolat
n
constructanodeinthedependencygraphfor
a
foreachnode
n
intheparsetree
foreachsemanticrule
b=f(c1,...,ck)
associatedwith
theproductionusedat
n
constructanedgefromeach
c
i
to
b
Topologicalsort:orderthenodesofthegraphas m
1
;m
2
;:::;m
n
suchthatnoedgegoesfrom
m
i+k
to
m
i
forany
i;k
CompilerConstruction:SyntaxDirectedTranslation–p.4/16

5. EvaluationofSDDs
Generalscheme:
1.Parsetheinputprogramandconstructtheparsetree.
2.Drawthedependencygraphfortheparsetree.
3.Doatopologicalsortforthedependencygraph.
4.Traversenodesintopologicallysortedorder,andevaluate
attributesateachnode.
CompilerConstruction:SyntaxDirectedTranslation–p.5/16

6. Section5.3
S-attributeddenitions
Denition:SDDwithonlysynthesizedattributes
Scheme:
1.Extendparserstacktohaveanextraeldthatstoresthe
valueofattributes.
ALT
.haveaparsingstackandaparallel,valuestack.
top
!
X
X:x
Y
Y:y
.
.
.
.
.
.
2.Whenpushingaterminalsymbolonparsingstack,push
correspondingattributevalueonvaluestack
CompilerConstruction:SyntaxDirectedTranslation–p.6/16

7. S-attributeddenitions
3.Fortherule
A!X
1
X
2
:::X
r
A:a=f(X
1
:x
1
;X
2
:x
2
;:::;X
r
:x
r
)
modifythevaluestackasfollows: ntop=top-r+1;
val[ntop]=f(val[top-r+1],...,val[top]);
top=ntop;
Example:
PRODUCTION
SEMANTICRULES
L!Enn
printval[top]
E!E
1
+T
val[ntop]=val[top-2]+val[top]
E!T T!TF
val[ntop]=val[top-2]*val[top]
T!F F!(E)
val[ntop]=val[top-1]
F!num
CompilerConstruction:SyntaxDirectedTranslation–p.7/16

8. Section5.4
L-attributeddenitions
Denition:ASDDistbL-attributedifeachinheritedattributeof X
i
intheRHSof
A!X
1
:::X
n
dependsonlyon
1.attributesof
X
1
;X
2
;:::;X
i1
(symbolstotheleftof
X
i
inthe
RHS);
2.inheritedattributesof
A
.
Restrictionsfortranslationschemes:
1.Inheritedattributeof
X
i
mustbecomputedbyanaction
before
X
i
.
2.Anactionmustnotrefertosynthesizedattributeofany
symboltotherightofthataction.
3.Synthesizedattributefor
A
canonlybecomputedafterall
attributesitreferenceshavebeencompleted(usuallyatend
ofRHS).
CompilerConstruction:SyntaxDirectedTranslation–p.8/16

9. Section5.6
Bottom-uptranslation
Removingembeddedactions:
foreachembeddedaction
replaceactionbyadistinctmarkernon-terminal
M
addproduction
M!
tothegrammar
attachtheactiontotheendofthisproduction
NOTE
:Originalgrammarandmodiedgrammaracceptthesamelanguage;
actionsareperformedinthesameorderduringparsing.
Example: S!aAfC:i=f(A:s)gC
S!bABfC:i=A:sgC
C!cfC:s=g(C:i)g
)
PRODUCTION
SEMANTICRULES
S!aANC
(N:i=A:s;C:i=N:s)
N!
N:s=f(A:s)
S!bABMC
(M:i=A:s;C:i=M:s)
M!
M:s=A:s
C!c
C:s=g(C:i)
CompilerConstruction:SyntaxDirectedTranslation–p.9/16

10. Bottom-uptranslation
Assumption:Eachsymbol
X
hasonesynthesized(
X:s
)and
oneinherited(
X:i
)attribute.
1.Replaceeach A!X
1
:::X
n
by
A!M
1
X
1
:::M
n
X
n
;M
i
!fX
i
:i=f(:::)g
whereeach
M
i
isanewmarkernon-terminal
2.Whenreducingby
M
i
!
:
top!
X
i1
X
i1
:s
top1!
M
i1
X
i1
:i
.
.
.
.
.
.
top2i+4!
X
1
X
1
:s
top2i+3!
M
1
X
1
:i
top2i+2!
M
A
A:i
::::::
Compute
X
i
:i
and
pushonstack;
top top+1
CompilerConstruction:SyntaxDirectedTranslation–p.10/16

11. Bottom-uptranslation
3.Whenreducingby
A!M
1
X
1
:::M
n
X
n
:
A.s=f(val[top-2n+2],...,val[top]);
val[top-2n+1]=A.s;
top=top-2n+1;
4.Simplications:
If
X
j
hasnoinheritedattributesoriscomputedbyacopyrule
X
j
:i=X
j1
:s
discard
M
j
;adjustindicesofvalarraysuitably.
If
X
1
:i
existsand
X
1
:i=A:i
,omit
M
1
.
(avoidsparsingconictsinleftrecursivegrammars)
NOTES
:
i)LL(1)grammar+markersisLL(1))noconicts
ii)LR(1)grammar+markersmaynotbeLR(1))conictsmayoccur
CompilerConstruction:SyntaxDirectedTranslation–p.11/16

12. Bottom-uptranslation
Example:
PRODUCTION
SEMANTICRULES
STACKOPS
S!aANC
(N:i=A:s;C:i=N:s)
N!
N:s=f(A:s)
val[ntop]=f(val[top])
S!bABMC
(M:i=A:s;C:i=M:s)
M!
M:s=A:s
val[ntop]=val[top-1]
C!c
C:s=g(C:i)
val[ntop]=g(val[top-1])
CompilerConstruction:SyntaxDirectedTranslation–p.12/16

13. Miscellaneous
non-L-attributeddenitions:
D!L:T
T!integerjchar
L!L;idjid
)
D!idL
T!integerjchar
L!;idLj:T
“Hard”L-attributeddenitions:
PRODUCTION
SEMANTICRULES
S!L
L:count=0
L!L
1
1
L
1
:count=L:count+1
L!
print(L:count)
CompilerConstruction:SyntaxDirectedTranslation–p.13/16

14. Section5.5
Top-downtranslation
Left-recursionelimination:
Input:
A!A
1
YfA:a=g(A
1
:a;Y:y)g
A!XfA:a=f(X:x)g
Output:
A!XfR:i=f(X:x)gRfA:a=R:sg
R!YfR
1
:i=g(R:i;Y:y)gR
1
fR:s=R
1
:sg
R!fR:s=R:ig
Example:
E!E
1
+TfE:val=E
1
:val+T:valg
E!E
1
TfE:val=E
1
:valT:valg
E!TfE:val=T:valg
T!(E)fT:val=E:valg
T!numfT:val=num:valg
E!TfR:i=T:valgR
fE:val=R:sg
R!+TfR
1
:i=R:i+T:valgR
1
fR:s=R
1
:sg
R!TfR
1
:i=R:iT:valgR
1
fR:s=R
1
:sg
R!fR:s=R:ig
CompilerConstruction:SyntaxDirectedTranslation–p.14/16

15. Predictivetranslation
Input:translationschemebasedonagrammarsuitablefor
predictiveparsing
Output:Codeforasyntax-directedtranslator
Method:
1.Foreachnonterminal
A
,constructafunctionwith
Inputparameters:oneforeachinheritedattributeof
A
;
Returnvalue:synthesizedattributesof
A
;
Localvariables:oneforeachattributeofeachgrammar
symbolthatappearsinaproductionfor
A
.
2.Codefornon-terminal
A
decideswhatproductiontouse
basedonthecurrentinputsymbol(switchstatement).Code
foreachproductionformsonecaseofaswitchstatement.
CompilerConstruction:SyntaxDirectedTranslation–p.15/16

16. Predictivetranslation
3.Inthecodeforaproduction,tokens,nonterminals,actionsin
theRHSareconsideredlefttoright.
(i)Fortoken
X
:save
X:s
inthevariablecreatedfor
X
;
generateacalltomatch
X
andadvanceinput.
(ii)Fornonterminal
B
:generateanassignment
c=B(b1,b2,...,bk);
where: b1,b2,...
arevariablescorrespondingto
inheritedattributesof
B
,
c
isthevariableforsynthesizedattributeof
B
,
B
isthefunctioncreatedfor
B
.
(iii)Foranaction,copythecodeintothefunction,replacing
eachreferencetoanattributebythevariablecreatedfor
thatattribute.
CompilerConstruction:SyntaxDirectedTranslation–p.16/16