编译原理文法的判别实验报告

编译原理实验报告实验名称 文法类型的判别 实验时间 2013年11月2日 院系 安徽大学江淮学院 学号 JV114025 姓名 张巧巧 学号 JV114002 姓名 王文悦 学号 JV114045 姓名 冯岚 文法类型的判别1.实验目的1）、检测对文法类型的掌握程度2）、加深对文法的理解3）、练习用编程解决问题4）、培养动手能力与创作思维2.实验原理1)、0型文法（短语文法）设G=（Vn，Vt，P,S),如果它的每一个产生式#-&是这样一种结构：#属于（终结符和终结符）的闭包且至少含有一个非终结符，&属于（终结符和终结符）的闭包。任何0型语言都是递归可枚举的，递归可枚举集必定是一个0型文法，0型文法的能力相当于图灵机（Turning）。2)、1型文法（上下文有关文法）设G=（Vn，Vt，P,S)为一文法，若P中的每一个产生式#-&均满足|#|=|&|,仅仅S-空 除外。 其识别系统：线性界限自动机3)、2型文法（上下文无关文法）设G=（Vn，Vt，P,S)为一文法，若P中的每一个产生式#-&均满足：#是一个非终结符，&属于（终结符和终结符）的闭包。2型文法其识别系统：不确定的下推自动机一般定义程序设计语言的文法是上下文无关的。如C语言便是如此。因此，上下文无关文法及相应语言引起了人们较大的兴趣与重视。4)、3型文法（正规文法）设G=（Vn，Vt，P,S)为一文法，若P中的每一个产生式都是A-aB或A-a,其中A和B都是非终结符，a属于终结符的闭包。其识别系统：确定的有穷自动机可以看出上述4类文法，从0型到3型，产生式的限制越来越强，其后一类都是前一类的子集，而描述语言的功能越来越弱，四类文法之间的关系可表示为：0型1型2型3型3.实验内容1）、输入文法的终结符（小写字母或数字）和非终结符（大写字母）以及确定识别符（规定第一输入的非终结符为识别符）2）、输入文法的产生式的个数以及各个产生式（左部-右部）3）、判断文法类型4.实验心得通过这次实验让我们深深的体会到了判别文法的复杂性，也走了许多冤枉路，想过多种方法，尝试过，可是有的没有走下去，最终没有出我们知道文法是嵌套的，也就是说满足3型文法的条件，一定是2型、1型、0型文法；满足2型文法的条件，一定是1型、0型文法；满足1型文法一定是0型文法；利用这一特点着手判断，先判断一条产生式是否满足3型文法，如果不是3型文法然后判断是否是2型文法、1型文法、0型文法，直到判断最精确的文法类型。在过程中从一条产生式的0型文法开始判断，若发现上一条规则是符合1型文法，则就从1型文法开始判断，详见源代码。5. 实验代码与结果1）、实验代码#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include using namespace std;const int STRING_MAX_LENGTH = 10;/*一条规则*/struct Principle string left; string right; Principle(const char *l, const char *r) : left(l), right(r) ;/*文法的四元组形式，同时将该文法类型也作为其属性*/struct Grammer set Vn; set Vt; vector P; char S; int flag; / 文法类型 Grammer(void) : flag(-1) ;/*输入规则*/void input(vector &principleSet) char leftSTRING_MAX_LENGTH; char rightSTRING_MAX_LENGTH; while (EOF != scanf(%-%s, left, right) getchar(); principleSet.push_back(Principle(left, right); /*得到S, Vn, Vt*/void getGrammer(Grammer &G) G.S = G.P.front().left.front(); G.Vn.clear(); G.Vt.clear(); for (unsigned i = 0; i G.P.size(); +i) const Principle &prcp = G.Pi; for (unsigned j = 0; j prcp.left.size(); +j) char v = prcp.leftj; !isupper(v) ? G.Vt.insert(v) : G.Vn.insert(v); for (unsigned j = 0; j prcp.right.size(); +j) char v = prcp.rightj; !isupper(v) ? G.Vt.insert(v) : G.Vn.insert(v); /*判断字符串（文法的左部）中是否存在一个非终结符。*/bool hasUpper(string s) return s.end() != find_if(s.begin(), s.end(), isupper);/*判断文法类型。*/void check(int &flag, const Principle &prcp) switch (flag) case 3: if (1 = prcp.left.size() & isupper(prcp.left.front() & (1 = prcp.right.size() & !isupper(prcp.right.front() | 2 = prcp.right.size() & !isupper(prcp.right.front() & isupper(prcp.right.back() break; case 2: if (1 = prcp.left.size() & isupper(prcp.left.front() flag = 2; break; case 1: if (hasUpper(prcp.left) & prcp.left.size() = prcp.right.size() flag = 1; break; default : / 所有的文法规则左部都必须至少含有一个非终结符，是否应放到最前面判断？ / 用异常机制exit是否合适？ try if (!hasUpper(prcp.left) throw exception(输入的文法错误！); catch (exception e) cout e.what() endl; exit(-1); flag = 0; break; /*判别文法并生成四元组形式。*/void solve(Grammer &G) G.flag = 3; / 从正则文法开始判断 for (unsigned i = 0; i G.P.size(); +i) check(G.flag, G.Pi); getGrammer(G);/* 输出文法*/void output(const Grammer &G) cout G = (Vn, Vt, P, S)是 G.flag 型文法n endl; cout Vn: endl; for (auto ite = G.Vn.begin(); ite != G.Vn.end(); +ite) cout *ite endl; cout endl; cout Vt: endl; for (auto ite = G.Vt.begin(); ite != G.Vt.end(); +ite) cout *ite endl; cout endl; cout P: endl; for (auto ite = G.P.begin();