东南大学 编译原理 课件 Cp4.ppt

Chapter4SyntaxAnalysis ZhaiYuqingZhouXiaoyu Introduction DescriptionoftheSyntax Context freegrammars AdvantagesOfferedbyGrammar 1 tobothlanguagedesignersandcompilerwritersprecise structuralforlanguagedescriptionandparserconstruction errorreport facilitateevolvementofprogramminglanguages PositionofParserinCompilerModel TheRoleoftheParser 1 Obtainsastringoftokensfromthelexicalanalyzer Verifiesthatthestringcanbegeneratedbythegrammar Reportsanysyntaxerrorsinanintelligiblefashion TheRoleoftheParser 2 Recoversfromcommonlyoccurringerrorssothatitcancontinueprocessingtheremainderofitsinput Generatestheparsetree GeneralTypesofParsersforGrammar UniversalParsingMethod Cocke Yonger KasamialgorithmEarley salgorithmtooinefficient Top DownMethod Buildparsetreesfromthetop root tothebottom leaves DeriveandmatchLL 1 grammars oftenimplementedbyhand Bottom UpMethod reduceLRgrammars oftenconstructedbyautomatedtools SyntaxErrorHandling Errors 1 Lexicalsuchasmisspellinganidentifier keyword oroperatorSyntacticsuchasanarithmeticexpressionwithunbalancedparentheses Errors 2 SemanticsuchasanoperatorappliedtoanincompatibleoperandLogicalsuchasaninfinitelyrecursivecall Simple to StateGoalsofanErrorHandler Itshouldreportthepresenceoferrorsclearlyandaccurately Itshouldrecoverfromeacherrorquicklyenoughtobeabletodetectsubsequenterrors Itshouldnotsignificantlyslowdowntheprocessingofcorrectprograms Error RecoveryStrategies PanicmodeDiscardinputsymbolsoneatatimeuntiloneofadesignatedsetofsynchronizingtokensisfoundPhraselevelReplaceaprefixoftheremaininginputbysomestringthatallowstheparsertocontinue Error RecoveryStrategies ErrorproductionsAugmentthegrammarforthelanguageathandwithproductionsthatgeneratetheerroneousconstructsGlobalcorrection Top DownParsing BasicIdeas Left mostderivation Top down match backtracking retry Example4 14of 1 adapted ConsiderthegrammarS cAdA c ab aConstructaparsetreefortheinputstring cad Recursive DescentParsing 1 Aproceduretoconstructtheparsetreefortheinputstringstartingfromthestartsymbol normallynamedS inpreorder Whenthereisamismatch gobacktothelastnon terminalsymbolandchooseanotheralternativeproduction Recursive DescentParsing 2 Haltwhenaparsetreeisconstructedsuccessfullyfortheinputstring Announcefailurewhenitisnotpossibletoconstructaparsetreefortheinputstring Backtrackingvs Non backtracking Recursive DescentParsing inefficientNon backtrackingparser predictive FactorsConcernsPrediction Commonprecedingsymbolsderivedbyalternativeproductionsofthesamenon terminalsymbolLeft recursivegrammarAmbiguitygrammar EliminatingAmbiguity RewritingthegrammarStmt ifexprthenstmt ifexprthenstmtelsestmt other stmt matched stmt unmatched stmtmatched stmt ifexprthenmatched stmtelsematched stmt otherunmatched stmt ifexprthenstmt ifexprthenmatched stmtelseunmatched stmt EliminationofLeftRecursion Basicformofleftrecursion ImmediateleftrecursionP P IndirectleftrecursionP Aa A Pb EliminationofIntermediateLeftRecursion Thesimplestform P P P P P P EliminationofIntermediateLeftRecursion Thegeneralform p p 1 p 2 p m 1 2 n p 1P 2P nP P 1P 2P mP EliminationofIndirectLeftRecursion Howtosolvethefollowingsimplecase IndirectleftrecursionP Aa A Pb cCyclesformedbytheprecedingnon terminalsofindirectleftrecursionproductions CasesofIndirectLeftRecursion 1 Algorithm4 1 1 Arrangethenon terminalsinGinsomeorderasP1 P2 Pn 2 for i 1 i n i for k 1 k i 1 k replaceeachproductionoftheformPi Pk byPi 1 2 n wherePk 1 2 nareallthecurrentPk productions eliminatetheimmediateleftrecursion 3 Rearrangethegrammar CasesofIndirectLeftRecursion 2 P Aa f A Bb Pc B Pd Ae Example theQuestion 2 Eliminatingleftrecursionsofthefollowingproductions 1 S Qc c 2 Q Rb b 3 R Sa a Example theAnswer 2 1 Arrangethenon terminalsintheorder R Q S 2 forR noactions forQ Q Rb bQ Sab ab bforS S Qc cS Sabc abc bc c thengetS abc bc c S S abcS 3 BecauseR Qisnotreachable sodeletethemso thegrammaris S abc bc c S S abcS Notes Ifthenon terminalsisarrangedinadifferentorder theoutputgrammarwillbedifferent However itproducesthesamelanguage Thestartingsymbolshouldnotbechanged LeftFactoring Agrammartransformationforpredictiveparsingprediction PredictiveParsers stmt ifexprthenstmtelsestmt whileexprdostmt beginstmt listend Example S aA aBA bCB bDC cD dabd Answer S aEE bFF C DC cD dabd LeftFactoring ChangeproductionslikeA 1 2 nintoA A A 1 2 n PredictiveParsers Inmanycases byeliminatingleftrecursionfromagrammar andleftfactoringtheresultgrammar ForA 1 2 mthecurrentinputsymbolatherewouldbenomorethanonealternativethatderivesastringbeginningwitha TransitionDiagrambasedParsers TransitionDiagramforParsers 1 createaninitialandfinal return stateforeachproductionA X1X2 Xn createapathfrominitialtothefinalstate withedgeslabeledX1 X2 Xn TransitionDiagramforParsers 2 Thereisonediagramforeachnon terminal Thelabelsofedgesaretokensornon terminals Iftheedgeislabeledbyanon terminalA theparserinsteadgoestothestartstateforA withoutmovingtheinputcursor ParsingBasedonTransitionDiagram 3 Beginsinthestartstateforthestartsymbol Whenitisinstateswithanedgelabeledbyterminalatostatet andthenextinputsymbolisa thentheparsermovestheinputcursorandgoestostatet ParsingBasedonTransitionDiagram 4 Whenitisinstateswithanedgelabeledbynon terminalAtostatet thentheparserinsteadgoestothestartstateforA withoutmovingtheinputcursor IfiteverreachesthefinalstateforA itimmediatelygoestostatet ineffecthavingreadAfromtheinputduringthetimeitmovedfromstatestot Example4 15of 1 OriginalgrammarE E T TT T F FF E id Example4 15of 1 GrammaraftereliminationofleftrecursionE TE E TE T FT T FT F E id Example4 15of 1 Parsingtheinputstringid id id TransitionDiagramfortheGrammar SimplifiedTransitionDiagram PredictiveParsingUsingStackandParsingTable ModelofaNon recursivePredictiveParser PredictiveParsingProgramParsingTableM a b Output S Input Stack BehaviorofthePredictiveParsingProgram 1 X thesymbolontopofthestack a thecurrentinputsymbolIfX a theparserhaltsandannouncessuccess IfX a theparserpopsXoffthestackandadvancestheinputpointertothenextinputsymbol BehaviorofthePredictiveParsingProgram 2 IfXisanon terminal consultsentryM X a oftheparsingtableM ThisentrywillbeeitheranX productionoranerrorentry If M X a X UVW replacesXbyWVU withUontop Example4 17of 1 Considerthegrammar 4 11 of 1 andparsethestringid id id Example4 17of 1 ParsingtableMforGrammar 4 11 of 1 Example4 17of 1 MovesMadebyPredictiveParseroninputid id id ConstructionofPredictiveParsingTables FIRST FOLLOW FIRST V FIRST a a a VT If then isalsoinFIRST FOLLOW Fornon terminalA tobethesetofterminalsathatcanappearimmediatelytotherightofAinsomesententialform FOLLOW A a S Aa a VT IfS A then FOLLOW A ComputationofFIRST X 1 IfXisterminal thenFIRST X is X IfX isaproduction thenadd toFIRST X IfXisnon terminal andX Y1Y2 Yk Yj VN VT 1 j k then ComputationofFIRST 2 j 0 FIRST X initializationrepeat j j 1 FIRST X FIRST X FIRST Yj until j kor FIRST Y j if j k and FIRST Yk thenFIRST X FIRST X ComputationofFIRST X1X2 Xn Xi VN VT 1 i n i 0 FIRST initializationrepeat i i 1 FIRST FIRST FIRST Xi until i nand FIRST Xj if i nand FIRST Xn thenFIRST FIRST ComputationofFollow A 1 Place inFOLLOW S whereSisthestartsymboland istheinputrightend marker 2 IfthereisA B inG thenadd FIRST toFOLLOW B 3 IfthereisA B orA B whereFIRST contains thenaddFOLLOW A toFOLLOW B Example4 17of 1 1 ConsiderthefollowingGrammar constructFIRST FOLLOWforeachnon terminals1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F i8 F E Example4 17of 1 2 Answer FIRST E FIRST T FIRST F i FIRST E FIRST T ComputationofFollow A fixpointofFOLLOW A FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW F ConstructionofaPredictiveParsingTable SupposeA isaproductionwithainFIRST ThenexpandAby whenthecurrentinputsymbolisa If expandAby ifthecurrentinputsymbolisinFOLLOW A orifthe ontheinputhasbeenreachedand isinFOLLOW A AlgorithmtoConstructaPredictiveParsingTable 1 Input GrammarG Output ParsingtableM 1 ForeachproductionA dosteps2and3 2 ForeachterminalainFIRST addA toM A a AlgorithmtoConstructaPredictiveParsingTable 2 3 If isinFIRST addA toM A b foreachterminalbinFOLLOW A If isinFIRST and isinFOLLOW A addA toM A 4 MakeeachundefinedentryofMbeerror Example4 18of 1 1 ConsiderthefollowingGrammar constructpredictiveparsingtableforit 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F i8 F E Example4 18of 1 2 Answer First E First T First F i First E First T Follow E Follow E Follow T Follow T Follow F Example4 18of 1 3 LL 1 Grammars Example4 190f 1 TheFollowingGrammarabstractsthedangling elseproblem S iEtS iEtSeS aE b AfterLeftFactoringS iEtSS aS eS E bConstructpredictiveparsingtableforthegrammar PredictiveParsingTableM IllustrationoftheConfliction LL 1 Grammars whoseparsingtablehasnomultiply definedentries Whatdoes LL 1 Standsfor Thefirst L standsforscanningtheinputfromlefttoright Thesecond L standsforproducingaleftmostderivation 1 meansusingoneinputsymboloflook aheadateachsteptomakeparsingactiondecisions DistinctivePropertiesofLL 1 Grammar 1 NoambiguousorLeft recursivegrammarcanbeLL 1 DistinctivePropertiesofLL 1 Grammar 2 AgrammarGisLL 1 ifandonlyifwheneverA aretwodistinctproductionsofG First First noterminaladoboth and derivestringsbeginningwitha Atmostoneof and canderivetheemptystring If First Follow TransformingaGrammartoLL 1 Grammar EliminatingallleftrecursionLeftfactoring ErrorRecoveryinPredictiveParsing Panic modeerrorrecoveryPhrase levelrecovery Bottom UpParsing Operator precedenceParsing Operator precedenceParsingforExpressions Grammar E E F FF F G GG E iinput i i i i i PrecedenceRelations Threedisjointprecedencerelations betweencertainpairsofterminals Operator precedenceRelations thePrecedenceRelations ab meansa yieldsprecedenceto b markstheleftendofahandleab meansa hasthesameprecedenceas b appearsintheinteriorofahandleab meansa takesprecedenceover b markstherightendofahandle StackImplementationofOperator precedenceParsing Operator precedenceParsingforExpression i i i 1 scanthestringfromtheleftenduntilthefirstisencountered 2 thenscanbackwardsoverany suntilaisencountered 3 thehandlecontainseverythingtotheleftofthefirstandtotherightoftheencounteredinstep2 includinganyinterveningorsurroundingnonterminals OperatorGrammar Thegrammarhasthepropertythatnoproductionrightsideis orhastwoadjacentnon terminals DeterminationofthePrecedenceRelations Ifthereissuchstringas aP attherightsideofaproduction foreachterminalbbelongtoFIRSTVT P therelationisab FIRSTVT P b P b orP Qb b VT P Q VN DeterminationofthePrecedenceRelations Ifthereissuchstringas Pb attherightsideofaproduction foreachterminalabelongtoLASTVT P therelationisab LASTVT P a P aorP aQ a VT P Q VN DeterminationofthePrecedenceRelations Ifthereissuchstringas aPb or ab attherightsideofaproduction therelationisabtheprecedenceofaunaryoperatorisalwayshigherthanthatofabinaryoperator ConstructionoftheOperator precedenceRelationshipTable CalculatetheFIRSTVTandLASTVTforeachnon terminalsinthegrammar CalculationofFIRSTVT P 1 IftheproductionsarelikeP a orP Qa thena FIRSTVT P 2 Ifa FIRSTVT Q andthereisaproductionlikeP Q inthegrammar thena FIRSTVT P CalculationofLASTVT P Operator precedenceParsingAlgorithm Input Aninputstringwandatableofprecedencerelations Output Ifwiswellformed aparsetree otherwise anerrorindication Method Initially thestackcontains andtheinputbufferthestring Setiptopointtothefirstsymbolofw While 1 if isontopofthestackanippointsto return success else letabethetopmostterminalsymbolonthestackandletbbethesymbolpointedtobyip if ab ab Shift then pushbontothestack advanceiptothenextinputsymbol elseif ab reduce thendo popthestack untilthetopstackterminalisrelatedbytotheterminalmostrecentlypopped elseerror forthefollowinggrammar pleaseconstructtheFIRSTVTandLASTVTforthenon terminals andfindouttherelationshipbetweentheterminals S ifEbthenEelseEE E T TT T F FF iEb b Example Answer addaproductionS S FIRSTVT S if LASTVT S else i FIRSTVT E i LASTVT E i FIRSTVT T i LASTVT T i FIRSTVT F i LASTVT F i FIRSTVT Eb b LASTVT Eb b Example AdvantagesofOperator PrecedenceParsing Simple easytoconstructbyhand DisadvantagesofOperator precedenceParsing handlingtokensliketheunaryoperatorsSincetherelationshipbetweenagrammarandtheoperator precedenceparseristenuous onecannotalwaysbesuretheparseracceptsexactlythedesiredlanguage Onlyasmallclassofgrammarscanbeparsedusingoperator precedencetechniques LRParsing Shift reduceParsing HandlesHandlePruning LR k Parsing L left to rightscanR constructarightmostderivationinreversek thenumberofinputsymbolsoflookahead AdvantagesofLRParsing 1 Itcanrecognizevirtuallyallprogramminglanguageconstructsforwhichcontext freegrammarscanbewritten Itisthemostgeneralnonbacktrackingshift reduceparsingmethod Itcanparsemoregrammarsthanpredictiveparsers AdvantagesofLRParsing 2 Itcandetectasyntacticerrorassoonasitispossibletodosoonaleft to rightscanoftheinputItisusedinanumberofautomaticparsergenerators DrawbacksofLRParsing ItistoomuchworktoconstructanLRparserbyhandforatypicalprogramminglanguage LRparsergeneratorsareneeded YACC ThreetechniquesforconstructinganLRparsingTable LR 0 SLR simpleLRLR 1 canonicalLRLALR lookaheadLR CanonicalLR 0 Parsing LR 0 Item AnLR 0 itemofagrammarGisaproductionofGwithadotatsomepositionoftherightside FourItemsYieldedbyA XYZ 1 A XYZWehopetoseeastringderivablefromXYZnextontheinput A X YZWehavejustseenontheinputastringderivablefromXandthatwehopenexttoseeastringderivablefromYZnextontheinput FourItemsYieldedbyA XYZ 2 A XY ZA XYZ LR 0 ItemsYieldedbyA onlyoneitem A ViablePrefixes Eachofthisitemisaviableprefix AnExampleofLR 0 Parsing ConstructthecanonicalcollectionofsetsofLR 0 itemsforthefollowingaugmentedgrammar E aA bBA cA dB cB d AugmentingtheGrammar AugmentthegrammarwithS ES ES E ViablePrefixesoftheGrammar 1 S E2 S E 3 E aA4 E a A5 E aA 6 A cA7 A c A8 A cA 9 A d10 A d 11 E bB12 E b B13 E bB 14 B cB15 B c B16 B cB 17 B d18 B d 0 S EE aAE bB 5 B c BB cBB d 3 E b BB cBB d 2 E a AA cAA dc 1 S E 4 A c AA cAA d 8 A cA 10 A d 6 E aA 7 E bB 11 B d 9 B cB b E a c c c c d d d d A A B B KernelandNonkernelItems kernelitems whichincludetheinitialitem S S andallitemswhosedotsarenotattheleftend nonkernelitems whichhavetheirdotsattheleftend ConstructionoftheCanonicalLR 0 Collection 1 DefineaaugmentedgrammarIfGisagrammarwithstartsymbolS theaugmentedgrammarG isGwithanewstartsymbolS andproductionS SThepurposeoftheaugmentedgrammaristoindicatetotheparserwhenitshouldstopparsingandannounceacceptanceoftheinput ConstructionoftheCanonicalLR 0 Collection 2 IfIisasetofitemsforagrammarG thenclosure I isthesetofitemsconstructedfromIbythetworules Initially everyiteminIisaddedtoclosure I IfA B isinCLOSURE I andB isaproduction thenaddtheitemB toCLOSURE I ApplythisruleuntilnomorenewitemscanbeaddedtoCLOSURE I 3 theGotoOperationForm goto I X IisasetofitemsandXisagrammarsymbolgoto I X isdefinedtobetheCLOSURE J X VN VT J A X A X I TheSets of ItemsConstructionAlgorithm voidITEMSETS LR0 C CLOSURE S S initial do for eachsetofitemsIinCandeachgrammarsymbolX if Goto I X isnotemptyandnotinC addGoto I X toC untilnomoresetsofitemscanbeaddedtoC TheLRParsingModel 1 LRParsingProgram a b output S0 action goto input stack TheLRParsingModel 2 ThedriverprogramisthesameforallLRparsers onlytheparsingtablechangesfromoneparsertoanother Theparsingprogramreadscharactersfromaninputbufferoneatatime Siisastate eachstatesymbolsummarizestheinformationcontainedinthestackbelowit TheLRParsingModel 3 Eachstatesymbolsummarizestheinformationcontainedinthestack Thecurrentinputsymbolareusedtoindextheparsingtableanddeterminetheshift reduceparsingdecision Inanimplementation thegrammarsymbolsneednotappearonthestack TheParsingTable Action S a Srepresentthestatecurrentlyontopofthestack andarepresentthecurrentinputsymbol Action S a specifiestheparsingactionforSanda ActionShift LetstateS bethetargetoftheedgeleavingstateSwhichisatthetopofthestackcurrently PushS andthecurrentinputtokenontothestack ActionReduce 1 ReduceA Iflengthof is thenpop itemsfromthetop suchthatstateSm becomesthetopitem 2 IfS GOTO Sm A thenpushS andAontotheitem 3 theinputpointerholdsstill ActionAccept Theparserannouncessuccessofparsing ActionError Theparserdiscoversthatasyntaxerrorhasoccurredandcallsanerrorrecoveryroutine NotationsinaLRParsingTable Sj shifttheinputpointer push j a ontothestack rj reducebyproductionnumberedj Acceptblank error ConstructionoftheLR 0 ParsingTable 1 If A a isinIiandgoto Ii a Ij thensetACTION i a Shiftj hereamustbeaterminal If A Ik thensetACTION k a rj forallainVT hereAmaynotbeS andjistheNo ofproductionA forallnonterminalsAusingtherule ifgoto Ii A Ij thengoto i A j ConstructionoftheLR 0 ParsingTable 2 Allentriesnotdefinedbythethreerulesaremade error Theinitialstateoftheparseristheoneconstructedfromthesetofitemscontaining S S Ifanyconflictingactionsaregeneratedbytheaboverules wesaythegrammarisnotLR 0 ExampleofaLR 0 ParsingTable page108of 2 ActionConflict IfthereisasetofLR 0 itemsofgrammarGsuchasI X b A B shift reduceconflictreduce reduceconflict EliminationofConflictUsingtheCurrentInputSymbol Follow A Follow B andb Follow A andb Follow B AnambiguousgrammarcancauseconflictsandcanneverbeLR ConstructionoftheSLRParsingTable If A a isinIiandgoto Ii a Ij thensetACTION i a Shiftj hereamustbeaterminal If A Ik thensetACTION k a rj forallainfollow A hereAmaynotbeS andjistheNo ofproductionA forallnonterminalsAusingtherule ifgoto Ii A Ij thengoto i A j Ifanyconflictingactionsaregeneratedbytheaboverules wesaythegrammarisnotSLR 1 Example ConstructtheSLR 1 tableforthefollowinggrammar0 S E1 E E T2 E T3 T T F4 T F5 F E 6 F i I0 S EE E TE TT T FT FF E F i I2 E T T T F I1 S E E E T I4 F E E E TE TT T FT FF E F i I7 T T FF E F i I10 T T F I6 E E TT T FT FF E F i I8 F E E E T I11 F E I9 E E T T T F I5 F i I3 T F T E i i F F E T I2 T F i I3 I5 F I4 i I5 MovesofLRparseroni i i LR 1 Parsing AnExampletoShowDrawbackofSLRParsing EverySLR 1 grammarisunambiguous buttherearemanyunambiguousgrammarsthatarenotSLR 1 1 S S2 S L R3 S R4 L R5 L i6 R L Why How Why NoteverysymbolinFollow A FollowseveryappearanceofA TheSolution torememberthefollowingsymbolofcurrenthandle LR 1 Items Item A a isanLR 1 item 1 referstothelengthofthesecondcomponent calledth