1、
西北师范大学计算机科学与工程学院学生实验报告
学号
111111
专业
计算机科学与技术
班级
技师(1)班
姓名
111
课程名称
编译原理
课程类型
实验
实验名称
有穷状态自动机
实验目的：
1， 准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，为词法分析程序的自动构造寻找特殊的方法和工具；
2， 掌握了有穷状态自动转换机的概念；
3， 掌握DFA的存储表示；
4， 掌握DFA与正则文法的联系
实验原理：
1， 一个确定的有穷状态自动机DFA是五元组（K,∑,M,S,F,）,其中，
2、
K是有穷非空的状态集合；
∑是有穷非空的输入字母表；
M是从K×∑到K的映象。如果M（R,T）=Q，则输入字符为T时，当前状态R将转换到状态Q，Q成为下一当前状态；
S是开始状态；
F是非空的终止状态集合。
输入任意的正则文法，输出相应的有穷状态自动机
要求：识别有穷状态自动转换机是非确定的还是确定的，以相应的五元组形式输出。
实验代码如下：
实验源代码：
#include
using namespace std;
const int maxsize=10;
class DFA
{
private:
3、 int M[maxsize][maxsize];
char Vn[maxsize],Vt[maxsize];
int VnNum,VtNum;
public:
DFA();
~DFA(){}
void print();
int move(char start,char s[]);
};
int DFA::move(char start,char s[])
{
4、 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&&left5、 {
next=Vn[M[left][right]];
cout<<"M("<6、le,left,right,final;
int i=0,j=0,k=0;
cout<<"rule=";cin>>rule;
cout<<"Vn ";cin>>n;
cout<<"Vt ";cin>>t;
cout<<"grammar";
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;i7、j]=-1;
i=0;
while(i!=rule)
{
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(
8、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<9、"},M"<>i;DFA s;
while(i<=3)
{
//system("color 1e");
if(i==2)s.pr
11、int();
if(i==3)
{cout<<"输入串";
cin>>t;if(s.move('S',t))cout<<"字符串"<>i;
}
system("pause");
}
实验结果：
实验总结：
通过本次实验，对有穷状态自动转换机有了更进一步的了解，掌握了其存储表示与正则文法的联系，并且通过对整个程序的阅读，知道了任意的正则文法如何以五元组的形式输出。能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合.通过本次实验，对有穷状态自动机的概念、其存储表示及其正则文法的联系，有了进一步的理解和认识，增强了动手能力和编程能力。
实验成绩
教师签名
浙ICP备2021020529号-1 | 浙B2-20240490 
