《句法结构模式识别课件》由会员分享，可在线阅读，更多相关《句法结构模式识别课件（107页珍藏版）》请在金锄头文库上搜索。
1、第七章句法结构模式识别,形式语言概述 文法推断 句法分析 自动机理论 误差校正句法分析,7-1 形式语言概述 一、基本概念 1、字母表：与所研究的问题有关的符号集合。 例：V1=A,B,C,D, V2=a,b,c,d 2、句子(链)：由字母表中的符号所组成的有限长度的符号串。 3、句子(链)的长度：所包含的符号数目。例: |a3b3c3|=9 4、语言：由字母表中的符号组成的句子集合，用L表示。 例：字母表V=a,b L1=ab,aab,abab 有限语言 L2=anbm|n,m=0,1,2.无限语言 5、文法：在一种语言中，构成句子所必须遵循的规则的集合，用G表示。L(G)表示由文法G构成的
2、语言。,6、V*:由字母表V中的符号组成的所有句子的集合，包括空句子在内。例： V*,01, 001 7、 V:不包括空句子在内的句子集合，即VV*() 8、VT: 终止符，不能再分割的最简基元的集合，用小写字母 表示。 VT=a,b,c 9、 VN: 非终止符，由基元组成的子模式和句子的集合。用大 写字母表示。VN=A,B,C VT， VN的关系： VTVN= (空集) VT VN= V（全部字母表） 10、产生式(再写规则)P：存在于终止符和非终止符间的关系式。 例： ， VN ， VN, VT. 11、文法的数学定义：它是一个四元式，由四个参数构成。 G=VN, VT, P, S,二.
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: SaAbc AbbA AcBbcc bBBb aBaaA aB(空格),SAabcabAcabBbccaBbbcc bbcc 此文法可以产生：X=anbn+2cn+2 n0 X|n=0=bbcc 由0型文法产生的语言称为0型语言。 2. 1
4、型文法（上下文有关文法） 设文法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, c P: SaSBC CBBC SabC bBbb bCbc cCcc 1S21aSBC2, bBbb 对于SaSBC 1= , 2= , A = S, B=aSBC,并且|S|aSBC| 符合1型文法规则 对于bBbb 1= b, 2= ,A = B, B=b,并且|
5、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 = (
6、VN,VT, P, S) VN = S, B, C VT = a, b P: 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) Fa SS+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a,两种方法替换非终止符： 最左推导：每次替换都是先从最左边的非终止符开始，例如上边的例子。我们经常采用最左推导。 最右推导：每次替换都是先从最右
7、边的非终止符开始， 例如： 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
8、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,头,头,尾,尾,一元算子 一个基元的头或尾可以与另一基元的头或尾相连而成为 模式串，并可设
9、置一些较复杂的联结关系和进行各种运 算。 例：文法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,求表达式的规则： 脱括号由内往外的次序进行，无括号由左向右进行 对于
10、连接基元组成基元结构，必须符合规定的连接 点头，尾数目 例：给出一个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,
11、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-
12、1.nYn,n-1 YiVN 若i VN,则令Yi=i；若i VT,再引入Yii,例：把文法G = (VN,VT, P, S)变成Chomsky范式 VN = S, A, B VP = a, b P: SAB，Aa, AabABa，Bb 把SAB，Aa,Bb放入 中 AabABa，A12345， 其中1=5=a, 2=b, 3=A, 4=B AY1Y2345, Y2345Y2Y345, Y345Y3Y45, Y45Y4Y5, 3,4VN Y345AY45, Y45BY5, 125VT 引入新的产生式，Y1a, Y2b, Y5a,符合chomsky范式文法，文法G2 = (VN,VT, , S)
13、 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,
14、aVT, VN*(带空格) 则此文法称为Greibach范式。 例：上下文无关文法 G = (VN,VT, P, S) VN = S,C, VT = a, b, c P形式：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)=2 P: SK Aa Bb Aa Bb SK,a,b,A,B
