实验3词法分析FA的应用已完成.docx

实验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;

for（i=0;i

{

pNode=Array[i].link;

while（pNode）

{

for（j=0;j

if（pNode->tran==temp[j]）break;

if（j==len）

{

count++;

temp[len]=pNode->tran;

len++;

}

pNode=pNode->nextsibling;

}

}

returncount;

}

intgetstate（RightNode*pNode,chararc）//判定一个状态是否能通过一条弧进入下一状态

{

while（pNode）

{

if（pNode->tran==arc）return1;

pNode=pNode->nextsibling;

}

return0;

}

voidSort（charA[],intn）//将取得的新状态进行排序

{

for（inti=n-1;i>0;i--）

for（intj=0;j

{

if（A[j+1]

{

chartemp=A[j+1];

A[j+1]=A[j];

A[j]=temp;

}

}

}

voidBianli1（LeftItemArray[],intsize）//输出FA中有穷非空的状态集合

{

chartemp[20];

intlen=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）

{

if（len==0）cout<nextstate;

else

cout<<","<nextstate;

temp[len]=pNode->nextstate;

len++;

}

pNode=pNode->nextsibling;

}

}

}

voidBianli2（LeftItemArray[],intsize）

//输出FA中有穷的输入字母表

{

chartemp[20];

intlen=0;

inti,j;

RightNode*pNode;

for（i=0;i

{

pNode=Array[i].link;

while（pNode）

{

for（j=0;j

if（pNode->tran==temp[j]）break;

if（j==len）

{

if（len==0）cout<tran;

else

cout<<","<tran;

temp[len]=pNode->tran;

len++;

}

pNode=pNode->nextsibling;

}

}

}

voidBianli31（LeftItemArray[],intsize）

//输出DFA状态转换关系的集合M

{

inti;

RightNode*pNode;

for（i=0;i

{

pNode=Array[i].link;

while（pNode!

=NULL）

{

cout<<"M（"<tran

<<"）="<nextstate<

pNode=pNode->nextsibling;

}

}

}

voidBianli32（LeftItemArray[],intsize）//输出NFA状态转换关系集合M

{

charK[20];

intlen=0;

inti,j;

RightNode*pNode;

RightNode*qNode;

for（i=0;i

{

pNode=Array[i].link;

while（pNode）

{

for（j=0;j

if（pNode->tran==K[j]）break;

if（j==len）

{

K[len]=pNode->tran;

len++;

}

pNode=pNode->nextsibling;

}

}

Sort（K,len）;

for（i=0;i

{

for（j=0;j

{

pNode=Array[i].link;

cout<<"M（"<

if（getstate（pNode,K[j]））

{

cout<<"{";

while（pNode）

{

if（pNode->tran==K[j]）

{

qNode=pNode->nextsibling;

cout<nextstate;

break;

}

pNode=pNode->nextsibling;

}

while（qNode）

{

if（qNode->tran==K[j]）

cout<<","<nextstate;

qNode=qNode->nextsibling;

}

cout<<"}"<

}

else

cout<<"$"<

}

}

}

voidInitiate（LeftItemArray[],intsize,charTArray[]）//将FA中的输入字母表存入数组TArray[]

{

intlen=0;

inti,j;

RightNode*pNode;

for（i=0;i

{

pNode=Array[i].link;

while（pNode）

{

for（j=0;j

if（pNode->tran==TArray[j]）break;

if（j==len）

{

TArray[len]=pNode->tran;

len++;

}

pNode=pNode->nextsibling;

}

}

}

voidGetState（LeftItemArray[],intsize,charnstate[],chararc,chartemp[]）

//将NFA确定化创建二维矩阵时取得新状态

{

inti=0;

while（nstate[i]!

='\0'）

{

for（intj=0;j

{

if（Array[j].state==nstate[i]）

{

RightNode*p=Array[j].link;

while（p!

=NULL）

{

if（p->tran==arc）

{

intk=0;

while（temp[k]!

='\0'）

{

if（p->nextstate==temp[k]）break;

k++;

}

if（temp[k]=='\0'）

{

temp[k]=p->nextstate;

temp[k+1]='\0';

}

}

p=p->nextsibling;

}

}

}

i++;

}

}

