句法结构模式识别课件

第七章

句法结构模式识别

形式语言概述文法推断句法分析自动机理论误差校正句法分析第七章

句法结构模式识别

形式语言概述1§7-1形式语言概述一、基本概念1、字母表：与所研究的问题有关的符号集合。例：V1={A,B,C,D},V2={a,b,c,d}2、句子(链)：由字母表中的符号所组成的有限长度的符号串。3、句子(链)的长度：所包含的符号数目。例:|a3b3c3|=94、语言：由字母表中的符号组成的句子集合，用L表示。 例：字母表V={a,b} L1={ab,aab,abab}有限语言L2={anbm|n,m=0,1,2….}无限语言5、文法：在一种语言中，构成句子所必须遵循的规则的集合，用G表示。L(G)表示由文法G构成的语言。§7-1形式语言概述26、V*:由字母表V中的符号组成的所有句子的集合，包括空句子λ在内。例：V*＝{λ,01,001}7、V＋:不包括空句子在内的句子集合，即V＋＝V*－(λ)8、VT:终止符，不能再分割的最简基元的集合，用小写字母表示。VT={a,b,c}9、VN:非终止符，由基元组成的子模式和句子的集合。用大写字母表示。VN={A,B,C}VT，VN的关系：VT∩VN=Φ(空集)

VT∪

VN=V（全部字母表）10、产生式(再写规则)P：存在于终止符和非终止符间的关系式。例：α→β，α∈VN，β∈VN,VT.11、文法的数学定义：它是一个四元式，由四个参数构成。G={VN,VT,P,S}6、V*:由字母表V中的符号组成的所有句子的集合，包括空句子3二.短语结构文法

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,c}P:①S→aAbc②Ab→bA③Ac→Bbcc④bB→Bb⑤aB→aaA⑥aB→λ(空格)二.短语结构文法4S→Aa bc→abAc→abBbcc→aBbbcc→bbcc此文法可以产生：X=anbn+2cn+2n≥0X|n=0=bbcc由0型文法产生的语言称为0型语言。2.1型文法（上下文有关文法）设文法G=(VN,VT,P,S)产生式P：α1Aα2→α1βα2

其中A∈VN，β∈V+,α1,α2∈V*|α1Aα2|≤|α1βα2|,或|A|≤|B|由上下文有关文法构成的语言称为上下文有关语言，用L(G1)表示，G1：上下文有关文法①②③④⑥①②③④⑥5例：G=(VN,VT,P,S)VN={S,B,C}VT

={a,b,c}P:①S→aSBC②CB→BC③S→abC④bB→bb⑤bC→bc⑥cC→ccλ1Sλ2→λ1aSBCλ2,bBλ→bbλ对于S→aSBC∵α1=λ,α2=λ,A=S,B=aSBC,并且|S|<|aSBC|∴符合1型文法规则对于bB→bb∵α1=b,α2=λ,A=B,B=b,并且|B|≤|b|∴也符合1型文法规则产生式都符合1型文法的要求例：G=(VN,VT,P,S)6S→aSBC→aabCBC→abbBCC→aabbCC→aabbcC→aabbcc∴X=a2b2c2

此文法G可产生的语言：L(G)={anbncn|n=1,2...}假设基元语言L(G)可以描述不同的三角型X=abcX=a2b2c2abc①②③④⑥⑤abcccbbaaabc①②③④⑥⑤abcccbbaa72.2型文法（上下文无关文法）设文法G=(VN,VT,P,S)产生式P：A→β其中A∈VN（且是单个的非终止符)β∈V+(可以是终止符，非终止符，不能是空格)对产生式的限制比较严格由上下文无关文法构成的语言称为上下文无关语言。例：文法G=(VN,VT,P,S)VN={S,B,C}VT={a,b}P:①S→aB②S→bA③A→a④A→aS⑤A→bAA⑥B→b⑦B→bS⑧B→aBB

2.2型文法（上下文无关文法）8

aB→abS→abaB→ababSabbA→abbabA→baS→baaB→baabbabA→baba例：G=(VN,VT,P,S)VN={S,T,F}VT={a,+,*,(,)}P:①S→S+T②S→T③T→T*F④T→F⑤F→(S)⑥F→aS→S+T→T+T→F+T→a+T→a+T*F→a+F*F→a+a*F→a+a*a①⑦③④③⑥⑥①①②②②①②④⑥⑥⑥③④aB→abS→abaB→abab①⑦③④③⑥⑥①9

两种方法替换非终止符：①最左推导：每次替换都是先从最左边的非终止符开始，例如上边的例子。我们经常采用最左推导。②最右推导：每次替换都是先从最右边的非终止符开始，例如：S→S+T→S+F→S+a→T+a→F+a→a+a两种方法替换非终止符：103.3型文法（有限状态文法）

