非确定有限自动机的确定化

编译原理复习例题(有些内容没有覆盖，比如优化、SLR（1）、LR（1）、LALR（1）等。

但要求至少要按照作业题的范围复习。

)一选择题1．编译的各阶段工作都涉及。

[A]词法分析[B]表格管理 [C]语法分析 [D]语义分析2．型文法也称为正规文法。

[A] 0 [B] 1 [C] 2 [D] 33．文法不是LL(1)的。

[A]递归 [B]右递归 [C]2型 [D]含有公共左因子的4．文法E→E+E|E*E|i的句子i*i+i*i有棵不同的语法树。

[A] 1 [B] 3 [C] 5 [D] 75．文法 S→aaS|abc 定义的语言是。

[A]{a2k bc|k>0} [B]{a k bc|k>0}[C]{a2k-1bc|k>0} [D]{a k a k bc|k>0}6．若B为非终结符，则 A→α.Bβ为。

[A]移进项目 [B]归约项目 [C]接受项目 [D]待约项目7．同心集合并可能会产生新的冲突。

[A]二义 [B]移进/移进 [C]移进/归约 [D]归约/归约8．代码优化时所依据的是。

[A]语法规则 [B]词法规则[C]等价变换规则 [D]语义规则9．表达式a-(-b)*c的逆波兰表示（@为单目减）为。

