资源描述：
《实验3--词法分析-fa的应用new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、-18-实验三词法分析——有穷自动机的应用实验目的：一：输入正则文法二：FA1．生成FA(DFA或NFA)2．运行FA，DFA（自动）；NFA（交互）3．**NFA→DFA实验设想：对输入的文法存储并判断是确定的有穷状态自动机还是不确定是有穷状态自动机，并给出标准的表示形式，若是DFA，可直接测试一个符号串是否是文法的句子，即能否被有穷状态机接受，给出过程及结果；若是NFA，首先将其转化为DFA，再测试一个符号串是否是文法的句子，亦即是否能被DFA接受。例如：输入文法规则的数目：7输入开始状态:S输入文法Z::=ZaZ::=BbZ::=AaB::=
2、AbB::=bA::=BaA::=a此为确定有穷状态自动机!DFAD=({Z,A,B},{a,b},M,S,{Z})其中M:M(Z,a)=ZM(B,b)=ZM(B,a)=AM(A,a)=ZM(A,b)=BM(S,b)=BM(S,a)=A输入要推导的符号串:ababaaM(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)-18--18-=Z该符号串能被有
3、穷状态所接受!输入文法规则的数目：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],[B
4、Z],[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]}输入要推导的字符串:ababcM'([S],ababc)=M'(M'([S],a),babc)=M'([A],babc)=M'(M'([A],b),abc)=M'([BZ],abc)=M'(
5、M'([BZ],a),bc)=M'([AZ],bc)-18--18-=M'(M'([AZ],b),c)=M'([BZ],c)=[Z][Z]属于终止状态集合!该字符串能被有穷状态所接受!参考程序#include#includestructLeftItem;structRightNode//存储状态转换关系中弧与终止状态结点结构{chartran;charnextstate;RightNode*nextsibling;RightNode(charx,chary){tran=x;nextstate=y;next
6、sibling=NULL;}};structLeftItem//存储状态转换关系中初始状态结点结构{charstate;RightNode*link;};structStateItem//存放确定化的NFA状态结点结构{charnewstates[10];StateItem(){newstates[0]=' ';}};////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
7、//////////////////////////intCheckState(LeftItemArray[],intsize){RightNode*p;RightNode*q;-18--18-for(inti=0;inextsibling;if(q==NULL)return1;while(q!=NULL){if(p->tran==q->tran)return0;q=q->nextsibling;}}return1;}intCheckExist(StateItemSArray[],in
8、t&length,chartemp[])//将NFA确定化创建二维矩阵时判别新产生的状态是否在状态数组中存储过{inti=
