资源描述：
《编译原理2E全套配套课件龙书 Chapter_five(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、COMPILERCONSTRUCTIONPrinciplesandPracticeKennethC.Louden5.Bottom-UpParsingPARTTWOContentsPARTONE5.1OverviewofBottom-UpParsing5.2FiniteAutomataofLR(0)ItemsandLR(0)ParsingPARTTWO5.3SLR(1)Parsing[More]5.4GeneralLR(1)andLALR(1)Parsing[More]5.5Yacc:AnLALR(1)ParserGenerator[More]
2、5.6GenerationofaTINYParserUsingYacc5.7ErrorRecoveryinBottom-UpParsers[More]LR(0)ItemsofAGrammarA'→AA→(A)
3、aThisgrammarhaseightitems:A'→·AA'→A·A→·(A)A→(·A)A→(A·)A→(A)·A→·aA→a·DFAandtheLR(0)ParsingofThegrammar:A→(A)
4、a123456789ParsingstackinputAction$0$0(3$0(3(3$0(3(3a2$0(3(3A4
5、$0(3(3A4)5$0(3A4$0(3A4)5$0A1((a))$(a))$a)$))$))$)$)$$$shiftshiftshiftreduceA→ashiftreduceA→(A)shiftreduceA→(A)acceptTheLR(0)parsingtableOnecolumnisreservedtoindicatetheactionsforeachstate;Afurthercolumnisusedtoindicatethegrammarchoiceforthereduction;Foreachtoken,thereisacol
6、umntorepresentthenewstate;Transitionsonnon-terminalsarelistedintheGotosections.StateActionRuleInputGoto012345shiftreducereduceshiftshiftreduceA’→AA→aA→(A)(a)A33225145.3SLR(1)ParsingSLR(1),calledsimpleLR(1)parsing,usestheDFAofsetsofLR(0)itemsasconstructedintheprevioussection
7、SLR(1)increasesthepowerofLR(0)parsingsignificantbyusingthenexttokenintheinputstringFirst,itconsultstheinputtokenbeforeashifttomakesurethatanappropriateDFAtransitionexistsSecond,itusestheFollowsetofanon-terminaltodecideifareductionshouldbeperformed5.3.1TheSLR(1)ParsingAlgori
8、thmDefinitionofTheSLR(1)parsingalgorithm(1)Letsbethecurrentstate,actionsaredefinedasfollows:.1.IfstatescontainsanyitemofformA→α·XβwhereXisaterminal,andXisthenexttokenintheinputstring,thentoshiftthecurrentinputtokenontothestack,andpushthenewstatecontainingtheitemA→αX·β2.Ifst
9、atescontainsthecompleteitemA→γ·,andthenexttokenininputstringisinFollow(A)thentoreducebytheruleA→γDefinitionofTheSLR(1)parsingalgorithm(2)2.(Continue)AreductionbytheruleS'→S,isequivalenttoacceptance;Thiswillhappenonlyifthenextinputtokenis$.Inallothercases,Removethestringγand
10、acorrespondingstatesfromtheparsingstackCorrespondingly,backupintheDFAtothestatefro
