编译原理实验二：压缩文法的等价变换

实验二：压缩文法的等价变换

一：要求

输入：任意的上下文无关文法 输出：等价的压缩了的文法

要求：除了可查看压缩了的文法，还可查看删除了哪些规则 二：实验目的 了解文法的简化 三：实验原理

删除文法中的有害规则和多余规则 有害规则：

若文法中有如U::=U的规则，则这就是有害规则，它会引 起二义性，而无任何用处。 多余规则：

（1）某条规则U::=u的左部非终结符U（U不是识别符号），不在任何其他规则右部出现，即所有的推导始终不会用到此规则。【不可到达】

（2）在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。即该规则中含有推不出任何终结符号串的非终结符。【不可终止】

四：数据结构与算法 struct Chomsky {

string left; string right; };

void apart(Chomsky *p,int i) //分开产生式左右部 void VNVT(Chomsky *p)//求VN和VT int zero(Chomsky *p)//0型文法 int one(Chomsky *p)//1型文法 int two(Chomsky *p)//2型文法

void shanchu(Chomsky *p)//删除多余规则与有害规则

五：出错分析

1：变量重复定义导致了一些小错误 2：程序太长{}缺少也导致了错误

3：后面删除规则的程序出错了，没有调试成功。

2

六：实验结果与分析 不是上下文无关文法的：

2型文法的压缩：

3

七：源代码

#include #include using namespace std;

#define max 50 int NONE=1; int RELEFT=1;

string strings,noend,end;//非终结符与终结符存储 int n;//产生式总数 int flag;

struct Chomsky {

string left;

string right; };

void apart(Chomsky *p,int i) //分开产生式左右部 {

4

int j;

for(j=0;j

void VNVT(Chomsky *p)//求VN和VT {

if(strings[j]=='-') { }

p[i].left=strings.substr(0,j);

p[i].right=strings.substr(j+1,strings.length()-j);

int i,j;

for(i=0;i

for(j=0;j<(int)p[i].left.length();j++) {

if((p[i].left[j]>='A'&&p[i].left[j]<='Z'))//非终结符判断 { } else

5

if(noend.find(p[i].left[j])>100)

noend+=p[i].left[j];

}

}

}

{ }

if(end.find(p[i].left[j])>100)

end+=p[i].left[j];

for(j=0;j<(int)p[i].right.length();j++) { } }

if(!(p[i].right[j]>='A'&&p[i].right[j]<='Z'))//终结符判断 { } else {

if(noend.find(p[i].right[j])>100)

noend+=p[i].right[j]; if(end.find(p[i].right[j])>100)

end+=p[i].right[j];

int zero(Chomsky *p)//0型文法

6

{

int flag(0),count(0);

int i,j;

for(i=0;i

{ }

if(count==n)

return 1; //属于0型文法 for(j=0;j<(int)p[i].left.length();j++) { } if(flag>0) { } else

break; //左部没有非终结符，结束 flag=0; count++;

if(p[i].left[j]>='A'&&p[i].left[j]<='Z') //有否非终结符

flag++;

else {

7

}

}

cout<

int one(Chomsky *p)//1型文法 {

int flag(0);

int i; if(zero(p)) 部

{

for(i=0;i

if(p[i].right.length()

}

{ } flag++; break;

8

} else flag--;

if(flag>0) {

cout<

return 1; //属于1型文法

else

return 0;

}

int two(Chomsky *p)//2型文法 {

int flag(0); int i; if(one(p))

{

9

\

for(i=0;i

if((p[i].left.length()!=1)||!(p[i].left[0]>='A'&&p[i].left[0]<='Z'))

//左部不属于一个字符或不属于非终结符 } else { } flag++; break;

flag--;

if(flag>0) {

cout<

\

return 0; //不属于2型文法

} else

if(flag==0) { }

10

cout<<\次文法属于2型文法\return 1;//属于2型文法

else

return 0;

}

void shanchu(Chomsky *p)//删除多余规则与有害规则 { if(two(p)) {

cout<<\此文法属于上下文无关文法，可进行文法压缩，实验

继续\ int i,j;

for(i=0;i

break;//次规则不是有害规则

}

11

}

if(j==p[i].left.length()-1)//此条规则为有害规则，删除 {

cout<<\

删

除

此

条

有

害

规

则

\

for(int k=0;k<(int)noend.length();k++)//多余规则中不可到达的 } } } n--;

判断

{

for(i=0;i

for(j=0;j<(int)p[i].right.length();j++) {

if(noend[k]!=p[i].right[j])

continue;

else

i--;break;

12

}

if(i==n-1)//此条规则为多余规则 {

for(i=0;i

if(p[i].left[j]==noend[k]||p[i].right[j]==noend[k])

cout<<\删除此条多余规则

\ 断

}

n--;

}

}

}

for(k=0;k<(int)noend.length();k++)//多余规则中不可终止的判

{

}

13

}

cout<<\压缩后的文法是：\for(i=0;i

cout<

} else

cout<<\此文法不是上下文无关文法，实验结束\

void main() { int i;

cout<<\编译原理实验二：压缩文法的等价变换....................\

cout<<\请输入产生式总数及各产生式：\其中左右部之间用'-'表示，空用'#'表示\ cin>>n;

Chomsky *p=new Chomsky[max];

for(i=0;i

14

cin>>strings; apart(p,i);

}

VNVT(p); shanchu(p);

}

15

本文来源：https://www.bwwdw.com/article/4glr.html