《上下文无关语法》PPT课件.ppt

1,计算理论,2,主要内容,2.1上下文无关文法概述2.1.1上下文无关文法的形式化定义2.1.2上下文无关文法举例2.1.3设计上下文无关文法2.1.4歧义性2.1.5乔姆斯基范式2.2下推自动机2.2.1下推自动机的形式化定义2.2.2下推自动机举例2.2.1与上下文无关文法的等价性2.3非上下文无关语言,3,上下文无关文法(CFG)概述,A0A1ABB#,变量(Variables)A,B,终止符(Terminals)0,1,#,起始变元(StartVariable)A,箭头的左侧只有一个变量,替换规则又称为产生式,4,如何利用CFG产生字符串,A0A1ABA#,获取一个字符串的替换过程叫派生。例如字符串000#111的过程如下：A0A100A11000A111000B111000#111,(1)写下起始变元第一条规则左边的变元。(2)取一个已写下的变元，并找到以该变元开始的规则，把这个变元替换成规则右边的字符串。(3)重复步骤2，直到写下的字符串没有变元。,5,如何利用CFG产生字符串,A0A1ABA#,可以用语法生成树形象地表示派生过程。,A,A,A,B,#,0,0,0,1,1,1,A,6,文法的语言,A0A1ABA#,文法G1可以产生的字符串包括：#,0#1,00#11,000#111,用文法生成的所有字符串的集合称为文法的语言。L(G1)表示文法G1产生的语言。L(G1)=0n#1n|n0用上下文无关文法产生的语言叫上下文无关语言。文法G1的简写：A0A1|BB#,7,上下文无关文法的形式化定义,定义2.1,上下文无关文法是一个4元组(V,R,S)，且(1)V是一个有穷集合，称为变元集。(2)是一个与V不相交的有穷集合，称为终结符集。(3)R是一个有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成。(4)SV是起始变元。,8,CFG的术语,假设u与v由变元及终结符构成的字符串，Aw是文法的一条规则，称uAv生成uwv，记作uAvuwv。如果u=v，或者存在u1,u2,uk,k0使得uu1u2ukv，则称u派生v，记作u*v。文法G=(V,R,S)的语言为L(G)=w*|S*w,9,上下文无关文法举例,例2.1考虑文法G=(S,a,b,R,S)，其中规则集R为：SaSb|SS|。该文法生成abab，aaabbb，aababb，如果将a看作(，将b看作)，L(G)是所有正常嵌套的括号字符串构成的语言。,10,设计上下文无关文法,设计如下语言的上下文无关文法0n1n|n01n0n|n00n1n|n01n0n|n0设计技巧化繁为简，利用正则，考察子串，利用递归。,11,设计上下文无关文法,CFGforL1=0n1n|n0S0S1|CFGforL2=1n0n|n0S1S0|CFGforL1L2SS1|S2S10S11|S21S20|CFGforL3=02n13n|n0?S00S111|,12,上下文无关文法与正则语言,任何正则语言可以由CFG描述。,如果(qi,a)=qj，则增加规则VjaVi如果qi是接受状态，则增加规则Vi如果q0是起始状态，则V0是起始变元。,CFG,G=(V0,V1,0,1,R,V0)V00V0|1V1|V11V1|0V0,13,最左派生,对于文法G中的一个字符串w的派生，如果在每一步都是替换左边剩下的变元，则称这个派生是最左派生。例如G=(S,(,),R,S)，其中规则为S(S)|SS|SSS(S)S()S()(S)()()SSSS(S)(S)(S)()(S)()(),14,歧义性,一个串可能有两个甚至更多的最左派生。例如CFGG=(S,+,*,a,R,S)，其中规则为SS+S|S*S|a产生串a+a*aSS+Sa+Sa+S*Sa+a*Sa+a*aSS*SS+S*Sa+S*Sa+a*Sa+a*a,15,歧义性,定义2.4,如果字符串w在上下文无关文法G中有两个或两个以上不同的最左派生，则称G歧义地(ambiguously)产生字符串w，如果文法G歧义地产生某个字符串，则称G是歧义的。某些上下文无关语言只能用歧义文法产生，这样的语言是固有二义的。,16,乔姆斯基范式,定义2.5,称一个上下文无关文法是为乔姆斯基范式(Chomskynormalform)，如果它的每一个规则具有如下形式：ABCAa其中a是任意的终结符，A、B和C是任意的变元，且B和C不能同时是起始变元。此外，允许规则S，其中S是起始变元。,17,乔姆斯基范式,定理2.6,任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。,Step1:增加起始变元S0和规则S0S,其中S是原来的起始变元。Step2:考虑所有的规则。对于A,删去每个A都会产生一个新规则。例如RuAvAwRuAvw,RuvAw,Ruvw,18,乔姆斯基范式,定理2.6,任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。,Step3:考虑单一产生式AB。例如：AB,BaC,BCC,则增加AaC,ACC。Step4:考虑Au1u2uk,其中k2且ui是变量或终结符。替换该规则Au1A1,A1u2A2,A2u3A3,Ak-2uk-1uk,19,例题,SASA|aBAB|SBb|,S0SSASA|aBAB|SBb|,20,例题,Afterthat,weremoveB,S0SSASA|aBAB|SBb|,S0SSASA|aB|aAB|S|Bb,BeforeremovingB,AfterremovingB,21,例题,Afterthat,weremoveA,S0SSASA|aB|aAB|S|Bb,BeforeremovingA,AfterremovingA,S0SSASA|aB|a|SA|AS|SAB|SBb,22,例题,Then,weremoveSSandS0S,AfterremovingSS,AfterremovingS0S,S0SSASA|aB|a|SA|ASAB|SBb,S0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAB|SBb,23,例题,Then,weremoveAB,BeforeremovingAB,AfterremovingAB,S0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAB|SBb,S0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAb|SBb,24,例题,Then,weremoveAS,BeforeremovingAS,AfterremovingAS,S0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAb|SBb,S0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAb|ASA|aB|a|SA|ASBb,25,例题,Then,weapplyStep4,BeforeStep4,AfterStep4GrammarisinCNF,S0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAb|ASA|aB|a|SA|ASBb,S0AA1|UB|a|SA|ASSAA1|UB|a|SA|ASAb|AA1|UB|a|SA|ASBbA1SAUa,26,作业,W5:3.3、3.6,27,主要内容,2.1上下文无关文法概述2.1.1上下文无关文法的形式化定义2.1.2上下文无关文法举例2.1.3设计上下文无关文法2.1.4歧义性2.1.5乔姆斯基范式2.2下推自动机2.2.1下推自动机的形式化定义2.2.2下推自动机举例2.2.1与上下文无关文法的等价性2.3非上下文无关语言,28,下推自动机,考虑语言0n1n|n0的识别装置,状态控制器,栈,下推自动机(pushdownautomata)PDA=NFA+stackwithunlimitedsize确定型PDA和非确定型PDA的语言识别能力不相同。,29,下推自动机(PDA)的形式化定义,定义2.8,下推自动机是6元组(Q,q0,F)(1)Q是一个有穷集合，称为状态集。(2)是一个有穷集合，称为输入字母表。(3)是一个有穷集合，称为栈字母表。(4):QP(Q)是转移函数，其中=,=(5)q0Q是起始状态。(6)FQ是接受状态集。,PDA的形式化定义没有提供检验空栈的直接手段。约定PDA在开始时就把一个特殊符号$放入栈中。,30,PDA的计算过程,PDAM=(Q,q0,F)接受输入串w，如果能够把w写成w1w2wm，其中wi存在状态序列r0,r1,rmQ存在s0,s1,sm*满足下述3个条件，字符串si是M在计算的接受分支中的栈内容序列。(1)r0=q0,s0=(2)对于i=0,1,m-1,有(ri+1,b)(ri,wi+1,a),其中si=at,si+1=bt,a,b(3)rmF,31,下推自动机举例,例2.9描述识别语言0n1n|n0的PDAM。,q1,q2,q3,q4,$,1,0,0,0,1,0,$,M=(q1,q2,q3,q4,0,1,0,$,q1,q1,q4),(q1,)=(q2,$),(q2,0,)=(q2,0)(q2,1,0)=(q3,),(q3,1,0)=(q3,)(q3,$)=(q4,),(q,x,y)=,32,下推自动机举例,例2.10构造识别语言aibjck|i,j,k0且i=j或i=k的PDAM。,q1,q2,q5,q6,$,a,a,$,q7,q3,q4,$,b,c,a,c,b,a,33,下推自动机举例,例2.11构造识别语言wwR|w0,1*的PDAM。,q1,q2,q3,q4,$,0,01,1,0,01,1,$,34,PDA与上下文无关文法的等价性,35,PDA与上下文无关文法的等价性,设A是一个CFL，根据定义，存在一个CFGG产生它。如何把G转换成一台等价的PDAP。通过确定是否存在关于输入w的派生，当G产生w时，PDAP接受这个输入。设计P，以确定是否有一系列使用G的规则替换。,36,由CFG构造PDA,P的非形式化描述如下：(1)把标记符$和起始变元放入栈中。(2)重复下述步骤：a)如果栈顶是变元A，则非确定地选择一个关于A的规则，并且把A替换成这条规则右边的字符串。b)如果栈顶是终结符a，则读输入中的下一个符号，并且把它与a进行比较。如果它们匹配，则重复，否则，这个非确定性分支被拒绝。c)如果栈顶是符号$，则进入接受状态，如果此刻收入已全部读完，则接受这个输入串。,37,由CFG构造PDA,输入:1100CFG:SSS|1S0|10,1100,Atthebeginning,1100,PDAusestheruleS1S0,100,Inputcharismatched,Nextchar,Nextchar,Nextchar,38,由CFG构造PDA,输入:1100CFG:SSS|1S0|10,100,PDAusestheruleS10,00,Inputcharismatched,0,Inputcharismatched,Nextchar,Nextchar,Nextchar,39,由CFG构造PDA,输入:1100CFG:SSS|1S0|10,Wholeinputstringisprocessed,The$inthetopofstacktellsPDAthestackisempty.PDAacceptsthestring,Nextchar,Nextchar,40,由CFG构造PDA的证明,采用一种缩写记号表示转移函数，即一步把一个字符串写入到栈中。设q和r是P的状态，a，s。要求P，当读a并且弹出s时，从q到r，并且同时把整个字符串u=u1u2ul推入栈。可以如下完成这个动作：引入新的状态q1,ql-1,并且令转移函数(q,a,s)包含(q1,ul)(q1,)=(q2,ul-1)(ql-1,)=(r,u1)使用记号(r,u)(q,a,s)表示当q是P的状态，a是下一个输入符号以及s是栈顶符号时，PDAP能够读a和弹出s，然后把字符串u推入栈和转移到状态r。,41,由CFG构造PDA的示意图,q,r,a,sxyz,Ashorthandnotation,q,r,q1,q2,a,sz,y,x,Usingtwodummystatestoreplacesbyxyzatthetopofthestack,42,由CFG构造PDA的证明,P的状态集Q=qstart,qloop,qacceptE，E实现上面描述的缩写所需要的状态集合。转移函数定义如下：从初始化栈开始，把符号$和S推入栈，实现步骤1的非形式描述：(qstart,)=(qloop,S$),然后进行步骤2循环处理情况1,此时栈顶为一变元。令(qloop,A)=(qloop,w)|Aw是R中的一条规则处理情况2，这时栈顶是一个终结符。令(qloop,a,a)=(qloop,)处理情况3，这时栈顶是空栈标记符。令(qloop,$)=(qaccept,),43,由CFG构造PDA的示意图,qstart,qloop,start,S$,AxyzforruleAxyz,a,aforterminala,$,qaccept,shorthandnotationusedhere,44,例题,例2.14把下述CFGG转换成一台PDAP1SaTb|bTTa|,见书74页。,45,PDA与上下文无关文法的等价性,为简化工作，对P轻微修改:(1)有唯一的接受状态,qaccept(2)在接受之前清空栈(3)每一个转移把一个符号推入栈，或者把一个符号弹出栈，但不同时做这两个动作使P具有第三个特点，需要：(1)把同时push和pop的转移替换成两个转移，中间要经过一个新的状态；(2)把每一个既不push也不pop的转移，替换成两个转移，先推入任意一个栈符号，再把它弹出,证明略,46,PDA与上下文无关文法的等价性,对P中的每一对状态p,q,建立一个CFG变量Apq目标是使Apq能准确地产生把P从p和空栈一块带到q和空栈的所有字符串。PDA有两种方法可以从p和空栈到q和空栈:(1)在到达q之前栈变空这意味着我们从p到某一个r(withemptystack)然后到达q(2)在到达q之前栈从不变空表明在p时，我们push一些字符t进栈，在q时，我们弹出相同的字符t,47,PDA与上下文无关文法的等价性,对每一个p,q,r,增加规则ApqAprArq对每一个p,q,r,s，当(r,t)(p,a,)且(q,)(s,b,t),增加规则ApqaArsb,即,如果我们可以从p到r，并且从r到q，那么我们可以从p到q（这里，所有开始与结束时栈都为空的,即,如果我们可以从状态p到r，通过读一个字符a并且将t压入栈中，我们可以从状态s到达q，通过读字符b并且从栈中弹出t，那么如果我们开始状态p，栈为空，可以到达q，栈为空，通过读a，从r到s，然后读b获得,48,PDA与上下文无关文法的等价性,对每一个p,增加规则App,即,我们可以从p到p，不需要读任何字符,49,PDA与上下文无关文法的等价性,所以,在我们的文法中，将有所以的规则Apq与Aqstart,qaccept集合作为开始变元剩下的就是证明Apq能通过P中准确地产生那些串，从p到q（withemptystacks)也就是说,我们需要证明如果Apq产生x,x由P从p到q(withemptystacks)产生如果x由P从p到q(withemptystacks),Apq产生x,Exercise:Provetheabovetwostatements(Hint:byinduction),50,主要内容,2.1上下文无关文法概述2.1.1上下文无关文法的形式化定义2.1.2上下文无关文法举例2.1.3设计上下文无关文法2.1.4歧义性2.1.5乔姆斯基范式2.2下推自动机2.2.1下推自动机的形式化定义2.2.2下推自动机举例2.2.1与上下文无关文法的等价性2.3非上下文无关语言,51,非上下文无关语言,定理2.19,关于上下文无关语言的泵引理如果A是上下文无关语言，则存在p(泵长度)，使得A中任何一个长度不小于p的字符串s都能被划分成5段s=uvxyz，且满足下述条件：(1)对于每一个i0,uvixyizA；(2)|vy|0；(3)|vxy|p。,52,泵引理的证明思路,设A是CFL，G是产生A的CFG。要证明A中任何足够长的字符串s都能够被抽取，并且抽取后的字符串仍在A中。设s是A中一个很长的字符串。由于s在A中，它可以用G派生出来，从而有一棵语法树。由于s很长，s的语法树一定很高，即，这棵语法分析树一定有一条很长的从树根的起始变元到树叶上的终结符的路径。根据鸽巢原理，在这条长路径上一定有某个变元R重复出现。,53,泵引理的证明思路,把s切成5段uvxyz，重复第2段和第4段，得到的字符串仍在A中。即，对任意i0，uvixyizA,54,泵引理的证明思路泵长度,设G是关于CFLA的一个CFG，令b是规则右边符号数的最大值。在G的任意一棵语法树中，一个节点做多有b个儿子，即，离起始变元1步最多有b片树叶；离起始变元不超过2步最多有b2片树叶；离起始变元不超过h步最多有bh片树叶。因此，如果语法树高度不超过h，则它产生的字符串的长度不超过bh。反之，如果一个产生的字符串长度