正规文法构造正规式(安徽大学编译原理实验报告)

《正规文法构造正规式(安徽大学编译原理实验报告)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、由正规文法构造正规式【实验冃的】输入：任意的正规文法。输出：相应的正规式。【实验原理】3型文法（止则文法，线性文法）如果对于某文法G,P中的每个规则具冇下列形式：U::=T或U::=WT其屮TEVT；U,WeVN,则称该文法G为左线性文法。如果对于某文法G,P中的每个规则具有下列形式：U::=T或U::二TW其屮TWVT；U,WEVN,则称该文法G为右线性文法。左线性文法和右线性文法通称为3型文法或正则文法，有时乂称为有穷状态文法，简写为RGo按照定义，对于正则文法应用规则吋，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个

2、终结符号加上单个非终结符号。3型文法所确定的语言为3型语言L3,3型语言可由确定的有限状态自动机来识别。【程序代码】#include#include#include#include#include#includeusingnamespacestd;structrelation!string_left,_Tight;};vectorrel;stringVN;relationget_realation(stringstr){intt=str.find('

3、-^);relationr;匚」eft=st匚substr(O,t);r>_right=str.substr(t+2,str.length()-t);returnr;}vectorfind_Vn(charc){vectorv;for(inti=();iREC++2012/4/27COPYRIGHTFROMNINGYU]n«endl;}voidinit(){

4、print();cout«"inputtheRG,EndwithCtrl+Z(note:beginwithS)n«endl;stringstrPath;relationr;intp;while(cin»strPath){rel.push_back(get_realation(strPath));if(rel[rel.size()-1]._left.length()==1){charc=rel[rel.size()-l]._left[O];if(c<=*Z&&c>=A){intt=VN.find(c);if(t==string::npos)VN+=c;}}}}stringdf

5、s(charc){boolflag;vectorvl,v2,v3,v4;v4=find_Vn(c);for(inti=0;i=A)v2.push_back(v4[i]);elsev3.push_back(v4[i]);}relationr;r._left.push_back(c);for(inti=0;ivv2.size();i++){chart=

6、v2[i]._right[v2[i]._right.length()-l];strings=v2[i]._right.substr(0,v2[i]._right.length()-l);s+=dfs(t);匚_right=s;v3.push_back(r);}relationrl;rl.Jeft.push_back(c);r1._right.push_back(V)；flag=0;for(inti=0;ivv3.size();i++){if(flag)rl._right+=T;elseflag=l;rl._right+=v3[i]—right;}rl._right.push

7、_back(,)1);relationr2;r2._left.push_back(c);r2._right.push_back(,(，)；for(inti=0,flag=0;i