词法分析NFA到DFA.docx
- 文档编号:10025921
- 上传时间:2023-05-23
- 格式:DOCX
- 页数:22
- 大小:18.25KB
词法分析NFA到DFA.docx
《词法分析NFA到DFA.docx》由会员分享,可在线阅读,更多相关《词法分析NFA到DFA.docx(22页珍藏版)》请在冰点文库上搜索。
词法分析NFA到DFA
#include
#include
#include
#include
#include
#include
usingnamespacestd;
classNFA_Node;
classTrans
{
public:
charincept;
NFA_Node*des;
Trans(charincept,NFA_Node*des)
{
this->incept=incept;
this->des=des;
}
};
classNFA_Node
{
public:
intstateID;
vector
boolvisit;
NFA_Node(intstateID)
{
visit=false;
this->stateID=stateID;
}
voidAddTrans(Trans*tt)
{
t.push_back(tt);
}
};
classNFA
{
public:
NFA_Node*start;
NFA_Node*end;
NFA(){}
NFA(intSID,charc)
{
NFA_Node*s1=newNFA_Node(SID);
NFA_Node*s2=newNFA_Node(SID+1);
Trans*tt=newTrans(c,s2);
s1->AddTrans(tt);
start=s1;
end=s2;
}
};
classConverter
{
public:
intS_ID;
Converter(stringstr)
{
pretreat(str);
Houzhui(this->lamb);
S_ID=1;
}
Converter(){S_ID=1;}
voidshow()
{
cout< } NFAToNFA() { //stNFA.Clear(); //Operator_Stack.Clear(); NFAtempb,tempb1,tempb2; chartempc1; for(inti=0;i { tempc1=lamb[i]; if(isOperator(tempc1)) { switch(tempc1) { case'|': tempb1=stNFA.top(); stNFA.pop(); tempb2=stNFA.top(); stNFA.pop(); tempb1=Union(tempb2,tempb1); stNFA.push(tempb1); break; case'&': tempb1=stNFA.top(); stNFA.pop(); tempb2=stNFA.top(); stNFA.pop(); tempb2=Connect(tempb1,tempb2); stNFA.push(tempb2); break; case'*': tempb1=stNFA.top(); stNFA.pop(); tempb1=Closure(tempb1); stNFA.push(tempb1); break; } } else { tempb=NFA(S_ID,tempc1); S_ID+=2; stNFA.push(tempb); } } tempb=stNFA.top(); stNFA.pop(); returntempb; } private: stack stack stringlamb; boolisOperator(charc) { switch(c) { case'|': case'&': case'(': case')': case'! ': case'*': returntrue; default: returnfalse; } } intgetOperatorNumber(chart1) { switch(t1) { case'$': return0; case'! ': return1; case')': return2; case'|': return3; case'&': return4; case'*': return5; case'(': return6; default: return7; } } boolOperator_Less_Than(chart1,chart2) { inttemp1=getOperatorNumber(t1); inttemp2=getOperatorNumber(t2); if(temp1<=temp2) returntrue; returnfalse; } voidpretreat(stringstr)//穿进去原始正则表达式使ab变成a&b { inti=0; charc,pc; pc=str[i]; c=str[++i]; while(str[i]! ='\0') { if(((pc==')'&&c=='('))||(! isOperator(pc)&&! isOperator(c))||(! isOperator(pc)&&c=='(')||(pc==')'&&! isOperator(c))||(pc=='*'&&! isOperator(c))||(pc=='*'&&c=='('))//四种情况需要加& str.insert(i,"&"); pc=str[i++]; c=str[i]; } str+="! "; this->lamb=str; } voidHouzhui(stringlamb) { stringl=""; Operator_Stack.push('$'); chartempc,tempc2; for(inti=0;i { tempc=lamb[i]; if(isOperator(tempc)) { switch(tempc) { case'(': Operator_Stack.push(tempc);break; case')': while(Operator_Stack.top()! ='(') { tempc2=Operator_Stack.top(); Operator_Stack.pop(); l+=tempc2; } Operator_Stack.pop(); break; default: tempc2=Operator_Stack.top(); while(tempc2! ='('&&Operator_Less_Than(tempc,tempc2)) { tempc2=Operator_Stack.top(); Operator_Stack.pop(); l+=tempc2; tempc2=Operator_Stack.top(); } Operator_Stack.push(tempc); break; } } else l+=tempc; } this->lamb=l; } NFA&Connect(NFAG1,NFAG2)//把G1连在G2后面 { Trans*t=newTrans('@',G1.start); G2.end->AddTrans(t); G2.end=G1.end; returnG2; } NFA&Union(NFAG1,NFAG2)//G1|G2 { NFA_Node*n1=newNFA_Node(S_ID++); Trans*t1=newTrans('@',G1.start); Trans*t2=newTrans('@',G2.start); n1->AddTrans(t1); n1->AddTrans(t2); NFA_Node*n2=newNFA_Node(S_ID++); Trans*t3=newTrans('@',n2); Trans*t4=newTrans('@',n2); G1.end->AddTrans(t3); G2.end->AddTrans(t4); NFA*G=newNFA(); G->start=n1; G->end=n2; return*G; } NFA&Closure(NFAG2)//G2* { Trans*t=newTrans('#',G2.start);//#表示是重复的空输入 G2.end->AddTrans(t); NFA_Node*n1=newNFA_Node(S_ID++); Trans*t1=newTrans('@',n1); G2.end->AddTrans(t1); NFA_Node*n2=newNFA_Node(S_ID++); Trans*t2=newTrans('@',G2.start); n2->AddTrans(t2); Trans*t3=newTrans('@',n1); n2->AddTrans(t3); NFA*G=newNFA(); G->start=n2; G->end=n1; return*G; } }; voidDisplay(NFA&G,set { cout<<"正则表达式转NFA"< queue MyQueue.push(G.start); cout<<"开始状态"< chartt; while(! MyQueue.empty()) { NFA_Node*tmp=MyQueue.front(); MyQueue.pop(); V.push_back(tmp); tmp->visit=true; if(tmp->t.size()>0) cout<<"从状态"< if(tmp->t.size()>0) for(inti=0;i { tt=tmp->t[i]->incept; if(tt! ='@'&&tt! ='#') S.insert(tt); if(tt=='@') { cout< if(tmp->t[i]->des->t.size()==0)cout<<"接收状态"; cout< if(tmp->t[i]->des->visit==false) {MyQueue.push(tmp->t[i]->des);tmp->t[i]->des->visit=true;} } elseif(tt=='#') { cout< } else { cout< if(tmp->t[i]->des->t.size()==0)cout<<"接收状态"; cout< if(tmp->t[i]->des->visit==false) {MyQueue.push(tmp->t[i]->des);tmp->t[i]->des->visit=true;} } } } cout<<"接收状态"< } classDFA_Edge; classDFA_Node { public: intstateID; vector vector boolflag; DFA_Node(ints) { flag=false; stateID=s; } }; classDFA_Edge { public: charincept; DFA_Node*des; boolvisit; DFA_Edge(chara,DFA_Node*&b) { incept=a; des=b; visit=false; } }; constintMAX=100; classNFA_To_DFA { public: intMaxStatus; intT[MAX][MAX]; intvisit[MAX]; vector set vector NFA_Node*start; vector intcando;//存NFA的接收状态 NFA_To_DFA(intmax,NFA_Node*&S,intcando) { this->MaxStatus=max; this->start=S; this->cando=cando; Init(); for(inti=0;i<=MAX;i++) for(intj=0;j<=MAX;j++) T[i][j]=0; } voidInit() { for(inti=0;i<=this->MaxStatus;i++) { this->visit[i]=0; } this->tmp.clear(); } NFA_Node*&find(intst) { for(inti=0;i if(nfa[i]->stateID==st)returnnfa[i]; } DFA_Node*&finddfa(intst) { for(inti=0;i if(dfa[i]->stateID==st)returndfa[i]; } voidfindclosure(NFA_Node*p) { visit[p->stateID]=1; visit[0]++; if(p->t.size()==0)return; for(inti=0;i { if(! visit[p->t[i]->des->stateID]&&(p->t[i]->incept=='#'||p->t[i]->incept=='@')) findclosure(p->t[i]->des); } } voidclosure() { for(inti=0;i { findclosure(tmp[i]); } } intAddStatus()//T[0][0]当前状态集合数初始为0 { if(visit[0]==0)//表示没有状态 return-2; for(inti=1;i<=T[0][0];i++) { if(visit[0]! =T[i][0])//此集合状态数不一样则跳过 continue; intj=1; for(;j<=MaxStatus;j++) if(visit[j]! =T[i][j])//有一个状态不一样则跳过 break; if(j==(MaxStatus+1))//说明矩阵T中已有此集合,并返回位置 returni; } T[0][0]++; for(inti=0;i<=MaxStatus;i++) T[T[0][0]][i]=visit[i]; //cout< return-1; }//返回-1表示插入了新状态集合 voidmoveto(intst,charc) { //if(st==2)cout< for(inti=1;i<=MaxStatus;i++) { if(T[st][i]) { NFA_Node*p=find(i); if(p->t.size()>0) for(intj=0;j if(p->t[j]->incept==c) {tmp.push_back(p->t[j]->des);}//cout< } } } voidConvert() { inti,j; findclosure(start); AddStatus(); DFA_Node*s1=newDFA_Node (1); if(visit[cando])s1->flag=true; for(i=1;i<=MaxStatus;i++) if(visit[i])s1->ori.push_back(i); dfa.push_back(s1); Init(); //cout< for(i=1;i<=T[0][0];i++)//i目前的状态集合号 { for(set : iteratort1=Alpha.begin();t1! =Alpha.end();t1++) { moveto(i,*t1); closure(); if((j=AddStatus())>=0)//没有新状态产生 { DFA_Edge*e1=newDFA_Edge(*t1,finddfa(j)); finddfa(i)->t.push_back(e1); } elseif(j==-1)//产生了新状态 { DFA_Node*d1=newDFA_Node(T[0][0]); if(visit[cando])d1->flag=true;//是否是接收状态 for(inttt=1;tt<=MaxStatus;tt++) if(visit[tt])d1->ori.push_back(tt);//把原状态加进去 dfa.push_back(d1); DFA_Edge*e1=newDFA_Edge(*t1,finddfa(T[0][0])); finddfa(i)->t.push_back(e1); //cout< } Init(); } } } voidshow(DFA_Node*p) { if(p->ori.size()==0)return; cout<<"(原状态"; for(inti=0;i cout< cout<<")"; } voidDisplay() { cout<<"NFA转DFA"< for(inti=0;i dfs(dfa[i]); } voiddfs(DFA_Node*&p) { if(p->t.size()>0) for(inti=0;i if(p->t[i]->visit==false) { cout< if(p->flag)cout<<"(接收状态)"; show(p); cout<<"---"< show(p->t[i]->des); if(p->t[i]->des->flag)cout<<"(接收状态)"; cout< p->t[i]->visit
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 词法 分析 NFA DFA