编译原理之算符优先分析语法程序
生活随笔
收集整理的這篇文章主要介紹了
编译原理之算符优先分析语法程序
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
聲明：本程序只是筆者的第一次構造結果，存在非常多需要改進的地方，筆者會在github上持續重構，大家可以在下面地址中找到最新的重構代碼。https://github.com/Ggmatch/The-principle-to-compile
體驗算法優先分析法能達到的效果
算符優先分析法只考慮算符（廣義為終結符）之間的優先關系，例如若有文法G為：
（1）E->E+E
（2）E->E*E
（3）E->i
對輸入串i1+i2*i3的規約過程如表所示：
| (1) | # | i1 | +i2+i3# | 移進 |
| (2) | #i1 | + | i2*i3# | 規約(3) |
| (3) | #E | + | i2*i3# | 移進 |
| (4) | #E+ | i2 | *i3# | 移進 |
| (5) | #E+i2 | * | i3# | 規約(3) |
| (6) | #E+E | * | i3# | 移進 |
| (7) | #E+E* | i3 | # | 移進 |
| (8) | #E+E*i3 | # | 規約(3) | |
| (9) | #E+E*E | # | 規約(2) | |
| (10) | #E+E*E | # | 規約(1) | |
| (11) | #E | # | 接受 |
算符優先文法的定義
定義1：設有一文法G，如果G中沒有形如A->…BC…的產生式，其中B和C為非終結符，則稱G為算符文法也稱OG文法。
定義2：設有一不含空產生式的算符文法G，如果對任意兩個終結符對a,b之間至多只有優先級高于、低于和等于三種關系中的一種成立，則稱G是一個算符優先文法。
算符優先關系表的構造
- 首先定義兩個集合FIRSTVT(B)和LASTVT(B)
FIRSTVT(B)={b|B+=>b…或B+=>Cb…}，其中…表示V*中的符號串。
LASTVT(B)={a|B+=>…a或B+=>…aC} - 計算每個終結符之間的優先關系
對于A->…ab… A->…aBb… 則有a 優先級等于 b 成立。
對于A->…aB… 對于每一個b屬于FIRSTVT(B) 有a優先級低于b成立。
對于A->…Bb… 對于每一個a屬于LASTVT(B) 有a優先級高于b成立。 - 構造優先關系矩陣
利用每個終結符之間的優先關系即可構造出來。
構造FIRSTVT集和LASTVT集的算法
定義一個布爾數組F[m,n]（m為非終結符個數，n為終結符個數）和一個后進先出棧STACK。將所有的非終結符排序，用iA表示非終結符A的序號，再將所有的終結符排序，用iA表示非終結符A的序號，再將所有的終結符排序，用ja表示終結符a的序號。算法的目的是要使數組每一個元素最終取值滿足：F[iA,ja]的值為真，當前僅當a屬于FIRSTVT(A)。
構建FIRSTVT集的偽代碼（LASTVT集類似）如下：
PROCEDURE INSERT(A,a);IF NOT F[iA,ja] THENBEGINF[iA,ja] := TRUEPUSH[A,a] ONTO STACKEND /*主程序*/ BEGIN (MAIN)FOR i從1到m,j從1到nDO F[iA，ja] := FALSE;FOR 每個形如 A->a... 或 A->Ba...的產生式DO INSERT(A,a)WHILE STACK非空 DOBEGIN 把STACK的頂項記為(B,a)彈出去FOR 每個形如 A->B...的產生式彈出去INSERT(A,a)ENDEND (MAIN)構造優先關系表的算法
FPR 每個產生式 A->X1X2...Xn DOFOR i := 1 TO n-1 DOBEGIN IF Xi和X(i+1)均為終結符THEN 置 Xi優先級等于X(i+1);IF i<=n-2 且Xi和X(i+2)都為終結符，但X(i+1)為非終結符THEN 置 Xi優先級等于X(i+2);IF Xi為終結符而X(i+1)為非終結符THEN FOR FIRSTVT(X(i+1))中的每個b DO 置 Xi優先級低于b;IF Xi為非終結符而X(i+1)為終結符THEN FOR LASTVT(Xi)中的每個a DO 置 a優先級高于X(i+1);END優先函數f和g的構建
- 對于每個終結符a屬于VT（包括#號在內）令f(a) = g(a) = 1（也可以是其他整數）。
對每一終結符對逐一比較
如果a優先級高于b，而f(a)<=g(b)則令f(a)=g(b)+1。
如果a優先級低于b，而f(a)>=g(b)則令g(b)=f(a)+1。
如果a優先級等于b，而f(a)!=g(b)則令min{f(a),g(b)}=max{f(a),g(b)}。
重復第二步直到過程收斂。算符優先分析算法
最左素短語
設有文法G[S]，其句型的素短語是一個短語，它至少包含一個終結符，并除自身外不包含其他素短語，最左邊的素短語稱最左素短語。形如NiaiN(i+1)a(i+1)…ajN(j+)滿足：
（1）a(i-1)優先級低于ai
（2）ai/a(i+1)/…/aj優先級相同
（3）aj優先級高于a(j+1)
- 算法
完整代碼
#include <iostream> #include <string> #include <fstream> #include <stack> #include <algorithm> #include <sstream> using namespace std;#define P_Amount 20 #define RMAX 20 #define CMAX 20 #define NT_AMOUNT 20 #define T_AMOUNT 20 //文法結構體 class G { public:string T; //終結符的集合string NT; //非終結符的集合string begin; //文法開始符號string P[P_Amount]; //產生式的集合int P_Length; //產生式的個數bool FIRSTVT[RMAX][CMAX]; //非終結符的FIRSTVT集合bool LASTVT[RMAX][CMAX]; //非終結符的FIRSTVT集合int PRIORITY_TABLE[NT_AMOUNT][NT_AMOUNT]; //優先表，表內元素只有4種類型的值，-1代表行<列，1代表行>列，0代表行=列，2代表出錯int FR; //記錄F的有效行數int FC; //記錄F的有效列數int f[T_AMOUNT]; //符號棧內的優先級,f優先函數int g[T_AMOUNT]; //符號棧外的優先級，g優先函數G(){//初始化T = "";NT = "";begin = "";P_Length = 0;for (int i = 0; i < P_Amount; i++)P[i] = "";for (int i = 0; i < RMAX; i++){for (int j = 0; j < CMAX; j++){FIRSTVT[i][j] = false;}}for (int i = 0; i < RMAX; i++){for (int j = 0; j < CMAX; j++){LASTVT[i][j] = false;}}for (int i = 0; i < NT_AMOUNT; i++){for (int j = 0; j < NT_AMOUNT; j++){PRIORITY_TABLE[i][j] = 2; //默認為出錯狀態}}//初始狀態下f和g內的元素都置為1for (int i = 0; i < T_AMOUNT; i++){f[i] = 1; g[i] = 1;}}~G(){} };class Temp { public:char NT;char T; };void findor(string &str, char c, int *pos,int cap,int &len) //在str中尋找出所有|的位置,pos記錄其位置,cap為位置數組的容量，len為pos的有效長度 {for (int i = 0; i < cap; i++){//初始化pos[i] = 0;}int temp=0;for (int i = 0; i < str.length(); i++){int j=str.find(c, temp);if (j == -1){break;}pos[i] = j;len++;temp = j+1;} } //根據產生式得到終結符集合與非終結符集合 void getSyms(string *strs, int len, string &T,string &NT) //strs為產生式集合，len為產生式個數 {string strTemp=""; for (int i = 0; i < len; i++){if (strTemp.find(strs[i][0]) != -1) //若是找到已存在的符號，跳過continue;strTemp += strs[i][0];}NT = strTemp;for (int i = 0; i < len; i++){for (int j = 3; j < strs[i].length(); j++){if (strs[i][j] >= 'A' && strs[i][j] <= 'Z') //非終結符{if (NT.find(strs[i][j]) != 0) //該符號已存在,跳過continue;NT += strs[i][j];}else //終結符,可能是算符或i{if (T.find(strs[i][j]) != -1) //該符號已存在，跳過continue;T += strs[i][j];}}} }void zero(string *strs, int &len) //strs為輸入的文法表達式，len為表達式的個數 {string StrTemp[P_Amount];int lens,count=0; //count記錄新生成表達式的個數,lens記錄每個int pos[10]; for (int i = 0; i < len; i++) //將所有產生式按|隔開，生成多個產生式，存儲到StrTemp中{lens = 0;findor(strs[i], '|', pos, 10, lens); //尋找這條表達式中所有“|”的位置，存放到pos中，10為其最大容量,lens為“|”個數for (int z = 0; z < lens+1; z++) //將一個產生式按|隔開，生成多個產生式，存儲到StrTemp中，(len+1)代表要生成的表達式個數{if (z == 0){StrTemp[z + count] = strs[i].substr(0, 3) + strs[i].substr(3, (pos[z]-2 - 1));continue;}StrTemp[z + count] = strs[i].substr(0, 3) + strs[i].substr(pos[z - 1]+1, (pos[z] - pos[z - 1] - 1));if (z == lens){StrTemp[count + lens] = strs[i].substr(0, 3) + strs[i].substr(pos[lens - 1]+1, (strs[i].length() - pos[lens - 1] - 1));}}count += lens + 1;}//把StrTemp賦給strslen = count;for (int i = 0; i < count; i++){strs[i] = StrTemp[i];} } void test1(G &gm); //聲明 void first(G &grammer,string strs[],int len) //grammer為需要構造的文法對象，strs為經過zero后的文法表達式，len為表達式的個數 {grammer.begin = strs[0][0]; //開始符號grammer.P_Length = len; //產生式的個數for (int i = 0; i < len; i++) //得到產生式{grammer.P[i] = strs[i];}getSyms(strs, len, grammer.T, grammer.NT); //從產生式中得到非終結符集合與終結符集合}void test1(G &gm) //檢測函數,這里檢查文法數據結構的正確性 {cout << endl << "檢測：" << endl;cout << "文法的開始符號：" << gm.begin << endl;cout << "文法的非終結符集合：" << gm.NT << endl;cout << "文法的終結符集合：" << gm.T << endl;cout << "文法的產生式：" << endl;for (int i = 0; i < gm.P_Length; i++){cout << gm.P[i] << endl;}cout << endl; }void insert(G &gm, stack<Temp> &stck, char A, char a) // {int iA = gm.NT.find(A);int ia = gm.T.find(a);Temp tmp;tmp.NT = A;tmp.T = a;if (!gm.FIRSTVT[iA][ia]){gm.FIRSTVT[iA][ia] = true;stck.push(tmp);} }void insert1(G &gm, stack<Temp> &stck, char A, char a) // {int iA = gm.NT.find(A);int ia = gm.T.find(a);Temp tmp;tmp.NT = A;tmp.T = a;if (!gm.LASTVT[iA][ia]){gm.LASTVT[iA][ia] = true;stck.push(tmp);} }void test2(G &gm); //測試gm的FIRSTVT和LASTVT集合void second(G &gm) //gm為文法的四元組 {gm.FR = gm.NT.length();gm.FC = gm.T.length();stack<Temp> stck; Temp tmpBa;//得到G的FIRSTVT集合for (int i = 0; i < gm.P_Length; i++){if (gm.P[i].length() - 4 == 0) //產生式右邊只有一個符號{if (gm.P[i][3] < 'A' || gm.P[i][3]>'Z') //這個符號是終結符{insert(gm, stck, gm.P[i][0], gm.P[i][3]);}}else if (gm.P[i][3] >= 'A' && gm.P[i][3] <= 'Z') //右部的第一個符號為非終結符，那么加入右部的第二個符號{insert(gm, stck, gm.P[i][0], gm.P[i][4]);}else //右部的第一個符號為終結符{insert(gm, stck, gm.P[i][0], gm.P[i][3]);}}while (!stck.empty()){tmpBa = stck.top();stck.pop();for (int i = 0; i < gm.P_Length; i++){if (gm.P[i][0] != tmpBa.NT&&gm.P[i][3] == tmpBa.NT) //找到形如A->B···的產生式，FIRSTVT(B)必然FIRSTVT(A){insert(gm, stck, gm.P[i][0], tmpBa.T);}}}//得到G的LASTVT集合for (int i = 0; i < gm.P_Length; i++){if (gm.P[i].length() - 4 == 0) //產生式右邊只有一個符號{if (gm.P[i][3] < 'A' || gm.P[i][3]>'Z') //這個符號是終結符{insert1(gm, stck, gm.P[i][0], gm.P[i][3]);}}else if (gm.P[i][3] >= 'A' && gm.P[i][3] <= 'Z') //右部的最后一個符號為非終結符，那么加入右部的倒數第二個符號{insert1(gm, stck, gm.P[i][0], gm.P[i][gm.P[i].length()-2]);}else //右部的最后一個符號為終結符{insert1(gm, stck, gm.P[i][0], gm.P[i][gm.P[i].length()-1]);}}while (!stck.empty()){tmpBa = stck.top();stck.pop();for (int i = 0; i < gm.P_Length; i++){if (gm.P[i][0] != tmpBa.NT&&gm.P[i][gm.P[i].length()-1] == tmpBa.NT) //找到形如A->···B的產生式，LASTVT(B)必然LASTVT(A){insert1(gm, stck, gm.P[i][0], tmpBa.T);}}}}void test2(G &gm) {cout << "G的FIRSTVT集合：" << endl;cout << "\t";for (int i = 0; i < gm.T.length(); i++){if (i == gm.T.length() - 1){cout << gm.T[i] << endl;break;}cout << gm.T[i] << "\t";}for (int i = 0; i < gm.FR; i++){cout << gm.NT[i] << "\t";for (int j = 0; j < gm.FC; j++){if (j == gm.FC - 1){cout << gm.FIRSTVT[i][j] << endl;break;}cout << gm.FIRSTVT[i][j] << "\t";}}cout << "G的LASTVT集合：" << endl;cout << "\t";for (int i = 0; i < gm.T.length(); i++){if (i == gm.T.length() - 1){cout << gm.T[i] << endl;break;}cout << gm.T[i] << "\t";}for (int i = 0; i < gm.FR; i++){cout << gm.NT[i] << "\t";for (int j = 0; j < gm.FC; j++){if (j == gm.FC - 1){cout << gm.LASTVT[i][j] << endl;break;}cout << gm.LASTVT[i][j] << "\t";}}cout << endl; }void test3(G &gm); //測試third函數void third(G &gm) //gm為文法的數據結構 {for (int i = 0; i < gm.P_Length; i++){int lens = gm.P[i].length();for (int j = 3; j <= lens-2; j++){if ((gm.P[i][j]<'A'||gm.P[i][j]>'Z')&&(gm.P[i][j + 1]<'A'||gm.P[i][j + 1]>'Z')) //Xi和X(i+1)都為終結符{int temp = gm.T.find(gm.P[i][j]);int temp1 = gm.T.find(gm.P[i][j + 1]);gm.PRIORITY_TABLE[temp][temp1] = 0; //置為同等優先級}if (j <= (lens - 3) && (gm.P[i][j]<'A' || gm.P[i][j]>'Z') && (gm.P[i][j + 2]<'A' || gm.P[i][j + 2]>'Z') && (gm.P[i][j + 1] >= 'A'&&gm.P[i][j + 1] <= 'Z')) //Xi和X(i+2)為終結符，但X(i+1)為非終結符{int temp = gm.T.find(gm.P[i][j]);int temp1 = gm.T.find(gm.P[i][j + 2]);gm.PRIORITY_TABLE[temp][temp1] = 0; //置為同等優先級}if ((gm.P[i][j]<'A' || gm.P[i][j]>'Z') && (gm.P[i][j + 1] >= 'A' && gm.P[i][j + 1] <= 'Z')) //Xi為終結符而X(i+1)為非終結符{for (int z = 0; z < gm.T.length(); z++){if (gm.FIRSTVT[gm.NT.find(gm.P[i][j + 1])][z]){int temp = gm.T.find(gm.P[i][j]);int temp1 = z;gm.PRIORITY_TABLE[temp][temp1] = -1; //置于列優先于行}}}if ((gm.P[i][j+1]<'A' || gm.P[i][j+1]>'Z') && (gm.P[i][j] >= 'A' && gm.P[i][j] <= 'Z')) //X(i+1)為終結符而Xi為非終結符{for (int z = 0; z < gm.T.length(); z++){if (gm.LASTVT[gm.NT.find(gm.P[i][j])][z]){int temp = z;int temp1 = gm.T.find(gm.P[i][j+1]);gm.PRIORITY_TABLE[temp][temp1] = 1; //置于行優先于列}}}}} }void test3(G &gm) {cout << "G的優先分析表：" << endl;cout << "\t";for (int i = 0; i < gm.T.length(); i++){if (i == gm.T.length() - 1){cout << gm.T[i] << endl;break;}cout << gm.T[i] << "\t";}int lens = gm.T.length();for (int i = 0; i < lens; i++){cout << gm.T[i] << "\t";for (int j = 0; j < lens; j++){if (j == gm.T.length() - 1){cout << gm.PRIORITY_TABLE[i][j] << endl;break;}cout << gm.PRIORITY_TABLE[i][j] << "\t";}} }void test4(G &gm); //檢測優先函數f和gvoid four(G &gm) //構造優先函數f和g {bool isChanged = true; //isChanged代表上一次迭代f和g函數有沒有發生變化，有為trueint lens = gm.T.length();while (isChanged){isChanged = false;for (int i = 0; i < lens; i++){for (int j = 0; j < lens; j++){if (gm.PRIORITY_TABLE[i][j] == 2)continue;if (gm.PRIORITY_TABLE[i][j] == 1 && (gm.f[i] <= gm.g[j])){gm.f[i] = gm.g[j] + 1;isChanged = true;continue;}if (gm.PRIORITY_TABLE[i][j] == -1 && (gm.f[i] >= gm.g[j])){gm.g[j] = gm.f[i] + 1;isChanged = true;continue;}if (gm.PRIORITY_TABLE[i][j] == 0 && (gm.f[i] != gm.g[j])){if (gm.f[i] > gm.g[j]){gm.g[j] = gm.f[i];}else{gm.f[i] = gm.g[j];}isChanged = true;continue;}}}} }void test4(G &gm) //檢測four函數 {cout << "\t";for (int i = 0; i < gm.T.length(); i++){if (i == gm.T.length() - 1){cout << gm.T[i] << endl;break;}cout << gm.T[i] << "\t";}int lens = gm.T.length();cout << "f函數： ";for (int i = 0; i < lens; i++){if (i == lens - 1){cout << gm.f[i] << endl;break;}cout << gm.f[i] << "\t";}cout << "g函數： ";for (int i = 0; i < lens; i++){if (i == lens - 1){cout << gm.g[i] << endl;break;}cout << gm.g[i] << "\t";} }void test5(bool b); //檢測GuiYueQi是否識別出待規約串,b為true，則說明能識別bool GuiYueQi(G &gm, string str) //gm為文法的數據結構，str為待規約串,能識別為true，否則為false {string strStck=""; //用string對象做符號棧，方便取值strStck.append("#"); //初始化int k = 0,num=0;int j; //j表示最左素短語的開頭位置string a=""; //讀入單元string Q = ""; //作為待審查的最左素短語的開頭符號while (a!="#") //到了輸入串的最后一個字符，跳出{a = str[num++]; //把下一個輸入符號讀進a中if (gm.T.find(strStck[k]) != gm.T.npos) //如果棧頂的符號為終結符{j = k;}else{j = k - 1;}while (gm.f[gm.T.find(strStck[j])] > gm.g[gm.T.find(a)]) //往下找，直到找到棧內符號優先級小于或等于當前輸入符號的優先級{do{Q = strStck[j];if (gm.T.find(strStck[j - 1]) != gm.T.npos) //{j = j - 1;}else{j = j - 2;}} while (gm.f[gm.T.find(strStck[j])] >= gm.g[gm.T.find(Q)]);//把strStck[j+1]~strStck[k]規約為某個NstrStck.erase(strStck.begin() + j + 1, strStck.begin() + k); //把規約的符號退棧strStck.append("N"); //壓入某個非終結符Nk = j + 1;break;}if (gm.f[gm.T.find(strStck[j])] <= gm.g[gm.T.find(a)]) {k = k + 1;strStck.append(a);}else{return false;}}return true; // }void test5(bool b) {if (b){cout << "acc!" << endl;}else{cout << "fail!" << endl;} }int main() {G gm;string str[10];int len; //輸入的表達式個數int i = 0;//從文件讀入文法ifstream ifile("wenfa.txt"); //打開wenfa.txt文件while (ifile){ifile >> str[i++]; //讀入文法}ifile.close(); //關閉文件len = i - 1;zero(str, len); //依據‘|’，拆分表達式first(gm, str, len); //得到文法數據結構//test1(gm); //檢查zero()、first()函數second(gm); //得到每個非終結符的FIRSTVT和LASTVT集合//test2(gm); //檢測second函數third(gm); //得到優先分析表//test3(gm); //檢測third函數four(gm); //得到優先函數f和g//test4(gm); //檢測four函數string guiyuestr; //規約串ifile.open("guiyuechuan.txt"); stringstream io;io <<ifile.rdbuf();io >> guiyuestr;cout << "待規約串為："<< guiyuestr <<endl;bool b = GuiYueQi(gm, guiyuestr); //規約器，規約strtest5(b); //檢測待規約串被規約器處理后的結果return 0; }上述代碼中wenfa.txt與guiyuechuan.txt的內容如下，自己構建，并放在項目里c++文件所在處，要符合相對路徑。
wenfa.txt:
S->#E#
E->E+T
E->T
T->T*F
T->F
F->P!F|P
P->(E)
P->i
guiyuechuan.txt:
i+i#
本文理論部分引用于 《編譯原理（第二版）——張素琴——清華大學出版社》
總結
以上是生活随笔為你收集整理的编译原理之算符优先分析语法程序的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 书包网小说多线程爬虫
- 下一篇： MAUI 跨平台应用开发实战