计算机理论导引实验报告CFG是P成员.doc

个人收集整理 勿做商业用途HUNAN UNIVERSITY计算理论导引实验报告题 目：CFG是P成员学生姓名：安佳玮学生学号：20090810101专业班级:计算机科学与技术1班上课老师:吴昊实验日期:2011-12-22目 录一、实验目的2二、实验方法2三、实验代码2四、测试数据以及运行结果10一、实验目的上下文无关文法CFG G是否派生某个串W。采用动态规划（Dynamic Programming）设计一个多项式时间的验证算法二、试验方法编写一个算法/程序，对于给定的输入G，w，可以在多项式时间内判定ACFG。三、实验代码include / 第一类规则，即规则右边只含有两个变元class Regular_1public：int left；int right_1;int right_2;；/ 第二类规则，即规则右边只含有一个终结符或者空class Regular_2public:int left;int right；;/ 表格类,用来存放中间数据class Tablepublic:int size；/ 表格的行和列的数量,与输入长度相同int num_v；/ 表格中每个单元格最多含有的数量大小，与cfg的变元数量相同int value;/ 用来存放数据的三元数组Table(int num_v,int num_w);/ 构造函数，参数指定输入字符串的长度以及cfg变元的数量Table(）；/ 析构函数void SetValue(int i,int j,int num）；/ 向表格第i行j列追加数据numbool CheckValue（int i,int j,int num)；/ 检查表格第i行j列是否含有数据num，含有则返回true，否则返回falsevoid Print（)；/ 打印表格的内容；Table：Table()if(value)delete value;void Table:SetValue（int i,int j,int num)int *p=valueij；/ 寻找追加数据的位置while(（*p）!=1）p+;p=num；bool Table：:CheckValue(int i，int j,int num)int *p=valueij;while（*p)!=1)if（(*p)=num)return true；p+;return false;Table：:Table（int num_v,int num_w)size=num_w;thisnum_v=num_v；value=new intnum_w；/ 给value动态分配，并将初值设为1for(int i=0；inum_w;i+）valuei=new int*num_w；for（int j=0；jnum_w；j+)valueij=new intnum_v;for(int k=0；knum_v；k+）valueijk=1；void Table：:Print（）int i，j,k；cout-打印表格内容-endl；if（size=0)cout”表格为空”endl；return；cout”表格内容如下：endl；for（i=0；isize；i+)for(j=0；jsize；j+）cout”table”i”jvalueijk=1）break；elsecoutthis-valueijk ”;coutendl；class CFGpublic：int num_v;int num_e;Regular_1 r1;Regular_2* r2;int start_v;bool Go（int w）;CFG（);CFG()；;CFG：:CFG（）coutendl”-CFG构造函数-”endl；int num_r1，num_r2;int i，j,k;cout”-num_v;coutnum_e；cout”-endlnum_r1；r1=new Regular_1num_r1+1;cout-endl；cout”在下面的输入中注意：变元编号以及终结符编号从0开始endl；cout-endl;for（i=0;inum_r1;i+）cout”第”ir1i。leftr1i.right_1r1i。right_2；r1i。left=-1;cout”-endlnum_r2;r2=new Regular_2num_r2+1；for(i=0;inum_r2;i+)cout第”ir2i。leftr2i.right；r2i。left=-1;cout-”endl”起始变元的编号为：；cinstart_v；CFG：CFG()if（r1）delete r1;if(r2)delete r2；bool CFG：:Go(int w）bool result=false；Regular_1 *p1=r1；Regular_2 *p2=r2;int len_w=0;int p=w;/ 获取输入长度while（p!=1)len_w+；p+；p=w;Table t(num_v,len_w）；int i，j，k,l；cout-开始运行-”endl；if(w0=1）cout”-”endl;cout检查发现输入为空.endl;while(p2)。left!=-1）if(p2）。left=start_v&（*p2).right=-1)cout”检查到起始变元到空的规则.endl；cout运行完毕！结果为:接受!endl;cout-”endl;result=true；return result;p2+；cout未发现从起始变元到空的派生。”endl;cout运行完毕，结果为：拒绝”endl;cout”-endl;return false;p2=r2；i=0；cout”-endl；cout开始从头到尾扫描，将某些变元放入对应的对角线上的表格中：”endl；while（p！=1）while（(*p2)。left！=1）if（(*p2)。right=p)cout”由于变元”(*p2).left”派生”终结符”p”，故将其放入表格的i行i”列”endl;t。SetValue（i,i，（p2）.left）;p2+;p2=r2；p+;i+；p=w;cout-”endl；cout开始依次向表格的某些单元格添加数据.。.endl；for（l=2;l=len_w；l+)for(i=0;ilen_wl+1；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）)couttable（”i,k”)中含有变元”（p1）.right_1”而且table（”k+1,j”)中含有”（p1).right_2;cout,因此将变元”(p1）.left”放入table（i,”j）中endl；t.SetValue(i，j，(p1）。left);p1+；p1=r1;t.Print(）;if(t.CheckValue（1，len_w1,start_v)）cout”起始变元start_v在talbe(0，”len_w1”)中endl；cout”运行完毕!结果为：接受！endl;cout-”endl；return true;elsecout起始变元”start_v”在不在talbe(0,len_w-1)中”endl；cout”运行完毕！结果为:拒绝！endl;cout-endl;return false；main（)cout”-CFG是P成员判定程序-”endl;CFG c;while（true）int w；int len_w;cout”-endllen_w;w=new intlen_w+1；if（len_w=0)cout”-endl;elsecoutwi；wi=1；c。Go(w);coutc；if(c=N）return;改程序在VC+下可以通过编译，并且运行结果正确四、测试数据以及运行结果以教材习题上面的一个CFG为例.该CFG描述如下：SRTR-TRaTTRb在该CFG下面测试输入w1=baba和w2=ababb测试结果如下：14