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

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

3、t; right;int sign;struct defineint data;char type;struct progect /项集vector<grammar1> data; /数据vector<char> acc; /可接受的符号vector<define> next; /转移到的位置;vector<grammar> lge; /文法vector<progect> pro; /项目集规范族4. 程序结构描述本程序一共有10个功能函数：void get(); /获取文法void print(); /打印文法void fun();

4、 /构造LR（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); /根据状态机，返回下一步所跳转的状态集5

5、. 实验代码 详见附件6. 程序测试6.1功能测试程序运行后显示如下功能菜单：选择获取文法：选择打印文法：选择构造LR（0）项目集规范族：选择构造LR（0）分析表：6.2文法测试分析失败:aAcAd分析成功:acd7. 实验总结：本次实验按照书上的相应步骤，一步一步按照要求来完成实现，最终文成了给定文法的分析程序。首先是获取文法，文法的获取是采用直接输入的方法，保存成预先设定的结构体，然后根据文法，对文法编号，求出项目集规范族，然后再构造LR（0）分析表，最后根据分析表来判断输入符号串是否为此文法产生的语言。这次实验花费的时间比较长，因为用c语言在编写项目集族以及构造分析表的算法都遇到了一些困

6、难,需要再实验中边写边学习。在完成实验后，我对LR（0）文法有了更加深入的了解。/ lr0.cpp : 定义控制台应用程序的入口点。/#include "stdafx.h"#include <iostream>#include <string>#include <vector>using namespace std;struct grammar /文法char left;vector<string> right;struct grammar1char left;vector<string> right;int si

7、gn;struct defineint data;char type;struct progect /项目集vector<grammar1> data; /数据vector<char> acc; /可接受的符号vector<define> next; /转移到的位置;vector<grammar> lge; /文法vector<progect> pro; /项目集规范族void get(); /获取文法void print(); /打印文法void fun(); /构造LR（0）项目集规范族void analy(); /构造LR（0）

8、分析表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 main()int choose;while(1)cout <

9、< "*" << endl;cout << " 获取文法请按 1" << endl;cout << " 打印文法请按 2" << endl;cout << " 构造LR（0）项目集规范族请按 3" << endl;cout << " 构造LR（0）分析表请按 4" << endl;cout << " 文法测试请按 5" << endl;co

10、ut << " 结束请按 0" << endl;cout << "*" << endl;cout << endl;cin >> choose;if(choose = 0)break;switch(choose)case 1: get(); break;case 2: print(); break;case 3: fun(); break;case 4: analy(); break;case 5: test(); break;default:break;return 0;void g

11、et()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.p

12、ush_back("d");lge.push_back(temp);lge.push_back(temp1);lge.push_back(temp2);cout << "*" << endl;cout << " 文法获取完成" << endl;cout << "*" << endl;cout << endl;void print()cout << "*" << endl;for(int i

13、 = 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.right.push_back(

14、".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 <= 'Z' && ch >= 'A' && pro0.datai.sign = 0)

15、 /需要迭代pro0.datai.sign = 1;sign = 1;for(int k = 0;k < lge.size();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;

16、for(int i = 0;i < pro.size();i +)for(int j = 0;j < proi.data.size();j +)for(int k = 0;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 = p

17、roi.dataj.left;gg.sign = 0;string temp1 = ""for(int q = 0;q < p;q +) /复制改变右部temp1 += tempq;temp1 += tempp + 1; /.右边第一个元素temp1 += "."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 != '.'&&

18、amp; p < temp1.length()p +;if(p < temp1.length() - 1)if(temp1p + 1 >= '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 = 0;n < lgem.right.size();n +)gg1.r

19、ight.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 +

20、) /打印cout << "I" << i << ":" << endl;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

21、<< "*" << 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 < proi.dataj.right.size();k +)string temp = proi.dataj.rightk;if(findpoint(temp) /移近项目int t = 0;while(tempt != '.')t +;t +;proi

22、.acc.push_back(tempt); /添加可接受符号define d;if(tempt > 'Z' | tempt < 'A')d.data = findlocal(temp);d.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.pus

23、h_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 +)cout << tempi << " "cout << endl;for(int i

24、 = 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)co

25、ut << proi.nextj.type << proi.nextj.data << " "sign = 1;if(sign = 0)cout << " "cout << endl;cout << "*" << endl;cout << endl;void test()cout << "*" << endl;cout << "请输入有识别的字符串" <<

26、; endl;string str;cin >> 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

27、= 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

28、= 0;j < lgei.right.size();j +)tt +;if(tt = num)left = lgei.left;right = lgei.rightj;string temp1 = ""for(i = 0;i < temp.length() - right.length();i +)temp1 += tempi;temp1 += left;temp = temp1;elsecout << "failure" << endl;cout << "*" << end

29、l;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.datai.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