[A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-*10．过程的DISPLAY表是用于存取过程的。

[A]非局部变量[B]嵌套层次 [C]返回地址 [D]入口地址二填空题1．词法分析阶段的任务式从左到右扫描字符流，从而逐个识别一个个的单词。

2．对于文法G[E]：E→T|E+T T→F|T*F F→P^F|P P→(E)|i，句型T+T*F+i的句柄是。

3．最右推导的逆过程称为规范归约，也称为最左归约。

4．符号表的每一项是由名字栏和两个栏目组成。

在目标代码生成阶段，符号表是的依据。

三判断题（认为正确的填“T”，错的填“F”）【】1．同心集的合并有可能产生“归约/归约”冲突。

课程设计报告课程：编译原理学号：姓名：班级：教师：时间：2014.5--2014.6.20计算机科学与技术系图4.4-1 NFA-DFA处理流程图2.NFA转换为DFA的原理及过程通过以下例子说明：①假如输入的NFA如图4.4-2所示：图4.4-2 NFA状态转换图②对于图4.2-2中的状态转换图的状态转换矩阵为：在图4.2-2中的状态转换图加一个起始状态X和结束状态Y，I为起始节点X经过一个或多个ε边到达的状态集，Ia为{X,1}经过a边到达的结点的ε闭包，Ib经过b边到达的结点的ε闭包;知道Ia和Ib列都在I列中出现为止。

如下表4.2.1所示：表4.2.1状态转换矩阵I Ia Ib{X,1} {2,3,Y}{2,3,Y} {2,3,Y}③对表4.2.1的状态转换矩阵进行重新命名，令A={X,1}，B={2,3,Y}，转换结果如下表4.2.2所示：表4.2.2重命名的状态转换矩阵④表4.2.2相对应的 DFA状态转换图为下图图4.2-2所示：图4.2-2 DFA状态图I Ia IbA BB B结果与分析（可以加页）：1.对于下图1中的NFA：图1 NFA状态图2.输入图1中NFA的各边信息：如下截图图2所示：图2 输入各边信息截图3.对于图1的NFA状态转换矩阵和重命名后的状态矩阵如下截图图3所示：图3 DFA状态矩阵截图4.将图3中的状态矩阵图最小化，如下截图图4所示：图4 最小化的DFA5.根据图4最小化的DFA状态转换矩阵，画出DFA状态转换图，如下图图5所示：图5 DFA状态装换图设计体会与建议：编译原理是一门重要但难学的课程，因为编译原理是关于编写编译器的技术，编译器的编写一直被认为是十分困难的事情，所以这次选到课程设计的课题就有些无从下手的感觉，感觉任务挺艰巨的。

设计要求从理论上就不太好理解，不像以前的设计编写一个应用程序实现常见的功能，这次的课程设计注重各种算法的实现，比如用子集法实现不确定的有限自动机的确定化、又能够分割法实现确定的有限自动机的最小化。

不确定有限状态自动机的确定化(NFA TO DFA)不确定有限状态自动机的确定化(NFA TO DFA 2008-12-05 22:11#in clude<iostream>#in clude<stri ng>#defi ne MAXS 100using n amespace std;string NODE; // 结点集合stri ng CHANGE; // 终结符集合int N; //NFA 边数struct edge{stri ng first;stri ng cha nge;stri ng last;};struct cha n{stri ng ltab;stri ng jihe[MAXS];};void kon g(i nt a){int i;for(i=0;i<a;i++)cout«'';}//排序void paixu(stri ng &a){int i,j;char b;for(j=0;j<a」en gth();j++)for(i=0;i<a」en gth();i++)if(NODE.fi nd(a[i])>NODE.fi nd(a[i+1])){b=a[i];a[i]=a[i+1];a[i+1]=b;void eclouse(char c,stri ng &he,edge b[]){int k;for(k=0;k<N;k++){if(c==b[k].first[0])if(b[k].cha nge=="*"){if(he.fi nd(b[k].last)>he.le ngth())he+=b[k].last; eclouse(b[k].last[0],he,b);}}}void move(cha n &he,i nt m,edge b[]){int i,j,k,l;k=he .l tab .len gth();l=he.jihe[m].le ngth();for(i=0;i<k;i++)for(j=0;j<N;j++)if((CHANGE[m]==b[j].cha nge[0])&&(he.ltab[i]==b[j].first[0])) if(he.jihe[m].find(b[j].last[0])>he.jihe[m].le ngth()) he.jihe[m]+=b[j].last[0];for(i=0;i<l;i++)for(j=0;j<N;j++)if((CHANGE[m]==b[j].cha nge[0])&&(he.jihe[m][i]==b[j].first[0] ))if(he.jihe[m].fi nd(b[j].last[0])>he.jihe[m].le ngth()) he.jihe[m]+=b[j].last[0]; }//输出void outputfa(i nt le n,i nt h,cha n *t){int i,j,m;cout«" I ";for(i=0;i<le n;i++) coutv<TvvCHANGE[i]vv" ";cout«endlvv" ------------------------- "<<e ndl;for(i=0;i<h;i++)cout«' '<<t[i].ltab;m=t[i].ltab.le ngth();for(j=0;j<le n;j++){{kon g(8-m);m=t[i].jihe[j].le ngth();cout<<t[i].jihe[j];}cout«e ndl;}}void mai n(){edge *b=new edge[MAXS];int i,j,k,m,n,h,x,y,len;bool flag;stri ng jh[MAXS],e ndno de,ed no de,sta;coutvv"请输入NFA各边信息(起点条件[空为*]终点)，以#结束："vvendl; for(i=0;i<MAXS;i++){cin> >b[i].first;if(b[i].first=="#") break;cin> >b[i].cha nge»b[i].last;}N=i;/*for(j=0;j<N;j++)cout<<b[j].firstvvb[j].cha nge<<b[j].lastvve ndl;*/for(i=0;i<N;i++){if(NODE.fi nd(b[i].first)>NODE.Ie ngth())NODE+=b[i].first;if(NODE.fi nd(b[i].last)>NODE.le ngth())NODE+=b[i].last;if((CHANGE.fi nd(b[i].cha nge)>CHANGE.Ie ngth())&&(b[i].cha nge!="*"))CHANGE+=b[i].cha nge;}len=CHANGE.le ngth();coutvv"结点中属于终态的是："<<endl;{coutvv"所输终态不在集合中，错误! "<<e ndl;cin>>endno de;for(i=0;i<e ndnode.len gth();i++)if(NODE.fi nd(e ndn ode[i])>NODE.le ngth()) {{coutvv"所输终态不在集合中，错误! "<<e ndl; return;}〃cout«"e ndno de="«e ndno de<<e ndl;chan *t=new chan [MAXS];t[O].ltab=b[O].first;h=1;for(j=0;j<le n;j++){paixu(t[i].jihe[j]);//对集合排序以便比较for(k=0;k<h;k++){flag=operator==(t[k].ltab,t[i].jihe[j]);if(flag)break;}if(!flag&&t[i].jihe[j].le ngth())t[h++].ltab=t[i].jihe[j];} }cout«endlvv"状态转换矩阵如下："<<endl;outputfa(len,h,t); II 输出状态转换矩阵eclouse(b[0].first[0],t[0].ltab,b); //cout<<t[0].ltab<<e ndl; for(i=0;i<h;i++) { for(j=0;j<t[i].ltab.le ngth();j++) for(m=0;m<le n;m++) eclouse(t[i].ltab[j],t[i].jihe[m],b); for(k=0;k<le n;k++) { 〃cout<vt[i].jihe[k]vv"->"; move(t[i],k,b); 〃cout<vt[i].jihe[k]vve ndl; for(j=0;j<t[i].jihe[k].le ngth();j++) eclouse(t[i].jihe[k][j],t[i].jihe[k],b); // } // 求 e-clouse // 求 e-clouse // 求 move(I,a) 求 e-clouse//状态重新命名NODE.erase();cout«endlvv"重命名："<<endl; for(i=0;i<h;i++)sta=t[i].ltab;{t[i].ltab.erase();t[i].ltab='A'+i;NODE+=t[i].ltab;coutvv'{'v<stavv"}="vvt[i].ltabvve ndl;for(j=0;j<e ndnode.len gth();j++)if(sta.fi nd(e ndno de[j])<sta.le ngth()) d[1]=ednode+=t[i].ltab;for(k=0;k<h;k++) for(m=0;m<le n;m++) if(sta==t[k].jihe[m])t[k].jihe[m]=t[i].ltab;}for(i=0;i<NODE.le ngth();i++)if(ed node.fi nd(NODE[i])>ed node.le ngth()) d[0]+=NODE[i]; endnode=ednode;cout«endl<v"DFA 如下："<<endl; outputfa(len,h,t); // 输出DFA cout«"其中终态为："<<endnode<<endl; //DFA最小化m=2;sta.erase();flag=0;for(i=0;i<m;i++){〃coutvv"d["vvivv"]="vvd[i]vve ndl;for(k=0;k<le n;k++){//coutv<TvvCHANGE[k]vve ndl;y=m;for(j=0;j<d[i].le ngth();j++){for(n=0;n<y;n++){if(d[ n].fi nd(t[NODE.fi nd(d[i][j])].jihe[k])<d[ n].le ngth() ||t[NODE.fi nd(d[i][j])].jihe[k].le ngth()==0){if(t[NODE.fi nd(d[i][j])].jihe[k].le ngth()==0)x=m;elsex=n;if(!sta.le ngth())sta+=x+48;{}elseif(sta[0]!=x+48){ d[m]+=d[i][j]; flag=1;d[i].erase(j,1); 〃cout<vd[i]vve ndl;j--；} break; // 跳出n}}//n}〃jif(flag){m++;flag=0;}//cout<<"sta="<<sta<<e ndl; sta.erase();}//k}//icout«endl<<"集合划分：";for(i=0;i<m;i++)cout<v"{"vvd[i]vv"}";cout«e ndl;//状态重新命名cha n *md=new cha n[ m];NODE.erase();cout«endlvv"重命名："<<endl;for(i=0;i<m;i++){md[i].ltab='A'+i;NODE+=md[i].ltab; coutvv"{"v<d[i]vv"}="vvmd[i].ltabvve ndl; }for(i=0;i<m;i++)for(k=0;k<le n;k++)for(j=0;j<h;j++){if(d[i][0]==t[j].ltab[0])for(n=0;n<m;n++){{if(!t[j].jihe[k]」e ngth()) break;elseif(d[ n].fi nd(t[j].jihe[k])<d[ n].le ngth()) {md[i].jihe[k]=md[ n] .Itab;break;}}break;}}edno de.erase();for(i=0;i<m;i++)for(j=0;j<e ndnode.len gth();j++) if(d[i].fi nd(e ndno de[j])<d[i].le ngth()&&ed node.fi nd(md[i].lta b))edno de+=md[i].ltab;endnode=ednode;cout«endlvv"最小化DFA如下："<<endl;outputfa(le n,m ,md);cout«"其中终态为："<<endnode<<endl;}/////////////////////////////////测试数据：i* 11a 11b 11 * 22a 32b 43a 54 b 55* 66 a 66 b 66 * f#////////////////////////////////请输入NFA各边信息（起点条件［空为*］终点），以#结束:i * 11 a 11b 11 * 22a 32b 43a 54 b 55* 66 a 66 b 66 * f#结点中属于终态的是：状态转换矩阵如下：I la lbi12 123 12412312356f124124123 12456f12356f12356f1246f12456f1236f 12456f1246f 1236f 12456f1236f 12356f1246f重命名：{i12}=A{123}=B{124}=C{12356f}=D{12456f}=E{1246f}=FDFA如下：I Ia Ib B D C C B E DDF E G E F G E G D F其中终态为：DEFG集合划分：{A} {DEFG} {B} {C}重命名：{A}=A{DEFG}=B{B}=C{C}=D最小化DFA如下：I la lbA C DB B BC B DD C B 其中终态为：B。

编译原理课程设计：NFM（非有限自动机）的确定化代码如下：// 编译原理课程设计.cpp : 定义控制台应用程序的入口点。

//#include "stdafx.h"#include<iomanip>#include<iostream>#include<fstream>#include<cmath>#include<string>using namespace std;#define MAX 20class mul_str{public:string str[MAX];};string state_change[MAX][MAX] ;string judge;string result[MAX][MAX];string str_start;string str_end;int line, column;int result_count = 0;void init();void read_file();bool cmp(string s1,string s2);string begin();string start(string s);void operation();void show();int look_line(string s);int look_line2(string s);int look_column(string s);bool check();void make_sure();int _tmain(int argc, _TCHAR* argv[]){while(true){init();if(check()){operation();make_sure();show();cout<<"已输出至result.txt"<<endl;}}return 0;}//初始化void init(){read_file();cout<<"非有限自动机为："<<endl;cout<<" ";for(int i = 1 ; i < column ; i ++){cout<<setw(3)<<state_change[0][i]<<" ";}cout<<endl;for(int i = 1 ; i < line; i ++){for(int j = 0; j < column; j ++){cout<<setw(3)<<state_change[i][j]<<" ";}cout<<endl;}}//读文件void read_file(){line = 0;column = 0;int i = 0 ;string con ;ifstream in;in.open("state.txt",ios::in);if(!in){cerr<< "open error!";}while(!in.eof()){in >> con;if("-2" == con){column = i;i = 0;line ++;}else{state_change[line][i] = con;i ++ ;}}}//字符串比较bool cmp(string s1, string s2){int i, j;bool con ;con = false ;if(s1.length() != s2.length()){return false;}else{for(i = 0; i < s1.length(); i++ ){con = false ;for(j = 0; j < s2.length(); j ++){if(s1[i] == s2[j] ){con = true;j = s2.length() + 1;}}if( con == false ){return false;}}return con;}}//检查bool check(){cout<<"input the start char please"<<endl;cin>> str_start;cout<<"input the end char please"<<endl;cin>> str_end;bool con = true ;for(int i =0 ; i < line; i ++)for(int j = 0; j < column; j ++){if(state_change[i][j] == str_start){con = false;}}if(con){cout<< "start char is error!"<<endl;return false;}con = true ;for(int i =0 ; i < line; i ++)for(int j = 0; j < column; j ++){if(state_change[i][j] == str_end){con = false;}}if(con){cout<< "end char is error!"<<endl;return false;}return true;}//查所在行int look_line(string s){for(int i = 0; i < line; i++){if(s == state_change[i][0]){return i;}}return 0;}//确定化int look_line2(string s){for(int i = 0; i <result_count; i++){if(cmp(s,result[i][0])){return i;}}return 0;}//查所在列int look_column(string s){for(int i = 0; i < column; i++){if(s == state_change[0][column]){return i;}}return 0;}//开始的第一个状态string start(string s1, int column){string temp1;string temp2;int i;int temp_line;temp1 = s1;for(i = 0; i<temp1.length(); i ++){temp2 = temp1[i];if(str_end == temp2){//return "y";}else{temp_line = look_line(temp2);if(temp_line == 0){cerr<<temp2<<"状态有错误"<<endl;int i;cin >> i;}if(state_change[temp_line][column] != "-1"){bool temp_con =false;int temp_i ;for(temp_i = 0; temp_i < temp1.length(); temp_i ++){temp2 = temp1[temp_i];temp_con = cmp(temp2,state_change[temp_line][column]);if(temp_con){break ;}}if(!temp_con){temp1 += state_change[temp_line][column];}}}}return temp1;}//求某一状态string begin(string s1, int column){string temp1;string temp2;string temp3="";int i;int temp_line;temp1 = s1;int a = temp1.length();for(i = 0; i<a; i ++){temp2 = temp1[i];if(str_end == temp2){}else{temp_line = look_line(temp2);if(temp_line == 0){cerr<<temp2<<"状态有错误"<<endl;int i;cin >> i;}if(state_change[temp_line][column] != "-1"){bool temp_con =false;int temp_i ;for(temp_i = 0; temp_i < temp3.length(); temp_i ++){temp2 = temp3[temp_i];temp_con = cmp(temp2,state_change[temp_line][column]);if(temp_con){break ;}}if(!temp_con){temp3 += state_change[temp_line][column];}}}}column = 1;temp1 = temp3;for(i = 0; i<temp1.length(); i ++){temp2 = temp1[i];if(str_end == temp2){}else{temp_line = look_line(temp2);if(temp_line == 0){cerr<<temp2<<"状态有错误"<<endl;int i;cin >> i;}if(state_change[temp_line][column] != "-1"){bool temp_con =false;int temp_i ;for(temp_i = 0; temp_i < temp1.length(); temp_i ++){temp2 = temp1[temp_i];temp_con = cmp(temp2,state_change[temp_line][column]);if(temp_con){break ;}}if(!temp_con){temp1 += state_change[temp_line][column];}}}}return temp1;}//调用求状态的过程void operation(){bool con = true;bool con2 = false ;string temp;int i, j, k;i = 0;j = 0;temp = state_change[1][0];temp = start(str_start,1);judge = temp;while(con){result[result_count][0]=judge;// cout<<"当前状态："<<judge<<" ";for(j = 2 ; j < column; j ++){temp = begin(judge,j);// cout<<"经过："<<state_change[0][j]<<"之后："<<temp<<" ";result[result_count][j]=temp;}//cout<<endl;result_count ++;for(i = 0 ; i < result_count ; i ++){for(j = 2; j < column ; j ++){for(k = 0; k < result_count ; k ++){con2=cmp(result[k][0],result[i][j]);if(con2){k = result_count + 1 ;}}if(k == result_count){judge = result[i][j];con = true ;i = result_count+1 ;j = column +1;}}}if(i == result_count){con = false;}}}//显示void show(){ofstream out;out.open("res0lt.txt",ios::out|ios::ate);if(!out){cerr<<"open error";}for(int i = 0 ; i < result_count; i ++){for(int j = 0; j < column; j ++){int lengh;int k;lengh = result[i][j].length();if(lengh > 0){out<<"{";out<< result[i][j][0];for(k = 1 ; k < lengh ; k ++ ){out<<","<<result[i][j][k];}out<<"}";for(; k < 18 ;k ++){out<<" ";}}}out<<endl;}out.close();}//确定化void make_sure(){cout<<"确定化以后："<<endl;cout<<" ";for(int i = 2 ; i < column ; i ++){cout<<state_change[0][i]<<" ";}cout<<endl;for(int i = 0 ; i < result_count; i ++){cout<<i<<" ";for(int j = 2; j < column; j ++){cout<<look_line2(result[i][j])<<" ";}cout<<endl;}}。

编译原理实验NFA确定化为DFA编译原理中的NFA（Non-deterministic Finite Automaton，非确定性有限自动机）是一种能够识别正则语言的形式化模型。

它的设计简单，但效率较低。

为了提高识别效率，需要将NFA转化为DFA（Deterministic Finite Automaton，确定性有限自动机）。

本文将介绍NFA确定化为DFA的一般方法，并以一个具体例子来说明该过程。

首先，我们来了解一下NFA和DFA的差异。

NFA可以有多个转移路径，每个输入符号可以对应多个状态转移，而DFA每个输入符号只能对应唯一的状态转移。

这使得NFA在识别过程中具有非确定性，无法确定下一个状态。

而DFA则能够准确地根据当前状态和输入符号确定下一个状态。

NFA确定化为DFA的一般方法如下：1.创建DFA的初始状态。

该状态对应NFA的起始状态以及从起始状态经过ε（空）转移可以到达的所有状态。

2.对DFA的每个状态进行如下处理：a)对当前状态的每个输入符号进行处理。

b)根据当前状态和输入符号，确定下一个状态。

