LR-分析方法程序设计原理与实现技术实验报告及源代码-北京交通大学

1、LR 分析方法程序设计原理与实现技术XXX 1028XXX 计科1XXX班1. 程序功能描述通过设计、编写和构造LR（0）项目集规范簇和LR 分析表、对给定的符号串进行LR 分析的程序，了解构造LR（0）分析表的步骤，对文法的要求，能够从文法G 出发生成LR（0）分析表，并对给定的符号串进行分析。要求以表格或图形的方式实现。实现LR(0)分析法，完成以下文法。GE:EaAbBAcAdBcBd2. 设计要求（1）构造LR（0）项目集规范簇；要求输入LR(0)文法时，可以直接输入，也可以读取文件，并能够以表格的形式输出项目集规范簇集识别活前缀的有穷自动机（2）构造LR（0）分析表。要求要求输入LR

2、(0)文法时，可以直接输入，也可以读取文件；输出项目集规范簇，可以调用前一处理部分的结果，输出为LR(0)分析表（3）LR(0)分析过程【移进、归约、接受、报错】的实现。要求调用前一部分处理结果的分析表，输入一个符号串，依据LR（0）分析表输出与句子对应的语法树，或直接以表格形式输出分析过程。3. 主要数据结构描述：文法表示，项目集规范族表示以及文法接受的符号和移植到的位置：struct grammar /文法char left;vector right;struct grammar1char left;vector right;int sign;struct defineint data;c

3、har type;struct progect /项集vector data; /数据vector acc; /可接受的符号vector next; /转移到的位置;vector lge; /文法vector pro; /项目集规范族4. 程序结构描述本程序一共有10个功能函数：void get(); /获取文法void print(); /打印文法void fun(); /构造LR（0）项目集规范族void analy(); /构造LR（0）分析表void test(); /测试文法int equal(progect p1,progect p2); /判断两项是否相等int findpoin

4、t(string str); /判断点的位置是否在最后，是的话就是规约项目int findlocal(string str); /寻找此符号串对应的规范族的位置char gettype(char ch,int num); /根据状态集，返回操作的类别（移近，规约，接受）int getnumber(char ch,int nun); /根据状态机，返回下一步所跳转的状态集5. 实验代码 详见附件6. 程序测试6.1功能测试程序运行后显示如下功能菜单：选择获取文法：选择打印文法：选择构造LR（0）项目集规范族：选择构造LR（0）分析表：6.2文法测试分析失败:aAcAd分析成功:acd7. 实验总

5、结：本次实验按照书上的相应步骤，一步一步按照要求来完成实现，最终文成了给定文法的分析程序。首先是获取文法，文法的获取是采用直接输入的方法，保存成预先设定的结构体，然后根据文法，对文法编号，求出项目集规范族，然后再构造LR（0）分析表，最后根据分析表来判断输入符号串是否为此文法产生的语言。这次实验花费的时间比较长，因为用c语言在编写项目集族以及构造分析表的算法都遇到了一些困难,需要再实验中边写边学习。在完成实验后，我对LR（0）文法有了更加深入的了解。/ lr0.cpp : 定义控制台应用程序的入口点。/#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 /项目集vector data; /数据vector acc; /可接受的符号vector next; /转移到的位置;vector lge; /文法vector pro; /项目集规范族void get(); /获取文法void print(); /打印文法void fun(); /构造LR

7、（0）项目集规范族void analy(); /构造LR（0）分析表void test(); /测试文法int equal(progect p1,progect p2); /判断两项是否相等int findpoint(string str); /判断点的位置是否在最后，是的话就是规约项目int findlocal(string str); /寻找此符号串对应的规范族的位置char gettype(char ch,int num); /根据状态集，返回操作的类别（移近，规约，接受）int getnumber(char ch,int nun); /根据状态机，返回下一步所跳转的状态集int mai

8、n()int choose;while(1)cout * endl;cout 获取文法请按 1 endl;cout 打印文法请按 2 endl;cout 构造LR（0）项目集规范族请按 3 endl;cout 构造LR（0）分析表请按 4 endl;cout 文法测试请按 5 endl;cout 结束请按 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 +) /复制改变右部temp1 += tempq;temp1 += tempp + 1; /.右边第一个元素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) /非终结符，继续添加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);/判断是否已经存在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 /规约项目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 请输入有识别的字符串 str;cout endl;string temp = ;int i,j;int num = 0; /初始状态int count = 0; /字符串指针char ch = strcount;temp += strcount; /放入第一个符号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) /规约num = getnumber(ch,num); /规约式子编号if(num = -1)cout success endl;cout * endl;cout endl;break;char left; /规约式子左部string right; /规约式子右部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) /不在最后，不是规约项目string temp