编译原理_第3章_第1节_词法分析、DFA、NFA和其转换

编译原理词法NFADFA的确定化和化简编译原理中的词法分析主要包括以下步骤：词法分析器将输入的源程序文本转化为一个个单词（token），即词法单元。

在词法分析过程中，使用的主要工具是有限自动机(NFA)和确定的有限自动机(DFA)。

NFA(DFA)的确定化是指将一个非确定的有限自动机转化为一个确定的有限自动机。

非确定有限自动机具有多个可能的转换路径，而确定有限自动机每个状态只能有一个转换路径。

确定化的目的是简化自动机的状态图，减少转换的复杂性，便于理解和实现。

确定化的过程一般包括以下步骤：1）初始化：将NFA的起始状态作为DFA的起始状态，并为其创建一个新的DFA状态。

2）闭包运算：对于DFA中的每个状态，根据NFA的ε-转换，计算其ε-闭包（即能够通过ε-转换到达的状态集合）。

3）转换运算：对于DFA中的每个状态和每个输入符号，根据NFA的转换函数，计算DFA中该输入下的状态转移集合。

4）如果新生成的DFA状态集合不在已有的DFA状态集合中，则将其加入到DFA状态集合中，并进行闭包和转换运算；如果已存在，则继续下一个输入符号的转换运算。

5）重复步骤4，直到不再生成新的DFA状态集合。

化简是指对于一个确定的有限自动机(DFA)，将其中无用的状态进行合并，得到一个更加简洁的自动机。

化简的目的是减少状态数目，提高运行效率和存储效率。

化简的过程一般包括以下步骤：1）初始化：将DFA状态分为两个集合，一个是终止状态集合，一个是非终止状态集合。

2）将所有的等价状态划分到同一个等价类中。

3）不断迭代以下步骤，直到不能再划分等价类为止：a）对于每对不同的状态p和q，若存在一个输入符号a，通过转移函数计算得到的状态分别位于不同的等价类中，则将该状态划分到不同的等价类中。

b）对于每个等价类中的状态集合，将其进一步划分为更小的等价类。

最终，得到的化简DFA状态图比原始DFA状态图要小，且功能等价。

nfa转换为dfa编译原理 c++有限自动机（NFA）和确定有限自动机（DFA）是计算机科学中有限状态自动机的两种形式。

NFA可以接受多个转移状态，而DFA则只能有一个转移状态。

NFA到DFA的转换是一个重要的编译原理问题。

以下是NFA转换为DFA的步骤：1. 确定NFA的开始状态和接受状态。

2. 对于每个输入符号，确定NFA的转换规则和转换后的状态。

3. 重复第二步，直到我们不能获得新的状态。

4. 标记DFA中的状态，即从NFA的多个状态中派生出的状态。

5. 为DFA添加开始状态和接受状态。

开始状态是NFA的开始状态的ε闭包。

6. 对于每个输入符号，使用NFA的转移规则来定义DFA中的转移。

7. 扫描DFA的状态表，并删除不可到达的状态。

下面是在C++中实现的NFA到DFA转换过程的伪代码：//定义状态类class State{public:string name;unordered_map<char, set<string>> transitions;bool is_final_state;};//定义NFA类class NFA{public:State start_state;set<State> final_states;unordered_set<State> all_states;};//定义DFA类class DFA{public:State start_state;set<State> final_states;unordered_set<State> all_states;};//NFA转换为DFADFA ConvertToDFA(NFA nfa){//创建DFA对象DFA dfa;//确定开始状态dfa.start_state = nfa.start_state;//确定接受状态dfa.final_states = nfa.final_states;//添加开始状态到DFA的所有状态dfa.all_states.insert(dfa.start_state);while (有新的状态可以加入DFA){//从DFA中选择一个未标记的状态State current_state = 选择一个未标记的状态;for (每个输入符号a){//根据当前状态的a过渡创建新状态State new_state = 创建新状态;//从当前状态开始，获得状态a的ε闭包set<State> epsilon_closure = current_state.获取状态a的ε闭包;//通过NFA的规则从当前状态和ε闭包中跳转到新状态set<State> transition_states = 通过NFA规则从当前状态和ε闭包中跳转到新状态;//确定新状态是否应该成为DFA的接受状态bool is_final_state = 确定新状态应该成为DFA的接受状态;//设置新状态的属性new_ = 新状态的名称;new_state.transitions = 转移函数;new_state.is_final_state = is_final_state;//将状态添加到DFA中dfa.all_states.insert(new_state);}}return dfa;}这是将NFA转换为DFA的基本伪代码。

