Chomsky文法类型判断.doc

安 徽 大 学

实 验 课 程 教 案

课 程 名 称
编译原理
学号
E01114278
姓名
徐勇兵

实验一
名称
Chomsky文法类型判断（Recognizing the type of the Chomsky grammar）
一、背景资料
1956年，N.Chomsky首先对形式语言进行了描述。N.Chomsky在对某些自然语言进行研究的基础上，提出了一种用于描述语言和文法的数学系统，按照对文法规则的不同定义形式，对语言和文法分成了4类，对每一类语言，让它与一种特定种类的自动机那样的识别器联系起来。形式语言理论的形成与发展，对计算机科学的发展是一个推动，在程序设计语言的设计与编译实现以及计算复杂性等方面都有着重大影响。
二、实验目的要求
输入：一组任意的规则。
输出：相应的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

四、仪器
微机
五、实验代码：import java.util.Vector;

import javax.swing.JOptionPane;
public class test1
{
public class End
{
Vector<String> end=new Vector<String>();
public void add()
{
while(true)
{
String s=JOptionPane.showInputDialog(null,"请输入终结符 ");
if(s==null)
{ break;

}//if
end.add(s);
}//while

}//add()
public boolean iscontain(String s)
{
if(end.contains(s))
return true;
else return false;
}// iscontain()
public boolean isRGPcontain(String s)//正则表达式判断s1是否在END的壁报里面 正则忘了怎么写了
{
int length=s.length();
for(int i=0;i<length;i++)
{
String a=""+s.charAt(i);
if(end.contains(a))
continue;
else return false;
}//for
return true;
}
}//class end
public class Noend
{
Vector<String> noend=new Vector<String>();
public boolean iscontain(String s)
{
if(noend.contains(s))
return true;
else return false;
}
public void add()
{
while(true)
{
String s=JOptionPane.showInputDialog(null,"请输入非终结符 ");
if(s==null)
return;
noend.add(s);
}
}//addendelement()

public boolean isRGPcontain(String s)//正则表达式判断s1是否在END的壁报里面 正则忘了怎么写了
{
int length=s.length();
for(int i=0;i<length;i++)
{
char a=s.charAt(i);
if(noend.contains(a))
continue;
else return false;
}//for
return true;
}
}//class noend
public class Produce
{
Vector<String> left=new Vector<String>();//生产式的左部
Vector<String> right=new Vector<String>();//生产式的右部
public void add()
{ while(true)
{
String s=JOptionPane.showInputDialog(null,"请输入产生式空格隔开 ");
if(s==null)
return;
String ss[]=s.split(" ");
System.out.println("*"+ss[0]+"*");
System.out.println("*"+ss[1]+"*");
left.add(ss[0]);
right.add(ss[1]);
}
}//add()
public boolean is1()
{
int length=left.size();
for(int i=0;i<length;i++)
{
String s1=right.get(i);
String s2=left.get(i);
if(s1.length()>=s2.length())
continue;
else
return false;
}//for
return true;
}//is1
public boolean is2(Noend noend)
{
int length=left.size();
for(int i=0;i<length;i++)
{
String s1=right.get(i);
String s2=left.get(i);
if(noend.iscontain(s2))
continue;
return false;
}//for
return true;
}//is2
public boolean is3(Noend noend,End end)
{
int length=left.size();
for(int i=0;i<length;i++)
{
String s1=right.get(i);
String s2=left.get(i);
System.out.println(s1);
System.out.println(s2);
if(noend.iscontain(s2))//如果左部是一个非终结符
{
if(end.isRGPcontain(s1))//正则表达式判断终结符是否包含s1 A->a型
{System.out.println("A->a型");continue;}
int s1length=s1.length();
String left1=s1.substring(0,s1length-2);//A-aB型中的a
String right1=""+s1.charAt(s1length-1);//A-aB型中的B
if(end.isRGPcontain(left1)&&noend.isRGPcontain(right1))
{System.out.println("A-aB型");continue;}
else return false;

}//if
else
return false;
}//for
return true;
}//is3
}//calss produce
public test1()
{
End end=new End();
Noend noend= new Noend();
Produce produce=new Produce();
end.add();
noend.add();
produce.add();
if(produce.is1())
System.out.println("是1型");
if(produce.is2(noend))
System.out.println("是2型");
if(produce.is3(noend,end))
System.out.println("是3型");
}
public static void main(String args[])
{
test1 app=new test1();
}
}//class gramemer
六、注意事项
⑴ 文法的输入应简便。
⑵ 指明是哪一类Chomsky 文法，并给出相应的四元组形式：G=（VN，VT，P，S）。
说明：简单起见， 可以不考虑0型文法类。

数据结构：向量（vecotr）
实验截图：