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

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

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；i〈num_w;i++）
｛
value[i］=new int*[num_w]；
for（int j=0；j<num_w；j++)
{
value［i］[j]=new int［num_v];
for(int k=0；k<num_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；i<size；i++)
{
for(j=0；j<size；j++）
｛
cout〈<”table[”<〈i〈<”］[”<〈j<<"］：”；
for(k=0;k〈num_v；k++)
｛
if（this—>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<<endl<<”--——-——-—---CFG构造函数—-———-———-”<<endl；
int num_r1，num_r2;
int i，j,k;

cout<<”-——-————-—-—---———--——"〈<endl〈〈”变元总数：”;
cin>>num_v;

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

cout<<”—--————---—-——-—-—-—--"〈〈endl<<”第一类规则总数（规则右边为变元）："；
cin>〉num_r1；
r1=new Regular_1［num_r1+1];
cout〈〈"—-———--——-————-——---——"<<endl；
cout〈<”在下面的输入中注意：变元编号以及终结符编号从0开始"<〈endl；
cout<<"—-—--------——-———-—---"〈<endl;
for（i=0;i<num_r1;i++）
{
cout<<”第”〈<i<〈”条规则的三个变元的编号依次为(以空格隔开）:";
cin〉>r1［i]。left>〉r1［i］.right_1〉>r1［i]。right_2；
｝
r1[i］。left=-1;

cout<〈”-—-——-——--—-—-——-----—"<<endl<〈”第二类规则总数(规则右边为终结符或空）:";
cin>>num_r2;
r2=new Regular_2[num_r2+1]；
for(i=0;i〈num_r2;i++)
{
cout〈〈"第”〈<i〈<”条规则的变元的编号和终结符编号(空以—1表示）依次为（以空格隔开）:"；
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〈〈"检查发现输入为空..."〈<endl;
while((＊p2)。left!=-1）
{
if((＊p2）。left==start_v＆&（*p2).right==-1)
｛
cout〈<”检查到起始变元到空的规则..."<〈endl；
cout<<"运行完毕！结果为:接受!"<〈endl;
cout<〈"—--——-—----—————-——-—-”<<endl;
result=true；
return result;
｝
p2++；
}

cout〈〈"未发现从起始变元到空的派生。”<<endl;
cout<〈"运行完毕，结果为：拒绝”〈<endl;
cout<<”—--——-—-——---—---—--—-"〈〈endl;
return false;
}
p2=r2；
i=0；
cout〈<”--—--—-———--—-—---————-—--——-—-"〈<endl；
cout〈<"开始从头到尾扫描，将某些变元放入对应的对角线上的表格中：”<<endl；
while（＊p！=—1）
｛
while（(*p2)。left！=—1）
{
if（(*p2)。right==＊p)
{
cout<<”由于变元”〈<(*p2).left〈〈”派生”<〈"终结符”〈<＊p〈<”，故将其放入表格的"〈〈i<<"行"<〈i<〈”列”〈〈endl;
t。SetValue（i,i，（＊p2）.left）;
}
p2++;
｝
p2=r2；
p++;
i++；
}
p=w;

cout<<"—-———--—-—--—————-—----————-——-”〈<endl；
cout〈〈"开始依次向表格的某些单元格添加数据.。."〈<endl；
for（l=2;l<=len_w；l++)
{
for(i=0;i<len_w—l+1；i++)
{
j=i+l-1；
for（k=i;k<=j-1;k++）
｛
while（(*p1).left!=-1）
{
if(t.CheckValue(i，k,(＊p1）.right_1）&＆t。CheckValue（k+1,j,(*p1）。right_2）)
{
cout〈〈"table（”〈<i〈<","<<k〈<”)中含有变元”〈<（＊p1）.right_1<〈”而且table（”<〈k+1<<","〈<j〈<”)中含有”〈〈（＊p1).right_2;
cout〈<",因此将变元”〈<(＊p1）.left<〈”放入table（"<〈i<〈",”〈<j〈〈"）中"〈〈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，”〈<len_w—1〈〈”)中"〈〈endl；
cout〈<”运行完毕!结果为：接受！"〈〈endl;
cout〈<"—---—--—--—--—---————-”〈<endl；
return true;
}
else{
cout〈<"起始变元”〈〈start_v<<”在不在talbe(0,"〈<len_w-1〈<")中”<<endl；
cout〈〈”运行完毕！结果为:拒绝！"〈〈endl;
cout〈〈"————--———-———---——-———"<〈endl;
return false；
｝
｝

main（)
｛
cout〈<”—--——----—-—CFG是P成员判定程序-------—-—”<<endl;
CFG c;
while（true）
{
int ＊w；
int len_w;
cout〈〈”-——————-——-——-——--—-—-"<<endl<〈”输入w的长度："；
cin〉>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