new第四章语法分析.ppt

编译原理CompilerPrinciples,蒋凌云南京邮电大学.计算机学院,第四章语法分析,教材：编译技术原理及其实现方法王汝传编著,第四章语法分析,本章内容,4.1引言一、语法分析任务二、语法分析方法4.2自顶向下语法分析一、自顶向下分析方法的问题及其解决办法二、递归子程序分析法（递归下降分析法）三、LL（1）分析法4.3自底向上语法分析一、简单优先文法分析法二、算符优先分析法三、优先函数及其构造四、LR分析法五、二义性文法的应用4.4语法分析程序的自动生成一、分析器的生成器YACC二、用YACC处理二义性文法,一、简单优先文法分析法三、优先函数及其构造1.与文法有关的一些关系定义1.优先函数定义2.构造文法关系传递闭包2.优先函数矩阵的构造和自反传递闭包3.利用优先函数矩阵进行语法分析3.文法优先关系概念四、LR分析法4.文法优先关系的构造1.LR分析法一般概述5.简单优先文法2.LR分析器工作原理6.简单优先文法分析算法3.LR（0）分析表构造二、算符优先分析法4.SLR（1）分析表构造1.算符优先关系概念5.LR（1）分析表构造2.算符优先文法6.LALR分析表构造3.算符优先关系的构造方法五、二义性文法的应用4.最左素短语1.问题的提出5.算符优先分析算法2.二义性文法分析表的构造,第四章语法分析,4.3自底向上语法分析,一、简单优先文法分析法三、优先函数及其构造1.与文法有关的一些关系定义1.优先函数定义2.构造文法关系传递闭包2.优先函数矩阵的构造和自反传递闭包3.利用优先函数矩阵进行语法分析3.文法优先关系概念四、LR分析法4.文法优先关系的构造1.LR分析法一般概述5.简单优先文法2.LR分析器工作原理6.简单优先文法分析算法3.LR（0）分析表构造二、算符优先分析法4.SLR（1）分析表构造1.算符优先关系概念5.LR（1）分析表构造2.算符优先文法6.LALR分析表构造3.算符优先关系的构造方法五、二义性文法的应用4.最左素短语1.问题的提出5.算符优先分析算法2.二义性文法分析表的构造,第四章语法分析,4.3自底向上语法分析,一、简单优先文法分析法三、优先函数及其构造1.与文法有关的一些关系定义1.优先函数定义2.构造文法关系传递闭包2.优先函数矩阵的构造和自反传递闭包3.利用优先函数矩阵进行语法分析3.文法优先关系概念四、LR分析法4.文法优先关系的构造1.LR分析法一般概述5.简单优先文法2.LR分析器工作原理6.简单优先文法分析算法3.LR（0）分析表构造二、算符优先分析法4.SLR（1）分析表构造1.算符优先关系概念5.LR（1）分析表构造2.算符优先文法6.LALR分析表构造3.算符优先关系的构造方法五、二义性文法的应用4.最左素短语1.问题的提出5.算符优先分析算法2.二义性文法分析表的构造,第四章语法分析,4.3自底向上语法分析,4.3自底向上语法分析,前面我们介绍的几种语法分析方法对相应的文法都有一定的要求。例如：因此，上述这些方法在使用上有一定局限性。LR分析法是1965年由Knuth提出一种自底向上语法分析方法，可用于一大类上下文无关文法分析，这种技术叫做LR(K)分析技术。,不带回溯的自顶向下分析方法要求文法不存在左递归，并且每一规则的各候选式的终结首符集两两不相交；算符优先分析方法则要求文法的各终结符号对间至多只有一种优先关系，等等。,1.LR分析法一般概述,4.3自底向上语法分析,（1）LR（K）分析法定义,LR(K)分析法意思是：L是指从左(Left)到右扫描输入符号串，R是构造最右(Rightmost)推导过程自底向上的分析方法。K是指在决定分析动作时向前看符号的个数。若K0，就为LR(0)分析，说明分析动作时，不向前看任何符号，LR(1)分析，说明分析动作时只向前看一个符号。这是一类对上下文无关文法进行“自左到右扫描和最左归约”的自底向上的分析方法，在这种分析过程中，它至多只向前查看个输入符号就能确定当前的动作是移进还是归约；若动作归约，它还能唯一地选中一个规则去归约当前已识别的句柄。,4.3自底向上语法分析,（2）LR分析法的特点,1)LR分析器(程序)基本上可以识别所有上下文无关文法写的编程语言结构，分析能力强且适用范围广2)LR分析法是当前最一般的“移进-归约”分析方法3)LR分析法在自左向右扫描输入串时能发现其中错误，并能指出出错地点。4)LR分析程序可以自动生成,4.3自底向上语法分析,（3）LR分析器的组成,从逻辑上说，一个LR分析器包括两部分：一个总控程序和一张分析表。一般说来，所有LR分析器总控程序是一样的，只是分析表各不相同。,4.3自底向上语法分析,（4）LR分析表种类,1)最简单分析表LR(0)：局限性大，但它是建立其它分析表的基础2)简单分析表SLR：比较容易实现，SLR分析表的功能比LR(0)稍强些3)LR(K)分析表：分析能力最强，但实现代价高。主要讨论LR(1)4)LALR分析表：称为向前看LR分析表，功能介于SLR(1)和LR(1)之间，适用于大多数程序设计语言的结构，并且可以比较有效地实现。,一、简单优先文法分析法三、优先函数及其构造1.与文法有关的一些关系定义1.优先函数定义2.构造文法关系传递闭包2.优先函数矩阵的构造和自反传递闭包3.利用优先函数矩阵进行语法分析3.文法优先关系概念四、LR分析法4.文法优先关系的构造1.LR分析法一般概述5.简单优先文法2.LR分析器工作原理6.简单优先文法分析算法3.LR（0）分析表构造二、算符优先分析法4.SLR（1）分析表构造1.算符优先关系概念5.LR（1）分析表构造2.算符优先文法6.LALR分析表构造3.算符优先关系的构造方法五、二义性文法的应用4.最左素短语1.问题的提出5.算符优先分析算法2.二义性文法分析表的构造,第四章语法分析,4.3自底向上语法分析,4.3自底向上语法分析,Sm.S1S0,总控程序,分析表,Sm.S2S1S0,Xm.X2X1#,(1)LR分析器的逻辑结构在逻辑上，一个LR分析器结构如下图所示。它是由一个输入符号串，一个下推状态栈，以及一个总控程序和分析表组成。实际上在分析时读入符号是不进栈的。为使分析解释更清楚，我们另设一个符号栈（实际上只有一个状态栈用于存放状态）。,状态栈,状态栈,符号栈,输入串,2.LR分析器工作原理,LR分析器核心是分析表，分析表由两个子表组成：1)分析动作表其中：S，S2，Sn为分析器各状态a,a2am为文法的全部终结符号和句子界限符ACTIONSi,aj指明，当状态Si面临输入符号aj时应采取的分析动作。有如下四个取值：ACTIONSi,aj=S移进动作，当前输入符号进桟ACTIONSi,aj=rj按第j个产生式进行归约ACTIONSi,aj=acc接受ACTIONSi,aj=ERROR出错,2）状态转换表其中：，p是文法字汇表中全部非终结符号和终结符号S，S，Sn为分析器各状态GOTOSi,Xj指明当状态Si面对文法符号Xj时下一状态是什么,（2）LR分析器基本工作过程1）分析实例下面我们通过一个例子来说明LR分析器分析过程例4.15设已知文法GE：(首先对每个文法规则要编号）=E+T=T*=（E）=i为了节省空间，我们将文法分析动作表（ACTION）和状态转换表（GOTO）关于终结符的各列对应地进行合并，合并之后分析表如下表所示。（关于表的构造方法以后再讨论）,2.LR分析器工作原理,实例LR分析表,表中所引用记号的意义是：a.Sj把下一个状态j和现行输入符号ai移进栈b.rj按第j个规则进行归约c.acc接受d.空白格出错标志，报错GOTO表仅对所有非终结符A列出GOTOSm,A的值，表明所要到达的状态的值。,实例分析过程现以输入串为i+i*i为例，给出分析器对它进行分析过程如下表,步骤状态栈符号栈输入串分析动作下一状态10#i+i*i#S55205#i+i*i#r6GOTO0,F=3303#F+i*i#r4GOTO0,T=2402#T+i*i#r2GOTO0,E=1501#E+i*i#S666016#E+i*i#S5570165#E+i*i#r6GOTO6,F=380163#E+F*i#r4GOTO6,T=990169#E+T*i#S771001657#E+T*i#S5511016575#E+T*i#r6GOTO7,F=10120165710#E+T*F#r3GOTO6,T=9130169#E+T#r1GOTO0,E=11401#E#acc,2）LR分析器基本工作过程LR分析器的工作是在总控程序控制下进行，其过程如下：分析开始时，首先将初始状态S及句子左界限符#推入分析栈和输入串构成一个三元式为（S，#，a1a2an#）其中S为初态，#为句子左界限符，a1a2an是输入串，其后#为句子右界限符。设在分析的某一步，分析栈和余留输入符号串表示为（S0S1Sm，#X1X2Xm，aiai+1an#）这时用当前栈顶状态Sm及正扫视的输入符号ai组成符号对去查分析动作表，并根据分析表中元素ACTIONSm,ai所规定的动作进行分析。,2.LR分析器工作原理,a.若ACTIONSm，ai移进S，这表明句柄尚未在栈顶部形成，正期待着移进输入符号以形成句柄，故将当前输入符号ai推入栈中，其三元式变为（S0S1Sm,#X1X2Xmai,ai+1ai+2an#）然后以符号对（Sm，ai）查状态转换表，若相应表元素为GOTOSm,aiSm+1再将此新状态Sm+1推入栈中，则三元式变为（S0S1SmSm,#X1X2Xmai,ai+1ai+2an#）,分析动作表每一元素ACTIONSm,ai所规定动作不外是下列四种可能之一：,2.LR分析器工作原理,b.若ACTIONSm，ai归约rj，其中rj是指文法中第j个规则，r是规则右部长度。此时按规则执行一次归约动作，这表明栈顶部的符号串m-r+1m-r+2m已是当前句型（对非终结符）的句柄。按第j个产生式进行归约，此时将分析栈从顶向下的r个符号退出，使状态Sm-r变成栈顶状态，再将文法符号推入栈中，其三元式为（S0S1Sm-r,#X1X2Xm-r,aiai+1an#）然后再以（Sm-r，）查状态转换表，设GOTOSm-r，Sk，将此新状态推入栈中则三元式变为（S0S1Sm-rSk,#X1X2Xm-RA,aiai+1an#）归约动作不改变现行输入符号，输入串指示器不向前推进，它仍然指向动作前的位置。,2.LR分析器工作原理,c.若ACTIONSm,ai接受acc，则表明当前输入串已被成功地分析完毕，则三元式不再变化，宣布分析成功。d.若ACTIONSm,ai报错ERROR，则三元式变化过程终止，报告错误。重复上述，直到在分析某一步，栈顶出现“接受状态”或“出错状态”为止。对于前者，其三元式变为（SSz，）其中为文法开始符号，Sz则为使ACTIONSz，“接受”的唯一状态。一个分析器工作过程就是一步一步地变换三元式，直至执行“接受”或“报错”为止。,2.LR分析器工作原理,实例分析过程现以输入串为i+i*i为例，给出分析器对它进行分析过程如下表,步骤状态栈符号栈输入串分析动作下一状态10#i+i*i#S55205#i+i*i#r6GOTO0,F=3303#F+i*i#r4GOTO0,T=2402#T+i*i#r2GOTO0,E=1501#E+i*i#S666016#E+i*i#S5570165#E+i*i#r6GOTO6,F=380163#E+F*i#r4GOTO6,T=990169#E+T*i#S771001657#E+T*i#S5511016575#E+T*i#r6GOTO7,F=10120165710#E+T*F#r3GOTO6,T=9130169#E+T#r1GOTO0,E=11401#E#acc,一、简单优先文法分析法三、优先函数及其构造1.与文法有关的一些关系定义1.优先函数定义2.构造文法关系传递闭包2.优先函数矩阵的构造和自反传递闭包3.利用优先函数矩阵进行语法分析3.文法优先关系概念四、LR分析法4.文法优先关系的构造1.LR分析法一般概述5.简单优先文法2.LR分析器工作原理6.简单优先文法分析算法3.LR（0）分析表构造二、算符优先分析法4.SLR（1）分析表构造1.算符优先关系概念5.LR（1）分析表构造2.算符优先文法6.LALR分析表构造3.算符优先关系的构造方法五、二义性文法的应用4.最左素短语1.问题的提出5.算符优先分析算法2.二义性文法分析表的构造,第四章语法分析,4.3自底向上语法分析,4.3自底向上语法分析LR（0）分析就是LR（K）分析当的情况，就是指在分析每一步，只要根据当前栈顶状态，就能确定应采取何种分析动作，而无需向前查看输入符号。为了构造LR分析表，首先引入规范句型活前缀的概念。（1）规范句型的活前缀字的前缀：是指字的任意首部。如字abc的前缀有,a,ab,abc.活前缀：规范句型（右句型）的一个前缀，如果它不含句柄后任何符号，则称它是该规范句型的一个活前缀。也就是说在活前缀右边增添一些终结符号之后，就可以成为规范句型。,在LR分析过程中的任何时候，栈里的文法符号X1X2Xm应该构成活前缀，把输入串的剩余部分配上之后即成为规范句型（如果整个输入串确实构成一个句子的话。）,如：S+abcdef,其中cd是句柄，则,a,ab,abc,abcd是该规范句型的活前缀，而abcd是包含句柄的活前缀。,3.LR(0)分析表的构造,实例分析过程现以输入串为i+i*i为例，给出分析器对它进行分析过程如下表,步骤状态栈符号栈输入串分析动作下一状态10#i+i*i#S55205#i+i*i#r6GOTO0,F=3303#F+i*i#r4GOTO0,T=2402#T+i*i#r2GOTO0,E=1501#E+i*i#S666016#E+i*i#S5570165#E+i*i#r6GOTO6,F=380163#E+F*i#r4GOTO6,T=990169#E+T*i#S771001657#E+T*i#S5511016575#E+T*i#r6GOTO7,F=10120165710#E+T*F#r3GOTO6,T=9130169#E+T#r1GOTO0,E=11401#E#acc,（2）LR（）项目1)活前缀与句柄之间的关系作为规范句型的活前缀不含有句柄后任何符号。因此，前缀与句柄的关系可能有三种情况：,活前缀已包含句柄全部符号，这表明规则的右部符号串已在分析栈顶，因此相应的分析动作应是用此规则进行归约，称可归约的活前缀。我们用表示,3.LR(0)分析表的构造,4.3自底向上语法分析,活前缀中只含句柄一部分符号，意味着形如规则12的右部子串1已出现在栈顶，正期待着从余留输入串中看到能由推出的符号串。我们用表示活前缀不包含句柄的任何符号，这表明规则的右部符号串不在分析栈顶，正期待从余留输入串中由规则的所能推出的符号串。我们用表示,3.LR(0)分析表的构造,4.3自底向上语法分析,2)LR（0）项目我们把右部某位置上标有圆点的规则称为相应文法的一个LR（0）项目。特别地，对形如的规则，相应（）项目为。例如，一个（）项目12一个（）项目一个（）项目若一个（）项目例如一个规则=aBC，根据圆点的位置不同可以有四个LR（）项目：aBC正期待着从余留输入串中由aBC推出的符号串进栈aBCa已进栈，正期待着从余留输入串中由BC推出的符号串进栈aBCaB推出的符号串进栈,正期待着从余留输入串中由C推出的符号串进栈aBCaBC推出的符号串进栈对于规则对应项目数为个。（表示所含字符的个数）显然，不同的（）项目反映了分析过程中栈顶的不同情况。,3.LR(0)分析表的构造,(3)构造识别活前缀的有穷自动机(FA)MKnuth证明了一个LR文法的右句型的所有活前缀能够为有穷自动机所接受我们可以把文法G中每一个项目作为非确定有穷自动机的一个状态，构造NFA，然后再将其确定化为DFA。1)文法G的全部项目例4.16设有文法GE=(E,A,B,a,b,c,d,P,E)，其中P由下列规则组成:E=aAA=dE=bBB=cBA=cAB=d,3.LR(0)分析表的构造,S=EE=aAA=dE=bBB=cBA=cAB=d将文法拓广的目的是使文法只有一个开始符作为左部规则，这样构造出来的分析器有唯一接受项目。否则E=aA和E=bB就有两个归约项目。,0,为了方便起见，我们在上述文法中引入一个新的开始符号S，并将S=E作为第0个规则，从而得到所谓G的拓广文法G，显然，L(G)=L(G)。,3.LR(0)分析表的构造,对于文法G,其LR(0)项目有S=EA=cAE=bBS=EA=cAB=cBE=aAA=dB=cBE=aAA=dB=cBE=aAE=bBB=dA=cAE=bBB=d,说明：(1)可用一个整数对n,m来表示一个LR(0)项目，其中第一个整数n用指明产生式的编号，第二个整数m则用来指明圆点所处的位置。例如，项目(1)可表示为0,0，项目(7)表示3,1等等。,3.LR(0)分析表的构造,(2)我们可根据它们不同作用,将一个文法全部LR(0)项目进行分三类。a）对于形如A=项目,因为它表明右部符号串已出现在栈顶,此时相应分析动作应按规则进行归约,称此种项目为归约项目。上例中的项目(2),(5),(8),(10),(13),(16),(18)都是归约项目。对于项目显然仅用于分析过程中最后一次归约,它表明整个分析过程已成功地完成,是一个特殊的归约项目,称接受项目。b）对于形如A=a,其中1可以是,a是终结符,相应分析动作应将当前输入符号移入栈中,故称此项目为移进项目。上例中项目(3),(6),(9),(11),(14),(17)都是移进项目.c）对于形如A=1B，其中1可以是,B是非终结符,由于我们期待着从余留输入符号串中进行归约而得到B,称此类项目为待约项目。上例中的(1),(4),(7),(12),(15)都是待约项目。,3.LR(0)分析表的构造,2)构造识别活前缀的NFA上述文法共有18个LR（0）项目，所以可以构造一个具有18个状态的NFA。并规定项目（1）为初始状态。NFA构造方法如下；如果状态i和j出自同一规则，而且状态j的圆点只落后于状态i的圆点一个位置，如状态i(i为一个项）i-1ii+1m而状态j(j为为一个项）i-1ii+1m则从状态i出发，画一条标记为i的弧到状态j,i,j,i,1,2,E,3,4,a,例如：,对于文法G,其LR(0)项目有S=EA=cAE=bBS=EA=cAB=cBE=aAA=dB=cBE=aAA=dB=cBE=aAE=bBB=dA=cAE=bBB=d,如果状态i圆点之后那个符号i为非终结符，那么从状态i画弧到所有形如i的项目（状态）例如状态圆点之后那个符号是E，为非终结符，那么从状态画弧到所有形如E的项目（状态）,即状态(E=aA)和状态(E=bB),i,i,1,2,3,11,E,任何其它状态是NFA终态，凡是属于归约项目的状态是特殊的终态，即可识别可归约活前缀。根据上述方法很容易构造出-NFA状态转换图，图中状态是唯一的初态，其他17个状态都是终态。画双圆圈者是可归约状态，可指向句柄识别状态，即可归约活前缀,1,2,3,11,12,13,14,15,16,17,18,4,5,9,10,8,7,6,E,b,B,d,B,A,a,c,A,d,显然，NFA可以识别文法G的活前缀：从的开始状态出发，沿着弧所指示的方向前进，当到达某一双圆圈状态时，把所经历的全部弧上的标记依次连成一符号串，此字符串就是某规范句型的一个可归约活前缀，若到达其他任一状态所得符号串就是规范句型活前缀。如可归约活前缀bcB，规范句型活前缀bc.,例如活前缀bcB其符号串bcB是可归约活前缀，因为B=cB，可将cB归约成B,即cB是句柄所以bcB是可归约活前缀。而bc是活前缀所以bc是一个活前缀，但不是可归约活前缀，因为不包括所有句柄符号，从上面例子可以看出，NFA是可以识别文法G的活前缀,1,11,12,14,15,16,b,c,B,1,11,12,14,15,b,c,3)将NFA确定化为DFA我们采用子集法，消去，将NFA确定化使其变成DFA，按照子集法：,然后我们对每一个集合(状态集合)作为DFA一个状态，如：I0,I1,I2,这样，就可以画出DFA状态转换图，其转换图的每一个状态都是以项目集合来表示，如I0S=E,E=aA,E=bB,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,B,I7:EbB,A,I8:AcA,B,I9:BcB,I10:Ad,d,d,I11:Bd,d,d,4)DFA中状态及转换函数与文法项目之间的关系我们分析关系目的是直接由文法项目构造DFA，因为分析表就是由DFA直接造出的。DFA状态与文法项目的关系由DFA状态图可以看出：DFA的每一状态都是一个项目子集。首先来看一下状态I0中包含的各个项目是如何确定的。I0S=E,E=aA,E=bB,规定S=E是属于I0的一个项目，而E又是非终结符，E的规则为：E=aA|bB，所以状态I0还包含E=aA和E=bB。由此即得状态I0的项目子集S=E，E=aA，E=bB,3.LR(0)分析表的构造,结论：若NFA的某一状态的相应项目为B2，而是非终结符号，如果有形如规则,其相应项目均为项目子集中一个项目，如果新获得圆点之后的符号又为非终结符号，则又将派生出新的项目，如此继续下去，直到全部新获得项目的圆点之后的符号为终结符号或圆点之后无符号为止。这时，所有获得新项目连同原有项目构成一个项目子集，作为DFA一个状态。(如：状态I0),3.LR(0)分析表的构造,4.3自底向上语法分析,实际上，我们将项目S称为项目集I0的基本项目，上述从项目S出发构造项目集I0的过程可用一个对其基本项目集S的闭包运算，即CLOSURE（S）来表示，一般地，设为一项目集，则构造的闭包CLOSURE（I）的方法如下：,a.中每一项目都属于S（）；b.若形如B2的项目属于S（），那么，对于任何有关B的规则，项目也属于CLOSURE（Ic.重复执行上述两步骤，直至CLOSURE（I）不再增大为止。显然，CLOSURE（S）S=E,aA，bB，这就是图中初态I0。,3.LR(0)分析表的构造,4.3自底向上语法分析,DFA转换函数与文法项目的关系（即从一个状态到另一个状态弧上标记）分析DFA状态图：状态I0中有项目S=E，所以可以由状态I0画一标记为E的弧指向下一状态I1，I1包含项目S=E，圆点向后移一位。由此得结论：设为一个文法符号（终结符或非终结符）,若i中有圆点位于左边的项目（其中可以是）,则可从i出发画一条弧，标记为X，而到下一状态；设此状态为j，其项目为J，显然是新状态集j中一个基本的项目，因此，按照上面构造项目集I0相类似方法，我们就有jS（）例如:I0中有项目S=E，(其中和2是),从I0出发画一条弧，标记为E，而到下一状态I1，圆点向后移一位，则I1中有基本项目JS=E。由于项目S=E，圆点后无符号，所以I1S=E同样I0中有项目E=aA，(其中是)，从I0出发画一条弧标记为a，而到下一状态I2，圆点向后移一位,则I2中有基本项目JE=aAIjI2S（）S（E=aA）则构造的闭包CLOSURE（I）的方法，可求得I2E=aA,A=cA,A=d,3.LR(0)分析表的构造,为了指明状态j和状态i之间这种转换关系，我们定义一个状态转换函数（i，）S（）其中，i为当前状态，为文法符号，而任何形如的项目属于jJ是基本项目集例如：I0中有项目E=bBI3GO(I0,b)S（）,JE=bB而文法有规则B=cB和B=d所以I3E=bB,B=cB,B=d,3.LR(0)分析表的构造,4.3自底向上语法分析,(4)由文法LR(0)项目直接构造DFA上面我们分析了DFA中状态和文法项目之间关系，DFA中转换函数和文法项目之间关系，我们由文法构造DFA时，就不必要先构造NFA，然后再用子集法来构造DFA，我们可以直接由文法来构造DFA了。1)将一般文法G改写成拓广文法G如果S是文法G的开始符号，则拓广文法G中增加一个规则S=S，S是文法G开始符号，显然L(G)L(G)这样就使得拓广文法G中有项目S=S是唯一接受项目例如上面我们举的例子中的拓广文法G为：S=EE=aAA=dE=bBB=cBA=cAB=d,0,3.LR(0)分析表的构造,4.3自底向上语法分析,2)写出拓广文法GLR(0)的全部项目对于文法G,其LR(0)项目有：S=EA=cAE=bBS=EA=cAB=cBE=aAA=dB=cBE=aAA=dB=cBE=aAE=bBB=dA=cAE=bBB=d3）构造DFA先求出DFA初态I0的状态集I0的状态集由基本项目JS=E开始求出即I0S（）S（S=E）按构造的闭包CLOSURE（I）的方法,可求得I0S=E,E=aA,E=bB,3.LR(0)分析表的构造,4.3自底向上语法分析,由初态I0构造其他状态I1，I2，I3，.I11I1GO（I0，E）CLOSURE（SE）SEI2G0(I0，a)CLOSURE(EaA)EaA,A=cA,AdI3GO(I0,b)CLOSURE（EbB）=bB，cB，dI4GO(I2，c)CLOSURE(=cA)cA，cA，dI5GO(I3，c)CLOSURE(cB)cB，=cB，dI6GO(I2，A）CLOSURE(aA）EaAI7GO(I3,B)CLOSURE(bB)bBI8GO(I4,A）CLOSUREcA）AcAI9GO(I5,B）CLOSURE（cB）cBI10GO(I4，d)CLOSUREAd）AdI11GO(I3，d）CLOSURE(d）d此外，由于GO（4，c），GO（，d）GO（，c）=I5,GO(,d）=I11故它们不产生新项目集。实际上，我们可以直接画图求出I2，I3，.I11，这样可直接画出DFA图,十分方便。,3.LR(0)分析表的构造,I0:SE,I0:SEEaAEbB,I0:SEEaAEbB,I0:SEEaAEbB,I1:SE,I0:SEEaAEbB,I1:SE,a,I0:SEEaAEbB,I1:SE,a,I2:EaA,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbB,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcA,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcB,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,B,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,B,I7:EbB,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,B,I7:EbB,A,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,B,I7:EbB,A,I8:AcA,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,B,I7:EbB,A,I8:AcA,B,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,B,I7:EbB,A,I8:AcA,B,I9:BcB,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,B,I7:EbB,A,I8:AcA,B,I9:BcB,d,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,B,I7:EbB,A,I8:AcA,B,I9:BcB,I10:Ad,d,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,B,I7:EbB,A,I8:AcA,B,I9:BcB,I10:Ad,d,d,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,B,I7:EbB,A,I8:AcA,B,I9:BcB,I10:Ad,d,d,I11:Bd,d,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,B,I7:EbB,A,I8:AcA,B,I9:BcB,I10:Ad,d,d,I11:Bd,d,d,(5)LR(0)项目集规范族构成识别一个文法的活前缀的的项目集(状态)的全体称为这个文法的LR(0)项目集规范族。上例中文法的()项目集规范族为I0，I1，I2，I3，I11(6)LR(0)文法1)冲突项目如果一个项目集中既有移进项目又含有归约项目，或一个项目集中有两个以上不同归约项目，则称这些项目是冲突项目。前面我们构造的项目集还没有冲突项目2)LR（0）文法如果一个文法的项目规范族的每个项目集不存在任何冲突项目，则称该文法为（）文法。如：上例文法的LR（0）项目集规范族的每个项目集中就不存在冲突项目，所以该文法就是LR（0）文法。,3.LR(0)分析表的构造,(7)LR（0）分析表的构造对于（）文法，我们构造出识别活前缀DFA后，我们就可以根据DFA的状态转换图来构造LR（0）分析表。下面给出构造（）分析表的算法,假定I0，I1，I2，I3，In，为了方便起见，我们用整数0，1，2，3，n表示状态I0，I1，I2，I3，In，1）对于每个项目集Ii中有形如1X2项目，且GO（Ii,X）Ij，若XaVT，则置ACTIONi,aSj，若XVN，则置GOTOi,X=j如：I0中有E=aA，GO（I0，a)=I2,aVT,所以置ACTION0,aS2(见p125表4.17）I2中有E=aA，GO（I2,A）I6，AVN所以置GOTO2，A=6(见p125表4.17）,3.LR(0)分析表的构造,2)若归约项目属于i，设是文法第j个规则，则对任意终结符a和句子右界符#，均置ACTIONi,a或#rj，表示按文法第j条规则将符号栈顶符号串归约为。如：I6有项目E=aA,其规则E=aA是文法的第一个规则所以置ACTION6,a=ACTION6,b=ACTION6,c=ACTION6,d=ACTION6,#=r1(见p125表4.17）,3)若接受项目SS属于i，则置ACTION,#acc，表示接受如：SE属于I1，所以置ACTION1，#=acc(见p125表4.17）,4)分析表中，凡不能用前3个规则填入信息的空白格位置上，均表示出错。,I0:SEEaAEbB,I1:SE,a,I2:EaAAcAAd,b,I3:EbBBcBBd,c,I4:AcAAcAAd,c,c,I5:BcBBcBBd,c,A,I6:EaA,B,I7:EbB,A,I8:AcA,B,I9:BcB,I10:Ad,d,d,I11:Bd,d,d,S=EE=aAE=bBA=cAA=dB=cBB=d,(1)写出给定文法G的拓广文法G并编号，同时写出全部项目(2)写出G初始状态I0，项目集基本项目S=S，并由此基本项目求I0项目集合。(3)由I0项目集合，再根据GO函数和CLOSURE求LR（0）项目其它项目集I1,I2(4)构造识别活前缀的DFA(5)由DFA根据算法构造LR（0）分析表,构造LR（0）分析表小结,4.3自底向上语法分析,已知文法GS:S:=aAa|aBbA:=cB:=c,够造识别活前缀DFA,一、简单优先文法分析法三、优先函数及其构造1.与文法有关的一些关系定义1.优先函数定义2.构造文法关系传递闭包2.优先函数矩阵的构造和自反传递闭包3.利用优先函数矩阵进行语法分析3.文法优先关系概念四、LR分析法4.文法优先关系的构造1.LR分析法一般概述5.简单优先文法2.LR分析器工作原理6.简单优先文法分析算法3.LR（0）分析表构造二、算符优先分析法4.SLR（1）分析表构造1.算符优先关系概念5.LR（1）分析表构造2.算符优先文法6.LALR分析表构造3.算符优先关系的构造方法五、二义性文法的应用4.最左素短语1.问题的提出5.算符优先分析算法2.二义性文法分析表的构造,第四章语法分析,4.3自底向上语法分析,4.3自底向上语法分析,（1）问题提出上面介绍的LR(0)方法，是从左向右扫描源程序，当到达某规则右部最右符号时，便识别出这条规则，并且对于每一句柄，无需查看句柄之外任何输入符号。这种分析方法要求文法的每一个项目集都不含冲突性的项目。但通常程序设计语言文法不一定符合这种要求。例如LR(0)项目集规范族中有这样一个项目集IiIi1b2，其中第一个项目是移进项目，第二、三个项目是归约项目。仔细分析前面讨论的LR（0）分析表的构造可以知道，由于这三个项目相互冲突，因而使得（）分析表中出