new第四章语法分析.ppt

《new第四章语法分析.ppt》由会员分享，可在线阅读，更多相关《new第四章语法分析.ppt（156页珍藏版）》请在三一办公上搜索。

1、编 译 原 理Compiler Principles,蒋凌云南京邮电大学.计算机学院,第四章 语法分析,教材：编译技术原理及其实现方法王汝传 编著,第四章 语法分析,本章内容,4.1 引言 一、语法分析任务 二、语法分析方法4.2 自顶向下语法分析 一、自顶向下分析方法的问题及其解决办法 二、递归子程序分析法（递归下降分析法）三、LL（1）分析法4.3 自底向上语法分析 一、简单优先文法分析法 二、算符优先分析法 三、优先函数及其构造 四、LR分析法 五、二义性文法的应用4.4 语法分析程序的自动生成 一、分析器的生成器YACC 二、用YACC处理二义性文法,一、简单优先文法分析法 三、优先函

2、数及其构造 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.二义性文法分析表

3、的构造,第四章 语法分析,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、文法的应用 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）分析表

5、构造 2.算符优先文法 6.LALR分析表构造 3.算符优先关系的构造方法 五、二义性文法的应用 4.最左素短语 1.问题的提出 5.算符优先分析算法 2.二义性文法分析表的构造,第四章 语法分析,4.3 自底向上语法分析,4.3 自底向上语法分析,前面我们介绍的几种语法分析方法对相应的文法都有一定的要求。例如：因此，上述这些方法在使用上有一定局限性。LR分析法是1965年由Knuth提出一种自底向上语法分析方法，可用于一大类上下文无关文法分析，这种技术叫做LR(K)分析技术。,不带回溯的自顶向下分析方法要求文法不存在左递归，并且每一规则的各候选式的终结首符集两两不相交；算符优先分析方法则要求

6、文法的各终结符号对间至多只有一种优先关系，等等。,1.LR分析法一般概述,4.3 自底向上语法分析,（1）LR（K）分析法定义,LR(K)分析法意思是：L是指从左(Left)到右扫描输入符号串，R是构造最右(Rightmost)推导过程自底向上的分析方法。K是指在决定分析动作时向前看符号的个数。若K0，就为LR(0)分析，说明分析动作时，不向前看任何符号，LR(1)分析，说明分析动作时只向前看一个符号。这是一类对上下文无关文法进行“自左到右扫描和最左归约”的自底向上的分析方法，在这种分析过程中，它至多只向前查看个输入符号就能确定当前的动作是移进还是归约；若动作归约，它还能唯一地选中一个规则去归

7、约当前已识别的句柄。,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)：局限性大，但它是建立其它分

8、析表的基础 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分

9、析器工作原理 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分析器结构如下图所示。它是由一个输入符号串，一个下推状态栈，以及一个总控程序和

10、分析表组成。实际上在分析时读入符号是不进栈的。为使分析解释更清楚，我们另设一个符号栈（实际上只有一个状态栈用于存放状态）。,状态栈,状态栈,符号栈,输入串,2.LR分析器工作原理,LR分析器核心是分析表，分析表由两个子表组成：1)分析动作表 其中：S，S2，Sn 为分析器各状态 a,a2 am 为文法的全部终结符号和句子界限符 ACTIONSi,aj 指明，当状态Si面临输入符号aj时应采取的分析动作。有如下四个取值：ACTION Si,aj=S 移进动作，当前输入符号进桟 ACTION Si,aj=rj 按第j个产生式进行归约 ACTION Si,aj=acc 接受 ACTION Si,aj

