LR-分析方法程序設(shè)計(jì)原理與實(shí)現(xiàn)技術(shù)實(shí)驗(yàn)報(bào)告及源代碼-北京交通大學(xué)

1、LR 分析方法程序設(shè)計(jì)原理與實(shí)現(xiàn)技術(shù)XXX 1028XXX 計(jì)科1XXX班1. 程序功能描述通過設(shè)計(jì)、編寫和構(gòu)造LR（0）項(xiàng)目集規(guī)范簇和LR 分析表、對(duì)給定的符號(hào)串進(jìn)行LR 分析的程序，了解構(gòu)造LR（0）分析表的步驟，對(duì)文法的要求，能夠從文法G 出發(fā)生成LR（0）分析表，并對(duì)給定的符號(hào)串進(jìn)行分析。要求以表格或圖形的方式實(shí)現(xiàn)。實(shí)現(xiàn)LR(0)分析法，完成以下文法。GE:EaAbBAcAdBcBd2. 設(shè)計(jì)要求（1）構(gòu)造LR（0）項(xiàng)目集規(guī)范簇；要求輸入LR(0)文法時(shí)，可以直接輸入，也可以讀取文件，并能夠以表格的形式輸出項(xiàng)目集規(guī)范簇集識(shí)別活前綴的有窮自動(dòng)機(jī)（2）構(gòu)造LR（0）分析表。要求要求輸入LR

2、(0)文法時(shí)，可以直接輸入，也可以讀取文件；輸出項(xiàng)目集規(guī)范簇，可以調(diào)用前一處理部分的結(jié)果，輸出為L(zhǎng)R(0)分析表（3）LR(0)分析過程【移進(jìn)、歸約、接受、報(bào)錯(cuò)】的實(shí)現(xiàn)。要求調(diào)用前一部分處理結(jié)果的分析表，輸入一個(gè)符號(hào)串，依據(jù)LR（0）分析表輸出與句子對(duì)應(yīng)的語法樹，或直接以表格形式輸出分析過程。3. 主要數(shù)據(jù)結(jié)構(gòu)描述：文法表示，項(xiàng)目集規(guī)范族表示以及文法接受的符號(hào)和移植到的位置：struct grammar /文法char left;vector right;struct grammar1char left;vector right;int sign;struct defineint data;c

3、har type;struct progect /項(xiàng)集vector data; /數(shù)據(jù)vector acc; /可接受的符號(hào)vector next; /轉(zhuǎn)移到的位置;vector lge; /文法vector pro; /項(xiàng)目集規(guī)范族4. 程序結(jié)構(gòu)描述本程序一共有10個(gè)功能函數(shù)：void get(); /獲取文法void print(); /打印文法void fun(); /構(gòu)造LR（0）項(xiàng)目集規(guī)范族void analy(); /構(gòu)造LR（0）分析表void test(); /測(cè)試文法int equal(progect p1,progect p2); /判斷兩項(xiàng)是否相等int findpoin

4、t(string str); /判斷點(diǎn)的位置是否在最后，是的話就是規(guī)約項(xiàng)目int findlocal(string str); /尋找此符號(hào)串對(duì)應(yīng)的規(guī)范族的位置char gettype(char ch,int num); /根據(jù)狀態(tài)集，返回操作的類別（移近，規(guī)約，接受）int getnumber(char ch,int nun); /根據(jù)狀態(tài)機(jī)，返回下一步所跳轉(zhuǎn)的狀態(tài)集5. 實(shí)驗(yàn)代碼 詳見附件6. 程序測(cè)試6.1功能測(cè)試程序運(yùn)行后顯示如下功能菜單：選擇獲取文法：選擇打印文法：選擇構(gòu)造LR（0）項(xiàng)目集規(guī)范族：選擇構(gòu)造LR（0）分析表：6.2文法測(cè)試分析失敗:aAcAd分析成功:acd7. 實(shí)驗(yàn)總

