编译原理_第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的特例。