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

个人收集整理 勿做商业用途

HUNAN UNIVERSITY

计算理论导引
实验报告

题 目：
CFG是P成员

学生姓名：
安佳玮

学生学号：
20090810101

专业班级:
计算机科学与技术1班

上课老师:
吴昊

实验日期:
2011-12-22
目 录
一、实验目的 2
二、实验方法 2
三、实验代码 2
四、测试数据以及运行结果 10
一、实验目的
上下文无关文法CFG G是否派生某个串W。采用动态规划（Dynamic Programming）设计一个多项式时间的验证算法
二、试验方法
编写一个算法/程序，对于给定的输入
// 第一类规则，即规则右边只含有两个变元
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；i〈num_w;i++）
｛
value[i］=new int*[num_w]；
for（int j=0；j return；
}
cout〈〈”表格内容如下："〈value[i］［j]［k］==—1）
break；
else
cout<〈this-〉value[i][j]［k]<〈" ”;
｝
cout<〈endl；
｝
}

｝
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：:CFG（）
{
cout<>numv;

cout<〈"终结符总数：”;
cin>>num_e；

cout<<”—--————---—-——-—-—-—--"〈〈endl<<”第一类规则总数（规则右边为变元）："；
cin>〉num_r1；
r1=new Regular_1［num_r1+1];
cout〈〈"—-———--——-————-——---——"< cout<<”第”〈r1［i]。left>〉r1［i］.right_1〉>r1［i]。right_2；
｝
r1[i］。left=-1;

cout<〈”-—-——-——--—-—-——-----—"<>num_r2;
r2=new Regular_2[num_r2+1]；
for(i=0;i〈num_r2;i++)
{
cout〈〈"第”〈空格隔开）:"；
cin>〉r2[i］。left>>r2[i].right；
｝
r2［i]。left=-1;

cout<〈"---———----———-——————-—”<〈endl<〈”起始变元的编号为："；
cin〉〉start_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〈〈"---————-—-—开始运行-————-——-—-”〈〈endl；

if(w［0］==—1）
｛
cout<〈”-——-——-———---—-----—-—--——-—-—-”<〈endl;
cout〈〈"检查发现输入为空..."〈
if((＊p2）。left==start_v＆&（*p2).right==-1)
｛
cout〈<”检查到起始变元到空的规则..."<〈endl；
cout<<"运行完毕！结果为:接受!"<〈endl;
cout<〈"—--——-—----—————-——-—-”<—--——-—-——---—---—--—-"〈〈endl;
return false;
}
p2=r2；
i=0；
cout〈<”--—--—-———--—-—---————-—--——-—-"〈的"〈〈i<<"行"<〈i<〈”列”〈〈endl;
t。SetValue（i,i，（＊p2）.left）;
}
p2++;
｝
p2=r2；
p++;
i++；
}
p=w;

cout<<"—-———--—-—--—————-—----————-——-”〈
｛
while（(*p1).left!=-1）
{
if(t.CheckValue(i，k,(＊p1）.right_1）&＆t。CheckValue（k+1,j,(*p1）。right_2）)
{
cout〈〈"table（”〈endl；
t.SetValue(i，j，(＊p1）。left);

｝
p1++；
｝
p1=r1;
}

｝
｝

t.Print(）;
if(t.CheckValue（1，len_w—1,start_v)）
｛
cout<<”起始变元"<〈start_v〈〈"在talbe(0，”〈 true;
}
else{
cout〈<"起始变元”〈〈start_v<<”在不在talbe(0,"〈ut〈〈”-——————-——-——-——--—-—-"<len_w;
w=new int［len_w+1]；
if（len_w==0)
cout<<”----——-—---——-——---—-—"<〈endl;
else
cout<<”依次输入w的内容的编号（以空格隔开）:";
for（int i=0;i〈len_w；i++)
{
cin>〉w[i］；
｝
w［i］=—1；
c。Go(w);
cout<〈”验证其它字符串？（Y/N）"；
char c;
cin〉>c；
if(c==’N'）
return;
｝

}
改程序在VC++下可以通过编译，并且运行结果正确

四、测试数据以及运行结果
以教材习题上面的一个CFG为例.该CFG描述如下：
S—〉RT
R-〉TR｜a
T—〉TR｜b
在该CFG下面测试输入w1=baba和w2=ababb测试结果如下：

14