正规文法生成正规式.doc

学号：专业：姓名： 实验日期：2012.4.27教师签字：成绩：实验名称：试验三：由正规文法构造正规式实验目的：掌握上下文无关文法类型的定义，及与其他类型文法的区别；.熟悉上下文无关文法类型的判断，能够快速按照要求写出对应文法类型的文法用例；.给出一个上下文无关文法类型，能够正确判断其是否存在左递归，若存在则消除直接、间接左递归。实验原理：1.对于任意一个正规文法GS,都存在一个正规式与其等价，故可以使用RG构造RE。2.对于RGRE,可遵循以下三种规则。1) r1r2,r1r3 r1r2|r32) r1r2r3,r3r4 r1r2r43) r1r2r1,r1r3 r1r2*r33.对于任意的RE，实验内容：. 实验要求：输入任意的正规文法,输出相应的正规式。. 实验代码：#include #include #include #include #include #include using namespace std;struct relationstring _left,_right;vector rel;string VN;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;vector find_Vn(char c)/查找左部为c的产生式vector v;for(int i=0;irel.size();i+)if(reli._left0=c)v.push_back(reli);return v;void print()coutRE C+ 2012/4/27 COPYRIGHT FROM NINGYU endl;void init()/*string strPath=d:/a.txt;ifstream fin(strPath);*/print();coutinput the RG ,End with Ctrl+Z (note:begin with S)strPath)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;string dfs(char c)bool flag;vector v1,v2,v3,v4;/v1是左部为c右部为c的关系，v2是左部为c但是右部Vn不为c的关系，v3是左部为c，右部为re的关系v4=find_Vn(c);/按照右部vn的关系分类;for(int i=0;iv4.size();i+)char t=v4i._rightv4i._right.length()-1;if(t=c)v1.push_back(v4i);else if(t=A)v2.push_back(v4i);else v3.push_back(v4i);/将递归关系合并relation r;r._left.push_back(c);for(int i=0;iv2.size();i+)char t=v2i._rightv2i._right.length()-1;string s=v2i._right.substr(0,v2i._right.length()-1);s+=dfs(t);r._right=s;v3.push_back(r);/将re的关系右部合并;relation r1;r1._left.push_back(c);r1._right.push_back();flag=0;for(int i=0;iv3.size();i+)if(flag)r1._right+=|;else flag=1;r1._right+=v3i._right;r1._right.push_back();/生成r*项目relation r2;r2._left.push_back(c);r2._right.push_back();for(int i=0,flag=0;iv1.size();i+)if(flag) r2._right.push_back(|);else flag=1;r2._right+=v1i._right.substr(0,v1i._right.length()-1);r2._right.push_back();r1._right=(+r2._right+)+*+r1._right;/输出r1观察/coutr1._rightendl;return r1._right;string regular(string s)/去除无用括号，去除无用#string str1;stack sta1;for(int i=0;is.length();i+)if(si=(|si=a|si=|)sta1.push(si);continue;else if(si=)if(sta1.top()=()sta1.pop();else sta1.push(si);else if(si=*)if(sta1.size()=0)continue;else if(sta1.top()=*)continue;else sta1.push(si);while(sta1.size()!=0)str1+=sta1.top();sta1.pop();reverse(