编译原理课程设计报告
实验名称班学姓级号名
编译原理课程设计
指导教师实验成绩
2013年06月
f一、实验目的通过设计、编写和调试，将正规式转换为不确定的有穷自动机，再将不确定的有穷自动机转换为与之等价的确定的有穷自动机，最后再将确定有穷自动机进行简化。通过设计、编写和调试构造LR0项目集规范簇和LR分析表、对给定的符号串进行LR分析的程序，了解构造LR0分析表的步骤，对文法的要求，能够从文法G出发生成LR0分析表，并对给定的符号串进行分析。二、实验内容正规式NFADFAMFA1正规式转化为不确定的有穷自动机
（1）目的与要求
通过设计、编写和调试将正规式转换为不确定的有穷自动机的程序，使学生了解Thompso
算法，掌握转换过程中的相关概念和方法，NFA的表现形式可以是表格或图形。
（2）问题描述
任意给定一个正规式r（包括连接、或、闭包运算），根据Thompso
算法设计一个程序，生成与该正规式等价的NFAN。
（3）算法描述
对于Σ上的每个正规式R，可以构造一个Σ上的NFAM，使得LMLR。步骤1：首先构造基本符号的有穷自动机。
步骤2：其次构造连接、或和闭包运算的有穷自动机。
2
f（4）基本要求
算法实现的基本要求是：1输入一个正规式r；2输出与正规式r等价的NFA。
（5）测试数据
输入正规式：abaabbab得到与之等价的NFAN
3
f（6）输出结果
2不确定的有穷自动机的确定化
（1）目的与要求
通过设计、编写和调试将不确定的有穷自动机转换为与之等价的确定的有穷自动机的程序，使学生了解子集法，掌握转换过程中的相关概念和方法。DFA的表现形式可以是表格或图形。
（2）问题描述
任意给定一个不确定的有穷自动机N，根据算法设计一个程序，将该NFAN变换为与之等价的DFAD。
（3）算法描述
用子集法将NFA转换成接受同样语言的DFA。步骤一：对状态图进行改造1增加状态XY使之成为新的唯一的初态和终态。从X引ε弧到原初态结点从原终态结点引ε弧到Y结点。2对状态图进一步进行如下形式的改变
4
f步骤2：对NFA进行确定化，构造状态转换表。1子集构造法：初始时，ε_closures0是Dstates中唯一的状态且未被标记；whileDstates中存在一个未标记的状态Tdobegi
标记T；for每个输入符号adobegi
Uε_closuremoveTaifU没在Dstates中the
将U作为一个未标记的状态添加到Dstates中；e
de
d2ε_closure的计算，计算ε_closureT的简单算法是用栈来保存其弧还没有完成ε转换检查的状态。将T中r