模式识别之句法分析.ppt

1、句法分析相关概念 一、基本概念 1、当各类模式的文法产生之后，就可以进行识别分类。对任一待识别的模式x，逐一用各类模式的文法来进行识别，如果某一文法Gi可以生成x，则它就应属于该文法。根据文法进行句法模式识别一般有两种方法，一种称为句法分析，一种采用自动机识别。 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→1B 分析未知句子：x1=10010和x2=10110是否可以由P产生。 二、标准形式文法 在句法分析和自动机的一些算法中，有时要求标准化文法，下面介绍一种常用的标准文法即Chomsky范式。 1、乔姆斯基(Chomsky)范式 一种上下文无关文法，如果它的每个产生式P都符合两种形式： ① A→BC (A,B,C∈VN) ，即： 非终止符→非终止符?非终止符（双非终止符形式） ② A→a (A∈VN, a∈VT) 非终止符→终止符（终止符形式） 则该文法称Chomsky范式。 　 已知上下文无关文法 G1 = (VN , VT , P , S)用以下步骤产生Chomsky范式的等价文法 G2 = (VN, VT, , S) ①将Ｐ中已经是A→BC，A→a形式的产生式放入 中 ②Ｐ中其它的产生式形式为A→ θ1θ2….θn，其中θi∈VN　或 θi∈VT 用下面的产生式集合代替： A→Y1Y234...n Y234...n→Y2Y34...n … Yn-1 n→Yn-1Yn , Yi∈VN 若θi ∈ VN,则令Yi=θi；若θi ∈ VT,再引入Yi→θi 例：把文法G1 = (VN,VT, P, S), VN = {S, A, B},VT = {a, b} P: S→AB，A→a, A→abABa，B→b 变成Chomsky范式。 ①把S→AB，A→a,B→b放入 中 ②把A→abABa写成A→θ1θ2θ3θ4θ5，其中θ1=θ5=a, θ2=b, θ3=A, θ4=B。 引入A→Y1Y2345, Y2345→Y2Y345, Y345→Y3Y45, Y45→Y4Y5, 则Y1=a, Y2345=bABa,Y2=b, Y345=ABa,Y3=A,Y45=Ba,Y4=B,Y5=a ∵θ3∈VN ∴ Y345→AY45为双非终止符形式 ∵ θ1，θ2，θ5∈VT ∴引入新的产生式，Y1→a, Y2→b, Y5→a则A→Y1Y2345， Y2345→Y2Y345 , Y45→Y4Y5化为双非终止符形式。 符合Chomsky范式文法为G2 = (VN,VT, , S) VN = { Y1，Y2345, Y2，Y345, Y45, Y5, S, A, B},VT = {a, b} :A→Y1Y2345,Y1→a,Y2345→Y2Y345,Y2→b,Y345→AY45, Y45→BY5, Y5→a, S→BA, A→a, B→b 2、 句法分析主要方法 一、用句法分析作模式识别 设给定训练样本为M类即：ω1, ω2, … ωM 每类有N个样本，如ω1的训练样本为：S=(X1, X2,… XN)T 由这些样本可以推断出ω1类的文法G1 , 同样方法可推断 出ω2类的文法G2 , ….ωM类的文法GM .对待识别句子X进 行句法分析，若X属于由文法Gi构成的语言L(Gi)，则 x∈ωi 类。 X∈样本链码X1 X∈L{G2} x …… X∈样本链码X2 X∈样本链码XN 判决 X∈ωi X∈Xi 2、状态图法：适用于有限状态文法 每一有限状态文法G = (VN,VT, P, S)都可以用一相应的状态图来表示，并规定：VN中的每一非终止符表示一个状态，起始符S为始态，引入的T表示终态。每一Ai态到Aj态间的通路根据Ai→aAj的代换式标以a，每一Ai态到T态间的通路根据Ai→b的代换式标以b，则可以得到对应于给定的任一个有限状态文法G的状态图。 例：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→1B S C B A T 1 1 0 0 0 1 0 由状态图可以知道此文法可以识别的句子 X1=10n+1 ,