《自底向上分析》PPT课件.ppt

《《自底向上分析》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《自底向上分析》PPT课件.ppt（105页珍藏版）》请在三一办公上搜索。

1、6 自底向上分析,1,1,6.1 移进-归约分析(自底向上分析的一般过程)6.2 算符优先分析法,6.1 自底向上分析,2,2,若采用自左向右的描述和分析输入串,那么自 底向上的基本算法是：从输入符号串开始，通过重复查找当前句型的句柄(最左简单短语)，并利用有关规则进行规约，若能规约为文法的识别符号，则表示分析成功，输入符号串是文法的合法句子，否则有语法错误。,基本算法思想:,3,3,分析过程是重复一下步骤：,1、找出当前句型的句柄 x（或句柄的变形）,2、找出以 x 为右部的规则 X:=x,3、把 x 规约为X，产生语法树的一枝,关键：找出当前句型的句柄 x(或其变形），这不是很容易。,6.

2、1 移进规约分析（Shift-reduce parsing),4,4,要点：建立符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是规约。,5,5,分析过程：把输入符号串按描述顺序一一地移进符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号形成当前句型的句柄时，就根据规则进行规约，将句柄从符号栈中弹出，并将相应的非终结符号压入栈内（即规则的左部符号），然后再检查栈内符号串是否形成新的句柄，若有就再进行规约，否则移进符号。分析一直进行到读到输入串的右界符为止。最后，若栈中仅含有左界符号和识别符号，则表示分析成功，否则失败。,6,6,例：GS:SaAcBe Ab AA

3、b Bd,输入串为abbcde，检查是否是该文法的合法句子。若采用自底向上分析，即能否一步步规约当前句型的句柄，最终规约到识别符号S。先设立一个符号栈，我们统一符号“#”作为待分析的符号串的左右分界符。作为初始状态，先将符号串的分界符推进符号栈，作为栈底符号。分析过程如下表:,7,7,例：GS:SaAcBe Ab AAb Bd,8,8,这一方法简单明了,不断地进行移进规约,关键是确定当前句型的句柄.,说明:(1)例子的分析过程是一步步地规约当前句型的句柄,该句子的唯一语法树为:,注意两点：,（a）栈内符号串+未处理输入符号串=当前句型,（b）句柄都在栈顶,实际上，以上分析过程并未真正解决句柄的

4、识别问题,9,9,(2)未真正解决句柄的识别.,上述分析过程的怎样识别句柄的，主要看栈顶符号串 是否形成规则的右部。这种做法形式上是正确的，但在实际上不一定正确。举例的分析过程可以说是一种巧合。因为不能认为:对句型 xuY 而言 若有Au，即Au 就断定u是简单短语，u 就是句柄，而是要同时满足 S xAY,*,6.2 简单优先分析,例:GS SbAb A(B|a B Aa),(1)先确定符号之间的优先关系,1)X=Y if文法中有形如 AXY 2)XY if 文法中有形如 ABD的规则,其中 B X或DY。,+,.,+,*,+,例:GS SbAb b=A,A=b,bb,ab,Bb A(B|a

5、(=B,(a,aa,)a,SbAb b=A,A=b,bb,ab,Bb A(B|a(=B,(a,aa,)a,6.3 算符优先分析(Operator-Precedence Parsing),13,13,1)这是一种经典的自底向上分析法，简单直观，并被广泛使 用。,运算法则:,1.乘除的优先大于加减 2.同优先级的运算符左大于右 3.括号内的优先级大于括号外 于是：4+8-6/2*3 运算过程和结果唯一。,2)称为算符优先分析是因为这种方法是仿效算术式的四则运算 而建立起来的，作算术式的四则运算时，为了保证计算结果 和过程的唯一性，规定了一个统一的四则运算法则，规定运 算符之间的优先关系。,6.3.

6、1 直观算符优先文法,14,14,例:GE EE+E|E*E|(E)|i Vt=+,*,(,),i 这是一个二义文法，要用算符优先法分析有该文法所确定的 语言句子。如：i+i*i,(1)先确定终结符之间的优先关系,15,15,2)例中文法终结符之间的优先关系可以用一个矩阵M来表示,3)矩阵元素空白处表示这两个终结符不能相邻,故没有优先关系,16,16,步骤,符号栈,输入串,优先关系,动作,1,2,3,4,5,6,7,8,9,10,11,#,#i,#E,#E+,#E+i,#E+E,#E+E*,#E+E*i,#E+E*E,#E+E,#E,#,#,#,#,i#,*i#,*i#,i*i#,+i*i#,

