LR(0)文法分析

1、实验名称： LR（ 0）文法分析1、 实验目的 ：输入：任意的压缩了的上下文无关文法。输出：相应的 LR（ 0）分析表。2、 实验原理：对于LR文法，我们可以自动构造相应的LR分析表。为了构造LR分析表，我们需要定义一个重要概念文法的规范句型“活前缀” 。这种句柄之后不含任何符号的前缀称为活前缀。在LR分析工作过程中的任何时候，栈里的文法符号（自栈底而上）X1X2 Xm应该构成活前缀， 把输入串的剩余部分配上之后即应成为规范句型 （如果整个输 入串确实构成一个句子） 。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。对于一个文法G， 我们可以构造一个有限自

2、动机， 它能识别G 的所有活前缀，然后把这个自动机转变成LR分析表，按照该LR分析表进行LR分析，就能保证 在分析的过程中，如果分析的句子是正确的，栈里的文法符号（自栈底而上）始终构成活前缀。假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态（项目集）不存在下述情况： （ 1）既含移进项目又含归约项目；（ 2）含有多个归约项目，则称 G 是一个 LR（ 0）文法。该自动机的状态集合即为该文法的LR（ 0）项目集规范族。构造识别文法活前缀DFAt 3种方法：（ 1）根据形式定义求出活前缀的正则表达式，然后由此正则表达式构造NFA再确定为DFA；（2）求出文法的所有项目，按一定规则构造识别活

3、前缀的NFM确定化为DFA；（3）使用闭包函数（CLOSURE和转向函数（GO（I,X）构造文法G的LR（0） 的项目集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的 DFA。符号用的前缀是指该符号用的任意首部，包括空用一例如，对于符号用abc, 其前缀有a, ab, abco如果输入用没有错误的话，一个规范句型的活前缀是 该句型的一个前缀， 但它不含句柄之后的任何符号。 之所以称为活前缀， 是因为 在该前缀后联接尚未输入的符号串可以构成一个规范句型。活前缀与句柄的关系如下：（1）活前缀已含有句柄的全部符号，表明产生式 Z B的右部B已出现在栈 顶。（2）活前缀只含句柄的一部分符

4、号，表明A- B 1 B 2的右部子用B 1已出现在 栈顶，期待从输入用中看到B 2推出的符号。（3）活前缀不含有句柄的任何符号，此时期望z B的右部所推出的符号用。在文法G勺每个产生式的右部（候选式）的任何位置上添加一个圆点，所构成的每个产生式称为 LR（ 0 ）项目。如产生式A xyz 有如下项目： A .xyz ，A x.yz ， A xy.z ， A xyz. 。为刻划分析过程中的文法的每一个产生式的右部符号已有多大一部分被识别 （出现在栈顶） ， 可以用这种标有圆点的产生式来确 定。(1) z B .刻划产生式 2 B的右部B已出现在栈顶。 z B 1. 0 2刻划A- B1B 2的

5、右部子用B 1已出现在栈顶，期待从输入用中 看到B 2推出的符号。(3) 2. B刻划没有句柄的任何符号在栈顶，此时期望A-B的右部所推出的符号串。(4)对于Afe的LR(0)项目只有Af.。*设文法G=(VT, Vn, S, P)是一个上下文无关文法，若存在一个规范推导 Srm错误 ! 未找到引用源。 Aw 错误 ! 未找到引用源。错误! 未找到引用源。 1错误 !未找到引用源。2W (其中库昔误！未找到引用源。错误！未找到引用源。1错误！未 找到引用源。2错误！未找到引用源。P),则称项目A错误！未找到引用源。错误！ 未找到引用源。 1? 错误 ！ 未找到引用源。2对活前缀错误 ！ 未找到

