《模式识别原理与应用》课件第7章

第7章结构模式识别7.1

结构模式识别概述7.2

形式语言与自动机7.3高维文法和随机文法7.4句法分析7.5文法推断习题7.1结构模式识别概述统计模式识别是从模式中提取一组特性的度量,构成特征向量来表示模式,然后通过划分特征空间的方式进行分类。对于较复杂的模式,要对其充分描述需要很多特征,以至过于复杂。结构模式识别又称句法模式识别,它采用一些比较简单的子模式组成多级结构来描述一个复杂模式,先将模式分为子模式,子模式又分为更简单的子模式,依次分解,直至在某个研究水平上不再需要细分。最后一级最简单的子模式称为模式基元,识别模式基元比识别原模式要简单得多。结构模式识别主要突出模式的结构信息,常用于以结构特征为主的目标识别中,例如指纹、染色体和汉字识别等。图7-1所示是一个模式多级分解的例子。图7-1模式分解示意图结构模式识别法将观察对象表达为一个由基元组成的句子,将模式类表达为由有限或无限个具有相似结构特性的模式组成的集合。基元构成模式所遵循的规则即为文法,或称句法。与统计模式识别类似,用已知类别的训练样本进行学习,产生该类或至少是这些样本的文法,这个学习和训练过程称为文法推断。结构模式识别的系统框图如图7-2所示,包括预处理、模式表达、句法分析和文法推断四个部分。其中,模式表达包括两部分:模式分割和基元及关系的识别。对于一个模式,经过预处理并对模式分解提取基元后,得到表征模式的句子,然后进行句法分析,判断它是否能被代表某个模式类的文法所接受,最终给出识别结果和模式的结构描述。图7-2结构模式识别系统框图7.2形式语言与自动机形式语言的渊源可以追溯到20世纪50年代中期,乔姆斯基(Chomsky)等在研究自然语言的过程中发展了文法的数学模型。他将语言形式地定义为由一个字母表中的字母组成的串的集合,在字母表上按照一定的规则定义一个文法,该文法产生的所有句子组成的集合就是该文法产生的语言。若一个句子能由某种语言对应的文法产生,则判断这个句子属于该语言。克林(Kleene)在研究神经细胞时提出了自动机,用它来识别语言。按照一定规则构造任意一个自动机,该自动机所能识别的所有句子组成的集合就是一个语言,即一个自动机定义了一个语言。文法和自动机是表示语言的两种不同方法。1959年,乔姆斯基通过深入研究,证明文法和自动机具有等价性。7.2.1短语结构文法

1.字母表和字符串字符的有限集合称为字母表,记为V。由字母表V中的字符构成的有限序列称为字母表V上的字符串(链)。例如字母表V={a,b,c,…,z,0,1,…,9},即表由26个英文字母和10个阿拉伯数字构成,则字符串可以是a,b,012,ce78等。一个字符串所包含字符的个数称为该字符串的长度,字符串x的长度记为|x|。允许有不含任何符号的空串,记为ε,空串的长度为零。假设X和Y都是字母表V上的字符串,则XY称为字符串X和Y的连接。字母表上的任意一个字符串W与空串ε的连接还是W,即εW=Wε=W。

V+是字母表V上所有字符串构成的集合,V*是字母表V上所有字符串和空串构成的集合,有V*=V+∪{ε}。

2.短语结构文法定义7.1短语结构文法是一个四元组:G=(VN,VT,P,S)其中:VN为非终止符集,通常用大写字母表示;VT为终止符集,通常用小写字母表示,VN∪VT=V,且VN∩VT=

,即VN与VT不相交;P是形如α→β的产生式有限集,且α∈V+,β∈V*,符号“→”的含义是“能够再写为”;S∈VN为起始符。如果A→β是P中的产生式,α和γ是V*中的字符串,则有

称αβγ是αAγ的直接推导。设α,α0,α1,…,αn,α′都是V*中的字符串,且有α=α0,α′=αn,其中αi直接推出αi+1(0≤i≤n－1),则称序列是长度为n的直接推导序列,可记为即包含了和。有一文法G=(VN,VT,P,S),若，且α是终止符和非终止符组成的字符串,则α是文法G的句型;若α∈V*T,则α是文法G的句子,即句子是由终止符组成的符号串。

定义7.2

文法G=(VN,VT,P,S)产生的语言L(G)是由S开始根据G推出的所有终止符串组成的集合,【例7.1】给定文法G=(VN,VT,P,S),其中:，由文法产生的语言L(G)如下:以此类推,该文法生成的语言的一般形式是

3.文法的分类乔姆斯基(Chomsky)分类体系将短语结构文法分为四种类型,即0型、1型、2型和3型文法。

1)0型文法

