编译原理大礼包万海analysis iii

PrinciplesofCompilerLecture7 ysisLecturer:HaiNotethatmostoftheseslideswerecreatedProf.Wen-junLI(SchoolofCourse

语法分析方法的分Top-Bottom-Bottom-up优点：可以分 的文缺点：实现较

Bottom-upET F 4类actionshiftreduceaccept问*如果S*柄

，则是句型wαβ.直观的理解：一个句型的句柄就是这个句型的分析树中最左那棵有父子两代 的所有叶子的从左到右的排LRD.Knuth(StanfordU.).OntheTranslationofLanguagesfromLefttoRight.InformationandControl,8(6),1965,Prof. :TheArtofComputerProgramming,TEX,Algorithm,LRParsing,Attribute r,LR(k)"L":left-to-rightscanningofthe"R“:constructingarightmostderivationink:thenumberofinputsymbolsoflookaheadthatareusedinmakingparsingdecisions,when(k)isomitted,kisassumedtobe1.LR

LR不同的LR分析法具有相同的LR分析程不同之处在于用不同的方法构造出不ACTION表和GOTO表SimpleLR(SLR)最简单的LR分如何构造SLR的分析LR(0)AnLR(0)item(itemforshort)aproductionwithadotatsomepositionofthebody.Eg.,A→XYZyieldsthefourA→·YZ·ZA→XA→XTheproductionA→єgeneratesonlyoneitem,A→·Augmented IfGisagr rwithstartsymbolS,thenG',theaugmentedgr rforG,isGwithanewstartsymbolS’andproductionS’→Considerthefollowing S a|b c|d c|dS'S'InitialInitialS'S'SSaASbEquivalentEquivalentS'SSaASbNonkernelitemsorclosureitemsEquivalentEquivalentS'SS'SSaASbSS'SIfIftheremainingstringcanbereducedtoS(expected!)SSaS'SSaASbaSS'SIfthefirstsymbolofremainingIfthefirstsymbolofremainingstringisa(shift!)Ia0Ia0SaAAcAAdI1S'SSaASbSS'SEquivalentEquivalentclosureinstateI2Ia0Ia0SaAAcAAdI1S'SSaASbSS'SbSbBBcBBdIfthefirstsymbolofremainingIfthefirstsymbolofremainingstringisb(shift!)AcAcAAcAAdI0I2SaAAcAAdAddAaSaAI1S'SSaASbSS'SbSbBBcBBdAllAllpossiblestatesfromstateI2cIcIaAcAAcAAdI2SaAAcAAddAAcAAddASaA0I1S'SSaASbSS'SbSbBBcBBdAllAllpossiblestatesfromstateI6caS'SSaASbbAllpossiblestatesfromstateI3

AcA AI2dSaAcASSbBcB I10BcBBcBBd

AAdAS'SBBd

AcASaASbBcaS'SSaASbbcAllpossiblerecognizedbya

AcA AI2dSaAcASSbBcB I10 BcBBcBBd

AAdAS'SBBdB

AcASaASbBBcBWorkingwiththeConsiderthefollowingaccWehavetheright-mostS'SaAacAaccAacccaS'SSaASbbcInputa|cc(shift

AcA AI2dSaAcASSbBcB I10 BcBBcBBd

AAdAS'SBBdB

AcASaASbBBcBcaS'SSaASbbcInputac|c(shift

AcA AI2dSaAcASSbBcB I10 BcBBcBBd

AAdAS'SBBdB

AcASaASbBBcBcaS'SSaASbbcInputacc|(shift

AcA AI2dSaAcASSbBcB I10 BcBBcBBd

AAdAS'SBBdB

AcASaASbBBcBcaS'SSaASbbcInputaccd(shift

AcA AI2dSaAcASSbBcB I10 BcBBcBBd

AAdAS'SBBdB

AcASaASbBBcBInputaccInputaccA(reducewithAdc Expectation:thedreamcomestrueAcA AAI2SaAAcAAddAcAAddAIaSaA0I1S'SSaASbSS'SbSbBBcBBddBSbBcI10BcBBcBBdBddIBBcBInputacAInputacA(reducewithAcAcAcA AAI2SaAAcAAddAcAAddASaAIa0I1S'SSaASbSS'SSbBBcBBdbdBSbBcI10BcBBcBBdBddIBBcBcaS'SSaASbbcInputaA(reducewithAcA

AcA AI2dSaAcASSbBcB I10 BcBBcBBd

AAdAS'SBBdB

AcASaASbBBcBcaS'SSaASbbcInputS(reducewithSaandaccept

AcA AI2dSaAcASSbBcB I10 BcBBcBBd

AAdAS'SBBdB

AcASaASbBBcBClosureofItem求CLOSURE({[E’→

TheFunction活前缀(ViableViableAviableprefixmustbeaprefixofaright-sententialS*rm,whereisthecontentofthestackandcontainsnoNotallprefixesofaright-sententialformareviableE*rmF*nrm(E)*where(,(E,(E)areviablebut(E)*isnot,sincetheparserwillperformreductiononceViableAviableprefixisaprefixofaright-sente