11、=ERROR 出错,2）状态转换表 其中：，p是文法字汇表中全部非终结符号和终结符号 S，S，Sn为分析器各状态 GOTO Si,Xj指明当状态Si面对文法符号Xj时下一状态是什么,（2）LR分析器基本工作过程 1）分析实例 下面我们通过一个例子来说明LR分析器分析过程 例4.15设已知文法GE：(首先对每个文法规则要编号）=E+T=T*=（E）=i 为了节省空间，我们将文法分析动作表（ACTION）和状态转换表（GOTO）关于终结符的各列对应地进行合并，合并之后分析表如下表所示。（关于表的构造方法以后再讨论）,2.LR分析器工作原理,实例LR分析表,表中所引用记号的意义是：a.Sj 把下一个

12、状态j和现行输入符号ai移进栈b.rj 按第j个规则进行归约c.acc接受d.空白格出错标志，报错GOTO表仅对所有非终结符A列出GOTOSm,A的值，表明所要到达的状态的值。,实例分析过程现以输入串为i+i*i为例，给出分析器对它进行分析过程如下表,步骤 状态栈 符号栈 输入串 分析动作 下一状态 1 0#i+i*i#S5 5 2 05#i+i*i#r6 GOTO0,F=3 3 03#F+i*i#r4 GOTO0,T=2 4 02#T+i*i#r2 GOTO0,E=1 5 01#E+i*i#S6 6 6 016#E+i*i#S5 5 7 0165#E+i*i#r6 GOTO6,F=3 8 0

13、163#E+F*i#r4 GOTO6,T=9 9 0169#E+T*i#S7 7 10 01657#E+T*i#S5 5 11 016575#E+T*i#r6 GOTO7,F=10 12 0165710#E+T*F#r3 GOTO6,T=9 13 0169#E+T#r1 GOTO0,E=1 14 01#E#acc,2）LR分析器基本工作过程 LR分析器的工作是在总控程序控制下进行，其过程如下：分析开始时，首先将初始状态S及句子左界限符#推入分析栈和输入串构成一个三元式为（S，#，a1a2an#）其中S为初态，#为句子左界限符，a1a2an是输入串，其后#为句子右界限符。设在分析的某一步，分析栈

14、和余留输入符号串表示为（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,a

15、i+1ai+2 an#）,分析动作表每一元素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，将此新状态推入栈中则三元式变为（S0S1

16、Sm-rSk,#X1X2Xm-RA,aiai+1an#）归约动作不改变现行输入符号，输入串指示器不向前推进，它仍然指向动作前的位置。,2.LR分析器工作原理,c.若ACTIONSm,ai接受acc，则表明当前输入串已被成功地分析 完毕，则三元式不再变化，宣布分析成功。d.若ACTIONSm,ai报错ERROR，则三元式变化过程终止，报告错误。重复上述，直到在分析某一步，栈顶出现“接受状态”或“出错状态”为止。对于前者，其三元式变为（SSz，）其中为文法开始符号，Sz则为使ACTIONSz，“接受”的唯一状态。一个分析器工作过程就是一步一步地变换三元式，直至执行“接受”或“报错”为止。,2.LR

17、分析器工作原理,实例分析过程现以输入串为i+i*i为例，给出分析器对它进行分析过程如下表,步骤 状态栈 符号栈 输入串 分析动作 下一状态 1 0#i+i*i#S5 5 2 05#i+i*i#r6 GOTO0,F=3 3 03#F+i*i#r4 GOTO0,T=2 4 02#T+i*i#r2 GOTO0,E=1 5 01#E+i*i#S6 6 6 016#E+i*i#S5 5 7 0165#E+i*i#r6 GOTO6,F=3 8 0163#E+F*i#r4 GOTO6,T=9 9 0169#E+T*i#S7 7 10 01657#E+T*i#S5 5 11 016575#E+T*i#r6 G

18、OTO7,F=10 12 0165710#E+T*F#r3 GOTO6,T=9 13 0169#E+T#r1 GOTO0,E=1 14 01#E#acc,一、简单优先文法分析法 三、优先函数及其构造 1.与文法有关的一些关系定义 1.优先函数定义 2.构造文法关系传递闭包 2.优先函数矩阵的构造 和自反传递闭包 3.利用优先函数矩阵进行语法分析 3.文法优先关系概念 四、LR分析法 4.文法优先关系的构造 1.LR分析法一般概述 5.简单优先文法 2.LR分析器工作原理 6.简单优先文法分析算法 3.LR（0）分析表构造二、算符优先分析法 4.SLR（1）分析表构造 1.算符优先关系概念 5.

19、LR（1）分析表构造 2.算符优先文法 6.LALR分析表构造 3.算符优先关系的构造方法 五、二义性文法的应用 4.最左素短语 1.问题的提出 5.算符优先分析算法 2.二义性文法分析表的构造,第四章 语法分析,4.3 自底向上语法分析,4.3 自底向上语法分析 LR（0）分析就是LR（K）分析当的情况，就是指在分析每一步，只要根据当前栈顶状态，就能确定应采取何种分析动作，而无需向前查看输入符号。为了构造LR分析表，首先引入规范句型活前缀的概念。（1）规范句型的活前缀 字的前缀：是指字的任意首部。如字abc的前缀有,a,ab,abc.活 前 缀：规范句型（右句型）的一个前缀，如果它不含句柄后

20、任何符号，则称它是该规范句型的一个活前缀。也就是说在活前缀右边增添一些终结符号之后，就可以成为规范句型。,在LR分析过程中的任何时候，栈里的文法符号X1X2Xm应该构成活前缀，把输入串的剩余部分配上之后即成为规范句型（如果整个输入串确实构成一个句子的话。）,如：S+abcdef,其中cd是句柄，则,a,ab,abc,abcd是该规范句型的活前缀，而abcd是包含句柄的活前缀。,3.LR(0)分析表的构造,实例分析过程现以输入串为i+i*i为例，给出分析器对它进行分析过程如下表,步骤 状态栈 符号栈 输入串 分析动作 下一状态 1 0#i+i*i#S5 5 2 05#i+i*i#r6 GOTO0

21、,F=3 3 03#F+i*i#r4 GOTO0,T=2 4 02#T+i*i#r2 GOTO0,E=1 5 01#E+i*i#S6 6 6 016#E+i*i#S5 5 7 0165#E+i*i#r6 GOTO6,F=3 8 0163#E+F*i#r4 GOTO6,T=9 9 0169#E+T*i#S7 7 10 01657#E+T*i#S5 5 11 016575#E+T*i#r6 GOTO7,F=10 12 0165710#E+T*F#r3 GOTO6,T=9 13 0169#E+T#r1 GOTO0,E=1 14 01#E#acc,（2）LR（）项目 1)活前缀与句柄之间的关系 作为规

22、范句型的活前缀不含有句柄后任何符号。因此，前缀与句柄的关系可能有三种情况：,活前缀已包含句柄全部符号，这表明规则的右部符号串已在分析栈顶，因此相应的分析动作应是用此规则进行归约，称可归约的活前缀。我们用 表示,3.LR(0)分析表的构造,4.3 自底向上语法分析,活前缀中只含句柄一部分符号，意味着形如规则12的右部子串1已出现在栈顶，正期待着从余留输入串中看到能由推出的符号串。我们用表示 活前缀不包含句柄的任何符号，这表明规则的右部符号串不在分析栈顶，正期待从余留输入串中由规则的所能推出的符号串。我们用表示,3.LR(0)分析表的构造,4.3 自底向上语法分析,2)LR（0）项目我们把右部某位