0型文法是对P中产生式的形式不加任何限制的文法,又称为无约束文法。由此可知,任何一个文法必然是0型文法。只有0型文法才允许有产生空句的产生式。

2)1型文法

1型文法也称上下文有关文法,它对每一产生式的形式限制为α1Aα2→α1βα2,其中α1、α2∈V*,A∈VN,β∈V+。文法的含义是在α1和α2之间的非终止符A可被重写为β,α1和α2被视为A的上下文。理论上讲,每步推导时,可以对句型中的任何一个非终止符进行表达式替换。在形式语言理论中,为了简单,常采取每次对最左边的或最右边的非终止符进行表达式替换,即采用最左推导或最右推导。最左推导即每次对最左边的非终止符进行推导,最右推导即每次对最右边的非终止符进行推导。不论是采用最左推导还是最右推导,其目的均在于简化推导过程。

1型文法的一种等价定义是:产生式集P的形式为α→β,α、β∈V+,且|α|≤|β|。

【例7.2】

给定文法，，改写为改写为改写为改写为该文法为上下文有关文法。虽然表面上看上下文不完整,但根据α1、α2∈V*,可以有α1=α2=ε,经过改写就可以明显看出给定文法是上下文有关的。或者根据1型文法的另一种定义,本例中每个产生式左部字符串长度小于或等于右部字符串长度,表明给定文法是上下文有关的。

3)2型文法

2型文法也称上下文无关文法,它要求每一产生式的形式为A→β,其中A∈VN,β∈V+。产生式的左端是单个非终止符A,可被重写为右端的字符串β,而与A的上下文无关。

4)3型文法

3型文法也称正则文法,或称正规文法、有穷文法、有限状态文法。对每一产生式的形式限制为A→aB或A→b,其中A、B∈VN,a、b∈VT。由定义可以看出,从0型文法到3型文法,对产生式的限制越来越严格,四种文法的类别包含关系是:3型2型1型0型。对应四类文法,产生的语言也分为四类。0型文法产生的语言称为无限制性语言,1型文法产生的语言称为上下文有关语言,2型文法产生的语言称为上下文无关语言,3型文法产生的语言称为正则语言。每一种类型的语言对应一种识别器,即每个语言的句子都能被某种识别器所接受。句法识别器可以被视为一个离散控制系统,一个离散控制系统可以模型化为一个自动机。短语结构文法和自动机之间的对应关系如下:文法类型自动机类型

0型文法

——

图灵机

1型文法——

线性有界自动机

2型文法——

下推自动机

3型文法——

有限自动机7.2.2正则文法和有限自动机定义7.3

一个确定的有限状态自动机Af是一个五元组:其中:Q为有限状态集;Σ是有限输入字母表;δ是Q×Σ→Q的映射;q0为起始状态;为终止状态集。图7-3给出了有限状态自动机的一般表示。有限状态自动机由一个带有读头的有限控制器和一条写有字符的输入带组成。有限控制器包含有限个状态,读头从左到右依次从输入带上读入字符,每当读头从输入带上读入一个字符时,控制器的状态发生改变,即出现状态转换。图7-3有限状态自动机假设映射δ(q,a)=q′,其中,q、q′∈Q,a∈Σ,表示的意思是有限状态自动机当前处于状态q,读头从输入带上读入字符a,自动机的状态转换为q′,读头从左到右移动一个方格。可以用状态转移图方便地描述映射δ,相应于映射δ(q,a)=q′的状态转移图如图7-4所示。每个状态标以一个节点,终止状态集F中的状态用双圈标示,状态集Q中F以外的节点用单圆圈表示。图7-4

δ(q,a)=q′的状态转移图对确定的有限状态自动机而言,由当前状态及读入字符决定的下一步状态是确定的。确定的有限状态自动机Af接受的全部字符串的集合为上式表明,若一个串x被自动机接受,要求自动机Af从起始态q0出发,经输入串x后,状态最后转换到终止态上。

【例7.3】

设确定的有限状态自动机Af=(Q,Σ,δ,q0,F),其中:，，δ:，，，，自动机的状态转移图如图7-5所示。图7-5例7.3的有限状态自动机的状态转移图自动机Af从起始态q0出发,输入串x=aabbab,在逐个读入x的各字符时,自动机的状态变化过程为整个输入串读完后,自动机处于状态q0∈F,所以输入串x被自动机接受。

定义7.4

一个非确定的有限状态自动机Af是一个五元组:与确定的有限状态自动机相比,只是映射规则不同,δ是Q×Σ→2Q的映射。对非确定的有限状态自动机而言,在当前状态及输入符号确定的情况下,下一步的状态不唯一,即δ(q,a)是一个状态集合(可能为空)。例如δ(q,a)={q1,q2,…,ql},它的解释是:非确定的有限状态自动机处于状态q,读头从输入带上读入字符a,选择q1,q2,…,ql中的任意一个作为下一步状态,并将读头向右移动一格。非确定的有限状态自动机Af接受的语言也定义为输入串后能停留在终止态上的所有串的集合:

