一.前言

作為當(dāng)代大學(xué)生的我，我喜極而泣，最后一個(gè)編譯原理實(shí)驗(yàn)報(bào)告了，這次是一個(gè)提高性實(shí)驗(yàn)報(bào)告。肝完這個(gè)，編譯原理，這門(mén)課，再也沒(méi)有實(shí)驗(yàn)報(bào)告了，我再也不要擔(dān)心我沒(méi)有頭發(fā)了。行了，廢話不多說(shuō)，我直接呈現(xiàn)內(nèi)容吧。實(shí)驗(yàn)心得這類(lèi)的什么東西，還是留一點(diǎn)小小的隱私吧。直接肝！！

二.內(nèi)容

1.問(wèn)題描述
預(yù)測(cè)分析屬于自上而下不帶回溯的語(yǔ)法分析方法，這種分析方法要求文法是LL(1)的，語(yǔ)法分析程序的輸入是終結(jié)符號(hào)串（即單詞符號(hào)串，一一個(gè)“#”結(jié)尾），如果輸入串是句子，則輸出YES，否則輸出NO和錯(cuò)誤信息。
以算術(shù)表達(dá)式的文法為例來(lái)進(jìn)行LL（1）分析程序的設(shè)計(jì)。
（1）文法： 設(shè)LL（1）文法G為：
E→TE’
E’→+TE’|ε
T→FT’
T’→*FT’|ε
F→（E）|i
注：i為整型常數(shù)或者為標(biāo)示符表示的整型變量。
（2）分析表 設(shè)LL（1）分析表M如下表所示。

2.問(wèn)題實(shí)現(xiàn)的算法
預(yù)測(cè)分析算法 實(shí)現(xiàn)預(yù)測(cè)分析算法需要使用一個(gè)分析棧stack存放文法符號(hào)。變量top為stack的棧頂指針，變量a存放當(dāng)前輸入符號(hào)。LL（1）分析表為整型二維數(shù)組M[m][n].
x為棧頂符號(hào)
分析算法思想：
①若x=a=’#’,則分析成功，分析器停止工作。
②若x=a≠’#’，即棧頂符號(hào)x與當(dāng)前掃描的輸入符號(hào)a匹配；則將x從棧頂彈出,輸入指針指向下一個(gè)輸入符號(hào)，繼續(xù)對(duì)下一個(gè)字符進(jìn)行分析。
③若x為一非終結(jié)符號(hào)A,則查M[A,a]:
1.若M[A,a]中為一個(gè)A的產(chǎn)生式，則將A自棧頂彈出，并將M[A,a]中的產(chǎn)生式右部符號(hào)串按逆序逐一入棧；如果M[A,a]中的產(chǎn)生式為A->ε，則只將A自棧頂彈出。
2.若M[A，a]中為空，則發(fā)現(xiàn)語(yǔ)法錯(cuò)誤，調(diào)用出錯(cuò)處理程序進(jìn)行處理。
控制程序描述如下：
將“#“和文法開(kāi)始符號(hào)依次壓入棧中；
把第一個(gè)輸入符號(hào)讀入a；
do{
把棧頂符號(hào)彈出并放入x中；
if(x∈VT)
{
if(x==a)
{
if(a!=’#’) 將下一個(gè)輸入符號(hào)讀入a；
}
else error();
}
else
if(M[x，a]=”x→Y1Y2…Yk”)
{
按逆序依次把Yk,Yk-1…Y1壓入棧中，
輸出”x→Y1Y2…Yk”；
}
else error();
}while (x!=”#”)

3.問(wèn)題選用的數(shù)據(jù)結(jié)構(gòu)

實(shí)現(xiàn)預(yù)測(cè)分析算法需要使用一個(gè)分析棧stack存放文法符號(hào)。變量top為stack的棧頂指針，變量a存放當(dāng)前輸入符號(hào)。LL（1）分析表為整型二維數(shù)組M[m][n].x為棧頂符號(hào)，ex存放輸入串，j為輸入串的指針。non_sign數(shù)組存放非終結(jié)符號(hào)，ter_sign數(shù)組存放終結(jié)符號(hào)，字符串?dāng)?shù)組form存放產(chǎn)生式。本程序采用c++語(yǔ)言來(lái)實(shí)現(xiàn)。
non_sign:char[]//存放非終結(jié)符號(hào)
ter_sign:char[]//存放終結(jié)符號(hào)
form:string[]//存放產(chǎn)生式
M:int[][]//分析表
stack:char[]//符號(hào)棧(分析棧)
a:char //當(dāng)前輸入符號(hào)
ex:string//輸入串
j:int //輸入串的指針

