(重庆理工大学计算机学院)编译原理课程设计报告.docVIP

(重庆理工大学计算机学院)编译原理课程设计报告.doc

  1. 1、本文档共23页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
编译原理课程设计报告 实验名称 编译原理课程设计 班 级 学 号 姓 名 指导教师 实验成绩 2013 年06月 实验目的 通过设计、编写和调试,将正规式转换为不确定的有穷自动机,再将不确定的有穷自动机转换为与之等价的确定的有穷自动机,最后再将确定有穷自动机进行简化。 通过设计、编写和调试构造LR(0)项目集规范簇和LR分析表、对给定的符号串进行LR分析的程序,了解构造LR(0)分析表的步骤,对文法的要求,能够从文法G出发生成LR(0)分析表,并对给定的符号串进行分析。 实验内容 正规式——NFA——DFA——MFA 1.正规式转化为不确定的有穷自动机 (1)目的与要求 通过设计、编写和调试将正规式转换为不确定的有穷自动机的程序,使学生了解Thompson算法,掌握转换过程中的相关概念和方法,NFA的表现形式可以是表格或图形。 (2)问题描述 任意给定一个正规式r(包括连接、或、闭包运算),根据Thompson算法设计一个程序,生成与该正规式等价的NFA N。 (3)算法描述 对于Σ上的每个正规式R,可以构造一个Σ上的NFA M,使得L(M)=L(R)。 步骤1:首先构造基本符号的有穷自动机。 步骤2:其次构造连接、或和闭包运算的有穷自动机。 (4)基本要求 算法实现的基本要求是: (1) 输入一个正规式r; (2) 输出与正规式r等价的NFA。 (5)测试数据 输入正规式:(a|b)*(aa|bb)(a|b)* 得到与之等价的NFA N (6)输出结果 2.不确定的有穷自动机的确定化 (1)目的与要求 通过设计、编写和调试将不确定的有穷自动机转换为与之等价的确定的有穷自动机的程序,使学生了解子集法,掌握转换过程中的相关概念和方法。DFA的表现形式可以是表格或图形。 (2)问题描述 任意给定一个不确定的有穷自动机N,根据算法设计一个程序,将该NFA N变换为与之等价的DFA D。 (3)算法描述 用子集法将NFA转换成接受同样语言的DFA。 步骤一:对状态图进行改造 (1) 增加状态X,Y,使之成为新的唯一的初态和终态。从X引ε弧到原初态结点, 从原终态结点引ε弧到Y结点。 (2) 对状态图进一步进行如下形式的改变 步骤2:对NFA 进行确定化,构造状态转换表。 (1) 子集构造法: 初始时,ε_closure(s0)是Dstates中唯一的状态且未被标记; while Dstates中存在一个未标记的状态T do begin 标记T; for 每个输入符号a do begin U:= ε_closure(move(T,a)); ifU没在Dstates中then 将U作为一个未标记的状态添加到Dstates中; end; end; (2) ε_closure的计算,计算ε_closure(T)的简单算法是用栈来保存其弧还没有完成ε转换检查的状态。 将T中所有的状态压入栈stack中: 将ε_closure(T)初始化为T; while栈stack不空 do begin 将栈顶元素t弹出栈; for每个这样的状态u:从t到u有一条标记为ε的边do if u不在ε_closure(T)中do begin 将u添加到ε_closure(T); 将u压入栈stack中; end; end; (4)基本要求 算法实现的基本要求是: (1) 输入一个NFA N; (2) 输出与之等价的DFA。 (5)测试数据 给定不确定的有穷自动机: 得到与之等价的确定的有穷自动机: (6)输出效果 输出状态转换表表示的确定的有穷自动机如下: 3.确定的有穷自动机的化简 (1)目的与要求 通过设计、编写和调试将确定的有穷自动机的状态数变为最少的程序,使学生掌握化简有穷自动机的过程中的相关概念和方法。DFA的表现形式可以是表格或图形。 (2)问题描述 每一个正规集都可以由一个状态数最少的DFA所识别,这个DFA是唯一的(因状态名不同的同构情况除外)。任意给定一个确定的有穷自动机,根据算法设计一个程序,将该DFA化简为与之等价的最简DFA。 (3)算法描述 1.构造具有两个组的状态集合的初始划分Π:接受状态组F,非接受状态组S-F。 2.对Π采用下面所述的过程来构造新的划分Πnew。 for Π中每个组G do begin 当且仅当对任意输入符号a,状态s和t读入a后转换到Π的同一组中; /*最坏情况下,一个状态就可能成为一个组*/ 用所

文档评论(0)

celkhn5460 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档