正规文法-正规式.doc

该【正规文法-正规式 】是由【文艺人生】上传分享，文档一共【20】页，该文档可以免费在线阅读，需要了解更多关于【正规文法-正规式 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。正规文法-正规式
由正规文法构造正规式
年级_______
专业________
学号________
姓名__________
{
stringleft;//规则左部,因为输入的为2型文法,
stringright;//规则右部
};
structRuleData
{
stringleft;
vector<string>right;
};
classGrammar
{
private:
vector<Rule>grammar;//文法
Rulerule;//规则
vector<string>Dleft;
RuleDataruledata;
public:
Grammar(){}
~Grammar(){}
voidChangeInput(stringinput);//输入分析
voidShow();//
voidDataChange(intC);//存储结构转换
vector<RuleData>grammardata;
};
voidGrammar::ChangeInput(stringinput)//扫描字符串,遇到'-'停止,
{//并跳两格
inthelp1=0;
();
();
for(inti=0;i<int(());i++)
{
if(input[i]=='-')
{
help1=i;
break;
}
+=input[i];
}
if(help1!=1)
{
cout<<"不符合要求!!";
exit(0);
}
help1=help1+2;
for(intj=help1;j<int(());j++)
{
+=input[j];
}
(rule);
}
voidGrammar::DataChange(intC)
{
inti,j;
if(C==0)//简单->复杂
{
intl=0;
();
();
();
=grammar[0].left;
(grammar[0].right);
(ruledata);
for(i=1;i<int(());i++)//存储转换
{
for(j=0;j<int(());j++)
{
if(grammar[i].left==grammardata[j].left)
{
grammardata[j].(grammar[i].right);
l=1;
break;
}
}
if(l==0)
{
();
();
=grammar[i].left;
(grammar[i].right);
(ruledata);
}
l=0;
}
}
if(C==1)//复杂->简单
{
();
for(i=0;i<int(());i++)
{
();
();
=grammardata[i].left;
for(j=0;j<int(grammardata[i].());j++)
{
=grammardata[i].(j);
(rule);
}
}
}
}
voidGrammar::Show()
{
cout<<"输入的文法的正规式为:"<<endl;
for(inti=0;i<int(());i++)
cout<<grammar[i].left<<"="<<grammar[i].right<<endl;
}
classGenerateGtoE:publicGrammar//正规文法转正规式
{
private:
public:
GenerateGtoE(){}
~GenerateGtoE(){}
voidGenerating();
};
voidGenerateGtoE::Generating()
{
DataChange(0);
//STEP1
//将文法G的所有非终结符形如a1A|a2A|...的候选式
//归并为(a1|a2|...)A的侯选式,其中a∈Vt,A∈Vn
stringZ1="|";
stringZ2="(";
stringZ3=")";
stringZ4="*";