武汉理工编译原理课设

1、学 号： 0121204930233课 程 设 计题 目正规文法G与有穷自动机FA相互转换学 院计算机科学与技术学院专 业软件工程班 级软件1201姓 名张立炜指导教师何九周2014年12月26日课程设计任务书学生姓名： 张立炜 专业班级： 软件1201 指导教师： 何九周 工作单位：计算机科学与技术学院题 目: 正规文法G与有穷自动机FA相互转换初始条件：程序设计语言:主要使用C语言的开发工具，或者采用LEX、YACC等工具，也可利用其他熟悉的开发工具。算法：可以根据编译原理课程所讲授的算法进行设计。要求完成的主要任务:（包括课程设计工作量及其技术要求，说明书撰写等具体要求）1. 明确课程设

2、计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求，学会设计的基本方法与步骤，学会如何运用前修知识与收集、归纳相关资料解决具体问题的方法。严格要求自己，要独立思考，按时、独立完成课程设计任务。2. 主要功能包括：利用算符优先分析方法和思想对某些语句进行语法分析与语义分析，生成相应的中间代码。学会正确运用语法规则，并能应用所学的方法解决存在的问题。给出语法分析方法及中间代码形式的描述、文法和属性文法的设计。3. 进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试，合理使用出错处理程序。4. 设计报告：要求层次清楚、整洁规范、不得相互抄袭。正文字数不少于0.3万字

3、。包含内容：课程设计的题目。目录。正文：包括引言、需求分析、总体设计及开发工具的选择，设计原则（给出语法分析方法及中间代码形式的描述、文法和属性文法的设计），数据结构与模块说明（功能与流程图）、详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。结束语。参考文献。附录：软件清单（或者附盘）。时间安排： 消化资料、系统调查、形式描述1天系统分析、总体设计、实施计划3天撰写课程设计报告书1天指导教师签名： 2014年 12月 26日系主任（或责任教师）签名： 2014年 12月 26日目录课程设计任务书11引言3 1.1目的31.2设计内容31.3设计原则42需求分析42

4、.1正规式42.2有限自动机（有穷自动机）52.3NFA向DFA的转换52.4正规式与有限自动机之间的转换63数据结构和模块说明63.1从正规文法到有限自动机63.11正规文法到有限自动机的等价性证明63.12 正规文法到有限自动机的构造方法83.2从有限自动机到正规文法83.21 有限自动机到正规文法的等价性证明83.22 有限自动机到正规文法的构造方法94详细设计105软件测试和结果146收获与体会.157结束语.168参考文献.171引言1.1目的1.理解正规文法与有限自动机（FA）的本质联系；2.掌握正规文法与有限自动机之间相互转化的算法原理；3.学会使用Visual C+等编程工具实

5、现正规文法与有限自动机之间的相互转化；1.2设计内容使用Visual C+/Visual C#等工具，设计软件MySoft_3，可以实现以下功能：1.根据用户输入的文本文件（*.txt）的名称，打开文件，并从文件中获取文法的产生式、非终结符、终结符、开始符等基本信息；2.判断该文法是否为正规文法，若是，则将其转化为有限自动机；3.根据用户输入的文本文件（*.txt）的名称，打开文件，并从文件中获取有限自动机的状态集、字母表、初态、终态集、转移函数等基本信息；4.判断该自动机是否合法，若合法，则将其转化为正规文法；1.3设计原则正规文法与有穷自动机有着特殊的关系，采用下面的规则可从正规文法G直接

6、构造一个有穷自动机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。2需求分析2.1正规式正规式：正则表达式，表示正规集的工具。一个正规式对应一个正规文法（3型文法）之间能够进行准换三个基本规则：A->xB,B->y  则 A=xy。A->

7、xA|y  则A=x*y  （x*代表x从1到无穷多个）A->x,A->y 则A=x|y正规式主要用到了递归的思想，无论遇到多复杂的正规式都可以拆分成上面这三种形式，然后进行解题。2.2有限自动机（有穷自动机）DFA（Deterministic Finite Automation ）：确定的有限自动机表达式：M=（S，f，So，Z）1.S为一个有限状态集合2.是一个字母表，它所包含的的每个元素称为一个输入字符；3.f是一个从SX（笛卡尔乘积）至S的单值部分映射。f（S，a）=s'意味着当现在的状态为s，输入字符a时，将转换到下一状态s'.s

8、9;为s的一个后继状态。4.SoS，是唯一的初态；5.ZS，是一个终态集。NFA（Nondeterministic Finite Automata）：不确定的有限自动机如果理解了有限自动机，则无限自动机和它的区别就是上面的第四项。SoS，它的初态不是唯一的，而是一个集合。2.3NFA向DFA的转换这个转换是一个比较简单的过程。1.如果有一个不确定的有限自动机，则可以转化为图的方式。此处不详述怎样转图的方式。2.先将初态确定，然后根据输入的每个元素可以得到哪些状态，依次列表。3.这些状态集合可以称为这个有限状态集合n个子集。按0,1,2的顺序编号。4.因为这些子集之间的关系是

