编译原理(2)词法_2(NFA、DFA的确定化和化简)

实用文档2016.11.02不确定有穷状态自动机的确定化目录一、实验名称 (2)二、实验目的 (2)三、实验原理 (2)1、NFA定义 (2)2、DFA的定义 (2)3、closure函数 (2)4、move函数 (3)四、实验思路 (3)1、输入 (3)2、closure算法 (3)3、move算法 (3)4、构造子集 (4)5、输出 (4)五、实验小结 (4)1、输入存储问题 (4)2、closure算法问题 (4)3、输出问题 (5)六、附件 (5)1、源代码 (5)2、运行结果截图 (7)一、实验名称不确定有穷状态自动机的确定化二、实验目的输入：非确定有穷状态自动机NFA输出：确定化的有穷状态自动机DFA三、实验原理1、NFA定义一个不确定的有穷自动机M是一个五元组，M=(K,E,f,S,Z)其中a.K是一个有穷集，它的每个元素称为一个状态；b.E是一个有穷字母表，它的每个元素称为一个输入符号；c.f是一个从K×E*到K的子集的映像，即：K*E*->2k，其中2k表示K的幂集；d.S包含于K，是一个非空初态集；e.Z包含于K，是一个终态集。

2、DFA的定义一个确定的有穷自动机M是一个五元组，M=(K,E,f,S,Z)其中a.K是一个有穷集，它的每个元素称为一个状态；b.E是一个有穷字母表，它的每个元素称为一个输入符号；c.f是转换函数，是K×E->K上的映像，即，如f(ki,a)=kj(ki∈K,kj∈K)就意味着，当前状态为ki，输入字符为a时，将转换到下一状态kj，我们把kj称作ki的一个后继状态；d.S∈K，是唯一的一个初态；e.Z包含于K，是一个终态集，终态也称可接受状态或结束状态。

3、closure函数状态集合I的ε—闭包，表示为ε—closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。

4、move函数状态集合I的a弧转换，表示为move(I,a)，定义为状态集合J，其中J是所有那些从I中的某一状态经过一条a弧而到达的状态的全体。

深圳大学实验报告课程名称：编译原理
实验项目名称：词法分析技术及其应用
学院：计算机与软件学院
专业：软件工程
指导教师：蔡树彬
报告人学号：
实验时间：2015年11月4日至12月30日实验报告提交时间：2015年12月31日
教务处制
首先定义一个数组，逐个判断输入的字符串中的字符是否属于数组，根据无符号数的定义和状态转移图进行识别。

对输入的字符串从0状态开始，如果遇到‘d’,’·’,’E’,’+/
上图进行相应状态，扫描字符串结束后，如果处于状态1,2,6，代表能到达终态，即扫描到的字符串是无符号数。

同时定义两个字符串储存扫描的字符串属于无符号数部分和其
实验2_1_2结果截图：实验2_2结果截图：。

编译原理习题解答参考1.计算机执行用高级语言编写的程序的途径有哪些？它们之间主要区别是什么？答：计算机执行用高级语言编写的程序途径有两种：解释方式和编译方式。

解释方式下直接对源程序进行解释执行，并得到计算结果，特点是计算机并不事先对高级语言进行全盘翻译将其全部变为机器代码，而是每读入一条语句，就用解释器将其翻译为机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如些反复，即边翻译边执行；编译方式下对源程序的执行需要经过翻译阶段和运行阶段才能得到计算结果，其特点是计算机事先对高级语言进行全盘翻译将其全部变为机器代码，再统一执行，即先翻译后执行。

简单来说解释方式不生成目标代码，编译方式生成目标代码。

2.名字与标识符的区别是什么？答：在程序设计语言中，凡是以字母开头的有限个字母数字的序列都是标识符。

当给予一个标识符确切的含义后，该标识符就叫做一个名字。

标识符是一个没有意义的字符序列，而名字有确切的含义，一个名字代表一个存储单元，该单存放该名字的值。

此外，名字还有属性（如类型和作用域等）。

如objectint, 作为标识符，它没有任何含义，但作为名字，它可能表示变量名、函数名等。

3.许多编译程序在真正编译之前都要进行预处理操作，请问预处理的目的是什么？预处理主要做哪些工作？答：在源程序中有时存在多个连续的空格、回车、换行及注释等编辑性字符，它们不是程序的必要组成部分，它们的意义只是改善程序的易读性和易理解性。

为了降低编译程序的处理负担，许多编译程序在编译之前通过预处理工作将这些部分删除。

