slide02

FL&A第二讲上下文无关文法与上下文无关语言FL&A上下文无关文法的基本概念归约与推导上下文无关语言文法与语言的Chomsky分类语法分析树归约、推导与分析树之间关系上下文无关文法与上下文无关语言文法和语言的二义性FL&A回顾：在第一讲中介绍过如下内容设=0,1，L=0n1nn1，如0011,000111,01L,而10,1001,,010L.如下是一个可接受该语言的上下文无关文法S01S0S1上下文无关文法的基本概念FL&A另一个例子EEOEE(E)EvEdO＋O上下文无关文法的基本概念FL&A上下文无关文法(context-freegrammars)的四个基本要素1.终结符(terminals)的集合有限符号集，相当于字母表EEOEE(E)EvEdO＋O终结符2.非终结符(nonterminals)的集合有限变量符号的集合非终结符3.开始符号(startsymbol)一个特殊的非终结符开始符号4.产生式(productions)的集合形如：headbody产生式集合上下文无关文法的基本概念FL&A终结符的集合一个上下文无关文法CFG(context-freegrammars)是一个四元组G=(V,T,P,S).上下文无关文法的形式定义非终结符的集合产生式的集合开始符号满足VT=SV产生式形如A,其中AV,(VT)*上下文无关文法的基本概念FL&A(1)CFGG01=({S},{0,1},P,S).其中产生式集合P为S01S0S1上下文无关文法举例(2)CFGGexp=({E,O},{(,),＋,,v,d},P,E).其中产式集合P为EEOEE(E)EvEdO＋O上下文无关文法的基本概念FL&A产生式集合的缩写记法形如A1,A2,…,An的产生式集合可简缩记为A12…n，如S01S0S1S010S1EEOEE(E)EvEdO＋OEEOE(E)vdO＋上下文无关文法的基本概念FL&A用于推理字符串是否属于文法所定义的语言一种是自下而上的方法，称为递归推理（recursiveinference），递归推理的过程习称为归约；另一种是自上而下的方法，称为推导（derivation）归约过程将产生式右部（body）形式的符号串替换为产生式左部（head）的符号推导过程将产生式左部的符号替换为产生式右部的符号归约与推导FL&A归约过程举例对于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）E归约与推导FL&A推导过程举例对于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)归约与推导FL&A推导关系对于CFGG=(V,T,P,S)，上述推导过程可用关系描述.设,(VT)*，A是一个产生式，则定义A.若G在上下文中是明确的，则简记为A.GG扩展推导关系到自反传递闭包定义上述关系的传递闭包，记为，可归纳定义如下：基础对任何(VT)*，满足.归纳设,,(VT)*，若，成立，则.GGGGG归约与推导FL&AEEOEE(E)EvEdO＋Ov(v＋d)v(v＋E)v(EOE)EOEEv(E)vOEvEv(vOE)lm最左推导（leftmostderivations）若推导过程的每一步总是替换出现在最左边的非终结符，则这样的推导称为最左推导.为方便，最左推导关系用表示，其传递闭包用表示.如对于文法Gexp，下面是关于v(v＋d)的一个最左推导：lmlmlmlmlmlmlmlmlm归约与推导FL&AEEOEE(E)EvEdO＋Ov(v＋d)E(v＋d)EO(E＋d)EOEEEO(EOd)EO(E)EO(EOE)EO(v＋d)rm最右推导（rightmostderivations）若推导过程的每一步总是替换出现在最右边的非终结符，则这样的推导称为最右推导.为方便，最右推导关系用表示，其传递闭包用表示.如对于文法Gexp，下面是关于v(v＋d)的一个最右推导：rmrmrmrmrmrmrmrmrm归约与推导FL&A句型(sententialforms)设CFGG=(V,T,P,S)，称(VT)*为G的一个句型，当且仅当S.若S，则是一个左句型（left-sententialform）;若S，则是一个右句型（right-sententialform）.若句型T*，则称为一个句子（sentence）.lmrm归约与推导FL&A上下文无关文法的语言设CFGG=(V,T,P,S)，定义G的语言为L(G)={wwT*Sw}G上下文无关语言CFGGexp=({E,O},{(,),＋,,v,d},P,E)的语言L(Gexp)=？归纳定义：1基础v,dL(Gexp)2归纳ifeL(Gexp),then(e)L(Gexp)ife1,e2L(Gexp),thene1＋e2L(Gexp)ife1,e2L(Gexp),thene1e2L(Gexp)EEOEE(E)EvEdO＋OFL&A上下文无关语言（context-freelanguages）如果一个语言L是某个CFGG的语言，即L(G)=L，则是上下文无关语言.上下文无关语言FL&A上下文无关语言文法设计例给出语言L=0n1nn1的一个文法。如下是一个可接受该语言的上下文无关文法G[S]S01S0S1课堂练习？FL&A证明给定语言L是某个文法G的语言一般步骤•ifwLthenwL(G)•ifwL(G)thenwL.对于前者，多数情况下可以归纳于w的长度|w|；对于后者，一般情况下可以归纳于推导w的步数.一个例子见定理5.7.上下文无关语言FL&A证明给定语言L是某个文法G的语言举例!!Exercise5.1.8考虑定义了下面的产生式的CFGG：SaSbS|bSaS|ε证明L(G)是所有有相同个数的a和b的串的集合。证明思路用归纳法证明：•若串w中包含相同个数的a和b，则wL(G).（通过对|w|进行归纳来证明w在L(G)中，即S*w）•若wL(G)，即S*w，则w中包含相同个数的a和b.（对从S到w的推导过程的步数进行归纳）（留作练习）上下文无关语言FL&A证明给定语言L是某个文法G的语言举例设G为上下文无关文法，其终结符集合为{a,b}，开始符号为S，产生式集合如下：SaBbAAaaSbAABbbSaBB试证明L(G)={ww{a,b}*,occur(w,a)=occur(w,b)}.其中，对于符号a和串w，occur(a,w)表示a在w中出现的次数.证明思路用互归纳法证明：对所有的w{a,b}*，如下三个等价式成立：1）S*wiffoccur(a，w)=occur(b，w)；2）A*wiff|w|0occur(a，w)=occur(b，w)+1；3）B*wiff|w|0occur(b，w)=occur(a，w)+1（留作思考题）上下文无关语言FL&A文法（grammar）文法是一个四元组G=(V,T,P,S)，V、T、P及S的含义如前.Chomsky通过对产生式施加不同的限制，把文法分成四种类型，即0型、1型、2型和3型.文法与语言的Chomsky分类方法FL&A0型文法0型文法G=(V,T,P,S)的产生式形如,其中,(VT)*，但中至少包含一个非终结符.能够用0型文法定义的语言称为0型语言.结论0型文法的能力相当于图灵机（Turingmachines）.文法与语言的Chomsky分类方法FL&A1型文法1型文法G=(V,T,P,S)的产生式形如,满足，仅S例外，且要求S不得出现在任何产生式的右部.1型文法也称谓上下文有关文法（context-sensitivegrammars）.能够用1型文法定义的语言称为1型语言或上下文有关语言.与1型文法的能力相当的一种状态机模型为线性有界自动机.文法与语言的Chomsky分类方法FL&A2型文法2型文法G=(V,T,P,S)的产生式形如A,其中AV，(VT)*.2型文法即上下文无关文法.能够用2型文法定义的语言称为2型语言，即上下文无关语言.结论与2型文法的能力相当的一种状态机模型为下推自动机（PushdownAutomata）.文法与语言的Chomsky分类方法FL&A3型文法3型文法G=(V,T,P,S)的产生式形如AaB或Aa,其中A,BV，aT{}3型文法也称为正规文法.能够用3型文法定义的语言称为3型语言，即正规语言.结论3型文法的能力等价于有限状态自动机.文法与语言的Chomsky分类方法FL&A(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()v语法分析树FL&A(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)语法分析树FL&A语法分析树（parsetrees）对于CFGG=(V,T,P,S)，语法分析树是满足下列条件的树：(1)每个内部结点由一个非终结符标记.(2)每个叶结点或由一个非终结符，或由一个终结符，或由来标记.但标记为时，它必是其父结点唯一的孩子.(3)如果一个内部结点标记为A，而其孩子从左至右分别标记为X1,X2,…,Xk，则AX1X2…Xk是P中的一个产生式.注意：只有k=1时上述Xi才有可能为，此时结点A只有唯一的孩子，且A是P中的一个产生式.语法分析树FL&A语法分析树的果实（yield）设CFGG=(V,T,P,S).将语法分析树的每个叶结点按照从左至右的次序连接起来，得到一个(VT)*中的字符串，称为该语法树的果实.G的每个句型都是某个根结点为S的分析树的果实;这些分析树中，有些树的果实为句子，它们构成了G的语言.语法分析树FL&A三者之间的关系设CFGG=(V,T,P,S).以下命题是相互等价的：(1)字符串wT*可以归约（递归推理）到非终结符A；(2)Aw；(3)Aw；(4)Aw；(5)存在一棵根结点为A的分析树，其果实为w.lmrm归约、推导与分析树之间关系FL&A递归推理（归约）语法分析树最左推导最右推导推导证明策略归约、推导与分析树之间关系FL