7、+i*i#,i+i*i#,#i,i+,#+,+i,i*,+*,*i,i#,*#,+#,移进,移进,移进,移进,移进,规约,规约,规约,规约,规约,接受,EE+E|E*E|(E)|i,算法:当栈顶项(或次栈顶项)终结符的优先级大于栈外的终结符的优先级则进行规约，否则移进.,(2)分析过程 i+i*i,6.3.2 算符优先文法的定义,17,17,(1)算符优先文法(OPG)(2)构造优先关系矩阵(3)算符优先分析算法的设计,18,18,（1）算符优先文法（OPG）,算符文法（OG）的定义,优先关系的定义,若文法中无形如ABC的规则，这里B,CVN 则称G为OG文法，也就是算符文法。,若G是一OG文

8、法，a,bVT,A,B,CVN分别有以下三种情况:,G中不含的产生式,19,19,+,算符优先文法（OPG）的定义,设有一OG文法，如果在任意两个终结符之间，至多只有 上述关系中的一种，则称该文法为算符优先文法(OPG),21,21,对于OG算法的几点说明:,1)运算是以中缀形式出现的,3)算法语言中的表达式以及大部分语言成分的文法均是OG文法,2)可以证明，若文法为OG文法，则不会出现两个非终结符相邻的句型。,22,22,（2）构造优先关系矩阵,23,23,求“”:,.,若文法有规则 A.aB.，对任何b,bFIRSTVT(B)则有：a b,.,若文法有规则 A.Bb.，对任何a,aLAST