5、結(jié)：本次實(shí)驗(yàn)按照書上的相應(yīng)步驟，一步一步按照要求來完成實(shí)現(xiàn)，最終文成了給定文法的分析程序。首先是獲取文法，文法的獲取是采用直接輸入的方法，保存成預(yù)先設(shè)定的結(jié)構(gòu)體，然后根據(jù)文法，對(duì)文法編號(hào)，求出項(xiàng)目集規(guī)范族，然后再構(gòu)造LR（0）分析表，最后根據(jù)分析表來判斷輸入符號(hào)串是否為此文法產(chǎn)生的語言。這次實(shí)驗(yàn)花費(fèi)的時(shí)間比較長(zhǎng)，因?yàn)橛胏語言在編寫項(xiàng)目集族以及構(gòu)造分析表的算法都遇到了一些困難,需要再實(shí)驗(yàn)中邊寫邊學(xué)習(xí)。在完成實(shí)驗(yàn)后，我對(duì)LR（0）文法有了更加深入的了解。/ lr0.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/#include stdafx.h#include #include #include us

6、ing namespace std;struct grammar /文法char left;vector right;struct grammar1char left;vector right;int sign;struct defineint data;char type;struct progect /項(xiàng)目集vector data; /數(shù)據(jù)vector acc; /可接受的符號(hào)vector next; /轉(zhuǎn)移到的位置;vector lge; /文法vector pro; /項(xiàng)目集規(guī)范族void get(); /獲取文法void print(); /打印文法void fun(); /構(gòu)造LR

7、（0）項(xiàng)目集規(guī)范族void analy(); /構(gòu)造LR（0）分析表void test(); /測(cè)試文法int equal(progect p1,progect p2); /判斷兩項(xiàng)是否相等int findpoint(string str); /判斷點(diǎn)的位置是否在最后，是的話就是規(guī)約項(xiàng)目int findlocal(string str); /尋找此符號(hào)串對(duì)應(yīng)的規(guī)范族的位置char gettype(char ch,int num); /根據(jù)狀態(tài)集，返回操作的類別（移近，規(guī)約，接受）int getnumber(char ch,int nun); /根據(jù)狀態(tài)機(jī)，返回下一步所跳轉(zhuǎn)的狀態(tài)集int mai

8、n()int choose;while(1)cout * endl;cout 獲取文法請(qǐng)按 1 endl;cout 打印文法請(qǐng)按 2 endl;cout 構(gòu)造LR（0）項(xiàng)目集規(guī)范族請(qǐng)按 3 endl;cout 構(gòu)造LR（0）分析表請(qǐng)按 4 endl;cout 文法測(cè)試請(qǐng)按 5 endl;cout 結(jié)束請(qǐng)按 0 endl;cout * endl;cout choose;if(choose = 0)break;switch(choose)case 1: get(); break;case 2: print(); break;case 3: fun(); break;case 4: analy();

9、 break;case 5: test(); break;default:break;return 0;void get()grammar temp,temp1,temp2;temp.left = E;temp.right.push_back(aA);temp.right.push_back(bB);temp1.left = A;temp1.right.push_back(cA);temp1.right.push_back(d);temp2.left = B;temp2.right.push_back(cB);temp2.right.push_back(d);lge.push_back(tem

10、p);lge.push_back(temp1);lge.push_back(temp2);cout * endl;cout 文法獲取完成 endl;cout * endl;cout endl;void print()cout * endl;for(int i = 0;i lge.size();i +)for(int j = 0;j lgei.right.size();j +)cout lgei.left ;cout lgei.rightj endl;cout * endl;cout endl;void fun()grammar1 g; /存入首元素g.sign = 0;g.left = S;g

11、.right.push_back(.E);progect p;p.data.push_back(g);pro.push_back(p);int sign = 0;while(1)sign = 0;for(int i = 0;i pro0.data.size();i +)for(int j = 0;j pro0.datai.right.size();j +)char ch = pro0.datai.rightj1;if(ch = A & pro0.datai.sign = 0) /需要迭代pro0.datai.sign = 1;sign = 1;for(int k = 0;k lge.size(

12、);k +)if(lgek.left = ch)grammar1 gg;gg.left = lgek.left;gg.sign = 0;for(int p = 0;p lgek.right.size();p +)gg.right.push_back(. + lgek.rightp);pro0.data.push_back(gg);if(sign = 0)break;/迭代添加其他的sign = 0;while(1)sign = 0;for(int i = 0;i pro.size();i +)for(int j = 0;j proi.data.size();j +)for(int k = 0;

13、k proi.dataj.right.size();k +)string temp = proi.dataj.rightk;int p = 0;while(p temp.length() & tempp != .)p +;if(p temp.length() - 1) /需要添加progect pp;grammar1 gg;gg.left = proi.dataj.left;gg.sign = 0;string temp1 = ;for(int q = 0;q p;q +) /復(fù)制改變右部temp1 += tempq;temp1 += tempp + 1; /.右邊第一個(gè)元素temp1 +=

