编译原理实验五：有穷自动机的确定化

编译原理实验五：有穷自动机的确定化,zip文件里包含实验报告和源代码两部分。

#include
#include
#include
using namespace std;
#define max 100
int n;//NFA的边数
vector value;

struct edge{
    string first;//边的初始结点
	string condition;//边上的条件
	string last;//边的终点
};


string closure（string aedge *b）//求状态集合I的&-闭包，用&代替“空“
{
	int ij;
	for（i=0;i	{
		for（j=0;j		{
			if（b[j].first[0]==a[i]&&b[j].condition==“&“）
			{
				a=a+b[j].last[0];
			}
		}
	}
	return a;
}

string move（string collectionchar chedge *b）//状态集合I的a弧转换
{
	int ij;
	string s=““;
	for（i=0;i	{   
		for（j=0;j		{
			if（b[j].first[0]==collection[i]&&b[j].condition[0]==ch）
			   s=s+b[j].last;
		}
	}
	return s;
}

string sort（string t）//字符串排序
{
	int kij;
	char tt;
	for（i=0;i	{
		k=i;
		for（j=i+1;j		{
			if（t[j]		}
		tt=t[k];t[k]=t[i];t[i]=tt;
	}
	return t;
}


void main（）
{
   int ijx=0hlengthmd=0;
   string Condition;//边上的条件
   string FirstLast;//初态，终态，
   string T[max]ss;
   edge *b=new edge[max];
   cout<<“...................编译原理实验五：有穷自动机的确定化....................“<   cout<<“请输入各边信息：起点  条件（空用&表示） 终点 并以输入#结束！！“<   for（i=0;i   {
	   cin>>b[i].first;
	   if（b[i].first==“#“）break;
	   else
		   cin>>b[i].condition>>b[i].last;
   }
   n=i;
   cout<<“请输入NFA的初态及终态：“<   cin>>First>>Last;
   cout<<“请输入NFA状态中的输入符号即边上的条件:“<   cin>>Condition;
   T[x]=closure（Firstb）;//字符串数组存储空闭包并排序
   T[x]=sort（T[x]）;
   value.push_back（0）;
   i=0;
   while（value[i]==0&&value.size（））
   {   
	   value[i]=1;
	   for（j=0;j	   {
		   ss=““;
		   ss=move（T[i]Condition[j]b）;
		   length=value.size（）;
		   for（h=0;h		   {
		      if（T[h]==sort（closure（ssb）））break;
           }
		   if（h==length）
		     {
			      T[++x]=sort（closure（ssb））;
			      value.push_back（0）;
		     }
		   
	   }
	   i++;
   }
   edge *DFA=new edge[max];
   for（i=0;i<=x;i++）//构造DFA的各边
   {
	   for（j=0;j	   {
		   DFA[d].first=T[i];
		   DFA[d].condition=Condition[j];
		   ss=““;
		   ss=sort（closure（move（T[i]Condition[j]b）b））;
		   for（m=0;m<=x;m++）
			   if（ss==T[m]）DFA[d++].last=T[m];
	   }
   }
   cout<<“NFA构造的DFA的各边信息如下：“<   for（i=0;i   {
	   for（m=0;m<=x;m++）
	   {
		   if（DFA[i].first==T[m]）cout<	   }
	   for（m=0;m<=x;m++）
		   if（DFA[i].last==T[m]）cout<<“     “<   }
   cout<<“确定后的DFA的初态为：“;
   for（m=0;m<=x;m++）
   {
	   for（j=0;j	   {
		   ss=T[m];
		   if（ss[j]==First[0]）cout<	   }
   }
   cout<<“确定后的DFA的终态为：“;
    for（m=0;m<=x;m++）
   {
	   for（j=0;j	   {
		   ss=T[m];
		   if（ss[j]==Last[0]）cout<	   }
   }
	cout<  system（“pause“）;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        3149  2014-05-21 16:33  5.cpp
     文件       62464  2015-12-13 20:42  编译原理实验五：有穷自动机的确定化.doc