Abstract data types Laboratorio Multimediale抽象数据类型该ppt课件.ppt

《Abstract data types Laboratorio Multimediale抽象数据类型该ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ParsingParsingCalculategrammaticalstructureofprogram,likediagrammingsentences,where:Tokens=“words”Programs=“sentences”Forfurtherinformation,read:Aho,Sethi,Ullman,“Compilers:Principles,Techniques,andTools”(a.k.a,the“DragonBook”)OutlineofcoverageContext-freegrammarsParsingTa

2、bularParsingMethodsOnepassTop-downBottom-upYaccParser:extractsgrammaticalstructureofprogramfunction-defnameargumentsstmt-listmainstmtexpressionoperatorexpressionexpressionvariablestringcout<<“hello,world”Context-freelanguagesGrammaticalstructuredefinedbycontext-freegramm

3、arstatementlabeled-statement

4、expression-statement

5、compound-statementlabeled-statementident:statement

6、caseconstant-expression:statementcompound-statement{declaration-liststatement-list}terminalnon-terminal“Context-free”=onlyonenon-terminalinleft-partParsetreesParsetree=t

7、reelabeledwithgrammarsymbols,suchthat:IfnodeislabeledA,anditschildrenarelabeledx1...xn,thenthereisaproductionAx1...xn“ParsetreefromA”=rootlabeledwithA“Completeparsetree”=allleaveslabeledwithtokensParsetreesandsentencesFrontieroftree=labelsonleaves(inleft-to-rightorder)F

8、rontieroftreefromSisasententialformFrontierofacompletetreefromSisasentenceLEaL;E“Frontier”ExampleG:LL;E

9、EEa

10、bSyntaxtreesfromstartsymbol(L):aa;Ea;b;bLEaLEaL;ELEaL;EbLEb;Sententialforms:DerivationsAlternatedefinitionofsentence:Given,inV*,sayisaderivationstepif

11、’’’and=’’’,whereAisaproductionisasententialformiffthereexistsaderivation(sequenceofderivationsteps)S(alternatively,wesaythatS*)Twodefinitionsareequivalent,butnotethattherearemanyderivationscorrespondingtoeachparsetreeAnotherexampleH:LE;L

12、EEa

13、bLEaLEa

14、L;ELEaL;EbLEb;AmbiguityForsomepurposes,itisimportanttoknowwhetherasentencecanhavemorethanoneparsetreeAgrammarisambiguousifthereisasentencewithmorethanoneparsetreeExample:EE+E

15、E*E

16、idEEEEEididid+*EEEEEididid+*Ifethenifbthendelsef{intx;y=0;}A.b.c=d;Id->s

17、s.idE->E+T->E+T+T->T

18、+T+T->id+T+T->id+T*id+T->id+id*id+T->id+id*id+idAmbiguityAmbiguityisafunctionofthegrammar