上下文无关文法的表示与存储

【问题描述】把输入的文法存储在计算机内。

【基本要求】

1、输入上下文无关文法的一组产生式。

2、将文法按顺序或链式结构存储在计算机内。

3、输出文法的四要素：终极符集合、非终极符集合、规则式集合和开始符。

4、开始符在输入时指明，否则将所输入第一条规则式的左部符号视为开始符。

例如输入如下文法：

E->E+T| T 

T- >T*F| F 

F->(E)|i

下面是C++代码：

#include<iostream>

using namespace std;

const int MaxRightLenth=20;

const int MaxRuleNum=20;

const int MaxVtNum=20;

const int MaxVnNum=20;

struct rule 

{

char Left;

char Right[MaxRightLenth];

int RLength;

} ;//声明结构体类型

char Vt[MaxVtNum]; //定义终极符号集

char Vn[MaxVnNum]; //定义非终极符号集

int  main()

{

int n;//文法表达式数目

int x=0;//非终极符号集元素个数

int y=0;//终极符号集元素个数

cout<<"请输入表达式数目n：";

cin>>n;

struct rule grammar[MaxRuleNum]; //定义文法

cout<<endl;

char xy[2];

//输入文法

for(int i=0;i<n;i++)

{

cout<<"请输入第"<<i<<"个文法右部长度：";

cin>>grammar[i].RLength;

cout<<"请输入第"<<i<<"个文法"<<endl;

cin>>grammar[i].Left;

for(int x=0;x<2;x++) 

{

cin>>xy[x];

}

//cout<<"请输入第"<<i<<"个文法右部：";

for(int j=0;j<grammar[i].RLength;j++) //输入文法右部

{

cin>>grammar[i].Right[j];

}

cout<<endl;

for(x=0;x<2;x++) 

{

xy[x]='\0';

}

}

//存储文法

for(i=0;i<n;i++)

{

if(grammar[i].Left>='A'&&grammar[i].Left<='Z')

{

Vn[x] = grammar[i].Left;

x++;

}

for(int j=0;j<grammar[i].RLength;j++) 

{

if(grammar[i].Right[j]>='A'&&grammar[i].Right[j]<='Z')

{

Vn[x] = grammar[i].Right[j];

x++;

}

else if(grammar[i].Right[j]!='|'&&grammar[i].Right[j]!='&')

{

Vt[y] = grammar[i].Right[j];

y++;

}

}

}

//去重复字符串

for(i=0;i<x;i++)

{

for(int j=i+1;j<x;j++)

{

if(Vn[i]==Vn[j])

{

Vn[j]='\0';

}

}

}

for(i=0;i<y;i++)

{

for(int j=i+1;j<y;j++)

{

if(Vt[i]==Vn[j])

{

Vt[j]='\0';

}

}

}

cout<<"开始符："<<grammar[0].Left<<endl;

cout<<"非终结符集：";

for(i=0;i<x;i++)

{

if(Vn[i]=='\0')

{

continue;

}

cout<<Vn[i];

cout<<" ";

}

cout<<endl;

cout<<"终结符集: ";

for(i=0;i<y;i++)

{

cout<<Vt[i]<<" ";

}

cout<<endl;

return 0;

}