Chapter 3 -Syntax Analyzer.ppt

compiler

1. Compiler Design
Instructor:Tadesse D.
Email: [email protected]
Telegram :@tadessedejene09
Samara University

2. Chapter Three
ThisChapterCovers:
SyntaxAnalyzer
Top-DownParsing
PredictiveParsing
RegularExpressionvsContextFreeGrammar
RecursiveDescentParsing
NonRecursivePredictiveParsing

3. Syntax Analyzer
SyntaxAnalyzercreatesthesyntacticstructureofthegiven
sourceprogram.
Thissyntacticstructureismostlyaparsetree.
SyntaxAnalyzerisalsoknownasparser.
Thesyntaxofaprogrammingisdescribedbyacontext-free
grammar(CFG).WewilluseBNF(Backus-NaurForm)
notationinthedescriptionofCFGs.
Thesyntaxanalyzer(parser)checkswhetheragivensource
programsatisfiestherulesimpliedbyacontext-free
grammarornot.
Ifitsatisfies,theparsercreatestheparsetreeofthat
program.
Otherwisetheparsergivestheerrormessages.

4. Parser
Acontext-freegrammar
givesaprecise(accurate)syntacticspecificationofa
programminglanguage.
thedesignofthegrammarisaninitialphaseofthedesign
ofacompiler.
agrammarcanbedirectlyconvertedintoaparserbysome
tools.
Parserworksonastreamoftokens.
Thesmallestitemisatoken.

5. Parsers (cont.)
Wecategorizetheparsersintotwogroups:
Top-DownParser
theparsetreeiscreatedtoptobottom,startingfromthe
root.
Bottom-UpParser
theparseiscreatedbottomtotop;startingfromtheleaves
Bothtop-downandbottom-upparsersscantheinputfrom
lefttoright(onesymbolatatime).
Efficienttop-downandbottom-upparserscanbe
implementedonlyforsub-classesofcontext-free
grammars.
LLfortop-downparsing
LRforbottom-upparsing

6. Context-Free Grammars
CFGisaformalgrammarwhichisusedtogenerateall
possiblestringsinagivenformallanguage.
InaCFG,G(whereGdescribesthegrammar)canbe
definedbyfourtuplesas:G=(V,T,P,S)
Tdescribesafinitesetofterminalsymbols.
Vdescribesafinitesetofnon-terminalsymbols.
Pdescribesasetofproductionsrulesinthefollowingform
A whereAisanon-terminaland
isastringofterminalsandnon-
terminals(includingtheemptystring)
Sisthestartsymbol(oneofthenon-terminalsymbol)
Example:EE+E|E–E|E*E|E/E|-E
E(E)
Eid

7. Derivations
InCFG,thestartsymbolisusedtoderivethestring.Youcan
derivethestringbyrepeatedlyreplacinganon-terminalby
therighthandsideoftheproduction,untilallnon-terminal
havebeenreplacedbyterminalsymbols.
EE+E
E+EderivesfromE
wecanreplaceEbyE+E
toabletodothis,wehavetohaveaproductionrule
EE+Einourgrammar.
EE+Eid+Eid+id
Asequenceofreplacementsofnon-terminalsymbolsis
calledaderivationofid+idfromE.

8. Derivations (Cont.)
Ingeneraladerivationstepis
A ifthereisaproductionruleAinour
grammar
whereandarearbitrarystringsof
terminalandnon-terminalsymbols

1
2...
n(
nderivesfrom
1or
1derives
n)
:derivesinonestep
:derivesinzeroormoresteps
:derivesinoneormoresteps
*
+

9. Derivation Example
E-E-(E)-(E+E)-(id+E)-(id+id)
OR
E-E-(E)-(E+E)-(E+id)-(id+id)
Ateachderivationstep,wecanchooseanyofthenon-
terminalinthesententialformofGforthereplacement.
Ifwealwayschoosetheleft-mostnon-terminalineach
derivationstep,thisderivationiscalledasleft-most
derivation.
Ifwealwayschoosetheright-mostnon-terminalineach
derivationstep,thisderivationiscalledasright-most
derivation.

10. CFG -Terminology
L(G)isthelanguageofG(thelanguagegeneratedbyG)
whichisasetofsentences.
AsentenceofL(G)isastringofterminalsymbolsofG.
IfSisthestartsymbolofGthen
isasentenceofL(G)iffSwhereisastringof
terminalsofG.
IfGisacontext-freegrammar,L(G)isacontext-free
language.
Twogrammarsareequivalentiftheyproducethesame
language.
+

11. CFG (Cont.)
S -Ifcontainsnon-terminals,itiscalledasa
sententialformofG.
-Ifdoesnotcontainnon-terminals,itiscalled
asasentenceofG.
*

12. Left-Most and Right-Most Derivations
Left-MostDerivation
E-E-(E)-(E+E)-(id+E)-(id+id)
Right-MostDerivation
E-E-(E)-(E+E)-(E+id)-(id+id)
Wewillseethatthetop-downparserstrytofindtheleft-
mostderivationofthegivensourceprogram.
Wewillseethatthebottom-upparserstrytofindtheright-
mostderivationofthegivensourceprograminthereverse
order.

