LR(0)表构造讲解

1、编译原理实验报告实验名称 自动生成LR (0)分析表实验时间2013、12、10院系计算机科学与电子技术系班级2011级计算机软件学号JV114023 JV114052 JV114078姓名 段国顺 葛立冬 黄磊、实验目的输入：任意的压缩了的上下文无关文法输出：相应的LR (0)分析表。二、实验原理对于LR文法，我们可以自动构造相应的 LR分析表。为了构造LR分析表, 我们需要定义一个重要概念一一文法的规范句型“活前缀”。这种句柄之后不含任何符号的前缀称为活前缀。在LR分析工作过程中的任何时候，栈里的文法符号(自栈底而上)X1X2Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型(

2、如果整 个输入串确实构成一个句子)。因此，只要输入串的已扫描部分保持可归约成一 个活前缀，那就意味着所扫描过的部分没有错误。对于一个文法G,我们可以构造一个 有限自动机，它能识别 G的所有活前 缀，然后把这个自动机转变成LR分析表，按照该LR分析表进行LR分析，就 能保证在分析的过程中，如果分析的句子是正确的，栈里的文法符号(自栈底而 上)始终构成活前缀。假若一个文法G的拓广文法G 的活前缀识别自动机中的每个状态(项目集) 不存在下述情况：(1)既含移进项目又含归约项目；(2)含有多个归约项目，则 称G是一个LR (0)文法。该自动机的状态集合即为该文法的 LR (0)项目集 规范族。构造识别

3、文法活前缀DFA有3种方法：(1) 根据形式定义求出活前缀的正则表达式， 然后由此正则表达式构造NFA 再确定为DFA;(2) 求出文法的所有项目，按一定规则构造识别活前缀的 NFA再确定化为 DFA;(3) 使用闭包函数(CLOSURE)和转向函数(GO(I,X)构造文法G的LR(0) 的项目集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。符号串的前缀是指该符号串的任意首部，包括空串。例如，对于符号串abc, 其前缀有c，a，ab, abc。如果输入串没有错误的话，一个规范句型的活前缀是 该句型的一个前缀，但它不含句柄之后的任何符号。之所以称为活前缀，是因为 在该前缀后

4、联接尚未输入的符号串可以构成一个规范句型。活前缀与句柄的关系如下：(1) 活前缀已含有句柄的全部符号，表明产生式 A - B的右部B已出现在 栈顶。(2) 活前缀只含句柄的一部分符号，表明 A1 B 2的右部子串B 1已出现 在栈顶，期待从输入串中看到B 2推出的符号。(3) 活前缀不含有句柄的任何符号，此时期望 A- B的右部所推出的符号 串。在文法G的每个产生式的右部(候选式)的任何位置上添加一个圆点，所构 成的每个产生式称为LR (0)项目。如产生式A- xyz有如下项目：A.xyz， A x.yz，A xy.z，A xyz.。为刻划分析过程中的文法的每一个产生式的右部 符号已有多大一部

5、分被识别(出现在栈顶)，可以用这种标有圆点的产生式来确 定。(1) Af B 刻划产生式Af B的右部B已出现在栈顶。(2) Af B 1. B 2刻划Af B i B 2的右部子串B i已出现在栈顶，期待从输入串 中看到B 2推出的符号。(3) Af.B刻划没有句柄的任何符号在栈顶，此时期望 AfB的右部所推出 的符号串。(4) 对于Af &的LR(O)项目只有Af.o设文法G= ( Vt, Vn , S, P)是一个上下文无关文法，若存在一个规范推导*s=. aAw= ab1b2W (其中A?b lb2?P)，则称项目A?b l?b 2对活前缀g=abi是有效的, rmrm即LR(0)有效

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

7、a,用Sf a进行归约，则整个分析成功。(3) 移进项目：表现形式：Af a.b ( b Vt)这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句 柄的活前级，需将b移进分析栈。(4) 待约项目：表现形式：Af a .BB (B Vn)这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句 柄的活前缀，应把当前输入字符串中的相应内容先归约到B。在给出LR(0)项目的定义和分类之后，我们从这些 LR(0)项目出发，来构造 能识别文法所有前缀的有限自动机。 其步骤是：首先构造能识别文法所有活前缀 的非确定的有限自动机，再将其确定化和最小化，最终得到所需的确定的有

8、限自 动机。由文法G的LR(0)项目构造识别文法G的所有活前缀的非确定有限自动机 的方法：(1) 规定含有文法开始符号的产生式 (设S f A)的第一个LR(0)项目(即 S f .A)为NFA的惟一初态。(2) 令所有LR(0)项目分别对应NFA的一个状态且LR(0)项目为归约项目 的对应状态为终态。(3) 若状态i和状态j出自同一文法G的产生式且两个状态LR(O)项目的圆 点只相差一个位置，即：若 i 为 X X1X2 Xi-1 XiXn, j 为 X XlX2Xi Xi+1 Xn,则从状态 i引一条标记为Xi的弧到状态j。(4) 若状态i为待约项目(设X a A B),则从状态i引弧到所

9、有A r的状态。为了使“接受”状态易于识别，我们通常将文法 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)不再扩大。定