23、置上标有圆点的规则称为相应文法的一个LR（0）项目。特别地，对形如的规则，相应（）项目为。例如，一个（）项目 12 一个（）项目 一个（）项目若 一个（）项目例如 一个规则=aBC，根据圆点的位置不同可以有四个LR（）项目：aBC 正期待着从余留输入串中由aBC推出的符号串进栈 aBC a已进栈，正期待着从余留输入串中由BC推出的符号串进栈 aBC aB推出的符号串进栈,正期待着从余留输入串中由C推出 的符号串进栈 aBC aBC推出的符号串进栈 对于规则对应项目数为个。（表示所含字符的个数）显然，不同的（）项目反映了分析过程中栈顶的不同情况。,3.LR(0)分析表的构造,(3)构造识别活前缀

24、的有穷自动机(FA)M Knuth证明了一个LR文法的右句型的所有活前缀能够为有穷自动机所接受我们可以把文法G中每一个项目作为非确定有穷自动机的一个状态，构造NFA，然后再将其确定化为DFA。1)文法G的全部项目例4.16 设有文法GE=(E,A,B,a,b,c,d,P,E)，其中P由下列规则组成:E=aA A=d E=bB B=cB A=cA B=d,3.LR(0)分析表的构造,S=E E=aA A=d E=bB B=cB A=cA B=d 将文法拓广的目的是使文法只有一个开始符作为左部规则，这样构造出来的分析器有唯一接受项目。否则E=aA和E=bB就有两个归约项目。,0,为了方便起见，我们

