實驗一-利用子集法構(gòu)造DFA

實驗一利用子集法構(gòu)造DFA一、實驗?zāi)康恼莆諏⒎谴_定有限自動機確定化的方法和過程實驗要求及內(nèi)容實驗要求：1.輸入一個NFA，輸出一個接受同一正規(guī)集的DFA；2.采用C++語言，實現(xiàn)該算法；3.編制測試程序；4.調(diào)試程序。實驗步驟：1.輸入一個NFA關(guān)系圖；2.通過一個轉(zhuǎn)換算法將NFA轉(zhuǎn)換為DFA；3.顯示DFA關(guān)系圖。三、實驗環(huán)境計算機、Windows操作系統(tǒng)、VisualC++程序集成環(huán)境。程序代碼#include"stdafx.h"#include<iostream>#include<algorithm>#include<queue>#include<stack>#include<string>usingnamespacestd;structedge{intstart,end;charc;}E[100],Ekong[100];//E保存所有的邊，Ekong保存轉(zhuǎn)換字符為空的邊structState{intH[100];//狀態(tài)集合intcount;//狀態(tài)集合中的元素個數(shù)intflag;//是否是接受狀態(tài)intmark;//狀態(tài)編號};intn;//n:邊數(shù)intnk=0;//空字符轉(zhuǎn)換的邊數(shù)intfirst,accept;//開始狀態(tài)，接受狀態(tài)charalpha[100];//輸入字母表,#代表空串intnumof_char=0;//字母表中的字符個數(shù)intuseof_char[256];//該轉(zhuǎn)換字符是否用過intf[200];//狀態(tài)屬性標(biāo)志：0表示始態(tài)，1表示接受態(tài)，-1表示中間態(tài)StateDFA[100];//DFA狀態(tài)集intuseof_DFA[100];//標(biāo)志構(gòu)造出來的狀態(tài)是否已存在intnumof_Dtran=0;//最后得到的DFA中的狀態(tài)數(shù)charDtran[100][100];//DFA狀態(tài)轉(zhuǎn)換表voidinput(){inti,s,e;charch;cout<<"請輸入轉(zhuǎn)換的有向邊數(shù)n："<<endl;cin>>n;cout<<"請輸入NFA的開始狀態(tài)："<<endl;cin>>first;cout<<"請輸入NFA的接受狀態(tài)(輸入-1結(jié)束)："<<endl;memset(f,-1,sizeof(f));memset(useof_char,0,sizeof(useof_char));f[first]=0;cin>>accept;while(accept!=-1){f[accept]=1; cin>>accept;}cout<<"請輸入NFA，起點，終點，轉(zhuǎn)換字符('#'表示空字符)："<<endl;intk=0;for(i=0;i<n;i++){ cin>>s>>e>>ch; E[i].start=s; E[i].end=e; E[i].c=ch; if(ch!='#'&&!useof_char[ch]) {alpha[numof_char++]=ch;useof_char[ch]=1; } if(ch=='#') {Ekong[nk].start=s;Ekong[nk].end=e;Ekong[nk].c=ch;nk++; }}}Statemove(StateT,chars)//c!='#'{Statetemp;temp.count=0;temp.mark=T.mark;inti,j=0,k=0;for(i=0;i<T.count;i++){j=0; while(j<n) {if(E[j].start==T.H[i]&&E[j].c==s){temp.H[temp.count++]=E[j].end;}j++;}}returntemp;}voidarriveBynone(intt,intresult[],int&num)//搜索狀態(tài)t通過一個或多個空字符到達的狀態(tài),結(jié)果存在result中{intk=0;intm=0;num=0;stack<int>S;S.push(t);intj;while(!S.empty()){ j=S.top(); S.pop(); m=0; while(m<nk) { if(Ekong[m].start==j) { result[num++]=Ekong[m].end; S.push(Ekong[m].end); } m++; }}}boolcheck(inti,StateT)//判斷狀態(tài)i是否在T中{intj;for(j=0;j<T.count;j++){if(T.H[j]==i)returntrue;}returnfalse;}Stateclosure(StateT)//求閉包{stack<int>STACK;Statetemp;inti,j,k;for(i=0;i<T.count;i++){ STACK.push(T.H[i]); temp.H[i]=T.H[i];}temp.count=T.count;temp.mark=T.mark; while(!STACK.empty()) { intt=STACK.top(); STACK.pop(); //搜索狀態(tài)t通過一個或多個空字符到達的狀態(tài) intsearch_result[100]; intnum; arriveBynone(t,search_result,num); for(j=0;j<num;j++) { if(!check(search_result[j],temp)) { temp.H[temp.count++]=search_result[j]; STACK.push(search_result[j]);} }}for(k=0;k<temp.count;k++){ if(f[temp.H[k]]==1) { temp.flag=1; break; } if(f[temp.H[k]]==0) { temp.flag=0; break; }}sort(temp.H,temp.H+temp.count);for(i=0;i<numof_Dtran;i++){ if(temp.count!=DFA[i].count) continue; sort(DFA[i].H,DFA[i].H+DFA[i].count); for(j=0;j<DFA[i].count;j++) { if(DFA[i].H[j]!=temp.H[j]) break; } if(j>=DFA[i].count) temp.mark=DFA[i].mark;}returntemp;}intcheck_inDFA()//檢查DFA中是否存在未被標(biāo)記的狀態(tài),有那么返回標(biāo)號，否那么返回-1{ inti; for(i=0;i<numof_Dtran;i++) { if(!useof_DFA[i]) returni;}return-1;}boolcheck_whetherin_DFA(StateT){inti,j;sort(T.H,T.H+T.count);for(i=0;i<numof_Dtran;i++){ if(T.count!=DFA[i].count) continue; sort(DFA[i].H,DFA[i].H+DFA[i].count); for(j=0;j<DFA[i].count;j++) { if(DFA[i].H[j]!=T.H[j]) break; } if(j>=DFA[i].count) returntrue;}if(i>=numof_Dtran) returnfalse;else returntrue;}voidchild_method(){intm,n;for(m=0;m<100;m++) for(n=0;n<100;n++) Dtran[m][n]='#'; for(m=0;m<100;m++) DFA[m].flag=-1; StateS0,U;S0.flag=0;S0.count=1;S0.H[0]=first;StateT;T=closure(S0);T.mark=0;T.flag=0;DFA[numof_Dtran++]=T;memset(useof_DFA,0,sizeof(useof_DFA));intj=check_inDFA(); intk; while(j!=-1) { useof_DFA[j]=1; for(k=0;k<numof_char;k++) { U=closure(move(DFA[j],alpha[k])); //ifU不在DFA中 if(!check_whetherin_DFA(U)) {U.mark=numof_Dtran; DFA[numof_Dtran++]=U; } Dtran[DFA[j].mark][U.mark]=alpha[k]; } j=check_inDFA();}}voidprint(){inti,j;for(i=0;i<numof_Dtran;i++){ cout<<i<<":"; for(j=0;j<DFA[i].count;j++) cout<<DFA[i].H[j]<<""; if(DFA[i].flag==1) cout<<"此為DFA的接受狀態(tài)"; if(DFA[i].flag==0) cout<<"此為DFA的開始狀態(tài)"; cout<<endl;}cout<<endl;for(i=0;i<numof_Dtran;i++){ for(j=0;j<numof_Dtran;j++) {if(Dtran[i][j]!='#') {cout<<i<<"->"<<j<<"By"<<Dtran[i][j]<<endl; } }}}voidjudge(stringch){ inti,j,k;intnum=ch.length(); Statetemp; k=0; for(i=0;i<num;i++) { for(j=0;j<numof_Dtran;j++) { if(Dtran[k][j]==alpha[i]) { temp=DFA[j]; k=j; break; } }}if(temp.flag!=1) cout<<"字符串"<<ch<<"無法由該DFA得到"<<endl;else cout<<"字符串"<<ch<<"可以由該DFA得到"<<endl;cout<<endl;}int_tmain(intargc,_TCHAR*argv[]){input();child_method();cout<<endl;print();strings;while(cin>>s) judge(s);system("pause");return0;}實驗結(jié)果算法分析使用子集構(gòu)造法對非確定有限自動機進行確定化的過程中存在大量重復(fù)計算的問題。為解決此問題,基于非確定有限自動機的特點并針對子集構(gòu)造法的缺乏,提出了一種優(yōu)化的非確定有限自動機確定化算法。首先定義了識別符的有效引出狀態(tài)集概念并證明了ε-closure的并定理以保證算法的正確性,其次給出了用于防止重復(fù)計算的識別符的有效引出狀態(tài)集的構(gòu)造子算法和單狀態(tài)集的ε-closure的求算子算法,基于這兩個子算法給出了優(yōu)化的非確定有限自動機確定化算法,最后將算法應(yīng)用于實例,實驗結(jié)果說明計算量遠小于子集構(gòu)造法的計算量。相比子集構(gòu)造法,算法能更有效地對非確定有限自動機進行確定化。七、實驗小結(jié)以前上課時有許多的問題并沒有真正的認(rèn)識到，但通過這次實驗，使我掌握了許多更重要的知識點。通過實驗，我們可以知道將NFA轉(zhuǎn)換成接受同樣語言的DFA的算法稱為子集構(gòu)造算法。NFA變換到DFA的根本思想是：讓DFA的每個狀態(tài)對應(yīng)NFA的一個狀態(tài)集。實驗實現(xiàn)了NFA到DFA的轉(zhuǎn)換。實驗二THOMPSON算法的實現(xiàn)一、實驗?zāi)康恼莆諏⒄?guī)表達式轉(zhuǎn)換為NFA的方法和過程實驗要求及內(nèi)容1.輸入一個正規(guī)表達式，輸出一個接受同一語言的NFA2.采用C++語言，實現(xiàn)該算法3.編制測試程序4.調(diào)試程序三、實驗環(huán)境計算機、Windows操作系統(tǒng)、VisualC++程序集成環(huán)境。四、程序代碼#include"Thompson.h"voidmain(){ stringRegular_Expression="(a|b)*abb"; cellNFA_Cell; input(Regular_Expression);//調(diào)試需要先屏蔽 Regular_Expression=add_join_symbol(Regular_Expression); Regular_Expression=postfix(Regular_Expression); NFA_Cell=express_2_NFA(Regular_Expression); Display(NFA_Cell);}cellexpress_2_NFA(stringexpression){ intlength=expression.size(); charelement; cellCell,Left,Right; stack<cell>STACK; for(inti=0;i<length;i++) { element=expression.at(i); switch(element) { case'|': Right=STACK.top(); STACK.pop(); Left=STACK.top(); STACK.pop(); Cell=do_Unite(Left,Right); STACK.push(Cell); break; case'*': Left=STACK.top(); STACK.pop(); Cell=do_Star(Left); STACK.push(Cell); break; case'+': Right=STACK.top(); STACK.pop(); Left=STACK.top(); STACK.pop(); Cell=do_Join(Left,Right); STACK.push(Cell); break; default: Cell=do_Cell(element); STACK.push(Cell); } } cout<<"處理完畢!"<<endl; Cell=STACK.top(); STACK.pop(); returnCell;}celldo_Unite(cellLeft,cellRight){ cellNewCell; NewCell.EdgeCount=0; edgeEdge1,Edge2,Edge3,Edge4; stateStartState=new_StateNode(); stateEndState=new_StateNode(); Edge1.StartState=StartState; Edge1.EndState=Left.EdgeSet[0].StartState; Edge1.TransSymbol='#'; Edge2.StartState=StartState; Edge2.EndState=Right.EdgeSet[0].StartState; Edge2.TransSymbol='#'; Edge3.StartState=Left.EdgeSet[Left.EdgeCount-1].EndState; Edge3.EndState=EndState; Edge3.TransSymbol='#'; Edge4.StartState=Right.EdgeSet[Right.EdgeCount-1].EndState; Edge4.EndState=EndState; Edge4.TransSymbol='#';//先將Left和Right的EdgeSet復(fù)制到NewCell cell_EdgeSet_Copy(NewCell,Left); cell_EdgeSet_Copy(NewCell,Right); //將新構(gòu)建的四條邊參加EdgeSet NewCell.EdgeSet[NewCell.EdgeCount++]=Edge1; NewCell.EdgeSet[NewCell.EdgeCount++]=Edge2; NewCell.EdgeSet[NewCell.EdgeCount++]=Edge3; NewCell.EdgeSet[NewCell.EdgeCount++]=Edge4; //構(gòu)建NewCell的啟示狀態(tài)和結(jié)束狀態(tài) NewCell.StartState=StartState; NewCell.EndState=EndState; returnNewCell;}//處理abcelldo_Join(cellLeft,cellRight){ for(inti=0;i<Right.EdgeCount;i++) { if(Right.EdgeSet[i].StartState.StateNamepare(Right.StartState.StateName)==0) { Right.EdgeSet[i].StartState=Left.EndState; STATE_NUM--; } elseif(Right.EdgeSet[i].EndState.StateNamepare(Right.StartState.StateName)==0) { Right.EdgeSet[i].EndState=Left.EndState; STATE_NUM--; } } Right.StartState=Left.EndState; cell_EdgeSet_Copy(Left,Right); Left.EndState=Right.EndState; returnLeft;}celldo_Star(cellCell){ cellNewCell; NewCell.EdgeCount=0; edgeEdge1,Edge2,Edge3,Edge4; stateStartState=new_StateNode(); stateEndState=new_StateNode(); //構(gòu)建邊 Edge1.StartState=StartState; Edge1.EndState=EndState; Edge1.TransSymbol='#'; Edge2.StartState=Cell.EndState; Edge2.EndState=Cell.StartState; Edge2.TransSymbol='#'; Edge3.StartState=StartState; Edge3.EndState=Cell.StartState; Edge3.TransSymbol='#'; Edge4.StartState=Cell.EndState; Edge4.EndState=EndState; Edge4.TransSymbol='#'; //構(gòu)建單元 cell_EdgeSet_Copy(NewCell,Cell); NewCell.EdgeSet[NewCell.EdgeCount++]=Edge1; NewCell.EdgeSet[NewCell.EdgeCount++]=Edge2; NewCell.EdgeSet[NewCell.EdgeCount++]=Edge3; NewCell.EdgeSet[NewCell.EdgeCount++]=Edge4; NewCell.StartState=StartState; NewCell.EndState=EndState; returnNewCell;}celldo_Cell(charelement){ cellNewCell; NewCell.EdgeCount=0; edgeNewEdge; stateStartState=new_StateNode(); stateEndState=new_StateNode(); NewEdge.StartState=StartState; NewEdge.EndState=EndState; NewEdge.TransSymbol=element; NewCell.EdgeSet[NewCell.EdgeCount++]=NewEdge; NewCell.StartState=NewCell.EdgeSet[0].StartState; NewCell.EndState=NewCell.EdgeSet[0].EndState;//EdgeCount此時為1 returnNewCell;}voidcell_EdgeSet_Copy(cell&Destination,cellSource){ intD_count=Destination.EdgeCount; intS_count=Source.EdgeCount; for(inti=0;i<S_count;i++) { Destination.EdgeSet[D_count+i]=Source.EdgeSet[i]; } Destination.EdgeCount=D_count+S_count;}statenew_StateNode(){ statenewState; newState.StateName=STATE_NUM+65;//轉(zhuǎn)換成大寫字母 STATE_NUM++; returnnewState;}voidinput(string&RegularExpression){ cout<<"請輸入正那么表達式：〔操作符：()*|;字符集：a~zA~Z〕"<<endl; do { cin>>RegularExpression; }while(!check_legal(RegularExpression)); }intcheck_legal(stringcheck_string){ if(check_character(check_string)&&check_parenthesis(check_string)) { returntrue; } returnfalse;}intcheck_character(stringcheck_string){ intlength=check_string.size(); for(inti=0;i<length;i++) { charcheck=check_string.at(i); if(is_letter(check))//小寫和大寫之間有5個字符，故不能連續(xù)判斷 { } elseif(check=='('||check==')'||check=='*'||check=='|') { } else { cout<<"含有不合法的字符!"<<endl; cout<<"請重新輸入:"<<endl; returnfalse; } } returntrue;}intcheck_parenthesis(stringcheck_string){ intlength=check_string.size(); char*check=newchar[length]; strcpy(check,check_string.c_str()); stack<int>STACK; for(inti=0;i<length;i++) { if(check[i]=='(') STACK.push(i); elseif(check[i]==')') { if(STACK.empty()) { cerr<<"有多余的右括號"<<endl;//暫時不記錄匹配位置location cout<<"請重新輸入:"<<endl; returnfalse; } else STACK.pop(); } } if(!STACK.empty()) { cerr<<"有多余的左括號"<<endl; cout<<"請重新輸入:"<<endl; returnfalse; } returntrue;}intis_letter(charcheck){ if(check>='a'&&check<='z'||check>='A'&&check<='Z') returntrue; returnfalse;}stringadd_join_symbol(stringadd_string){ stringcheck_string="abcdefg\0aaa"; cout<<check_string<<endl; intlength=check_string.size(); char*check=newchar[2*length]; strcpy(check,check_string.c_str()); cout<<check<<endl; char*s="ssss\0aa"; cout<<s<<endl; stringa(s); cout<<a<<endl; intlength=add_string.size(); intreturn_string_length=0; char*return_string=newchar[2*length];//做多是兩倍 charfirst,second; for(inti=0;i<length-1;i++) { first=add_string.at(i); second=add_string.at(i+1); return_string[return_string_length++]=first; if(first!='('&&first!='|'&&is_letter(second)) { return_string[return_string_length++]='+'; } elseif(second=='('&&first!='|'&&first!='(') { return_string[return_string_length++]='+'; } } return_string[return_string_length++]=second; return_string[return_string_length]='\0'; stringSTRING(return_string); cout<<"加'+'后的表達式："<<STRING<<endl; returnSTRING; }intisp(charc){ switch(c) { case'#':return0; case'(':return1; case'*':return7; case'|':return5; case'+':return3; case')':return8; } cerr<<"ERROR!"<<endl; returnfalse;}inticp(charc){ switch(c) { case'#':return0; case'(':return8; case'*':return6; case'|':return4; case'+':return2; case')':return1; } cerr<<"ERROR!"<<endl; returnfalse;}stringpostfix(stringe){ e=e+"#"; stack<char>s; charch='#',ch1,op; s.push(ch); stringout_string=""; intread_location=0; ch=e.at(read_location++); while(!s.empty()) { if(is_letter(ch)) { out_string=out_string+ch; ch=e.at(read_location++); } else { ch1=s.top(); if(isp(ch1)<icp(ch)) { s.push(ch); ch=e.at(read_location++); } elseif(isp(ch1)>icp(ch)) { op=s.top(); s.pop(); out_string=out_string+op; } else { op=s.top(); s.pop(); if(op=='(') ch=e.at(read_location++); } } } cout<<"后綴表達式："<<out_string<<endl; returnout_string;}voidDisplay(cellCell){ cout<<"NFA的邊數(shù)："<<Cell.EdgeCount<<endl; cout<<"NFA的起始狀態(tài)："<<Cell.StartState.StateName<<endl; cout<<"NFA的結(jié)束狀態(tài)："<<Cell.EndState.StateName<<endl; for(inti=0;i<Cell.EdgeCount;i++) { <<"轉(zhuǎn)換符："<<Cell.EdgeSet[i].TransSymbol<<endl; } cout<<"結(jié)束"<<endl;}算法分析Thompson算法的根本思想,提出一種利用算符優(yōu)先關(guān)系表來實現(xiàn)Thompson算法的方法,以實現(xiàn)正規(guī)式到有窮自動機的轉(zhuǎn)換.描述了算法的解決思路、算符優(yōu)先表的生成和NFA的表示.算法測試說明,該方法可以大大簡化算法的實現(xiàn),提高編譯程序的工作效率.六、實驗結(jié)果實驗小結(jié)通過這次試驗，我掌握了如何將正規(guī)表達式轉(zhuǎn)換為NFA的方法和過程。另外，我們要知道在構(gòu)造過程中，每次構(gòu)造的新狀態(tài)都要賦予不同的名字。這樣，任何NFA的兩個狀態(tài)都具有不同的名字。即使同一符號在r中出現(xiàn)屢次，我們也要為該符號的每個實例創(chuàng)立一個獨立的帶有自己狀態(tài)的NFA。實驗三詞法分析與語法分析程序設(shè)計一、實驗?zāi)康恼莆沼嬎銠C語言的詞法分析程序和語法分析程序的設(shè)計方法二、實驗要求、內(nèi)容及步驟實驗要求：1．根據(jù)以下的正規(guī)式，畫出狀態(tài)圖；標(biāo)識符：<字母>(<字母>|<數(shù)字字符>)*十進制整數(shù)：0|〔1|2|3|4|5|6|7|8|9〕〔0|1|2|3|4|5|6|7|8|9〕*運算符：+*2．根據(jù)狀態(tài)圖，設(shè)計詞法分析函數(shù)intscan()，實現(xiàn)從鍵盤讀入數(shù)據(jù)，分析出一個單詞。3．對于只含有+、*運算的算術(shù)表達式的文法，編寫相應(yīng)的語法分析程序，要求用LL(1)分析表實現(xiàn)，并以id+id*id為例進行測試。E—＞TE′E′—＞+TE′|εT—＞FT′T′—＞*FT′|εF—＞〔E〕|id實驗步驟1、根據(jù)狀態(tài)圖，設(shè)計詞法分析算法2、采用C++語言，實現(xiàn)該算法3、編制測試程序4、調(diào)試程序：輸入一組單詞，檢查輸出結(jié)果。5、編制給定文法的非遞歸的預(yù)測分析程序，并加以測試。三、實驗環(huán)境計算機、Windows操作系統(tǒng)、VisualC++程序集成環(huán)境。實驗原理1.詞法分析器讀入輸入串，將其轉(zhuǎn)換成將被語法分析器分析的詞法單元序列。產(chǎn)生下述小語言的單詞序列。單詞符號種別編碼DIMIFDOSTOPEND