10、义转换函数如下：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的闭

11、包项目集。(3) 重复(2)直到不出现新的项目集为止。计算LR (0)项目集规范族C=I0, I1 , . In 的算法伪代码如下：Procedure itemsets(G );Begin C := CLOSURE (S、.S)RepeatFor C中每一项目集I和每一文法符号XDo if GO(I,X)非空且不属于CThe n把GO(I,X)放入C中Un til C不再增大En d;一个项目集可能包含多种项目，若移进和归约项目同时存在，则称移进-归约 冲突，若归约和归约项目同时存在，则称归约-归约冲突。下面看一个具体的例子：我们希望能根据识别文法的活前缀的 DFA建立LR分析器，因此，需要研

12、 究这个我们说项目A 1. B 2对活前缀a B 1是有效的，其条件是存在规范推导 S匚.A二2。一般而言，同一项目可能对几个活前缀都是有效的(当一个项目出现在几个不同的集合中时便是这种情形)。若归约项目A-Bi对活前缀 :11是有效的，贝尼告诉我们应把符号串11归约为A，即把活前缀门i变成a A。 若移进项目Ai. B 2对活前缀Ji是有效的，则它告诉我们，句柄尚未形成， 因此，下一步动作应是移进。但是，可能存在这样的情形，对同一活前缀，存在 若干项目对它都是有效的。而且它们告诉我们应做的事情各不相同，互相冲突。 这种冲突通过向前多看几个输入符号，或许能够获得解决。对于每个活前缀，我们可以构

13、造它的有效项目集。实际上，一个活前缀丫的 有效项目集正是从上述的DFA的初态出发，经读出丫后而到达的那个项目集(状 态)。换言之，在任何时候，分析栈中的活前缀XlX2Xm的有效项目集正是栈顶状态Sm所代表的那个集合。这是LR分析理论的一条基本定理。实际上，栈 顶的项目集(状态)体现了栈里的一切有用信息一一历史。前面我们已经对LR (0)文法进行了定义，下面我们来看一下LR (0)分析 表是如何构造的。对于LR (0)文法，我们可以直接从它的项目集规范族C和活前缀识别自动机的状态转换函数GO构造出LR分析表。下面是构造LR (0)分析表的算法。假定C=l0, li, ，In，令每个项目集Ik的下

14、标k为分析器的一个状态，因此， G的LR(0)分析表含有状态0，1，n。令那个含有项目SS的Ik的下标k为初态。ACTION子表和GOT0子表可按如下方法构造：(1) 若项目A a .aB属于Ik且GO (Ik, a)= Ij, a为终结符，则置ACTIONk, a为“把状态j和符号a移进栈”，简记为“ s”；(2) 若项目A a 属于Ik，那么，对任何终结符a，置ACTIONk，a为“用 产生式A a进行规约”，简记为“ rj”；其中，假定A a为文法G的第j个产 生式；(3) 若项目S S.属于Ik,贝U置ACTIONk, #为“接受”，简记为“acc”；(4) 若GO (Ik, A)=

15、Ij, A为非终结符，则置 GOTOk, A=j ；(5) 分析表中凡不能用上述1至4填入信息的空白格均置上“出错标志”。按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不 含多重定义，则称它为文法G的一张LR(0)分析表。具有LR(0)表的文法G称为一 个LR (0)文法，LR(0)文法是无二义的。DFA的每个项目集(状态)中的项目的不同作用。三、实验内容(1) 建立一个项目集 class ProjectSet/(2) 建立 string actionTableMAX_PRO_SET_NUM+1MAX_VT_NUM;/ACTION表string gotoTableMAX

16、_PRO_SET_NUM+1MAX_VT_NUM;/GOTO 表( 3)输出分析表 voidinput()四、实验代码与结果#include #include #include using namespace std;#define MAX_PRO_NUM 50#define MAX_PRO_SET_NUM 20#define MAX_P_NUM 20#define MAX_VT_NUM 27string vn;/ 非终结符集 string vt;/ 终结符集，包括 #struct Project/ 项目的数据结构char left;string inputed;string uninpute

17、d;bool operator = (Project cmp)if(left = cmp.left & inputed = cmp.inputed & uninputed = cmp.uninputed) return true;elsereturn false;struct Go/* GO 映射的数据结构* goij.input = a* goij.nextProjectSet = 2* 表示 第 i 状态的第 j 条箭弧 受 a 激发到达第 2 状态*/char input;int nextProjectSet;goMAX_PRO_SET_NUMMAX_PRO_NUM;int goLeng

18、thMAX_PRO_SET_NUM = 0;/goLengthi 是第 i 状态共有多少条箭弧struct PSet/产生式集合char left;/产生式左部string right;/ 产生式右部 bool operator =(Project t)/ 判断项目是否是由该产生式得到的 string temp; if(left != t.left) return false;else if(t.inputed = null) temp = t.uninputed;else if(t.uninputed = null) temp = t.inputed;else temp = t.inpute

