（重庆理工大学计算机学院）编译原理课程设计报告

编译原理课程设计报告

实验名称 编译原理课程设计 班 级 学 号 姓 名 指导教师 实验成绩

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：其次构造连接、或和闭包运算的有穷自动机。

2

（4）基本要求

算法实现的基本要求是：

(1) 输入一个正规式r；

(2) 输出与正规式r等价的NFA。

（5）测试数据

输入正规式：(a|b)*(aa|bb)(a|b)* 得到与之等价的NFA N

3

（6）输出结果

2.不确定的有穷自动机的确定化

（1）目的与要求

通过设计、编写和调试将不确定的有穷自动机转换为与之等价的确定的有穷自动机的程序，使学生了解子集法，掌握转换过程中的相关概念和方法。DFA的表现形式可以是表格或图形。

（2）问题描述

任意给定一个不确定的有穷自动机N，根据算法设计一个程序，将该NFA N变换为与之等价的DFA D。

（3）算法描述

用子集法将NFA转换成接受同样语言的DFA。 步骤一：对状态图进行改造

(1) 增加状态X,Y,使之成为新的唯一的初态和终态。从X引ε弧到原初态结点, 从原终态结点引ε弧到Y结点。

(2) 对状态图进一步进行如下形式的改变

4