编译原理第2章文法和语言.ppt

第2章 文法和语言 A thousand-li journey is started by taking the first step. 千里之行，始于足下 第2章 文法和语言(P12) 2.1 字母表和符号串 2.2 文法 2.3 推导 2.4 句型和句子 2.5 语言 2.6 递归规则与递归文法 2.7 短语、简单短语和句柄 2.8 语法树 2.9 子树与短语 2.10 由树构造推导过程 2.11 文法的二义性 2.12 有关文法的实用限制 2.13 文法和语言分类 学习重点 1 文法的定义、分类和二义性 2 最左推导、规范推导(或最右推导) 3 语言、句型和句子 4 短语、简单短语(或直接短语)和句柄 5 语法树 形式语言(P12) 如果不考虑语义和语用，只从语法这一侧面来看语言，它是由符合某种语法（用规则定义）的句子构成的集合，这种意义下的语言称作形式语言。 形式语言 形式语言抽象地定义为一个数学系统，即能用数学符号和规则描述的语言。形式语言理论是对符号串集合的表示法、结构及其特性的研究。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。 2.1 字母表和符号串(P12) 2.1 字母表和符号串 2.1 字母表和符号串 2.1 字母表和符号串 2.1 字母表和符号串 2.1 字母表和符号串 2.1 字母表和符号串 2.1 字母表和符号串 2.1 字母表和符号串 2.2 文法 2.2 文法 2.2 文法 2.2 文法 2.2 文法 2.2 文法 2.2 文法 2.2 文法 2.2 文法 2.13文法和语言分类（P26） 2.13文法和语言分类（P26） 2.13文法和语言分类（P26） 2.13文法和语言分类（P27） 2.13文法和语言分类 2.13文法和语言分类 文法的四种分类 2.13文法和语言分类 2.3 推导(P17) 直接推导（?）：α→β是文法G的一个产生式， x,y∈V*，符号串xαy中的非终结符号α用β替换，从而得到符号串xβy，则表示为： xαy? xβy 其中“?”读为“直接推导出”或“直接产生” 。即称xαy直接推导出xβy,或xαy直接产生xβy。若从反方向看，则称xβy直接归约到xαy。显然，文法的产生式右部是其左部的直接推导。 2.3 推导 2.3 推导 推导（ ）：如果存在一直接推导序列 α0 ?α1 ?…… ?αn， 则表示为： α0 αn 其中， “ ”读为“推导出”或“产生”，即α 0推导出或产生αn。若从反方向看，则称αn归约到α0。 n 是推导长度，要求n0 。 2.3 推导 2.3 推导 广义推导（ ）：如果有α0 αn 或α0 =αn, 即n ≥0，则表示为： α0 αn 其中， “ ”读为“广义推导出”或“广义产生”。若从反方向看，则称αn广义归约到α0。 2.3 推导 2.3 推导 2.3 推导 2.4 句型和句子（P18） 2.4 句型和句子 2.4 句型和句子 2.5 语言（P19） 2.5 语言 2.5 语言 2.5 语言 2.5 语言 2.6递归规则与递归文法(P20) 2.6递归规则与递归文法 2.6递归规则与递归文法 2.6递归规则与递归文法 2.6递归规则与递归文法 2.8 语法树(P21) 2.8 语法树 2.8 语法树 2.10 由树构造推导过程（P23） 2.10 由树构造推导过程 2.10 由树构造推导过程 2.10 由树构造推导过程 2.7 短语、简单短语和句柄（P21） 2.7 短语、简单短语和句柄 2.9 子树和短语(P22) 2.9 子树和短语 2.9 子树和短语 2.11 文法的二义性（P23） 2.11 文法的二义性 2.11 文法的二义性 2.11 文法的二义性 2.11 文法的二义性 2.12 有关文法的实用限制（P25） 2.12 有关文法的实用限制 2.12 有关文法的实用限制 2.12 有关文法的实用限制 2.12 有关文法的实用限制 小 结 习题 （P27） 作 业 1 作 业 1 作 业 2 短语：设G[Z]是一文法, w=xuy是一句型,如果有 Z xUy 且U u , 其中U∈Vn , u∈V+,则称u是一个相对于非终