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

《计算机理论导引实验报告_CFG是P成员.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、HUNANUNIVERSITY计算理论导引实验报告题目：CFG是P成员学生姓名：安佳玮学生学号：20090810101专业班级：计算机科学与技术1班上课老师：吴昊实验日期：2011-12-22目录一、实验目的2二、实验方法2三、实验代码2四、测试数据以及运行结果10一、实验目的上下文无关文法CFGG是否派生某个串W。采用动态规划（DynamicProgramming）设计一个多项式时间的验证算法二、试验方法编写一个算法/程序，对于给定的输入，可以在多项式时间内判定ACFG。三、实验代码#include//第一类规则，

2、即规则右边只含有两个变元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

3、);//构造函数，参数指定输入字符串的长度以及cfg变元的数量~Table();//析构函数voidSetValue(inti,intj,intnum);//向表格第i行j列追加数据numboolCheckValue(inti,intj,intnum);//检查表格第i行j列是否含有数据num，含有则返回true，否则返回falsevoidPrint();//打印表格的内容};Table::~Table(){if(value)deletevalue;}voidTable::SetValue(inti,intj,intnum){int*p=value[

4、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动态分配，并将初值设为-1for(inti=0;i

5、

6、(i=0;ivalue[i][j][k]==-1)break;elsecout<value[i][j][k]<<"";}cout<

7、::CFG(){cout<>num_v;cout<<"终结符总数:";cin>>num_e;cout<<"----------------------"<>num_r1;r1=newRegular_1[num_r1+1];cout<<"--------

8、--------------"<