19、d + t.uninputed; if(right = temp) return true;return false; pSetMAX_P_NUM; int pSetLength = 0;/ 产生式个数class ProjectSet;struct DFA/识别活前缀的 DFA的项目集集合 ProjectSet* stateMAX_PRO_SET_NUM; int stateLength;aDFA;class ProjectSet/ 项目集private: int projectNum;Project proMAX_PRO_NUM;int proLength;int includeMAX_P_

20、NUM; public:ProjectSet(Project in)/ 由一个项目构造项目集闭包 projectNum = aDFA.stateLength; proLength = 1;for(int i = 0;i MAX_P_NUM;i+) includei = 0;pro0.left = in.left; pro0.inputed = in.inputed;pro0.uninputed = in.uninputed;for(int j = 0; j = a & vn = z) continue;for(int i = 0; i pSetLength; i+)if(pSeti.left

21、= vn & includei = 0)includei = 1;proproLength.left = pSeti.left; proproLength.inputed = null; proproLength.uninputed = pSeti.right; proLength+;int getProjectNum()return projectNum;int getProLength()return proLength;Project getPro(int i)return proi;string actionTableMAX_PRO_SET_NUM+1MAX_VT_NUM;/ACTIO

22、N 表string gotoTableMAX_PRO_SET_NUM+1MAX_VT_NUM;/GOTO 表void input(); int getActionIndex(char t);int getGotoIndex(char t); string intToString(int t);void display()/ 显示 LR(0) 分析表 couttttACTIONttttGOTOendl; coutendl;for(int i = 0;i 0) couti-1t;else coutt;for(unsigned j = 0;j vt.length();j+) coutactionTa

23、bleijt;for( j = 0;j vn.length();j+) coutgotoTableijt;coutendl; int main()input();for(int i = 0; i MAX_PRO_SET_NUM; i+) aDFA.statei = NULL;aDFA.stateLength = 0;Project start; start.left = pSet0.left; start.inputed = null; start.uninputed = pSet0.right;aDFA.state0 = new ProjectSet(start); aDFA.stateLe

24、ngth+;int currState = 0;/ 当前分析的项目集do for(int i = 0;i getProLength();i+) string temp = aDFA.statecurrState-getPro(i).uninputed; if(temp = null)/ 归约项目 continue;elsegocurrStategoLengthcurrState.input = temp0;/ 当前状态 currState 的第 goLengthcurrState 条箭弧 受 uninputed0 激发gocurrStategoLengthcurrState.nextProje

25、ctSet = aDFA.stateLength;/ 默认 到达一个新建的状态Project aProject,t = aDFA.statecurrState-getPro(i);aProject.left = t.left;if(t.inputed = null)aProject.inputed = t.uninputed0;else aProject.inputed = t.inputed + t.uninputed0;if(t.uninputed.length() = 1) aProject.uninputed = null;elseaProject.uninputed = t.unin

26、puted.substr(1,t.uninputed.length();bool flag = false;if(aProject = aDFA.statecurrState-getPro(0)/ 状态到达自身 置一条到 达自身的箭弧 gocurrStategoLengthcurrState.nextProjectSet = aDFA.statecurrState-getProjectNum();goLengthcurrState+; continue;elsefor(int iter = 0;iter getPro(0)/ 与其他某一状态吻合 置一跳到达该状态的箭弧 gocurrStateg

27、oLengthcurrState.nextProjectSet = iter; goLengthcurrState+;flag = true;break;if(flag = false)/ 均不满足时新建一个状态 gocurrStategoLengthcurrState.nextProjectSet = aDFA.stateLength; aDFA.stateaDFA.stateLength = new ProjectSet(aProject);aDFA.stateLength+; goLengthcurrState+; currState+;while(currState != aDFA.s

28、tateLength);/ 当前分析的项目集是项目集集合的最后一个项目 集时退出循环/* 以上 ,识别活前缀的 DFA 构造完毕* 以下 ,构造 LR(0) 分析表*/ACTION 表和 GOTO 表初始化for( i = 0;i vt.length();i+) actionTable0i = vti;for( i = 0;i vn.length();i+) gotoTable0i = vni;/以状态号顺序填表for( i = 0;i getPro(0); if(t.uninputed = null)/ 是归约项目 if(t.left = Z & t.inputed0 = vn0 & t.i

29、nputed.length() = 1)/ 接受状态 Z-S. actionTablei+1vt.length()-1 = acc; continue;for(int iter = 0;iter getPro(0) for(unsigned k = 0;k vt.length();k+) actionTablei+1k = r + intToString(iter); continue;for(int j = 0;j = a & goij.input = A & goij.input = Z)/非终结符 跳转int index = getGotoIndex(goij.input); gotoTablei+1index = intToString(goij.nextProjectSet);display();getchar();return 0;void input()char line20;c