4.整個(gè)程序的流程圖

5.詳細(xì)設(shè)計(jì)（設(shè)計(jì)各個(gè)函數(shù)）
本程序?qū)⑷缦略O(shè)置為全局變量，故下函數(shù)均沒(méi)有形參（print_tip函數(shù)例外）
non_sign:char[]//存放非終結(jié)符號(hào)
ter_sign:char[]//存放終結(jié)符號(hào)
form:string[]//存放產(chǎn)生式
M:int[][]//分析表
stack:char[]//符號(hào)棧(分析棧)
a:char //當(dāng)前輸入符號(hào)
ex:string//輸入串
j:int //輸入串的指針

各個(gè)函數(shù)：
void init_form()//算術(shù)表達(dá)式的產(chǎn)生式的初始化 //@代替ε A代替E’ B代替T’

void init_table()//LL(1)分析表的初始化

void suanshu_table()//賦值成算術(shù)表達(dá)式的LL(1)分析表

void display()//顯示主界面

void print_match()//匹配情況

void error()//錯(cuò)誤情況

int seek_non()//找到當(dāng)前非終結(jié)符號(hào)對(duì)應(yīng)的下標(biāo) 返回值非終結(jié)符號(hào)對(duì)應(yīng)的下標(biāo)

int seek_ter()//找到當(dāng)前終結(jié)符號(hào)對(duì)應(yīng)的下標(biāo) 返回值當(dāng)前終結(jié)符號(hào)對(duì)應(yīng)的下標(biāo)

void print_tip(char t)//輸出信息，彈出棧頂元素，，
//輸入當(dāng)前棧頂元素

6.程序功能效果圖：

3.代碼

