一、实验名称

​ 文法类型的判断和推导序列的生成

二、实验目的

​ 输入：一组任意的文法规则和任意符号串。

​ 输出：相应的Chomsky文法类型和推导。

三、实验原理1、文法G定义为四元组(Vn,Vt,P,S)

​ 其中Vn为非终结符（或语法实体，或变量）集：Vt为终结符集；P为规则（α->β）的集合，α∈(Vn∪Vt)且至少包含一个非终结符，β∈(Vn∪Vt)；Vn，Vt和P是非空有穷集。S称作识别符或开始符，它是一个非终结符，至少要在一条规则中作为左部出现。

2、文法类型的判断

​ a.设G=(Vn,Vt,P,S)为一文法，若P中的每一个产生式α->β均满足

|β|>=|α|，仅仅S->ε除外，则文法G是1型或上下文有关的。

​ b.设G=(Vn,Vt,P,S)，若P中的每一个产生式α->β满足: α是一个非终结符，β∈(Vn∪Vt)*，则此文法称为2型的或上下文无关的。

​ c. 设G=(Vn,Vt,P,S)，若P中的每一个产生式的形式都是A->αB或A->α，其中A和B都是终结符，α∈Vt*，则G是3型文法或正规文法。

四、实验思路

​ 本实验采取C++来完成，用大写字母A到Z表示非终结符，小写字符a到z表示终结符。

1、接受产生式

​ 首先建立一个结构体siyuanzu，其成员有非终结符集合数组Vn，终结符集合数组Vt以及产生式集合数组rule，通过函数input来接受从键盘输入的产生式，并且存储于string类字符串数组rule中。函数input实现接受产生式功能的思路为：先确定要输入的产生式数目n，用for循环实现产生式的存储。

2、文法类型的判断

​ 函数Grammer实现判断文法类型的功能并且输出文法的类型。其实现功能的思路为：

​ a.对rule数组中每一个产生式进行判断，以“->”中的“-”作为判断条件，将产生式分为左部和右部分别计算左部和右部的长度。若youb小于左部则不是1型文法。输出0型文法；若右部大于或等于左部，则继续判断。

​ b.判断文法是否为2型文法，经过a步骤的执行，若文法为1型文法，只需在此基础上判断文法的左部是否只有一个非终结符。通过判断条件zuo==1&&'A'