预处理的主要工作是对源程序进行格式方面的规范化处理，如去掉注释、将回车换行变成空格、将多个空格替换为一个空格等。

P35 4，6，7，8，9，11（1，2）4．答：256，86．（1）答：所产生的语言是：所有正整数集，且可以以0打头；0127，34，568的推导略。

7．答：S→ABD|AD|DA→2|4|6|8|DB→0|A|B0|BAD→1|3|5|7|98．答：略。

[编译原理代码][NFA转DFA并最⼩化DFA并使⽤DFA进⾏词法分析]#include <iostream>#include <vector>#include <cstring>#include "stack"#include "algorithm"using namespace std;int NFAStatusNum,AlphabetNum,StatusEdgeNum,AcceptStatusNum;char alphabet[1000];int accept[1000];int StartStatus;int isDFAok=1;int isDFA[1000][1000];/** NFA状态图的邻接表*/vector<vector<int>> Dstates;int Dstatesvisit[1000];int Dtran[1000][1000];vector<int> Dtranstart;vector<int> Dtranend;int isDtranstart[1000];int isDtranend[1000];class Edge{public:int to,w,next;} ;Edge edge[10000];int edgetot=0;int Graph[1000];void link(int u,int v,int w){edge[++edgetot].to=v;edge[edgetot].w=w;edge[edgetot].next=Graph[u];Graph[u]=edgetot;}void input(){int u,v,w;memset(Dtran,-1,sizeof(Dtran));scanf("%d %d %d %d\n",&NFAStatusNum,&AlphabetNum,&StatusEdgeNum,&AcceptStatusNum);for(int i=1;i<=AlphabetNum;i++){ //读⼊字母表scanf("%c",&alphabet[i]);}for(int i=1;i<=AcceptStatusNum;i++){scanf("%d",&accept[i]);}//开始状态序号scanf("%d",&StartStatus);for(int i=0;i<StatusEdgeNum;i++){scanf("%d%d%d\n",&u,&v,&w);link(u,v,w);if(isDFA[u][v]==0){isDFA[u][v]=1;}else{isDFAok=0;}if(w==0){isDFAok=0;}}//读⼊测试字符串}void e_clouser(vector<int> &T,vector<int> &ans){int visit[1000];memset(visit,0,sizeof(visit));stack<int> Stack;//T all push in Stack and copy to ansfor (int i=0;i < T.size();++i){Stack.push(T[i]);ans.push_back(T[i]);visit[T[i]]=1;while(Stack.empty()!=1){int t = Stack.top(); Stack.pop();for(int p=Graph[t];p!=0;p=edge[p].next){if(edge[p].w==0){if(visit[edge[p].to]==0){visit[edge[p].to]=1;Stack.push(edge[p].to);ans.push_back(edge[p].to);}}}}sort(ans.begin(),ans.end());}void move(vector<int> &T,int a,vector<int> &ans){ int visit[1000];memset(visit,0,sizeof(visit));for(int i=0;i<T.size();i++) {int t=T[i];for (int p = Graph[t]; p != 0; p = edge[p].next) { if (edge[p].w == a) {if (visit[edge[p].to] == 0) {visit[edge[p].to] = 1;ans.push_back(edge[p].to);}}}}}bool notin(vector<int> &a,int &U){for(int i=0;i<Dstates.size();i++){int ok=1;if(Dstates[i].size()==a.size()){for(int j=0;j<a.size();j++){if(Dstates[i][j]!=a[j]){ok=0;break;}}if(ok==1) {U=i;return false;}}}U=Dstates.size();return true;}void nfatodfa(){vector<int> s,t;s.push_back(StartStatus);e_clouser(s,t);Dstates.push_back(t);stack<int> Stack;Stack.push(Dstates.size()-1);while(Stack.empty()!=1){int T=Stack.top();Stack.pop();int U;for(int i=1;i<=AlphabetNum;i++){vector<int> ans,ans2;move(Dstates[T],i,ans2);e_clouser(ans2,ans);if(notin(ans,U)){Dstates.push_back(ans);Stack.push(Dstates.size()-1);}Dtran[T][i]=U;}}}void getDtranStartEnd(){for(int i=0;i<Dstates.size();i++){int ok=1;for(int j=0;j<Dstates[i].size();j++){if(Dstates[i][j]==StartStatus){Dtranstart.push_back(i);isDtranstart[i]=1;}for(int k=1;k<=AcceptStatusNum;k++){if(Dstates[i][j]==accept[k]){ok=0;Dtranend.push_back(i);isDtranend[i]=1;}}}}}}vector<vector<int>> newDstates;int newDstatesvisit[1000];int newDtran[1000][1000];int set[1000];vector<int> newDtranstart;vector<int> newDtranend;int isnewDtranstart[1000];int isnewDtranend[1000];void simple(){int visit[1000];memset(visit,0,sizeof(visit));vector<int> a,b;//接受结点加⼊afor(int i=0;i<Dtranend.size();i++){a.push_back(Dtranend[i]);visit[Dtranend[i]]=1;set[Dtranend[i]]=0;}//剩余结点加⼊bfor(int i=0;i<Dstates.size();i++){if(visit[i]==0){b.push_back(i);set[i]=1;}}newDstates.push_back(a);newDstates.push_back(b);while(1){int ok=0;for(int i=0;i<newDstates.size();i++){for (int k = 1; k <= AlphabetNum; k++) {for(int j=1;j<newDstates[i].size();j++) {int pp= Dtran[newDstates[i][0]][k];int u = newDstates[i][j], v = Dtran[u][k];if (set[v] != set[pp] ) {//将u剥离newDstates[i].erase(newDstates[i].begin() + j); vector<int> temp;temp.push_back(u);set[u] = newDstates.size();newDstates.push_back(temp);ok = 1;break;}if (ok == 1) break;}if(ok==1) break;}if(ok==1) break;}if(ok==0) break;}//isnewDtranstart,isnewDtranend,newDtranfor(int i=0;i<Dstates.size();i++) {for (int j = 1; j <= AlphabetNum; j++) {newDtran[set[i]][j]=set[Dtran[i][j]];}if(isDtranend[i]==1)isnewDtranend[set[i]]=1;if(isDtranstart[i]==1)isnewDtranstart[set[i]]=1;}//isnewDtranstart,isnewDtranend}bool dfa(char *S){int status=0;for(int i=0;i<newDstates.size();i++){if(isnewDtranstart[i]==1){status=i;}}for(int i=0;i<strlen(S);i++) {//这⾥我偷懒了,懒得弄个map存映射,直接对这个例⼦进⾏操作,就是 S[i]-'a'+1; int p=S[i]-'a'+1;status=newDtran[status][p];}if(isnewDtranend[status]==1) return true;else return false;}int main() {freopen("E:\\NFATODFA\\a.in","r",stdin);input();if(isDFAok==0){printf("This is NFA\n");nfatodfa();}else{printf("This is DNA\n");}//打印DFAprintf("\nPrint DFA's Dtran:\n");printf(" DFAstatu a b");getDtranStartEnd();for(int i=0;i<Dstates.size();i++){printf("\n");if(isDtranstart[i]==1)printf("start ");else if(isDtranend[i]==1)printf("end ");else printf(" ");printf("%5c ",i+'A');for(int j=1;j<=AlphabetNum;j++)printf("%5c ",Dtran[i][j]+'A');}printf("\nPrint simple DFA's Dtran:\n");simple();printf(" DFAstatu a b");for(int i=0;i<newDstates.size();i++){printf("\n");if(isnewDtranstart[i]==1)printf("start ");else if(isnewDtranend[i]==1)printf("end ");else printf(" ");printf("%5c ",i+'A');for(int j=1;j<=AlphabetNum;j++)printf("%5c ",newDtran[i][j]+'A');}printf("\n");char S[1000];while(scanf("%s\n",S)!=EOF){if(dfa(S)){printf("%s belongs to the DFA\n",S);}elseprintf("%s don't belong to the DFA\n",S);}return 0;}。