定理7.1设L是一个非确定的有限状态自动机所接受的语言,则有一个能接受L的确定的有限状态自动机的状态是Af的状态的所有子集,即，，，是中包含F的一个状态的所有状态集合。映射为当且仅当由于确定的有限状态自动机和非确定的有限状态自动机接受同样的语言,在讨论有限状态自动机时,可以不区分是确定的有限状态自动机还是非确定的有限状态自动机。定理7.2

设G=(VN,VT,P,S)是一个正则文法,则存在一个有限状态自动机Af=(Q,Σ,δ,q0,F),满足L(Af)=L(G),其中:

(1)Σ=VT,Q=VN∪{T},T为一附加的非终止符,q0=S;

(2)如果P包含产生式S→ε,则F={S,T},否则F={T};

(3)如果P包含产生式B→a,B∈VN,a∈VT,则T∈δ(B,a);

(4)如果P包含产生式B→aC,B、C∈VN,a∈VT,则C∈δ(B,a)。定理7.3给定一个有限状态自动机Af=(Q,Σ,δ,q0,F),则存在一个正则文法G=(VN,VT,P,S),满足L(G)=L(Af),其中:

(1)VN=Q,VT=Σ,S=q0;

(2)如果δ(B,a)=C,且B、C∈Q,a∈Σ,则P包含产生式B→aC;

(3)如果δ(B,a)=C,且C∈F,则P包含产生式B→a。

定义7.5两个有限状态自动机Af、，若有则称Af和等价。7.2.3上下文无关文法和下推自动机

1.乔姆斯基(Chomsky)范式

定义7.6

上下文无关文法G=(VN,VT,P,S),若P中的产生式形式都是A→BC或A→a,A、B、C∈VN,a∈VT,则G是Chomsky范式文法,或称G为Chomsky标准型。

定理7.4

若G为上下文无关文法,且

,则有Chomsky范式文法,满足L()=L(G)。对给定的上下文无关文法G,求出一个Chomsky范式文法使,称为把G化为Chomsky标准型。

2.格雷巴赫(Greibach)范式定义7.7上下文无关文法G=(VN,VT,P,S),若P中的产生式形式都是A→αβ且不含ε产生式,A∈VN,α∈VT,β∈V*N,则G是Greibach范式文法,或称G为Greibach标准型。

定理7.5

若G为上下文无关文法,且,则有Greibach范式文法,满足L(

)=L(G)。对给定的上下文无关文法G,求出一个Greibach范式文法,使,称为把G化为Greibach标准型。

3.下推自动机若文法G中至少存在一对形式推导:和其中，，,，则文法Ｇ称为自嵌套或自嵌入的,非终止符A也称为自嵌套的。若上下文无关文法G的导出包括，和

,其中，则有推导序列即语言L(G)是可数无穷集{uviwxiy|i≥0}。尽管有限状态自动机能够识别正则语言,但不能识别这个集合。这是因为子串vi的出现必须严格地平衡子串xi的出现,而且在L(G)中存在着含有大量v和x的句子,其中,v和x的数量大大超过任何具有有限确定存储量的自动机所能容许的数量。下推自动机有一个辅助存储器,能够处理在导出中使用了自嵌套的句子。下推自动机的辅助存储器是一个容量可以任意大的堆栈,又称为下推存储器。在堆栈中,最新存入的符号把所有先前存入的符号向下推,将自己置于堆栈顶部。下推自动机的一般表示如图7-6所示。图7-6下推自动机定义7.8

一个下推自动机是一个七元组：其中:Q为有限状态集;Σ是有限输入字母表;Γ是有限下推字符表;q0为起始状态;为终止状态集;Z0∈Γ是下推存储器顶端的初始字符;δ是Q×(Σ∪{ε})×Γ→Q×Γ*映射的有限子集。对于一个下推自动机,有两种能接受的语言:

(1)由终止态接受的语言。定义为L(AP)={x|x∈Σ+,从状态q0和栈顶Z0开始,读完字符串x,AP

停在F的一个状态上}

(2)由存储器变空方式接受的语言。定义为L(AP)={x|x∈Σ+,从状态q0和栈顶Z0开始,读完字符串x,AP

的堆栈变为空}

【例7.4】

下推自动机AP=(Q,Σ,Γ,δ,q0,Z0,F),其中,Q={q0,q1,q2},Σ={0,1},Γ={Z,A,B},Z0={Z},F={q0},δ为则字符串x=00110可被下推自动机以存储器变空方式所接受,因为

定理7.6

对于某个下推自动机M1,L是必然存在另一个下推自动机M2,且有L=L(M2)。由该定理可知,若L是M1以空堆栈方式接受的语言,必有另一下推自动机能以终止态方式接受它,反之亦然。

