东南大学 编译原理 教学教案 Cp4.ppt

《东南大学 编译原理 教学教案 Cp4.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter4SyntaxAnalysisZhaiYuqingZhouXiaoyuIntroductionDescriptionoftheSyntaxContext-freegrammarsAdvantagesOfferedbyGrammar(1)tobothlanguagedesignersandcompilerwritersprecise,structuralforlanguagedescriptionandparserconstruction(errorreport)facilitateevolvementofprogrammingl

2、anguagesPositionofParserinCompilerModelTheRoleoftheParser(1)Obtainsastringoftokensfromthelexicalanalyzer.Verifiesthatthestringcanbegeneratedbythegrammar.Reportsanysyntaxerrorsinanintelligiblefashion.TheRoleoftheParser(2)Recoversfromcommonlyoccurringerrorssothatitcancontinue

3、processingtheremainderofitsinput.Generatestheparsetree.GeneralTypesofParsersforGrammarUniversalParsingMethodCocke-Yonger-KasamialgorithmEarley’salgorithmtooinefficientTop-DownMethodBuildparsetreesfromthetop(root)tothebottom(leaves).DeriveandmatchLL(1)grammars(oftenimplement

4、edbyhand).Bottom-UpMethodreduceLRgrammars(oftenconstructedbyautomatedtools).SyntaxErrorHandlingErrors(1)Lexicalsuchasmisspellinganidentifier,keyword,oroperatorSyntacticsuchasanarithmeticexpressionwithunbalancedparenthesesErrors(2)Semanticsuchasanoperatorappliedtoanincompati

5、bleoperandLogicalsuchasaninfinitelyrecursivecallSimple-to-StateGoalsofanErrorHandlerItshouldreportthepresenceoferrorsclearlyandaccurately.Itshouldrecoverfromeacherrorquicklyenoughtobeabletodetectsubsequenterrors.Itshouldnotsignificantlyslowdowntheprocessingofcorrectprograms

6、.Error-RecoveryStrategiesPanicmodeDiscardinputsymbolsoneatatimeuntiloneofadesignatedsetofsynchronizingtokensisfoundPhraselevelReplaceaprefixoftheremaininginputbysomestringthatallowstheparsertocontinueError-RecoveryStrategiesErrorproductionsAugmentthegrammarforthelanguageath

7、andwithproductionsthatgeneratetheerroneousconstructsGlobalcorrectionTop-DownParsingBasicIdeasLeft-mostderivation(Top-down),match,backtracking,retryExample4.14of[1](adapted)ConsiderthegrammarScAdAc

8、ab

9、aConstructaparsetreefortheinputstring“cad”.Recursive-DescentParsing(1)Ap

10、roceduretoconstructtheparsetreefortheinputstringstartingfromthestartsymbol,normall