6、引用源。=错误 ！未找到引用源。错误！ 未找到引用源。 1是有效的，即 LR(0) 有效项目。从直观意义上讲，一个LR(0) 项目指明了在分析过程中的某一步我们看到产生式的多大部分被识别， LR(0) 项目中的圆点可看成是分析栈栈顶与输入串的分界线，圆点左边为已进入分析栈的部分，右边是当前输入或继续扫描的符号串。不同的 LR(0) 项目，反映了分析栈顶的不同情况。我们根据LR(0) 项目的作用不同，将其分为四类：( 1)归约项目：表现形式：Af a.这类LR(0)项目表示句柄a恰好包含在栈中，即当前栈顶的部分内容构成了 所期望的句柄，应按A-a进行归约。( 2)接受项目：表现形式：S-a.其中

7、 S 是文法惟一的开始符号。这类LR(0) 项目实际是特殊的归约项目，表示分析栈中内容恰好为a,用S-a进行归约，则整个分析成功。( 3)移进项目：表现形式：Za. b (b M)这类 LR(0) 项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前级，需将b 移进分析栈。( 4)待约项目：表现形式：2 a .B B (B Vn)这类 LR(0) 项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前缀，应把当前输入字符串中的相应内容先归约到B。在给出 LR(0) 项目的定义和分类之后，我们从这些 LR(0) 项目出发，来构造能识别文法所有前缀的有限自动机。 其步骤是：

8、首先构造能识别文法所有活前缀的非确定的有限自动机， 再将其确定化和最小化， 最终得到所需的确定的有限自动机。由文法G的LR(0)项目构造识别文法G的所有活前缀的非确定有限自动机的 方法：(1)规定含有文法开始符号的产生式(设 S -A)的第一个LR(0)项目(即 S - .A)为NFA的惟一初态。(2)令所有LR(0)项目分别对应NFA的一个X态且LR(0)项目为归约项目的 对应状态为终态。(3)若状态i和状态j出自同一文法G的产生式且两个状态LR(0)项目的 圆点只相差一个位置，即：若 i 为 X-X1X2 - X-1 - X Xn, j 为 XXiX, X - X+i Xn,则从状态 i

9、引 一条标记为Xi 的弧到状态j 。(4)若状态i为待约项目(设X-a AB),则从状态i弓屋弧到所有A f r的状态。为了使“接受”状态易于识别，我们通常将文法 G进行拓广。假定文法 G 是一个以 S 为开始符号的文法，我们构造一个G ，它包含了整个G,但它引进了一个不出现在 G中的非终结符S ,并加进一个新产生式S-S, 以S -SG为开始符号。那么，我们称G是G的拓广文法。这样，便会有一个仅含项目S -S的状态，这就是惟一的“接受”态。如果I是文法G/的一个项目集，定义和构造I的闭包CLOSURE(I)口下：(1) I的项目者B在CLOSURE。/。(2) 若A- .B属于CLOSURE

10、(I)则每一形如B-.的项目也属于 CLOSURE(I。)(3) 重复(2)直到CLOSURE。不再扩大。定义转换函数如下：GO(I ， X) = CLOSUR(EJ)其中：I为包含某一项目集的状态，X为一文法符号，J= A- X . | A -.X CI。圆点不在产生式右部最左边的项目称为核，惟一的例外是S' - .S,因此用GOTO I , X)状态转换函数得到的J为转向后状态闭包项目集的核。使用闭包函数(CLOSURE和转换函数(GO(I,X)构造文法G'的LR(0)的项目 集规范族，步骤如下：(4) 置项目S' -.S为初态集的核，然后对核求闭包CLOSURES

11、' -.S) 得到初态的闭包项目集。(5) 2)对初态集或其他所构造的项目集应用转换函数GO(I， X)= CLOSURE(J)求出新状态J 的闭包项目集。(6) 3) 重复(2)直到不出现新的项目集为止。计算 LR( 0)项目集规范族C=I 0， I 1 , . In 的算法伪代码如下：Procedure itemsets(G );Begin C := CLOSURE (S.S)RepeatFor C 中每一项目集I 和每一文法符号XDo if GO(I,X)非空且不属于CThen把GO(I,X) 放入研Until C 不再增大End;一个项目集可能包含多种项目，若移进和归约项目同时

