计算机理论导引实验报告-上下文无关文法(cfg)

《计算机理论导引实验报告-上下文无关文法(cfg)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算理论导引实验报告HUNANUNIVERSITY计算理论导引实验报告题目：上下文无关文法（CFG）学生姓名：学生学号：专业班级：计算机科学与技术2班上课老师：实验日期：2014-1-514计算理论导引实验报告目录一、实验目的2二、实验内容2三、实验代码2四、测试数据以及运行结果9五、实验感想1314计算理论导引实验报告一、实验目的1、掌握上下文无关文法概念。2、掌握用动态规划算法验证某个字符串w是否属于某上下文无关文法。二、实验内容对于任意给定的一个上下文无关文法，并对任意字符串w,用动态规划算法判断是否有w∈L(G)。编写一个算法/程序，对于给定的输

2、入，可以在多项式时间内判定ACFG。三、实验代码#include//第一类规则，即规则右边只含有两个变元classRegular_1{public:intleft;intright_1;intright_2;};//第二类规则，即规则右边只含有一个终结符或者空classRegular_2{public:intleft;intright;};//表格类，用来存放中间数据classTable{public:intsize;//表格的行和列的数量，与输入长度相同intnum_v;//表格中每个单元格最多含有的数量大小，与cfg

3、的变元数量相同int***value;//用来存放数据的三元数组Table(intnum_v,intnum_w);//构造函数，参数指定输入字符串的长度以及cfg变元的数量~Table();//析构函数voidSetValue(inti,intj,intnum);//向表格第i行j列追加数据numboolCheckValue(inti,intj,intnum);//检查表格第i行j列是否含有数据num，含有则返回true，否则返回falsevoidPrint();//打印表格的内容14计算理论导引实验报告};Table::~Table(){if(valu

4、e)deletevalue;}voidTable::SetValue(inti,intj,intnum){int*p=value[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_

5、v=num_v;value=newint**[num_w];//给value动态分配，并将初值设为-1for(inti=0;i

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

7、e;Regular_1*r1;Regular_2*r2;intstart_v;boolGo(int*w);CFG();14计算理论导引实验报告~CFG();};CFG::CFG(){cout<>num_v;cout<<"终结符总数:";cin>>num_e;cout<<"----------------------"

8、<>num_r1;