第一章一．填空题1．编译程序的工作过程一般可以划分为词法分析、语法分析、语义分析与中间代码产生、优化和生成目标程序等几个基本阶段，同时还伴有符号表管理和出错处理。

2．若源程序是用高级语言编写的，目标程序是汇编或机器语言，则其翻译程序称为编译程序。

3．编译方式与解释方式的根本区别在于运行目标程序时的控制权在解释器而不是目标程序。

4．翻译程序是这样一种程序，它能将用甲种语言书写的程序转换成与其等价的乙种语言书写的程序。

5．对编译程序而言，输入数据是高级语言（源）程序，输出结果是低级语言（目标）程序。

6．运行编译程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称目标机。

7．当把编译程序划分成编译前端和编译后端时，前端主要由与源语言有关但与目标机无关的部分组成，编译后端包括编译程序中与目标机有关的部分，编译后端不依赖于源语言而仅仅依赖于中间语言。

8．描述词法规则的有效工具是词法分析器，通常使用语法分析器来描述语法规则，使用语义分析（与中间代码产生）器描述语义规则。

二．综合题（该答案仅供参考）1、给出C语言编译程序对下面语句进行编译时从词法分析到目标代码生成5个分析阶段的分析过程。

c=a+b*30;（1）给出每个阶段的输入和输出代码或其它数据形式。

