自动生成LR0分析表实验

自动生成LR(0)分析表实验1/18 编译原理实验报告实验名称自动生成 LR(0)分析表实验时间2013 年 12 月 24 日院系计算机科学与电子技术系班级11计算机软件学号JV114001 JV114095 JP114065 姓名唐茹韩强强徐思维自动生成LR(0)分析表实验2/18 1.试验目的：输入：任意的压缩了的上下文无关文法。输出：相应的 LR（0）分析表。2.实验原理：对于 LR 文法，我们可以自动构造相应的LR 分析表。为了构造LR 分析表，我们需要定义一个重要概念文法的规范句型“活前缀”。这种句柄之后不含任何符号的前缀称为活前缀。在 LR 分析工作过程中的任何时候，栈里的文法符号（自栈底而上）X1X2Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型（如果整个输入串确实构成一个句子）。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。对于一个文法G，我们可以构造一个有限自动机，它能识别G 的所有活前缀，然后把这个自动机转变成LR 分析表，按照该LR 分析表进行 LR 分析，就能保证在分析的过程中，如果分析的句子是正确的，栈里的文法符号（自栈底而上）始终构成活前缀。假若一个文法 G 的拓广文法 G 的活前缀识别自动机中的每个状态（项目集）不存在下述情况：（1）既含移进项目又含归约项目；（2）含有多个归约项目，则称 G 是一个 LR（0）文法。该自动机的状态集合即为该文法的LR（0）项目集规范族。构造识别文法活前缀DFA 有 3 种方法：（1）根据形式定义求出活前缀的正则表达式，然后由此正则表达式构造 NFA再确定为 DFA；（2）求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA；（3）使用闭包函数（CLOSURE）和转向函数(GO(I,X)构造文法 G 的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。符号串的前缀是指该符号串的任意首部，包括空串。例如，对于符号串 abc，其前缀有，a，ab，abc。如果输入串没有错误的话，一个规范句型的活前缀是该句型的一个前缀，但它不含句柄之后的任何符号。之所以称为活前缀，是因为在该前缀后联接尚未输入的符号串可以构成一个规范句型。活前缀与句柄的关系如下：（1）活前缀已含有句柄的全部符号，表明产生式A的右部已出现在栈顶。（2）活前缀只含句柄的一部分符号，表明A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号。（3）活前缀不含有句柄的任何符号，此时期望A的右部所推出的符号串。在文法 G的每个产生式的右部（候选式）的任何位置上添加一个圆点，所构成的每个产生式称为LR（0）项目。如产生式Axyz有如下项目：A.xyz，自动生成LR(0)分析表实验3/18 Ax.yz，Axy.z，Axyz.。为刻划分析过程中的文法的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶），可以用这种标有圆点的产生式来确定。（1）A.刻划产生式 A的右部已出现在栈顶。（2）A1.2 刻划A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号。（3）A.刻划没有句柄的任何符号在栈顶，此时期望A的右部所推出的符号串。（4）对于 A的 LR(0)项目只有 A。设文法 G=（VT，VN，S，P）是一个上下文无关文法，若存在一个规范推导S*rmAwrm1 2w（其中 A1 2P），则称项目 A1?2对活前缀=1是有效的，即LR(0)有效项目。从直观意义上讲，一个LR(0)项目指明了在分析过程中的某一步我们看到产生式的多大部分被识别，LR(0)项目中的圆点可看成是分析栈栈顶与输入串的分界线，圆点左边为已进入分析栈的部分，右边是当前输入或继续扫描的符号串。不同的 LR(0)项目，反映了分析栈顶的不同情况。我们根据LR(0)项目的作用不同，将其分为四类：（1）归约项目：表现形式：Aa.这类 LR(0)项目表示句柄 a 恰好包含在栈中，即当前栈顶的部分内容构成了所期望的句柄，应按Aa进行归约。（2）接受项目：表现形式：Sa.其中 S 是文法惟一的开始符号。这类LR(0)项目实际是特殊的归约项目，表示分析栈中内容恰好为a，用 Sa进行归约，则整个分析成功。（3）移进项目：表现形式：Aa.b（bVT）这类 LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前级，需将b 移进分析栈。（4）待约项目：表现形式：A.B（BVN）这类 LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前缀，应把当前输入字符串中的相应内容先归约到B。在给出 LR(0)项目的定义和分类之后，我们从这些LR(0)项目出发，来构造能识别文法所有前缀的有限自动机。其步骤是：首先构造能识别文法所有活前缀的非确定的有限自动机，再将其确定化和最小化，最终得到所需的确定的有限自动机。由文法 G 的 LR(0)项目构造识别文法G 的所有活前缀的非确定有限自动机的方法：（1）规定含有文法开始符号的产生式（设 S A）的第一个 LR(0)项目（即S.A）为 NFA 的惟一初态。（2）令所有 LR(0)项目分别对应 NFA 的一个状态且 LR(0)项目为归约项目自动生成LR(0)分析表实验4/18 的对应状态为终态。（3）若状态 i 和状态 j 出自同一文法 G 的产生式且两个状态LR(0)项目的圆点只相差一个位置，即：若 i 为 XX1X2Xi-1XiXn，j 为 XX1X2XiXi+1Xn，则从状态i 引一条标记为 Xi的弧到状态 j。（4）若状态 i 为待约项目（设X A），则从状态 i 引弧到所有Ar 的状态。为了使“接受”状态易于识别，我们通常将文法G 进行拓广。假定文法 G 是一个以 S 为开始符号的文法，我们构造一个G，它包含了整个 G，但它引进了一个不出现在G 中的非终结符 S，并加进一个新产生式S S，以 S SG 为开始符号。那么，我们称G 是 G 的拓广文法。这样，便会有一个仅含项目S S 的状态，这就是惟一的“接受”态。如果I是文法 G的一个项目集，定义和构造I的闭包 CLOSURE(I)如下：（1）I的项目都在 CLOSURE(I)中。（2）若A.B 属于CLOSURE(I)，则每一形如 B.的项目也属于CLOSURE(I)。（3）重复（2）直到 CLOSURE(I)不再扩大。定义转换函数如下：GO（I，X）=CLOSURE（J）其中：I为包含某一项目集的状态，X为一文法符号，J=A X.|A.X I。圆点不在产生式右部最左边的项目称为核，惟一的例外是S.S，因此用GOTO（I，X）状态转换函数得到的 J为转向后状态闭包项目集的核。使用闭包函数（CLOSURE）和转换函数(GO(I,X)构造文法 G 的LR(0)的项目集规范族，步骤如下：（1）置项目 S.S为初态集的核，然后对核求闭包CLOSURE（S.S）得到初态的闭包项目集。（2）对 初 态 集 或 其 他 所 构 造 的 项 目 集 应 用 转 换 函 数 GO(I，X)=CLOSURE(J)求出新状态 J的闭包项目集。（3）重复（2）直到不出现新的项目集为止。计算LR（0）项目集规范族 C=I0，I1,.In 的算法伪代码如下：Procedure itemsets(G);Begin C:=CLOSURE(S.S)Repeat For C 中每一项目集 I 和每一文法符号 X Do if GO(I,X)非空且不属于 C Then 把 GO(I,X)放入C中自动生成LR(0)分析表实验5/18 Until C 不再增大End;一个项目集可能包含多种项目，若移进和归约项目同时存在，则称移进-归约冲突，若归约和归约项目同时存在，则称归约-归约冲突。下面看一个具体的例子：我们希望能根据识别文法的活前缀的DFA 建立 LR 分析器，因此，需要研究这个 DFA 的每个项目集（状态）中的项目的不同作用。我们说项目A1.2对活前缀1是有效的，其条件是存在规范推导21AS。一般而言，同一项目可能对几个活前缀都是有效的（当一个项目出现在几个不同的集合中时便是这种情形）。若归约项目A1.对活前缀1是有效的，则它告诉我们应把符号串1归约为 A，即把活前缀1变成 A。若移进项目 A1.2对活前缀1是有效的，则它告诉我们，句柄尚未形成，因此，下一步动作应是移进。但是，可能存在这样的情形，对同一活前缀，存在若干项目对它都是有效的。而且它们告诉我们应做的事情各不相同，互相冲突。这种冲突通过向前多看几个输入符号，或许能够获得解决。对于每个活前缀，我们可以构造它的有效项目集。实际上，一个活前缀的有效项目集正是从上述的DFA 的初态出发，经读出后而到达的那个项目集（状态）。换言之，在任何时候，分析栈中的活前缀X1X2Xm的有效项目集正是栈顶状态 Sm所代表的那个集合。这是LR 分析理论的一条基本定理。实际上，栈顶的项目集（状态）体现了栈里的一切有用信息历史。前面我们已经对LR（0）文法进行了定义,下面我们来看一下LR（0）分析表是如何构造的。对于 LR（0）文法，我们可以直接从它的项目集规范族C 和活前缀识别自动机的状态转换函数GO 构造出 LR 分析表。下面是构造 LR（0）分析表的算法。假定C=I0,I1,，In，令每个项目集 Ik的下标 k为分析器的一个状态，因此，G 的LR(0)分析表含有状态 0，1，n。令那个含有项目 S S的Ik的下标 k为初态。ACTION子表和 GOTO子表可按如下方法构造：（1）若项目 A.a属于 Ik且 GO(Ik,a)=Ij,a为终结符，则置 ACTIONk,a为“把状态 j 和符号 a 移进栈”，简记为“sj”；（2）若项目 A属于 Ik，那么，对任何终结符 a，置ACTIONk，a为“用产生式 A进行规约”，简记为“rj”；其中，假定 A为文法 G 的第j个产生式；（3）若项目S S属于Ik,则置ACTIONk,#为“接受”，简记为“acc”；（4）若GO(Ik,A)=Ij,A为非终结符，则置 GOTOk,A=j；（5）分析表中凡不能用上述 1至4填入信息的空白格均置上“出错标志”。按上述算法构造的含有 ACTION 和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张 LR(0)分析表。具有 LR(0)表的文法 G称为一个LR（0）文法，LR(0)文法是无二义的。自动生成LR(0)分析表实验6/18 例如，文法 G（E）的拓广文法如下：(0)SE(1)E aA(2)E bB(3)A cA(4)A d(5)B cB(6)B d 该文法的 LR（0）分析表如表所示。State ACTION GOTO A b C D#E A B 0 S2 S3 1 1 acc 2 S4 S10 6 3 S5 S11 7 4 S4 S10 8 5 S5 S11 9 6 r1 R1 r1 r1 r1 7 r2 R2 r2 r2 r2 8 r3 R3 r3 r3 r3 9 r4 R4 r4 r4 r4 10 r5 R5 r5 r5 r5 11 r6 R6 r6 r6 r6 3.实验内容及其代码如下所示：#include#include#include#include using namespace std;#define OK 1#define ERROR 0#define N 50#define Y 20 自动生成LR(0)分析表实验7/18 int vtnum,vnnum,pronum;/依次是终结符个数，非终结符个数，产生式个数char vtN;/终结符集char vnN;/非终结符集char oldNN=/0;/用于存储文法char oldzNN=/0;/用于存储增广文法int ACTIONNN=0;/动作表int GOTONN=0;/状态转换表typedef struct SqE int t;/状态编号char c1;SqE;/堆栈元素typedef struct item int f;/项目前部，表示产生式编号int l;/项目后部，表示停顿点在产生式的位置item;/定义项目typedef struct link int f;/连接前部，表示所用符号的编号，非终结符编号=在 vn 中的下标+100 int l;/连接后部，即状态编号link;/定义状态之间的连接typedef struct cd int item_num;/状态中的项目数int link_num;/状态的连接数item wN;/项目集link uN;/连接集cd;/定义状态typedef struct DFA int cd_num;/状态个数cd sN+1;/状态集DFA;/定义规范 LR(0)项目族,D.sN用作状态转换函数go_switch()的存储空间DFA D;void dfa();/求规范 LR(0)项目族void closure(int);/求闭包void go_switch(int,int);/求转换int test_go_switch();void add_go_switch();/增加新状态void del_go_switch();/清空状态转换函数的存储空间自动生成LR(0)分析表实验8/18 void action();/构造 ACTION 表void go_answer();/构造 GOTO 表int control();/总控程序int length(int);/返回增广文法产生式右部的长度int test(char);void printf_ag();/输出 ACTION 表和 GOTO 表bool test_link(int i,int num);void main()int i,j;ifstream in(input1.txt,ios_base:in);/读文件,从文件中读入pronum,vtnum,vnnum以及产生式inpronumvnnumvtnum;invn;invt;for(i=1;ioldi;/将产生式存入 old,old1 为第一个产生式for(i=1;iS，将原文法扩充，使其变为增广文法vtvtnum=$;/把结束符$加入终结符集D.cd_num=0;for(i=0;i=N;i+)D.si.item_num=0;D.si.link_num=0;/初始化状态个数、连接个数、项目个数dfa();action();go_answer();printf_ag();control();/求一个状态的闭包void closure(int i)int j,k,m,x,flag;do 自动生成LR(0)分析表实验9/18 j=D.si.item_num;/j 是本轮循环开始前的项目数for(k=0;kD.si.item_num;k+)for(m=0;ma.Ab 应找到 A-.flag=0;/判断该项是否在当前状态i 中,即检查(m,1)是否存在于状态 i 中,保证求闭包时加入的新项目和原项目集不重合for(x=0;xD.si.item_num;x+)if(D.si.wx.f=m&D.si.wx.l=1)flag=1;break;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;jD.si.item_num;j+)if(test(oldzD.si.wj.fD.si.wj.l)=num)D.sN.wD.sN.item_num.f=D.si.wj.f;D.sN.wD.sN.item_num.l=D.si.wj.l+1;D.sN.item_num+;closure(N);自动生成LR(0)分析表实验10/18/返回终结符和非终结符的标号,判断符号的类型,0=终结符返回值 100,100=非终结符返回值 200,错误符号返回值=200 int test(char c)int i,j;for(i=0;ivtnum;i+)if(vti=c)break;if(ivtnum)return i;else for(j=0;jvnnum;j+)if(vnj=c)break;if(jvtnum)return(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;iD.cd_num;i+)/选定一状态，对 sN中的每个项目进行循环，如果存在一个项目在当前状态中未找到，即flag=0，立即跳至下一状态 flag=1;/判断状态转换函数的结果是否已经完全包含于某一现有状态中，例如 go_switch(状态 4,符号 a)依然存在于状态4 中，go_switch(状态 4,符号c)已经存在于状态5 中for(j=0;jD.sN.item_num;j+)/如果在当前状态 i 中找不到 sN的当前项目 j,就跳至下一状态 for(k=0;k=D.si.item_num)自动生成LR(0)分析表实验11/18 flag=0;break;if(flag=1)return 1000+i;return 1;/状态转换函数的结果未被任何现有状态完全包含，完全满足建立新状态的条件 /把状态转换函数的结果加入DFA，即当建立新状态的条件符合时，建立新的状态 sD.cd_num void add_go_switch()int i;for(i=0;iS加入初状态，并求其闭包do i=D.cd_num;/本轮循环开始时状态数for(j=0;jD.cd_num;j+)/对每个状态进行循环 for(k=0;k=1000)/如果状态转换的结果包含于某一现有状态 D.sj.uD.sj.link_num.f=k+100;/建立当前状态和该现有状态的连接D.sj.uD.sj.link_num.l=test_go_switch()-1000;D.sj.link_num+;del_go_switch();/清空 for(k=0;k=1000)D.sj.uD.sj.link_num.f=k;D.sj.uD.sj.link_num.l=test_go_switch()-1000;自动生成LR(0)分析表实验13/18 D.sj.link_num+;del_go_switch();while(i!=D.cd_num);/当一轮没有新的状态产生时，结束/构造 ACTION 表void action()int i,j,k;for(i=0;iD.cd_num;i+)/对每个状态循环 for(j=0;jD.si.link_num;j+)/S，对每个状态的每个连接循环，如果找到当前状态用终结符建立的连接，则 ACTION 当前状态号 对应终结符编号=连接另一端状态号 if(D.si.uj.f100)ACTIONiD.si.uj.f=D.si.uj.l;for(j=0;jc.则 ACTION 当前状态 所有 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;jS.所在状态，则 ACTION 当前状态$=300，即 acc if(D.si.wj.f=0&D.si.wj.l=2)ACTIONivtnum=300;break;自动生成LR(0)分析表实验14/18 /构造 GOTO 表void go_answer()int i,j;for(i=0;iD.cd_num;i+)for(j=0;j=100)GOTOiD.si.uj.f-100=D.si.uj.l;/总控程序int control()int i,j,num;char cY=/0;/初始化带分析字符串的存储空间SqE stackN;int p1=0,p2=0;/p1 是待分析字符串指针,p2 是栈顶下一位元素的指针,stack0是栈底vtnum+;/把$加入终结符集for(i=0;ic;printf(/n 栈中状态栈中符号输入串分析动作/n);while(ACTIONstackp2-1.ttest(cp1)!=300)/ACTION栈顶状态号 当前字符编号 for(i=0,j=0;stacki.c1!=/0;i+)printf(%d,stacki.t);j+;自动生成LR(0)分析表实验15/18 for(i=0;i14-j;i+)printf();/输出栈中状态for(i=0,j=0;stacki.c1!=/0;i+)printf(%c,stacki.c1);j+;for(i=0;i14-j;i+)printf();/输出栈中符号for(i=p1,j=0;ci!=/0;i+)printf(%c,ci);j+;for(i=0;i0&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(oldznum0)-100;/若 T 是弹出后的栈顶元素中的状态号，把GOTOToldznum0 压栈，注意-100 stackp2.c1=oldznum0;/把 oldznum0 压栈p2+;stackp2.c1=/0;/封顶 else if(ACTIONstackp2-1.ttest(cp1)=0)/Error printf(Error/n/nError,您输入的句型和文法不符!/n);自动生成LR(0)分析表实验16/18 return ERROR;printf(01$%c$acc/n,oldz10);printf(/nSucceed,您输入句型和文法匹配!/n);return OK;/返回增广文法产生式右部的长度int length(int i)int j;for(j=1;oldzij!=/0;j+)return(j-1);/j-1 是产生式右部字符数/输出两张表void printf_ag()int i,j;printf(ACTION 表为:/n);printf();for(i=0;i=vtnum;i+)printf(%c,vti);printf(/n);for(i=0;iD.cd_num;i+)if(i10)printf(%d,i);else printf(%d,i);for(j=0;j=vtnum;j+)if(ACTIONij0)if(ACTIONij0)printf(s%d,ACTIONij);else printf(s%d,ACTIONij);else if(ACTIONij100&ACTIONij200)自动生成LR(0)分析表实验17/18 if(ACTIONij-100)0)printf(r%d,ACTIONij-100);else printf(r%d,ACTIONij-100);else if(ACTIONij=300)printf(acc);else printf();printf(/n);printf(/nGOTO 表为:/n);printf();for(i=0;ivnnum;i+)printf(%c,vni);printf(/n);for(i=0;iD.cd_num;i+)if(i10)printf(%d,i);else printf(%d,i);for(j=0;jvnnum;j+)if(GOTOij10)printf(%d,GOTOij);else printf(%d,GOTOij);printf(/n);/检验在当前状态下是否已存在用当前字符建立的连接bool test_link(int i,int num)int j;for(j=0;jD.si.link_num;j+)if(D.si.uj.f=num)return true;return false;自动生成LR(0)分析表实验18/18 4.运行结果截图：