正规文法生成正规式

学号： 专业： 姓名： 实验日期：2012.4.27 教师签字： 成绩： 实验名称： 试验三：由正规文法构造正规式 实验目的： 掌握上下文无关文法类型的定义，及与其他类型文法的区别； ２.熟悉上下文无关文法类型的判断，能够快速按照要求写出对应文法类型的文法用例； ３.给出一个上下文无关文法类型，能够正确判断其是否存在左递归，若存在则消除直接、间接左递归。 实验原理： 1.对于任意一个正规文法G[S],都存在一个正规式与其等价，故可以使用RG构造RE。 2.对于RG(RE,可遵循以下三种规则。 1) r1(r2,r1(r3 → r1(r2|r3 2) r1(r2r3,r3(r4 → r1(r2r4 3) r1(r2r1,r1(r3 → r1(r2*r3 3.对于任意的RE， 实验： 1. 实验要求： 输入任意的正规文法,输出相应的正规式 。 2. 实验代码： #include #include #include #include #include #include using namespace std; struct relation{ string _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;iRE C++ 2012/4/27 COPYRIGHT FROM NINGYU ]"<>strPath){ rel.push_back(get_realation(strPath));//得到左部与右部; if(rel[rel.size()-1]._left.length()==1){ //得到左部的非终结符 char c=rel[rel.size()-1]._left[0]; if(c<='Z'&&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;i='A') v2.push_back(v4[i]); else v3.push_back(v4[i]); } /////////////////////////////////////////////////////// //将递归关系合并 relation r; r._left.push_back(c); for(int i=0;i sta1; for(int i=0;i='a'||s[i]=='|'){ sta1.push(s[i]); continue; } else if(s[i]==')'){ if(sta1.top()=='(') sta1.pop(); else sta1.push(s[i]); } else if(s[i]=='*'){ if(sta1.size()==0) continue; else if(sta1.top()=='*') continue; else sta1.push(s[i]); } } while(sta1.size()!=0){ str1+=sta1.top(); sta1.pop(); } reverse(str1.begin(),str1.end()); return str1; } int main(){ init(); string s=dfs('S'); cout<