定理7.7

设L(G)是文法G=(VN,VT,P,S)以Greibach标准型产生的上下文无关语言,则存在一个下推自动机AP=(Q,Σ,Γ,δ,q0,Z0,F),使得，其中:

(1)Σ=VT,Q={q0},Γ=VN,Z0=S,

;

(2)如果P包含产生式A→αβ,A∈VN,α∈VT,β∈V*N,则δ中有δ(q0,a,A)=(q0,β)。在此定理中,将状态集合设置为只含一个元素的集合,简化了状态的表达,换句话说,可以不考虑状态所反映的信息,只需关注下推存储器所包含的信息即可。

定理7.8

设L(AP)是下推自动机AP=(Q,Σ,Γ,δ,q0,Z0,F)所接受的语言,则存在上下文无关文法G=(VN,VT,P,S),使得L(G)=L(AP)。7.3高维文法和随机文法上一节研究的文法只适用于描述基元间的左右连接关系,一般用于描述一维的模式。但模式识别中的许多问题不仅仅是一维的,还有二维的、三维的,甚至更高的维数。对于较复杂的模式,就需要研究高维文法。高维文法有很多种,在此只介绍树文法和网文法。7.3.1树文法和识别器树文法是高维文法中应用最广泛的一种。树文法的根本特点是,树中的节点可以拥有多个直接后代节点,描述多重连接关系。

1.树文法树T是一个或一个以上节点的有限集,它具有如下性质:

(1)具有一个唯一的指定为根的节点;

(2)其余节点分到m个不相交的集合T1,T2,…,Tm,其中每一个集合本身都是一个完整的树,被称为T的子树。在树T中,一个节点的直接子节点的数目定义为该节点的秩。假定某个节点a有秩r1,r2,…,rn,该节点的秩的集合记作r(a)={r1,r2,…,rn}。

定义7.9树文法是一个四元组:其中:V=VN∪VT是由非终止符和终止符构成的有限集合;

,Z+表示非负整数,即r={(a,r(a))|a∈V},规定了V中元素的秩;P是形如Ti→Tj的产生式有限集,Ti和Tj都是树;S∈TV是起始树有限集,TV是V中元素作为节点标记的子树集合。

定义7.10

L(GT)为GT生成的语言:其中,TT为用终止符集VT中元素作节点标记的树的集合。如果树文法的所有产生式都具有形式:则称为扩展的树文法。其中,X,X1,X2,…,Xk∈VN,x∈VT,k∈r(x)。

【例7.5】

用树文法描述如图7-7所示的L-C网络。生成该电路的树文法为GT=(V,r,P,S)其中:VN={S,A}

VT={$,Uin,L,C,W}各终止符的秩:r($)={2},r(Uin)={1},r(L)={2,1},r(C)={1},r(W)={0}。图7-7

L-C网络电路图及相应树(a)L-C网络电路图;(b)树

2.树自动机

有限自动机和下推自动机都是从左到右逐个字符扫描输入串,而与树文法对应的树自动机则是从输入树的每个叶节点同时开始并行地扫描到树根。若树句子被树自动机接受了,则判决该树属于给定的模式类,反之,则该树不属于该模式类。定义7.11在Σ上的一个由叶到根的树自动机为其中:Σ即VT是输入符号有限集;Q为有限状态集;FQ为终止态有限集;fa是Qn×Q的一个关系,n是a的秩,Qn是Q的n次笛卡儿积。给定一个扩展的树文法为GT=(V,r,P,S),可以构造一个能识别语言L(GT)的树自动机AT,其中,Q=VN,F={S},对Σ中每个符号a定义一个关系fa,若P中有产生式X→a,则

;若P中有产生式则fa={(X1,…,Xn,X)}。

【例7.6】

设有扩展树文法GT=(V,r,P,S),其中,V=VN∪VT,VN={S,A},VT={x,y,z,$},产生式P为能识别该文法生成的树的自动机AT=({S,A},{S},{fx,fy,fz,f$}),其中四个关系对应产生式P中的四个产生式,即关系fx的解释是将标记为x且无后代的节点(叶节点)指定为状态A,关系fy表示是将标记为y且无后代的节点指定为状态A,关系fz表示是将标记为z且有一个后代A的节点指定为状态A,关系f$表示是将标记为$且有两个后代A的节点指定为状态S。设输入树如图7-8(a)所示。首先使用关系fx和fy给叶节点x和y指定初始状态,如图7-8(b)所示,把状态A给这两个叶节点;第二步,节点z只有一个后代节点且状态为A,根据关系fz给节点z指定状态A,如图7-8(c)所示;最后,根$的两个后代节点均已被指定状态A,根据关系f$把状态S给根节点$,如图7-8(d)所示。因为状态S∈F,所以输入树被树自动机接受。图7-8树自动机工作示意图(a)输入树;(b)给叶节点指定状态;(c)给根的后代指定状态;(d)给根节点指定状态7.3.2网文法网文法是一种二维文法,又称网状文法。网文法生成的句子是以终止符为节点标记的有向图。

