欢迎来到天天文库
浏览记录
ID:51619206
大小:319.50 KB
页数:34页
时间:2020-03-26
《编译原理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
此文档下载收益归作者所有