实验一-利用子集法构造DFA

实验一利用子集法构造DFA一、实验目的掌握将非确定有限自动机确定化的方法和过程实验要求及内容实验要求：1.输入一个NFA，输出一个接受同一正规集的DFA；2.采用C++语言，实现该算法；3.编制测试程序；4.调试程序。实验步骤：1.输入一个NFA关系图；2.通过一个转换算法将NFA转换为DFA；3.显示DFA关系图。三、实验环境计算机、Windows操作系统、VisualC++程序集成环境。程序代码#include"stdafx.h"#include<iostream>#include<algorithm>#include<queue>#include<stack>#include<string>usingnamespacestd;structedge{intstart,end;charc;}E[100],Ekong[100];//E保存所有的边，Ekong保存转换字符为空的边structState{intH[100];//状态集合intcount;//状态集合中的元素个数intflag;//是否是接受状态intmark;//状态编号};intn;//n:边数intnk=0;//空字符转换的边数intfirst,accept;//开始状态，接受状态charalpha[100];//输入字母表,#代表空串intnumof_char=0;//字母表中的字符个数intuseof_char[256];//该转换字符是否用过intf[200];//状态属性标志：0表示始态，1表示接受态，-1表示中间态StateDFA[100];//DFA状态集intuseof_DFA[100];//标志构造出来的状态是否已存在intnumof_Dtran=0;//最后得到的DFA中的状态数charDtran[100][100];//DFA状态转换表voidinput(){inti,s,e;charch;cout<<"请输入转换的有向边数n："<<endl;cin>>n;cout<<"请输入NFA的开始状态："<<endl;cin>>first;cout<<"请输入NFA的接受状态(输入-1结束)："<<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，起点，终点，转换字符('#'表示空字符)："<<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通过一个或多个空字符到达的状态,结果存在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)//判断状态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通过一个或多个空字符到达的状态 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中是否存在未被标记的状态,有那么返回标号，否那么返回-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的接受状态"; if(DFA[i].flag==0) cout<<"此为DFA的开始状态"; 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;}实验结果算法分析使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的问题。为解决此问题,基于非确定有限自动机的特点并针对子集构造法的缺乏,提出了一种优化的非确定有限自动机确定化算法。首先定义了识别符的有效引出状态集概念并证明了ε-closure的并定理以保证算法的正确性,其次给出了用于防止重复计算的识别符的有效引出状态集的构造子算法和单状态集的ε-closure的求算子算法,基于这两个子算法给出了优化的非确定有限自动机确定化算法,最后将算法应用于实例,实验结果说明计算量远小于子集构造法的计算量。相比子集构造法,算法能更有效地对非确定有限自动机进行确定化。七、实验小结以前上课时有许多的问题并没有真正的认识到，但通过这次实验，使我掌握了许多更重要的知识点。通过实验，我们可以知道将NFA转换成接受同样语言的DFA的算法称为子集构造算法。NFA变换到DFA的根本思想是：让DFA的每个状态对应NFA的一个状态集。实验实现了NFA到DFA的转换。实验二THOMPSON算法的实现一、实验目的掌握将正规表达式转换为NFA的方法和过程实验要求及内容1.输入一个正规表达式，输出一个接受同一语言的NFA2.采用C++语言，实现该算法3.编制测试程序4.调试程序三、实验环境计算机、Windows操作系统、VisualC++程序集成环境。四、程序代码#include"Thompson.h"voidmain(){ stringRegular_Expression="(a|b)*abb"; cellNFA_Cell; input(Regular_Expression);//调试需要先屏蔽 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复制到NewCell cell_EdgeSet_Copy(NewCell,Left); cell_EdgeSet_Copy(NewCell,Right); //将新构建的四条边参加EdgeSet NewCell.EdgeSet[NewCell.EdgeCount++]=Edge1; NewCell.EdgeSet[NewCell.EdgeCount++]=Edge2; NewCell.EdgeSet[NewCell.EdgeCount++]=Edge3; NewCell.EdgeSet[NewCell.EdgeCount++]=Edge4; //构建NewCell的启示状态和结束状态 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(); //构建边 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='#'; //构建单元 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;//转换成大写字母 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个字符，故不能连续判断 { } 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的边数："<<Cell.EdgeCount<<endl; cout<<"NFA的起始状态："<<Cell.StartState.StateName<<endl; cout<<"NFA的结束状态："<<Cell.EndState.StateName<<endl; for(inti=0;i<Cell.EdgeCount;i++) { <<"转换符："<<Cell.EdgeSet[i].TransSymbol<<endl; } cout<<"结束"<<endl;}算法分析Thompson算法的根本思想,提出一种利用算符优先关系表来实现Thompson算法的方法,以实现正规式到有穷自动机的转换.描述了算法的解决思路、算符优先表的生成和NFA的表示.算法测试说明,该方法可以大大简化算法的实现,提高编译程序的工作效率.六、实验结果实验小结通过这次试验，我掌握了如何将正规表达式转换为NFA的方法和过程。另外，我们要知道在构造过程中，每次构造的新状态都要赋予不同的名字。这样，任何NFA的两个状态都具有不同的名字。即使同一符号在r中出现屡次，我们也要为该符号的每个实例创立一个独立的带有自己状态的NFA。实验三词法分析与语法分析程序设计一、实验目的掌握计算机语言的词法分析程序和语法分析程序的设计方法二、实验要求、内容及步骤实验要求：1．根据以下的正规式，画出状态图；标识符：<字母>(<字母>|<数字字符>)*十进制整数：0|〔1|2|3|4|5|6|7|8|9〕〔0|1|2|3|4|5|6|7|8|9〕*运算符：+*2．根据状态图，设计词法分析函数intscan()，实现从键盘读入数据，分析出一个单词。3．对于只含有+、*运算的算术表达式的文法，编写相应的语法分析程序，要求用LL(1)分析表实现，并以id+id*id为例进行测试。E—＞TE′E′—＞+TE′|εT—＞FT′T′—＞*FT′|εF—＞〔E〕|id实验步骤1、根据状态图，设计词法分析算法2、采用C++语言，实现该算法3、编制测试程序4、调试程序：输入一组单词，检查输出结果。5、编制给定文法的非递归的预测分析程序，并加以测试。三、实验环境计算机、Windows操作系统、VisualC++程序集成环境。实验原理1.词法分析器读入输入串，将其转换成将被语法分析器分析的词法单元序列。产生下述小语言的单词序列。单词符号种别编码DIMIFDOSTOPEND