9、VT(B)则有：a b,.,例:文法GE E:=E+T|T T:=T*F|F F:=(E)|i 1、求每个非终结符号的FIRSTVT及LASTVT,FIRSTVT LASTVT,E+,*,(,i+.*,),i,T*,(,i*,),i,F(,i),i,2、求=关系：(=),3、求关系：+FIRSTVT(T),*FITSTVT(F),(FIRSTVT(E),4、求关系：LASTVT(E)+,LASTVT(T)*,LASTVT(E),构造优先关系表：,26,26,构造FIRSTBT(A)的算法,27,27,设一个栈S和一个二维布尔数组F,FA,b=TRAE iff bFIRSTVT(A)PROCED

10、BRE INSERT(A,b)IF NOT FA,b THEN BEGIN FA,b:=TRAE 把(A,b)推进S栈/*bFIRSTVT(A)*/END BEGIN main FOR 每个非终结符号A和终结符b DO FA,b:=FALSE/*赋值符*/FOR 每个形如A:=b或A:=Bb 的规则 DO INSERT(A,b),具体方法如下:,28,28,WHILE S栈非空 DO BEIGN 把S栈的顶项弹出,记为(B,b)/*bFIRSTVT(A)*/FOR 每条形如A:=B的规则 DO INSTER(A,b);/*bFIRSTVT(A)*/END OF WHILE END,上述算法的工

11、作结果是得到一个二维的布尔数组F,从F 可以得到任何非终结符号A的FIRSTVT FIRSTVT(A)=b|FA,b=TRAE,29,29,构造LASTBT(A)的算法,1.若有规则A:=a或A:=aB,则aLASTVT(A),2.若有规则A:=B,且aLASTVT(B)则aLASTVT(A),设一个栈ST,和一个布尔数组B PROCEDARE INSERT(A,a)IF NOT BA,a THEN BEGIN BA,a:=TRAE;把(A,a)推进ST栈;END;,30,30,BEGIN FOR 每个非终结符号A和终结符号a DO BA,a:=FALSE;FOR 每个形如A:=a或A:=aB

12、的规则 DO INSERT(A,a);WHILE ST栈非空 DO BEGIN 把ST栈的栈顶弹出,记为(B,a);FOR 每条形如A:=B的规则 DO INSERT(A,a);END OF WHILE;END;,31,31,构造优先关系矩阵的算法,32,32,（3）算符优先分析算法的实现.,先定义优先级，在分析过程中通过比较相邻运算符之间的优先级来确定句型的“句柄”并进行归约.,定义 素短语：文法G的句型的素短语是一个短语，它至少包含有一个终结符号，并且除它自身以外不再包含其他素短语.,最左素短语？,33,33,文法的语法树:,短语:T+T*F+i,T+T*F T(最左),T*F,i 其中T

13、不包含终结符,T是句型 而T+T*F+i和T+T*F包含其他 素短语.,只有T*F和i为素短语,其中T*F为最左素短语,而该句型句柄为T.,例:文法GE E:=E+T|T T:=T*F|F F:=(E)|i 求句型T+T*F+i 的素短语,34,34,于是算符优先分析法：如何确定当前句型的最左素短语？设有OPG文法句型为:#N1a1N2a2NnanNn+1#其中Ni为非终结符(可以为空),ai为终结符,定理：一个OPG句型的最左素短语是满足下列条件的 最左子串：aj-1NjajNiaiNi+1ai+1其中 aj-1 ai+1,.,.,.,35,35,根据该定理,要找句型的最左素短语就是要找满足

14、 上述条件的最左子串.,注意:出现在aj左端和a i右端的非终结符号一定属于这个素短语,因为我们的运算是中缀形式给出的(OPG文法的特点)NaNaNaN NaWaN,例:文法GE E:=E+T|T T:=T*F|F F:=(E)|i,分析文法的句型T+T*F+i,36,36,可以看出:1.每次规约最左子串,确实是当前句型的最左素短语(语法树）2.规约的不都是真句柄（仅i规约为F是句柄，但它是最左短语)3.没有完全按规则进行规约,因为素短语不一定是简单短语,37,37,算符优先分析法的实现：,详见讲义，基本部分是找句型的最左子串（最左素短语）并进行规约。,当栈内终结符的优先级栈外的终结符的优先级

15、时，移进；栈内终结符的优先级栈外的终结符的优先级时，移进。表明找到了素短语的尾，再往前找其头，并进行规约。,优先函数,为了节约存储空间和便于执行比较运算?，用两个优先函数f和g，它们是从终结符号映射到整数的函数。对于终结符号a和b选择f和g,使之满足：1.当a=b时,f(a)=g(b);2.当ab时,f(a)g(b);3.当ab时,f(a)g(b)。于是a和b之间的优先关系可以由比较f(a)与g(b)的大小来决定。,算法:从优先关系构造优先函数 方法：aVT#,建立两个符号fa和ga;若a=b,从fa至gb画一条弧；也从gb至fa画 一条弧a，b VT，若ab，则从fa至gb画一条弧；若ab，

16、则从gb至fa画一条弧;若图中无环，则存在优先函数，f(a)和g(b)等于从fa 和gb出发所能到达的结点个数（包括该结点自身）。,41,41,注意特点:(a)优先函数值不唯一(b)优点：节省内存空间 若文法有n个终结符，则关系矩阵为n2 而优先函数为2n 易于比较：算法上容易实现,数与数比,不必 查矩阵.(c)缺点：可能掩盖错误.,算符优先分析小结 优点 1.简单、效率高 2.能够处理部分二义性文法 缺点 1.文法书写限制大 2.占用内存空间大 3.不规范、存在查不到的语法错误,7.1.1 LR分析法的概述,43,43,(1)LR分析法的优缺点(2)LR分析器有三部分:状态栈、分析表、控制程

17、序(3)分析表的种类(4)补充说明,(1)LR分析法的优缺点:,1)适合文法类足够大,适用于所有上下文无关文法 2)分析效率高 3)报错及时 4)可以自动生成 5)手工实现工作量大,45,45,状态栈：放置分析 器状态和文法符号.,分析表：由两个矩阵组成，其功能是指示分析器的动作，是移进还是规约，根据不同的文法类要采用不同 的构造方法.,控制程序：执行分析表所规定的动作，对栈进行操作。,(2)LR分析器有三部分:状态栈、分析表、控制程序,46,46,(3)分析表的种类,a)SLR分析表(简单LR分析表),b)LR分析表(规范LR分析表),构造简单,最易实现,大多数上下文无关文法都 可以构造出S

