1、12023/6/7School of Computer Science,BUPT第四章第四章 上下文无关文法与下推自动机上下文无关文法与下推自动机 推导树和文法的二义性推导树和文法的二义性上下文无关文法的变换上下文无关文法的变换 Chomsky范式范式Greibach范式范式 下推自动机下推自动机上下文无关语言的性质上下文无关语言的性质22023/6/7School of Computer Science,BUPT本章要点本章要点上下文无关文法（即上下文无关文法（即2型文法）：型文法）：产生式形如生式形如 A,A,)*所描述的所描述的语言称言称为上下文无关上下文无关语言。言。用途：用途：可可定
2、定义程程序序设计语言言、进行行语法法分分析析、简化化语言言翻翻译 2型文法型文法对应的的识别器器下推自下推自动机机 PDA（Push Down Automata)由由输入入带、有有限限控制器和下推控制器和下推栈构成构成32023/6/7School of Computer Science,BUPT 回回顾：在第一在第一讲中介中介绍过如下内容如下内容 设 T=0,1 ，L=0n1n n 1，如如 0011,000111,01 L,而而10,1001,010 L.如下是一个可接受如下是一个可接受该语言的上下文无关文法言的上下文无关文法 S 01 S 0S1 但没有任何有限自但没有任何有限自动机能机
3、能够接受接受语言言L.42023/6/7School of Computer Science,BUPT归约与推导的概念:推理字符串是否属于文法所定推理字符串是否属于文法所定义的的语言言 一种是自下而上的方法，称一种是自下而上的方法，称为递归推理推理(recursive inference），），递归推理的推理的过程程习称称为归约；一种是自上而下的方法，称一种是自上而下的方法，称为推推导（derivation）.归约过程程 将将产生式的右部（生式的右部（body）替替换为产生生式的左部（式的左部（head）.推推导过程程 将将产生式的左部（生式的左部（head）替替换为产生式的右部（生式的右部（
4、body）.4.1 推导树和二义性 52023/6/7School of Computer Science,BUPT归约与推导 归约过程归约过程举例举例 对于对于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 (vd)的一个归约过程为的一个归约过程为v (vd)（4）v (vE)（6）vO(vE)（3）vO(EE)（5）vO(EOE)（1）vO(E)（2）vOE（3）EOE（1）E62023/6/7School of Computer Science,BUPT
5、归约与推导 推导过程推导过程举例举例 对于对于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 (vd)的一个推导过程为的一个推导过程为v (vd)（4）v (vE)（6）E (E)（3）（1）v (EOE)（5）（3）EOE（1）EE E（2）v (E)v (EE)72023/6/7School of Computer Science,BUPT归约与推导E EOEE (E)E vE dO O 最左推导最左推导(leftmost derivations)若推
6、若推导过程的每一步程的每一步总是替是替换出出现在最左在最左边的非的非终结符，符，则这样的推的推导称称为最左推最左推导.为方便，最左推方便，最左推导关系用关系用 表示，其表示，其传递闭包用包用表示表示.如如对于文法于文法Gexp，下面是关于下面是关于 v (vd)的一个最左推的一个最左推导：lmlmv (vd)v (vE)v (EOE)EOEEv (E)vOEv Ev (vOE)lm lm lm lm lm lm lm lm82023/6/7School of Computer Science,BUPT归约与推导E EOEE (E)E vE dO O 最右推导最右推导(rightmost der
7、ivations)若若推导推导过程的每一步总是替换出现在最右边的非终结符，过程的每一步总是替换出现在最右边的非终结符，则这样的推导称为则这样的推导称为最右推导最右推导.为方便，最右推导关系用为方便，最右推导关系用 表示，其传递闭包用表示，其传递闭包用表示表示.如对于文法如对于文法Gexp，下面是关于下面是关于 v (vd)的一个最右推导的一个最右推导：rmrmv (vd)E (vd)EO(Ed)EOEEEO(EOd)EO(E)EO(EOE)EO(vd)rm rm rm rm rm rm rm rm92023/6/7School of Computer Science,BUPT推推导树用用图的方
8、法表示一个句型的推的方法表示一个句型的推导，这种种图称称为推推导树（也称（也称语法法树或或语法分析法分析树）。有助于理解）。有助于理解语法法结构的构的层次。次。定定义方法：方法：n文法的起始符文法的起始符为根，根，树的枝的枝结点点标记是非是非终结符，符，叶叶结点点标记为终结符或符或。n若枝若枝结点有直接子点有直接子孙x1,x2,xk，则文法中有生成文法中有生成式式Ax1 x2xk102023/6/7School of Computer Science,BUPT 推导树举例例：例：（书P94 例例1）文法文法SS+S|S*S|(S)|a，对句子句子(a*a+a)可有推可有推导树即：推导树是对文法
9、G中一个特定句子形式特定句子形式的派生过程所做的一种自然描述。112023/6/7School of Computer Science,BUPT边缘叶子叶子从左向右从左向右组成的字符串称成的字符串称为推推导树的的边缘。如如图x1 y1 y2 x3 xm xm+1 xn-1 y3 y4 y5是是树的的边缘122023/6/7School of Computer Science,BUPT(1)E EOE(2)E (E)(3)E v(4)E d(5)O(6)O 归约过程自下而上构造了一棵树归约过程自下而上构造了一棵树 如对于文法如对于文法Gexp，关于关于 v (vd)的一个归约过程可以认为是构造了
10、如下一棵树的一个归约过程可以认为是构造了如下一棵树：v (vd)（4）v (vE)（6）vO(vE)（3）vO(EE)（5）vO(EOE)（1）vO(E)（2）vOE（3）EOE（1）EEEOEEOEEdv()v132023/6/7School of Computer Science,BUPT(1)E EOE(2)E (E)(3)E v(4)E d(5)O(6)O 推导过程自上而下构造了一棵树推导过程自上而下构造了一棵树 如对于文法如对于文法Gexp，关于关于 v (vd)的一个推导过程可以认为是构造了如下一棵树的一个推导过程可以认为是构造了如下一棵树：Edv vOEEE()EEOv (vd)
11、（4）v (vE)（6）E (E)（3）（1）v (EOE)（5）（3）EOE（1）EE E（2）v (E)v (EE)142023/6/7School of Computer Science,BUPT归约、推导与分析树之间关系 三者之间的关系三者之间的关系 设设 CFG G=(N,T,P,S).以下命题是相互等价的：以下命题是相互等价的：(1)字符串字符串 w T*可以归约（递归推理）到非终结符可以归约（递归推理）到非终结符A；(2)A w；(3)A w；(4)A w；(5)存在一棵根结点为存在一棵根结点为 A 的分析树，其边缘为的分析树，其边缘为 w.lm rm152023/6/7Scho
12、ol of Computer Science,BUPT定理定理：设2型文法型文法G=（N，T，P，S），），如果存在如果存在S=+，当且当且仅当文法当文法G中有一棵中有一棵边缘为的推的推导树。证明：明：需需证明明对任意枝任意枝结点点B N，有有B=*当且当且仅当存在当存在边缘为的的B树（根（根为B的的树）子子树概念：概念：一棵派生一棵派生树的子的子树，是，是树中的某个中的某个顶点点连同它的全部同它的全部后裔，以及后裔，以及连接接这些后裔的些后裔的边。归约、推导与分析树之间关系162023/6/7School of Computer Science,BUPT证明步明步骤：1.证当当是是B树边缘时
13、，有，有B=*设B树边缘为，对树中枝中枝结点数目点数目m作作归纳证明。明。2.设有有B=*，证明存在一棵明存在一棵边缘为的的B树。对推推导步数步数作作归纳 172023/6/7School of Computer Science,BUPT1.证当当是是B树边缘时，有，有B=*设B树边缘为，对树中枝中枝结点数目点数目m作作归纳证明。明。wBX1X2X3w1w2w3B基础基础 m为为 1.分析树一定如分析树一定如 右图所示，必定有产生右图所示，必定有产生 式式B w.因此，因此，B w.归纳归纳 m大于大于 1 的分析树一定的分析树一定 如右图所示，必定有产如右图所示，必定有产 生式生式 B X1
14、X2Xk.存存在在 w1,w2,wk，wi 是是Xi子树子树 的边缘（的边缘（1 i k），），且且 w=w1w2wk，由归纳由归纳 假设，假设，Xi wi（1 i k）.在此基础上易证得在此基础上易证得B w.182023/6/7School of Computer Science,BUPT2.设有有B=*，证明存在一棵明存在一棵边缘为的的B树。对推推导步数步数作作归纳 基础基础 步数为步数为 1.一定有产生式一定有产生式 B w.w 可以归约到可以归约到 B.归纳归纳 设步数大于设步数大于 1，第一步使用了产生式，第一步使用了产生式B X1X2Xk.该推导如该推导如 B X1X2Xk w.
15、可以将可以将 w 分成分成 w=w1w2wk，其中其中 (a)若若 Xi 为终结符，则为终结符，则 wi=Xi.(b)若若 Xi 为非终结符，则为非终结符，则 Xi wi.由归纳假设，由归纳假设，wi 可以归约到可以归约到 Xi.这样，这样，wi 或者为或者为Xi，或者可以归约到或者可以归约到 Xi，使用产生使用产生 式式B X1X2Xk，得出得出w 可以归约到可以归约到 B.192023/6/7School of Computer Science,BUPT定定义:2型文法是二型文法是二义的的,当且当且仅当当对于句子于句子 L(G),存在两棵不存在两棵不同的具有同的具有边缘为的推的推导树。(即即：如如果果文文法法是是二二义的的,那那么么它它所所产生生的的某某个个句句子子必必然然能能从不同的最左从不同的最左(右右)推推导推出推出)。例例:(书P97 例例3)句句子子(a*a+a)有有二二棵棵不不同同的的推推导树.(相相当当于于一一个个先先算算乘乘法法,一个先算加法一个先算加法.)注意注意:可可有有二二个个文文法法,一一个个有有二二义,一一个个无无二二义,但但产生生相相同同的的语言言.可否通可否通过变换消除二消除二义性性?无一般的算法无一般的算法!二义性二义性
个人主页
