《计算机理论导引实验报告2-上下文无关文法(CFG)》由会员分享，可在线阅读，更多相关《计算机理论导引实验报告2-上下文无关文法(CFG)（15页珍藏版）》请在金锄头文库上搜索。
1、 计算理论导引实验报告HUNAN UNIVERSITY计算理论导引实验报告题 目：上下文无关文法（CFG）学生姓名：学生学号：专业班级：计算机科学与技术2班上课老师：实验日期：2014-1-5目 录一、实验目的2二、实验内容2三、实验代码2四、测试数据以及运行结果9五、实验感想13一、实验目的1、掌握上下文无关文法概念。2、掌握用动态规划算法验证某个字符串w是否属于某上下文无关文法。二、实验内容对于任意给定的一个上下文无关文法，并对任意字符串w, 用动态规划算法判断是否有wL(G)。编写一个算法/程序，对于给定的输入，可以在多项式时间内判定ACFG。三、实验代码#include / 第一类规则
2、，即规则右边只含有两个变元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);/ 构造函数，参数指定输入字符
3、串的长度以及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
4、=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;this-num_v=num_v;value=new int*num_w;/ 给value动态分配，并将初值设为-1for(int i=0;inum_w;i+)valuei=new int*num_w;for(int j=0;jnum_w;j+)valueij=new intnum_
5、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+)couttableij:;for(k=0;kvalueijk=-1)break;elsecoutvalueijk ;coutendl;class CFGpublic:int num_v;int num_e;Regular_1* r1;Regular_2* r2;int star
6、t_v;bool Go(int *w);CFG();CFG();CFG:CFG()coutendl-CFG构造函数-endl;int num_r1,num_r2;int i,j,k;cout-endlnum_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=ne
7、w Regular_2num_r2+1;for(i=0;inum_r2;i+)cout第ir2i.leftr2i.right;r2i.left=-1;cout-endlstart_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-开始
8、运行-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开始从头到尾扫描，将某些变元放入对应的对角线上的表格
9、中：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_w-l+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_w-1,start_v)