12、存在，则称移进 - 归约冲突，若归约和归约项目同时存在，则称归约- 归约冲突。下面看一个具体的例子：我们希望能根据识别文法的活前缀的DFA建立LR分析器，因此，需要研究这个DFA的每个项目集(状态)中的项目的不同作用。我们说项目 2 B 1. g对活前缀a B i是有效的，具条件是存在规范推导S A 12 。一般而言，同一项目可能对几个活前缀都是有效的(当一个项目出现在几个不同的集合中时便是这种情形)。若归约项目A- Bi.对活前缀i是有效的，则它告诉我们应把符号用i归约为A,即把活前缀i变成a A。若移进项目 2 Bi. 02对活前缀i是有效的，则它告诉我们，句柄尚未形成，因此，下一步动作应

13、是移进。但是，可能存在这样的情形，对同一活前缀，存在 若干项目对它都是有效的。而且它们告诉我们应做的事情各不相同，互相冲突。这种冲突通过向前多看几个输入符号，或许能够获得解决。对于每个活前缀，我们可以构造它的有效项目集。实际上，一个活前缀丫的 有效项目集正是从上述的DFA的初态出发，经读出丫后而到达的那个项目集(状 态)。换言之，在任何时候，分析栈中的活前缀XiX2Xm的有效项目集正是栈顶状态S所代表的那个集合。这是LR分析理论的一条基本定理。实际上，栈顶的 项目集(状态)体现了栈里的一切有用信息历史。前面我们已经对 LR( 0)文法进行了定义, 下面我们来看一下LR( 0)分析表是如何构造的

14、。对于LR (0)文法，我们可以直接从它的项目集规范族C和活前缀识别自动机的状态转换函数GO勾造出LR分析表。下面是构造LR (0)分析表的算法。假定C=I。, I i,，In,令每个项目集屋的下标k为分析器的一个状态，因 此，G'的LR(0)分析表含有状态0, i,，n。令那个含有项目S'-. S的I k的下 标k为初态。ACTION表和GOTO表可按如下方法构造：(i)若项目 Z a .a B属于Ik且GO(I k, a)= Ij, a为终结符，则置ACTIONk, 为“把状态j 和符号 a 移进栈”，简记为“sj ”；(2)若项目Aa.属于Ik,那么，对任何终结符a,置A

15、CTIONS a为“用 产生式A-a进行规约”，简记为“ 门” ；其中，假定 2a为文法G'的第j个产 生式；(3)若项目S'-S.属于Ik,则置ACTIONk, #为“接受”，简记为“acc” ；( 4)若 GO (I k, A)= I j , A 为非终结符，则置GOTOk, A=j ；(5)分析表中凡不能用上述i至4填入信息的空白格均置上“出错标志”。按上述算法构造的含有ACTIO网口GOTO部分的分析表，如果每个入口不含多 重定义，则称它为文法 G勺一张LR(0)分析表。具有LR(0)表的文法 的为一个LR( 0)文法，LR(0) 文法是无二义的。例如，文法G (E)的

16、拓广文法如下：(0)S' - E(i)E aA(2)E -bB(3)A - cA(4)A - d(5)B - cB三、实验内容及其代码如下所示：#include<iostream>#include<stdio.h>#include<fstream>#include<malloc.h>using namespace std;#define OK 1#define ERROR 0#define N 50#define Y 20int vtnum,vnnum,pronum;/ 依次是终结符个数，非终结符个数，产生式个数char vtN;/终结符