（2）给出符号表，说明在哪些阶段会对符号表进行填写或查找。

（3）编译过程是否进行了代码优化？若有，请指出优化之处，并给出属于哪种优化？答：词法分析：出入源程序；输出识别出的记号流。

c=a+b*30 id1=id2+id3*30语法分析器：输入记号流，构造句子结构；输出语法树。

=id1 +id2 *id3 30语义分析与中间代码生成：出入语法树，输出中间代码变量地址数值注：赋值阶段会对符号表进行填写或查找1. id1 0 c （itr，30，，t1）2. id2 4 x （*，id3，t1，t2）3. id3 8 y （+，id2，t2，t3）4. t1 12 30 （=，t3，，id1）优化：1.（*，id3，30.0，t1）2.（+，id2，t1，id1）精简掉多余的复写传播mulf #30.0，r2 mov id2，r1 sub r1，r2 mov r2，id1第二章一．填空题1．上下文无关文法包括以下四个组成部分：一组终结符号，一组非终结符号，一个开始符号，以及一组产生式。

编译原理实验报告实验名称不确定有限状态自动机的确定化实验时间院系计算机科学与技术学院班级学号姓名1.试验目的输入：非确定有限（穷）状态自动机。

输出：确定化的有限（穷）状态自动机2.实验原理一个确定的有限自动机（DFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中：（1）K是一个有穷非空集，集合中的每个元素称为一个状态；（2）∑是一个有穷字母表，∑中的每个元素称为一个输入符号；（3）F是一个从K×∑→K的单值转换函数，即F（R，a）＝Q，（R，Q∈K）表示当前状态为R，如果输入字符a，则转到状态Q，状态Q称为状态R的后继状态；（4）S∈K，是惟一的初态；（5）Z⊆K，是一个终态集。

由定义可见，确定有限自动机只有惟一的一个初态，但可以有多个终态，每个状态对字母表中的任一输入符号，最多只有一个后继状态。

对于DFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFA M所接受。

若M的初态结点同时又是终态结点，则称ε可为M所接受（或识别），DFA M所能接受的全部字符串（字）组成的集合记作L（M）。

一个不确定有限自动机（NFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中：（1）k是一个有穷非空集，集合中的每个元素称为一个状态；（2）∑是一个有穷字母表，∑中的每个元素称为一个输入符号；（3）F是一个从K×∑→K的子集的转换函数；（4）S⊆K，是一个非空的初态集；（5）Z⊆K，是一个终态集。

由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是：（1）NFA的初始状态S为一个状态集，即允许有多个初始状态；（2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。

即DFA中的F是单值函数，而NFA中的F是多值函数。

因此，可以将确定有限自动机DFA看作是不确定有限自动机NFA的特例。

编译原理文字总结编译原理文字总结1.高级程序设计语言的翻译主要有两种方式：编译和解释。

2.编译过程概述：(1)词法分析：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或符号）如基本字，标识符，常数，算符和界符。

(2)语法分析：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如短语，子句，句子，程序段和程序等(3)语义分析与中间代码产生：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。

包括静态语义检查和中间代码的翻译。

(4)优化：对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。

(5)目标代码生成：把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。

编译程序结构框图3．文法是表述语言的语法结构的形式规则。

4.所谓上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的。

一个上下文无关文法G包括四个组成部分：一组终结符号，一组非终结符号，一个开始符号，以及一组产生式。

5.形式上说，一个上下文无关文法G是一个四元式（VT,VN,S,＆）其中VT是一个非空有限集，它的每个元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=；S是一个非终结符号，称为开始符号；&是一个产生式集合，每个产生式的形式是P→a，其中P属于VN，a属于（VT∪VN）*。

开始符号S至少必须在某个产生式的左部出现一次。

6.推导每前进一步总是引用一条规则（产生式）。

7.假定G是一个文法，S是它的开始符号。

如果Sa，则称a是一个句型（0步或若干步）。

仅含终结符号的句型是一个句子。

文法G所产生的句子的全体是一个语言，将它记为L(G)。

