正规文法生成正规式
- 格式：doc
- 大小：88.00 KB
- 文档页数：10
学号：专业：姓名：
实验日期：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，
实验内容：
１.实验要求：
输入任意的正规文法,输出相应的正规式。
２.实验代码：
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
using namespace std;
struct relation{
string _left,_right;
};
vector<relation> 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<relation> find_Vn(char c){ //查找左部为c的产生式
vector<relation> v;
for(int i=0;i<rel.size();i++)
if(rel[i]._left[0]==c){
v.push_back(rel[i]);
}
return v;
}
void print(){
cout<<"[ RG->RE C++ 2012/4/27 COPYRIGHT FROM NINGYU ]"<<endl;
}
void init(){
/*
string strPath="d:/a.txt";
ifstream fin(strPath);*/
print();
cout<<"input the RG ,End with Ctrl+Z (note:begin with S)"<<endl; string strPath;
relation r;
int p;
while(cin>>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<relation> v1,v2,v3,v4;//v1是左部为c右部为c的关系，v2是左部为c但是右部Vn不为c的关系，v3是左部为c，右部为re 的关系
v4=find_Vn(c);
///////////////////////////////////////////////////////
//////按照右部vn的关系分类;
for(int i=0;i<v4.size();i++){
char t=v4[i]._right[v4[i]._right.length()-1];
if(t==c)
v1.push_back(v4[i]);
else if(t<='Z'&&t>='A')
v2.push_back(v4[i]);
else v3.push_back(v4[i]);
}
///////////////////////////////////////////////////////
//将递归关系合并
relation r;
r._left.push_back(c);
for(int i=0;i<v2.size();i++){
char t=v2[i]._right[v2[i]._right.length()-1];
string s=v2[i]._right.substr(0,v2[i]._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;i<v3.size();i++){
if(flag)
r1._right+='|';
else flag=1;
r1._right+=v3[i]._right;
}
r1._right.push_back(')');
////////////////////////////////////////////////////////////////
//生成r*项目
relation r2;
r2._left.push_back(c);
r2._right.push_back('(');
for(int i=0,flag=0;i<v1.size();i++){
if(flag) r2._right.push_back('|');
else flag=1;
r2._right+=v1[i]._right.substr(0,v1[i]._right.length()-1); }
r2._right.push_back(')');
r1._right='('+r2._right+')'+'*'+r1._right;
//////////////////////////////////////////////////////////////
//输出r1观察
//cout<<r1._right<<endl;
return r1._right;
}
string regular(string s){ //去除无用括号，去除无用# string str1;
stack<char> sta1;
for(int i=0;i<s.length();i++){
if(s[i]=='('||s[i]<='z'&&s[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<<endl
<<"The RE is:"
<<regular(s)<<endl;
print();
return 0;
}
３.实验结果：。
