正規(guī)文法生成正規(guī)式.doc

學號：專業(yè)：姓名： 實驗日期：2012.4.27教師簽字：成績：實驗名稱：試驗三：由正規(guī)文法構(gòu)造正規(guī)式實驗?zāi)康模赫莆丈舷挛臒o關(guān)文法類型的定義，及與其他類型文法的區(qū)別；.熟悉上下文無關(guān)文法類型的判斷，能夠快速按照要求寫出對應(yīng)文法類型的文法用例；.給出一個上下文無關(guān)文法類型，能夠正確判斷其是否存在左遞歸，若存在則消除直接、間接左遞歸。實驗原理：1.對于任意一個正規(guī)文法GS,都存在一個正規(guī)式與其等價，故可以使用RG構(gòu)造RE。2.對于RGRE,可遵循以下三種規(guī)則。1) r1r2,r1r3 r1r2|r32) r1r2r3,r3r4 r1r2r43) r1r2r1,r1r3 r1r2*r33.對于任意的RE，實驗內(nèi)容：. 實驗要求：輸入任意的正規(guī)文法,輸出相應(yīng)的正規(guī)式。. 實驗代碼：#include #include #include #include #include #include using namespace std;struct relationstring _left,_right;vector rel;string VN;relation get_realation(string str)/將一個字符串生成式分為左右部 輸入格式為-，返回生成式結(jié)構(gòu)體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的產(chǎn)生式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)/得到左部的非終結(jié)符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的關(guān)系，v2是左部為c但是右部Vn不為c的關(guān)系，v3是左部為c，右部為re的關(guān)系v4=find_Vn(c);/按照右部vn的關(guān)系分類;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);/將遞歸關(guān)系合并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的關(guān)系右部合并;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(