编译原理2E全套配套课件龙书 Chapter_five(1).ppt

《编译原理2E全套配套课件龙书 Chapter_five(1).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、COMPILERCONSTRUCTIONPrinciplesandPracticeKennethC.Louden5.Bottom-UpParsingPARTONEContentsPARTONE5.1OverviewofBottom-UpParsing5.2FiniteAutomataofLR(0)ItemsandLR(0)ParsingPARTTWO5.3SLR(1)Parsing5.4GeneralLR(1)andLALR(1)Parsing5.5Yacc:AnLALR(1)ParserGeneratorPARTTHREE5.6GenerationofaTINYParserUsing

2、Yacc5.7ErrorRecoveryinBottom-UpParsers5.1OverviewofBottom-UpParsingAbottom-upparserusesanexplicitstacktoperformaparseTheparsingstackcontainstokens,nonterminalsaswellassomeextrastateinformationThestackisemptyatthebeginningofabottom-upparse,andwillcontainthestartsymbolattheendofasuccessfulparseAsc

3、hematicforbottom-upparsing:$InputString$…….$StartSymbol$acceptWheretheparsingstackisontheleft,Theinputisinthecenter,andTheactionsoftheparserareontheright.Abottom-upparserhastwopossibleactions(besides"accept"):ShiftaterminalfromthefrontoftheinputtothetopofthestackReduceastringαatthetopofthestackt

4、oanonterminalA,giventheBNFchoiceA→αAbottom-upparseristhussometimescalledashift-reduceparserOnefurtherfeatureofbottom-upparsersisthat,grammarsarealwaysaugmentedwithanewstartsymbolS'→SExample5.1Theaugmentedgrammarforbalancedparentheses:S'→SS→(S)S

5、εAbottom-upparserofthestring()usingthisgrammarisgiv

6、eninfollowingtable1234567ParsingstackInputAction$$($(S$(S)$(S)S$S$S’()$)$)$$$$$shiftreduceS→εshiftreduceS→εreduceS→(S)SreduceS'→SacceptExample.5.2Theaugmentedgrammarforrudimentaryarithmeticexpressions:E’→EE→E+n

7、nAbottom-upparseofthestringn+nusingthisgrammarisgiveninfollowingtable.1234567Parsings

8、tackinputAction$$n$E$E+$E+n$E$E’n+n$+n$n$$$$$shiftreduceE→nshiftshiftreduceE→E+nreduceE’→EacceptThehandleoftherightsententialform:Astring,togetherwithThepositionintherightsententialformwhereitoccurs,andTheproductionusedtoreduceit.Determiningthenexthandleisthemaintaskofashift-reduceparser.1234567

9、ParsingstackinputAction$$n$E$E+$E+n$E$E’n+n$+n$n$$$$$shiftreduceE→nshiftshiftreduceE→E+nreduceE’→EacceptNote:Thestringofahandleformsacompleteright-handsideofoneproduction;Therightmostpositionofthehandlestringisatthetopofthes