模式识别之句法分析

1、1、句法分析相关概念一、基本概念一、基本概念1、当各类模式的文法产生之后，就可以进行识别分类。对任一待识别的模式x，逐一用各类模式的文法来进行识别，如果某一文法Gi可以生成x，则它就应属于该文法。根据文法进行句法模式识别一般有两种方法，一种称为句法分析句法分析，一种采用自动自动机机识别。2 2、句法分析：句法分析：利用文法对未知类别的句法模式进行识别或分类的过程。例：例： 已知文法G = (VN,VT, P, S)，VT =（0,1），VN =（S, A, B, C） 其中P: S1A,S0B,S1C,A0A,A0，B0,C0C,C0,C1B 分析未知句子：x1=10010和x2=10110是

2、否可以由P产生。二二、标、标准形式文法准形式文法 在句法分析和自动机的一些算法中，有时要求标准化文法，下面介绍一种常用的标准文法即Chomsky范式。1、乔、乔姆斯基姆斯基(Chomsky)范式范式 一种上下文无关文法，如果它的每个产生式P都符合两种形式： ABC (A,B,CVN) ，即： 非终止符非终止符非终止符（双非终止符形式） Aa (AVN, aVT) 非终止符终止符（终止符形式） 则该文法称Chomsky范式。 已知上下文无关文法 G1 = (VN , VT , P , S)用以下步骤产生Chomsky范式的等价文法 G2 = (VN, VT, , S) 将中已经是ABC，Aa形式

3、的产生式放入 中 中其它的产生式形式为A 12.n，其中iVN或 iVT用下面的产生式集合代替： AY1Y234.n Y234.nY2Y34.n Yn-1 nYn-1Yn , YiVN若i VN,则令Yi=i；若i VT,再引入Yii PP例：把文法G1 = (VN,VT, P, S), VN = S, A, B,VT = a, b P: SAB，Aa, AabABa，Bb变成Chomsky范式。把SAB，Aa,Bb放入 中把AabABa写成A12345，其中1=5=a, 2=b, 3=A, 4=B。 引入AY1Y2345, Y2345Y2Y345, Y345Y3Y45, Y45Y4Y5, 则

4、Y1=a, Y2345=bABa,Y2=b, Y345=ABa,Y3=A,Y45=Ba,Y4=B,Y5=a3VN Y345AY45为双非终止符形式 1，2，5VT引入新的产生式，Y1a, Y2b, Y5a则AY1Y2 3 4 5 ， Y2345Y2Y345 , Y45Y4Y5化为双非终止符形式。符合Chomsky范式文法为G2 = (VN,VT, , S) VN = Y1，Y2345, Y2，Y345, Y45, Y5, S, A, B,VT = a, b :AY1Y2345,Y1a,Y2345Y2Y345,Y2b,Y345AY45, Y45BY5, Y5a, SBA, Aa, Bb PPP2

5、、 句法分析主要方法一、用句法分析作模式识别一、用句法分析作模式识别设给定训练样本为M类即：1, 2, M 每类有N个样本，如1的训练样本为：S=(X1, X2, XN)T由这些样本可以推断出1类的文法G1 , 同样方法可推断出2类的文法G2 , .M类的文法GM .对待识别句子X进行句法分析，若X属于由文法Gi构成的语言L(Gi)，则xi 类。X样本链码X1 XLG2 xX样本链码X2 X样本链码XN 判决XiXXi2 2、状态图法：适用于有限状态文法、状态图法：适用于有限状态文法每一有限状态文法G = (VN,VT, P, S)都可以用一相应的状态图来表示，并规定：VN中的每一非终止符表示

6、一个状态，起始符S为始态，引入的T表示终态。每一Ai态到Aj态间的通路根据AiaAj的代换式标以a，每一Ai态到T态间的通路根据Aib的代换式标以b，则可以得到对应于给定的任一个有限状态文法G的状态图。例：G = (VN,VT, P, S) VT =（0,1）,VN =（S, A, B, C） P: S1A, S0B, S1C, A0A, A0，B0, C0C, C0, C1BSCBAT1100010由状态图可以知道此文法可以识别的句子X1=10n+1 , X2=00 , X3=10n10, X4=10n+1未知句子：由状态图可知x1=10010(可以识别)x2=10110(不可以识别)00状

