- 1、本文档共12页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
PAGE 1
2016.12.14
自动生成LR(0)分析表
目录
TOC \o 1-3 \h \z \u 一、实验名称 2
二、实验目的 2
三、实验原理 2
1、闭包closure(I) 2
2、转换函数GO(I,X) 2
3、ACTION子表和GOTO子表的构造 2
四、实验思路 3
1、输入 3
2、建立项目 3
3、closure算法 3
4、转向函数GO(I,X)的算法 3
5、建立状态及对应的项目集 3
6、ACTION子表的构造 4
7、GOTO子表的构造 4
五、实验小结 4
六、附件 5
1、源代码 5
2、运行结果截图 9
一、实验名称
自动生成LR(0)分析表
二、实验目的
1、实现计算闭包函数CLOSURE的算法。
2、实现转向函数GO(I,X)的算法。
3、实现ACTION子表和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)=closure(J)
其中:I为包含某一项目集的状态。
X为一文法符号,X∈Vn∪Vt
J={任何形如A-α?Xβ的项目|A-αX?β属于I}
3、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 (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,根据产生式建立项目,对每一条产生式的右部进行处理,依次在右部的每个终结符和非终结符前添加原点,并在最后添加原点。
3、closure算法
构造函数closure,求一个项目的闭包closure。分三种情况讨论,对于S-·和E-·a这两种情况,返回自身。对于E-b·B这种情况,对项目的右部进行处理,继续求B-·r闭包,因此这是一个递归函数。最终函数以列表的形式返回每个项目集。
4、转向函数GO(I,X)的算法
构造函数GO,求一个项目集的GO(I,X)。建立字典go存放最终结果,对不是S-a·形式的项目进行讨论,对项目的右部进行处理,将原点后移一位,利用closure函数得到圆点后移得到的项目的项目集,加入go中。直到处理完该项目集的所有项目。
5、建立状态及对应的项目集
构造函数createDFA,建立状态及对应的项目集。首先,从拓广文法的第一个项目开始,建立初态,定义number存放状态编号,初始值为0。设立字典status存放状态编号及对应的项目集。将初态加入一个队列qu中。每次从qu中取出一个状态,求该状态的项目集的Go(I,x),再对得到的项目集进行判断,若该项目集是已知的状态,则不做处理,若该项目集是新的状态,则将其加入队列qu中,number加1。每次从qu中取出一个状态重复上述操作,直到队列为空,说明已求得所有状态。
6、ACTION子表的构造
分两种情况讨论:项目集只有一个项目和项目集不止一个项目。对于第一种情况,再分两种情况,看该项目是否对应了初态,若是,则将#对应为acc,其余终结符对应为error,若不是,则求得该项目去掉圆点之后的产生式的编号
您可能关注的文档
- 电解原理测试题.doc
- Sedex土地权利程序.doc
- 智能小车电机驱动原理.doc
- 《河中石兽》译字、译句、简答.doc
- 会议口译原文及译文.doc
- 安全阀的工作原理.doc
- 北京工业大学编译原理考试一纸开卷【期末复习总结】.doc
- 员工申诉处理程序.doc
- 党组议事规则及程序.doc
- 北方工业大学编译原理实验2报告语法分析.doc
- 第十一章 电流和电路专题特训二 实物图与电路图的互画 教学设计 2024-2025学年鲁科版物理九年级上册.docx
- 人教版七年级上册信息技术6.3加工音频素材 教学设计.docx
- 5.1自然地理环境的整体性 说课教案 (1).docx
- 4.1 夯实法治基础 教学设计-2023-2024学年统编版九年级道德与法治上册.docx
- 3.1 光的色彩 颜色 电子教案 2023-2024学年苏科版为了八年级上学期.docx
- 小学体育与健康 四年级下册健康教育 教案.docx
- 2024-2025学年初中数学九年级下册北京课改版(2024)教学设计合集.docx
- 2024-2025学年初中科学七年级下册浙教版(2024)教学设计合集.docx
- 2024-2025学年小学信息技术(信息科技)六年级下册浙摄影版(2013)教学设计合集.docx
- 2024-2025学年小学美术二年级下册人美版(常锐伦、欧京海)教学设计合集.docx
文档评论(0)