定义7.12

一个网文法是一个四元组:其中:VN为非终止符集;VT为终止符集;S为起始网集;P为网状产生式集。一个网状产生式的形式为α→β,E,其中,α和β是子网,E是β的一个嵌套规则,规定把子网β嵌入到网W中用以代替子网α的逻辑关系,具体说就是E规定了怎样使β的节点和原与α连接的每个节点相连。对于起始主网,是一个单点,不受任何限制。

【例7.7】

网文法GW=(VN,VT,P,S),其中,VN={A},VT={a,b,c},S={A},P如图7-9(a)所示,E表示α能被重写为β,并且把β中的节点a和A标记为b和c的邻点连接起来。这个网文法所产生的语言是如图7-9(b)所示的所有网的集合。网文法主要应用于图形中,在使用时往往对产生式加一些限制以简化应用,如取VT为单终止符集合,此时的网文法称为图文法。图7-9例7.7网文法的产生式和生成的句子(a)产生式;(b)生成的句子7.3.3随机文法和识别器在实际的模式识别问题中,被研究的过程往往存在某种程度的不确定性。受不确定因素的影响,一个模式可能由多个文法产生。为解决这类问题,把概率引入结构模式识别,提出了随机文法和随机语言,给每个句子的出现加上概率分布。

1.随机文法与随机语言定义7.13

一个随机文法是一个四元组GS=(VN,VT,PS,S)。其中：VN为非终止符集；VT为终止符集;S∈VN为起始符;PS为随机产生式的有限集合。随机产生式的形式如下:式中:αi∈V*,其中至少有一个非终止符;βij∈V*;Pij是应用这个随机产生式的概率,对于每个产生式而言,要求与使用这个产生式相联系的Pij满足:，由于随机文法的产生式都具有相应的概率,对于从S出发导出终止符串x的过程而言,存在一个相关联的概率。对于x,不仅需考虑它和语言集合之间的从属关系,而且还得确定有几个推导序列能够得到x,以及每个推导序列的相应概率,则随机文法生成x的概率就是每个推导序列的概率之和。设导出x的第j条推导序列为则该推导相应的推导概率为可以简单表示为

定义7.14

一个随机文法生成的随机语言是式中,k为从S出发导出x的路径数目。当k>1时,文法是歧义的;当k=1时,文法是非歧义的。定义7.15对于任意的随机文法GS,相应的特征文法是由GS中除去与每个随机产生式相关的概率而得到的文法。如果一个随机文法的特征文法是0型、1型、2型或3型文法,则该随机文法相应的是0型、1型、2型或3型的随机文法。

2.随机识别器

对于确定文法而言,给定一个句子,可以通过自动机判断它是否属于给定的语言集合。随机文法生成的语言也会有等价的以随机方式工作的识别器。识别随机正则文法的识别器是随机有限自动机,与随机上下文无关文法对应的是随机下推自动机。

定义7.16

一个随机有限自动机是一个六元组:其中:Q为状态有限集;Σ为输入符号有限集;q0为起始状态;

为终止态有限集;δ是Q×Σ→2Q的映射;D为赋予这个映射的一组概率值。假定当前状态为q,输入符为a∈Σ,下一映射状态集为{q1,q2,…,qn},即δ(q,a)={q1,q2,…,qn}。令P(qi|a,q)表示由这个集合中选择状态qi的概率,如果对Q×Σ中(q,a)的所有组合都成立,则称AS是真正的。在识别过程中,AS从q0出发,在扫描完x后,经由nx条可能路径停在F中的一个状态上,若Pi(x)是某一条路径的概率,则自动机识别x的概率是AS接受的语言是

定理7.9给定一个随机正则文法GS,可以构造一个随机有限自动机AS,使得L(AS)=L(GS)。构造随机有限自动机AS时,Σ=VT,Q=VN∪{T}∪{R},q0=S,F={T}。其中:T为一附加的终止状态;R为一附加的拒绝状态,利用附加的拒绝状态使概率归一化以保证AS是一个真正的随机自动机。δ,D根据PS定义如下:

(1)若，则

(2)若，则

(3)R是陷阱态,

，

