1、 合肥工業大學計算機與信息學院計算機系2013級編譯原理課程設計報告姓 名： 馬駿 專業年級： 信息安全13-1 學 號： 2013211869 提交時間： 2016年07月 1、 實驗題目自上而下的LL(1)文法分析2、 實驗目的了解掌握自上而下的LL（1）文法分析過程。二、實驗內容與要求 從語法分析樹構造句型所有的推導的程序實現，接受用戶任意輸入的一個句型的語法分析樹（其表示存于指定文件中），生成該語法分析樹中包含的該句型的所有推導（顯示輸出）。 構造一程序，實現教材P.78的FIRST(X)集合的構造算法。對任一給定的文法G，程序輸出所有非終結符P的FIRST(P)。構造一程序，實現教材

2、P.78的FIRST(X)集合的構造算法。對任一給定的文法G，程序輸出所有非終結符P的FIRST(P)。在此基礎上，構造一程序，實現教材P.79的FOLLOW(A)集合的構造算法。對任一給定的文法G，程序輸出所有非終結符A的FOLLOW (A)。對于給定的一個LL(1)文法，假定所有非終結符號P的集合FIRST(P)和集合FOLLOW(P)都已知，構造其預測分析表（實現教材P.79給出的預測分析表構造算法）。對教材P.79給出的例4.7構造出預測分析表。程序顯示輸出預測分析表或輸出到指定文件中。 首先實現集合FIRST(X)構造算法和集合FOLLOW(A)構造算法，再實現教材P.79給出的預測

3、分析表構造算法。程序顯示輸出預測分析表或輸出到指定文件中。 對文法按教材P.76表4.1構造出G的預測分析程序，程序顯示輸出如P.78那樣的匹配過程。三、實驗環境與工具操作系統：Windows 7開發語言：C+4、 開發過程1） 字符要求：你的程序必須能夠根據以下字符來處理語法：- 終端字符：字母，數字，符號例如“+”，“ ”，;- 非終端字母表中的大寫字母。符號“=”，“|”和“”（替換“”，因為它更容易輸入到文本文件）被保留用于語法的描述中，因此不能被用作終端。2） 初始狀態您的程序通過讀取一個文件中的“文本”格式開始。這個文件的結構可以隨意構建，不做要求，但建議做成簡單的<simp

4、le>。例如，程序描述以下語句：E = E + T |TT = T * F |FF =（E）| 0 |1在這種情況，我們可以很容易確定E，T和F是非終端，而符號“（”，“）”，“*”和“+”和數字“0”和“1”是在終端。第一個非終端（第一衍生物）被認為是語法的公理。文本結構（在內存中）過程顯示在屏幕結果必須存儲在內存中，是一個您所選擇的數據結構。然后，使用一個函數再取出數據，存儲在內存中并屏幕上顯示（以你選擇的格式）。在上面的圖中，并在下文中，右列顯示的程序的執行的過程，并左欄表示中使用的數據結構。這些都是明顯的例子。你可以使用任何你想要的格式。3）消除傳遞沒有發現傳遞關系發現傳遞關系判

5、斷：是否包含左傳遞消除傳遞關系判斷你的程序是否包含一個傳遞關系或沒有。如果包含，遞歸應該被消除。沒有傳遞關系的語句遍歷語句指向自己的判斷：您可以創建一個新的數據結構語句來表示其中傳遞關系已被刪除，這有利于進一步加工。在這種情況下，如果語法不包含判定遞歸的語句，程序當然必須使用第二數據結構的副本。3）計算“first集”和“follow集”的集合為了產生一個分析器，你現在必須計算，每個分支，“第一個”和“其后”的集合·。 結果被存儲在數據結構，再次“你的選擇。”然后，這些集合被顯示在屏幕上圖注釋：Calcul des ensembles « premiers

6、87; et « suivants » 計算“第一個”和“其后”的集合Affichage des ensembles 顯示集合 premiers 第一個 suivants其后 4）分析表的結構具有非遞歸語法以及“第一個”和“其后”的集合，你的程序現在可以建立預測分析表。結果以表的形式顯示在屏幕上。圖注釋：Construction de la table danalyse分析表的結構table danalyse 分析表 Affichage de la table danalyse 顯示分析表輸入字符串的分析最后一步：你的程序讀取輸入（鍵盤）的表達和分析。指出，結果是否符合語法

