實驗二-LL(1)分析法實驗報告

實驗二LL(1)分析法實驗?zāi)康耐ㄟ^完成預(yù)測分析法的語法分析程序，了解預(yù)測分析法和遞歸子程序法的區(qū)別和聯(lián)系。使學(xué)生了解語法分析的功能，掌握語法分析程序設(shè)計的原理和構(gòu)造方法，訓(xùn)練學(xué)生掌握開發(fā)應(yīng)用程序的根本方法。有利于提高學(xué)生的專業(yè)素質(zhì)，為培養(yǎng)適應(yīng)社會多方面需要的能力。二、實驗內(nèi)容及設(shè)計原理所謂LL〔1〕分析法，就是指從左到右掃描輸入串〔源程序〕，同時采用最左推導(dǎo)，且對每次直接推導(dǎo)只需向前看一個輸入符號，便可確定當(dāng)前所應(yīng)中選擇的規(guī)那么。實現(xiàn)LL〔1〕分析的程序又稱為LL〔1〕分析程序或LL1〔1〕分析器。我們知道一個文法要能進行LL〔1〕分析，那么這個文法應(yīng)該滿足：無二義性，無左遞歸，無左公因子。當(dāng)文法滿足條件后，再分別構(gòu)造文法每個非終結(jié)符的FIRST和FOLLOW集合，然后根據(jù)FIRST和FOLLOW集合構(gòu)造LL〔1〕分析表，最后利用分析表，根據(jù)LL(1)語法分析構(gòu)造一個分析器。LL〔1〕的語法分析程序包含了三個局部，總控程序，預(yù)測分析表函數(shù)，先進先出的語法分析棧，本程序也是采用了同樣的方法進行語法分析，該程序是采用了C++語言來編寫，其邏輯結(jié)構(gòu)圖如下：LL〔1〕預(yù)測分析程序的總控程序在任何時候都是按STACK棧頂符號X和當(dāng)前的輸入符號a做哪種過程的。對于任何〔X，a〕，總控程序每次都執(zhí)行下述三種可能的動作之一：〔１〕假設(shè)X=a=‘#’，那么宣布分析成功，停止分析過程?！玻病臣僭O(shè)X=a‘#’，那么把X從STACK棧頂彈出，讓a指向下一個輸入符號。〔３〕假設(shè)X是一個非終結(jié)符，那么查看預(yù)測分析表M。假設(shè)M[A，a]中存放著關(guān)于X的一個產(chǎn)生式，那么，首先把X彈出STACK棧頂，然后，把產(chǎn)生式的右部符號串按反序一一彈出STACK棧〔假設(shè)右部符號為ε，那么不推什么東西進STACK?！?。假設(shè)M[A，a]中存放著“出錯標(biāo)志〞，那么調(diào)用出錯診斷程序ERROR。三、程序結(jié)構(gòu)描述1、定義的變量初始化預(yù)測分析表：LLE[8]={"TG","TG","error","error","error","error","error","error"};LLG[8]={"error","error","null","+TG","-TG","error","error","null"};LLT[8]={"FS","FS","error","error","error","error","error","error"};LLS[8]={"error","error","null","null","null","*FS","/FS","null"};LLF[8]={"i","(i)","error","error","error","error","error","error"};constintMaxLen=10;初始化棧的長度constintLength=10;初始化數(shù)組長度charVn[5]={'E','G','T','S','F'};非終結(jié)符數(shù)組charVt[8]={'i','(',')','+','-','*','/','#'};終結(jié)符數(shù)組charch,X;/全局變量，ch用于讀當(dāng)前字符，X用于獲取棧頂元素charstrToken[Length];存儲規(guī)約表達(dá)式2、定義的函數(shù)classstack棧的構(gòu)造及初始化intlength(char*c)輸出字符數(shù)組的長度voidprint(inti,char*c)剩余輸入串的輸出voidrun()分析程序3、LL(1)預(yù)測分析程序流程圖四、程序源代碼及運行結(jié)果#include<iostream>usingnamespacestd;constintMaxLen=10;//初始化棧的長度constintLength=10;//初始化數(shù)組長度charVn[5]={'E','G','T','S','F'};//非終結(jié)符數(shù)組charVt[8]={'i','(',')','+','-','*','/','#'};//終結(jié)符數(shù)組charch,X;//全局變量，ch用于讀當(dāng)前字符，X用于獲取棧頂元素charstrToken[Length];//存儲規(guī)約表達(dá)式structLL//ll(1)分析表的構(gòu)造字初始化{char*c;};LLE[8]={"TG","TG","error","error","error","error","error","error"};LLG[8]={"error","error","null","+TG","-TG","error","error","null"};LLT[8]={"FS","FS","error","error","error","error","error","error"};LLS[8]={"error","error","null","null","null","*FS","/FS","null"};LLF[8]={"i","(i)","error","error","error","error","error","error"};classstack//棧的構(gòu)造及初始化{public:stack();//初始化boolempty()const;//是否為空boolfull()const;//是否已滿boolget_top(char&c)const;//取棧頂元素boolpush(constcharc);//入棧boolpop();//刪除棧頂元素voidout();//輸出棧中元素~stack(){}//析構(gòu)private:intcount;//棧長度chardata[MaxLen];//棧中元素};stack::stack(){count=0;}boolstack::empty()const{if(count==0)returntrue;returnfalse;}boolstack::full()const{if(count==MaxLen)returntrue;returnfalse;}boolstack::get_top(char&c)const{if(empty())returnfalse;else{c=data[count-1];returntrue;}}boolstack::push(constcharc){if(full())returnfalse;data[count++]=c;returntrue;}boolstack::pop(){if(empty())returnfalse;count--;returntrue;}voidstack::out(){for(inti=0;i<count;i++)cout<<data[i];cout<<"";}intlength(char*c){intl=0;for(inti=0;c[i]!='\0';i++)l++;returnl;}voidprint(inti,char*c)//剩余輸入串的輸出{for(intj=i;j<Length;j++)cout<<c[j];cout<<"";}voidrun(){boolflag=true;//循環(huán)條件intstep=0,point=0;//步驟、指針intlen;//長度cout<<"請輸入要規(guī)約的字符串："<<endl;cin>>strToken;ch=strToken[point++];//讀取第一個字符stacks;s.push('#');//棧中數(shù)據(jù)初始化s.push('E');s.get_top(X);//取棧頂元素cout<<"步驟"<<"分析棧"<<"剩余輸入串"<<"所用產(chǎn)生式"<<"動作"<<endl;cout<<step++<<"";s.out();print(point-1,strToken);cout<<""<<"初始化"<<endl;while(flag){if((X==Vt[0])||(X==Vt[1])||(X==Vt[2])||(X==Vt[3])||(X==Vt[4])||(X==Vt[5])||(X==Vt[6]))//判斷是否為終結(jié)符〔不包括#〕{if(X==ch)//終結(jié)符,識別，進行下一字符規(guī)約{s.pop();s.get_top(X);ch=strToken[point++];cout<<step++<<"";s.out();print(point-1,strToken);cout<<""<<"GETNEXT(I)"<<endl;}else{flag=false;cout<<"error!"<<endl;}}elseif(X=='#')//規(guī)約結(jié)束{if(X==ch){cout<<step++<<"";s.out();print(point-1,strToken);cout<<""<<X<<"->"<<ch<<""<<"結(jié)束"<<endl;s.pop();flag=false;}else{flag=false;cout<<"error!"<<endl;}}elseif(X==Vn[0])//非終結(jié)符E{for(inti=0;i<8;i++)//查分析表if(ch==Vt[i]){if(strcmp(E[i].c,"error")==0)//出錯{flag=false;cout<<"error"<<endl;}else{//對形如X->X1X2的產(chǎn)生式進行入棧操作s.pop();len=length(E[i].c)-1;for(intj=len;j>=0;j--)s.push(E[i].c[j]);cout<<step++<<"";s.out();print(point-1,strToken);cout<<X<<"->"<<E[i].c<<""<<"POP,PUSH(";for(intz=len;z>=0;z--)cout<<E[i].c[z];cout<<")"<<endl;s.get_top(X);}}}elseif(X==Vn[1])//同上，處理G{for(inti=0;i<8;i++)if(ch==Vt[i]){if(strcmp(G[i].c,"null")==0){s.pop();cout<<step++<<"";s.out();print(point-1,strToken);cout<<""<<X<<"->"<<"ε"<<""<<"POP"<<endl;s.get_top(X);}elseif(strcmp(G[i].c,"error")==0){flag=false;cout<<"error"<<endl;}else{s.pop();len=length(G[i].c)-1;for(intj=len;j>=0;j--)s.push(G[i].c[j]);cout<<step++<<"";s.out();print(point-1,strToken);cout<<X<<"->"<<G[i].c<<""<<"POP,PUSH(";for(intz=len;z>=0;z--)cout<<G[i].c[z];cout<<")"<<endl;s.get_top(X);}}}elseif(X==Vn[2])//同上處理T{for(inti=0;i<8;i++)if(ch==Vt[i]){if(strcmp(T[i].c,"error")==0){flag=false;cout<<"error"<<endl;}else{s.pop();len=length(T[i].c)-1;for(intj=len;j>=0;j--)s.push(T[i].c[j]);cout<<step++<<"";s.out();print(point-1,strToken);cout<<X<<"->"<<T[i].c<<""<<"POP,PUSH(";for(intz=len;z>=0;z--)cout<<T[i].c[z];cout<<")"<<endl;s.get_top(X);}}}elseif(X==Vn[3])//同上處理S{for(inti=0;i<8;i++)if(ch==Vt[i]){if(strcmp(S[i].c,"null")==0){s.pop();cout<<step++<<"";s.out();print(point-1,strToken);cout<<""<<X<<"->"<<"ε"<<""<<"POP"<<endl;s.get_top(X);}elseif(strcmp(S[i].c,"error")==0){flag=false;cout<<"error"<<endl;}else{s.pop();len=length(S[i].c)-1;for(intj=len;j>=0;j--)s.push(S[i].c[j]);cout<<step++<<"";s.out();print(point-1,strToken);cout<<X<<"->"<<S[i].c<<""<<"POP,PUSH(";for(intz=len;z>=0;z--)cout<<S[i].c[z];cout<<")"<<endl;s.get_top(X);}}}elseif(X=