形式语言与自动机课件上下文无关文法与下推自动机

1CollegeofComputerScience&Technology,BUPT第四章上下文无关文法与下推自动机推导树和文法的二义性上下文无关文法的变换Chomsky范式Greibach范式下推自动机上下文无关语言的性质2CollegeofComputerScience&Technology,BUPT本章要点上下文无关文法（即2型文法）：产生式形如A→α,A,∪Τ)*所描述的语言称为上下文无关语言。用途：可定义程序设计语言、进行语法分析、简化语言翻译2型文法对应的识别器——下推自动机PDA（PushDownAutomata)由输入带、有限控制器和下推栈构成（书P152图）3CollegeofComputerScience&Technology,BUPT回顾：在第一讲中介绍过如下内容设T=0,1，L=0n1nn1，如0011,000111,01L,而10,1001,,010L.如下是一个可接受该语言的上下文无关文法S01S0S1但没有任何有限自动机能够接受语言L.4CollegeofComputerScience&Technology,BUPT归约与推导的概念:推理字符串是否属于文法所定义的语言一种是自下而上的方法，称为递归推理(recursiveinference），递归推理的过程习称为归约；一种是自上而下的方法，称为推导（derivation）.归约过程将产生式的右部（body）替换为产生式的左部（head）.推导过程将产生式的左部（head）替换为产生式的右部（body）.4.1推导树和二义性5CollegeofComputerScience&Technology,BUPT归约与推导归约过程举例对于CFGGexp=({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(EOE)（1）vO(E)（2）vOE（3）EOE（1）E6CollegeofComputerScience&Technology,BUPT归约与推导推导过程举例对于CFGGexp=({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）E(E)（3）（1）v(EOE)（5）（3）EOE（1）EEE（2）v(E)v(E＋E)7CollegeofComputerScience&Technology,BUPT归约与推导EEOEE(E)EvEdO＋O最左推导(leftmostderivations)若推导过程的每一步总是替换出现在最左边的非终结符，则这样的推导称为最左推导.为方便，最左推导关系用表示，其传递闭包用表示.如对于文法Gexp，下面是关于v(v＋d)的一个最左推导：lmlmv(v＋d)v(v＋E)v(EOE)EOEEv(E)vOEvEv(vOE)lmlmlmlmlmlmlmlm8CollegeofComputerScience&Technology,BUPT归约与推导EEOEE(E)EvEdO＋O最右推导(rightmostderivations)若推导过程的每一步总是替换出现在最右边的非终结符，则这样的推导称为最右推导.为方便，最右推导关系用表示，其传递闭包用表示.如对于文法Gexp，下面是关于v(v＋d)的一个最右推导：rmrmv(v＋d)E(v＋d)EO(E＋d)EOEEEO(EOd)EO(E)EO(EOE)EO(v＋d)rmrmrmrmrmrmrmrm9CollegeofComputerScience&Technology,BUPT推导树用图的方法表示一个句型的推导，这种图称为推导树（也称语法树或语法分析树）。有助于理解语法结构的层次。定义方法：文法的起始符为根，树的枝结点标记是非终结符，叶结点标记为终结符或。若枝结点有直接子孙x1,x2,…,xk，则文法中有生成式A→x1x2…xk10CollegeofComputerScience&Technology,BUPT推导树举例例：（书P124例1）文法S→S+S|S*S|(S)|a，对句子(a*a+a)可有推导树aaS(S)S+SS*SaaaS(S)S*SS+Sa即：推导树是对文法G中一个特定句子形式的派生过程所做的一种自然描述。11CollegeofComputerScience&Technology,BUPT边缘叶子从左向右组成的字符串称为推导树的边缘。如图x1y1y2x3xmxm+1xn-1y3y4y5是树的边缘y1y2SABx1X2...xm......xm+1...Xny3y4y512CollegeofComputerScience&Technology,BUPT(1)EEOE(2)E(E)(3)Ev(4)Ed(5)O＋(6)O归约过程自下而上构造了一棵树如对于文法Gexp，关于v(v＋d)的一个归约过程可以认为是构造了如下一棵树：v(v＋d)（4）v(v＋E)（6）vO(v＋E)（3）vO(E＋E)（5）vO(EOE)（1）vO(E)（2）vOE（3）EOE（1）EEEOEEOEEd＋v()v13CollegeofComputerScience&Technology,BUPT(1)EEOE(2)E(E)(3)Ev(4)Ed(5)O＋(6)O推导过程自上而下构造了一棵树如对于文法Gexp，关于v(v＋d)的一个推导过程可以认为是构造了如下一棵树：Ed＋vvOEEE()EEOv(v＋d)（4）v(v＋E)（6）E(E)（3）（1）v(EOE)（5）（3）EOE（1）EEE（2）v(E)v(E＋E)14CollegeofComputerScience&Technology,BUPT归约、推导与分析树之间关系三者之间的关系设CFGG=(V,T,P,S).以下命题是相互等价的：(1)字符串wT*可以归约（递归推理）到非终结符A；(2)Aw；(3)Aw；(4)Aw；(5)存在一棵根结点为A的分析树，其边缘为w.lmrm15CollegeofComputerScience&Technology,BUPT定理：设2型文法G=（N，T，P，S），如果存在S=+ω，当且仅当文法G中有一棵边缘为ω的推导树。证明：需证明对任意枝结点B∈N，有B=*ω当且仅当存在边缘为ω的B树（根为B的树）子树概念：一棵派生树的子树，是树中的某个顶点连同它的全部后裔，以及连接这些后裔的边。归约、推导与分析树之间关系16CollegeofComputerScience&Technology,BUPT证明步骤：1.证当ω是B树边缘时，有B=*ω设B树边缘为ω，对树中枝结点数目m作归纳证明。2.设有B=*ω，证明存在一棵边缘为ω的B树。对推导步数作归纳17CollegeofComputerScience&Technology,BUPT1.证当ω是B树边缘时，有B=*ω设B树边缘为ω，对树中枝结点数目m作归纳证明。wAX1X2X3w1w2w3……A基础m为1.分析树一定如右图所示，必定有产生式Aw.因此，Aw.归纳m大于1的分析树一定如右图所示，必定有产生式AX1X2…Xk.存在w1,w2,…,wk，wi是Xi子树的边缘（1ik），且w=w1w2…wk，由归纳假设，Xiwi（1ik）.在此基础上易证得Aw.18CollegeofComputerScience&Technology,BUPT2.设有B=*ω，证明存在一棵边缘为ω的B树。对推导步数作归纳基础步数为1.一定有产生式Aw.w可以归约到A.归纳设步数大于1，第一步使用了产生式AX1X2…Xk.该推导如AX1X2…Xkw.可以将w分成w=w1w2…wk，其中(a)若Xi为终结符，则wi=Xi.(b)若Xi为非终结符，则Xiwi.由归纳假设，wi可以归约到Xi.这样，wi或者为Xi，或者可以归约到Xi，使用产生式AX1X2…Xk，得出w可以归约到A.19CollegeofComputerScience&Technology,BUPT定义:2型文法是二义的,当且仅当对于句子ω∈L(G),存在两棵不同的具有边缘为ω的推导树。(即：如果文法是二义的,那么它所产生的某个句子必然能从不同的最左(右)推导推出)。例:(书P124例1)句子(a*a+a)有二棵不同的推导树.(相当于一个先算乘法,一个先算加法.)注意:可有二个文法,一个有二义,一个无二义,但产生相同的语言.可否通过变换消除二义性?——无一般的算法!二义性20CollegeofComputerScience&Technology,BUPT对于前缀表达式文法G1:E::=–EEE::=–EE::=a|b|c画出文法的句子––a–bc的所有可能语法树。课堂练习21CollegeofComputerScience&Technology,BUPT作业Ch4习题：1.2.3.