一.前言

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

二.內(nèi)容

1.問題描述
預(yù)測分析屬于自上而下不帶回溯的語法分析方法，這種分析方法要求文法是LL(1)的，語法分析程序的輸入是終結(jié)符號串（即單詞符號串，一一個“#”結(jié)尾），如果輸入串是句子，則輸出YES，否則輸出NO和錯誤信息。
以算術(shù)表達式的文法為例來進行LL（1）分析程序的設(shè)計。
（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.問題實現(xiàn)的算法
預(yù)測分析算法 實現(xiàn)預(yù)測分析算法需要使用一個分析棧stack存放文法符號。變量top為stack的棧頂指針，變量a存放當(dāng)前輸入符號。LL（1）分析表為整型二維數(shù)組M[m][n].
x為棧頂符號
分析算法思想：
①若x=a=’#’,則分析成功，分析器停止工作。
②若x=a≠’#’，即棧頂符號x與當(dāng)前掃描的輸入符號a匹配；則將x從棧頂彈出,輸入指針指向下一個輸入符號，繼續(xù)對下一個字符進行分析。
③若x為一非終結(jié)符號A,則查M[A,a]:
1.若M[A,a]中為一個A的產(chǎn)生式，則將A自棧頂彈出，并將M[A,a]中的產(chǎn)生式右部符號串按逆序逐一入棧；如果M[A,a]中的產(chǎn)生式為A->ε，則只將A自棧頂彈出。
2.若M[A，a]中為空，則發(fā)現(xiàn)語法錯誤，調(diào)用出錯處理程序進行處理。
控制程序描述如下：
將“#“和文法開始符號依次壓入棧中；
把第一個輸入符號讀入a；
do{
把棧頂符號彈出并放入x中；
if(x∈VT)
{
if(x==a)
{
if(a!=’#’) 將下一個輸入符號讀入a；
}
else error();
}
else
if(M[x，a]=”x→Y1Y2…Yk”)
{
按逆序依次把Yk,Yk-1…Y1壓入棧中，
輸出”x→Y1Y2…Yk”；
}
else error();
}while (x!=”#”)

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

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

4.整個程序的流程圖

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

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

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

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

void display()//顯示主界面

void print_match()//匹配情況

void error()//錯誤情況

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

int seek_ter()//找到當(dāng)前終結(jié)符號對應(yīng)的下標(biāo) 返回值當(dāng)前終結(jié)符號對應(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é)符號 從0開始 char ter_sign[10]={'i','+','*','(',')','#'};//存放終結(jié)符號 從0開始 string form[10];//存放產(chǎn)生式 從0開始 int M[5][6];//LL(1)分析表 從0開始 char stack[max];//分析棧(符號棧) 從1開始 char x;//棧頂符號 int top=0;//棧頂指針 char a;//當(dāng)前輸入的符號 string ex;//輸入串 從0開始 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ù)表達式的產(chǎn)生式的初始化init_table();//LL(1)分析表的初始化suanshu_table();//賦值成算術(shù)表達式的LL(1)分析表display();//顯示主界面 //將#和文法開始符依次壓入棧中top++;stack[top]='#';top++;stack[top]='E';a=ex[j];//把第一個輸入符號讀入acout<<endl;cout<<"符號棧";cout<<'\t';cout<<"當(dāng)前輸入符號";cout<<'\t';cout<<"輸入串"; cout<<'\t';cout<<"說明"<<endl; do{x=stack[top];//把棧頂符號彈出并放入x中 print_tip(x);//輸出信息，彈出棧頂元素，，top--;if(x<'A'||x>'Z'){//棧頂符號是終結(jié)符號 if(x==a){//匹配 if(a!='#'){j++;a=ex[j];//將下一個輸入符號讀入a print_match();//匹配情況cout<<a<<endl;}else{//x=a='#'的情況 cout<<",匹配";} // cout<<",匹配";}else{error();//錯誤情況 exit(0);} }else{//棧頂符號是非終結(jié)符號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++){//符號棧 // cout<<stack[i]; // } // cout<<'\t'; // cout<<'\t'; // cout<<a;//當(dāng)前輸入符號 // cout<<'\t'; // for(i=j+1;i<=ex.size();i++){//輸入串 // cout<<ex[i]; // } // cout<<'\t';cout<<",分析成功，YES,accept!";} return 0; }void init_form(){//算術(shù)表達式的產(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ù)表達式的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ù)表達式的文法為:"<<endl;for(i=0;i<8;i++){cout<<'\t'<<form[i]<<endl;}cout<<"****************************************************"<<endl;cout<<"請輸入一個算術(shù)表達式串（以#結(jié)束）：（串只能以i,+,*,(,)構(gòu)成）"<<endl;cin>>ex;ex[ex.size()]='#';//用戶忘記輸入#,系統(tǒng)自動加上 }void print_match(){//匹配情況 // cout<<'\t'; // for(i=1;i<=top;i++){//符號棧 // cout<<stack[i]; // } // cout<<'\t'; // cout<<'\t'; // cout<<a;//當(dāng)前輸入符號 // cout<<'\t'; // for(i=j+1;i<=ex.size();i++){//輸入串 // cout<<ex[i]; // } // cout<<'\t'; //說明 cout<<",匹配";cout<<",讀出輸入串的下一個輸入符號"; }void error(){//錯誤情況 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,輸入的符號不正確!!"<<endl; } int seek_non(){//找到當(dāng)前非終結(jié)符號對應(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é)符號對應(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++){//符號棧 cout<<stack[i];} cout<<'\t';cout<<'\t';cout<<a;//當(dāng)前輸入符號 cout<<'\t';for(i=j+1;i<=ex.size();i++){//輸入串 cout<<ex[i];}cout<<'\t';cout<<"彈出棧頂符號"<<t; }

總結(jié)

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

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