[编译原理代码][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.实验原理一个确定的有限自动机（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的特例。

第3章词法分析习题答案1．判断下面的陈述是否正确。

（1）有穷自动机接受的语言是正规语言。

(√)（2）若r1和r2是Σ上的正规式，则r1|r2也是Σ上的正规式。

(√)（3）设M是一个NFA，并且L(M)={x,y,z}，则M的状态数至少为4个。

(× )（4）设Σ={a,b}，则Σ上所有以b为首的符号串构成的正规集的正规式为b*(a|b)*。

(× )（5）对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。

(√)（6）对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。

(√) （7）一个DFA，可以通过多条路识别一个符号串。

(× )（8）一个NFA，可以通过多条路识别一个符号串。

(√)（9）如果一个有穷自动机可以接受空符号串，则它的状态图一定含有 边。

(× )（10）DFA具有翻译单词的能力。

(× )2.指与出正规式匹配的串.（1)(ab|b)*c 与后面的那些串匹配？ababbc abab c babc aaabc（2）ab*c*(a|b)c 与后面的那些串匹配？ acac acbbc abbcac abc acc（3）(a|b)a*(ba)* 与后面的那些串匹配? ba bba aa baa ababa答案（1) ababbc c babc（2) acac abbcac abc（3) ba bba aa baa ababa3. 为下边所描述的串写正规式，字母表是{0, 1}.（1)以01 结尾的所有串（2)只包含一个0的所有串（3) 包含偶数个1但不含0的所有串（4)包含偶数个1且含任意数目0的所有串（5)包含01子串的所有串（6)不包含01子串的所有串答案注意 正规式不唯一（1)(0|1)*01（2)1*01*（3)(11)*（4)(0*10*10*)*（5)(0|1)*01(0|1)*（6)1*0*4.请描述下面正规式定义的串. 字母表{x, y}.（1) x(x|y)*x（2)x*(yx)*x*（3) (x|y)*(xx|yy) (x|y)*答案（1)必须以 x 开头和x结尾的串（2)每个 y 至少有一个 x 跟在后边的串 （3)所有含两个相继的x或两个相继的y的串5．处于/* 和 */之间的串构成注解，注解中间没有*/。

编译原理NFA转化为DFA的转换算法及实现编译原理是研究计算机程序语言的一门学科，其中一项重要的内容就是自动机理论，包括NFA（非确定性有限自动机）和DFA（确定性有限自动机）的转换。

NFA到DFA转换算法的实现分为几个关键步骤，下面将逐一进行介绍。

首先，我们需要了解NFA和DFA的基本概念。

NFA是一种具有状态、输入字母表和状态转移函数的自动机模型，允许多个状态同时转移到其他状态。

而DFA则是一种状态转移函数确定的自动机模型，每个输入字符只能引发一条状态转移。

接下来，我们将介绍NFA到DFA的转换算法。

1. 子集构造法（Subset Construction）子集构造法是将NFA转化为DFA的一种常用算法。

该算法的基本思想是，将NFA的每个状态集表示为DFA的状态。

转换过程如下：-创建DFA的初始状态集，初始状态集即为NFA的初始状态的ε闭包。

-逐个处理DFA的状态集，对于每个状态集，针对输入字符进行转移，计算新的状态集的ε闭包。

-若新的状态集已存在于DFA中，则不需要再次处理，若不存在，则将其加入到DFA中。

-迭代上述步骤，直至没有新的状态集加入。

2. ε闭包（ε-closure）ε闭包是指在NFA中的一些状态集S中，能够通过连续零个或多个ε转移到达的状态集合。

在转换过程中，需要计算新的状态集的ε闭包，来确定DFA的状态集。

具体步骤如下：-初始化ε闭包为输入的状态集S。

-对于S中的每个状态，获取其所有的ε转移目标状态，并将其添加到ε闭包中。

-重复上述步骤，直到ε闭包不再发生变化为止。

3. 状态转移（Transition）在NFA中，状态可以同时转移到多个状态。

而在DFA中，每个状态只能转移到一个状态。