#include<iostream> #include<string> #include<string.h> #define max 100 #include<stdlib.h> using namespace std; int i;//循環(huán)變量 char non_sign[10]={'E','A','T','B','F'};//存放非終結(jié)符號(hào) 從0開(kāi)始 char ter_sign[10]={'i','+','*','(',')','#'};//存放終結(jié)符號(hào) 從0開(kāi)始 string form[10];//存放產(chǎn)生式 從0開(kāi)始 int M[5][6];//LL(1)分析表 從0開(kāi)始 char stack[max];//分析棧(符號(hào)棧) 從1開(kāi)始 char x;//棧頂符號(hào) int top=0;//棧頂指針 char a;//當(dāng)前輸入的符號(hào) string ex;//輸入串 從0開(kāi)始 int j=0;//輸入串指針 int main(){void init_form();void init_table();void suanshu_table();void display(); void print_match();int seek_non();int seek_ter();void error();void print_tip(char t);//輸出信息，彈出棧頂元素，，int flag;//分析表中的數(shù) init_form();//算術(shù)表達(dá)式的產(chǎn)生式的初始化init_table();//LL(1)分析表的初始化suanshu_table();//賦值成算術(shù)表達(dá)式的LL(1)分析表display();//顯示主界面 //將#和文法開(kāi)始符依次壓入棧中top++;stack[top]='#';top++;stack[top]='E';a=ex[j];//把第一個(gè)輸入符號(hào)讀入acout<<endl;cout<<"符號(hào)棧";cout<<'\t';cout<<"當(dāng)前輸入符號(hào)";cout<<'\t';cout<<"輸入串"; cout<<'\t';cout<<"說(shuō)明"<<endl; do{x=stack[top];//把棧頂符號(hào)彈出并放入x中 print_tip(x);//輸出信息，彈出棧頂元素，，top--;if(x<'A'||x>'Z'){//棧頂符號(hào)是終結(jié)符號(hào) if(x==a){//匹配 if(a!='#'){j++;a=ex[j];//將下一個(gè)輸入符號(hào)讀入a print_match();//匹配情況cout<<a<<endl;}else{//x=a='#'的情況 cout<<",匹配";} // cout<<",匹配";}else{error();//錯(cuò)誤情況 exit(0);} }else{//棧頂符號(hào)是非終結(jié)符號(hào)flag=M[seek_non()] [seek_ter()];if(flag!=-1){if(form[flag][3]=='@'){ // top--;cout<<"，因M["<<x<<","<<a<<"]中為"<<form[flag]<<",故不壓棧"<<endl;}else{for(i=form[flag].size()-1;i>=3;i--){//按逆序依次將產(chǎn)生式的候選式壓入棧 top++;stack[top]=form[flag][i];}cout<<",將M["<<x<<","<<a<<"]中為"<<form[flag]<<"的";for(i=3;i<form[flag].size();i++){cout<<form[flag][i];} cout<<"逆序壓棧"<<endl; }}else{error();exit(0);}} }while(x!='#');if(x==a){ // for(i=1;i<=top;i++){//符號(hào)棧 // cout<<stack[i]; // } // cout<<'\t'; // cout<<'\t'; // cout<<a;//當(dāng)前輸入符號(hào) // cout<<'\t'; // for(i=j+1;i<=ex.size();i++){//輸入串 // cout<<ex[i]; // } // cout<<'\t';cout<<",分析成功，YES,accept!";} return 0; }void init_form(){//算術(shù)表達(dá)式的產(chǎn)生式的初始化 //@代替ε A代替E' B代替T' form[0]="E->TA";form[1]="A->+TA";form[2]="A->@"; form[3]="T->FB";form[4]="B->*FB";form[5]="B->@";form[6]="F->(E)";form[7]="F->i"; }void init_table(){//LL(1)分析表的初始化 int i;//循環(huán)變量 int j; //循環(huán)變量for(i=0;i<5;i++){for(j=0;j<6;j++){M[i][j]=-1;}} }void suanshu_table(){//賦值成算術(shù)表達(dá)式的LL(1)分析表M[0][0]=0;M[0][3]=0;//E->TAM[1][1]=1; //A->+TAM[1][4]=2;M[1][5]=2;//A->@M[2][0]=3;M[2][3]=3;//T->FBM[3][1]=5;M[3][4]=5;M[3][5]=5;//B->@M[3][2]=4;//B->*FBM[4][0]=7;//F->iM[4][3]=6;//F->(E) }void display(){//顯示主界面 cout<<"***************@代替ε A代替E' B代替T'*****************"<<endl;cout<<"算術(shù)表達(dá)式的文法為:"<<endl;for(i=0;i<8;i++){cout<<'\t'<<form[i]<<endl;}cout<<"****************************************************"<<endl;cout<<"請(qǐng)輸入一個(gè)算術(shù)表達(dá)式串（以#結(jié)束）：（串只能以i,+,*,(,)構(gòu)成）"<<endl;cin>>ex;ex[ex.size()]='#';//用戶(hù)忘記輸入#,系統(tǒng)自動(dòng)加上 }void print_match(){//匹配情況 // cout<<'\t'; // for(i=1;i<=top;i++){//符號(hào)棧 // cout<<stack[i]; // } // cout<<'\t'; // cout<<'\t'; // cout<<a;//當(dāng)前輸入符號(hào) // cout<<'\t'; // for(i=j+1;i<=ex.size();i++){//輸入串 // cout<<ex[i]; // } // cout<<'\t'; //說(shuō)明 cout<<",匹配";cout<<",讀出輸入串的下一個(gè)輸入符號(hào)"; }void error(){//錯(cuò)誤情況 for(i=1;i<=top;i++){cout<<stack[i];} cout<<'\t';cout<<a;cout<<'\t';for(i=j+1;i<ex.size();i++){cout<<ex[i];}cout<<'\t';cout<<"NO,輸入的符號(hào)不正確!!"<<endl; } int seek_non(){//找到當(dāng)前非終結(jié)符號(hào)對(duì)應(yīng)的下標(biāo) for(i=0;i<strlen(non_sign);i++){if(x==non_sign[i]){break;}}return i; } int seek_ter(){//找到當(dāng)前終結(jié)符號(hào)對(duì)應(yīng)的下標(biāo) for(i=0;i<strlen(ter_sign);i++){if(a==ter_sign[i]){break;}}return i; } void print_tip(char t){//輸出信息，彈出棧頂元素，， for(i=1;i<=top;i++){//符號(hào)棧 cout<<stack[i];} cout<<'\t';cout<<'\t';cout<<a;//當(dāng)前輸入符號(hào) cout<<'\t';for(i=j+1;i<=ex.size();i++){//輸入串 cout<<ex[i];}cout<<'\t';cout<<"彈出棧頂符號(hào)"<<t; }

總結(jié)

以上是生活随笔為你收集整理的编译原理中LL（1）分析程序的设计---用c++程序语言实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。