资源描述：
《编译原理实验自动生成LR(0)分析表》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、2016.12.14自动生成LR（0）分析表16目录一、实验名称2二、实验目的2三、实验原理21、闭包closure(I)22、转换函数GO(I,X)23、ACTION子表和GOTO子表的构造2四、实验思路31、输入32、建立项目33、closure算法34、转向函数GO(I,X)的算法35、建立状态及对应的项目集36、ACTION子表的构造47、GOTO子表的构造4五、实验小结4六、附件51、源代码52、运行结果截图916一、实验名称自动生成LR（0）分析表二、实验目的1、实现计算闭包函数CLOSURE的算法。2、实现转向函数GO(I,X)的算法。3、实现AC
2、TION子表和GOTO子表的构造算法。4、输入任意的压缩了的上下文无关文法，输出相应的LR（0）分析表（以表格形式输出）。三、实验原理1、闭包closure(I)若文法G已拓广为G’，而S为文法G的开始符号，拓广后增加产生式S’->S。如果I是文法G’的一个项目集，定义和构造I的闭包closure(I)如下：a.I的项目在closure(I)中。b.若A->α•Bβ属于closure(I)，则每一形如B->•γ的项目也属于closure(I)。c.重复b直到不出现新的项目为止。即closure(I)不再扩大。2、转换函数GO(I,X)GO(I,X)=closur
3、e(J)其中：I为包含某一项目集的状态。X为一文法符号，X∈Vn∪VtJ={任何形如A->α•Xβ的项目
4、A->αX•β属于I}163、ACTION子表和GOTO子表的构造a.若项目A→α.aβ属于Ik且GO(Ik,a)=Ij,a为终结符，则置ACTION[k,a]为“把状态j和符号a移进栈”，简记为“sj”；b.若项目A→α．属于Ik，那么，对任何终结符a，置ACTION[k，a]为“用产生式A→α进行规约”，简记为“rj”；其中，假定A→α为文法G'的第j个产生式c.若项目S'→S．属于Ik,则置ACTION[k,#]为“接受”，简记为“acc”；d.若GO
5、(Ik,A)=Ij,A为非终结符，则置GOTO[k,A]=j；e.分析表中凡不能用上述1至4填入信息的空白格均置上“出错标志”。按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张LR(0)分析表。具有LR(0)表的文法G称为一个LR（0）文法，LR(0)文法是无二义的。四、实验思路本次实验采用python完成。1、输入构造一个LR类，输入非终结符，终结符，开始符以及产生式分别存于LR类的成员：Vn，Vt，start，production。2、建立项目构造函数Project，根据产生式建立项目，对每一条产生式的
6、右部进行处理，依次在右部的每个终结符和非终结符前添加原点，并在最后添加原点。3、closure算法构造函数closure，求一个项目的闭包closure。分三种情况讨论，对于S->·16和E->·a这两种情况，返回自身。对于E->b·B这种情况，对项目的右部进行处理，继续求B->·r闭包，因此这是一个递归函数。最终函数以列表的形式返回每个项目集。4、转向函数GO(I,X)的算法构造函数GO，求一个项目集的GO(I,X)。建立字典go存放最终结果，对不是S->a·形式的项目进行讨论，对项目的右部进行处理，将原点后移一位，利用closure函数得到圆点后移得到的项目
7、的项目集，加入go中。直到处理完该项目集的所有项目。5、建立状态及对应的项目集构造函数createDFA，建立状态及对应的项目集。首先，从拓广文法的第一个项目开始，建立初态，定义number存放状态编号，初始值为0。设立字典status存放状态编号及对应的项目集。将初态加入一个队列qu中。每次从qu中取出一个状态，求该状态的项目集的Go(I,x)，再对得到的项目集进行判断，若该项目集是已知的状态，则不做处理，若该项目集是新的状态，则将其加入队列qu中，number加1。每次从qu中取出一个状态重复上述操作，直到队列为空，说明已求得所有状态。6、ACTION子表的
8、构造分两种情况讨论：项目集只有一个项目和项目集不止一个项目。对于第一种情况，再分两种情况，看该项目是否对应了初态，若是，则将#对应为acc，其余终结符对应为error，若不是，则求得该项目去掉圆点之后的产生式的编号i，终结符合#对应为ri。对于项目集不止一个项目的情况，依次对终结符和#寻找在该状态的的GO(I,X)下是否有所对应，有则求得编号对应为Si，没有则对于16error。7、GOTO子表的构造对于每个状态的GO(I,X)函数进行遍历，寻找是否有对应的终结符，若有则返回对应的项目集的编号，若没有则返回error。五、实验小结通过本次实验，了解了LR(0)分
9、析表的构造，对于构造过程
