《计算机理论导引实验报告_cfg是p成员》由会员分享，可在线阅读，更多相关《计算机理论导引实验报告_cfg是p成员（15页珍藏版）》请在金锄头文库上搜索。
1、HUNAN UNIVERSITY计算理论导引实验报告题 目： CFG 是 P 成员学 生 姓 名 ： 安佳玮学 生 学 号 ： 20090810101专 业 班 级 ： 计算机科学与技术 1 班上 课 老 师 ： 吴昊实 验 日 期 ： 2011-12-22 计 算 理 论 导 引 实 验 报 告1目 录一、实验目的.2二、实验方法.2三、实验代码.2四、测试数据以及运行结果.10 计 算 理 论 导 引 实 验 报 告2一、实验目的上下文无关文法 CFG G 是否派生某个串 W。采用动态规划（Dynamic Programming）设计一个多项式时间的验证算法二、试验方法编写一个算法/程序，
2、对于给定的输入，可以在多项式时间内判定 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; / 用
3、来存放数据的三元数组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(); / 打印表格的内容; 计 算 理 论 导 引 实 验 报 告3Table:Table()if(value)delete
4、 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;this-num_v=num_v;value=new int*num_w;/ 给 value 动态分
5、配，并将初值设为 -1for(int i=0;ivalueijk=-1)break;elsecoutvalueijknum_v;coutnum_e;coutnum_r1;r1=new Regular_1num_r1+1;coutr1i.leftr1i.right_1r1i.right_2;r1i.left=-1;coutnum_r2;r2=new Regular_2num_r2+1;for(i=0;ir2i.leftr2i.right;r2i.left=-1;coutstart_v;CFG:CFG() 计 算 理 论 导 引 实 验 报 告6if(r1)delete r1;if(r2)dele
6、te 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;coutlen_w;w=new intlen_w+1;if(len_w=0)coutwi; 计 算 理 论 导 引 实 验 报 告9wi=-1;c.Go(w);coutc;if(c=N)return;改程序在 VC+下可以通过编译，并且运行结果正确 计 算 理 论 导 引 实 验 报 告10四、测试数据以及运行结果以教材习题上面的一个 CFG 为例。该 CFG 描述如下：S-RTR-TR|aT-TR|b在该 CFG 下面测试输入 w1=baba 和 w2=ababb 测试结果如下： 计 算 理 论 导 引 实 验 报 告11 计 算 理 论 导 引 实 验 报 告12 计 算 理 论 导 引 实 验 报 告13 计 算 理 论 导 引 实 验 报 告14