25、在上述文法中引入一个新的开始符号S，并将S=E作为第0个规则，从而得到所谓G的拓广文法G，显然，L(G)=L(G)。,3.LR(0)分析表的构造,对于文法G,其LR(0)项目有 S=E A=cA E=bB S=E A=cA B=cB E=aA A=d B=cB E=aA A=d B=cB E=aA E=bB B=d A=cA E=bB B=d,说明：(1)可用一个整数对n,m来表示一个LR(0)项目，其中第一个整数n用指 明产生式的编号，第二个整数m则用来指明圆点所处的位置。例如，项目(1)可表示为0,0，项目(7)表示3,1等等。,3.LR(0)分析表的构造,(2)我们可根据它们不同作用,将

26、一个文法全部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是非终结符,由于我们期待着从余留输

27、入符号串中进行归约而得到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+1 m 而状态j(j为为一个项）i-1ii+1m 则从状态i出发，画一条标记为i的弧到状态j,i,j,i,1,2,E,3,4,a,例如：,对于文法G,其LR(0)项目有 S=E A=cA E=bB

28、S=E A=cA B=cB E=aA A=d B=cB E=aA A=d B=cB E=aA E=bB B=d A=cA E=bB B=d,如果状态i圆点之后那个符号i 为非终结符，那么从状态i画弧到所有形如i的项目（状态）例如状态圆点之后那个符号是E，为非终结符，那么从状态画弧到所有形如E的项目（状态）,即状态(E=aA)和 状态(E=bB),i,i,1,2,3,11,E,任何其它状态是NFA终态，凡是属于归约项目的状态是特殊的终态，即可识别可归约活前缀。根据上述方法很容易构造出-NFA状态转换图，图中状态是唯一的初态，其他17个状态都是终态。画双圆圈者是可归约状态，可指向句柄识别状态，即可

29、归约活前缀,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是一个活前缀，但不是可归约活前缀，因为

30、不包括所有句柄符号，从上面例子可以看出，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:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c

31、,c,I5:B c B B cB B d,c,A,I6:E aA,B,I7:E bB,A,I8:A cA,B,I9:B cB,I10:A d,d,d,I11:B d,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。由此即得

32、状态I0 的项目子集S=E，E=aA，E=bB,3.LR(0)分析表的构造,结论：若NFA的某一状态的相应项目为B2，而是非终结符 号，如果有形如规则,其相应项目均为项目子集 中一个项目，如果新获得圆点之后的符号又为非终结符号，则又将派 生出新的项目，如此继续下去，直到全部新获得项目的圆点之后的符 号为终结符号或圆点之后无符号为止。这时，所有获得新项目连同原有项目构成一个项目子集，作为DFA一 个状态。(如：状态I0),3.LR(0)分析表的构造,4.3 自底向上语法分析,实际上，我们将项目S称为项目集I0的基本项目，上述从项目S出发构造项目集I0的过程可用一个对其基本项目集S的闭包运算，即C

33、LOSURE（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，圆点向后移一位。由此

34、得结论：设为一个文法符号（终结符或非终结符）,若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=aA Ij I2S（）S（E=aA）则构

35、造的闭包CLOSURE（I）的方法，可求得 I2E=aA,A=cA,A=d,3.LR(0)分析表的构造,为了指明状态j和状态i之间这种转换关系，我们定义一个状态转换函数（i，）S（）其中，i为当前状态，为文法符号，而任何形如的项目属于j J是基本项目集例如：I0中有项目E=bB I3GO(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时，就

36、不必要先构造NFA，然后再用子集法来构造DFA，我们可以直接由文法来构造DFA了。1)将一般文法G改写成拓广文法G 如果S是文法G的开始符号，则拓广文法G中增加一个规则 S=S，S是文法G开始符号，显然L(G)L(G)这样就使得拓广文法G中有项目S=S是唯一接受项目 例如上面我们举的例子中的拓广文法G为：S=E E=aA A=d E=bB B=cB A=cA B=d,0,3.LR(0)分析表的构造,4.3 自底向上语法分析,2)写出拓广文法GLR(0)的全部项目对于文法G,其LR(0)项目有：S=E A=cA E=bB S=E A=cA B=cB E=aA A=d B=cB E=aA A=d

