实验预测分析.doc

实验四 语法分析(一预测分析技术实验目的：对给定的文法及其预测分析表，对输入的符号串进行识别，并给出符号串的识别过程，包括各步骤的栈内容，输入和输出。实验要求：首先应该详细掌握预测分析技术的原理，方法详细的分析步骤。其次要了解数据结构中栈部分的内容，包括栈的特点及在预测分析中的使用情况，预测分析其实可以看成是对两个基本的栈的操作，因此，对栈的有关知识要求比较熟悉。在实验前可复习数据结构中栈的内容，这样可使本实验比较顺利的进行。b5E2RGbCAP下面以例说明最后所应实现的功能输入文法规则0:Z:=BA 1:A:=+BA 2:A:=3:B:=DC 4:C:=*DC 5:C:=6:D:=(Z 7:D:=i输入预测分析表!0:Z:=BA 1:A:=+BA 2:A:=3:B:=DC 4:C:=*DC 5:C:=6:D:=(Z 7:D:=i依次输入PTableZ,+ PTableZ,* PTableZ,( PTableZ, PTableZ,i PTableZ,#p1EanqFDPw对应的规则编号:-1 -1 0 -1 0 -1依次输入PTableA,+ PTableA,* PTableA,( PTableA, PTableA,i PTableA,#DXDiTa9E3d对应的规则编号:1 -1 -1 2 -1 2依次输入PTableB,+ PTableB,* PTableB,( PTableB, PTableB,i PTableB,#RTCrpUDGiT对应的规则编号:-1 -1 3 -1 3 -1依次输入PTableC,+ PTableC,* PTableC,( PTableC, PTableC,i PTableC,#5PCzVD7HxA对应的规则编号:5 4 -1 5 -1 5依次输入PTableD,+ PTableD,* PTableD,( PTableD, PTableD,i PTableD,#jLBHrnAILg对应的规则编号:-1 -1 6 -1 7 -1 + * ( i # Z Z:=BA Z:=BA A A:=+BA A:= A:= B B:=DC B:=DC C C:= C:=*DC C:= C:= D D:=(Z D:=i请输入要识别的符号串:i+i*i步骤 栈 输入 输出0 #Z i+i*i# Z:=BA1 #AB i+i*i# B:=DC2 #ACD i+i*i# D:=i3 #ACi i+i*i#4 #AC +i*i# C:=5 #A +i*i# A:=+BA6 #AB+ +i*i#7 #AB i*i# B:=DC8 #ACD i*i# D:=i9 #ACi i*i#10 #AC *i# C:=*DC11 #ACD* *i#12 #ACD i# D:=i13 #ACi i#14 #AC # C:=15 #A # A:=16 # # Success!该符号串是该文法的句子!输入要识别的符号串:ii步骤 栈 输入 输出0 #Z ii# Z:=BA1 #AB ii# B:=DC2 #ACD ii# D:=i3 #ACi ii#4 #AC i# Failure!该符号串不是该文法的句子!参考程序#include#include#include#includestruct Regularity /存放文法规则的数组结构xHAQX74J0Xchar regular20。class Stack /定义一个栈类 public: Stack(int=10。 Stack( deleteelements。 void Push(const char& item。 char Pop(。 char GetTop(。 void MakeEmpty(top=-1。 int IsEmpty( const return top=-1。 int IsFull( const return top=maxSize-1。 void display(。 private: int top。 char* elements。 int maxSize。Stack:Stack(int s:top(-1,maxSize(selements=new charmaxSize。assert(elements!=0。void Stack:Push(const char& itemassert(!IsFull(。elements+top=item。char Stack:Pop(assert(!IsEmpty(。return elementstop-。char Stack:GetTop(assert(!IsEmpty(。return elementstop。void Stack:display(elementstop+1=0。cout Zzz6ZB2Ltkint i,j,size=0。for(i=0。i for(j=0。j if(VNj=Arrayi.regular0 break。 if(j=size VNsize=Arrayi.regular0。 size+。 VNsize=0。 void FindVT(char VT,Regularity Array,int length dvzfvkwMI1int i,j,k,m,size=0。for(i=0。i for(j=4。j。j+ for(k=0。k if(Arrayk.regular0=Arrayi.regularj break。rqyn14ZNXI if(k=length&Arrayi.regularj!= for(m=0。m if(VTm=Arrayi.regularj break。if(m=size VTsize=Arrayi.regularj。 size+。 VTsize=0。 VTsize=#。VTsize+1=0。int FindRegularity(int PTable20,char VN,char VT,char temp1,char temp2EmxvxOtOcoint i,j。int size1=strlen(VN。int size2=strlen(VT。for(i=0。iif(VNi=temp1 break。for(j=0。jif(VTj=temp2 break。return PTableij。int CheckVT(char VT,char temp int i。int size=strlen(VT。 for(i=0。iif(VTi=temp return 1。return 0。void Display(Regularity Array,int length cout。 int i。 for(i=0。i couti:。 cout%3=0 coutendl。 coutint i,j。char temp20。int size=strlen(TD。for(i=index,j=0。itempj=TDi。tempj=0。cout SixE2yXPq5int i。coutlength。for(i=0。i cout请输入编号为iArrayi.regular。 FindVN(VN,Array,length。FindVT(VT,Array,length。void InputPredictTable(Regularity Array,int length,int PTable20,char VN,char VT6ewMyirQFL int i,j。int size1=strlen(VN。int size2=strlen(VT。cout请输入预测分析表!。for(i=0。icout依次输入。for(j=0。jcoutPTableVNi,VTj 。 cout对应的规则编号:。 for(j=0。j cinPTableij。void ShowRegularity(Regularity Array,int length Display(Array,length。void ShowPredictTable(Regularity Array,int PTable20,char VN,char VTkavU42VRUs int i,j。int size1=strlen(VN。int size2=strlen(VT。 cout。cout。cout 。for(i=0。icoutVTi。coutendl。for(i=0。icoutVNi。for(j=0。jif(PTableij=0coutArrayPTableij.regular。elsecout 。couty6v3ALoS89int i,index=0,count=0。char TD20。stack.MakeEmpty(。stack.Push(#。stack.Push(Array0.regular0。Display(Array,length。coutTD。i=strlen(TD。TDi=#。TDi+1=0。cout。cout步骤。cout 。 cout栈。cout。 cout。cout输入。cout。 cout。cout 。cout输出 coutcount。 cout 。 cout。 stack.display(。 cout。 cout。 cout。 DisplayString(TD,index。 cout。 cout。 if(stack.GetTop(=#&TDindex=# cout 。 coutSuccess!。 coutendl。 cout该符号串是该文法的句子! if(stack.GetTop(!=TDindex cout 。 coutFailure!。 coutendl。 cout该符号串不是该文法的句子!。 index+。 cout,TDindex。M2ub6vSTnP if(i=-1 cout 。 coutFailure!。 coutendl。 cout该符号串不是该文法的句子!endl。 break。 else cout 。 cout。 if(Arrayi.regular4!= for(int j=strlen(Arrayi.regular-1。j=4。j- stack.Push(Arrayi.regularj。 count+。 coutRegularity Array20。 /定义数组存放文法规则eUts8ZQVRd char VN20。 /定义数组存放非终结符号sQsAEJkW5Tchar VT20。 /定义数组存放终结符号GMsIasNXkA int PTable2020。 /定义二维数组存放预测分析表TIrRGchYzgint length=0。Stack stack(20。 /创建栈用于识别符号串7EqZcWLZNXint sel。 int sign1=0,sign2=0。aaa: /显示用户界面lzq7IGf02Ecout1endl。cout2endl。cout3endl。cout4endl。 cout5endl。cout6sel。while(sel!=1&sel!=2&sel!=3&sel!=4&sel!=5&sel!=6。zvpgeqJ1hk switch(sel case 1: /输入文法规则NrpoJac3v1 sign1=1。 InputRegularity(Array,length,VN,VT。 break。 case 2: /输入预测分析表1nowfTG4KI if(sign1=0 cout请先输入文法规则!。 break。 case 3: /查看文法规则fjnFLDa5Zo if(sign1=0 cout请先输入文法规则! cout