17、集char vnN;/非终结符集char oldNN='/0'/ 用于存储文法char oldzNN='/0'/ 用于存储增广文法int ACTIONNN=0;/ 动作表int GOTONN=0;/ 状态转换表typedef struct SqEint t;/ 状态编号char c1;SqE;/ 堆栈元素typedef struct itemint f;/项目前部，表示产生式编号int l;/项目后部，表示停顿点在产生式的位置item;/ 定义项目typedef struct linkint f;/连接前部，表示所用符号的编号，非终结符编号=在 vn 中的下标+

18、100int l;/连接后部，即状态编号link;/ 定义状态之间的连接typedef struct cdint item_num;/状态中的项目数int link_num;/状态的连接数item wN;/项目集link uN;/连接集cd;/ 定义状态typedef struct DFAint cd_num;/ 状态个数cd sN+1;/ 状态集DFA;/定义规范LR(0)项目族,D.sN用作状态转换函数go_switch()的存储空 间DFA D;void dfa();/ 求规范 LR(0) 项目族void closure(int);/ 求闭包求转换增加新状态清空状态转换函数的存储空间vo

19、id go_switch(int,int);/ int test_go_switch();void add_go_switch();/ void del_go_switch();/ void action();/ 构造 ACTIONS void go_answer();/ 构造 GOTO!int control();/ 总控程序int length(int);/ 返回增广文法产生式右部的长度int test(char);void printf_ag();/ 输出 ACTIONS和 GOTOfe bool test_link(int i,int num);void main()int i,j;i

20、fstream in("input1.txt",ios_base:in);/读 文 件 , 从 文 件 中 读 入pronum,vtnum,vnnum 以及产生式in>>pronum>>vnnum>>vtnum;in>>vn;in>>vt;for(i=1;i<=pronum;i+)in>>oldi;/ 将产生式存入 old,old1 为第一个产生式for(i=1;i<=pronum;i+)for(j=0;oldij!='/0'j+)oldzij=oldij;/将产生式从old

21、 录入 oldzoldz00='P'01dz01=old10;/ 加入P->S,将原文法扩充，使其变为增广文法vtvtnum='$'/ 把结束符 '$' 加入终结符集D.cd_num=0;for(i=0;i<=N;i+)D.si.item_num=0;D.si.1ink_num=0;/ 初始化状态个数、连接个数、项目个数dfa();action();go_answer();printf_ag();control();/ 求一个状态的闭包void closure(int i) int j,k,m,x,flag;doj=D.si.item

22、_num;/j是本轮循环开始前的项目数for(k=0;k<D.si.item_num;k+)for(m=0;m<=pronum;m+)if(oldzm0=oldzD.si.wk.fD.si.wk.l)/对 当前状态 i 中的每个项目，查询每个产生式，例如： A->a.Ab 应找到A->.flag=0;/判断该项是否在当前状态i 中, 即检查 (m,1) 是否存在于状态i 中,保证求闭包时加入的新项目和原项目集不重合for(x=0;x<D.si.item_num;x+)if(D.si.wx.f=m&&D.si.wx.l=1) flag=1; brea

23、k; if(flag=0)/如果该项不在当前状态i 中，将其加入状态i D.si.wD.si.item_num.f=m;D.si.wD.si.item_num.l=1;D.si.item_num+;while(j!=D.si.item_num);/ 当一轮没有新的项目加入i 时，结束循环/状态转换函数，i是状态编号，num是符号编号，状态转换函数的结果存于sN void go_switch(int i,int num) int j;for(j=0;j<D.si.item_num;j+)if(test(oldzD.si.wj.fD.si.wj.l)=num)D.sN.wD.sN.item_

24、num.f=D.si.wj.f;D.sN.wD.sN.item_num.l=D.si.wj.l+1;D.sN.item_num+;closure(N);/ 返回终结符和非终结符的标号, 判断符号的类型,0<=终结符返回值<100,100<=非终结符返回值<200, 错误符号返回值=200int test(char c) int i,j;for(i=0;i<vtnum;i+) if(vti=c)break;if(i<vtnum)return i;elsefor(j=0;j<vnnum;j+)if(vnj=c)break;if(j<vtnum) re