L(G)=｛a|Sa&a∈VT*｝例如终结符号串（i*i+i）是文法（2.1）的一个句子。

第二章2.3叙述由下列正规式描述的语言(a) 0(0|1)*0在字母表{0, 1}上,以0开头和结尾的长度至少是2的01串(b) ((ε|0)1*)*在字母表{0, 1}上,所有的01串,包括空串(c) (0|1)*0(0|1)(0|1)在字母表{0, 1}上,倒数第三位是0的01串(d) 0*10*10*10*在字母表{0, 1}上,含有3个1的01串(e) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*在字母表{0, 1}上,含有偶数个0和偶数个1的01串2.4为下列语言写正规定义C语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀（本身除外）不以 */ 结尾。

［解答］ other → a | b | … other指除了*以外C语言中的其它字符other1 → a | b | …other1指除了*和/以外C语言中的其它字符 comment → /* other* (* ** other1 other*)* ** */(f) 由偶数个0和偶数个1构成的所有0和1的串。

［解答］由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况：x 偶数个0和偶数个1（用状态0表示）； x 偶数个0和奇数个1（用状态1表示）； x 奇数个0和偶数个1（用状态2表示）； x 奇数个0和奇数个1（用状态3表示）；所以，x 状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：偶数个0和奇数个1（状态1）x 状态0（偶数个0和偶数个1）读入0，则0和1的数目变为：奇数个0和偶数个1（状态2）x 状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：偶数个0和偶数个1（状态0）x 状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：奇数个0和奇数个1（状态3）x 状态2（奇数个0和偶数个1）读入1，则0和1的数目变为：奇数个0和奇数个1（状态3）x 状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：偶数个0和偶数个1（状态0）x 状态3（奇数个0和奇数个1）读入1，则0和1的数目变为：奇数个0和偶数个1（状态2）x 状态3（奇数个0和奇数个1）读入0，则0和1的数目变为：偶数个0和奇数个1（状态1）因为，所求为由偶数个0和偶数个1构成的所有0和1的串，故状态0既为初始状态又为终结状态，其状态转换图：由此可以写出其正规文法为：S0 → 1S1 | 0S2 | ε S1 → 1S0 | 0S3 | 1 S2 → 1S3 | 0S0 | 0 S3 → 1S2 | 0S1在不考虑S0 →ε产生式的情况下，可以将文法变形为： S0 = 1S1 + 0S2 S1 = 1S0 + 0S3 + 1 S2 = 1S3 + 0S0 + 0S3 = 1S2 + 0S1 所以： S0 = (00|11) S0 + (01|10) S3 + 11 + 00(1) S3 = (00|11) S3 + (01|10) S0 + 01 + 10(2) 解(2)式得： S3 = (00|11)* ((01|10) S0 + (01|10)) 代入(1)式得：S0 = (00|11) S0 + (01|10) (00|11)*((01|10) S0 + (01|10)) + (00|11) => S0 = ((00|11) + (01|10) (00|11)*(01|10))S0 + (01|10) (00|11)*(01|10) + (00|11) => S0 = ((00|11)|(01|10) (00|11)*(01|10))*((00|11) + (01|10) (00|11)* (01|10)) => S0 = ((00|1 1)|(01|10) (00|11)* (01|10))+因为S0→ε所以由偶数个0和偶数个1构成的所有0和1的串的正规定义为： S0 → ((00|11)|(01|10) (00|11)* (01|10))* (g) 由偶数个0和奇数个1构成的所有0和1的串。

编译原理nfa
编译原理中的NFA，是指非确定有限状态自动机（Nondeterministic Finite Automata）。

在计算机科学中，NFA是一种有限状态自动机，它可以用于描述一类模式匹配问题。

NFA由一组状态、一组输入符号、一个转移函数、一个初始状态和一组接受状态组成。

与确定性有限状态自动机（DFA）相比，NFA在某些方面具有更高的表达能力，因为它允许在同一时刻有多个状态，并且在输入符号为空时可以不进行转移。

但由于NFA的非确定性，使用NFA进行模式匹配时，需要进行转换和回溯，增加了计算的复杂度。

在编译原理中，NFA通常用于描述正则表达式的语法结构和匹配算法。

编译器在识别程序中的正则表达式时，会将其转换为NFA，并使用NFA进行模式匹配和语义分析。

通过这种方式，可以实现高效的正则表达式匹配和语法分析。

总之，NFA是编译原理中非常重要的概念，它为编译器设计和实现提供了一种有效的工具，能够实现正则表达式匹配和其他相关问题的解决。