chomsky文法类型的判断.docxVIP

精品文档 精品文档 PAGE PAGE #欢迎下载 编译原理实验报告 实验名称 Chomsky文法类型判断 实验时间 _2014-4-2 院系 计算机科学与技术学院 班级 _2011 级科技（3）班 学号 _ 姓名 张练钢 1. 实验目的 （ 1）通过实验进一步理解 chomsky 文法类型判断的的依据，理解每个类型文法 的特点。 （2）进一步理解 4 种文法类型之间的包含关系。 （3）体会这种理论对于计算机科学发展的深刻影响，特别是对程序设计语言的 设计、编译方法和计算复杂性等方面的重大作用。 通过上机实现文法类型的自动 判别。 2. 实验原理 1．0 型文法（短语文法） 如果对于某文法 G，P 中的每个规则具有下列形式： u:: = v 其中u€ V+, v € V,则称该文法G为0型文法或短语文法，简写为 PSG 0型文法或短语结构文法的相应语言称为 0型语言或短语结构语言Loo这种 文法由于没有其他任何限制， 因此 0 型文法也称为无限制文法， 其相应的语言称 为无限制性语言。任何0型语言都是递归可枚举的，故0型语言又称递归可枚举 集。这种语言可由图灵机（Turning ）来识别。 2．1 型文法（上下文有关文法） 如果对于某文法 G， P 中的每个规则具有下列形式： xUy:: = xuy 其中U€ M； u€ V+; x, y € V,则称该文法G为1型文法或上下文有关文法， 也称上下文敏感文法，简写为 CSGo 1型文法的规则左部的U和右部的u具有相同的上文x和下文y，利用该规 则进行推导时，要用u替换U,必须在前面有x和后面有y的情况下才能进行， 显示了上下文有关的特性。 1型文法所确定的语言为1型语言Li, 1型语言可由线性有界自动机来识别。 3．2 型文法（上下文无关文法） 如果对于某文法 G， P 中的每个规则具有下列形式： U :: = u 其中U€ Vn； u€ /,则称该文法G为2型文法或上下文无关文法，简写为 CFGo 按照这条规则， 对于上下文无关文法， 利用该规则进行推导时， 无需考虑非 终结符U所在的上下文，总能用u替换U,或者将u归约为U,显示了上下文无 关的特点。 2型文法所确定的语言为2型语言L2, 2型语言可由非确定的下推自动机来 识别。 一般定义程序设计语言的文法是上下文无关的。如 C语言便是如此。因此， 上下文无关文法及相应语言引起了人们较大的兴趣与重视。 4. 3型文法(正则文法，线性文法) 如果对于某文法G, P中的每个规则具有下列形式： U :: = T 或 U :: = WT 其中T€ VT; U,WE 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 型；即 Lo 二 L i 二 L 2 二 L 3..实验内容 理解四种文法类型的特点，并利用他们之间包含关系 0型二1型二2 型二3型；即L0二L1二L2二L对所属类型作出判断。 通过编程自动实现将输入的文法判断出其所属类型。 实验心得 本实验的上机实现需注意一下几点： 数据的表示，利用struct co n{ stri ng front; stri ng end; };//定义每个产生式的结构如 A::=a 则front=A,end=a; 因为每个文法都有多个产生式，我们将这多个文法依次存入一个 stri ng类 型的test数组中，然后再将每个产生式分解成前端和后端的格式以便于分析每 个产生式所属的类型。 在对文法进行判断前先对每个产生式作出判断，那么所有产生式中文 精品文档 精品文档 PAGE PAGE # 欢。迎下载 法类型最低的那个产生式所属的类型即为该文法所属的类型。 （3）在对每个每个产生的类型做出判断时要充分利用四种文法类型之间的 包含关系以简化程序。 如 3 型文法和 2 型文法的产生前端都为一个非终端符我们 可以先利用这个特点先判断