9、输入一个确定值确定的，所以这些子集之间存在一些关系，即把这些子集的关系写出来完成NFA向DFA的转换。如果不懂可以从网上找一个例子进行理解。2.4正规式与有限自动机之间的转换任意的正规式都可以转换为上述三种的表现形式。在一个有限自动机转换为正规式时，就是考虑从初态到终态可以输入哪些数据到达。而这些数据可以用哪种正规式概括进来。3设计原则 3.1从正规文法到有限自动机 3.11正规文法到有限自动机的等价性证明定理1：对于每一个右线性正规文法GR和左线性正规文法GL，都存在一个有限自动机M与之等价。证明：1.设右线性文法GR=（VT,VN,S,P），将VN中每个非终结符视为状态符号，并增加一个新的

10、终止符号f，（f VN）。令M=(VN f，VT，d，S，f)，其中状态转换函数d由以下规则定义：若对某个A VN及a VT ，P中有产生式Aa，则令d(A，a)=f；对任意的A VN及a VT ，设P中左端为A右端第一个符号为a的所有产生式为AaA1aA2aAk（不包括Aa），则令d(A，a)= A1，A2，Ak。显然上述得到的M为一个NFA。到此，已说明存在一个FAM与该右线性文法对应，下面说明它们的等价性(L(GR)=L(M) )。对右线性正规文法GR，在S W的最左推导过程中，利用AaB一次就相当于在M中从状态A出发经标记为a的箭弧到达状态B(包括a=的情形)。在推导过程的最后，利用A

11、a一次则相当于在中从状态A出发经标记为a的箭弧到达终态f(包括a=的情形)。综上所述，在正规文法GR中，S W的充要条件是：在M中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于W，这就是说，W L(GR)当且仅当W L(M)，故L(GR)=L(M)。2. 设左线性文法GL=（VT,VN,S,P），将VN中每个非终结符视为状态符号，并增加一个新的初始状态符号q，（q VN）。令M=(VN q，VT，d，q，S)，其中状态转换函数d由以下规则定义：若对某个A VN及a VT ，P中有产生式Aa，则令d(q，a)=A；对任意的A VN及a VT ，设P中所有右端第一个符号为

12、A，第二个符号为a的所有产生式为A1Aa，A2Aa，AKAa，则令d(A，a)= A1，A2，Ak。显然上述得到的M为一个NFA。到此，已说明存在一个FAM与该左线性文法对应，下面说明它们的等价性(L(GL)=L(M) )。对左线性正规文法GL，在S W的最左推导过程中，利用BAa一次就相当于从状态A出发经标记为a的箭弧到达状态B(包括a=的情形)。在推导的最后，利用Aa一次则相当于在中从状态q出发经标记为a的箭弧到达状态A(包括a=的情形)。综上所述，在正规文法GL中，S W的充要条件是：在M中，从状态q到状态S有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于W，这就是说，W L(GL

13、)当且仅当W L(M)，故L(GL)=L(M)。3.12 正规文法到有限自动机的构造方法上述定理的证明采用了构造性的证明方法，由此可以得出由正规文法到有限自动机的构造方法。从右线性正规文法GR=(VT,VN,S,P)构造有限自动机M=( VN f，VT，d，S，f)的方法如下：将VN中每个符号视为一个状态符号，增加一个新的终态符号f，f VN；对于产生式Aa（a VT ），则构造d(A，a)=f；对于产生式AaA1（a VT ），则构造d(A，a)= A1。从左线性正规文法GL=(VT,VN,S,P)构造有限自动机M=( VN q，VT，d，q，S)的方法如下：将VN中每个符号视为一个状态符号

14、，增加一个新的初态符号q，q VN；对于产生式Aa（a VT ），则构造d(q，a)=A；对于产生式A1Aa（a VT ），则构造d(A，a)= A1。3.2从有限自动机到正规文法3.21 有限自动机到正规文法的等价性证明定理2：对于每一个有限自动机M，都存在一个右线性正规文法GR和左线性正规文法GL与之等价。证明：1.设DFAM=(S，d，S0，F)，分以下两种情况进行证明：（1）若S0 F，则令GR=(,S, S0, P)，其中P是由以下规则定义的产生式集合，对任何a 及A,B S，若d(A，a)=B，则：当B F时，令AaB；当B F时，令AaBa；显然，上述得到的文法为一个右线性正规文

