动机向正规文法的转换课程设计文档

1、学 号： 课 程 设 计题 目有穷自动机FA转换为正规文法G的程序设计学 院计算机学院专 业软件工程班 级姓 名指导教师何九周2010年6月12日目 录目录1课程设计任务书31设计目的 42设计内容内容 43设计环境与工具 44设计任务要求与说明 45.设计原则 46.简要分析与概要设计 47.详细算法描述 57.1程序总体流程图 57.2输入开始状态 57.3输入中间状态 57.4输入终态 67.5输入终结符 67.6构造自动机 67.7生成对应的正规文法 77.8输出得到的正规文法 77.9源程序清单 88软件的测试方法和测试结果179设计的特点、不足、收获与体会1210参考文献13本科生

2、课程设计成绩评定表14课程设计任务书学生姓名： 郭 滨 专业班级： 软件工程0704 指导教师： 何九周 工作单位： 计算机学院 题 目: 有穷自动机FA转换为正规文法G的程序设计 初始条件：程序设计语言:主要使用C语言的开发工具，或者采用LEX、YACC等工具，也可利用其他熟悉的开发工具。算法：可以根据编译原理课程所讲授的算法进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，说明书撰写等具体要求）设计报告书写要求与说明课程设计报告：要求层次清楚、整洁规范、不得相互抄袭。设计报告正文字数不少于0.3万字。课程设计报告书的内容应包括：1. 封面：学号、题目、学院、专业、班级、姓名

3、、指导老师、完成日期；2. 报告书的目录；3. 概述：设计题目，设计目的，设计任务内容、时间；4. 设计环境与工具；5. 设计原则：给出语法分析方法及中间代码形式的描述、文法和属性文法的设计或者词法分析方法及符号表和TOKEN代码的设计；6. 简要的分析与概要设计；7. 详细的算法描述，框图；8. 源程序清单(不打印，附盘)；9. 给出软件的测试方法和测试结果（打印）；10. 设计的特点、不足、收获与体会；11. 参考文献（按公开发表的规范书写）。课程设计报告书装订顺序：封面 课程设计任务书（由指导老师填写） 正文 评分表 封底时间安排：消化资料、系统调查、形式描述1天系统分析、总体设计、实施

4、计划3天撰写课程设计报告书1天指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日1. 设计目的课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。2. 设计任务内容 有穷自动机FA转换为正规文法G的程序设计。任意给定一个有穷自动机，求出其对应的正规

5、文法。3. 设计环境与工具Windows XP系统Visual C+ 6.0；4.设计任务要求与说明明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求，学会设计的基本方法与步骤，学会如何运用前修知识与收集、归纳相关资料解决具体问题的方法。严格要求自己，要独立思考，按时、独立完成课程设计任务。深入理解所学的编译原理相关知识，按照软件工程的设计方法进行简要的分析与概要设计，进行总体设计，详细设计、系统实施、调试。运用程序设计语言实现算法，编写相关程序。学会正确运用语法规则，并能应用优先关系和结合性解决二义性和冲突问题，有效而正确的利用各种分析方法和思想，合理使用出错处理程

6、序，上机调试通过。最后撰写课程设计报告。通过编程实践逐步提高分析问题，解决问题的能力。5.设计原则正规文法与有穷自动机有着特殊的关系，采用下面的规则可从正规文法G直接构造一个有穷自动机NFA M；使得L(M)=L(G)：（1）M的字母表与G的终结符相同；（2）为G中的每一个非终结符生成M的一个状态，G的开始符S是开始状态；（3）增加一个新状态Z，作为NFA的终态；（4）对G中的形如A->tB的规则（其中T为终结符或，A为非终结符的产生式），构造M的一个转换函数f(A,t)=B；（5）对G中形如A->t的产生式，构造M的一个转换函数f（A，t）=Z。6.简要分析与概要设计对于一个图形