7、。你要盡可能準確的鑒定結果：定位錯誤在沒有辨認出表達式的情況下。其次，你的程序必須能夠完成對輸入多個字符串作為輸入，不要忘記重新啟動你的程序。顯示分析結果判斷是否繼續讀取表達式5、 程序實現6、 程序代碼/*不支持規則源文件中有空格注意 使用#表示空產生式 使用$表示結束符# */#include<iostream>#include<string>#include<fstream>#include<windows.h>using namespace std;const char* sourcefile="ma_grammaira.txt

8、" /定義源文件/const int max=100;#define max 100class signpublic:sign()sign(int check,char fu)if(check!=0&&check!=1) /符號屬性只有0和1cout<<"error sign creat!"<<endl;elseidentity=check; /設置符號屬性id=fu; /設置非終結符 符號funnumber=0;/設置符號規則數為0firstnumber=0;follownumber=0;void add(string s

9、l)/添加產生規則funfunnumber=sl;funnumber+;void pop(int q)/刪除某一規則if(q>=funnumber|q<0)cout<<"error wrong delete fun in sign!"return;for(int x=q;x<funnumber-1;x+)funx=funx+1;funnumber-;void pop_first(char q)/從first集刪除某一節點for(int x=0;x<firstnumber;x+)if(firstx=q)for(int y=x;y<fi

10、rstnumber-1;y+)firsty=firsty+1;firstnumber-;x-;/為了接著上次檢查點void pop_follow(char q)/從first集刪除某一節點for(int x=0;x<follownumber;x+)if(followx=q)for(int y=x;y<follownumber-1;y+)followy=followy+1;follownumber-;x-;/為了接著上次檢查點void add_first(char q)/向first添加元素for(int x=0;x<firstnumber;x+)if(firstx=q)ret

11、urn; firstfirstnumber=q;firstnumber+;void add_follow(char q)/向follow添加元素for(int x=0;x<follownumber;x+)if(followx=q)return; followfollownumber=q;follownumber+;int identity; /符號屬性0為非終結符 1為終結符char id; /符號string funmax;/符號產生規則int funnumber; /符號產生規則數量char firstmax;/first集 int firstnumber; char followm

12、ax;/follow集 int follownumber;class cell /分析表的單元格結構public: char cell_unendsign;/終結符char cell_endsign;/非終結符string cell_fun;/產生式;cell tablemaxmax; /分析表數據結構int table_unend_number;/非終結符數int table_end_number;/終結符數sign unendsignmax;/非終結點集合int unendsignnumber=0;sign endsignmax;/終結點集合int endsignnumber=0;void

