【文件属性】：
文件名称：Chomsky文法类型判断及消除文法的左递归.txt
文件大小：7KB
文件格式：TXT
更新时间：2015-07-18 13:49:51
chomsky
byylChomsky文法类型判断
#include
#include
using namespace std;
#define MAXS 50
int NONE=1;
int RELEFT=1;
string strings,noend,end;
int N;
struct STR
{
string left;
string right;
};
//输出四元组
void print(STR *p)
{
int i;
cout<"<='A'&&p[i].left[j]<='Z'))
{
if(noend.find(p[i].left[j])>100)
noend+=p[i].left[j];
}
else
{
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'))
{
if(end.find(p[i].right[j])>100)
end+=p[i].right[j];
}
else
{
if(noend.find(p[i].right[j])>100)
noend+=p[i].right[j];
}
}
}
}
//删除无用产生式
void useless(STR *p)
{
int i,j,k;
string vn;
vn+=p[0].left;
for(j=0;j='A'&&p[i].right[k]<='Z'&&vn;.find(p[i].right[k])>100)
vn+=p[i].right[k];
}
//cout<100)
{
for(i=0;i"<100)
{
noend+=vn;
break;
}
}
return vn;
}
//消除直接左递归
void releft(STR *p,int i)
{
int j,k;
char c;
for(j=0;j"<"<"<"<='A'&&p[i].left[j]<='Z') //有否非终结符
flag++;
}
if(flag>0)
{
flag=0;
count++;
}
else
break; //左部没有非终结符，结束
}
if(count==N)
return 1; //属于0型文法
else
{
cout<0)
{
cout<='A'&&p[i].left[0]<='Z')) //左部不属于一个字符或不属于非终结符
{
flag++;
break;
}
}
else
flag--;
if(flag>0)
{
cout<='A'&&p[i].right[0]<='Z')) //右部字符个数不是1或2，或首字符是非终结符
{
flag++;
break;
}
else
if((p[i].right.length()==2)&&!(p[i].right[1]>='A'&&p[i].right[1]<='Z')) //第二个字符不是非终结符
{
flag++;
break;
}
}
else
flag--;
if(flag>0)
{
cout<>N;
STR *p=new STR[MAXS];
for(i=0;i>strings;
getlr(p,i);
}
three(p);
VNVT(p);
if(NONE)
print(p);
}
////////////////////////////////////////////////////////////////
测试数据：
//3型文法
9
S-0A
S-1B
S-0
A-0A
A-0S
A-1B
B-1B
B-1
B-0
//2型文法，不含左递归
4
S-aA
S-d
A-bAS
A-#
//2型文法，含左递归，可消除
6
S-Qc
S-c
Q-Rb
Q-b
R-Sa
R-a
//2型文法，含左递归，可消除，有无用产生式
4
S-B3
B-S5
B-2
A-3
//2型文法，含左递归，不能消除
6
S-Qc
S-c
Q-Q
Q-Rb
Q-b
Q-#
//1型文法
3
A-kL
La-K0a
K-6as
//0型文法
4
fQg-f8A9g
tA-tkQ
9Q1-9P21
P-#
//不是0型文法
3
wer-3
rtG-uy
rt-y