文法G=(VN,VT,P,S)产生式P：A→aB或A→a，（对产生式限制最严格）

其中A,B∈VN（且是单个字符），a∈V

T(且是单个字符)由3型文法产生的语言成为3型语言。例：文法G=({S,A},{0,1},P,S)P:①S→0A②A→0A③A→1S→0A→00A→000A→0001L(G)={0n1|n=1,2...}例：构造文法G能产生语言L(G)={x|x=0n10m|n,m>0}解：G=(VN,VT,P,S)VT=(0,1)P:①S→0B②B→0B③B→1S④B→0∴VN=(S,B)3.3型文法（有限状态文法）11四种文法的关系:包含关系：限制不严格的文法必然包含限制严格的文法。3型2型1型0型四种文法的关系:3型2型1型0型12三.图象描述语言（PDL）1970年，Show提出图像描述语言任何图象都可用头尾来表示定义了四种二元连接算子

1.a+b2.axb3.a–b4.a*btha头与b尾相连hhta尾与b尾相连,形成两个头htta头与b头相连，形成一头二尾a头连b头,a尾连b尾，形成一头一尾hhttht基元bababab头头尾尾三.图象描述语言（PDL）tha头与b尾相连hhta尾与b13一元算子~一个基元的头或尾可以与另一基元的头或尾相连而成为模式串，并可设置一些较复杂的联结关系和进行各种运算。例：文法G=(VN,VT,P,S)VT={→,↗,↘,↓,(),+,-,x,*,~}VN={S,A,B,C}P:①S→A②S→B③A→(b+(C+c))④B→(d+(a+(~d))*C),⑤C→((b+c)*a)htbht~babcd一元算子~htbht~babcd14L(G)={(b+(((b+c)*a)+c));((d+(a+(~d)))*((b+c)*a))}bcaad~dbbccaCBSdb~+导出过程da++c*aSAb+c+Cb+c*aL(G)={(b+(((b+c)*a)+c));((15

求ＰＤＬ表达式的规则：①

脱括号由内往外的次序进行，无括号由左向右进行②

对于连接基元组成基元结构，必须符合规定的连接点头，尾数目例：给出一个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→ac求ＰＤＬ表达式的规则：c16可以导出手写大写字符“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)))①⑧②⑥④⑦adbbaabbba~ddc~daabc⑴⑵⑶⑷可以导出手写大写字符“A”的四种表达式⑵⑶⑷①⑧②⑥④⑦a17四.标准形式文法在句法分析和自动机的一些算法中，有时要求标准化文法，下面介绍二种标准文法。1.乔姆斯基(Chomsky)范式,一种上下文无关文法如果它的每个产生式P都符合二种形式：A→BC(A,B,C∈VN)或A→a(A∈VN,a∈VT)该文法称Chomsky范式已知上下文无关文法G=(VN,VT,P,S)用以下步骤产生Chomsky范式的等价文法G=(VN,VT,,S)①若Ｐ中已经是A→BC，A→a形式放入中②Ｐ中其它的产生式形式为A→θ1θ2….θn其中θi∈VN或θi∈VT

四.标准形式文法18用下面的产生式集合代替：A→Y1Y2...nY2...n→Y2Y3...n…Yn-1...n→Yn,,n-1Yi∈VN若θi∈VN,则令Yi=θi；若θi∈VT,再引入Yi→θi用下面的产生式集合代替：19例：把文法G=(VN,VT,P,S)变成Chomsky范式VN={S,A,B}VP={a,b}P:S→AB，A→a,A→abABa，B→b①把S→AB，A→a,B→b放入中②A→abABa，A→θ1θ2θ3θ4θ5，

其中θ1=θ5=a,θ2=b,θ3=A,θ4=BA→Y1Y2345,Y2345→Y2Y345,Y345→Y3Y45,Y45→Y4Y5,∵θ3,θ4∈VN∴Y345→AY45,Y45→BY5,∵θ1θ2θ5∈VT∴引入新的产生式，Y1→a,Y2→b,Y5→a

