编译原理课程设计

合肥工业大学 计算机与信息学院

课程设计

编译原理课程设计

专业班级：

学 号：

姓 名：

引 言

本题的题目要求为: 对给定的正规式r1、r2，已知它们的NFA分别为M1、M2(其状态转换矩阵及初态、终态信息分别保存在指定文件中)。构造一程序，由此程序构造正规式r1r2（或运算）的NFA(将其状态转换矩阵及初态、终态信息保存在指定文件中)。

程序实现前,需要两个文件存放正规式r1和r2,连接运算成功后,需要将新的正规式存放在新的文件中.故本实验共有三个文件:nfa1.txt、nfa2.txt、nfa.txt，其中nfa1.txt、nfa2.txt为实验运行前建立的，nfa.txt是运行程序后程序建立的，存放的是连接后的正规式。

本课程设计用C++编写，用到了文件的输入输出流，连接运算并

不复杂，故程序并不复杂。

一．概述

1．1设计内容

1．2 设计要求

对给定的正规式r1、r2，已知它们的NFA分别为M1、M2(其状态转换矩阵及初态、终态信息分别保存在指定文件中)。构造一程序，由此程序构造正规式r1r2（或运算）的NFA(将其状态转换矩阵及初态、终态信息保存在指定文件中)。

构造正规式r1r2（或运算）的NFA的程序实现。

二．设计的基本原理

2.1 正规式与有限自动机的等价性

(1)对任何FAM，都存在一个正规式r，使得L(r)＝L(M). (2)对任何正规式r，都存在一个FAM，使得L(M)=L(r).

2.2 状态转换图的合并

三 . 程序设计

3.1 总体方案设计

由于此题目较为简单,所以总体上有三个函数,分别是OnFile1(),OnFile2（）和 OnRun(),OnRun()函数完成r1、r2的或运算，而OnFile1()和OnFile2（）函数完成对OnRun(()函数的调用。

3.2 各模块设计

本程序仅有一个函数，就是 OnRun()。其中有几个功能模块：

1) 文件的读与写,即将nfa1、nfa2写入输入文件流，将nfa与输出文件流关联;

2) 正规式的或运算与输出(含有对原正规式的输出); 3) 关闭文件输入输出流.

四． 程序测试

1.r1的NFA为M1, 其状态转换矩阵及初态、终态信息为(&表示空串): 5 -9999(初态) 6 -9999(终态) 5 a 5# 5 b 5# 5 & 1# 1 a 3# 1 b 4# 3 a 2# 4 b 2# 2 & 6# 6 a 6# 6 b 6@ 状态转换图:

本文来源：https://www.bwwdw.com/article/5d9d.html