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

1、1College of Computer Science & Technology, BUPT第四章第四章 上下文无关文法与下推自动机上下文无关文法与下推自动机 推导树和文法的二义性推导树和文法的二义性上下文无关文法的变换上下文无关文法的变换 Chomsky范式范式Greibach范式范式 下推自动机下推自动机上下文无关语言的性质上下文无关语言的性质2College of Computer Science & Technology, BUPT本章要点本章要点上下文无关文法（即上下文无关文法（即2型文法）：型文法）： 产生式形如产生式形如 A, A, )* 所描述的语言称为上下文

2、无关语言。所描述的语言称为上下文无关语言。用途：用途：可定义程序设计语言、进行语法分析、简化语言可定义程序设计语言、进行语法分析、简化语言翻译翻译 2型文法对应的识别器型文法对应的识别器下推自动机下推自动机 PDA（Push Down Automata)由输入带、有限由输入带、有限控制器和下推栈构成（书控制器和下推栈构成（书P152 图）图）3College of Computer Science & Technology, BUPT 回顾：回顾：在第一讲中介绍过如下内容在第一讲中介绍过如下内容 设设 T= 0, 1 ， L = 0n1n n 1 ，如如 0011, 000111, 0

3、1 L, 而而10, 1001 , , 010 L . 如下是一个可接受该语言的上下文无关文法如下是一个可接受该语言的上下文无关文法 S 01 S 0S1 但没有任何有限自动机能够接受语言但没有任何有限自动机能够接受语言L.4College of Computer Science & Technology, BUPT归约与推导的概念: 推理字符串是否属于文法所定义的语言推理字符串是否属于文法所定义的语言 一种是自下而上的方法，称为一种是自下而上的方法，称为递归推理递归推理(recursive inference），），递归推理的过程习称为递归推理的过程习称为归约归约； 一种是自上而下的

4、方法，称为一种是自上而下的方法，称为推导推导（derivation）.归约过程归约过程 将产生式的右部（将产生式的右部（body）替换为产生式替换为产生式的左部（的左部（ head ）. 推导过程推导过程 将产生式的左部（将产生式的左部（ head ）替换为产生替换为产生式的右部（式的右部（ body ）.4.1 推导树和二义性 5College of Computer Science & Technology, BUPT归约与推导 归约过程归约过程举例举例 对于对于CFG Gexp = (E,O, (, ), , v, d , P , E ) ，P 为为 （1）E EOE （2） E

5、 (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）E6College of Computer Science & Technology, 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、 （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)7College of Computer Science & Technology, BUPT归约与推导E EOEE (E)E vE dO O 最左推导最左推导(leftmost derivations) 若推导过程的每一步总是替换出现在最左边的非终结符，若推导过程的每一步总是替换出现在最左边的非终结符， 则这样的推导称为则这样的推导称为最左推导最左推导. 为

7、方便，最左推导关系用为方便，最左推导关系用 表示，其传递闭包用表示，其传递闭包用表示表示. 如对于文法如对于文法Gexp ，下面是关于下面是关于 v (vd) 的一个最左推导的一个最左推导： lmlmv (vd)v (vE)v (EOE)EOEEv (E)vOEv Ev (vOE) lm lm lm lm lm lm lm lm8College of Computer Science & Technology, BUPT归约与推导E EOEE (E)E vE dO O 最右推导最右推导(rightmost derivations) 若若推导推导过程的每一步总是替换出现在最右边的非终结符

8、，过程的每一步总是替换出现在最右边的非终结符， 则这样的推导称为则这样的推导称为最右推导最右推导. 为方便，最右推导关系用为方便，最右推导关系用 表示，其传递闭包用表示，其传递闭包用表示表示. 如对于文法如对于文法Gexp ，下面是关于下面是关于 v (vd) 的一个最右推导的一个最右推导： rmrmv (vd)E (vd)EO(Ed)EOEEEO(EOd)EO(E)EO(EOE)EO(vd) rm rm rm rm rm rm rm rm9College of Computer Science & Technology, BUPT推导树推导树用图的方法表示一个句型的推导，这种图称为推

9、导用图的方法表示一个句型的推导，这种图称为推导树（也称语法树或语法分析树）。有助于理解语法树（也称语法树或语法分析树）。有助于理解语法结构的层次。结构的层次。定义方法：定义方法：n文法的起始符为根，树的枝结点标记是非终结符，文法的起始符为根，树的枝结点标记是非终结符，叶结点标记为终结符或叶结点标记为终结符或 。n若枝结点有直接子孙若枝结点有直接子孙x1, x2, xk，则文法中有生成则文法中有生成式式Ax1 x2xk10College of Computer Science & Technology, BUPT 推导树举例例：例：（书（书P124 例例1）文法文法SS+S | S*S

10、|(S)| a ，对句子对句子 (a*a+a) 可有推导树可有推导树a aa aS S( S )( S )S + SS + SS * SS * Sa aa aa aS S( S )( S )S * SS * SS + SS + Sa a即：推导树是对文法G中一个特定句子形式特定句子形式的派生过程所做的一种自然描述。 11College of Computer Science & Technology, BUPT边缘叶子叶子从左向右组成的字符串称为推导树的边缘。从左向右组成的字符串称为推导树的边缘。如图如图x1 y1 y2 x3 xm xm+1 xn-1 y3 y4 y5是树的边缘是树的

11、边缘y1y1y2y2S SA BA Bx1 Xx1 X2 2 . x . xm m.x xm+1m+1 . Xn . Xny3y3y4y4y5y512College of Computer Science & Technology, BUPT(1) E EOE(2) E (E)(3) E v(4) E d(5) O (6) O 归约过程自下而上构造了一棵树归约过程自下而上构造了一棵树 如对于文法如对于文法Gexp ，关于关于 v (vd) 的一个归约过程可以认为是构造了如下一棵树的一个归约过程可以认为是构造了如下一棵树：v (vd)（4）v (vE)（6）vO(vE)（3）vO(EE)

12、（5）vO(EOE)（1）vO(E)（2）vOE（3）EOE（1）EEEOEEOEEdv() v13College of Computer Science & Technology, BUPT(1) E EOE(2) E (E)(3) E v(4) E d(5) O (6) O 推导过程自上而下构造了一棵树推导过程自上而下构造了一棵树 如对于文法如对于文法Gexp ，关于关于 v (vd) 的一个推导过程可以认为是构造了如下一棵树的一个推导过程可以认为是构造了如下一棵树：Edv vOEEE()EEOv (vd)（4）v (vE)（6）E (E)（3）（1）v (EOE)（5）（3）EO

13、E（1）EE E（2）v (E)v (EE)14College of Computer Science & Technology, BUPT归约、推导与分析树之间关系 三者之间的关系三者之间的关系 设设 CFG G = (V, T, P , S ). 以下命题是相互等价的：以下命题是相互等价的： (1) 字符串字符串 w T* 可以归约（递归推理）到非终结符可以归约（递归推理）到非终结符A； (2) A w； (3) A w； (4) A w； (5) 存在一棵根结点为存在一棵根结点为 A 的分析树，其边缘为的分析树，其边缘为 w. lm rm15College of Computer

14、 Science & Technology, BUPT定理定理：设设2型文法型文法G=（N，T，P，S），），如果存在如果存在S=+ ，当且仅当文法当且仅当文法G中有一棵边缘为中有一棵边缘为的推导树。的推导树。证明：证明：需证明对任意枝结点需证明对任意枝结点BN，有有B=* 当且仅当存在当且仅当存在边缘为边缘为的的B树（根为树（根为B的树）的树）子树概念：子树概念：一棵派生树的子树，是树中的某个顶点连同它的全部一棵派生树的子树，是树中的某个顶点连同它的全部后裔，以及连接这些后裔的边。后裔，以及连接这些后裔的边。归约、推导与分析树之间关系16College of Computer Sci

15、ence & Technology, BUPT证明步骤：证明步骤：1. 证当证当是是B树边缘时，有树边缘时，有B =* 设设B树边缘为树边缘为，对树中枝结点数目对树中枝结点数目m作归纳证明。作归纳证明。2. 设有设有B = * ，证明存在一棵边缘为证明存在一棵边缘为的的B树。树。对对推导步数推导步数作归纳作归纳 17College of Computer Science & Technology, BUPT1. 证当证当是是B树边缘时，有树边缘时，有B =* 设设B树边缘为树边缘为，对树中枝结点数目对树中枝结点数目m作归纳证明。作归纳证明。wAX1X2X3w1w2w3A基础基础

16、 m为为 1. 分析树一定如分析树一定如 右图所示，必定有产生右图所示，必定有产生 式式A w. 因此，因此， A w. 归纳归纳 m大于大于 1 的分析树一定的分析树一定 如右图所示，必定有产如右图所示，必定有产 生式生式 A X1X2Xk . 存在存在 w1,w2,wk，wi 是是Xi子树子树 的边缘（的边缘（1 i k），），且且 w = w1w2wk， 由归纳由归纳 假设，假设， Xi wi（1 i k）. 在此基础上易证得在此基础上易证得A w. 18College of Computer Science & Technology, BUPT2. 设有设有B = * ，证明存

17、在一棵边缘为证明存在一棵边缘为的的B树。树。对对推导步数推导步数作归纳作归纳 基础基础 步数为步数为 1. 一定有产生式一定有产生式 A w . w 可以归约到可以归约到 A.归纳归纳 设步数大于设步数大于 1，第一步使用了产生式，第一步使用了产生式A X1X2Xk . 该推导如该推导如 A X1X2Xk w . 可以将可以将 w 分成分成 w = w1w2wk，其中其中 (a) 若若 Xi 为终结符，则为终结符，则 wi = Xi. (b) 若若 Xi 为非终结符，则为非终结符，则 Xi wi. 由归纳假设，由归纳假设， wi 可以归约到可以归约到 Xi . 这样，这样，wi 或者为或者为X

18、i，或者可以归约到或者可以归约到 Xi ，使用产生使用产生 式式A X1X2Xk ，得出得出w 可以归约到可以归约到 A. 19College of Computer Science & Technology, BUPT定义定义: 2型文法是二义的型文法是二义的,当且仅当对于句子当且仅当对于句子L(G),存在两棵不存在两棵不同的具有边缘为同的具有边缘为的推导树。的推导树。 (即：如果文法是二义的即：如果文法是二义的, 那么它所产生的某个句子必然能从那么它所产生的某个句子必然能从不同的最左不同的最左(右右)推导推出推导推出)。例例: (书书P124 例例1)句子句子(a*a+a)有二棵不同的推导树有二棵不同的推导树. (相当于一个先算乘法相当于一个先算乘法,一一个先算加法个先算加法.)注意注意: 可有二个文法可有二个文法,一个有二义一个有二义,一个无二