實(shí)驗(yàn)二--LL(1)分析法實(shí)驗(yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)二 LL(1)分析法一、 實(shí)驗(yàn)?zāi)康?通過完成預(yù)測分析法的語法分析程序，了解預(yù)測分析法和遞歸子程序法的區(qū)別和聯(lián)系。使學(xué)生了解語法分析的功能，掌握語法分析程序設(shè)計(jì)的原理和構(gòu)造方法，訓(xùn)練學(xué)生掌握開發(fā)應(yīng)用程序的基本方法。有利于提高學(xué)生的專業(yè)素質(zhì)，為培養(yǎng)適應(yīng)社會(huì)多方面需要的能力。二、實(shí)驗(yàn)內(nèi)容及設(shè)計(jì)原理 所謂LL（1）分析法，就是指從左到右掃描輸入串（源程序），同時(shí)采用最左推導(dǎo)，且對每次直接推導(dǎo)只需向前看一個(gè)輸入符號，便可確定當(dāng)前所應(yīng)當(dāng)選擇的規(guī)則。實(shí)現(xiàn)LL（1）分析的程序又稱為LL（1）分析程序或LL1（1）分析器。我們知道一個(gè)文法要能進(jìn)行LL（1）分析，那么這個(gè)文法應(yīng)該滿足

2、：無二義性，無左遞歸，無左公因子。當(dāng)文法滿足條件后，再分別構(gòu)造文法每個(gè)非終結(jié)符的FIRST和FOLLOW集合，然后根據(jù)FIRST和FOLLOW集合構(gòu)造LL（1）分析表，最后利用分析表，根據(jù)LL(1)語法分析構(gòu)造一個(gè)分析器。LL（1）的語法分析程序包含了三個(gè)部分，總控程序，預(yù)測分析表函數(shù)，先進(jìn)先出的語法分析棧，本程序也是采用了同樣的方法進(jìn)行語法分析，該程序是采用了C+語言來編寫，其邏輯結(jié)構(gòu)圖如下：LL（1）預(yù)測分析程序的總控程序在任何時(shí)候都是按STACK棧頂符號X和當(dāng)前的輸入符號a做哪種過程的。對于任何（X，a），總控程序每次都執(zhí)行下述三種可能的動(dòng)作之一：（）若X = a =#，則宣布分析成功，

3、停止分析過程。（）若X = a #，則把X從STACK棧頂彈出，讓a指向下一個(gè)輸入符號。（）若X是一個(gè)非終結(jié)符，則查看預(yù)測分析表M。若MA，a中存放著關(guān)于X的一個(gè)產(chǎn)生式，那么，首先把X彈出STACK棧頂，然后，把產(chǎn)生式的右部符號串按反序一一彈出STACK棧（若右部符號為，則不推什么東西進(jìn)STACK棧）。若MA，a中存放著“出錯(cuò)標(biāo)志”，則調(diào)用出錯(cuò)診斷程序ERROR。三、程序結(jié)構(gòu)描述1、定義的變量初始化預(yù)測分析表：LL E8="TG","TG","error","error","error",&qu

4、ot;error","error","error"LL G8="error","error","null","+TG","-TG","error","error","null"LL T8="FS","FS","error","error","error","error"

5、,"error","error"LL S8="error","error","null","null","null","*FS","/FS","null"LL F8="i","(i)","error","error","error","error","error&quo

6、t;,"error"const int MaxLen=10; 初始化棧的長度const int Length=10; 初始化數(shù)組長度char Vn5='E','G','T','S','F' 非終結(jié)符數(shù)組char Vt8='i','(',')','+','-','*','/','#' 終結(jié)符數(shù)組char ch,X; /全局變量，ch用于讀當(dāng)前字符，X用于獲取棧頂元素cha

7、r strTokenLength; 存儲(chǔ)規(guī)約表達(dá)式2、定義的函數(shù)class stack 棧的構(gòu)造及初始化int length(char *c) 輸出字符數(shù)組的長度void print(int i,char*c) 剩余輸入串的輸出void run() 分析程序3、LL(1)預(yù)測分析程序流程圖四、程序源代碼及運(yùn)行結(jié)果#include<iostream>using namespace std;const int MaxLen=10; /初始化棧的長度 const int Length=10;/初始化數(shù)組長度 char Vn5='E','G','T&

8、#39;,'S','F'/非終結(jié)符數(shù)組 char Vt8='i','(',')','+','-','*','/','#'/終結(jié)符數(shù)組 char ch,X;/全局變量，ch用于讀當(dāng)前字符，X用于獲取棧頂元素 char strTokenLength;/存儲(chǔ)規(guī)約表達(dá)式 struct LL/ll(1)分析表的構(gòu)造字初始化 char*c;LL E8="TG","TG","error",&

9、quot;error","error","error","error","error"LL G8="error","error","null","+TG","-TG","error","error","null"LL T8="FS","FS","error","error&quo

10、t;,"error","error","error","error"LL S8="error","error","null","null","null","*FS","/FS","null"LL F8="i","(i)","error","error","error&q

11、uot;,"error","error","error"class stack/棧的構(gòu)造及初始化 public: stack();/初始化 bool empty() const;/是否為空 bool full() const;/是否已滿 bool get_top(char &c)const;/取棧頂元素 bool push(const char c);/入棧 bool pop();/刪除棧頂元素 void out();/輸出棧中元素 stack()/析構(gòu) private: int count;/棧長度 char dataMax