voidChange（StateItemSArray[],chartemp[],int&length,intMArray[][20],intindex,inti）

//取得新状态后对状态数组以及状态转换矩阵进行对应变化

{

intk;

if（temp[0]!

='\0'）

{

k=CheckExist（SArray,length,temp）;

MArray[index][i]=k;

if（k==length）

strcpy（SArray[length].newstates,temp）;

}

}

charFindNewState（LeftItemArray[],intsize,charS,chararc）//得到当前状态的下一状态

{

inti;

for（i=0;i

{

if（Array[i].state==S）

{

RightNode*p=Array[i].link;

while（p!

=NULL）

{

if（p->tran==arc）returnp->nextstate;

p=p->nextsibling;

}

}

}

returnNULL;

}

intFindy（charTArray[],chars）//取得输入字母在字母表中的下表

{

inti=0;

while（TArray[i]!

='\0'）

{

if（TArray[i]==s）returni;

i++;

}

}

voidCreateFA1（LeftItemArray[],intsize,charstart,charend）

//根据输入文法创建FA

{

if（CheckState（Array,size））

{

cout<<"此为确定有穷状态自动机!

"<

cout<<"DFAD=（";

}

else

{

cout<<"此为非确定有穷状态自动机!

"<

cout<<"NFAN=（";

}

cout<<"{";

Bianli1（Array,size）;

cout<<"},{";

Bianli2（Array,size）;

cout<<"},M,";

if（CheckState（Array,size））cout<

elsecout<<"{"<

cout<<","<<"{"<

cout<<"其中M:

"<

if（CheckState（Array,size））

Bianli31（Array,size）;

else

Bianli32（Array,size）;

}

voidCreateFA2（LeftItemArray[],intsize,charstart,charend,StateItemSArray[],charTArray[],int&length,intMArray[][20]）

//将NFA转换为DFA

{

chartemp[20];

intindex=0;

inti;

do

{

i=0;

while（TArray[i]!

='\0'）

{

temp[0]='\0';

GetState（Array,size,SArray[index].newstates,TArray[i],temp）;

Sort（temp,strlen（temp））;

Change（SArray,temp,length,MArray,index,i）;

i++;

}

index++;

}while（index<=length）;

}

voidDisplay（StateItemSArray[],charTArray[],intMArray[][20],intx,inty,charstart,charend）

//输出确定化的NFA

{

inti,j,k;

cout<<"将NFA转化为DFA!

"<

cout<<"DFAN'=（{";

for（i=0;i

{

if（i==0）cout<<"["<

elsecout<<",["<

}

cout<<"},{";

for（i=0;i

{

if（i==0）cout<<"["<

else

cout<<",["<

}

cout<<"},M',["<

cout<<"其中M':

"<

for（i=0;i

for（j=0;j

{

if（MArray[i][j]!

=-1）

{

k=MArray[i][j];

cout<<"M'（["<

}

}

cout<<"其中F'={";

k=0;

for（i=0;i

{

j=0;

while（SArray[i].newstates[j]!

='\0'）

{

if（SArray[i].newstates[j]==end）break;

j++;

}

if（SArray[i].newstates[j]!

='\0'）

{

if（k==0）cout<<"["<

else

cout<<",["<

k++;

}

}

cout<<"}"<

}

voidRunFA1（LeftItemArray[],intsize,charstart,charend）

{

charTD[20];

inti=0,j;

chars=start;

cout<<"请输入要推导的符号串:

";

cin>>TD;

cout<<"M（"<

for（j=0;TD[j]!

='\0';j++）

cout<

cout<<"）"<

while（TD[i]!

='\0'）

{

if（TD[i+1]!

='\0'）

{

cout<<"=M（M（"<

for（j=i+1;TD[j]!

='\0';j++）

cout<

cout<<"）"<

}

s=FindNewState（Array,size,s,TD[i]）;