Chomsky文法类型判断
文法简介
1．0型文法（短语文法）
如果对于某文法G，P中的每个规则具有下列形式：
u:: = v
其中u∈V＋，v∈V*，则称该文法G为0型文法或短语文法，简写为PSG。
0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L0。这种文法由于没有其他任何限制，因此0型文法也称为无限制文法，其相应的语言称为无限制性语言。任何0型语言都是递归可枚举的，故0型语言又称递归可枚举集。这种语言可由图灵机（Turning）来识别。
2．1型文法（上下文有关文法）
如果对于某文法G，P中的每个规则具有下列形式：
xUy:: = xuy
其中U∈VN；u∈V＋；x，y∈V*，则称该文法G为1型文法或上下文有关文法，也称上下文敏感文法，简写为CSG。
1型文法的规则左部的U和右部的u具有相同的上文x和下文y，利用该规则进行推导时，要用u替换U，必须在前面有x和后面有y的情况下才能进行，显示了上下文有关的特性。
1型文法所确定的语言为1型语言L1，1型语言可由线性有界自动机来识别。
3．2型文法（上下文无关文法）
如果对于某文法G，P中的每个规则具有下列形式：
U :: = u
其中U∈VN；u∈V＋，则称该文法G为2型文法或上下文无关文法，简写为CFG。
按照这条规则，对于上下文无关文法，利用该规则进行推导时，无需考虑非终结符U所在的上下文，总能用u替换U，或者将u归约为U，显示了上下文无关的特点。
2型文法所确定的语言为2型语言L2，2型语言可由非确定的下推自动机来识别。
一般定义程序设计语言的文法是上下文无关的。如C语言便是如此。因此，上下文无关文法及相应语言引起了人们较大的兴趣与重视。
4．3型文法（正则文法，线性文法）
如果对于某文法G，P中的每个规则具有下列形式：
U :: = T 或 U :: = WT
其中T∈VT；U,W∈VN，则称该文法G为左线性文法。
如果对于某文法G，P中的每个规则具有下列形式：
U :: = T 或 U :: = TW
其中T∈VT；U, W∈VN，则称该文法G为右线性文法。
左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状态文法，简写为RG。
按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。
3型文法所确定的语言为3型语言L3，3型语言可由确定的有限状态自动机来识别。
在常见的程序设计语言中，多数与词法有关的文法属于3型文法。
可以看出，上述4类文法，从0型到3型，产生式限制越来越强，其后一类都是前一类的子集，而描述语言的功能越来越弱，四类文法及其表示的语言之间的关系可表示为：
0型 1型 2型 3型；即L0 L1 L2 L3
流程图
代码
文法的数据结构：考虑到文法是一个四元组，包含Vn为非终结符，Vt为终结符，P为文法的规则，S为识别符或开始符，flag为文法的类型，因此下面使用C++中的类来为文法定义，并且使用set集合来保存每个文法的某些属性（不会重复）。
C++
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include<set>
#define MAX_LENGTH 10
using namespace std;
struct Principle{
string left;
string right;
};
struct Grammar{
set<char> Vn;
set<char> Vt;
vector<Principle> P;
char S;
int flag = -1;
};
void input(vector<Principle> &principleSet)
{
char tempLeft[MAX_LENGTH];
char tempRight[MAX_LENGTH];
while(scanf("%[^-]->%s",tempLeft,tempRight)!=EOF){
getchar();
Principle temp;
temp.left = tempLeft;
temp.right = tempRight;
principleSet.push_back(temp);
}
}
void analyseGram(Grammar &G)
{
G.S = G.P.front().left[0];//获得起始符
for(int i=0;i<G.P.size();++i){
Principle &temp = G.P[i];
for(int j = 0;j<temp.left.size();++j){
char v = temp.left[j];
if(!isupper(v)){
G.Vt.insert(v);
}else{
G.Vn.insert(v);
}
}
for(int j = 0;j<temp.right.size();++j){
char v = temp.right[j];
if(!isupper(v)){
G.Vt.insert(v);
}else{
G.Vn.insert(v);
}
}
}
}
bool existVNT(string s)
{
for(int i=0;i<s.size();i++){
if(isupper(s[i])){
return true;
}
}
return false;
}
void judgeGram(Grammar &G)
{
for(int i=0;i<G.P.size();++i){
if(existVNT(G.P[i].left)){
G.flag = 0;
break;
}
}
int temp = 0;
for(int i=0;i<G.P.size()&&G.flag==0;++i){
if(G.P[i].left.size()<=G.P[i].right.size()){
temp++;
}
}
if(temp==G.P.size()){
G.flag=1;
}
temp = 0;
for(int i=0;i<G.P.size()&&G.flag==1;++i){
if(1==G.P[i].left.size()&&isupper(G.P[i].left[0])){
temp++;
}
}
if(temp==G.P.size()){
G.flag=2;
}
temp = 0;
for(int i=0;i<G.P.size()&&G.flag==2;++i){
if(1==G.P[i].left.size()&&isupper(G.P[i].left[0])&&
(1==G.P[i].right.size()&&!isupper(G.P[i].right[0])||
2==G.P[i].right.size()&&!isupper(G.P[i].right[0])&&
isupper(G.P[i].right[G.P[i].right.size()-1]))){temp++;}
}
if(temp==G.P.size()){
G.flag=3;
}
}
void printResult(Grammar &G)
{
cout<<"G=(Vn,Vt,P,S)是"<<G.flag<<"型文法"<<endl<<endl;
cout<<"非终结符Vn有：";
for(set<char>::iterator i = G.Vn.begin();i!=G.Vn.end();++i){
cout<<*i<<" ";
}
cout<<endl;
cout<<"终结符Vt有：";
for(set<char>::iterator i = G.Vt.begin();i!=G.Vt.end();++i){
cout<<*i<<" ";
}
cout<<endl;
cout<<"开始符为："<<G.S<<endl;
cout<<"规则P如输入所示"<<endl;
cout<<endl;
}
int main()
{
Grammar G;
G.Vn.clear();
G.Vt.clear();
input(G.P);
G.flag = 3;
analyseGram(G);
judgeGram(G);
printResult(G);
}实验验证
1型文法实验结果
2型文法实验结果
3型文法实验结果
困难与解决方法
- 数据结构的建立
为了便于以后实验的代码复用，需要建立一个良好的数据结构类型。因此本次实验我采用了C++来写，并使用了C++中的容器，如set和vector。
- 文法类型的判断方式
这一部分是此次实验的重点，如何有效地判断文法的类型是一个难题。经过分析后，我决定自上而下，由低到高地来判断文法的类型。首先判断是否为低级文法，再判断是否为高级文法。在判断过程中出现很多分支语句，因此可以将某些模块提出，比如非终结符判断模块，可以整合为函数bool existVNT(string s)。
- 如果一开始实验中输入的格式不对，对此种问题我们可以有两种解决方法，一种是在输入的时候立即判断是否是合法的规则，也可以在文法类型判断是输出错误消息。