25、turn (100+j);else return 200;/ 检验状态转换函数的结果int test_go_switch() int i,j,k,flag;if(D.sN.item_num=0)/ 判断状态转换的结果是否为空， 即当前状态可否接收该字符return 0;else for(i=0;i<D.cd_num;i+)/ 选定一状态，对sN 中的每个项目进行循环，如果存在一个项目在当前状态中未找到，即 flag=0 ，立即跳至下一状态flag=1;/ 判断状态转换函数的结果是否已经完全包含于某一现有状态中，例如go_switch(状态4,符号a)依然存在于状态4中，go_switch

26、(状态4,符号 c) 已经存在于状态5 中for(j=0;j<D.sN.item_num;j+)/如果在当前状态i 中找不到 sN的当前项目 j, 就跳至下一状态for(k=0;k<D.si.item_num;k+)if(D.si.wk.f=D.sN.wj.f&&D.si.wk.l=D.sN.wj.l)break;if(k>=D.si.item_num) flag=0; break; if(flag=1) return 1000+i;return 1;/ 状态转换函数的结果未被任何现有状态完全包含，完全满足建立新状态的条件/把状态转换函数的结果加入 DFA即当

27、建立新状态的条件符合时，建立新的状 态 sD.cd_numvoid add_go_switch()int i;for(i=0;i<D.sN.item_num;i+)D.sD.cd_num.wD.sD.cd_num.item_num.f=D.sN.wi.f;D.sD.cd_num.wD.sD.cd_num.item_num.l=D.sN.wi.l;D.sD.cd_num.item_num+;D.cd_num+;/ 清空状态转换函数的存储空间void del_go_switch()D.sN.item_num=0; / 构造规范 LR(0) 项目族 void dfa()int i,j,k;D.

