实验二

西北师范大学计算机科学与工程学院学生实验报告
学号 专业 ） 班级 计师1班 姓名
课程名称 计算机编译原理 课程类型 实验

实验名称 有穷状态自动机
一．实验目的：
1：掌握有穷状态自动机的概念。
2：学会从文法构造有穷状态自动机。
3：掌握有穷状态自动机的存储方式。
4：掌握运行有穷状态自动机。
二．实验原理
一个确定的有穷状态自动机DFA是一个五元组（K,∑,M,S,F）其中K是有
穷非空的状态集合。∑是有穷非空的输入字母表。M是从K*∑到K的映像。S
是开始状态。F是非空的终止状态集合。
利用数组将输入的Vn和Vt存储起来，而DFA中的五元组里K对应Vn,，
∑对应Vt，S是Vn[0]，F是Vn[1]，利用Vn数组下标可以改变M的状态。
三：实验内容
1：从正则文法构造有穷状态自动机
输入任意的正则文法，输出相应的有穷状态自动机，以五元组的形式输出。
2：运行有穷状态自动机
输入一些简单的字符串。运行有穷状态自动机判别是否可以被接受。
四．实验步骤
实验代码如下：
第一步：主函数
#include
using namespace std;
const int maxsize=10;
int main()
{
char t[10];
int i;
cout<<"------------------------------------------------"<cout<<"---1.DFA构造,2.打印五元组,3.接受字符串,4.退出---\n";
cin>>i;DFA s;
while(i<=3)
{
system("color 1e");
if(i==2)s.print();
if(i==3)
{cout<<"输入串";
cin>>t;if(s.move('S',t))cout<<"字符串"<接收";
else cout<<"字符串"<cout<<"\n输入操作";
cin>>i;
}
system("pause");
}
class DFA
{
private:
int M[maxsize][maxsize];
char Vn[maxsize],Vt[maxsize];
int VnNum,VtNum;

public:
DFA();
~DFA(){}
void print();
int move(char start,char s[]);
};：

第二步：从输入的文法构造相应的有穷状态自动机：
DFA::DFA()
{
char grammar[maxsize],n[maxsize],t[maxsize];
int RuleNum,left,right,final;
int i=0,j=0,k=0;
cout<<"RuleNum=";cin>>RuleNum;
cout<<"Vn ";cin>>n;
cout<<"Vt ";cin>>t;
cout<<"grammar\n";
Vn[0]='S';
j=0;
while(n[j]!='\0')Vn[j+1]=n[j++];VnNum=j+1;
while(t[i]!='\0')Vt[i]=t[i++];VtNum=i;
for(i=0;ifor(j=0;j<=VtNum;j++)M[i][j]=-1;
i=0;
while(i!=RuleNum)
{
j=0;k=0;
cin>>grammar;
while(Vn[k]!=grammar[0])k++;
final=k;
while(grammar[j]!='\0')j++;
if(j==2)
{
k=0;
while(Vt[k]!=grammar[1])k++;
left=0;
right=k;
}
else
{
k=0;while(Vn[k]!=grammar[1])k++;left=k;
k=0;while(Vt[k]!=grammar[2])k++;right=k;
}
M[left][right]=final;
i++;
}
}
第三步：打印该有穷状态自动机
void DFA::print()
{
int i=0,j=0;
cout<<"DFA ({";
while(i!=VnNum){cout<while(j!=VtNum){cout<cout<<"{"<i=0;
while(i!=VnNum)
{ j=0;
while(j!=VtNum)
{
if(M[i][j]!=-1)
{
cout<<"M("<cout<<","<}
j++;
}
i++;
}
cout<<"},{"<};
第四步：输入字符串运行该有穷状态自动机
int DFA::move(char start,char s[])
{
char t[10];char next=start;
int left=0,right=0,i=0,j=0;
while(s[i]!='\0'){t[i]=s[i++];}
t[i]='\0';
while(t[0]!='\0')
{
left=0;right=0;
while(next!=Vn[left]){left++;}
while(t[0]!=Vt[right]){right++;}
if(M[left][right]!=-1&&left{
next=Vn[M[left][right]];
cout<<"M("<}
else return 0;
i=1;
while(t[i]!='\0'){t[i-1]=t[i++];}
t[i-1]='\0';
}
return 1;

}
五．实验结果
1：输入正则文法
2：打印有穷状态自动机
3：输入字符串ab,，运行有穷状态自动机，ab可以被接受。

六.实验总结
通过本次实验，基本掌握了正则文法构造有穷状态自动机及运行过程。但是
本实验的运行过程还有欠缺，程序执行的复杂度还有待提高，希望通过后续课程
的学习加以改善，以期达到满意的成效。

实验评语：
实验成绩 教师签名