编译原理及其习题解答(武汉大学出版社)课件chap2.ppt

第二章 文法和语言 补充： 文法的直观概念(1/5) 直观文法举例(2/5) 例如：简单的汉语句子的构成规则 句子::= 主语 谓语 主语::= 代词 | 名词 代词::= 我 | 你 | 他 名词::=王明| 大学生|工人|英语 谓语::=动词 直接宾语 动词::=是 |学习 直接宾语::=代词 | 名词 则 “我是大学生”是句子 程序设计语言对文法的要求(4/5) 这些规则必须是准确的，易于理解的，且应当有相当强的描述能力，足以描述各种不同的结构。 文法作用(5/5) （1）定义句子的结构； （2）用适当条数的规则把语言的全部句子描述出来，以有穷集合刻划无穷集合。 （5） 符号串的方幂 同一符号串的连接可以写成方幂的形式。 设x是符号串，把x自身连接n次得到的符号串z，即z=xx…xx，称为符号串x的方幂，记作z=xn，有： x0=ε x1= x x2= xx x3= xxx … 当n0时， xn ＝x xn-1 = xn-1 x 定义 0型文法（或称短语文法, phrase structure grammar,PSG） G=( VN, VT, P, S)是0型文法是指： 若它的每个产生式α→β是这样一种结构: α∈(VN∪VT)+且至少含有一个非终结符， β∈(VN∪VT)*。 任何0型文法都是递归可枚举的。 0型文法的能力相当于图灵机（计算机的一种简单的理论模型）。 称L为递归可枚举的：若存在一个产生L的过程。 称L为递归的：若存在一个识别L的算法。 定义 1型文法（或称上下文有关文法,CSG Context Sensitive Grammar） 如果对0型文法加以以下的限制，则可得到1型文法。 设G=( VN, VT, P, S)为一文法，若G的任何产生式α→ β均满足|α| ≤ |β| (指符号串的长度)，仅仅S→ ε例外。 课本P24例2.2。 定义 2型文法（或称上下文无关文法，CFG Context Free Grammar） 设G=( VN, VT, P, S)为一文法，若G的任何产生式形似A→ β，其中A ∈ VN， β ∈ (VN∪VT)+ 。 上下文无关文法的说明 　　上下文无关，顾名思义就是非终结符的替换可以不必考虑上下文。由于这种文法对程序已基本可以描述，因此，上下文无关文法常简称为文法。 　　上下文无关文法最多能生成anbn类特征的语言，不能生成anbncn类特征的语言。 左线性文法 设G=( VN, VT, P, S)为一文法，若G的任何产生式A→α或A→ Bα ，其中A、B ∈ VN ，α∈ VT* 。 2.3.2 文法分类的意义 自动机 具有有穷描述的某种机器，对于给定文法，可接收某个终结符号串，并确定是否能从该文法推导出来。 分析器 判定（分析）一个终结符号串是否是某个文法的句子，给出给定串的推导序列，完成此工作的自动机，称为分析器。 正规文法与自动机 自动机由一个有穷状态集和一个状态对偶之间的转换集组成。 CFG与自动机 CFG可以由下推自动机来识别。 文法分类的意义 文法的分类，对于实现程序设计语言的编译程序， 具有重要意义。 语言的词法规则：用正规文法（RG）描述。 语言的语法规则：局部语法用CFG描述； 全局语法用CSG描述。 语言的语义描述：CSG（实际定义采用CFG）。 编译程序在实现时，一般采用CFG识别技术（易实现，高效）。 2.3.3 文法举例 2.3.3 文法举例(2) 2.3.3 文法举例(3) 2.3.4 文法的构造（补充） 以{an}、{anbn}、{anbncn}、{ωωr｜ω∈{0|1}*}的构造为基础，以它们为依据来构造其它文法。 给出下面语言相应的文法 1、L1={abna | n≥ 0}； 2、L2={an bn+mcm | m,n≥ 1}； 3、L3={anbnci | n≥ 1，i ≥ 0}； 4、L4={aibncn | n≥ 1，i ≥ 0}； 5、L5={anbncn|n ≥ 1 } 文法的构造的分析（补充） 类型：①A →□A或A →A□对应于{an| n≥ 1}类 　　　② A →□A◇对应于{anbcn| n≥ 1}类 　　　③ 分步：先用A →□A◇对应于{an(BC)n| n≥ 1}，然后再通过改变排列顺序，最终实现 {anbncn| n≥