如果有多个状态，需要将它们合并为一个DFA状态。

c)重复上述步骤，直到处理完所有输入符号。

3.对于合并的DFA状态，需要重复执行第2步的处理过程，直到没有新的合并状态产生为止。

4.最终得到的DFA包含的状态即为NFA确定化的结果。

下面以一个具体的例子来说明NFA确定化为DFA的过程。

考虑以下NFA：（状态）（输入符号）（转移状态）1a,ε1,22a33b44a5首先，创建DFA的初始状态，根据NFA的起始状态和通过ε转移可以到达的状态。

在该例子中，起始状态为1，通过ε转移可以到达状态1和2、因此，初始状态为{1,2}。

接下来，对初始状态{1,2}进行处理。

对于输入符号a，根据NFA的状态转移表可以得到DFA的下一个状态为{1,2,3}，因为NFA的状态1通过a和ε可以到达状态3、对于输入符号b，当前状态没有转移。

实验一：利用子集法构造DFA一．实验目的掌握将非确定有限自动机确定化的方法和过程。

二．实验要求、内容及步骤实验要求：1.输入一个NFA，输出一个接受同一正规集的DFA；2.采用C++语言，实现该算法；3.编制测试程序；4.调试程序。

实验步骤：1.输入一个NFA关系图；2.通过一个转换算法将NFA转换为DFA；3.显示DFA关系图。