13. Parse Tree
Innernodesofaparsetreearenon-terminalsymbols.
Theleavesofaparsetreeareterminalsymbols.
Aparsetreecanbeseenasagraphicalrepresentationofa
derivation.
E -E
E
E-
-(E)
E
E
E-
( )
-(E+E)
E
E
EE
E
+
-
( )
-(id+E)
E
E
E
EE+
-
( )
id
-(id+id)
E
E
id
E
E
E+
-
( )
id

14. Ambiguity
Agrammarproducesmorethanoneparsetreefora
sentenceiscalledasanambiguousgrammar.
EE+Eid+Eid+E*E
id+id*Eid+id*id
EE*EE+E*Eid+E*E
id+id*Eid+id*id
E
E+
id
E
E
*
E
id id
E
id
E+
id
id
E
E
*
E

15. Ambiguity (cont.)
Forthemostparsers,thegrammarmustbeunambiguous.
unambiguousgrammar
uniqueselectionoftheparsetreeforasentence
Weshouldeliminatetheambiguityinthegrammarduring
thedesignphaseofthecompiler.
Anunambiguousgrammarshouldbewrittentoeliminate
theambiguity.
Wehavetopreferoneoftheparsetreesofasentence
(generatedbyanambiguousgrammar)todisambiguate
thatgrammartorestricttothischoice.

16. Ambiguity (cont.)
stmt ifexpr thenstmt |
ifexpr thenstmt elsestmt | otherstmts
ifE
1then ifE
2thenS
1else S
2

17. Ambiguity –Operator Precedence
Ambiguousgrammars(becauseofambiguousoperators)
canbedisambiguatedaccordingtotheprecedenceand
associativityrules.
EE+E|E*E|E^E|id|(E)
disambiguatethegrammar
precedence:^(righttoleft)
*(lefttoright)
+(lefttoright)
EE+T|T
TT*F|F
FG^F|G
Gid|(E)

18. Left Recursion
Agrammarisleftrecursiveifithasanon-terminalAsuch
thatthereisaderivation.
AAforsomestring
Top-downparsingtechniquescannothandleleft-recursive
grammars.
So,wehavetoconvertourleft-recursivegrammarintoan
equivalentgrammarwhichisnotleft-recursive.
Theleft-recursionmayappearinasinglestepofthe
derivation(immediateleft-recursion),ormayappearin
morethanonestepofthederivation.
+

19. Immediate Left-Recursion
AA| wheredoesnotstartwithA
 eliminateimmediateleftrecursion
AA
’
A
’
A
’
| anequivalentgrammar
Ingeneral,
AA
1|...|A
m|
1|...|
n where
1...
ndonot
startwithA
 eliminateimmediateleftrecursion
A
1A
’
|...|
nA
’
A
’

1A
’
|...|
mA
’
| an equivalent
grammar

20. Immediate Left-Recursion --Example
EE+T|T
TT*F|F
Fid|(E)
ETE
’
E
’
+TE
’
|
TFT
’
T
’
*FT
’
|
Fid|(E)
 eliminateimmediate left recursion

21. Left-Recursion --Problem
Agrammarcannotbeimmediatelyleft-recursive,butitstill
canbeleft-recursive.
Byjusteliminatingtheimmediateleft-recursion,wemay
notgetagrammarwhichisnotleft-recursive.
SAa|b
A Sc| dThis grammar is not immediately left-
recursive, but it is still left-recursive.
SAaScaor
AScAac causestoaleft-recursion
So,wehavetoeliminateallleft-recursionsfromour
grammar

22. Eliminate Left-Recursion --Example
SAa|b
AAc|Sd|f
-Orderofnon-terminals:S,A
forS:
-wedonotentertheinnerloop.
-thereisnoimmediateleftrecursioninS.
forA:
-ReplaceASdwithAAad|bd
So,wewillhaveAAc|Aad|bd|f
-Eliminatetheimmediateleft-recursioninA
AbdA
’
|fA
’
A
’
cA
’
|adA
’
|

23. Cont.
So,theresultingequivalentgrammarwhichisnotleft-
recursiveis:
SAa|b
AbdA
’
|fA
’
A
’
cA
’
|adA
’
|

24. Left-Factoring
Apredictiveparser(atop-downparserwithout
backtracking)insiststhatthegrammarmustbeleft-
factored.
grammaranewequivalentgrammarsuitablefor
predictiveparsing
stmtifexprthenstmtelsestmt|
ifexprthenstmt
whenweseeif,wecannotnowwhichproductionruleto
choosetore-writestmtinthederivation.

25. Left-Factoring (cont.)
Ingeneral,
A 
1| 
2 where is non-empty and the first
symbols of 
1and 
2(if they have one)are different.
whenprocessingwecannotknowwhetherexpand
Ato
1or
Ato
2
But,ifwere-writethegrammarasfollows
AA
’
A’
1|
2 so,wecanimmediatelyexpandA
toA
’

26. Left-Factoring --Algorithm
Foreachnon-terminalAwithtwoormorealternatives
(productionrules)withacommonnon-emptyprefix,letsay
A
1|...|
n|
1|...|
m
convertitinto
AA
’
|
1|...|
m
A
’

1|...|
n

27. Left-Factoring –Example1
AabB|aB|cdg|cdeB|cdfB

AaA
’
|cdg|cdeB|cdfB
A
’
bB|B

AaA
’
|cdA
’’
A
’
bB|B
A
’’
g|eB|fB

28. Left-Factoring –Example2
Aad|a|ab|abc|b

AaA’|b
A’d||b|bc

AaA’|b
A’d||bA’’
A’’|c