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

《编译原理文法的判别实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理实验报告实验名称文法类型的判别实验时间2013年11月2日院系安徽大学江淮学院学号JV114025姓名张巧巧学号JV114002姓名王文悦学号JV114045姓名冯岚文法类型的判别1.实验目的1）、检测对文法类型的掌握程度2）、加深对文法的理解3）、练习用编程解决问题4）、培养动手能力与创作思维2.实验原理1)、0型文法（短语文法）设G=（Vn，Vt，P,S),如果它的每一个产生式#->&是这样一种结构：#属于（终结符和终结符）的闭包且至少含有一个非终结符，&属于（终结符和终结符）的闭包。任何0型语言都是递归可枚举的，递归可枚举集

2、必定是一个0型文法，0型文法的能力相当于图灵机（Turning）。2)、1型文法（上下文有关文法）设G=（Vn，Vt，P,S)为一文法，若P中的每一个产生式#->&均满足

3、#

4、>=

5、&

6、,仅仅S->空除外。其识别系统：线性界限自动机3)、2型文法（上下文无关文法）设G=（Vn，Vt，P,S)为一文法，若P中的每一个产生式#->&均满足：#是一个非终结符，&属于（终结符和终结符）的闭包。2型文法其识别系统：不确定的下推自动机6一般定义程序设计语言的文法是上下文无关的。如C语言便是如此。因此，上下文无关文法及相应语言引起了人们较大的兴趣与重视

7、。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

8、.实验心得通过这次实验让我们深深的体会到了判别文法的复杂性6，也走了许多冤枉路，想过多种方法，尝试过，可是有的没有走下去，最终没有出我们知道文法是嵌套的，也就是说满足3型文法的条件，一定是2型、1型、0型文法；满足2型文法的条件，一定是1型、0型文法；满足1型文法一定是0型文法；利用这一特点着手判断，先判断一条产生式是否满足3型文法，如果不是3型文法然后判断是否是2型文法、1型文法、0型文法，直到判断最精确的文法类型。在过程中从一条产生式的0型文法开始判断，若发现上一条规则是符合1型文法，则就从1型文法开始判断，详见源代码。5.实验代码与

9、结果1）、实验代码#define_CRT_SECURE_NO_WARNINGS#include#include#include#include#include#includeusingnamespacestd;constintSTRING_MAX_LENGTH=10;/*一条规则*/structPrinciple{stringleft;stringright;Principle(constchar*l,constchar*r):left(

10、l),right(r){}};/*文法的四元组形式，同时将该文法类型也作为其属性*/structGrammer{setVn;setVt;vectorP;charS;intflag;//文法类型Grammer(void):flag(-1){}};/*输入规则*/voidinput(vector&principleSet){charleft[STRING_MAX_LENGTH];charright[STRING_MAX_LENGTH];while(EOF!=scanf("%[

11、^-]->%s",left,right)){getchar();principleSet.push_back(Principle(left,right));}}6/*得到S,Vn,Vt*/voidgetGrammer(Grammer&G){G.S=G.P.front().left.front();G.Vn.clear();G.Vt.clear();for(unsignedi=0;i

12、+j){charv=prcp.left[j];!isupper(v)?G.Vt.insert(v):G.Vn.insert(v);}for(unsignedj=0;j