形式语言自动机——上下文无关文法与下推自动机(一)new

《形式语言自动机——上下文无关文法与下推自动机(一)new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1CollegeofComputerScience&Technology,BUPT第四章上下文无关文法与下推自动机推导树和文法的二义性上下文无关文法的变换Chomsky范式Greibach范式下推自动机上下文无关语言的性质2CollegeofComputerScience&Technology,BUPT本章要点上下文无关文法（即2型文法）：产生式形如A→α,A,∪Τ)*所描述的语言称为上下文无关语言。用途：可定义程序设计语言、进行语法分析、简化语言翻译2型文法对应的识别器——下推自动机PDA（PushDownAutomata)由输入带、有限控制器和下推栈

2、构成（书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），递归推理的过程习称为归约

3、；一种是自上而下的方法，称为推导（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

4、）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)7CollegeofComputerScie

5、nce&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归约

6、与推导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推导树用图的方法表示一个句型

7、的推导，这种图称为推导树（也称语法树或语法分析树）。有助于理解语法结构的层次。定义方法：文法的起始符为根，树的枝结点标记是非终结符，叶结点标记为终结符或。若枝结点有直接子孙x1,x2,…,xk，则文法中有生成式A→x1x2…xk10CollegeofComputerScience&Technology,BUPT推导树举例例：（书P124例1）文法S→S+S

8、S*S

9、(S)

10、a，对句子(a*a+a)可有推导树即：推导树是对文法G中一个特定句子形式的派生过程所做的一种自然描述。11CollegeofComputerScience&Technology,