28、s0.w0.f=0;D.s0.w0.l=1;D.cd_num+;D.s0.item_num+;closure(0);/ 把P->S加入初状态，并求其闭包do i=D.cd_num;/ 本轮循环开始时状态数for(j=0;j<D.cd_num;j+)/ 对每个状态进行循环对当前状态，每个非终结符检验当前状态用当前非终结符构造的for(k=0;k<vnnum;k+)/if(!test_link(j,k+100)/连接是否已经存在，若存在，则跳至下一非终结符，这样可以防止do_while()二次执行时，将连接集重新加入当前状态，比如 s0go_switch(j,k+100);/对当

29、前状态， 当前符号调用状态转换if(test_go_switch()=1)/ 如果符合建立新状态的条件add_go_switch();建立当前状态如果状态转换的结果包建立当前D.sj.uD.sj.link_num.f=k+100;/和新状态的连接D.sj.uD.sj.link_num.l=D.cd_num-1;D.sj.link_num+;elseif(test_go_switch()>=1000)/含于某一现有状态D.sj.uD.sj.link_num.f=k+100;/状态和该现有状态的连接D.sj.uD.sj.link_num.l=test_go_switch()-1000;D.s

30、j.link_num+; del_go_switch();/ 清空for(k=0;k<vtnum;k+)/ 对当前状态，每个终结符if(!test_link(j,k)go_switch(j,k);if(test_go_switch()=1) add_go_switch(); D.sj.uD.sj.link_num.f=k; D.sj.uD.sj.link_num.l=D.cd_num-1; D.sj.link_num+; else if(test_go_switch()>=1000) D.sj.uD.sj.link_num.f=k;D.sj.uD.sj.link_num.l=tes

31、t_go_switch()-1000;D.sj.link_num+; del_go_switch(); while(i!=D.cd_num);/ 当一轮没有新的状态产生时，结束 / 构造 ACTIONS void action() int i,j,k;for(i=0;i<D.cd_num;i+)/ 对每个状态循环 for(j=0;j<D.si.link_num;j+)/S ，对每个状态的每个连接循环，如果找到当前状态用终结符建立的连接，则ACTION曾前状态号对应终结符编号=连接另一端状态号if(D.si.uj.f<100) ACTIONiD.si.uj.f=D.si.uj.

32、l; for(j=0;j<D.si.item_num;j+)/r， 对每个状态的每个项目循环， 如果找到一个终结项目，例如 A->c.则ACTION曾前X态所有vt和$=产生式 A->c 的编号if(oldzD.si.wj.fD.si.wj.l='/0')for(k=0;k<=vtnum;k+) ACTIONik=D.si.wj.f+100; for(j=0;j<D.si.item_num;j+)/acc ， 对每个状态的每个项目循环， 如 果找到P->S.所在状态，则ACTION启前状态$=300 ,即accif(D.si.wj.f=0&a

33、mp;&D.si.wj.l=2) ACTIONivtnum=300; break; / 构造 GOTOfe void go_answer() int i,j;for(i=0;i<D.cd_num;i+)for(j=0;j<D.si.link_num;j+)/对每个状态的每个连接循环， 如果找到当前状态用非终结符建立的连接，则GOTO®前状态号对应非终2符编号=连接另一端状态号if(D.si.uj.f>=100) GOTOiD.si.uj.f-100=D.si.uj.l; / 总控程序 int control()int i,j,num;char cY='

34、;/0'/初始化带分析字符串的存储空间SqE stackN;int p1=0,p2=0;/p1是待分析字符串指针,p2是栈顶下一位 元素的指针 ,stack0 是栈底vtnum+;/ 把'$' 加入终结符集for(i=0;i<N;i+)stacki.c1='/0'/初始化符号栈stackp2.t=0;stackp2.c1='$'/ 把(0,$) 压栈p2+;/ 指针更新printf("/n 请输入要分析的字符串 ( 以$结尾 ):");cin>>c;printf("/n 栈中状态栈中符号输入

35、串 分析动作 /n");while(ACTIONstackp2-1.ttest(cp1)!=300)/ACTION栈 顶 状 态号 当前字符编号for(i=0,j=0;stacki.c1!='/0'i+)printf("%d",stacki.t);j+;for(i=0;i<14-j;i+)printf(" ");/输出栈中状态for(i=0,j=0;stacki.c1!='/0'i+)printf("%c",stacki.c1);j+;for(i=0;i<14-j;i+)print

36、f(" ");/输出栈中符号for(i=p1,j=0;ci!='/0'i+)printf("%c",ci);j+;for(i=0;i<14-j;i+)printf(" ");/输出剩余字符串if(ACTIONstackp2-1.ttest(cp1)>0&&ACTIONstackp2-1.ttest(cp1)<100)/Sprintf("S%d/n",ACTIONstackp2-1.ttest(cp1);/输出 分析动作stackp2.t=ACTIONstackp2-

37、1.ttest(cp1);/将状态压栈stackp2.c1=cp1;/ 将当前字符压栈p2+;p1+;/ 更新两个指针elseif(ACTIONstackp2-1.ttest(cp1)>100&&ACTIONstackp2-1.ttest(cp1)<200)/r, 归约num=ACTIONstackp2-1.ttest(cp1)-100;/num 是归约所用的产生式编号printf("r%d/n",num);p2=p2-length(num);/ 弹出 length(num) 个元素stackp2.t=GOTOstackp2-1.ttest(ol

38、dznum0)-100;/若 T 是弹出后的栈顶元素中的状态号，把GOTOToldznum0 压栈，注意-100stackp2.c1=oldznum0;/ 把 oldznum0 压栈p2+;stackp2.c1='/0'/ 封顶elseif(ACTIONstackp2-1.ttest(cp1)=0)/Errorprintf("Error/n/nError,您输入的句型和文法不符 !/n");return ERROR;printf("01$%c$acc/n",oldz10);printf("/nSucceed, 您输入句型和文法匹配!/n");return OK;/ 返回增广文法产生式右部的长度