编译原理－何炎祥-第二章.pptVIP

第二章 形式语言概论 本章主要介绍形式语言理论中的一些最基本的概念和基础知识，它是学习以后各章节的基石。 2.1 语言成分 一个语言的成分包括字母表（Alphabet）,文法(Grammar)以及它的语义。 本章将主要讨论字母表、符号串、产生式文法系统以及句子分析等方面的内容。 2.1 语言成分 字母表与符号 ：字母表是元素的非空有穷集合。字母表中的元素称为符号。 符号串及其运算 ： ① 符号串。 ② 符号串的长度。 ③ 符号串的连接。 ④ 符号串集合的乘积。 ⑤ 符号串的方幂。 ⑥ 符号串集合的方幂。 ⑦ 符号串集合的正闭包。 ⑧ 符号串集合的自反闭包。 2.2 产生式文法和语言 文法(Grammar)是定义或描述语言的语法结构的一组形式规则(即语法规则)。一个程序语言的文法的目的就是用适当条数的规则把该程序语言全部成分描述出来。 2.2.1 产生式文法 定义2.1 产生式文法定义成一个四元组G=(VN，VT，S，P)， VT:非空有限的终结符号集(符号表)； VN:非空有限的非终结符号集(变量表)； S:开始符号(识别符号)，是文法G规定的最终目标； P:产生式的集合。 其中VN∩VT= ?，S?VN。我们令V=VN∪VT，则P中产生式的一般形式为 A??|? A?VN 且 ?,? ?V＋ 或 A::=?|? (本书中统一采用“A??|?”的表示方法)。 2.2.2 上下文无关文法 定义2.2 文法G是一个四元组，G=(VN，VT，P，S)，其中，VN、VT分别是非空有限的非终结符号集和终结符号集，VN∩VT=?，P是产生式集，S?VN称为文法的识别符号或开始符号。开始符号S必须至少在某个产生式的左部出现一次。 2.2.3 上下文无关文法定义的语言 定义2.3 设文法G=(VN，VT，P，S)，A→?是其中的产生式，若有符号串?, ??(VN∪VT)*，使得 U=?A? ，w=??? 则称w为U应用产生式A→?所得到的直接推导(Direct Deriavtion)，也称w可直接归约到U,记为 U?w ,即 ?A????? 特别的，当?=?=?时，有 A?? 即每个产生式的右部都是它左部的直接推导，符号“?”仅指“推导一步”的意思。 2.2.3 上下文无关文法定义的语言 定义2.4 如果存在一个直接推导的序列 v=?0??1??2?…??n=w （n0） 则称符号串w为符号串u的一个推导，或称“w可归约到v”记为 定义2.5 表示 或v=w。 2.3 文法的分类 2.3.1 文法分类 0型文法 1型文法（上下文有关文法） 2型文法（上下文无关文法） 3型文法（右线性文法和正规文法） 2.3.2 文法分类的意义 2.3.3 文法举例 0型文法 在2.2.1节中定义的文法即为0型文法(无限制的文法)。其产生式具有以下形式： ?→? 其中，??(VN∪VT)+，??(VN∪VT)* 1型文法（上下文有关文法） 1型文法G的产生式具有以下形式： ?→? 其中?=?1 A?2；?=?1??2；?1，?2?(VN∪VT)*；A?VN；??(VN∪VT)+。 例 1型文法G6=(VN，VT，P，S) 其中， VN={S，X，Y，Z} VT=（x，y，z） P={S→xSYZ?xYZ, xY→xy，yY→yy, yZ→yz ZY→YZ, zZ→zz} 2型文法（上下文无关文法） 在1型文法的产生式中上下文?1和?2用空符号串?代替，则有以下形式的产生式称为2型文法： A→? 其中，A?VN，??(VN∪VT)+。 例 2型文法G3=(VN，VT，P，E) 其中， VN={E，T，F} VT={+，*，(，)，i } P={E→E+T?T，T→T?F?F，F→(E) ?i } 3型文法（右线性文法和正规文法） 如果P中的产生式只含有下面的两种形式： A→a A→aB 则称该文法为右线性文法， 其中，A，B?VN，a?VT*。 例 右线性文法 G4=(VN，VT，P，S) 其中， VN={S，A