7、态图3 3、填充树图法、填充树图法( (适用于上下文无关文法适用于上下文无关文法) )：当给定某待识别句子X及相应的文法G时，我们建立一个以X为底，S为顶的三角形，按文法G的产生式来填充此三角形，使之成为一个分折树。若填充成功表明 否则填充树有两种方法由顶向底剖析法由底向顶剖析法填充树图法在填充三角形时应遵守三条原则：首位考察：首先考虑选用某个产生式后能导出X的 第一个字符用某产生式后，不能出现X中不包含的终止符用某产生式后，不能导致符号串变长(变短)(GLX )(GLX SX由顶向底(由上而下)剖析例：G = (VN,VT, P, S) , VT =（0,1）,VN =（S, A, B）P:

8、 S1 SB1 SB B1A BB1A A0A A0设：X=1000，用由上而下剖析方法判断X是否属于L(G)BB10AASBS1ASA00 X=1000L(G)产生句子X的过程为：SB1A10A100A1000由底向顶(由下而上)剖析例：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 用Ib用Ic 用TI用TIa f b g ca f b g cIa f b g cIIa f b g cIIIa f b g cITIIa f b g cITIIT

9、a f b g cITIITTa f b g cITIITT Sa f b g cITIITTS用TIgT用ST用STfS S X=afbgc L(G)STfSIfSafSafTafIgTafbgTafbgIafbgc三、杨格三、杨格(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 L(G)是否成立. 首先将上述文法

10、化为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

11、，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,根据

12、所给出的文法算得的识别表如下： 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 表中每一位置由三个符号表示。头两个即i和j，而第三个是非终止符(现为S,A,B,见表中第一列)。i1栏中第2列(j=2)与B行相交的位置即为(1, 2, B),其余类推。表中(1, 2, B)位置上有 ，代表对于所给文法，B可导出i=1,j=2的子串，即

13、“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符合给出的文法。反之，即判不符合此文法。020SBSA 建立识别表的

14、递推规则递推规则：将要决定 或 的位置表为(i, j, k)通用形式。K代表非终止符。又将r(i, j, K)称为(i, j, k)位置的识别值。此值为1或0，分别表示(i, j, k)位置上是 或 。计算r(i, j, K)(也即决定 或 )的步骤是：(i)算出其中K1,K2代表KK1K2.例如：ABS,K=A, K1=B, K2=S.),1,1(),1(),2,2(),2(),1,1(),1(212121KijrKjirKjirKjrKjirKjr（1）解释如下：1、设有一待识别的句子为a1a2a3ajaj+1aj+2aj+i-1aj+ian,其中一个子串为ajaj+1aj+2aj+i-1

15、，引入符号（i,j）=ajaj+1aj+2aj+i-12、(i,j)= aj aj+1aj+2aj+i-1=(1,j) (i-1,j+1)或 (i,j)= ajaj+1 aj+2aj+i-1=(2,j) (i-2,j+2)或 . (i,j)= ajaj+1aj+2aj+i-2 aj+i-1=(i-1,j) (1,j+i-1)3、分析r(i,j,k)= r(1,j,k1) r(i-1,j+1,k2) 设r(1,j,k1)=1，即k1 (1,j) 设r(i-1,j+1,k2)=1，即k2 (i-1,j+1) 因为kk1k2(1,j) k2(1,j) (i-1,j+1)= (i,j) 所以r(i,j

16、,k)=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后的各值，余类推。),1,1(),1(),2,2(),2(),1,1(),1(212121KijrKjirKjirKjrKjirKjr现作为例子用递推规则考察(2, 2, A)中的 或 。由于左侧为A的代换式只有ABS一个，故此时对于(1)式只需计算r(1, 2, B) r(1, 3, S)=1 1=1 ,即(2, 2, A)应打。此结果与前面分析得到的相符