第二章 前后文无关文法及语言.ppt

第二章 前后文无关文法和语言 语言及其表示方法 文法的定义 由文法产生句子 有关定义和记号 语言的形式文法 句型的分析 文法和语言的乔姆斯基分类 重点和难点 重点： 本章中涉及的概念和术语的理解 文法和语言的形式定义 难点： 短语和句柄的识别 二义性文法的判定 2.1 语言及其表示方法 规定一种语言首先要规定它各种构造成分的形式，词汇、句子等的构造规则及表示法。 编译原理则应建立有关语言的数学化（形式化）模型，以便对程序语言进行研究。 定义1：相当大的地区内公众所懂得并使用的“话”，以及组成这些“话”的方法的统一体。 缺点：不够形式化和精确化 定义2：某一个字母表上的符号串的（句子）的集合。 缺点：缺乏语言句子的结构性组成描述， 缺乏判断任一符号串是否为合法句子判断机制。 因此，如果能刻画一个语言句子，就定义了该语言。 1956年，chomsky建立文法的数学模型，对形式化语言和自动机理论的研究取得较大的成果。 1960年。P.Nuaur和J.Boukas首先用BNF成功对ALGOL语言的文法进行了描述，虽然对语义形式化描述不理想，但在程序设计语言的语法描述上有足够的能力。 至此，程序语言就有了形式化表述。 枚举（句子有限） 例：L={We are learning computer science,it is interesting} 数学表示（句子无限） 例:{1，1/2，1/3，……1/n}→{1/n|n∈N} 制定有限条规则，用来产生所需描述语言中的句子全部，这些规则即文法。 建立一种算法能对于任给的符号串，判别是否为给定语言的合法句子——自动机理论。 2.2 文法的定义 ∷=左端的规则由∷=右端的符号串代替： 〈句子〉 ? 〈主语〉〈谓语〉 ? 〈代词〉〈谓语〉  ? 我〈谓语〉  ? 我〈动词〉〈直接宾语〉 ? 我是〈直接宾语〉 ? 我是〈名词〉 ? 我是大学生 英语句子 sentence – subject verb-phrase object subject – This | Computers | I verb-phrase – adverb verb | verb adverb – never verb – is | run | am | tell object – the noun | a noun | noun noun – university | world | cheese | lies This is a university. Computers run the world. I am the cheese. I never tell lies. 2、文法的形式化表示 符号： 表示一个语法单位； ∷=（ – ）表示“定义为”； | 表示为“或” 。 文法：描述语言的形式结构的规则。 产生式 产生式左部 产生式右部 文法的一般构成： 一组终结符号：仅出现在产生式右部的符号 VT 一组非终结符号：至少在产生式左部出现过一次的符号VN 一个开始符号：特殊的非终结符，表示了定义语言中最感兴趣的语法范畴。 S； 一组规则：P G={VT，VN，S，P} 例如 2.3 由文法产生句子 1、推导 〈句子〉 ? 〈主语〉〈谓语〉 ? 〈代词〉〈谓语〉 ?我〈谓语〉 ? …… 过程：文法的开始符号开始，每次把当前串的一个非终结符号用于之对应的产生式右部来代换，得到一个新符号串，称一步推导。 2、推导长度 2.4 有关定义和记号 一、基本定义 1、符号：可以相互区别的记号（元素）。 2、字母表?：符号（元素）的非空有穷集合。 3、符号串：由字母表?中的符号组成的任何有穷序列。 空符号串ε(没有符号的符号串)是?上的符号串。 若x是?上的符号串，a是?的元素，则xa是?上的符号串。 y是?上的符号串，当且仅当它可以由1和2导出。 例如： Σ={a,b} ε，a，b，aa，ab，aabba…都是?上的符号串 三、符号串集合 2.5 语言和文法的形式定义 一个上下文无关文法G定义为四元组(VN，VT，P，S ) 其中： VN：非终结符号(或语法实体，或变量)集；VT：终结符号集；P：