标识符常数〔整〕=+***，〔〕1234567891011121314这个小语言的单词符号的状态转换图，如下列图：2.语法分析是决定如何使用一个文法生成一个终结符串的过程。语法分析器能识别由加+减-乘*除/乘方^括号〔〕操作数所组成的算术表达式，其文法如下：E→E+T|E-T|TT→T*F|T/F|FF→P^F|Pp→(E)|i使用的算法可以是：预测分析法；递归下降分析法；算符优先分析法；LR分析法等。3.中间代码生成器产生上述算术表达式的中间代码〔四元式序列〕。id+*()$EE—＞TE′E—＞TE′E′E′—＞+TE′E′—＞εE′—＞εTT—＞FT′T—＞FT′T′T′—＞εT′—＞*FT′T′—＞εT′—＞εFF—＞idF—＞(E)五、程序代码〔1〕词法分析程序的数据结构与算法：#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<<"请输入一段程序〔以#结束〕:"; do { cin.get(ch); prog[p++]=ch; } while(ch!='#'); p=0; cout<<endl<<"词法分析结果如下"<<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〕语法分析程序的数据结构与算法：#include<string.h>#include<malloc.h>#include<iostream>usingnamespacestd;typedefstructtable//分析表存储结构{charm[100];}table;tableM[100][100];//定义分析表typedefstructstacknode//定义栈内元素节点(带头结点〔为空〕的){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)//打印现实显示栈内元素{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[])//查找函数，{inti;intflag=0;for(i=0;i<100;i++){if(c==array[i])flag=1;}returnflag;}intlocation(charc,chararray[])//定位函数,指出字符所在位置{inti;for(i=0;i<100;i++){if(c==array[i])returni;}}voiderror()//出错函数定义{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所用产生式\n",'','','');opt1:printf("%-16d",h);//显示步骤h++;display(st);//显示分析栈中内容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