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

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

1、COMPILERCONSTRUCTIONPrinciplesandPracticeKennethC.Louden4.Top-DownParsingPARTTWOContentsPARTONE4.1Top-DownParsingbyRecursive-Descent4.2LL(1)Parsing[More]PARTTWO4.3FirstandFollowSets[More]4.4ARecursive-DescentParserfortheTINYLanguage[More]4.5ErrorRecoveryinTop-DownParsers4.1Top-DownParsin

2、gbyRecursive-Descent4.2LL(1)Parsing4.2.1TheBasicMethodofLL(1)ParsingMainideaLL(1)ParsingusesanexplicitstackratherthanrecursivecallstoperformaparseAnexample:asimplegrammarforthestringsofbalancedparentheses:S→(S)S∣εThefollowingtableshowstheactionsofatop-downparsergiventhisgrammarandthestri

3、ng()TableofActionsStepsParsingStackInputAction1$S()$S→(S)S2$S)S(()$match3$S)S)$S→ε4$S))$match5$S$S→ε6$$acceptGeneralSchematicAtop-downparserbeginsbypushingthestartsymbolontothestackItacceptsaninputstringif,afteraseriesofactions,thestackandtheinputbecomeemptyAgeneralschematicforasuccessfu

4、ltop-downparse:$StartSymbolInputstring$……//oneofthetwoactions……//oneofthetwoactions$$acceptTwoActionsThetwoactionsGenerate:Replaceanon-terminalAatthetopofthestackbyastringα(inreverse)usingagrammarruleA→α,andMatch:Matchatokenontopofthestackwiththenextinputtoken.Thelistofgeneratingactionsi

5、ntheabovetable:S=>(S)S[S→(S)S]=>()S[S→ε]=>()[S→ε]Whichcorrespondspreciselytothestepsinaleftmostderivationofstring().Thisisthecharacteristicoftop-downparsing.4.2.2TheLL(1)ParsingTableandAlgorithmPurposeandExampleofLL(1)TablePurposeoftheLL(1)ParsingTable:Toexpressthepossiblerulechoicesfora

6、non-terminalAwhentheAisatthetopofparsingstackbasedonthecurrentinputtoken(thelook-ahead).TheLL(1)Parsingtableforthefollowingsimplegrammar:S→(S)S∣εM[N,T]()$SS→(S)SS→εS→εTheGeneralDefinitionofTableThetableisatwo-dimensionalarrayindexedbynon-terminalsandterminalsContainingproductionchoicesto

7、useattheappropriateparsingstepcalledM[N,T]Nisthesetofnon-terminalsofthegrammarTisthesetofterminalsortokens(including$)AnyentrancesremainingemptyRepresentingpotentialerrorsTable-ConstructingRuleThetable-constructingruleIfA→αisaproductionchoice,andthereisaderivationα=>*aβ,w