python版本（詞法分析器整合預測分析表）：
編譯原理預測分析表一篇解決你所有問題（python版）
實驗 預測分析表方法
一、實驗目的
了解預測分析表方法的實作原理。
二、實驗内容
編寫一通用的預測法分析程式，要求有一定的錯誤處理能力，出錯後能夠使程式繼續運作下去，直到分析過程結束。可通過不同的文法（通過資料表現）進行測試。
三、實驗内容提示
1．算法資料構造：
構造終結符數組：char Vt[10][5]={“id”,”+”……}；
構造非終結符數組：char Vn[10]={ };
構造follow集數組：char *follow[10][10]={ } (可将follow集與預測分析表合并存放，可省略，直接給出分析表。)
資料構造示例（使用的預測分析表構造方法1）：
/*data1.h簡單算術表達式資料*/
char VN[10][5]={"E","E'","T","T'","F"}; //非終結符表
int length_vn=5; //非終結符的個數
char VT[15][5]={"id","+","*","(",")","#"}; //終結符表
int length_vt=6; //終結符的個數
char Fa[15][10]={"TE'","+TE'","","FT'","*FT'","","(E)","id"};
//産生式表:E->TE' 1:E'->+TE' 2:E'->空
// 3:T->FT' 4:T'->*FT' 5:T'->空 6:F->(E) 7:F->id
int analysis_table[10][11]={0,-1,-1,0,-2,-2,0,0,0,0,0,
-1,1,-1,-1,2,2,0,0,0,0,0,
3,-2,-1,3,-2,-2,0,0,0,0,0,
-1,5, 4,-1,5, 5,0,0,0,0,0,
7,-2,-2,6,-2,-2,0,0,0,0,0};
//預測分析表,-1表示出錯，-2表示該行終結符的follow集合，用于錯誤處理
（1） 預測分析表的構造方法1
給文法的正規式編号：存放在字元數組中，從0開始編号，正規式的編号即為該正規式在數組中對應的下标。
構造正規式數組：char P[10][10]={“E->TE’”,”E’->+TE’”,………}; (正規式可隻存儲右半部分，如E->TE’可存儲為TE’ ，正規式中的符号可替換，如可将E’改為M )
構造預測分析表：int analyze_table[10][10]={ } //數組元素值存放正規式的編号，-1表示出錯
（2）預測分析表的構造方法2
可使用三維數組
Char analyze_table[10][10][10]={ }
或
Char *analyze_table[10][10][10]={ }
2．針對預測分析表構造方法1的查找方法提示：
（1） 查非終結符表得到非終結符的序号no1
（2） 查終結符表得到終結符的序号no2
（3） 根據no1和no2查正規式表得到對應正規式的序号no3=analyze_table[no1][no2] ，如果no3=-1 表示出錯。
（4） 根據no3查找對應的正規式P[no3]
（5） 對正規式進行處理
3．錯誤處理機制
緊急方式的錯誤恢複方法（抛棄某些符号，繼續向下分析）
（1）棧頂為非終結符A，串中目前單詞屬于FOLLOW（A），則從棧中彈出A（此時可認為輸入串中缺少A表示的結構），繼續分析。 ---------錯誤編号為1
（2）棧頂為非終結符A，串中目前單詞不屬于FOLLOW（A），則可使串指針下移一個位置（認為輸入串中目前單詞多餘），繼續分析。----------錯誤編号為2
（3）棧頂為終結符，且不等于串中目前單詞，則從棧中彈出此終結符（認為輸入串中缺少目前單詞）或者将串指針下移一個位置（認為串中目前單詞多餘）。在程式中可選擇上述兩種 觀點中的一種進行處理。-------------錯誤編号3
是以error（）函數的編寫方式可按如下方式處理
Error（int errornum）
{
If（errornum==1）………………
Else if（errornum==2）……………
Else ………………..
//或者可用choose case語句處理
}
4．增加了錯誤處理的預測分析程式預測分析程式的算法：
将“#”和文法開始符依次壓入棧中；
把第一個輸入符号讀入a；
do{
把棧頂符号彈出并放入x中；
if(x∈VT)
{
if(x＝＝a) 将下一輸入符号讀入a;
else error(3 );
}
else
if(M[x,a]＝“x→y1y2…yk”)
{
按逆序依次把yk、yk−1、…、y1壓入棧中;
輸出“x→y1y2…yk”;
}
else if afollow（x）error(1 ); else error（2）；
}while(x!=“#”)
三．實驗要求
給定算術表達式文法，編寫程式。
測試資料：
1．算術表達式文法
E→TE’
E’ → +TE’|- TE’|ε
T→FT’
T’ →*FT’ |/ FT’ |%FT’|ε
F→(E) |id|num
給定一符合該文法的句子，如id+id*id#，運作預測分析程式，給出分析過程和每一步的分析結果。
輸出形式參考下圖：
四、編寫實驗報告
實驗分析：
1.将原算術表達式方法改寫為LL(1)文法為：
E→TE’
E’ → +TE’|- TE’|ε
T→FT’
T’ →*FT’ |/ FT’ |%FT’|ε
F→(E) |id|num
2.求出每個非終結符的FIRST和FOLLOW集；
| 非終結符 | FIRET | FOLLOW |
|---|---|---|
| E | { (,id,num } | { #,) } |
| E’ | { +,-,ε } | { #,) } |
| T | {(,id,num} | { +,-,#,) } |
| T’ | { *,/,%,ε } | { +,-,#,) } |
| F | { (,id,num } | { *,/,%,+,-,# ,)} |
3.構造預測分析表
| 坐标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 非\終結符 | * | / | % | + | - | ( | ) | id | num | # |
| 0 E | error(2) | error(2) | error(2) | error(2) | error(2) | E→ TE’ | error(1) | E→ TE’ | E→ TE’ | error(1) |
| 1 E’ | error(2) | error(2) | error(2) | E’ → +TE’ | E’ → -TE’ | error(2) | E’ → ε | error(2) | error(2) | E’ → ε |
| 2 T | error(2) | error(2) | error(2) | error(1) | error(1) | T→FT’ | error(1) | T→FT’ | T→FT’ | error(1) |
| 3 T’ | T’ →*FT’ | T’ →/FT’ | T’ →%FT’ | T’ →ε | T’ →ε | error(2) | T’ →ε | error(2) | error(2) | T’ →ε |
| 4 F | error(1) | error(1) | error(1) | error(1) | error(1) | F→(E) | error(1) | F→id | F→num | error(1) |
4.繪制程式設計流程圖
5.c++代碼實作
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define TT 0
char aa[20]=" ";//用來存儲從txt檔案中讀取的字元串
int pp=0;//用來标記字元
char VN[5]={'E','e','T','t','F'}; // 非終結符表
int length_vn=5; //非終結符的個數
char VT[10]={'*','l','m','+','-','(',')','i','n','#'}; //終結符表 l->/ m->% i->id n->num
int length_vt=10; // 終結符的個數
char Fa[12][6]={"Te","+Te","-Te","NULL","Ft","*Ft","nFt","mFt","NULL","(E)","i","n"};
//産生式表 :0:E->Te 1:e->+Te 2:e->-Te 3:e->空
char F[12][6]={"E->","E'->","E'->","E'->","T->","T'->","T'->","T'->","T'->","F->","F->","F->"};
//構造預測分析表,-1表示出錯，-2表示該行終結符的follow集合，用于錯誤處理
int analysis_table[5][10]={
-2,-2,-2,-2,-2,0,-1,0,0,-1,
-2,-2,-2,1,2,-2,3,-2,-2,3,
-2,-2,-2,-1,-1,4,-1,4,4,-1,
5,6,7,8,8,-2,8,-2,-2,8,
-1,-1,-1,-1,-1,9,-1,10,11,-1};
char stack[50];
int top=-1;
// 程式初始化：輸入并打開源程式檔案
void initscanner()
{
int i=0;
FILE *fp;
if((fp=fopen("a.txt","r"))==NULL){
printf("Open error!");
exit(0);
}
char ch=fgetc(fp);
while(ch!=EOF){
aa[i]=ch;//将字元依次存入aa數組
i++;
ch=fgetc(fp);
}
fclose(fp);
}
//字元入棧
void push(char a)
{
top++;
stack[top]=a;
}
//字元出棧 ，彈出棧頂元素
char pop()
{
return stack[top--];
}
//字元x是否是終結符
int includevt(char x)
{
for(int i=0;i<length_vt;i++)
{
if(VT[i]==x) return 1;
}
return 0;
}
//查找非終結符，終結符 在預測分析表中的坐标，傳回坐标對應資訊
int includean(char x,char a)
{
int i,j;
//非終結符
for(i=0;i<length_vn;i++)
if(VN[i]==x) break;
//終結符
for(j=0;j<length_vt;j++)
if(VT[j]==a) break;
return analysis_table[i][j];
}
void destory()
{
int flag=0;
int flagg=0;
push('#'); //将 "#"和文法開始符依次壓入棧中
push(VN[0]);//将第一個非終結符入棧
char a =aa[pp]; //把第一個輸入符号讀入 a,aa
char x;
//錯誤處理機制
do{
// printf("%s\t\t",stack);
if(flag==0)
x=pop(); //把棧頂符号彈出并放入 x 中
flag=0;
printf("%c\t\t\t\t%c\t\t",x,a);
//如果a是終結符
if(includevt(a)==1)
{
if(includevt(x)==1)
{
if(x==a)
{
if(a=='#')
{
flagg=1;
printf(" 結束 \n");
}
else printf(" 比對終結符 %c\n",x);
pp++;
a=aa[pp]; //将下一輸入符号讀入 a;
}
else
{
flag=1;
printf(" 出錯 ,跳過 %c\n",a);
pp++;
a=aa[pp];
}
}
//存在該表達式
else if(includean(x,a)>=0)
{
//擷取分析表對應坐标資料
int h=includean(x,a);
printf(" 展開非終結符 %s%s\n",F[h],Fa[h]);
int k;
for(k=0;k<10;k++)
if(Fa[h][k]=='\0')
break;
if(k==4)
{
//printf("+++++++++++pop %c \n",x);
}
else
{
while(k!=0) //按逆序依次把 yk、yk?1、 , 、 y1 壓入棧中
{
k--;
push(Fa[h][k]);
}
}
}
//-1表示出錯
else if(includean(x,a)==-1)
{
flag=1;
printf(" 出錯 ,從棧頂彈出 %c\n",x);
x=pop();
}
//
else
{
flag=1;
printf(" 出錯 ,跳過 %c\n",a);
pp++;
a=aa[pp];
}
}
else
{
flag=1;
printf(" 出錯 ,跳過 %c\n",a);
pp++;
a=aa[pp];
}
}while(x!='#');
if(flagg==0)
{
printf("%c\t\t\t%c\t",x,a);
printf(" 結束 \n");
}
}
int main()
{
printf(" 文法分析工程如下 :\n");
initscanner();
cout<<"-----------------文法如下---------------------"<<endl;
cout<<"E->TE'"<<endl;
cout<<"E'->+TE'|-TE'|~"<<endl;
cout<<"T->FT'"<<endl;
cout<<"T'->*FT'|/FT'|%FT'|~"<<endl;
cout<<"F->(E)|id|num"<<endl;
printf(" 要分析的語句是 :%s\n",aa);
printf(" 文法分析工程如下 :\n");
printf("棧頂元素 \t\t 目前單詞記号 \t\t 動作 \n");
printf("--------------------------------------------------------------------\n");
destory();
return 0;
}
6.測試結果展示
7.不足分析
實驗還存在一定的不足，相信一些同學通過對比測試結果會發現，與實驗要求存在不小的差别，
首先棧頂元素輸出的時候，沒有輸出T‘，取而帶之的是小寫的t，這裡主要差別是前者是兩個字元，後者是一個字元，相比易兩個字元，一個字元在進行字元讀取時更好處理，比如說在倒序入棧時，兩個字元由于可以分割，進入棧中時就變成了’T，這樣就導緻了程式混亂。
還有不同的地方目前單詞記号實驗要求輸出的時id，而我輸出的時i，這裡也是遇到了逆序入棧的問題，多于一個字元串，就會導緻入棧出錯，這裡我想到了解決辦法，這就需要于詞法分析器聯合使用，詞法分析器将單詞分析出來，然後再進行處理。
再然後就是動作動作中由于id是兩個字元，是以在進行處理時，識别了i,但是在識别d是，發現終結符中不存在該字元，導緻程式出錯，識别不出，跳過。這個問題的解決方式也和上一個是一樣的，利用詞法分析，将語句進行詞法分析。再進行處理，就不會出錯了。
實驗算是完成了，但是還有許多不足，下一篇文章将用python再做一遍，python相對于c++更易操作，對字元串的處理更加寬松靈活，好了，做完後我會把python版連接配接分享到這裡。
最後！！！
歡迎點贊，關注
編譯原理預測分析表一篇解決你所有問題（python版）