6推导树与文法二义性.ppt

fall 2001 第四章 上下文无关文法与下推自动机 推导树和文法的二义性 上下文无关文法的变换 Chomsky范式 Greibach范式 下推自动机 上下文无关语言的性质 本章要点 上下文无关文法（即2型文法）： 产生式形如 A→α, A??, ????∪Τ)* 所描述的语言称为上下文无关语言。 用途： 可定义程序设计语言、进行语法分析、简化语言翻译? 2型文法对应的识别器——下推自动机 PDA（Push Down Automata)由输入带、有限控制器和下推栈构成（书P152 图） 归约与推导的概念: 归约与推导 归约与推导 归约与推导 归约与推导 推导树 用图的方法表示一个句型的推导，这种图称为推导树（也称语法树或语法分析树）。有助于理解语法结构的层次。 定义方法： 文法的起始符为根，树的枝结点标记是非终结符，叶结点标记为终结符或?。 若枝结点有直接子孙x1, x2,…, xk，则文法中有生成式A→x1 x2…xk 推导树举例 例：（书P124 例1） 文法S→S+S | S*S |(S)| a ， 对句子 (a*a+a) 可有推导树 边缘 叶子从左向右组成的字符串称为推导树的边缘。 如图 x1 y1 y2 x3? xm xm+1? xn-1 y3 y4 y5是树的边缘 定理： 设2型文法G=（N，T，P，S），如果存在S=+ ω，当且仅当文法G中有一棵边缘为ω的推导树。 证明： 需证明对任意枝结点B∈N，有B=* ω当且仅当存在边缘为ω的B树（根为B的树） 子树概念： 一棵派生树的子树，是树中的某个顶点连同它的全部后裔，以及连接这些后裔的边。 证明步骤： 1. 证当ω是B树边缘时，有B =* ω 设B树边缘为ω，对树中枝结点数目m作归纳证明。 2. 设有B =?* ω，证明存在一棵边缘为ω的B树。 对推导步数作归纳 1. 证当ω是B树边缘时，有B =* ω 设B树边缘为ω，对树中枝结点数目m作归纳证明。 2. 设有B =?* ω，证明存在一棵边缘为ω的B树。 对推导步数作归纳 定义: 2型文法是二义的,当且仅当对于句子ω∈L(G),存在两棵不同的具有边缘为ω的推导树。 (即：如果文法是二义的, 那么它所产生的某个句子必然能从不同的最左(右)推导推出)。 例: (书P124 例1) 句子(a*a+a)有二棵不同的推导树. (相当于一个先算乘法,一个先算加法.) 注意: 可有二个文法,一个有二义,一个无二义,但产生相同的语言. 可否通过变换消除二义性? —— 无一般的算法! 对于前缀表达式文法G1: E::= – EE E::= – E E::= a | b | c 画出文法的句子 – – a – bc 的所有可能语法树。 *College of Computer Science Technology, BUPT 回顾：在第一讲中介绍过如下内容 设 T= ? 0, 1 ?， L = ? 0n1n ? n ? 1?， 如 0011, 000111, 01 ? L, 而10, 1001 , ?, 010 ? L . 如下是一个可接受该语言的上下文无关文法? S ? 01 S ? 0S1 但没有任何有限自动机能够接受语言L. 推理字符串是否属于文法所定义的语言 一种是自下而上的方法，称为递归推理(recursive inference），递归推理的过程习称为归约； 一种是自上而下的方法，称为推导（derivation）. 归约过程 将产生式的右部（body）替换为产生式的左部（ head ）. 推导过程 将产生式的左部（ head ）替换为产生式的右部（ body ）. 4.1 推导树和二义性 归约过程举例 对于CFG Gexp = ({E,O}, { (, ),＋, ?, v, d }, P , E ) ，P 为 （1）E ? EOE （2） E ? (E) （3） E ? v （4） E ? d （5） O ?＋ （6） O ? ? 递归推理出字符串 v ?(v＋d) 的一个归约过程为 v ?(v＋d) （4） v ?(v＋E) （6） vO(v＋E) （3） vO(E＋E) （5） vO(EO