15、法，下面说明它们的等价性(L(M)=L(GR) )。在DFAM中，对任何w *，不妨设w=a1a2ak，其中ai (i=1,2,k)，若S W，则存在一个最左推导：S0 a1A1 a1a2A2 a1aiAi a1aiai+1Ai+1 a1ak，因而，在M中存在一条从S0出发一次经过A1，Ak-1到达终态的通路，该通路上所有箭弧的标记依次为a1，ak。反之亦然。所以，w L(GR)当且仅当w L(M)，故L(M)=L(GR)。（2）若S0 F，因为d(S0,)= S0，所以 L(M)，但上面构造的L(GR)中不含。因此，需在文法中添加产生式S0，这样，就有L(M)=L(GR)。2. 设DFAM=

16、(S，d，S0，F)，分以下两种情况进行证明：（1）若S0 F，则令GL=(,S, X, P)，其中X F，P是由以下规则定义的产生式集合，对任何a 及A,B S，若d(A，a)=B，则：当AS0时，令BAa；当A=S0时，令BaAa；显然，上述得到的文法为一个左线性正规文法，下面说明它们的等价性(L(M)=L(GL) )。在DFAM中，对任何w *，不妨设w=a1a2ak，其中ai (i=1,2,k)，若存在一条从S0到X的通路，通路上所有箭弧的标记依次为a1，ak，则在GL中一定存在一个最左推导：X Akak Ak-1ak-1ak A2a2ak a1ak，即w L(GL)。反之亦然。所以，

17、w L(GL)当且仅当w L(M)，故L(M)=L(GL)。（2）若S0 F，则 L(M)，但上面构造的L(GL)中不含。因此，需在文法中添加产生式X，这样，就有L(M)=L(GL)。3.22 有限自动机到正规文法的构造方法上述定理的证明采用了构造性的证明方法，由此可以得出由有限自动机到正规文法的构造方法。从有限自动机M=( S，d，S0，F)构造右线性正规文法GR的方法如下：令GR=(,S, S0，P)，其中P是由以下规则定义的产生式集合：对任何d(A，a)=B,若B F，则令AaB；若B F，并且B状态有箭弧射出，则令AaBa；若B F，并且B状态没有箭弧射出，则令Aa；若S0 F，则令S

18、0。从有限自动机M=( S，d，S0，F)构造左线性正规文法GL的方法如下：令GL=(,S, X，P)，其中P是由以下规则定义的产生式集合：对任何d(A，a)=B,若A不是初始状态，则令BAa；若A是初始状态，并且A状态有箭弧射入，则令BAaa；若A是初始状态，并且A状态没有箭弧射入，则令Ba；若S0 F，则令X。4详细算法设计#include<iostream>using namespace std;int main()int n, m;/n为自动机状态的总数目/m为自动机终结符的数目int n_midd_stat, n_final_stat;/n_midd_stat为中间状态的

19、数目/n_final_stat为终态的数目cout << "请输入自动机共有的状态数目："cin >> n;char* stat = new charn;cout << "请输入开始状态："cin >> stat0;cout << "请输入中间状态的个数："cin >> n_midd_stat;cout << "请输入分别中间状态：" << endl;for(int i1 = 0; i1 < n_midd_stat

20、; 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 << "请输入终结符的数目："cin >> m;char* terminal = new charm;cout << "请分别输入终结

21、符：" << 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 = 0; i < n; i+)for(j = 0; j < n; j+)cout << "状态" << s

22、tati << "能否直接推出状态"<< statj;if(i = 0) && (j = 0)cout << "? (若能则输入相应的终结符，否则输入"0")"elsecout << "?"cin >> fij;cout << endl;/转换成对应的文法cout << "由此自动机转换成的对应的文法为：" << endl;cout << "G=("/&

23、lt;< 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 << ","cout <<terminali5;cout << ","cout << "P,&

24、quot;cout << stat0 << "),"cout << "其中P为：" << endl;for(i = 0; i < n; i+)for(j = 0; j < n; j+)if(fij != '0')cout << stati << "->" << fij << statj <<endl;/输出可接受状态增加的产生式，例如A->for(int i6 = 0; i6 < n

25、_final_stat; i6+)cout << statn_midd_stat + 1 + i6 << "->" << endl;return 0;5软件的测试与结果 测试程序使用的自动机用例：开始状态：A；中间状态：1个，为B；终态：2个，分别为C、D；终结符：2个，分别为a、b；装换关系为StatABCDA0a0bB00b0Ca00bD0b0b 收获与体会经过一个学期的编译原理相关内容的学习和几周的调试与编写程序，课程设计的任务终于完成了，在这过程中有出现过各种各样的问题与学习的不足，感谢传授我知识的老师和帮我一起调试解决问题的同学。做的过程中有许许