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

HUNAN UNIVERSITY 计算理论导引 实验报告 题 目： CFG是P成员 学生姓名： 安佳玮 学生学号： 20090810101 专业班级： 计算机科学与技术1班 上课老师： 吴昊 实验日期： 2011-12-22 目 录 一、实验目的 2 二、实验方法 2 三、实验代码 2 四、测试数据以及运行结果 10 一、实验目的 上下文无关文法CFG G是否派生某个串W。采用动态规划（Dynamic Programming）设计一个多项式时间的验证算法 二、试验方法 编写一个算法/程序，对于给定的输入G,w，可以在多项式时间内判定ACFG。 三、实验代码 #include iostream.h // 第一类规则，即规则右边只含有两个变元 class Regular_1 { public: int left; int right_1; int right_2; }; // 第二类规则，即规则右边只含有一个终结符或者空 class Regular_2 { public: int left; int right; }; // 表格类，用来存放中间数据 class Table { public: 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列追加数据num bool CheckValue(int i,int j,int num); // 检查表格第i行j列是否含有数据num，含有则返回true，否则返回false void Print(); // 打印表格的内容 }; Table::~Table() { if(value) delete value; } void Table::SetValue(int i,int j,int num) { int *p=value[i][j]; // 寻找追加数据的位置 while((*p)!=-1) { p++; } *p=num; } bool Table::CheckValue(int i,int j,int num) { int *p=value[i][j]; 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动态分配，并将初值设为-1 for(int i=0;inum_w;i++) { value[i]=new int*[num_w]; for(int j=0;jnum_w;j++) { value[i][j]=new int[num_v]; for(int k=0;knum_v;k++) { value[i][j][k]=-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++) { couttable[i][j]:; for(k=0;knum_v;k++) { if(this-value[i][j][k]==-1) break; else coutthis-value[i][j][k] ; } coutendl; } } } class CFG { public: int num_v; int num_e; Regular_1* r1; Regular_2* r2; int start_v; bool Go(int *w); CFG(); ~CFG(); }; CFG: