计算机理论导引实验报告2上下文无关文法CFG.docx
- 文档编号:16420134
- 上传时间:2023-07-13
- 格式:DOCX
- 页数:18
- 大小:180.14KB
计算机理论导引实验报告2上下文无关文法CFG.docx
《计算机理论导引实验报告2上下文无关文法CFG.docx》由会员分享,可在线阅读,更多相关《计算机理论导引实验报告2上下文无关文法CFG.docx(18页珍藏版)》请在冰点文库上搜索。
计算机理论导引实验报告2上下文无关文法CFG
HUNANUNIVERSITY
计算理论导引
实验报告
题目:
上下文无关文法(CFG)
学生姓名:
学生学号:
专业班级:
计算机科学与技术2班
上课老师:
实验日期:
2014-1-5
目录
一、实验目的2
二、实验内容2
三、实验代码2
四、测试数据以及运行结果9
五、实验感想13
一、实验目的
1、掌握上下文无关文法概念。
2、掌握用动态规划算法验证某个字符串w是否属于某上下文无关文法。
二、实验内容
对于任意给定的一个上下文无关文法,并对任意字符串w,用动态规划算法判断是否有w∈L(G)。
编写一个算法/程序,对于给定的输入
三、实验代码
#include
//第一类规则,即规则右边只含有两个变元
classRegular_1
{
public:
intleft;
intright_1;
intright_2;
};
//第二类规则,即规则右边只含有一个终结符或者空
classRegular_2
{
public:
intleft;
intright;
};
//表格类,用来存放中间数据
classTable
{
public:
intsize;//表格的行和列的数量,与输入长度相同
intnum_v;//表格中每个单元格最多含有的数量大小,与cfg的变元数量相同
int***value;//用来存放数据的三元数组
Table(intnum_v,intnum_w);//构造函数,参数指定输入字符串的长度以及cfg变元的数量
~Table();//析构函数
voidSetValue(inti,intj,intnum);//向表格第i行j列追加数据num
boolCheckValue(inti,intj,intnum);//检查表格第i行j列是否含有数据num,含有则返回true,否则返回false
voidPrint();//打印表格的内容
};
Table:
:
~Table()
{
if(value)
deletevalue;
}
voidTable:
:
SetValue(inti,intj,intnum)
{
int*p=value[i][j];
//寻找追加数据的位置
while((*p)!
=-1)
{
p++;
}
*p=num;
}
boolTable:
:
CheckValue(inti,intj,intnum)
{
int*p=value[i][j];
while((*p)!
=-1)
{
if((*p)==num)
returntrue;
p++;
}
returnfalse;
}
Table:
:
Table(intnum_v,intnum_w)
{
size=num_w;
this->num_v=num_v;
value=newint**[num_w];
//给value动态分配,并将初值设为-1
for(inti=0;i { value[i]=newint*[num_w]; for(intj=0;j { value[i][j]=newint[num_v]; for(intk=0;k { value[i][j][k]=-1; } } } } voidTable: : Print() { inti,j,k; cout<<"---------------打印表格内容------------------"< if(size==0) { cout<<"表格为空"< return; } cout<<"表格内容如下: "< for(i=0;i { for(j=0;j { cout<<"table["< "; for(k=0;k { if(this->value[i][j][k]==-1) break; else cout< } cout< } } } classCFG { public: intnum_v; intnum_e; Regular_1*r1; Regular_2*r2; intstart_v; boolGo(int*w); CFG(); ~CFG(); }; CFG: : CFG() { cout< intnum_r1,num_r2; inti,j,k; cout<<"----------------------"< "; cin>>num_v; cout<<"终结符总数: "; cin>>num_e; cout<<"----------------------"< "; cin>>num_r1; r1=newRegular_1[num_r1+1]; cout<<"----------------------"< cout<<"在下面的输入中注意: 变元编号以及终结符编号从0开始"< cout<<"----------------------"< for(i=0;i { cout<<"第"< "; cin>>r1[i].left>>r1[i].right_1>>r1[i].right_2; } r1[i].left=-1; cout<<"----------------------"< "; cin>>num_r2; r2=newRegular_2[num_r2+1]; for(i=0;i { cout<<"第"< "; cin>>r2[i].left>>r2[i].right; } r2[i].left=-1; cout<<"----------------------"< "; cin>>start_v; } CFG: : ~CFG() { if(r1) deleter1; if(r2) deleter2; } boolCFG: : Go(int*w) { boolresult=false; Regular_1*p1=r1; Regular_2*p2=r2; intlen_w=0; int*p=w; //获取输入长度 while(*p! =-1) { len_w++; p++; } p=w; Tablet(num_v,len_w); inti,j,k,l; cout<<"-----------开始运行-----------"< if(w[0]==-1) { cout<<"-------------------------------"< cout<<"检查发现输入为空..."< while((*p2).left! =-1) { if((*p2).left==start_v&&(*p2).right==-1) { cout<<"检查到起始变元到空的规则..."< cout<<"运行完毕! 结果为: 接受! "< cout<<"----------------------"< result=true; returnresult; } p2++; } cout<<"未发现从起始变元到空的派生。 "< cout<<"运行完毕,结果为: 拒绝"< cout<<"----------------------"< returnfalse; } p2=r2; i=0; cout<<"-------------------------------"< cout<<"开始从头到尾扫描,将某些变元放入对应的对角线上的表格中: "< while(*p! =-1) { while((*p2).left! =-1) { if((*p2).right==*p) { cout<<"由于变元"<<(*p2).left<<"派生"<<"终结符"<<*p<<",故将其放入表格的"< t.SetValue(i,i,(*p2).left); } p2++; } p2=r2; p++; i++; } p=w; cout<<"-------------------------------"< cout<<"开始依次向表格的某些单元格添加数据..."< for(l=2;l<=len_w;l++) { for(i=0;i { j=i+l-1; for(k=i;k<=j-1;k++) { while((*p1).left! =-1) { if(t.CheckValue(i,k,(*p1).right_1)&&t.CheckValue(k+1,j,(*p1).right_2)) { cout<<"table("< cout<<",因此将变元"<<(*p1).left<<"放入table("< t.SetValue(i,j,(*p1).left); } p1++; } p1=r1; } } } t.Print(); if(t.CheckValue(1,len_w-1,start_v)) { cout<<"起始变元"< cout<<"运行完毕! 结果为: 接受! "< cout<<"----------------------"< returntrue; } else{ cout<<"起始变元"< cout<<"运行完毕! 结果为: 拒绝! "< cout<<"----------------------"< returnfalse; } } main() { cout<<"------------CFG是P成员判定程序----------"< CFGc; while(true) { int*w; intlen_w; cout<<"----------------------"< "; cin>>len_w; w=newint[len_w+1]; if(len_w==0) cout<<"----------------------"< else cout<<"依次输入w的内容的编号(以空格隔开): "; for(inti=0;i { cin>>w[i]; } w[i]=-1; c.Go(w); cout<<"验证其它字符串? (Y/N)"; charc; cin>>c; if(c=='N') return; } } 四、测试数据以及运行结果 CFG描述如下: S->RT R->TR|a T->TR|b 在该CFG下面测试输入w1=baba和w2=ababb测试结果如下: 五、实验感想 拿到这个题首先有些无从下手,感觉任务挺艰巨的。 要想编写出这个程序,首先就要对课本的理论知识有清晰深刻的理解,其次在过程中要注意各种算法的运用。 判定某个字符串是否属于上下文无关文法,判断CFG是否派生某个串可以采用递归 的思想,这一点很容易想到,因为上下无关文法的生成就是通过递归完成的。 但是递归的效率有时候很低下,这里采用动态规划的算法对递归进行优化处理,将每一个已经生成的子串填在表里,下一次用到的时候查表得到,省去重复计算的部分。 在推导过程中采取从结果反推原因的顺序,从输入串推到起始变元。 这种从大化小的顺序也与递归中将问题逐步分解最终到某个出口一致。 1)创建一个二维数字,用于动态规划过程中填表。 根据乔姆斯基范式的特点,推出字符串中的每个字符的直接产生变元,并将其填写在表的对角线table[i][i]上。 2)考虑长度为2到n的子串,对每一条规则A->BC,若table[i][k]包含B并且table[k+1][j]包含C,则把A放入table[i][j]。 这样记录表将按照斜线的顺序逐步填完。 3)将所有子串运行完毕后,右上角table[0][n]若包含起始变元,则证明该CFG可以派生出该串。 最终通过程序实现,加深了对上下文无关文法的理解,巩固了课堂知识,也提高了编程能力。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 理论 导引 实验 报告 上下文 无关 文法 CFG