文法判别实验报告

1、编译原理实验报告实验名称文法类型的判别学号xxxxxxxxx姓名xxx10文法类型的判别1. 实验目的输入一组文法规则，判定它是哪一种文法。2. 实验原理乔姆斯基(Chomsky)于1956年建立形式语言的描述他把文法分成：0型、1型、2型、3型1) 、0型文法短语文法设G=(VN VT, P, S),如果它的每个产生式aP (VNU,简称PSG种结构：a (VNU VT)*且a至少包含一个非终结符,VT)* ,则G是一个0型文法(短语结构文法、无限制文法)2) 、1型文法上下文有关文法设G=( VN VT, P, S),如果它的每个产生式a关文法,3)、| a |，仅仅S 除外，则文法G是1

2、型文法上下文敏感文法)，简称CSG2型文法上下文无关文法(上下文有设G=( VN VT, P , S),如果它的每个产生式aa是一个非终结符，P V*，则文法G是2型文法(上下文无关文法)，简称CFG有时将2型文法的产生式表示为A P的形式，其中A VN也就是用P取代非终结符A时，与A所在的上下文无关，因此取名为 上下文无关。4）、3型文法正规文法设G=（ VN VT, P, S）,如果它的每个产生式a VT*,则文，简称RGa （A B a或A a ）,其中A和B都是非终结符, 法G是3型文法（正规文法，正则文法，有穷状态文法）若文法中所有的产生式均为 A a B或Aa形式，则此文法为右线性

3、的若文法中所有的产生式均为 A B a或A a形式，则此文法为左线性的其后一类都是前一类的子集，而描述语言的功能越来越弱，四类文法之间的关系可表示为：0型1型2型3型因此，每一种正规文法（3型）都是上下文无关的，每一种上下 文无关文法（2型）都是上下文有关的，而每一种上下文有关文法（1型）都是0型文法。各类文法对应的语言叫各类文法语言。型语言型语言型语言线性界限自动机下推自动机A3型语言-有穷状态自动机例 3.5-2 :文法 GS:0A|1B|0A0|B1|0SB1|1|0第一,左边有非终结符，所以此文法是 0型文法;第二,第三,左边只有一个非终结符，所以此文法是 2型文法;左边符号串长度不大

4、于右边，所以此文法是 1型文法;第四，由于文法中既有左线性文法又有右线性文法，所以此 文法不是3型文法;综上所述，此文法是2型文法。3. 实验内容1）、输入文法的终结符（小写字母或数字）和非终结符（大写字母）以及确定识别符（规定第一输入的非终结符为识别符）2）、输入文法的产生式的个数以及各个产生式（左部 -右部）3）、判断文法类型4. 实验代码与结果 1）、实验代码#define _CRT_SECURE_NO_W ARNINGS#in clude #in clude #in clude #in clude #i nclude #in clude using n ames pace std;co

5、n st int STRING_MAX_LENGTH = 10;/* 一条规则*/struct Prin ci pie stri ng left;stri ng right;Principl e(c onst char *l, const char *r) : left(l), right(r) ;*/*文法的四元组形式，同时将该文法类型也作为其属性 struct Grammer set Vn;set Vt;vectorvPrincip le P;char S;int flag; /文法类型Grammer(void) : flag(-1) ;/*输入规则*/void inpu t(vector

6、 &pnncipl eSet) char leftSTRING_MAX_LENGTH;char rightSTRING_MAX_LENGTH;while (EOF != scan f(%F-%s, left, right)getcharO;princip leSet. pu sh_back (Princip le(left, right);/* 得到 S, Vn, Vt*/void getGrammer(Grammer &G) GS = G.P.fron t().left.fro nt();G.Vn.clear();GVt.clearO;for (unsigned i = 0; i G .P.

7、size(); +i)const Principle &prcp = G .Pi;for (un sig ned j = 0; j prcp.l eft.size(); +j) char v = prcp.l eftj;!isupper(v) ? G.Vt.insert(v) : G .Vn.insert(v);for (un sig ned j = 0; j prep .right.size(); +j)char v = prep .rightj;!isupper(v) ? G.Vt.insert(v) : G .Vn.insert(v);（文法的左部）中是否存在一个非终结符。/*判断字符串

8、bool has Upp er(stri ng s)return s.e nd() != fin d_if(s.begi n(), s.e nd(), is upper);*/*判断文法类型。*/void check(i nt &flag, const Principle &prcp) switch (flag) case 3:if (1 = prcp.l eft.size() & isupper(prcp.l eft.fro nt() &(1 = prep .right.size() & !is upper(prcp .right.fr on t() |2=prep .right.size(

9、)&!is upper(prcp .right.fro nt()isupper(prcp .right.back()&break;case 2:if (1 = prcp.l eft.sizeO & isupper(p rcp.left.fro nt() flag = 2;break;case 1:if (has Upper(prcp.l eft) & prcp.l eft.size() = prep .right.size() flag = 1;break;default :/所有的文法规则左部都必须至少含有一个非终结符，是否应放到最前面判断? 用异常机制exit是否合适？try if (!h

10、as Upper(prcp.l eft) throw exception(”输入的文法错误！”)；catch (exce pti on e) cout e.what() en dl;exit(-1);flag = 0; break;/*判别文法并生成四元组形式。*/void solve(Grammer &G) Gflag = 3;/从正则文法开始判断for (unsigned i = 0; i G .P.size(); +i) check(G.flag, G.P i); getGrammer(G);/*输出文法*/void out pu t(c onst Grammer &G) cout G

11、= (Vn, Vt, P, S)是 G .flag 型文法 n endl;cout Vn: en dl;for (auto ite = G .Vn.begin(); ite != G.Vn.end(); +ite) cout *ite en dl;cout en dl;cout Vt: endl;for (auto ite = G .Vt.begin(); ite != G .Vt.end(); +ite) cout *ite en dl;cout en dl;cout P: endl;for (auto ite = G P.begin(); ite != G.P.end(); +ite) cout (*ite).left (*ite).right endl;cout en dl;cout S:n G .S aSBE