《消除文法左递归》由会员分享，可在线阅读，更多相关《消除文法左递归（6页珍藏版）》请在金锄头文库上搜索。
1、学号学号：专业专业：姓名姓名： 实验日期实验日期：2012.4.13教师签字教师签字：成绩成绩：实验名称实验名称：实验二：消除文法的左递归 实验目的：实验目的：. 掌握上下文无关文法类型的定义，及与其他类型文法的区别；.熟悉上下文无关文法类型的判断，能够快速按照要求写出对应文法类型的文法用例；.给出一个上下文无关文法类型，能够正确判断其是否存在左递归，若存在则消除直接、 间接左递归。实验原理：实验原理：1.文法中如果存在左递归，会产生循环递归，故需要将文法中的左递归给删除掉。 2.删除左递归需要删除直接左递归与间接左递归。 3.在删除左递归是，使用循环消元法，将左线性递归修改为又递归。 4.最
2、后删除无用产生式。实验内容：实验内容：.实验要求：输入任意的一个上下文无关文法,判断其是否存在左递归，若存在左递归则输出消除了 左递归的等价文法。.实验代码：#include #include #include #include #include using namespace std;struct relation string _left; string _right; ;/关系最大为 MAXN 条 vector rel; string VN;void print() coutr2._left) return true; else if(r1._left=r2._left return f
3、alse; relation get_realation(string str)/将一个字符串生成式分为左右部 输入格式为-，返回生成式结构体 int t=str.find(-); relation r; r._left=str.substr(0,t); r._right=str.substr(t+2,str.length()-t); return r; bool isUpper(char c) if(c=A for(int i=0;i find_Vn(char c) /查找左部为 c 的产生式 vector v; for(int i=0;i v1,v2,v3; relation r; for
4、(int i=0;ibr; if(is_exist(r) rel.push_back(r); void init() coutstrPath) rel.push_back(get_realation(strPath);/得到左部与右部; if(relrel.size()-1._left.length()=1)/得到左部的非终结符 char c=relrel.size()-1._left0; if(c=A) int t=VN.find(c); if(t=string:npos) VN+=c; vector find_1(char c) /查找 c 的直接左递归 vector v; for(int
5、 i=0;i find_2(char c)/查找 c 的非左递归 vector v; for(int i=0;i v1,v2; v1=find_1(c); relation r; string ch; ch.push_back(c); ch.push_back(.); bool p=false; / if(v1.size()=1) p=true; / if(p) v2=find_2(c); r._left=“; r._left.push_back(c); r._right=“; r._right.push_back(#); if(is_exist(r) rel.push_back(r); for (int q=0;q“reli._rightendl; print(); 3.实验结果：