7、表示的自动机，在程序中可以用一个二维数组表示该自动机的图，从开始状态开始，如果两个点直接连通，则从该状态可以直接推出另一个状态，对应于一个装换函数f(A,t)=B；那么就可以先遍历状态机的图形，如果两个点直接连通，就可以产生一个对应文法的产生式；对应文法产生式生成完毕，就是得到了对应的正规文法。7.详细算法描述7.1程序总体流程图 7.2输入开始状态 7.3输入中间状态 7.4输入终态 7.5输入终结符7.6构造自动机7.7生成对应的正规文法 7.8输出得到的正规文法 7.9源程序清单#include<iostream>using namespace std;int main()i

8、nt n, m;/n为自动机状态的总数目/m为自动机终结符的数目int n_midd_stat, n_final_stat;/n_midd_stat为中间状态的数目/n_final_stat为终态的数目cout << "请输入自动机共有的状态数目："cin >> n;char* stat = new charn;cout << "请输入开始状态："cin >> stat0;cout << "请输入中间状态的个数："cin >> n_midd_stat;cout &

9、lt;< "请输入分别中间状态：" << endl;for(int i1 = 0; i1 < n_midd_stat; i1+)cin >> stati1 + 1;n_final_stat = n - n_midd_stat - 1;cout << "最后分别输入终态：" << endl;for(int i2 = 0; i2 < n_final_stat; i2+)cin >> statn_midd_stat + 1 + i2;cout << "请输入终结

10、符的数目："cin >> m;char* terminal = new charm;cout << "请分别输入终结符：" << endl;for(int i3 = 0; i3 < m; i3+)cin >> terminali3;cout << endl;/构造自动机int i, j,k;char* f = new char*n;for(k=0;k<n;k+)fk=new charn;cout << "构造自动机：" << endl;for(i =

11、 0; i < n; i+)for(j = 0; j < n; j+)cout << "状态" << stati << "能否直接推出状态"<< statj;if(i = 0) && (j = 0)cout << "? (若能则输入相应的终结符，否则输入"0")"elsecout << "?"cin >> fij;cout << endl;/转换成对应的文法cout <

12、;< "由此自动机转换成的对应的文法为：" << endl;cout << "G=("/<< stat0;for(int i4 = 0; i4 < n; i4+)if(i4 != 0)cout << ","cout << stati4;cout << ","cout << ""for(int i5 = 0; i5 < m; i5+)if(i5 != 0)cout << ",

13、"cout <<terminali5;cout << ","cout << "P,"cout << stat0 << "),"cout << "其中P为：" << endl;for(i = 0; i < n; i+)for(j = 0; j < n; j+)if(fij != '0')cout << stati << "->" <<

14、fij << statj <<endl;/输出可接受状态增加的产生式，例如A->for(int i6 = 0; i6 < n_final_stat; i6+)cout << statn_midd_stat + 1 + i6 << "->" << endl;return 0;8.软件的测试方法和测试结果 测试程序使用的自动机用例：（1） 开始状态：A；（2） 中间状态：1个，为B；（3） 终态：2个，分别为C、D；（4） 终结符：2个，分别为a、b；（5） 装换关系为StatABCDA0a0bB00

15、b0Ca00bD0b0b（6）得到的结果如图：9.设计的特点、不足、收获与体会经过一周的努力，终于把编译原理这门课的课程设计做完了，由于学习理论的时候总是感觉这门课程特别的复杂，有许多繁琐的东西，起初以为课程设计的内容会更加的复杂，后来认真看了题目，和相对应于课本上的内容，我的这个题目还真的很简单，只是用到了“数组”、“图”这两个数据结构，再就是有两个二层嵌套的循环就能够应对这个题目了。由于时间有限，这次的课程设计中我没有考虑到不确定的自动机转换成正规文法的情况，在以后的学习中一定将这种更加复杂的情况考虑进去，让自己的程序更加的完整。经过一学期的编译原理这门课程的学习，我们深深的了解到了编译器结构的复杂程度，更了解了我们学习的高级语言的强大功能，我们做的课程设计只是一个完整编译器的冰山一角。后面还有更多需要我们更加需要懂得的东西。10.参考文献1吕映芝、张素琴、蒋维杜.编译原理（第二版）.北京：清华大学出版社,2004.2 张幸儿.编译原理.北京：科学出版社.1999年4月.3 陈意云.编译原