標(biāo)識符常數(shù)〔整〕=+***，〔〕1234567891011121314這個小語言的單詞符號的狀態(tài)轉(zhuǎn)換圖，如下列圖：2.語法分析是決定如何使用一個文法生成一個終結(jié)符串的過程。語法分析器能識別由加+減-乘*除/乘方^括號〔〕操作數(shù)所組成的算術(shù)表達式，其文法如下：E→E+T|E-T|TT→T*F|T/F|FF→P^F|Pp→(E)|i使用的算法可以是：預(yù)測分析法；遞歸下降分析法；算符優(yōu)先分析法；LR分析法等。3.中間代碼生成器產(chǎn)生上述算術(shù)表達式的中間代碼〔四元式序列〕。id+*()$EE—＞TE′E—＞TE′E′E′—＞+TE′E′—＞εE′—＞εTT—＞FT′T—＞FT′T′T′—＞εT′—＞*FT′T′—＞εT′—＞εFF—＞idF—＞(E)五、程序代碼〔1〕詞法分析程序的數(shù)據(jù)結(jié)構(gòu)與算法：#include<string.h>#include<iostream>usingnamespacestd;charprog[100],token[10];charch;intsyn,p,m=0,n,row,sum=0;char*rwtab[20]={"dim","if","do","stop","end","and","begin","bool","case","char", "false","for","int","not","or","set","then","true","until","while"};voidscaner(){ for(n=0;n<9;n++)token[n]=NULL; ch=prog[p++]; while(ch=='') { ch=prog[p]; p++; } if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')) { m=0; while((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')) { token[m++]=ch; ch=prog[p++]; } token[m++]='\0'; p--; syn=21; for(n=0;n<20;n++) { if(strcmp(token,rwtab[n])==0) { syn=n+1; break; } } } elseif((ch>='0'&&ch<='9')) { { sum=0; while((ch>='0'&&ch<='9')) { sum=sum*10+ch-'0'; ch=prog[p++]; } } p--; syn=7+15; if(sum>32767) syn=-1; } elseswitch(ch) {case'=':syn=8+15;token[0]=ch;break; case'+':syn=9+15;token[0]=ch;break; case'*': m=0; token[m++]=ch; ch=prog[p++]; if(ch=='*') { syn=11+15; token[m++]=ch; } else { syn=10+15; p--; }break;case',':syn=12+15;token[0]=ch;break;case'(':syn=13+15;token[0]=ch;break;case')':syn=14+15;token[0]=ch;break;case'#':syn=0;token[0]=ch;break;case'<':m=0;token[m++]=ch; ch=prog[p++]; if(ch=='>') { syn=17+15; token[m++]=ch; } elseif(ch=='=') { syn=16+15; token[m++]=ch; } else { syn=15+15; p--; } break;case'>':m=0;token[m++]=ch; ch=prog[p++]; if(ch=='=') { syn=19+15; token[m++]=ch; } else { syn=18+15; p--; } break;case':':m=0;token[m++]=ch; ch=prog[p++]; if(ch=='=') { syn=21+15; token[m++]=ch; } else { syn=20+15; p--; } break;case'/':syn=22+15;token[0]=ch;break;case'-':syn=23+15;token[0]=ch;break;case';':syn=24+15;token[0]=ch;break;default:syn=-1;break; }}voidmain(){ p=0; row=1; cout<<endl<<endl<<endl; cout<<"詞法分析"<<endl<<endl; cout<<"請輸入一段程序〔以#結(jié)束〕:"; do { cin.get(ch); prog[p++]=ch; } while(ch!='#'); p=0; cout<<endl<<"詞法分析結(jié)果如下"<<endl; cout<<"種別編碼自身值"<<endl; do { scaner(); switch(syn) { case22:cout<<"("<<syn<<","<<sum<<")"<<endl;break; case-1:cout<<"Errorinrow"<<row<<"!"<<endl;break;default:cout<<"("<<syn<<","<<token<<")"<<endl;break; } } while(syn!=0);}〔2〕語法分析程序的數(shù)據(jù)結(jié)構(gòu)與算法：#include<string.h>#include<malloc.h>#include<iostream>usingnamespacestd;typedefstructtable//分析表存儲結(jié)構(gòu){charm[100];}table;tableM[100][100];//定義分析表typedefstructstacknode//定義棧內(nèi)元素節(jié)點(帶頭結(jié)點〔為空〕的){chardata;structstacknode*next;}stackk;voidinitlink(stackk*&s)//初始化新棧{s=(stackk*)malloc(sizeof(stackk));s->next=NULL;}voidpoplink(stackk*&s)//頂元素出棧{stackk*p;charv;if(s->next!=NULL){p=s->next;v=p->data;s->next=p->next;}free(p);}voidpushlink(stackk*&s,charx)//新元素入棧{stackk*p;p=(stackk*)malloc(sizeof(stackk));p->data=x;p->next=s->next;s->next=p;}voiddisplay(stackk*s)//打印現(xiàn)實顯示棧內(nèi)元素{stackk*p;inti=0,j;charst[100];p=s->next;while(p!=NULL){st[i++]=p->data;p=p->next;}for(j=i-1;j>=0;j--)printf("%c",st[j]);for(j=0;j<16-i;j++)//打印對齊格式printf("%c",'');}chargettop(stackk*s)//返回棧頂元素值{if(s->next==NULL)return0;elsereturns->next->data;}intfind(charc,chararray[])//查找函數(shù)，{inti;intflag=0;for(i=0;i<100;i++){if(c==array[i])flag=1;}returnflag;}intlocation(charc,chararray[])//定位函數(shù),指出字符所在位置{inti;for(i=0;i<100;i++){if(c==array[i])returni;}}voiderror()//出錯函數(shù)定義{printf("%15c出錯!\n",'');}voidanalyse(charVn[],charVt[]){inti,j,m,p,q,length,t,h;charw,X;charstr[100];opt0:scanf("%s",str);for(i=0;i<strlen(str);i++){if(!find(str[i],Vt)){printf("輸入字符串有誤!請重新輸入!");gotoopt0;break;}}stackk*st;initlink(st);pushlink(st,'#');pushlink(st,Vn[0]);//#與識別符號入棧j=0;h=1;w=str[0];printf("步驟%-12c分析棧%-24c剩余輸入串%-12c所用產(chǎn)生式\n",'','','');opt1:printf("%-16d",h);//顯示步驟h++;display(st);//顯示分析棧中內(nèi)容X=gettop(st);//上托棧頂符號放入Xpoplink(st);for(intk=0;k<14+j;k++)//打印對齊格式printf("%c",'');for(t=j;t<strlen(str);t++){printf("%c",str[t]);//顯示剩余字符串}if(find(X,Vt)&&X!='#')//分析棧的棧頂元素和剩余輸入串的第一個元素相比擬{if(X==w){printf("%15c匹配\n",X);j++;w=str[j];gotoopt1;}elseerror();}else{if(X=='#'){if(X==w){printf("%8c是該文法的句子！\n",'');}else