14、.;for(int q = p + 2;q temp.length();q +)temp1 += tempq;gg.right.push_back(temp1);pp.data.push_back(gg);p = 0;while(temp1p != .& p temp1.length()p +;if(p = A & temp1p + 1 = Z) /非終結(jié)符，繼續(xù)添加for(int m = 0;m lge.size();m +)if(lgem.left = temp1p + 1)grammar1 gg1;gg1.left = temp1p + 1;gg1.sign = 0;for(int n

15、= 0;n lgem.right.size();n +)gg1.right.push_back(. + lgem.rightn);pp.data.push_back(gg1);/判斷是否已經(jīng)存在int sign1 = 0;for(int i1 = 0;i1 pro.size();i1 +)if(equal(proi1,pp)sign1 = 1;if(sign1 = 0)sign = 1;pro.push_back(pp); /添加新的東西if(sign = 0)break;cout * endl;for(int i = 0;i pro.size();i +) /打印cout I i : end

16、l;for(int j = 0;j proi.data.size();j +)for(int k = 0;k proi.dataj.right.size();k +)cout proi.dataj.left ;cout proi.dataj.rightk endl;cout endl;cout * endl;cout endl;void analy()for(int i = 0;i pro.size();i +)for(int j = 0;j proi.data.size();j +)for(int k = 0;k Z | tempt A)d.data = findlocal(temp);d.

17、type = s;elsed.data = findlocal(temp);d.type = ;proi.next.push_back(d); /添加位置else /規(guī)約項(xiàng)目string s = abcd#;for(int t = 0;t s.length();t +)proi.acc.push_back(st);define d;d.data = findlocal(temp);d.type = r;proi.next.push_back(d);cout * endl;string temp = abcd#EAB;cout ;for(int i = 0;i temp.length();i +

18、)cout tempi ;cout endl;for(int i = 0;i pro.size();i +)if(i 10)cout i ;elsecout i ; if(proi.next0.data = -1) /acccout acc;elsefor(int k = 0;k temp.length();k +)int sign = 0;for(int j = 0;j proi.acc.size();j +)if(proi.accj = tempk)cout proi.nextj.type proi.nextj.data ;sign = 1;if(sign = 0)cout ;cout e

19、ndl;cout * endl;cout endl;void test()cout * endl;cout 請(qǐng)輸入有識(shí)別的字符串 str;cout endl;string temp = ;int i,j;int num = 0; /初始狀態(tài)int count = 0; /字符串指針char ch = strcount;temp += strcount; /放入第一個(gè)符號(hào)while(1)if(gettype(ch,num) = s) /移近num = getnumber(ch,num);if(count str.length() - 1)count +;temp += strcount;ch =

20、 strcount;else if(gettype(ch,num) = r) /規(guī)約num = getnumber(ch,num); /規(guī)約式子編號(hào)if(num = -1)cout success endl;cout * endl;cout endl;break;char left; /規(guī)約式子左部string right; /規(guī)約式子右部int tt = 0;for(i = 0;i lge.size();i +)for(j = 0;j lgei.right.size();j +)tt +;if(tt = num)left = lgei.left;right = lgei.rightj;str

21、ing temp1 = ;for(i = 0;i temp.length() - right.length();i +)temp1 += tempi;temp1 += left;temp = temp1;elsecout failure endl;cout * endl;cout endl;break;int equal(progect p1,progect p2)int i,j;if(p1.data.size() = p2.data.size()for(i = 0;i p1.data.size();i +)if(p1.datai.left = p2.datai.left)if(p1.data

22、i.right.size() = p2.datai.right.size()for(j = 0;j p1.datai.right.size();j +)if(p1.datai.rightj != p2.datai.rightj)return 0;elsereturn 0;elsereturn 0;elsereturn 0;return 1;int findpoint(string str)int i;for(i = 0;i str.length() - 1;i +)if(stri = .)return 1;return 0;int findlocal(string str)if(findpoint(str) /不在最后，不是規(guī)約項(xiàng)目string temp