(4)为使AS为真,对于状态q和终止符a的每一组合,将R放在δ(q,a)中,定义定理7.10给定一个随机有限自动机AS=(Q,Σ,δ,q0,F,D),可以产生一个随机正则文法GS=(VN,VT,PS,S),使得L(GS)=L(AS)。7.4句法分析对于任意模式,经过预处理并对模式分解提取基元后,可得到表征模式的句子或串,然后进行判断,若该串能被某种文法所接受,则属于该文法所生成的语言。识别方法可分为两种:一种是采用自动机作为识别器;另一种是通过句法分析进行识别。前两节介绍的自动机识别器,本质上就是对输入串进行从左到右的分析,以判断该输入串是否被自动机所识别,若能被接受,则输入串属于自动机对应某类文法生成的语言。自动机识别模式样本的过程,实际上是对模式进行句法分析的过程,其特点是比较简单,计算量比较小,但对模式结构的剖析不够。利用句法分析可根据文法判断待识别模式属于某一类,同时通过对模式结构的深入剖析,可反过来改进相应的文法。7.4.1穷举法穷举算法有两种基本方式:自上而下的分析方法和自下而上的分析方法。

1.自上而下的分析方法对于给定的串x∈V+T,应该给定文法G,由起始符S开始,使用产生式逐步导出给定的串。在导出过程中,句型的字符数目不断增加,若还没有达到给定串的长度|x|,句型中就不存在非终止符了,或者在导出过程中,句型中还存在非终止符,其长度达到或超过|x|,则给定串不被接受。

【例7.8】给定文法G=({S,A},{a,b},P,S),产生式P为S→Ab,S→ASb,A→a。用自上而下的方法分析串x=aabb。解利用产生式集,从S开始,有下列三个导出序列:(1)(2)(3)导出序列(1)在还没有达到被分析串x的长度前就终止了,导出序列(2)在没有终止前就超过了串x的长度,导出序列(3)是串x的正确导出路径,采用的是最左推导。为了方便,可约定在同一种分析算法中,都使用最左推导,或者都使用最右推导。一般地,自上而下的分析方法用最左推导,自下而上的分析方法用最右推导。但不论是哪一种方法,均有很强的试探性。试探时产生式的选择和运算的次序是决定分析速度的重要因素。一般而言,分析算法的效率较低。在实际应用中,上例中的三个导出序列可以并行处理,以节省算法时间。

2.自下而上的分析方法

给定串x∈V+T和文法G,从串x开始,反向使用产生式,导出可能形成串x的属于(VN∪VT)+的串,在反推过程中,不断用非终止符代替子串,直到反推到起始符S,并得到相应的串列。一般情况下,反推的路径不是唯一的,对给定的串,使用同一文法,可能会存在多个串列。

【例7.9】给定文法G=({S,A},{a,b},P,S),产生式P为S→Ab,S→ASb,A→a。用自下而上的方法分析串x=aabb。解反向使用产生式集,从串x=aabb开始,反推到起始符S:

(1)对aabb,反向使用产生式A→a,变成Aabb;

(2)对Aabb,反向使用产生式A→a,变成AAbb;

(3)对AAbb,反向使用产生式S→Ab,变成ASb;

(4)对ASb,反向使用产生式S→ASb,变成S。即得到一个串列aabb,Aabb,AAbb,ASb,S。如果选用不同的反推路径,可以得到另外两个串列,分别是aabb,aAbb,aSb,ASb,S

和aabb,aAbb,AAbb,ASb,S。在实际应用中,为避免同时研究所有的序列,可任意选择一个句柄进行化简,产生一个单一串列,同时准备好反向跟踪判决点,当简化停顿时,试验其他的可能性。7.4.2

Cocke-Younger-Kasami算法无论是自上而下的分析方法还是自下而上的分析方法,效率都很低,随着串长|x|的增加,所需时间按指数增加。而用CYK(Cocke-Younger-Kasami)算法进行分析时,时间随串长|x|的增加,正比于|x|3。

CYK算法要求文法G=(VN,VT,P,S)是上下文无关文法,且是Chomsky标准型,即P中的产生式形式是A→BC或A→a,A、B、C∈VN,a∈VT。

CYK算法是一种自下而上的分析算法,它的关键是对串长|x|=n的待分析句子构造一个(n+1)×(n+1)的识别矩阵。矩阵的构造方法是:方阵主对角线以下的元素全设为0,主对角线上的元素由待分析字符串的各字符构成,主对角线以上的元素由文法G的非终止符构成。假定待分析字符串为x=a1a2…an,具体步骤如下:

(1)构造主对角线。左上角元素t00=0,从t11开始到tnn依次为字符串x的各字符a1到an。

(2)构造主对角线以上紧靠主对角线的元素,即ti,i+1(i=0,1,…,n－1)。从字符串x的第一个字符a1开始,从左到右分析每个字符,如果产生式集中有一个产生式A→ai,则令ti－1,i=A。这表示,对于主对角线上的每一个终止符ai,将所有可能导出它的非终止符写在它上方的空格中。