例：把文法G=(VN,VT,P,S)变成Chomsk20符合chomsky范式文法，文法G2=(VN,VT,,S)VN={Y1Y2345,Y2Y345,Y45,Y5,S,A,B}A→Y1Y2345,Y1→a,Y2345→Y2Y345,Y2→b,Y345→AY45,Y45→BY5,Y5→a,S→BA,A→a,B→b若x=bababa用G1导出：S→BA→bA→babABa→bababa,用G2导出：S→BA→bY1Y2345...→baY2345→baY2Y345→babY345→babAY45→babaY5→bababY5→bababa用原文法G1只用四步可以导出bababa而用标准文法G2则用九步才导出符合chomsky范式文法，文法G2=(VN,VT,212.格雷巴赫范式(Greibach)若一个上下文无关文法具有P形式：A→aα,A∈VN,a∈VT,α∈VN*(带空格)则此文法称为Greibach范式。例：上下文无关文法G=(VN,VT,P,S)VN={S,C},VT={a,b,c}P形式：S→aCbb,C→aCbbC→c变成Greibach范式：C→cλ即C→c符合Greibach范式，不变S→aCbb,用S→aCBB,B→b代替C→aCbb,用C→aCBB,B→b代替符合Greibach范式：P:S→aCBB,C→aCBB,C→c,B→b,2.格雷巴赫范式(Greibach)22五.高维文法：上面我们介绍的都是一维链（串）文法，为了描述更复杂的图形、图象,需要用高维文法,包括树文法，图文法,网文法等等。1.树文法：定义：四元组Gt=(v,r,P,S)

其中V=VN∪VT，r:秩(一个节点的直接分支数)P形式：Ti→Tj

Ti,Tj都是树由Gt产生的语言叫树语言。L(Gt)={T|T∈T∑,Ti→TTi∈S},T∑是带有VT中结点的树集合

扩展树文法：全部产生式形式

其中x1,x2...xn∈VN,x∈VT，n∈r(x)具有上面产生式形式的树文法称扩展的树文法。GtXxx1,x2…xn五.高维文法：上面我们介绍的都是一维链（串）文法，为了描Gt23例：Gt=(v,r,P,S)

V=VN∪VT

＝（S,A,B,K,a,b）VT

＝(→,↗),r(a)=(2,0),r(b)=(2,0),r(k)=2P:①S→K②A→a③B→b

④A→a⑤B→b∴S→K

abABABABABab①④⑤abkAB①④⑤S→KabABAB④⑤②③abk导出树导出图bbaa例：Gt=(v,r,P,S)abABABA24例2：在氢云室内用正粒子打击核目标碰撞发出的射线可以用树文法来描述。树文法Gt=(v,r,P,S)，VN＝（S,A,B），VT

＝(a,b)基本定义：P:ab(凸弧)(凹弧)S

→

a

|S

S

→

a

A

BS

→

a

A

BBA

S

→

a

A

BBA

A

BA→

a

|AA→

a

B

→

a

|BB→

a

例2：在氢云室内用正粒子打击核目标碰撞发出的射线可以用ab(25r(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

bbbbb

bbbb

bbbbaab射线图：r(a)=(0,1,2,4,6),r(b)=(0,1)S26§7-2文法推断根据已知L(G)样本集导出未知文法G的过程。(一)基本定义：1.若在产生式中至少有一个产生式存在以下形式：Ai→αiAiβi此文法G=(VN,VT,P,S)是循环文法或不确定，由它产生的语言L(Gt)为无限的。2.若文法G为不循环的，则必为确定的，且L(G)为有限的。样本集推断算法GtSt=(x1,x2…xt)导师§7-2文法推断样本集推断算法GtSt=(x1,x2…273.当L(GA)=L(GB)时，则GA与GB等效，等价。例：有限状态文法GA=(VN,VT,P,S),VN={S},VT={0,1}P:S→0S,S→1

则L(GA)={0n1|n=1,2,…}上下文无关文法GB=(VN,VT,P,S),VN={S，A},VT={0,1}P:S→A1,A→AA,A→0则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),)也是完备的。3.当L(GA)=L(GB)时，则GA与GB等效，等价。28(二)有限状态文法推断状态图表示方法，文法可以用图来表示例：G=(VN,VT,P,S)VN={S,A,B,C}VT={0,1}P:①S→0A②A→0A③B→0④B→0B⑤S→1B⑥A→1B⑦C→0C⑧S→1C⑨A→1⑩C→1T：附加状态此文法可以产生的字符串x1=00n1,x2=0n+110m+1,x3=10n+1,x4=10n1ASCBT0000111110(二)有限状态文法推断ASCBT000011111029一.规范确定文法已知正取样S+=(x1,x2…..xn)推断规范文法Gc=(VN,VT,PL,S)的步骤如下：①VT=S+中不同的终止符②设xi=ai1ai2...ain链∴PL:S→ai1Zi1Zi1∈VN,ai1∈VT

Zi1→ai2Zi2Zi2∈VN,ai2∈VT…ZIn-2→ain-1Zin-1Zin-1∈VN,ain-1∈VTZIn-1→ainain∈VT∴VN={S,Zi1,Zi2,...Zin-1,}此文法产生的语言是确定的，有限的，且有性质：L(GL)=S+

一.规范确定文法30例：已知S+=(01，100，111，0010)①VT={0，1}②∵x1=01,∴S→0Z1,Z1→1x2=100,S→1Z2,Z2→0Z3,Z3→0x3=111,S→1Z4,Z4→1Z5,Z5→1x4=0010,S→0Z6,Z6→0Z7,Z7→1Z8,Z8→0∴VN={S,Z1,Z2,...Z8}推断出的文法为：Gc=(VN,VT,Pc,S)VN={S,Z1,Z2,...Z8,},VT={0，1}PL:S→0Z1,Z1→1,S→1Z2,Z2→0Z3,Z3→0,S→1Z4

Z4→1Z5,Z5→1,S→0Z6,Z6→0Z7,Z7→1Z8,Z8→0,例：已知S+=(01，100，111，0010)31状态图：显然对任一有限取样都可用此法推断出规范文法，方法简单，适用计算机运算。缺点是非终止符太多，产生式也多。SZ1Z2Z3Z4Z5Z6Z7Z8T000000111111状态图：SZ1Z2Z3Z4Z5Z6Z7Z8T0000001132二.导出文法（简化规范文法）设：Gc为规范文法，非终止符集合VN={S,Z1,Z2,...Zn},把VN分成r个子集:VND={Bj,B1,B2...Br}S∈Bj,Zi∈Bj这些子集满足：

Bj∩Bk=Ф,j≠k

∪Bj=VN

定义导出文法GD=(VND,VT,PD,Bs)是由规范文法Gc产生的文法，导出规则如下：①VT相同②VND=(Bs,B1,B2,…Br)③Bs为起始符，Bs=S④PD定义:a.若Zα→αZβ在Pc中，则PD中有Bi→αBj,Za∈Bi,Zβ∈Bjb.若Zα→a在Pc中，则PD中有Bi→a,Za∈Birj=s二.导出文法（简化规范文法）rj=s33例：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}对于S→0Z1∵S∈BS,Z1∈B1∴PD中有BS→0B1对于Z1→1

∵Z1∈B1∴PD中有B1→1同理：BS→1B2，B2→0B2,B2→0,BS→1B3，B3→1B3，B3→1BS→0B1，B1→0B1，B1→1B2，B2→0把相同的产生式合并后有：Pc：BS→0B1，BS→1B2，BS→1Bs,B1→1，B1→0B1，B1→1B2，B2→0B2,B2→0,B3→1B3，B3→1例：S+=(01，100，111，0010)34状态图导出文法等效规范文法L(GC)=L(GD) 这种方法由于分割方式不同会导出不同的文法而分割方式又无系统理论作指导，而靠经验和试探。B5B3B2B1T0011111100状态图B5B3B2B1T001111110035三.形式微商文法形式微商定义：集合A对于符号a∈VT的形式微商是：DaA={X|ax∈A}若a=λ(空串)，则DλA=A例：A=S+={01,100,111,0010}则D0A=D0S+={1，010}D1A=D1S+={00，11}扩展：二次微商Da1a2A=Da2(Da1A)n次微商：Da1a2…an－1anA=Dan(Da1a2…an－1)A对上例：D00S+=D0(D0S+)=D0(1.010)=(10)D11S+=(1)D000S+=Φ,D100S+={λ}三.形式微商文法36已知正取样S+={x1,x2,...xn}T形式微商文法GCD=(VN,VT,P,S),定义如下：①VT=（S＋中不同的符号）②VN=U=(U1,U2,…UP)其中Ui(i=1,2…p)是S+的形式微商，且令U1=DλS＋③起始符，S=U1=DλS＋④令Ui,Uj∈VNP:当DaUi=Uj,则Ui→aUj当λ∈DaUi，则Ui→a已知正取样S+={x1,x2,...xn}T37例：S+={101,111},推断形式微商文法如下：①VT=（0,1）②DλS＋=S＋={101,111}=U1=S起始符③∵D1S＋={01,11}=D1S=U2∴S→1U2∵D10S＋=D0(D1S＋)=D0U2={1}=U3∴U2→0U3∵D11S＋=D1(D1S＋)=D1U2={1}=U3∴U2→1U3∵D101S＋=D1(D10S＋)=D1U3={λ}

∴U3→1∵D111S-＋=D1(D11S＋)=D1U3={λ}

∴U3→1形式微商文法为(相同产生式合并)：GCD=(VN,VT,P,S)VT=（0,1）VN=（S,U2,U3）P:S→1U2,U2→1U3,U2→0U3,U3→1状态图为：SU2U3T110.1例：S+={101,111},推断形式微商文法如下：SU2U38四.k-尾文法：对形式微商文法进行长度限制，并对等价状态进行合并k尾定义：ф(U,A,k)={X|X∈DaA|X|≤k}形式微商文法中两个状态间的等效性的充要条件为：ф(XiS+k)=g(XjS+k)-k尾相等利用k尾等效把形式微商文法中的等效状态合并，导出k尾文法。例：S+={01,1001}①先求形式微商文法∵DλS+=S+={01,1001}=U1=SD0S+={1}=U2

∴S→0U2D01S+=D1(D0S+)=D1U2={λ}

∴

U2→1D1S+={001}=U3

∴S→1U3D10S-={01}=D0U3=U4

∴U3→0U4D100S+={1}=D0U4=U5

∴U4→0U5D1001S+={λ}∴U5→1四.k-尾文法：对形式微商文法进行长度限制，并对等价状态进行39②求k尾等效状态：|X|≤kk=4,k=3,k=2,k=1U1=DλS+={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时S→0U2,U1→1,S→1U3,U3→0U4,U4→0U2k=3,2时S→0U2,U2→1,S→1U3,U3→0Sk=1时S→0U2,U2→1,S→1S,S→0S②求k尾等效状态：|X|≤k40状态图讨论：推断k－尾文法时，k尾的选择很重要，k小时文法简单，但循环产生式增多，这样就可以导出更多的S+以外的子串来，有时这是不允许的。1SSSTTT111U2U3U4U2U3U20000000,11K=2,3K=1K=4状态图1SSSTTT111U2U3U4U2U3U20000041三.树文法推断一棵树可以看成一个多枝的链。因此前边讲的链（串）文法的推断方法可以用在树文法的推断上。任何一个数字化的网络模板都可以用树结构来表示如下：由下面的四种方式表示成树枝全从根开始的树。

X11X12......X1nX21X22......X2n...............Xn1Xn2......Xnn树状的数字化网络模式S根树干N个枝S树干M个枝…..…..三.树文法推断X11X12......X1nX21X22..42①树文法先选一个合适的树干，由树干推出一个链文法②再推各树枝的文法③把树干文法与树枝文法合并树干树干树枝树枝根SS树干树干树枝树枝根SS43例：已知数字化模式L1L2L3L4L5L6000111000111110000110000111100111000110000100000R1R2R3R4R5R6树干根S例：已知数字化模式树干根S44①先由树干推出树干文法GAP:S→

A1

A1

→

$

—

A2

||R1

L1

A2

→

$

—

A3

||R2

L2

A3

→

$

—

A4

||R3

L3

A4

→

$

—

A5

||R4

L4

A5

→

$

—

A6

||R5L5A6

→

$

||R6L6①先由树干推出树干文法GAS→A1A1→$—A245②上面推出树干文法GA,再推出树枝文法GL1,GL2...GL6,GR1,GR2,...GR6③再将树干文法与树枝文法合并

GT=GA∪GL∪GR②上面推出树干文法GA,再推出树枝文法GL1,GL2...46§7-3句法分析一.用句法分析作模式识别设给定训练样本为M类即：ω1,ω2,…ωM

每类有N个样本，如ω1的训练样本为：S=(X1,X2,…XN)T由这些样本可以推断出ω1类的文法G1,同样方法可推断出ω2类的文法G2,….ωM类的文法GM.对待识别句子X进行句法分析，若X属于由文法Gi构成的语言L(Gi)，则x∈ωi类。框图如下：§7-3句法分析47X∈L{G1}

G1X∈L{G2}

G2X∈L{GM}

GMx判决X∈ωi……句法分析过程识别结果待识别句子X∈L{G1}G1X∈L{G2}G2X∈L{GM}GM48二句法分析的主要方法1参考匹配法：2状态图法：适用于有限状态文法例：G=(VN,VT,P,S)VT=（0,1）VN=（S,A,B,C）P:S→1A,S→0B,S→1C,A→0A,A→0

B→0,C→0C,C→0,C→1BX∈样本链码X1

X∈L{G2}

x……X∈样本链码X2

X∈样本链码XN

判决X∈ωiX∈Xi二句法分析的主要方法X∈样本链码X1X∈L{G2}x……49SCBAT1100010由状态图可以知道此文法可以识别的句子X1=10n+1,X2=00,X3=10n10,X4=10n+1未知句子：由状态图可知x1=10010(可以识别)x2=10110(不可以识别)00状态图SCBAT1100010由状态图可以知道此文法可以识别的句子502、填充树图法(适用于上下文无关文法)： 当给定某待识别链X及相应的文法G时，我们建立一个以X为底，S为顶的三角形，按文法G的产生式来填充此三角形，使之成为一个分折树。若填充成功表明否则填充树有二种方法①由顶向底剖析②由底向顶剖析填充树图法在填充三角形时应遵守三条原则：①首位考察：首先考虑选用某个产生式后能导出X的第一个字符②用某产生式后，不能出现X中不包含的终止符③用某产生式后，不能导致符号串变长(变短)SX2、填充树图法(适用于上下文无关文法)：SX51⑴由顶向底(由上而下)剖析例：G=(VN,VT,P,S)VT=（0,1）VN=（S,A,B）P:

①S→1②S→B1③S→B④B→1A⑤B→B1A⑥A→0A⑦A→0设：X=1000，用由上而下剖析方法判断X是否属于L(G)BB10AASBS1ASA00⑦∴X=1000∈L(G)⑥⑥③④⑴由顶向底(由上而下)剖析BB10AASBS1ASA00⑦∴52⑵由底向顶(由下而上)剖析例：G=(VN,VT,P,S)VT=（a,b,c,f,g）VN=（S,T,I）P:

①S→T②I→a③S→Tfs④I→b⑤T→IgT⑥I→c⑦T→I设：X=afbgc①用I→a②用T→I③用I→b④用I→c⑤用T→Iafbgc↓Iafbgc↓I↓Tafbgc↓I↓T↓Iafbgc↓I↓T↓II↓afbgc↓I↓T↓II↓↓T①②③④⑤⑥⑵由底向顶(由下而上)剖析afbgc↓Iafb53afbgc↓I↓T↓II↓↓TTafbgc↓I↓T↓II↓↓TT↓

Safbgc↓I↓T↓II↓↓TTS⑥用T→IgT⑦用S→T⑧用S→TfSS⑦⑧∴X=afbgc∈L(G)afbgc↓I↓T↓II↓↓TTafbgc↓54三、杨格(Younger)法 Younger法是个较前述各方法更系统的方法，适用于任何相应于2型文法类别的识别。下面结合一例说明此方法。设有一代表类别的文法G=(VN,VT,P,S)其中VT=（0,1,2）VN=（S,B）P:

①S→SBS②B→BB③B→BS④S→2⑤B→0⑥B→1现在要用Younger法来识别X=202102是否∈G.⑴首先将上述文法化为Chomsky标准形式。此形式文法的代换式只有两种形式，即非终止符→非终止符•非终止符（双非终止符形式）非终止符→终止符（终止符形式）三、杨格(Younger)法55将式上所示文法中第1条改为S→SA，A→BS两条（A为人为增加的非终止符），使整个文法成为：①S→SA②A→BS③B→BB④B→BS⑤S→2⑥B→0⑦B→1而令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的子串即原符号串）。将式上所示文法中第1条改为S→SA，A→BS两条（A为人56这21个符号串都可由正整数i,j表示。i代表子串中符号的个数（即子串长度），而j表示这子串的首位在原符号串中占第几位。如上面所举的第1子串“2”，即为i=1、j=1的子串，第13个子串021即是i=3、j=2的子串。可见，任一子串都可用i,j二数来指明。⑶

识别表的建立，关键问题是根据给出的待识别串X,建立一识别表。对于202102,根据所给出的文法算得的识别表如下：这21个符号串都可由正整数i,j表示。i代表子串中符号的57

i

1

2

3

j

1

2

3

4

5

6

1

2

3

4

5

1

2

3

4

所有子串

2

0

2

1

0

2

20

02

21

10

02

202

021

210

102

所有VN

S

√

•

√

•

•

√

•

•

•

•

•

√

•

•

•

A

•

•

•

•

•

•

•

√

•

•

√

•

•

•

√

B

•

√

•

√

√

•

•

√

•

√

√

•

√

•

√

4

5

6

1

2

3

1

2

1

2021

0210

2102

20210

02102

202102

•

•

√

•

•

√

•

•

•

•

√

•

•

√

•

•

√

•

i123j58表中每一位置由三个符号表示。头二个即i和j，而第三个是非终止符(现为S,A,B,见表中第一列).。i＝1栏中第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，而第三个59⑷建立识别表的递推规则 递推规则：将要决定√

或•的位置表为(i,j,k)通用形式。K代表非终止符。又将r(i,j,K)称为(i,j,k)位置的识别值。此值为0或1，分别表示(i,j,k)位置上是√

或•。计算r(i,j,K)(也即决定√

或•)的步骤是：(i)算出其中K1,K2代表K→K1K2.例如：A→BS,K=A,K1=B,K2=S.（1）⑷建立识别表的递推规则（1）60(ii)如果(i,j,k)左侧是K的代换式不只一个，譬如K是B时，即有B→BB、B→BS两个。这时则把B、B叫做K1、K2，根据它计算式(1)中各值；此外，还需将B、S叫做K1’、K2’，再按下面式算出：对于所有i,j,k（包括题中各个非终止符），算出式(2)中的各值。只要其中之一值为1，便在相应当位置上打√，否则打•。如此便可填满整个识别表[若左侧为K的代换式有三个，可按上述原则，再增加计算将(1)式中K1、K2改为K1’’、K2’’后的各值，余类推。⑵(ii)如果(i,j,k)左侧是K的代换式不只一个，譬61 现作为例子用递推规则考察(2,2,A)中的√或•。由于左侧为A的代换式只有A→BS一个，故此时对于(1)式只需计算r(1,2,B)•r(1,3,S)=1•1=1,即(2,2,A)应打√。此结果与前面分析得到的相符。

根据上述递推规则和给定的文法，容易编制计算机程序。当待识别串X进入时，按此算出识别表，并检查表中最后一列S位置上是√还是•；若为√，便判属于给定文法相应的类别，否则判为不属于此类别。作业：对Younger法的例题编程上机，打出识别表。 现作为例子用递推规则考察(2,2,A)中的√或•。62四.CYK(Cocke-Younger-Kasami)剖析(列表法)条件：①适用上下文无关文法②产生式应符合Chomsky范式已知输入串X=a1a2...an构造三角形剖析表步骤如下：①令j=1,按从i=1到i=n次序，求ti1.把X分解为长度为1的子串，对子串ai,若p中有A→ai,把A填入ti1中②令j=2,按从i=1到i=n-1次序，求ti2，即第二行。把X分解为长度为2的子串，对子串aiai+1,若p中有A→BC,且有B→ai,C→ai+1则把A填入ti2中③对于j>2,1≤i≤n,已求出tij-1,现求tij对于1≤k≤j中的任一k,当P中有A→BC且B在tik中.C在ti+k,j-k中时，把A填入tij中④重复③直至完成此表，或整行都是空(拒识)当且仅当S在tin中，X∈L(G)，即由G可导出X分析一个长度为n的串，所用的存储量正比于n2,运算次数正比于n3。12345i54321tij剖析表j四.CYK(Cocke-Younger-Kasami)剖析(63例：G=(VN,VT,P,S)VT=（a,b）VN=（S,A,B,C）P:

①S→AB②S→AC

③A→a④B→b

⑤C→SB输入串：X=aabb=a1a2a3a4所有产生式符合Chomsky范式①令j=1,计算ti1，1≤i≤4i=1,a1=a,∵P中有A→a∴有t11=(A)i=2,a2=a,∵P中有A→a∴有t21=(A)i=3,a3=b,∵P中有B→b∴有t31=(B)i=4,a4=b,∵P中有B→b∴有t41=(B)②第一次迭代，令j=2,计算ti2，1≤i≤3对于a1a2=aa,∵不能产生aa∴有t21=φ对于a2a3=ab,∵S→AB,A→a,B→b∴有t22=(s)对于a3a4=bb,∵P中产生式不能产生bb∴有t32=(φ)1234ij4321AABBφSφ例：G=(VN,VT,P,S)VT=（a,b64③

第二次迭代，令j=3,计算ti3，1≤i≤2对于a1a2a3=aab,∵不能产生aab∴有t13=φ对于a2a3a4=abb,∵C→SB,S→ab,B→b∴有t23=(C)④

第三次迭代，令j=4,计算ti4，对于a1a2a3a4=aabb,∵S→AC,A→a,C→abb∴有t14=(S)∵t14=S∴X=aabb在L(G)中，∴此串被识别。此算法实际上是一个由底向顶剖析算法。4321AABBφSφ1234iφSC剖析表aabb↓↓↓↓AABBSSC导出树++③第二次迭代，令j=3,计算ti3，1≤i≤24AABB65作业：对CYK算法的例题上机编程，打出剖析表和导出树。作业：对CYK算法的例题上机编程，打出剖析表和导出树。66§7-4自动机理论引言：x当给出某类文法后，可根据它设计一种相应的称为自动机的硬件模型。它由控制装置、输入带和某些类型的存储器组成，这种硬件模型是一种识别器称自动机。不同的自动机可以识别不同的文法形成的语言。0型文法：图灵机识别上下文有关型：线性约束自动机上下文无关型：下推自动机有限状态型：有限状态自动机识别器X∈L{G}

G§7-4自动机理论识别器X∈L{G}G67一、有限状态自动机可以识别由有限状态文法所构成的语言1、基本定义：五元式M系统M=(∑,Q,δ,q0,F)其中：∑：输入符号的有限集合Q：状态的有限集合δ：状态转换函数是QΧ∑到Q的一种映射q0：初始状态q0∈Q

F：终止状态集合2、有限自动机的结构

转换函数：δ(q,a)=p表示有限控制器处于q状态，而输入头读入符号a，则有限控制器转换到下一状态p。∑输入带0110输入头有限状态控制器Qq0→q1→...F一、有限状态自动机可以识别由有限状态文法所构成的语言∑683、自动机识别输入字符串的方式L(M)={x|δ(q0,x)在F中}δ(q,x)＝Φ拒识，停机4、自动机的状态转换图:表示自动机识别过程例：M=(∑,Q,δ,q0,F)

Q＝{q0,q1,q2,q3}∑＝{0,1}F={q0}δ(q0,0)=q2,δ(q0,1)=q1,δ(q1,0)=q3,,δ(q1,1)=q0,δ(q2,0)=q0,δ(q2,1)=q3,δ(q3,0)=q1,δ(q3,1)=q2q0q1q2q3111100003、自动机识别输入字符串的方式q0q1q2q3111100069输入：x=110101q0

q1

q0q2q3

q1q0∈F∴X可以识别∴

δ(q0,110101)=q0

例：已知自动机状态转换图如下

x1=aab可以识别

x2=abb不可以识别可以识别的语言：L(G)=anbqB状态，只有出没有进，为不可到达状态qΦ状态，只有进没有出，为陷阱110110abbaabq0qAqBqΦ

a,b输入：x=110101110110abbaabq0qAqBq704、不确定的有限状态自动机即：δ(q,a)={q1,q2,…qk}当输入a时，下一个状态可能为多个状态之一。例：M=(∑,Q,δ,q0,F)

Q＝{q0,q1,q2,q3,q4}∑＝{0,1}F={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)=q44、不确定的有限状态自动机71状态转换图输入字串：010110q0q0q0q0q0

q3q1q3

q1q2q2∈Fq0q3q1000，10，1110，1q4q2010110∴

输入字符串X=010110可以被自动机识别，但在识别过程中，对不确定状态需要进行试探。状态转换图q0q3q1000，10，1110，1q4q201725、构造一个有限自动机定理1：设G=(VN,VT,P,S)为有限状态文法，一定存在一个有限状态自动机M=(∑,Q,δ,S,F)使L(G)=L(M).已知有限状态文法G=(VN,VT,P,S)由有限状态文法构造有限自动机的步骤：①∑＝VT②Q＝VN∪{T}③q0=S④若P中有S→Φ，则F=(S,T),否则F={T}⑤若P中有B→a，则δ(B,a)={T},B∈VN,a∈VT

⑥若P中有B→aC，则δ(B,a)=(C),B,C∈VN,a∈VT

⑦对VT中所有的终止符a，都有δ(T,a)=Φ,a∈VT

5、构造一个有限自动机73例：有限状态文法G=(VN,VT,P,S)VN={S,B}VT={0,1}P:S→0B,B→0B/1S/0(B→0B,B→1S,B→0)构造有限自动机M=(∑,Q,δ,q0,F)

①∵

∑＝VT∴∑＝{0,1}②∵

Q＝VN∪{T}＝{S,B，T}

③q0=S④∵P中无S→Φ

∴F={T}⑤∵S→0B,∴δ(S,0)=B,∵B→0B,∴δ(B,0)=B,∵B→1S,∴δ(B,1)=S,∵B→0,∴δ(B,0)=T,∵P中无S→1x,x∈VN,∴δ(S,1)=Φ

⑥对VT={0,1}有δ(T,0)=δ(T,1)＝Φ例：有限状态文法G=(VN,VT,P,S)74∴构造的自动机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)

010TSB0∴构造的自动机M为010TSB0756.由有限自动机M构造有限状态文法定理2：已知有限自动机M，则有一个有限状态文法G，使L(G)=L(M)。已知M=(∑,Q,δ,q0,F)，构造G=(VN,VT,P,S)的步骤如下：①VT＝∑②VN＝Q③S＝q0

④对于δ(B,a)=C,若B,C∈Q,a∈∑,则P中有B→aC.若C∈F,则还有产生式B→a例：已知有限自动机

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)=q16.由有限自动机M构造有限状态文法76构造G=(VN,VT,P,S)如下：

①VT＝∑＝{0,1}②VN=Q={q0,q1,q2}③S=q0④∵δ(q0,0)=q2,,∴有q0→0q2,∵

q2

∈F∴有q0→0∵δ(q0,1)=q1,,∴有q0→1q1,∵δ(q1,0)=q2,,∴有q1→0q2,∵

q2

∈F∴有q1→0∵δ(q1,1)=q0,,∴有q1→1q0,∵δ(q2,0)=q2,,∴有q2→0q2,∵

q2

∈F∴有q2→0∵δ(q2,1)=q1,,∴有q2→1q1,构造G=(VN,VT,P,S)如下：77∴有限状态文法为：G=(VN,VT,P,S)VT＝{0,1}VN={q0,q1,q2}

S=q0P:q0→0q2,q0→1q1,q0→0q1→0q2,q1→1q0,q1→0q2→0q2,q2→1q1,q2→0∴有限状态文法为：78状态图输入x＝1100由自动机M：δ(q0,1100)＝q2，∵

q2

∈F∴1100可以接受由有限文法G：q0→1q1→11q0→110q2→1100∴L(M)=L(G)q0q1q2111111000000000q1q0q2T有限自动机有限状态文法状态图q0q1q2111