三．实验设备计算机、Windows 操作系统、Visual C++ 程序集成环境。

四．实验原理1.NFA-DFA转换原理：从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态。

DFA使用它的状态去记录在NFA读入一个输入符号后可能到达的所有状态。

输入：一个NFA N输出：一个接受同样语言的DFA D方法：为D构造转换表Dtran，DFA的每个状态是NFA的状态集。

D的状态集合用Dstates表示。

D的开始状态为ε-closure(s0)，s0是N的开始状态。

使用下列算法构造D的状态集合Dstates和转换表Dtran。

如果D的某个状态是至少包含一个N的接受状态的NFA状态集，那么它是D的一个接受状态。

2.子集构造法：初始时, ε-closure(S0) 是Dstates中唯一的状态且未被标记;while Dstates中存在一个未标记的状态T do begin标记T;for 每个输入符号a do beginU := ε-closure ( move (T, a) );if U 没在Dstates中then将U作为一个未被标记的状态添加到 Dstates.Dtran [ T, a ] := Uendend3.ε-closure的计算：将T中所有状态压入栈stack;将ε-closure (T) 初始化为T;while stack不空 do begin将栈顶元素t弹出栈;for 每个这样的状态u：从t到u有一条标记为ε的边do if u不在ε-closure ( T )中 do begin将u 添加到ε-closure ( T );将u压入栈stack中 endend五．程序设计1.总体设计2.子程序设计识别模块读入字符识别模块识别标识符识别分界符、运算符识别常数输出六．程序中的结构说明1.结构体Symbolrecord 结构体结构体成员名 成员属性Symbol[10] 用于存储关键字编码名 id用于存储关键字对应的编码读取字符字母识别标识符数字识别数字/识别注释打印并结束FTFTFTentrytype结构体结构体成员名成员属性idname[10] 用于存储识别后标识符名address 用于存储标识符的地址type 用于存储标识符的类型digittype结构体结构体成员名成员属性num 用于存储识别后的数字address 用于存储标识符数字的地址tokentype结构体结构体成员名成员属性id 用于存储被识别的类型名entry 用于存储标识符的地址idname[10] 用于存储被识别的标识符名2.符号编码表符号编码表符号名代码符号名代码Begin 0 } 14End 1 ( 15If 2 ) 16 Then 3 < 17 Else 4 <= 18for 5 = 19do 6 != 20while 7 > 21+ 8 >= 22- 9 := 23* 10 ‘’24/ 11 Id 25; 12 Const 26{ 133.重要函数介绍tokentype recogid(char ch)//识别标识符算法tokentype recogdig(char ch) ///识别数字函数tokentype recogdel(char ch) //识别算符和界符函数tokentype handlecom(char ch) //handlecom函数，识别注释函数void sort(char ch) //sort函数，读取文件内容，并根据读入内容调用不同的识别函数void scanner()//scanner函数，打开文件七.函数代码#include <stdio.h>#include <string.h>#include <ctype.h>#include <stdlib.h>;-----------------------定义单词编码表的数据结构-------------------- struct symbolrecord{ char symbol[10];int id;} ;;-------------------------定义符号表的数据结构---------------------- struct entrytype{ char idname[10];int address;int type;};;-------------------------定义常数表的数据结构---------------------- struct digittype{ int num;int address;};;---------------------------Token字的数据结构----------------------- struct tokentype{ int id;int entry;char idname[10];};FILE *fp; //源文件指针struct digittype d[10]; //定义常数表，个数指针struct entrytype a[40];int k=0,t=0;;---------------------------单词编码表初始化------------------------ struct symbolrecord s[26]={ "Begin",0,"End",1,"If",2,"Then",3, "Else",4, "for",5, "do",6,"while",7, "+",8,"-",9,"*",10,"/",11,";",12,"{",13,"}",14,"(",15,")",16,"<",17,"<=",18, "=",19,"!=",20, ">",21,">=",22, ":=",23, " ",24,"const",26 };;---------------------------识别标识符算法-------------------------- tokentype recogid(char ch){ tokentype tokenid;FILE *fs;int flag,fflag;char word[10]={0};int i,j;i=0;while(isalpha(ch)||isdigit(ch)){ word[i]=ch;ch=fgetc(fp);i=i+1;}ungetc(ch,fp);word[i]='\0';for(j=0;j<=8;j++){ flag=strcmp(word, s[j].symbol);if(flag==0) //是关键字{ tokenid.id=j;tokenid.entry=-1;break;} }if(flag!=0){ for(j=0;j<=k;j++){ fflag=strcmp(a[j].idname,word);if(fflag==0) //在符号表中可以找到{ tokenid.id=25;tokenid.entry=a[j].address;break;} }if(fflag!=0){ fs=fopen("symbol.txt","a"); //符号表中不存在的标识符 strcpy(a[k].idname, word);a[k].address=k;a[k].type=25;tokenid.id=25;tokenid.entry=k;for(j=0;j<9;j++)fprintf(fs,"%c",word[j]);fprintf(fs,"%c",'\t');fprintf(fs,"%d",a[k].address);fprintf(fs,"%c",'\t');fprintf(fs,"%d",a[k].type);fprintf(fs,"%c",'\n');fclose(fs);k=k+1;} }strcpy(tokenid.idname, word);//自行添加的return tokenid;};-----------------------------识别数字函数-------------------------- tokentype recogdig(char ch){ int flag;int i=0,j;int num=0;tokentype tokenid;while(isdigit(ch)){ num=(ch-48)+num*10;ch=fgetc(fp);i=i+1;}for(j=0;j<=t;j++)if(d[j].num==num){ flag=1;tokenid.id=26;tokenid.entry=d[j].address;break;}if(flag!=1){ d[t].num=num;d[t].address=t;tokenid.id=26;tokenid.entry=t;t=t+1;}sprintf(tokenid.idname, "%d", num);//int>>charreturn tokenid;};------------------------识别算符和界符函数------------------------- tokentype recogdel(char ch){ tokentype tokenid;switch(ch){ case'{':{ tokenid.id=13;strcpy(tokenid.idname, "{");//自行添加的}break;case'}':{ tokenid.id=14;strcpy(tokenid.idname, "}");}break;case';':{ tokenid.id=12;strcpy(tokenid.idname, ";");}break;case'=':{ tokenid.id=19;strcpy(tokenid.idname, "=");}break;case':':ch=fgetc(fp);if(ch=='=') tokenid.id=23; break;case'!':{ ch=fgetc(fp);if(ch=='=') tokenid.id=20;strcpy(tokenid.idname, "!="); } break;case'<':{ch=fgetc(fp);if(ch=='='){ tokenid.id=18;strcpy(tokenid.idname, "<=");}else{ tokenid.id=17;strcpy(tokenid.idname, "<");ungetc(ch,fp);}}; break;case'>':ch=fgetc(fp);if(ch=='='){tokenid.id=22;strcpy(tokenid.idname, ">=");}else { tokenid.id=21;strcpy(tokenid.idname, ">");ungetc(ch,fp);}; break;case'+':{ tokenid.id=8;strcpy(tokenid.idname, "+");}break;case'*':{ tokenid.id=10;strcpy(tokenid.idname, "*");}break;case'(':{ tokenid.id=15;strcpy(tokenid.idname, "(");}break;case')':{ tokenid.id=16;strcpy(tokenid.idname, ")");}break;}tokenid.entry=-1;return tokenid;};---------------------------handlecom函数--------------------------- tokentype handlecom(char ch){ tokentype tokenid;char ch1;int flag=0;if(ch!='*' ){ tokenid.id=25;tokenid.entry=-1;}else{ while(flag==0){ ch1=ch;ch=fgetc(fp);if((ch1='*')&&(ch='/'))flag=1;}}return tokenid;};---------------------------sort函数---------------------------- void sort(char ch){struct tokentype tokenword;FILE * fq = fopen("tokenfile.txt","a");if(isalpha(ch))tokenword=recogid(ch); //字母else if(isdigit(ch))tokenword=recogdig(ch); //数字else if(ch=='/')tokenword=handlecom(ch);elsetokenword=recogdel(ch);printf("%s\t%d\t%d\n",tokenword.idname,tokenword.id,tokenword.entry) ;fprintf(fq,"%d",tokenword.id);fprintf(fq,"%c",'\t');fprintf(fq,"%d",tokenword.entry);fprintf(fq,"%c",'\n');fclose(fq);};--------------------------scanner函数---------------------------- void scanner(){ char ch;fp=fopen("source.txt","r");ch=getc(fp);while(ch!=EOF){ if(!isspace(ch)){ sort(ch);}ch=fgetc(fp);}fclose(fp);};------------------------------主函数------------------------------ int main(){ int i;printf("输出token字如下:\n");printf("idname\ttype\taddress\n");scanner();printf("************************************\n");printf("输出符号表如下：\n");printf("%s\t%s\t%s\n","idname","address","type");for(i=0;i<=k-1;i++)printf("%s\t%d\t%d\n",a[i].idname,a[i].address,a[i].type);printf("************************************\n"); printf("输出常数表如下：\n");printf("%s\t%s\n","num","address");for(i=0;i<=t-1;i++)printf("%d\t%d\n",d[i].num,d[i].address);printf("\n\n");system("pause");}八．程序测试Source源文件程序截图main(){If a!=35end;do whileend;36}九．实验小结子集构造法的基本思想是构造得到的DFA的每个状态对应于NFA的一个状态集合。