哈工程编译原理实验报告 词法分析.pdfVIP

编译原理实验报告

学号姓名

实验名称词法分析实验--DFA化简

实验目的1.熟练掌握DFA及NFA的定义及有关概念。

2.理解并掌握确定的有穷自动机的最小化等算法。

实验方案化简DFA的基本思想是指导它的状态分成一些互不相交的子集，每一个子

集中的状态都不是等价的，不同子集中的状态可以由某个输入串来区别，

最后将不能区别的每个子集用一个状态来做代表[13-15]，这种方法称为“分

割法”。具体过程是：

（1）将M的所有状态分成两个子集——终态集和非终态集；

（2）考察每一个子集，若发现某子集中的状态不等价，将其划分为两个集

合；

（3）重复第（2）步，继续考察已得到的每一个子集，直到没有任何一个子

集需要继续划分为止。这时DFA的状态被分成若干个互不相交的子集。

（4）从每个子集中选出一个状态做代表即可得到最简的DFA。

实验记录#includeiostream

#includestring

usingnamespacestd;

#definemax100

structedge{

stringfirst;//边的初始结点

stringcondition;//边上的条件

stringlast;//边的终点

};

intN;//NFA的边数

stringpart[max];//分割子集

stringmove(stringcollection,charch,edge*b){//状态集合I的a弧转换

inti,j;

for(i=0;icollection.length();i++){

for(j=0;jN;j++){

if(b[j].first[0]==collection[i]b[j].condition[0]==ch)

s=s+b[j].last;

}

}

elsereturns;

}

boolisexist(strings,stringd){//判断子串是否存在在某一集合

1

elsereturn0;

}

intdivide(edge*b,stringchange){//分割子集法进行DFA的最小化

intx,m,flag=2,flag0,i,j;

stringss,part0[max];

flag0=flag;

for(x=0;xchange.length();x++){

for(m=0;mflag0;m++){

for(i=0;ipart[m].length();i++){

ss=move(part[m].substr(i,1),change[x],b);

for(j=0;jflag;j++){

if(isexist(ss,part[j]))part0[j]=part0[j]+part[m].substr(i,1);