18、LR分析表,所以具有较高的实用 价值。使用SLR分析表进行语法分析的分析器 叫SLR分析器,适用文法类最大,n个所有上下文无关文法都能 构造出LR分析表,但其分析表体积太大.暂时实 用价值不大.,47,47,c)LALR分析表(超前LR分析表),这种表适用的文法类及其实现上难易在上面 两种之间,在实用上很吸引人.使用LALR分析表进行语法分析的分析器叫LALR分析器。例：ANIX-YACC,文法规则文件 YACC源文件,YACC,某语言的 LALR分析器,48,48,1.三种分析表对应三类文法,(4)几点说明,2.一个SLR文法必定是LALR文法和LR文法,3.仅讨论SLR分析表的构造方法,7

19、.1.2 LR分析,（1）逻辑结构（2）LR分析过程,50,50,（1）逻辑结构,分析动作表,状态转移表,控制程序,输入串：#a1 a2.ai.an#,#S0 x1S1x2.xmSm,LR分析器,状态栈,51,51,状态栈:,S0,S1,Sm 状态 S0-初始状态 Sm-栈顶状态,栈顶状态概括了从分析开始到该状态的 全部分析历史和展望资料.,符号串:X1X2.Xm,为从开始状态(S0)到当前状态(Sm)所识别的规范句型的活前缀.,#S0 x1S1x2.xmSm,S0S1.Sm#x1x2.xm,52,52,规范句型：通过规范规约得到的句型.,规范句型前缀：将输入串的剩余部分与其连结起来就构成了规

20、范句型.如：x1x2.xmai.an为规范句型 x1x2.xm 为规范句型前缀 ai.an为输入串的剩余部分,活前缀：若分析过程能够保证栈中符号均是规范句型的前缀，则表示输入串已分析过的部分没有语法错误，所以称为规范句型的活前缀.,规范句型的活前缀:,对于句型t，表示句柄,如果=u1u2ur那么符号串u1u2ui(1ir)即是句型t的活前缀,例：有文法 ET|E+T|E-T Ti|(E)拓广文法G：SE#ET|E+T|E-T Ti|(E)已知句型E-(i)#，求活前缀?,E,E-,E-(,E-(i 是句型E-(i+i)#的活前缀。,53,54,54,分析表,是一个矩阵：行-分析器的状态 列-文

21、法符号,状态,符号,E,T,F,S0,S1,S2,:,Sn,GOTO表,a.状态转移表(GOTO表),55,55,GOTOSi-1,xi=Si Si-1-当前状态(栈顶状态)xi-新的栈顶符号 Si-新的栈顶状态(状态转移)Si需要满足条件是:若X1X2.Xi-1是由S0到Si-1所识别的规范句型的活前缀,则X1X2.Xi是由S0到Si所识别的规范句型的活前缀,#S0 x1S1x2.xi-1Si-1 xiSi,56,56,通过对有穷自动机的了解,我们可以看出:,状态转移函数GOTO是定义了一个以文法符号集为字母表的有穷自动机，该自动机识别文法所有规范句型的活前缀。,57,57,b.分析动作表(

22、ACTION表),ACTIONSi,a=动作分析 aBt,58,58,分析动作：,1)移进(shift)ACTIONSi,a=Sj 动作：将a推进栈，并设置新的栈顶状态Sj Sj=GOTOSi,a，将指针指向下一个输入符号,2)规约(reduce)ACTIONSi,a=rd d：文法规则编号(d)A 动作：将符号串(假定长度为n)连同状态从栈内弹出把A推进栈，并设置新的栈顶状态Sj,Sj=GOTOSi-n,A,3)接受(accept)ACTIONSi,#=accept,4)出错(error)ACTIONSi,a=error,59,59,控制程序:(Driver Routine),1)根据栈顶状