因此，在转换过程中，需要确定每个状态在一些输入字符下的转移目标。

-对于每个状态集S、输入字符a，计算S在输入字符a下的转移目标状态集，即计算S中每个状态通过输入字符a能够到达的状态集。

-根据计算的转移目标状态集，将其作为DFA中S状态在输入字符a下的转移目标。

基本定义NFA，也称不确定的有穷自动机，是由一个五元式定义的数学模型，特点是它的不确定性，即在当前状态下，读入同一个字符，可能有多个下一状态。

DFA，也称确定的有穷自动机，也是由一个五元式定义的数学模型，相对的特点是它的确定性，即在当前状态下，读入同一个字符，最多有一个后继状态。

NFA与DFA的矩阵表示一个NFA或者DFA还可以用一个矩阵[5]表示，矩阵也可以说是状态转换表，它的优点是可以快速访问给定的状态在给定的输入字符时能转换到的状态集。

矩阵，每个状态一行，每个输入符号和ε（如果有需要的）各占一列，表的第i行中与输入符号a对应的表项是一个状态集合，表示NFA或者DFA在状态i输入a时所能到达的状态集合（DFA的集合唯一），即δ（i，a）[6]。

（7）如图可用表表示：NFA状态转换表DFA状态转换表NFA向DFA的转换的思路从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态DFA使用它的状态记录在NFA读入一个输入符号后可能达到的所有状态[4]。

NFA和DFA之间的联系在非确定的有限自动机NFA中,由于某些状态的转移需从若干个可能的后续状态中进行选择，故一个NFA对符号串的识别就必然是一个试探的过程。

这种不确定性给识别过程带来的反复，无疑会影响到FA的工作效率。

而DFA则是确定的,将NFA转化为DFA将大大提高工作效率,因此将NFA转化为DFA是有其一定必要的。

子集构造法已证明：非确定的有限自动机与确定的有限自动机从功能上来说是等价的，也就是说，我们能够从：NFA M使得L(M)=L(M’)为了使得NFA确定化，我们首先给出两个定义：定义1:集合I的ε-闭包：令I是一个状态集的子集，定义ε-closure（I）为：1）若s∈I，则s∈ε-closure（I）；2）若s∈I，则从s出发经过任意条ε弧能够到达的任何状态都属于ε-closure（I）。

词法分析(1)---词法分析的有关概念以及转换图词法分析是编译的第一个阶段，前面简介中也谈到过词法分析器的任务就是：字符流------>词法记号流这里词法分析和语法分析会交错进行，也就是说，词法分析器不会读取所有的词法记号再使用语法分析器来处理，通常情况下，每取一个词法记号，就送入语法分析器进行分析，图解：词法分析器是编译器中与源程序直接接触的部分，因此词法分析器可以做诸如1). 去掉注释，自动生成文档(c#中的///注释)2). 提供错误位置(可以通过记录行号来提供)，当字符流变成词法记号流以后，就没有了行的概念3). 完成预处理，比如宏定义1. 词法记号，词法单元(lexeme)，模式模式是一种规则每个词法单元都有一个特定记号比如 int a=3，这里 int，a，＝，3都是词法单元，每个词法单元都属于某个词法记号，比如3就是"num"这个词法记号的一个词法单元，而模式规定了什么样的字符串的词法记号是什么样的(模式是一种规则)某一特定模式规定了某个词法记号下的一类词法单元，比如：模式：用字母开头的包含字母和数字的串上面模式的词法记号：id(所有符合上面模式的字符串的记号都是id)词法单元：a123 或者 aabc 等词法记号举例(简称为记号)：1) 每个的关键字都有属于自己的一个记号，比如关键字for，它可以使用记号f or；关键字int，可以使用记号int2) 所有的关系运算符只有一个记号，比如 >=,<=都用记号relation3) 所有的标识符只有一个记号，比如a123,aab使用记号id4) 所有的常数只有一个记号，比如123,22,32.3,23E10使用记号num5) 所有的字符串只有一个记号，比如"123","ab1"使用记号literal在实际的编译器设计中，词法记号，一般用一个整形数字表示词法记号的属性：我们喜欢用<词法记号, 属性>这个二元组来描述一个词法单元，比如，对于源代码：position := initial + rate * 60对于词法单元 +，我们可以使用 <add_op, '+'> 来表示。