12、Len;/棧中元素 ;stack:stack() count=0;bool stack:empty() const if(count=0) return true; return false;bool stack:full() const if(count=MaxLen) return true; return false;bool stack:get_top(char &c)const if(empty() return false; else c=datacount-1; return true; bool stack:push(const char c) if(full() re

13、turn false; datacount+=c; return true;bool stack:pop() if(empty() return false; count-; return true;void stack:out() for(int i=0;i<count;i+) cout<<datai; cout<<" "int length(char *c) int l=0; for(int i=0;ci!='0'i+) l+; return l;void print(int i,char*c)/剩余輸入串的輸出 for(i

14、nt j=i;j<Length;j+) cout<<cj; cout<<" " void run() bool flag=true;/循環(huán)條件 int step=0,point=0;/步驟、指針 int len;/長度 cout<<"請輸入要規(guī)約的字符串："<<endl; cin>>strToken; ch=strTokenpoint+;/讀取第一個(gè)字符 stack s; s.push('#');/棧中數(shù)據(jù)初始化 s.push('E'); s.get_top

15、(X);/取棧頂元素 cout<<"步驟 "<<"分析棧 "<<"剩余輸入串 "<<"所用產(chǎn)生式 "<<"動(dòng)作"<<endl; cout<<step+<<" " s.out(); print(point-1,strToken); cout<<" "<<"初始化"<<endl; while(flag) if(

16、X=Vt0)|(X=Vt1)|(X=Vt2)|(X=Vt3)|(X=Vt4)|(X=Vt5)|(X=Vt6) /判斷是否為終結(jié)符（不包括#） if(X=ch)/終結(jié)符,識別，進(jìn)行下一字符規(guī)約 s.pop(); s.get_top(X); ch=strTokenpoint+; cout<<step+<<" " s.out(); print(point-1,strToken); cout<<" "<<"GETNEXT(I)"<<endl; else flag=false; cou

17、t<<"error!"<<endl; else if(X='#')/規(guī)約結(jié)束 if(X=ch) cout<<step+<<" " s.out(); print(point-1,strToken); cout<<" "<<X<<"->"<<ch<<" "<<"結(jié)束"<<endl; s.pop(); flag=false; el

18、se flag=false; cout<<"error!"<<endl; else if(X=Vn0) /非終結(jié)符E for(int i=0;i<8;i+)/查分析表 if(ch=Vti) if(strcmp(Ei.c,"error")=0)/出錯(cuò) flag=false; cout<<"error"<<endl; else /對形如 X->X1X2的產(chǎn)生式進(jìn)行入棧操作 s.pop(); len=length(Ei.c)-1; for(int j=len;j>=0;j-)

19、 s.push(Ei.cj); cout<<step+<<" " s.out(); print(point-1,strToken); cout<<X<<"->"<<Ei.c<<" "<<"POP,PUSH(" for(int z=len;z>=0;z-) cout<<Ei.cz; cout<<")"<<endl; s.get_top(X); else if(X=Vn

20、1) /同上，處理 G for(int i=0;i<8;i+) if(ch=Vti) if(strcmp(Gi.c,"null")=0) s.pop(); cout<<step+<<" " s.out(); print(point-1,strToken); cout<<" "<<X<<"->"<<""<<" "<<"POP"<<endl;

21、 s.get_top(X); else if(strcmp(Gi.c,"error")=0) flag=false; cout<<"error"<<endl; else s.pop(); len=length(Gi.c)-1; for(int j=len;j>=0;j-) s.push(Gi.cj); cout<<step+<<" " s.out(); print(point-1,strToken); cout<<X<<"->"&l

22、t;<Gi.c<<" "<<"POP,PUSH(" for(int z=len;z>=0;z-) cout<<Gi.cz; cout<<")"<<endl; s.get_top(X); else if(X=Vn2) /同上 處理 T for(int i=0;i<8;i+) if(ch=Vti) if(strcmp(Ti.c,"error")=0) flag=false; cout<<"error"<&

23、lt;endl; else s.pop(); len=length(Ti.c)-1; for(int j=len;j>=0;j-) s.push(Ti.cj); cout<<step+<<" " s.out(); print(point-1,strToken); cout<<X<<"->"<<Ti.c<<" "<<"POP,PUSH(" for(int z=len;z>=0;z-) cout<<Ti.c

24、z; cout<<")"<<endl; s.get_top(X); else if(X=Vn3)/同上 處理 S for(int i=0;i<8;i+) if(ch=Vti) if(strcmp(Si.c,"null")=0) s.pop(); cout<<step+<<" " s.out(); print(point-1,strToken); cout<<" "<<X<<"->"<<&q

25、uot;"<<" "<<"POP"<<endl; s.get_top(X); else if(strcmp(Si.c,"error")=0) flag=false; cout<<"error"<<endl; else s.pop(); len=length(Si.c)-1; for(int j=len;j>=0;j-) s.push(Si.cj); cout<<step+<<" " s.out(); print(point-1,strToken); cout<<X<<"->"<<Si.c<<" "<<"POP,PUSH(" for(int z=len;z>=0;z