13、 readsource(const char*sf) /讀取源文件ma_grammaira.txt int x;unendsignnumber=0;endsignnumber=0;ifstream ifs;ifs.open(sourcefile);char bufmax;for(x=0;x<max;x+)bufx='0'while(ifs.getline(buf,sizeof(buf) /一行一行讀取unendsignunendsignnumber=sign(0,buf0);unendsignnumber+;string rule;for(int x=2;x<max

14、;x+)if(bufx='0') break;if(bufx='|')/cout<<rule<<endl;unendsignunendsignnumber-1.fununendsignunendsignnumber-1.funnumber=rule;/規則放在每個非終結符實例中unendsignunendsignnumber-1.funnumber+;rule=""continue;rule+=bufx;char kk=bufx;unendsignunendsignnumber-1.fununendsignunends

15、ignnumber-1.funnumber=rule;unendsignunendsignnumber-1.funnumber+;/cout<<rule<<endl;void addendsign(char sg) /添加終結符for(int x=0;x<endsignnumber;x+)if(endsignx.id=sg)return;endsignendsignnumber.id=sg;endsignendsignnumber.identity=1;endsignnumber+;void dealend()/由非終結符產生式得到終結符for(int x=0;x

16、<unendsignnumber;x+)for(int y=0;y<unendsignx.funnumber;y+)for(int z=0;z<unendsignx.funy.length();z+)char kk=unendsignx.funyz;if(int(kk)>=65&&int(kk)<=90)continue; /A到Z為非終結符else addendsign(kk);bool exit_endsign(char sg) /終結符表是否有sgint x;for(x=0;x<endsignnumber;x+)if(endsignx.

17、id=sg) return true;return false;bool exit_unendsign(char sg) /非終結符表是否有sgfor(int x=0;x<unendsignnumber;x+)if(unendsignx.id=sg)return true;return false;sign get_unendsign(char sg)/從非終結符表中得到非終結符為sg的實例for(int x=0;x<unendsignnumber;x+)if(unendsignx.id=sg)return unendsignx;cout<<"error ge

18、t no unend sign!"<<endl;sign er;return er;int get_unendsign_number(char sg)/從非終結符表中得到非終結符為sg的下標for(int x=0;x<unendsignnumber;x+)if(unendsignx.id=sg)return x;cout<<"error get no unend sign!"<<endl;return 0;int get_endsign_number(char sg)/從非終結符表中得到終結符為sg的下標for(int x

19、=0;x<endsignnumber;x+)if(endsignx.id=sg)return x;cout<<"error get no end sign!"<<endl;return 0;bool rule_first_check(sign m_sign,char sg)/查看非終結符實例m_sign 產生式首是否為sg int y;for(y=0;y<m_sign.funnumber;y+)if(m_sign.funy0=sg)return true;int check=0;for(y=0;y<m_sign.funnumber;

20、y+)if(exit_unendsign(m_sign.funy0)sign msg=get_unendsign(m_sign.funy0);if(rule_first_check(msg,sg)check=1;break;if(check)return true;else return false;bool check_L_recursion()/檢查是否含有直接左遞歸和傳遞左遞歸 true表示有 false表示沒有 int x,y;for(x=0;x<unendsignnumber;x+) /檢查直接左遞歸for(y=0;y<unendsignx.funnumber;y+)if

21、(unendsignx.funy0=unendsignx.id)return true;for(x=0;x<unendsignnumber;x+) /檢查傳遞左遞歸 if(rule_first_check(unendsignx,unendsignx.id) return true;return false;sign new_unendsign() /創建一個新非終結符 即用于規則p=p. 需要p'char a=65;while(1)if(a>90|unendsignnumber>26)cout<<"error no more size for u

22、nend sign!"<<endl;break;int check=1; for(int x=0;x<unendsignnumber;x+)if(unendsignx.id=a)a+;check=0;break;if(check)unendsignunendsignnumber.id=a;unendsignunendsignnumber.identity=0;unendsignnumber+;break;return unendsignunendsignnumber-1;void pop_unendsign(char sg) /刪除某一非終結符for(int x=0

23、;x<unendsignnumber;x+)if(unendsignx.id=sg)for(int y=x;y<unendsignnumber-1;y+)unendsigny=unendsigny+1;unendsignnumber-;return;cout<<"error no unend sign for pop"<<endl;return;void deal_direct_L_recursion(int thisnumber) /消除 unendsignthisnumber的直接左遞歸 在deal_L_total_recursion

24、()中調用 int i;if(!check_L_recursion()return;int check=0;for(i=0;i<unendsignthisnumber.funnumber;i+) /先檢查 unendsignthisnumber是否存在 直接左遞歸 if(unendsignthisnumber.funi0=unendsignthisnumber.id)check=1;break;if(check)new_unendsign();int kp=unendsignnumber-1;for(i=0;i<unendsignthisnumber.funnumber;i+) /

25、增加p'的規則a0p'|a1p'|# 增加p->b0p'|b1p'if(unendsignthisnumber.funi0=unendsignthisnumber.id)string ss=""for(int x=1;x<unendsignthisnumber.funi.length();x+)ss+=unendsignthisnumber.funix;if(ss="#")cout<<"error can't deal whith P->P# "<&l

26、t;endl;return;ss=ss+unendsignkp.id;unendsignkp.add(ss);elseif(unendsignthisnumber.funi!="#")unendsignthisnumber.funi=unendsignthisnumber.funi+unendsignkp.id;if(unendsignthisnumber.funi="#")string ss=""ss+=unendsignkp.id;unendsignthisnumber.add(ss);unendsignkp.add("

27、#");/為p'增加 p-># 的規則for(i=0;i<unendsignthisnumber.funnumber;i+) /刪除p->p. 的產生式if(unendsignthisnumber.funi0=unendsignthisnumber.id)unendsignthisnumber.pop(i);i=0;void deal_L_total_recursion()/消除所有左遞歸 int i,j,t,k,qq;for(i=0;i<unendsignnumber;i+)for(j=0;j<i;j+)for( t=0;t<unends

28、igni.funnumber;t+)if(unendsigni.funt0=unendsignj.id)string say=""for( k=1;k<unendsigni.funt.length();k+)say+=unendsigni.funtk;unendsigni.pop(t);for( qq=0;qq<unendsignj.funnumber;qq+)string sp=unendsignj.funqq;if(sp!="#")sp+=say;unendsigni.add(sp);deal_direct_L_recursion(i);

29、 /消除Pi 的直接左遞歸void deal_first_club()/求各節點的first集 int x,t;for(x=0;x<endsignnumber;x+)endsignx.add_first(endsignx.id);int check=1;while(check)check=0;for(x=0;x<unendsignnumber;x+)int oldnumber=unendsignx.firstnumber; /用于記錄first集是否再增大for(t=0;t<unendsignx.funnumber;t+) unendsignx.add_first(unend

30、signx.funt0);for(t=0;t<unendsignx.firstnumber;t+)if(exit_unendsign(unendsignx.firstt)int kp=get_unendsign_number(unendsignx.firstt);for(int q=0;q<unendsignkp.firstnumber;q+)if(unendsignkp.firstq!='#')unendsignx.add_first(unendsignkp.firstq);if(unendsignx.firstnumber!=oldnumber)check=1;

31、check=1;while(check)check=0;for(x=0;x<unendsignnumber;x+) /判斷first是否應包含# for(int y=0;y<unendsignx.funnumber;y+) int overcheck=1; for(int t=0;t<unendsignx.funy.length();t+) if(exit_unendsign(unendsignx.funyt)continue;elseovercheck=0;break; if(overcheck)/如果存在P->ABCD. int thischeck=1;for(in

32、t t=0;t<unendsignx.funy.length();t+)int oop=get_unendsign_number(unendsignx.funyt);int incheck=0;for(int z=0;z<unendsignoop.firstnumber;z+)if(unendsignoop.firstz='#')incheck=1;break;if(incheck) continue;else thischeck=0;break;if(thischeck)int sp=unendsignx.firstnumber;unendsignx.add_fi

33、rst('#');if(sp!=unendsignx.firstnumber) check=1; for(x=0;x<unendsignnumber;x+)/消除first集中的非終結符for(int y=0;y<unendsignx.firstnumber;y+)if(exit_unendsign(unendsignx.firsty)unendsignx.pop_first(unendsignx.firsty); y-;void deal_follow_club() /求每個非終結符的follow集 int x,y,z,t;unendsign0.add_follo

34、w('$');/在開始符號的follow集中添加結束符$ int check=1; while(check) /循環至follow集不在增大check=0;for(x=0;x<unendsignnumber;x+)for( y=0;y<unendsignx.funnumber;y+)for( z=0;z<unendsignx.funy.length();z+)if(exit_unendsign(unendsignx.funyz)&&z<unendsignx.funy.length()-1)/p->.A kp=get_une

35、ndsign_number(unendsignx.funyz);int ss=unendsignkp.follownumber;if(unendsignx.funyz+1!='#')unendsignkp.add_follow(unendsignx.funyz+1);if(unendsignkp.follownumber!=ss)check=1; if(z=unendsignx.funy.length()-1&&exit_unendsign(unendsignx.funyz) /p->.Bint kp=get_unendsign_number(unends

36、ignx.funyz);for(t=0;t<unendsignx.follownumber;t+)int ssp=unendsignkp.follownumber;unendsignkp.add_follow(unendsignx.followt);if(unendsignkp.follownumber!=ssp)check=1;if(exit_unendsign(unendsignx.funyz)&&z<unendsignx.funy.length()-1)int thischeck=1; / 判斷p->.SABC 其中#在ABC的first集中for(in

37、t i=z+1;i<unendsignx.funy.length();i+)if(exit_unendsign(unendsignx.funyi)int thisthischeck=0;int kp=get_unendsign_number(unendsignx.funyi);for(int pp=0;pp<unendsignkp.firstnumber;pp+)if(unendsignkp.firstpp='#')thisthischeck=1;break;if(thisthischeck)continue;elsethischeck=0;break;thisch

38、eck=0;break;if(thischeck)int kp=get_unendsign_number(unendsignx.funyz); for(t=0;t<unendsignx.follownumber;t+)int ssp=unendsignkp.follownumber;unendsignkp.add_follow(unendsignx.followt);if(unendsignkp.follownumber!=ssp)check=1; for(x=0;x<unendsignnumber;x+) /非終結點在follow集則要把 其first集除#放入follow集fo

39、r(y=0;y<unendsignx.follownumber;y+)if(exit_unendsign(unendsignx.followy)int kp=get_unendsign_number(unendsignx.followy);for(t=0;t<unendsignkp.firstnumber;t+)if(unendsignkp.firstt='#')continue;elseint oop=unendsignx.follownumber;unendsignx.add_follow(unendsignkp.firstt);if(unendsignx.fo

40、llownumber!=oop)check=1;for(x=0;x<unendsignnumber;x+) /刪除follow集中的非終結點for(int y=0;y<unendsignx.follownumber;y+)if(exit_unendsign(unendsignx.followy)unendsignx.pop_follow(unendsignx.followy);y-; void init_LL_table() /分析表初始化 int x,y;addendsign('$');table_unend_number=0;table_end_number=0

41、;for(x=0;x<unendsignnumber;x+)for(y=0;y<endsignnumber;y+)tablexy.cell_endsign=endsigny.id;tablexy.cell_unendsign=unendsignx.id;cout<<"init table begin:"<<endl;for(x=0;x<unendsignnumber;x+)for(y=0;y<endsignnumber;y+)cout<<tablexy.cell_unendsign<<":&q

42、uot;<<tablexy.cell_endsign<<" "cout<<endl;void deal_LL_table()/ 產生LL(1)文法分析表 int x,j,y,t;init_LL_table(); for(x=0;x<unendsignnumber;x+)for(y=0;y<unendsignx.funnumber;y+)int check=1;int i=0;while(check) /P->A #一直屬于Aif(i=unendsignx.funy.length()break;check=0;if(exi

43、t_unendsign(unendsignx.funyi) /P->A 將A的first集的終結符 單元格 賦值P->Aint kp=get_unendsign_number(unendsignx.funyi);for(t=0;t<unendsignkp.firstnumber;t+)if(unendsignkp.firstt='#')check=1;i+;elseif(unendsignkp.firstt!='#') j=get_endsign_number(unendsignkp.firstt); tablexj.cell_fun=unen

44、dsignx.funy;else /p->a a是非終結符if(unendsignx.funyi!='#')j=get_endsign_number(unendsignx.funyi);tablexj.cell_fun=unendsignx.funy;if(unendsignx.funyi='#'&&i=0)check=1;break;if(check) /P->A如果#屬于Afor(t=0;t<unendsignx.follownumber;t+)if(unendsignx.followt!='#') j=ge

45、t_endsign_number(unendsignx.followt); tablexj.cell_fun=unendsignx.funy;for(x=0;x<unendsignnumber;x+) /沒有產生式的單元格標記為錯誤for(y=0;y<endsignnumber;y+) if(tablexy.cell_fun.length()>0)continue;else tablexy.cell_fun="error"void analizeLL_1() /預測分析程序string putin;char stackmax;int stacknumber

46、=0;stackstacknumber='$'stacknumber+;stackstacknumber=unendsign0.id;stacknumber+;cout<<"please enter:"cin>>putin;int x;for(x=0;x<putin.length();x+)cout<<putinx;if(!exit_endsign(putinx)|putinx='$'|putinx='#')cout<<" <- error no match sign"<<endl;return