学号:
专业:
姓名:
实验日期:2012.4.27
教师签字:
成绩:
实验名称:
试验三:由正规文法构造正规式
实验目的:
掌握上下文无关文法类型的定义,及与其他类型文法的区别;
2.熟悉上下文无关文法类型的判断,能够快速按照要求写出对应文法类型的文法用例;
3.给出一个上下文无关文法类型,能够正确判断其是否存在左递归,若存在则消除直接、间接左递归。
实验原理:
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<
本文档为【正规文法生成正规式】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。