(3)按平行于主对角线的方向,逐层往上填写矩阵的各元素,即对每个d=2,3,…,n,赋给tij(i=0,1,…,n－d;j=i+d)字符。其中：i是矩阵元素的行标号;j是矩阵元素的列标号;d为元素离主对角线的层数。给元素tij赋值时,考虑第i行下面及第j列左边的元素对:如果文法的产生式集中有A→BC,其右边第一个非终止符B与上面某个元素对的第一个元素相同,第二个非终止符C与同一元素对的第二个元素相同,则将产生式左端的非终止符A赋给tij。tij中的非终止符有可能超过一个,也有可能为空。待分析字符串x=a1a2…an是否由文法产生的充要条件是:起始符S是元素t0n中的一个符号。

【例7.10】

给定上下文无关文法G=(VN,VT,P,S),其中,VN={S,A,B,C},VT={a,b},P为S→AB,S→AC,A→a,B→b,C→SB。这个文法是Chomsky标准型,设输入串为x=aabb,用CYK算法分析是否为给定文法产生的句子。

解输入串长度|x|=4,构造一个5×5的识别矩阵,接下来具体步骤如下：

(1)构造主对角线。将主对角线上的元素t11、t22、t33、t44分别设置为a、a、b、b。

(2)构造主对角线以上紧靠主对角线的元素。因为有A→a和B→b,所以t01=t12=A,t23=t34=B。

(3)d=2,计算t02、t13

和t24:对于t02,因为t01=A,t12=A,P中没有非终止符Y→AA的产生式,所以

;对于t13,因为t12=A,t23=B,P中有产生式S→AB,所以t13=S;对于t24,因为t23=B,t34=B,P中没有非终止符Y→BB的产生式,所以

。识别矩阵构造完成,如表7-1所示。t0n=t04中含有起始符S,说明文法所产生的语言含有句子x=aabb,即x属于给定文法所代表的那一类模式。表7-1例7.10的识别矩阵

ASAASCABBBb7.4.3Earley剖析算法厄利(Earley)剖析算法是一种自上而下的剖析算法,其特点是沿着所有可能的剖析式同时进行剖析,以提高剖析效率。通常,Earley算法的时间正比于输入串长度的三次方。Earley剖析算法适用于所有的上下文无关文法,不要求转化为Chomsky标准型或Greibach标准型。因此,Earley算法的剖析过程可针对原来的子模式和基元进行,能较好地反映模式的结构关系。

【例7.11】

有上下文无关文法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→a。设输入串为x=a*a,用Earley算法分析是否为给定文法产生的句子。

解用Earley算法得到对x=a*a的剖析表如下:I0:I１:I2:I3:因为［S→T·,0］在I3中,所以x=a*a属于L(G)。7.5文法推断7.5.1文法推断的概念文法G产生的语言L(G)是由起始符S开始根据G推出的所有终止符串组成的集合,即,但并非V*T中的所有终止符串都属于L(G)。

是包含所有由VT的元素组成但不属于语言L(G)的终止符串的无穷集,称为L(G)的补集。可见,V*T被分为两个子集,即

以S(G)表示的样本定义为集合R+∪R－,有称R+为正样本集,R－为负样本集。若G中定义的每个产生式规则至少被用来产生R+的一个元素,则称语言L(G)的正样本集R+是结构完备的。以一个样本句子的集合为基础来学习文法的过程称为文法推断。文法推断的实质是推断一个未知文法G的句法规则。推断的依据是文法语言的一个有限样本集S(G),即属于L(G)的一个有限集R+和属于L(G)的补集的一个有限集R－,推断出的文法是一组规则,它们既可以描述文法语言中的给定有限集,也可以预测给定集以外的其他句子,这些句子与给定集在某种意义上具有相同性质。7.5.2正则文法的推断

1.规范确定文法和导出文法通常的文法推断是从现有的R+和R－来获得文法G,而最简单的推断是由R+得到仅仅能产生正样本集R+的限定文法。规范确定文法是只能产生给定正样本集中句子的正则文法。假定正样本集R+={x1,x2,…,xm},推断相应的规范确定文法,具体步骤如下:

(1)检查R+中所有的链(字符串),得到所有的终止符,若终止符相同,则只保留其中一个,将这组终止符作为VT。

(2)根据R+中每个形为xi=ai1ai2…ain的链,得出恰好产生链xi的产生式集合:其中:S为待推断文法的起始符;Zij(j=1,2,…,n－1)为待推断文法的非终止符。由正样本集R+中所有链得出的全部非终止符和S构成非终止符集合VN,R+中所有链得出的全部产生式构成产生式集P。

【例7.12】

设正样本集R+={01,001,101,0101},试推断出规范确定文法G。

解第一步:由R+可得VT={0,1}。第二步:根据R+中的样本得出产生式和非终止符集:

(1)由x1=01,可得到S→0Z1,Z1→1;

