实验3词法分析FA的应用已完成.docx
- 文档编号:10059566
- 上传时间:2023-05-23
- 格式:DOCX
- 页数:32
- 大小:53KB
实验3词法分析FA的应用已完成.docx
《实验3词法分析FA的应用已完成.docx》由会员分享,可在线阅读,更多相关《实验3词法分析FA的应用已完成.docx(32页珍藏版)》请在冰点文库上搜索。
实验3词法分析FA的应用已完成
实验三词法分析——有穷自动机的应用
一、实验目的:
一:
输入正则文法
二:
FA
1.生成FA(DFA或NFA)
2.运行FA,DFA(自动);NFA(交互)
3.**NFA→DFA
二、实验设想:
对输入的文法存储并判断是确定的有穷状态自动机还是不确定是有穷状态自动机,并给出标准的表示形式,若是DFA,可直接测试一个符号串是否是文法的句子,即能否被有穷状态机接受,给出过程及结果;若是NFA,首先将其转化为DFA,再测试一个符号串是否是文法的句子,亦即是否能被DFA接受。
例如:
输入文法规则的数目:
7
输入开始状态:
S
输入文法Z:
:
=ZaZ:
:
=BbZ:
:
=AaB:
:
=AbB:
:
=bA:
:
=BaA:
:
=a
此为确定有穷状态自动机!
DFAD=({Z,A,B},{a,b},M,S,{Z})
其中M:
M(Z,a)=Z
M(B,b)=Z
M(B,a)=A
M(A,a)=Z
M(A,b)=B
M(S,b)=B
M(S,a)=A
输入要推导的符号串:
ababaa
M(S,ababaa)
=M(M(S,a),babaa)
=M(A,babaa)
=M(M(A,b),abaa)
=M(B,abaa)
=M(M(B,a),baa)
=M(A,baa)
=M(M(A,b),aa)
=M(B,aa)
=M(M(B,a),a)
=M(A,a)
=Z
该符号串能被有穷状态所接受!
输入文法规则的数目:
7
输入开始状态:
S
输入规则:
Z:
:
=AbZ:
:
=BaZ:
:
=ZcA:
:
=BaA:
:
=aB:
:
=AbB:
:
=b
文法规则存储完毕!
此为非确定有穷状态自动机!
NFAN=({Z,B,A},{b,a,c},M,{S},{Z})
其中M:
M(A,a)=$
M(A,b)={Z,B}
M(A,c)=$
M(B,a)={Z,A}
M(B,b)=$
M(B,c)=$
M(Z,a)=$
M(Z,b)=$
M(Z,c)={Z}
M(S,a)={A}
M(S,b)={B}
M(S,c)=$
将NFA转化为DFA!
DFAN'=({[S],[B],[A],[AZ],[BZ],[Z]},{[b],[a],[c]},M',[S],F')
其中M':
M'([S],b)=[B]
M'([S],a)=[A]
M'([B],a)=[AZ]
M'([A],b)=[BZ]
M'([AZ],b)=[BZ]
M'([AZ],c)=[Z]
M'([BZ],a)=[AZ]
M'([BZ],c)=[Z]
M'([Z],c)=[Z]
其中F'={[AZ],[BZ],[Z]}
输入要推导的字符串:
ababc
M'([S],ababc)
=M'(M'([S],a),babc)
=M'([A],babc)
=M'(M'([A],b),abc)
=M'([BZ],abc)
=M'(M'([BZ],a),bc)
=M'([AZ],bc)
=M'(M'([AZ],b),c)
=M'([BZ],c)
=[Z]
[Z]属于终止状态集合!
该字符串能被有穷状态所接受!
三、参考程序
#include
#include
structLeftItem;
structRightNode//存储状态转换关系中弧与终止状态结点结构
{
chartran;
charnextstate;
RightNode*nextsibling;
RightNode(charx,chary)
{
tran=x;nextstate=y;nextsibling=NULL;
}
};
structLeftItem//存储状态转换关系中初始状态结点结构
{
charstate;
RightNode*link;
};
structStateItem//存放确定化的NFA状态结点结构
{
charnewstates[10];
StateItem()
{
newstates[0]='\0';
}
};
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
intCheckState(LeftItemArray[],intsize)
{
RightNode*p;
RightNode*q;
for(inti=0;i { p=Array[i].link; q=p->nextsibling; if(q==NULL)return1; while(q! =NULL) { if(p->tran==q->tran)return0; q=q->nextsibling; } } return1; } intCheckExist(StateItemSArray[],int&length,chartemp[]) //将NFA确定化创建二维矩阵时判别新产生的状态是否在状态数组中存储过 { inti=0,k,m; while(i<=length) { if(strlen(SArray[i].newstates)==strlen(temp)) { if(strcmp(SArray[i].newstates,temp)==0) { k=i; break; } } i++; } if(i>length) { length++; m=length; returnm; } else returnk; } intgetcount1(LeftItemArray[],intsize)//取得FA中状态的个数 { chartemp[20]; intlen=0,count=0; inti,j; RightNode*pNode; for(i=0;i { pNode=Array[i].link; while(pNode) { for(j=0;j if(pNode->nextstate==temp[j])break; if(j==len) { count++; temp[len]=pNode->nextstate; len++; } pNode=pNode->nextsibling; } } returncount; } intgetcount2(LeftItemArray[],intsize)//取得FA中输入字母的个数 { chartemp[20]; intlen=0,count=0; inti,j; RightNode*pNode;