23、态和现行输入符号，查分析动作表(ACTION表)，执行有分析表所规定的操作；2)并根据GOTO表设置新的栈顶状态(即实现状态转移),60,60,例：文法GE(1)E:=E+T(2)E:=T(3)T:=T*F(4)T:=F(5)F:=(E)(6)F:=i,（2）LR分析过程,该文法是SLR文法,故可以构造出SLR分析表(ACTION表和GOTO表),ACTION表 GOTO表,文法GE：(1)E:=E+T(2)E:=T(3)T:=T*F(4)T:=F(5)F:=(E)(6)F:=i,62,62,11(S11),10(S10),7,9(S9),11,6,8(S8),4,5,10,7(S7),4,5

24、,3,9,6(S6),5(S5),4,5,3,2,8,4(S4),3(S3),7,2(S2),6,1(S1),4,5,3,2,1,0(S0),),(,*,+,i,F,T,E,GOTO表 ACTION表,文法符号,状态,状态,若移入：i为状态若规约：i为产生式编号,文法GE：(1)E:=E+T(2)E:=T(3)T:=T*F(4)T:=F(5)F:=(E)(6)F:=i,Bn,Bt,63,63,ACTION 表,GOTO 表,输入符号,状态,文法GE(1)E:=E+T(2)E:=T(3)T:=T*F(4)T:=F(5)F:=(E)(6)F:=i,Si：移入，i为状态Ri：规约，i为产生式编号,6

25、4,64,分析过程：i*i+i,步骤状态栈符号输入串动作,10i*i+i#初始化,20i5i*i+i#S,30F3F*i+i#R6,40T2T*i+i#R4,50T2*7T*i+i#S,60T2*7i5T*i+i#S,70T2*7F10T*F+i#R6,GOTO表 ACTION表,110E1+6i5#E+i#S,120E1+6F3#E+F#R6,130E1+6T9#E+T#R4,140E1#E#R1,15#E Accept,90E1#E+i#R2,100E1+6#E+i#S,80T2#T+i#R3,GOTO表 ACTION表,66,66,由分析过程可以看到:,(1)每次规约总是规约当前句型的句

26、柄，是规范规约，可以看到语法树(算符优先是规约最左素短语),(2)分析的每一步栈内符号串均是规范句型的活前缀，与输入串的剩余部分构成规范句型.,7.1.3 构造SLR分析表,67,67,构造LR分析器的关键时构造其分析表,构造LR分析表的方法是:（1）根据文法构造识别规范句型活前缀的有穷自动机DFA（2）由DFA构造SLR分析表,68,1.构造DFA,(1)DFA是一个五元式,M=(S,B,GOTO,S0,Z),S：有穷状态集,在此具体情况下，S=LR(0)项目集规范族LR(0)。项目集规范族：其元素是由项目所构成的集合.,B：文法字汇表,S0：初始状态,GOTO:状态转移函数 GOTOSi,

27、X=Sj Si,SjS Si,Sj为项目集合 XBnBt表示当前状态Si面临文法符号为X时，应将状态转移到 Sj,Z：终态集合 Z=S-S0 即除S0以外，其余全部是终态,69,69,1）确定S集合，即LR（0）项目集规范族，同时确定S0,2）确定状态转移函数GOTO,构造DFA方法：,70,70,（2）构造LR（0）的方法,LR(0)是DFA的状态集，其中每个状态又都是项目的集合,项目:文法G的每个产生式(规则)的右部添加一个圆点就构成一个项目。,例:产生式:AXYZ 项 目:A.XYZ AX.YZ AXY.Z AXYZ.产生式:A 项 目:A.,项目的直观意义:指明在分过程中的某一时刻已经

28、规约的部分和等待规约部分。,71,71,.将文法扩充,构造LR(0)文法的方法(三步),目的：使构造出来的分析表只有一个接受状态,这是 为了实现的方便。,方法：修改文法，使识别符号的规则只有一条,L(G(E)=L(GE),72,72,.根据文法列出所有的项目,.将有关项目组合成集合，即DFA中的状态；所有状态再组合成一个集合，即LR（0）项目集规范族,我们通过一个具体例子来说明LR(0)的构造以及DFA 的构造方法,例：GE EE+T|T TT*F|F F(E)|i,73,73,例:GE EE+T|T TT*F|F F(E)|i,(0)EE(4)TF EE+T(5)F(E)ET(6)Fi TT

29、*F,74,74,为实现这一步，先定义：项目集闭包closure 状态转移函数GOTO,例:GE 令I=E.E closure(I)=E.E,E.E+T,E.T,T.T*F,T.F,F.(E),F.i,75,75,A.项目集闭包closure的定义和计算:令I是文法G的任一项目集合，定义closure(I)为项目集合I的闭包，可用一个过程来定义并计算closure(I)。Procedure closure(I);begin 将属于I的项目加入closure(I);repeat for closure(I)中的每个项目A.B(BBn)do 将B.r(rB*)加入closure(I)until c

30、losure(I)不再增大 end,例:GE 令I=E.E closure(I)=E.E,E.E+T,E.T,T.T*F,T.F,F.(E),F.i,76,76,所以,GOTO(I,X)=closure(J)的直观意义是:它规定了识别文法规范句型活前缀的DFA从状态I(项目集)出发,经过X弧所应该到达的状态(项目集合),77,77,例.I=EE.,EE.+T 求GOTO(I,+)=?GOTO(I,+)=closure(J)J=EE+.T GOTO(I,+)=EE+.T,T.T*F,T.F,F.(E),F.i,78,78,LR(0)项目集规范族的构造算法:,GLR(0)Procedure ITE

31、MSETS(G);begin LR(0):=closure(E.E);repeat for LR(0)中的每个项目集I和G的每个符号X do if GOTO(I,X)非空,且不属于LR(0)then 把GOTO(I,X)放入LR(0)中 until LR(0)不再增大 end,79,79,例.求GE的LR(0)B=E,T,F,I,+,*,(,),(0)EE(4)TF EE+T(5)F(E)ET(6)Fi TT*F,80,80,I2:ET.GOTO(I0,T)=closure(ET.TT.*F)=I2 TT.*F I3:TF.GOTO(I0,F)=closure(TF.)=I3I4:F(.E)G

32、OTO(I0,()=closure(F(.E)=I4 E.E+T E.T T.T*F T.F F.(E)F.i I5:Fi.GOTO(I0,i)=closure(Fi.)=I5 GOTO(I0,*)=GOTO(I0,+)=GOTO(I0,)=,I0:E.E E.E+T E.T T.T*F T.F F.(E)F.i,81,81,I6:EE+.T GOTO(I1,+)=closure(EE+.T)=I6T.T*F GOTO(I1,其他符号)为空 T.F F.(E)F.i I7:TT*.F GOTO(I2,*)=closure(TT*.F)=I7F.(E)GOTO(I2,其他符号)为空 F.i GO

33、TO(I3,其他符号)为空,I1:EE.EE.+T,I2:ET.TT.*F,82,82,I4:F(.E)E.E+T E.T T.T*F T.F F.(E)F.i,83,83,I10:TT*F.GOTO(I7,T)=closure(TT*F.)=I10 GOTO(I7,()=I4 GOTO(I7,i)=I5I11:F(E).GOTO(I8,)=closure(F(E).)=I11 GOTO(I7,()=I4 GOTO(I7,i)=I5求完所有Ii的后继GOTO(I8,+)=I6GOTO(I9,*)=I7 GOTO(I10,所有符号)=,GOTO(I11,所有符号)=,84,84,（3）构造DFA

34、,M=(S,B,GOTO,S0,Z)S=I0,I1,I2,I11=LR(0)B=+,*,i,(,),E,T,F GOTO(Im,X)=Im S0=I0Z=S-I0=I1,I2,I11,M的图解表示如下:,85,85,I0,I5,I2,I4,I3,I1,I11,I8,I6,I10,I7,I9,start,E,+,+,i,F,(,T,T,F,(,i,F,(,i,E,(,*,*,),+,i,F,86,86,关于自动机的说明:,1,除I0以外,其余状态都是活前缀的识别状态,从I0到每一状态的每条路径都识别和接受一个规范句型的活前缀,如对文法句子i+i*i 进行规范规约，所得到的规范句型的活前缀都可 以

35、由该自动机识别,如:I0I3 F(+i*i)I0I2 T(+i*i)I0I1 识别规范句型的活前缀E(+i*i)I0I6 识别规范句型的活前缀E+(i*i)I0I7 识别规范句型的活前缀E+T*(i)I0I9 识别规范句型的活前缀E+T(*i)I0I10 识别规范句型的活前缀E+T*F,E,E,T,+,T,8,5,4,3,2,1,(0)EE(3)TT*F(6)Fi EE+T(4)TF ET(5)F(E),6,87,87,注意：项目中圆点前的符号串成为活前缀的后缀,*,88,88,注意：经移进或规约后,在栈内仍是规范句型的活前缀,89,89,4,DFA中的状态,既代表了分析历史又提供了展望信息,

36、每条规范句型的活前缀都代表了一个确定的 的规范规约过程,故有状态可以代表分析历史.,由于状态中的项目都是有效项目,所以提供了 下一步可能采取的动作.,历史+展望+实现 句柄,90,90,（2）由DFA构造SLR分析表,*GOTO表在求LR（0）时已求出,91,91,设k为状态编号,E为原文法识别符号，E为扩充文法识别符号,*求ACTION表,1、求出文法每个非终结符的FOLLOW集合,2、若项目Ap.aq k,且a Bt,则置 ACTIONk,a=S(移进）,92,92,3、若项目Ap.k,那么对输入符号a,若 aFOLLOW(A),则置ACTIONk,a=rj 其中Ap为文法G的第j个产生式

37、。,4、若项目EE.k,则置 ACTION k,#=ACCEPT,5、ACTION表中不能用步骤24填入信息的 空白格，均置ERROR,93,93,在状态中可有三种类型的项目,其中只有两种有移 进或规约动作:,A.a aBt 移进项目 分析动作:移进 A.规约项目 分析动作:规约 A.B BBn 待约项目 无动作,根据上述算法,可以构造出文法GE的ACTION,94,94,对文法GE,k=2(I2)有效项目 ET.TT.*F FOLLOW(E)=#,+,),k=1(I1)EE.EE.+T FOLLOW(E)=#,k=0(I0)E.E E.E+T E.T T.T*F T.F F.(E)F.i,根

38、据算法造出的ACTION表为:,95,95,96,96,两点说明:,由DFA构造出的SLR分析表,在造表示,我们 只需向前看一个符号就能确定分析的动作是移 进还是规约.所以SLR(1)分析表简称SLR分析表 使用SLR分析表的分析器叫SLR分析器.对文法G,若使用上述算法,所造出的分析表 具有多重定义入口,分析动作就不唯一,则文法 G就不是SLR的需要用别的方法来构造分析表.,第五章 语法分析小结,97,97,语法分析方法:,SLZ,(一)自顶向下分析,98,98,1.构造First集合的算法 2.构造Follow集合的算法 3.构造分析表的算法,99,99,(二)自底向上分析,规约过程:,(

39、1)一般过程:移进规约过程,(2)算法:,问题:如何寻找句柄,i)算符优先分析法:,1.分析器的构造,分析过程.根据算符优先关系矩阵来决定 是移进还是规约.,100,100,2.算符优先法的进一步讨论,1.适用的文法类-引出的算符优先法的定义 2.优先关系矩阵地构造 3.什么是“句柄”,如何找 有句柄引出的最左素短语的概念.最左素短语的定理,如何找.,ii)LR分析法,1.概述-概念、术语(活前缀、项目),101,101,2.LR分析,1)逻辑结构,2)分析过程,状态栈,分析表,控制程序,GOTO表,分析动作表,3.如何构造SLR分析表,1)构造DFA,2)由DFA构造分析表,102,102,除了递归子程序法，其他几种方法逻辑结构很象：,(1)对于LL(1)分析法,符号栈,(自顶向下，保证最左推导),LL(1)分析表,首字符,103,103,(2)对于算法优先分析:,符号栈,(3)LR分析:,104,104,GOTO表,根据栈顶状态和栈 顶符号推导出下一 状态,分析动作表,根据栈顶状态和输入 符号推导出下一动作,105,105,将GOTO表和分析动作表压缩后得:,