(2)由x2=001,可得到S→0Z2,Z2→0Z3,Z3→1;

(3)由x3=101,可得到S→1Z4,Z4→0Z5,Z5→1;

(4)由x4=0101,可得到S→0Z6,Z6→1Z7,Z7→0Z8,Z8→1

G的产生式集P由以上12个产生式构成,非终止符共有9个,即VN={S,Z1,Z2,Z3,Z4,Z5,Z6,Z7,Z8}。推断出的规范确定文法G对应的状态转移图如图7-10所示,图中的各节点对应非终止符,T为一附加的终止状态。规范确定文法的推断很容易,但存在非终止符数量和产生式数量很多的缺点,不够简练。通过合并非终止符,由正样本集推断出的规范确定文法可以简化为导出文法。图7-10例7.12的规范确定文法状态转移图假定由正样本集推断出的规范确定文法G的非终止符集为VN={S,Z1,Z2,…,Zn},将非终止符适当组合,VN被分组成K+1个子集,得到一个非终止符数量相对较少的新的非终止＋符集VND={SD,D1,D2,…,DK},其中,K<n,SD包含S,每个Dj(j=1,2,…,K)是若干个Zi的组合。非终止符集分组的原则是将相似的产生式合并在一起,则原文法的产生式等效为数量较少的另一组产生式。导出文法GD=(VND,VTD,PD,SD),由文法G=(VN,VT,P,S)导出的规则如下:

(1)GD的非终止符集VND等于VN被分组的子集的集合。

(2)GD的终止符集VTD等于原文法G的终止符集VT。

(3)将原产生式集P中各产生式的非终止符全部替换为GD中对应的非终止符,替换后相同的产生式只保留一个,得到PD。(4)GD的起始符SD等于S。

【例7.13】

利用例7.12使用正样本集R+={01,001,101,0101}推断出的规范确定文法G,求导出文法GD。

解第一步:VTD=VT={0,1}。第二步:将例7.12的非终止符集分割为新的非终止符集其中，，，。第三步:导出等效产生式集PD。获得的导出文法GD=(VND,VTD,PD,SD)对应的状态转移图如图7-11所示,可以看出GD可以产生原文法G所有的正样本集R+。另外,规范确定文法G的非终止符集VN的分组可能存在多种方式,因此G相应的导出文法不只一种。图7-11例题的导出文法状态转移图

2.形式微商文法

定义7.17

链的集合A对于a(a∈V*T)的形式微商(余码)为DaA={x|ax∈A}其中,a可以是一个终止符或一个终止符串,也可以是空串ε。如果a=ε,则DaA=A。从定义可以看出,链的集合A的形式微商是舍去A的前面符号a(a∈V*T)之后剩下的符号串。设a1,a2,…,an是链集合A的各符号,则Da1a2A=Da2(Da1A)成立。也就是说,A对a1a2的形式微商等于A对a1的形式微商,再求a2的形式微商。

定义7.18正样本集R+={x1,x2,…,xm}的形式微商文法为其中,VNC、VTC、PC、S按如下方式计算:

(1)VTC是正样本集R+中各链所包含的全部互异的终止符的集合;

(2)SC=DεR+=R+;

(3)VNC={SC,U1,U2,…,Un},Ui(i=1,2,…,n)是正样本集R+的形式微商,但不包括空串ε;

(4)根据S+及U1,U2,…,Un的形式微商,如果DaUi=Uj,则产生式集PC中含有产生式Ui→aUj,如果ε∈DaUi,则PC中含有产生式Ui→a。

【例7.14】

设正样本集R+={01,001,101,0101},试推断出形式微商文法GC。

解第一步:VTC={0,1}。第二步:根据形式微商的定义,求非终止符集:于是得到利用形式微商,使用5个非终止符、2个终止符和8个产生式就可以产生正样本集R+中的所有链。例题推断出的形式微商文法相应的状态转移图如图7-12所示。图7-12例7.14的形式微商文法状态转移图

3.K-尾文法

定义7.19

设,

,则z关于R+而言的K-尾为其中,|x|为x的长度。由定义可知,K-尾实质上就是在余码的基础上再加上对长度的限制。

【例7.15】设正样本集R+={01,001,101,0101},试推断出K-尾文法GK。

解VTK={0,1}。计算正样本集R+的K-尾,结果如表7-2所示。根据表中数据,按K-尾等价的概念可得到K=4,3,2,1时的等价状态:

(1)K≥4时,U3、U5、U6等价;

(2)K=3时,U3、U5、U6等价;

(3)K=2时,S、U2等价,U3、U5、U6等价;

(4)K=1时,S、U2等价,U1、U3、U5、U6等价。表7-2正样本集的K-尾K=3K=2K=1{01,001,101}{01}{1,01,101}{1,01}{1}{01}{01}{1}{1}{1}{