句法结构模式识别课件.ppt

第七章句法结构模式识别,形式语言概述 文法推断句法分析自动机理论误差校正句法分析,7-1 形式语言概述一、基本概念1、字母表：与所研究的问题有关的符号集合。例：V1=A,B,C,D,V2=a,b,c,d2、句子(链)：由字母表中的符号所组成的有限长度的符号串。3、句子(链)的长度：所包含的符号数目。例:|a3b3c3|=94、语言：由字母表中的符号组成的句子集合，用L表示。例：字母表V=a,bL1=ab,aab,abab 有限语言 L2=anbm|n,m=0,1,2.无限语言5、文法：在一种语言中，构成句子所必须遵循的规则的集合，用G表示。L(G)表示由文法G构成的语言。,6、V*:由字母表V中的符号组成的所有句子的集合，包括空句子在内。例：V*,01,0017、V:不包括空句子在内的句子集合，即VV*()8、VT:终止符，不能再分割的最简基元的集合，用小写字母 表示。VT=a,b,c9、VN:非终止符，由基元组成的子模式和句子的集合。用大 写字母表示。VN=A,B,C VT，VN的关系：VTVN=(空集)VT VN=V（全部字母表）10、产生式(再写规则)P：存在于终止符和非终止符间的关系式。例：，VN，VN,VT.11、文法的数学定义：它是一个四元式，由四个参数构成。G=VN,VT,P,S,二.短语结构文法 1.0型文法（无限制）设文法G=(VN,VT,P,S)VN：非终止符，用大写字母表示 VT：终止符，用小写字符表示 P：产生式 S：起始符产生式P：，其中V+，V*，无任何限制(V+不包括空格,V*包括空格)例：0型文法 G=(VN,VT,P,S)VN=S,A,B VP=a,b,cP:SaAbc AbbA AcBbcc bBBb aBaaA aB(空格),SAabcabAcabBbccaBbbcc bbcc 此文法可以产生：X=anbn+2cn+2 n0 X|n=0=bbcc由0型文法产生的语言称为0型语言。2.1型文法（上下文有关文法）设文法G=(VN,VT,P,S)产生式P：1A212 其中AVN，V+,1,2V*|1A2|12|,或|A|B|由上下文有关文法构成的语言称为上下文有关语言，用L(G1)表示，G1：上下文有关文法,例：G=(VN,VT,P,S)VN=S,B,C VT=a,b,cP:SaSBC CBBC SabC bBbb bCbc cCcc1S21aSBC2,bBbb对于SaSBC 1=,2=,A=S,B=aSBC,并且|S|aSBC|符合1型文法规则对于bBbb 1=b,2=,A=B,B=b,并且|B|b|也符合1型文法规则产生式都符合1型文法的要求,SaSBCaabCBCabbBCCaabbCCaabbcCaabbcc X=a2b2c2 此文法G可产生的语言：L(G)=anbncn|n=1,2.假设基元 语言L(G)可以描述不同的三角型X=abc X=a2b2c2,a,b,c,a,b,c,c,c,b,b,a,a,2.2型文法（上下文无关文法）设文法G=(VN,VT,P,S)产生式P：A 其中AVN（且是单个的非终止符)V+(可以是终止符，非终止符，不能是空格)对产生式的限制比较严格 由上下文无关文法构成的语言称为上下文无关语言。例：文法G=(VN,VT,P,S)VN=S,B,C VT=a,bP:SaB SbA Aa AaS AbAA Bb BbS BaBB,aBabSabaBabab S abbAabba bAbaSbaaBbaab babAbaba例：G=(VN,VT,P,S)VN=S,T,F VT=a,+,*,(,)P:SS+T ST TT*F TF F(S)FaSS+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a,两种方法替换非终止符：最左推导：每次替换都是先从最左边的非终止符开始，例如上边的例子。我们经常采用最左推导。最右推导：每次替换都是先从最右边的非终止符开始，例如：SS+T S+F S+a T+a F+a a+a,3.3型文法（有限状态文法）文法 G=(VN,VT,P,S)产生式P：AaB 或Aa，（对产生式限制最严格）其中A,BVN（且是单个字符），aVT(且是单个字符)由3型文法产生的语言成为3型语言。例：文法G=(S,A,0,1,P,S)P:S0A A0A A1 S0A00A000A0001 L(G)=0n1|n=1,2.例：构造文法G能产生语言L(G)=x|x=0n 10m|n,m0 解：G=(VN,VT,P,S)VT=(0,1)P:S0B B0B B1S B0 VN=(S,B),四种文法的关系:包含关系：限制不严格的文法必然包含限制严格的文法。,3型,2型,1型,0型,三.图象描述语言（PDL）1970年，Show提出图像描述语言任何图象都可用头尾来表示 定义了四种二元连接算子 1.a+b 2.a x b 3.a b 4.a*b,t,h,a头与b尾相连,h,h,t,a尾与b尾相连,形成两个头,h,t,t,a头与b头相连，形成一头二尾,a头连b头,a尾连b尾，形成一头一尾,h,h,t,t,h,t,基元b,a,b,a,b,a,b,头,头,尾,尾,一元算子一个基元的头或尾可以与另一基元的头或尾相连而成为模式串，并可设置一些较复杂的联结关系和进行各种运算。例：文法G=(VN,VT,P,S)VT=,(),+,-,x,*,VN=S,A,B,C P:SA SB A(b+(C+c)B(d+(a+(d)*C),C(b+c)*a),h,t,b,h,t,b,a,b,c,d,L(G)=(b+(b+c)*a)+c);(d+(a+(d)*(b+c)*a),b,c,a,a,d,d,b,b,c,c,a,C,B,S,d,b,+,导出过程,d,a,+,+,c,*,a,S,A,b,+,c,+,C,b,+,c,*,a,求表达式的规则：脱括号由内往外的次序进行，无括号由左向右进行 对于连接基元组成基元结构，必须符合规定的连接 点头，尾数目例：给出一个PDL文法G=(S,A,B,C,D,E,a,b,d,(,),+,*,P,S)P:S(A+(B)B(C)+D D b E(a+b)A d C E*c D(d)A a,c,可以导出手写大写字符“A”的四种表达式 S(A+(B)(a+(B)(a+(C)+D)(a+(E*c)+D)(a+(a+b)*c)+D)(a+(a+b)*c)+(d)(d+(a+b)*c)+b),(a+(a+b)*c)+b),(d+(a+b)*c)+(d),a,d,b,b,a,a,b,b,b,a,d,d,c,d,a,a,b,c,四.标准形式文法在句法分析和自动机的一些算法中，有时要求标准化文法，下面介绍二种标准文法。1.乔姆斯基(Chomsky)范式,一种上下文无关文法如果它的每个 产生式P都符合二种形式：ABC(A,B,CVN)或Aa(AVN,aVT)该文法称Chomsky范式 已知上下文无关文法 G=(VN,VT,P,S)用以下步骤产生Chomsky范式的等价文法 G=(VN,VT,S)若中已经是ABC，Aa形式放入 中中其它的产生式形式为A 12.n 其中iVN或 iVT,用下面的产生式集合代替：AY1Y2.n Y2.nY2Y3.n Yn-1.nYn,n-1 YiVN若i VN,则令Yi=i；若i VT,再引入Yii,例：把文法G=(VN,VT,P,S)变成Chomsky范式 VN=S,A,B VP=a,bP:SAB，Aa,AabABa，Bb 把SAB，Aa,Bb放入 中AabABa，A12345，其中1=5=a,2=b,3=A,4=BAY1Y2345,Y2345Y2Y345,Y345Y3Y45,Y45Y4Y5,3,4VN Y345AY45,Y45BY5,125VT引入新的产生式，Y1a,Y2b,Y5a,符合chomsky范式文法，文法G2=(VN,VT,S)VN=Y1Y2345,Y2Y345,Y45,Y5,S,A,B AY1Y2345,Y1a,Y2345Y2Y345,Y2b,Y345AY45,Y45BY5,Y5a,SBA,Aa,Bb若x=bababa用G1导出：SBAbAbabABabababa,用G2导出：SBAb Y1Y2345.baY2345 baY2Y345 babY345 babAY45 babaY5 bababY5 bababa用原文法G1 只用四步可以导出bababa而用标准文法G2则用九步才导出,2.格雷巴赫范式(Greibach)若一个上下文无关文法具有P形式：Aa,AVN,aVT,VN*(带空格)则此文法称为Greibach范式。例：上下文无关文法 G=(VN,VT,P,S)VN=S,C,VT=a,b,cP形式：SaCbb,CaCbb Cc变成Greibach范式：Cc即Cc符合Greibach范式，不变SaCbb,用SaCBB,Bb代替CaCbb,用CaCBB,Bb代替符合Greibach范式：P:SaCBB,CaCBB,Cc,Bb,五.高维文法：上面我们介绍的都是一维链（串）文法，为了描述更复杂的图形、图象,需要用高维文法,包括树文法，图文法,网文法等等。1.树文法：定义：四元组 Gt=(v,r,P,S)其中V=VNVT，r:秩(一个节点的直接分支数)P形式：TiTj Ti,Tj都是树由Gt产生的语言叫树语言。L(Gt)=T|TT,TiT TiS,T是带有VT中结点的树集合 扩展树文法：全部产生式形式 其中x1,x2.xnVN,xVT，nr(x)具有上面产生式形式的树文法称扩展的树文法。,Gt,X,x,x1,x2 xn,例：Gt=(v,r,P,S)V=VNVT（S,A,B,K,a,b）VT(,),r(a)=(2,0),r(b)=(2,0),r(k)=2P:SK Aa Bb Aa Bb SK,a,b,A,B,A,B,A,B,A,B,a,b,a,b,k,A,B,SK,a,b,A,B,A,B,a,b,k,导出树,导出图,b,b,a,a,例2：在氢云室内用正粒子打击核目标碰撞发出的射线可以用 树文法来描述。树文法Gt=(v,r,P,S)，VN（S,A,B），VT(a,b)基本定义：P:,a,b,(凸弧),(凹弧),S,a,|,S,S,a,A,B,S,a,A,B,B,A,S,a,A,B,B,A,A,B,A,a,|,A,A,a,B,a,|,B,B,a,r(a)=(0,1,2,4,6),r(b)=(0,1)射线导出树：,S,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,b,b,b,b,b,b,b,b,b,b,b,b,b,a,a,b,射线图：,7-2 文法推断根据已知L(G)样本集导出未知文法G的过程。(一)基本定义：1.若在产生式中至少有一个产生式存在以下形式：AiiAii 此文法G=(VN,VT,P,S)是循环文法或不确定，由它产生的语言L(Gt)为无限的。2.若文法G为不循环的，则必为确定的，且L(G)为有限的。,样本集,推断算法,Gt,St=(x1,x2 xt),导师,3.当L(GA)=L(GB)时，则GA与GB等效，等价。例：有限状态文法GA=(VN,VT,P,S),VN=S,VT=0,1P:S0S,S1 则L(GA)=0n1|n=1,2,上下文无关文法GB=(VN,VT,P,S),VN=S，A,VT=0,1P:SA1,AAA,A0 则L(GB)=0n1|n=1,2,L(GA)=L(GB)GA与GB等效4.S+是L(G)的子集，即S+L(G)，称为正取样，是 子集，记为 称为负取样，5.若正取样S+=(x1,x2.xi)=L(G)，称为S+是完备的，负取样=(x1,x2.xi)=,称 也是完备的，且St=(S+,S-)=(x1,x2.xi)=(L(G),)也是完备的。,(二)有限状态文法推断状态图表示方法，文法可以用图来表示例：G=(VN,VT,P,S)VN=S,A,B,C VT=0,1P:S0A A0A B0 B0B S1B A1B C0C S1C A1 C1T：附加状态此文法可以产生的字符串 x1=00n1,x2=0n+110m+1,x3=10n+1,x4=10n1,A,S,C,B,T,0,0,0,0,1,1,1,1,1,0,一.规范确定文法已知正取样S+=(x1,x2.xn)推断规范文法Gc=(VN,VT,PL,S)的步骤如下：VT=S+中不同的终止符 设xi=ai1ai2.ain链PL:Sai1Zi1 Zi1VN,ai1VT Zi1ai2Zi2 Zi2VN,ai2VT ZIn-2ain-1Zi n-1 Zin-1VN,ain-1VT ZIn-1ain ainVTVN=S,Zi1,Zi2,.Zin-1,此文法产生的语言是确定的，有限的，且有性质：L(GL)=S+,例：已知S+=(01，100，111，0010)VT=0，1x1=01,S0Z1,Z11 x2=100,S1Z2,Z20Z3,Z30 x3=111,S1Z4,Z41Z5,Z51 x4=0010,S0Z6,Z60Z7,Z71Z8,Z80VN=S,Z1,Z2,.Z8 推断出的文法为：Gc=(VN,VT,Pc,S)VN=S,Z1,Z2,.Z8,VT=0，1PL:S0Z1,Z11,S1Z2,Z20Z3,Z30,S1Z4 Z41Z5,Z51,S0Z6,Z60Z7,Z71Z8,Z80,状态图：显然对任一有限取样都可用此法推断出规范文法，方法简单，适用计算机运算。缺点是非终止符太多，产生式也多。,S,Z1,Z2,Z3,Z4,Z5,Z6,Z7,Z8,T,0,0,0,0,0,0,1,1,1,1,1,1,二.导出文法（简化规范文法）设：Gc为规范文法，非终止符集合VN=S,Z1,Z2,.Zn,把VN分成r个子集:VND=Bj,B1,B2.Br SBj,ZiBj这些子集满足：BjBk=,jk Bj=VN 定义导出文法GD=(VND,VT,PD,Bs)是由规范文法Gc产生的文法，导出规则如下：VT相同 VND=(Bs,B1,B2,Br)Bs为起始符，Bs=S PD定义:a.若ZZ在Pc中，则PD中有 BiBj,ZaBi,ZBj b.若Za在Pc中，则PD中有Bia,ZaBi,r,j=s,例：S+=(01，100，111，0010)规范文法Gc=(VNC,VT,Pc,S)VNC=S,Z1,Z2,Z8对VNC分割为：VND=(S),(Z1,Z6,Z7),(Z2,Z3,Z8),(Z4,Z5)=Bs,B1,B2,B3对于S0Z1 SBS,Z1 B1 PD中有BS0B1对于Z11 Z1 B1 PD中有B11同理：BS1B2，B20B2,B20,BS1B3，B31B3，B31 BS0B1，B10B1，B11B2，B20把相同的产生式合并后有：Pc：BS0B1，BS1B2，BS1Bs,B11，B10B1，B11B2，B20B2,B20,B31B3，B31,状态图导出文法等效规范文法 L(GC)=L(GD)这种方法由于分割方式不同会导出不同的文法而分割方式又无系统理论作指导，而靠经验和试探。,B5,B3,B2,B1,T,0,0,1,1,1,1,1,1,0,0,三.形式微商文法形式微商定义：集合A对于符号aVT的形式微商是：DaA=X|axA 若a=(空串)，则DA=A例：A=S+=01,100,111,0010 则D0A=D0S+=1，010 D1A=D1S+=00，11扩展：二次微商Da1a2A=Da2(Da1A)n次微商：Da1a2an1anA=Dan(Da1a2an1)A对上例：D00 S+=D0(D0 S+)=D0(1.010)=(10)D11 S+=(1)D000 S+=,D100 S+=,已知正取样S+=x1,x2,.xnT 形式微商文法GCD=(VN,VT,P,S),定义如下：VT=（S中不同的符号）VN=U=(U1,U2,UP)其中Ui(i=1,2p)是S+的形式微商，且令U1=DS 起始符，S=U1=DS 令Ui,UjVNP:当DaUi=Uj,则UiaUj 当DaUi，则Uia,例：S+=101,111,推断形式微商文法如下：VT=（0,1）DS=S=101,111=U1=S 起始符 D1S=01,11=D1S=U2 S1U2 D10S=D0(D1S)=D0U2=1=U3 U20U3 D11S=D1(D1S)=D1U2=1=U3 U21U3 D101S=D1(D10S)=D1U3=U31 D111S-=D1(D11S)=D1U3=U31形式微商文法为(相同产生式合并)：GCD=(VN,VT,P,S)VT=（0,1）VN=（S,U2,U3）P:S1U2,U21U3,U20U3,U31状态图为：,S,U2,U3,T,1,1,0.1,四.k-尾文法：对形式微商文法进行长度限制，并对等价状态进行合并k尾定义：(U,A,k)=X|XDaA|X|k形式微商文法中两个状态间的等效性的充要条件为：(XiS+k)=g(XjS+k)-k尾相等利用k尾等效把形式微商文法中的等效状态合并，导出k尾文法。例：S+=01,1001 先求形式微商文法 DS+=S+=01,1001=U1=S D0S+=1=U2 S0U2 D01S+=D1(D0S+)=D1U2=U21 D1S+=001=U3 S1U3 D10S-=01=D0U3=U4 U30U4 D100S+=1=D0U4=U5 U40U5 D1001S+=U51,求k尾等效状态：|X|k k=4,k=3,k=2,k=1U1=DS+=01,1001，01，0,1，U2=D0S+=1，1，1，1 U3=D1S+=001，001,，U4=D10S+=01，01，01，U5=D100S+=1，1，1，1 等效状态为 k=4,k=3,k=2,k=1(U2,U5)(U1,U4)(U1,U4)(U1,U3,U4)(U2,U5)(U2,U5)(U2,U5,)合并状态，导出k尾文法 k=4时 S0U2,U11,S1U3,U30U4,U40U2 k=3,2时 S0U2,U21,S1U3,U30S k=1时 S0U2,U21,S1S,S0S,状态图讨论：推断k尾文法时，k尾的选择很重要，k小时文法简单，但循环产生式增多，这样就可以导出更多的S+以外的子串来，有时这是不允许的。,1,S,S,S,T,T,T,1,1,1,U2,U3,U4,U2,U3,U2,0,0,0,0,0,0,0,1,1,K=2,3,K=1,K=4,三.树文法推断一棵树可以看成一个多枝的链。因此前边讲的链（串）文法的推断方法可以用在树文法的推断上。任何一个数字化的网络模板都可以用树结构来表示如下：由下面的四种方式表示成树枝全从根开始的树。,树状的数字化网络模式,S,根,树干,N个枝,S,树干,M个枝,.,.,树文法先选一个合适的树干，由树干推出一个链文法再推各树枝的文法把树干文法与树枝文法合并,树干,树干,树枝,树枝,根S,S,例：已知数字化模式 L1 L2 L3 L4 L5 L6 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 R1 R2 R3 R4 R5 R6,树干,根S,先由树干推出树干文法GAP:,S,A1,A1,$,A2,|,|,R1,L1,A2,$,A3,|,|,R2,L2,A3,$,A4,|,|,R3,L3,A4,$,A5,|,|,R4,L4,A5,$,A6,|,|,R5,L5,A6,$,|,|,R6,L6,上面推出树干文法GA,再推出树枝文法GL1,GL2.GL6,GR1,GR2,.GR6再将树干文法与树枝文法合并 GT=GAGLGR,7-3 句法分析一.用句法分析作模式识别设给定训练样本为M类即：1,2,M 每类有N个样本，如1的训练样本为：S=(X1,X2,XN)T由这些样本可以推断出1类的文法G1,同样方法可推断出2类的文法G2,.M类的文法GM.对待识别句子X进行句法分析，若X属于由文法Gi构成的语言L(Gi)，则xi 类。框图如下：,XLG1,G1,XLG2,G2,XLGM,GM,x,判决,Xi,句法分析过程,识别结果,待识别句子,二句法分析的主要方法1参考匹配法：2状态图法：适用于有限状态文法例：G=(VN,VT,P,S)VT=（0,1）VN=（S,A,B,C）P:S1A,S0B,S1C,A0A,A0 B0,C0C,C0,C1B,X样本链码X1,XLG2,x,X样本链码X2,X样本链码XN,判决,Xi,XXi,S,C,B,A,T,1,1,0,0,0,1,0,由状态图可以知道此文法可以识别的句子X1=10n+1,X2=00,X3=10n10,X4=10n+1未知句子：由状态图可知x1=10010(可以识别)x2=10110(不可以识别),0,0,状态图,2、填充树图法(适用于上下文无关文法)：当给定某待识别链X及相应的文法G时，我们建立一个以X为底，S为顶的三角形，按文法G的产生式来填充此三角形，使之成为一个分折树。若填充成功表明 否则填充树有二种方法由顶向底剖析由底向顶剖析填充树图法在填充三角形时应遵守三条原则：首位考察：首先考虑选用某个产生式后能导出X的 第一个字符用某产生式后，不能出现X中不包含的终止符用某产生式后，不能导致符号串变长(变短),S,X,由顶向底(由上而下)剖析例：G=(VN,VT,P,S)VT=（0,1）VN=（S,A,B）P:S1 SB1 SB B1A BB1A A0A A0设：X=1000，用由上而下剖析方法判断X是否属于L(G),B,B,1,0,A,A,S,B,S,1,A,S,A,0,0,X=1000L(G),由底向顶(由下而上)剖析例：G=(VN,VT,P,S)VT=（a,b,c,f,g）VN=（S,T,I）P:ST Ia STfs Ib TIgT Ic TI 设：X=afbgc用Ia 用TI用Ib用Ic用TI,a f b g c,I,a f b g c,I,T,a f b g c,I,T,I,a f b g c,I,T,I,I,a f b g c,I,T,I,I,T,a f b g c,I,T,I,I,T,T,a f b g c,I,T,I,I,T,T,S,a f b g c,I,T,I,I,T,T,S,用TIgT用ST用STfS,S,X=afbgc L(G),三、杨格(Younger)法Younger法是个较前述各方法更系统的方法，适用于任何相应于2型文法类别的识别。下面结合一例说明此方法。设有一代表类别的文法G=(VN,VT,P,S)其中 VT=（0,1,2）VN=（S,B）P:SSBS BBB BBS S2 B0 B1现在要用Younger法来识别X=202102是否G.首先将上述文法化为Chomsky标准形式。此形式文法的代换式只有两种形式，即 非终止符非终止符非终止符（双非终止符形式）非终止符终止符（终止符形式）,将式上所示文法中第1条改为SSA，ABS两条（A为人为增加的非终止符），使整个文法成为：SSA ABS BBB BBS S2 B0 B1 而令VT=（0,1,2）VN=（S,A,B）便完成了Chomsky形式的转化。Younger法将对Chomsky形式文法进行分析。待识别符号串的任一“子串”都可用i,j两个整数来指明：所谓子串即把一符号串任一截取一段，这段符号串（包括单个符号）就叫原来符号的子串。譬如符号串202102的子串就有2，0，2，1，0，2（个数为1的子串）；20，02，21，10，02（个数为2的子串）；202，021，210，102（个数为3的子串）；2021，0210，2102（个数为4的子串）；20210，02102（个数为5的子串）和202102（个数为6的子串即原符号串）。,这21个符号串都可由正整数i,j表示。i代表子串中符号的个数（即子串长度），而j表示这子串的首位在原符号串中占第几位。如上面所举的第1子串“2”，即为i=1、j=1的子串，第13个子串021即是i=3、j=2的子串。可见，任一子串都可用i,j二数来指明。识别表的建立，关键问题是根据给出的待识别串X,建立一识别表。对于202102,根据所给出的文法算得的识别表如下：,表中每一位置由三个符号表示。头二个即i和j，而第三个是非终止符(现为S,A,B,见表中第一列).。i1栏中第2列(j=2)与B行相交的位置即为(1,2,B),余类推。表中(1,2,B)位置上有，代表对于所给文法，B可导出i=1,j=2的子串，即“0”。反之，若这位置上为，则说明B不能导生子串“0”。再举一例，第2栏中第2列、A行位置应该用（2,2,A）表示，此位置上有，代表对于所给文法，B可导出I=2,j=2的子串，即“02”（见表）。（）经分析可知，能容易地根据给出的符号串(202102),在i=1栏的各位置上打 或，又根据此栏结果，由一递推公式将i=2栏各位置打上 或。如此递推下去便可将表填满，识别表也就建成。在识别时只需检查最后一栏(现为i=6栏)第一列第S行位置即(6,1,S)上是 还是。若是，表示S可导生子串202102，故判202102符合给出的文法。反之，即判不符合此文法。,建立识别表的递推规则递推规则：将要决定 或 的位置表为(i,j,k)通用形式。K代表非终止符。又将r(i,j,K)称为(i,j,k)位置的识别值。此值为0或1，分别表示(i,j,k)位置上是 或。计算r(i,j,K)(也即决定 或)的步骤是：(i)算出其中K1,K2代表KK1K2.例如：ABS,K=A,K1=B,K2=S.,（1）,(ii)如果(i,j,k)左侧是K的代换式不只一个，譬如K是B时，即有BBB、BBS两个。这时则把B、B叫做K1、K2，根据它计算式(1)中各值；此外，还需将B、S叫做K1、K2，再按下面式算出：对于所有i,j,k（包括题中各个非终止符），算出式(2)中的各值。只要其中之一值为1，便在相应当位置上打，否则打。如此便可填满整个识别表若左侧为K的代换式有三个，可按上述原则，再增加计算将(1)式中K1、K2改为K1、K2后的各值，余类推。,现作为例子用递推规则考察(2,2,A)中的 或。由于左侧为A的代换式只有ABS一个，故此时对于(1)式只需计算r(1,2,B)r(1,3,S)=1 1=1,即(2,2,A)应打。此结果与前面分析得到的相符。根据上述递推规则和给定的文法，容易编制计算机程序。当待识别串X进入时，按此算出识别表，并检查表中最后一列S位置上是 还是；若为，便判属于给定文法相应的类别，否则判为不属于此类别。作业：对Younger法的例题编程上机，打出识别表。,四.CYK(Cocke-Younger-Kasami)剖析(列表法)条件：适用上下文无关文法 产生式应符合Chomsky范式已知输入串X=a1a2.an构造三角形剖析表步骤如下：令j=1,按从i=1到i=n次序，求ti1.把X分解为长度为1的子串，对子串ai,若p中有Aai,把A填入ti1中令j=2,按从i=1到i=n-1次序，求ti2，即第二行。把X分解为长度为2的子串，对子串aiai+1,若p中有ABC,且有Bai,Cai+1则把A填入ti2中对于j2,1in,已求出tij-1,现求tij对于1kj中的任一k,当P中有ABC且B在tik中.C在ti+k,j-k中时，把A填入tij中重复直至完成此表，或整行都是空(拒识)当且仅当S在tin中，XL(G)，即由G可导出X分析一个长度为n的串，所用的存储量正比于n2,运算次数正比于n3。,1 2 3 4 5 i,54321,tij,剖析表,j,例：G=(VN,VT,P,S)VT=（a,b）VN=（S,A,B,C）P:SAB SAC Aa Bb CSB 输入串：X=aabb=a1a2a3a4 所有产生式符合Chomsky范式令j=1,计算ti1，1i4i=1,a1=a,P中有Aa 有t11=(A)i=2,a2=a,P中有Aa 有t21=(A)i=3,a3=b,P中有Bb 有t31=(B)i=4,a4=b,P中有Bb 有t41=(B)第一次迭代，令j=2,计算ti2，1i3对于a1a2=aa,不能产生aa 有t21=对于a2a3=ab,SAB,Aa,Bb 有t22=(s)对于a3a4=bb,P中产生式不能产生bb 有t32=(),1 2 3 4 i,j4321,A,A,B,B,S,第二次迭代，令j=3,计算ti3，1i2对于a1a2a3=aab,不能产生aab 有t13=对于a2a3a4=abb,CSB,Sab,Bb 有t23=(C)第三次迭代，令j=4,计算ti4，对于a1a2a3a4=aabb,SAC,Aa,Cabb 有t14=(S)t14=S X=aabb在L(G)中，此串被识别。此算法实际上是一个由底向顶剖析算法。,4321,A,A,B,B,S,1 2 3 4 i,S,C,剖析表,a a b b,A A B B,S,S,C,导出树,+,+,作业：对CYK算法的例题上机编程，打出剖析表和导出树。,7-4 自动机理论引言：x当给出某类文法后，可根据它设计一种相应的称为自动机的硬件模型。它由控制装置、输入带和某些类型的存储器组成，这种硬件模型是一种识别器称自动机。不同的自动机可以识别不同的文法形成的语言。0型文法：图灵机识别上下文有关型：线性约束自动机上下文无关型：下推自动机有限状态型：有限状态自动机,识别器,XLG,G,一、有限状态自动机 可以识别由有限状态文法所构成的语言1、基本定义：五元式M系统 M=(,Q,q0,F)其中：输入符号的有限集合Q：状态的有限集合：状态转换函数是Q到Q的一种映射q0：初始状态 q0 Q F：终止状态集合2、有限自动机的结构 转换函数：(q,a)=p表示有限控制器处于q状态，而输入头读入符号a，则有限控制器转换到下一状态p。,输入带,0,1,1,0,输入头,有限状态控制器Q,q0 q1.F,3、自动机识别输入字符串的方式L(M)=x|(q0,x)在F中(q,x)拒识，停机4、自动机的状态转换图:表示自动机识别过程例：M=(,Q,q0,F)Q q0,q1,q2,q30,1F=q0(q0,0)=q2,(q0,1)=q1,(q1,0)=q3,(q1,1)=q0,(q2,0)=q0,(q2,1)=q3,(q3,0)=q1,(q3,1)=q2,q0,q1,q2,q3,1,1,1,1,0,0,0,0,输入：x=110101q0 q1 q0 q2 q3 q1 q0F X可以识别(q0,110101)=q0 例：已知自动机状态转换图如下 x1=aab 可以识别 x2=abb 不可以识别可以识别的语言：L(G)=anbqB状态，只有出没有进，为不可到达状态 q状态，只有进没有出，为陷阱,1,1,0,1,1,0,a,b,b,a,a,b,q0,qA,qB,q,a,b,4、不确定的有限状态自动机即：(q,a)=q1,q2,qk当输入a时，下一个状态可 能为多个状态之一。例：M=(,Q,q0,F)Q q0,q1,q2,q3,q40,1F=q2，q4(q0,0)=q0,q3,(q0,1)=q0,q1(q1,0)=(在q1不会输入0)(q1,1)=q2(q2,0)=q2,(q2,1)=q2,(q3,0)=q4,(q3,1)=(q4,0)=q4,(q4,1)=q4,状态转换图输入字串：010110q0 q0 q0 q0 q0 q3 q1 q3 q1 q2 q2F,q0,q3,q1,0,0,0，1,0，1,1,1,0，1,q4,q2,0,1,0,1,1,0,输入字符串X=010110可以被自动机识别，但在识别过程中，对不确定状态需要进行试探。,5、构造一个有限自动机定理1：设 G=(VN,VT,P,S)为有限状态文法，一定存在一个有限状态自动机M=(,Q,S,F)使L(G)=L(M).已知有限状态文法G=(VN,VT,P,S)由有限状态文法构造有限自动机的步骤：VT Q VNT q0=S 若P中有S，则F=(S,T),否则F=T 若P中有Ba，则(B,a)=T,BVN,aVT 若P中有BaC，则(B,a)=(C),B,CVN,aVT 对VT中所有的终止符a，都有(T,a)=,aVT,例：有限状态文法G=(VN,VT,P,S)VN=S,B VT=0,1P:S0B,B0B/1S/0(B0B,B1S,B0)构造有限自动机 M=(,Q,q0,F)VT 0,1 Q VNT S,B，T q0=S P中无S F=T S0B,(S,0)=B,B0B,(B,0)=B,B1S,(B,1)=S,B0,(B,0)=T,P中无S1x,xVN,(S,1)=对VT=0,1有(T,0)=(T,1),构造的自动机M为M=(,Q,q0,F)，0,1,Q=S,B,T,q0=S,F=T:(s,0)=B(s,1)=(B,0)=B,T(B,1)=S(T,0)=(T,1)=设x=00100，可以识别可以证明：L(M)=L(G),0,1,0,T,S,B,0,6.由有限自动机M构造有限状态文法定理2：已知有限自动机M，则有一个有限状态文法G，使L(G)=L(M)。已知M=(,Q,q0,F)，构造G=(VN,VT,P,S)的步骤如下：VT VN Q Sq0 对于(B,a)=C,若B,C Q,a,则P中有BaC.若C F,则还有产生式Ba例：已知有限自动机 M=(,Q,q0,F)，Q q0,q1,q2 0,1 F=q2(q0,0)=q2,(q0,1)=q1,(q1,0)=q2,(q1,1)=q0(q2,0)=q2，(q2,1)=q1,构造G=(VN,VT,P,S)如下：VT 0,1 VN=Q=q0,q1,q2 S=q0(q0,0)=q2,有q00 q2,q2 F 有q00(q0,1)=q1,有q01 q1,(q1,0)=q2,有q10 q2,q2 F 有q10(q1,1)=q0,有q11q0,(q2,0)=q2,有q20q2,q2 F 有q20(q2,1)=q1,有q21q1,有限状态文法为：G=(VN,VT,P,S)VT 0,1 VN=q0,q1,q2 S=q0P:q00 q2,q01q1,q00 q10 q2,q11q0,q10 q20 q2,q21 q1,q20,状态图输入x1100由自动机M：(q0,1100)q2，q2 F 1100可以接受由有限文法G：q01q111q0110q21100 L(M)=L(G),q0,q1,q2,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,q1,q0,q2,T,有限自动机,有限状态文法,二.下推自动机（PDA）可以识别由上下文无关文法构成的语言 下推自动机结构：七元式MP=(,Q,q0,Z0,F,)其中,Q,q0,F同有限自动机:转换函数:推下符号的有限集合 Z0:推下存贮器的起始符例如：(qi,b,Z)=(qj,)qi：目前状态，b：输入符号，Z：下推存储器的内容qj：下一状态，：下推存储器的下一状,输入带,只读头,有限状态器Q,读写头,下推存储器（堆栈型）,b,B,Z0,识别输入字串X的方式终止状态方式空堆栈识别方式例：不确定的下推自动机 MP=(q0),(a,b,c,d),(S,A,B,C,D),q0,S,)即：Q=(q0),=(a,b,c,d),=(S,A,B,C,D),Z0=(S),F=()(q0,c,S)=(q0,DAB),(q0,C)(q0,a,D)=(q0,),(q0,b,B)=(q0,)(q0,d,C)=(q0,),(q0,a,A)=(q0,AB),(q0,CB),输入xcaadbb(q0,S)(q0,DAB)(q0,AB)(q0,CBB)(q0,BB)(q0,B)(q0,C)(q0,ABB)(q0,)堆栈变空，X=caadbb可以接受，这种不确定的下推自动机在识别过程中需试探进行。,c,a,a,d,b,d,a,不通,不通,b,例：确定自动机MP=(,Q,q0,Z0,F,)=(0,1)Q q0,q1,q2(2,0)F=(q0)Z0=(Z)(q0,0,Z)=(q1,02),(q1,0,0)=(q1,00)(q1,1,0)=(q2,),(q2,1,0)=(q2,)(q2,2)=(q0,)X=0011(q0,Z)(q