37、B=cB E=aA E=bB B=d A=cA E=bB B=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）SE I2G0(I0，a)CLOSURE(Ea A)EaA,A=cA,AdI3GO(I0,b)CLOSURE（EbB）=bB，cB，dI4GO(I2，c)CLOSURE(=cA)cA，cA，dI5GO(

38、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）Ad I11GO(I3，d）CLOSURE(d）d此外，由于GO（4，c），GO（，d）GO（，c）=I5,GO(,d）=I11故它们不产生新项目集。实际上，我们可以直接画图求出I2，I3，.I11，这样可直接画出DFA图,十分方便。,3.LR(0)分析表的构造,I0:S E,I0:S E E aA E bB,I0:S E

39、 E aA E bB,I0:S E E aA E bB,I1:S E,I0:S E E aA E bB,I1:S E,a,I0:S E E aA E bB,I1:S E,a,I2:E a A,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB

40、 B d,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A

41、 c A A cA A d,c,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B

42、cB B d,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B cB B d,c,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B cB B d,c,A,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A

43、A cA A d,c,c,I5:B c B B cB B d,c,A,I6:E aA,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B cB B d,c,A,I6:E aA,B,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B cB B d,c,A,I6:E aA,B,I7:E bB,I0:S E E

44、aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B cB B d,c,A,I6:E aA,B,I7:E bB,A,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B cB B d,c,A,I6:E aA,B,I7:E bB,A,I8:A cA,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A

45、 d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B cB B d,c,A,I6:E aA,B,I7:E bB,A,I8:A cA,B,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B cB B d,c,A,I6:E aA,B,I7:E bB,A,I8:A cA,B,I9:B cB,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b

46、B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B cB B d,c,A,I6:E aA,B,I7:E bB,A,I8:A cA,B,I9:B cB,d,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B cB B d,c,A,I6:E aA,B,I7:E bB,A,I8:A cA,B,I9:B cB,I10:A d,d,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b

47、,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B cB B d,c,A,I6:E aA,B,I7:E bB,A,I8:A cA,B,I9:B cB,I10:A d,d,d,I0:S E E aA E bB,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B cB B d,c,A,I6:E aA,B,I7:E bB,A,I8:A cA,B,I9:B cB,I10:A d,d,d,I11:B d,d,I0:S E E aA E b

48、B,I1:S E,a,I2:E a A A cA A d,b,I3:E b B B cB B d,c,I4:A c A A cA A d,c,c,I5:B c B B cB B d,c,A,I6:E aA,B,I7:E bB,A,I8:A cA,B,I9:B cB,I10:A d,d,d,I11:B d,d,d,(5)LR(0)项目集规范族 构成识别一个文法的活前缀的的项目集(状态)的全体称为这个文法的LR(0)项目集规范族。上例中文法的()项目集规范族为I0，I1，I2，I3，I11(6)LR(0)文法 1)冲突项目 如果一个项目集中既有移进项目又含有归约项目，或一个项目集中有 两个以上不同

49、归约项目，则称这些项目是冲突项目。前面我们构造的项目集还没有冲突项目 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中有

50、形如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