第七章句法结构模式识别 形式语言概述 文法推断 句法分析 自动机理论 误差校正句法分析
第七章 句法结构模式识别 形式语言概述 文法推断 句法分析 自动机理论 误差校正句法分析
§7-1形式语言概述 、基本概念 1、字母表:与所研究的问题有关的符号集合。 B6 V=A, B, C D V2a, b, c, d 2、句子(链):由字母表中的符号所组成的有限长度的符号串。 3、句子(链)的长度:所包含的符号数目。例:|a3b3c9 4、语言:由字母表中的符号组成的句子集合,用L表示。 例:字母表V={a,b} L1={ab, aab. abab}有限语言 2={a" bm012}无限语言 5、文法:在一种语言中,构成句子所必须遵循的规则的集合, 用G表示。L(G)表示由文法G构成的语言
§7-1 形式语言概述 一、基本概念 1、字母表：与所研究的问题有关的符号集合。 例：V1={A,B,C,D}, V2={a,b,c,d} 2、句子(链)：由字母表中的符号所组成的有限长度的符号串。 3、句子(链)的长度：所包含的符号数目。例: |a3b 3c 3 |=9 4、语言：由字母表中的符号组成的句子集合，用L表示。 例：字母表V={a,b} L1={ab,aab,abab} 有限语言 L2={anb m|n,m=0,1,2….}无限语言 5、文法：在一种语言中，构成句子所必须遵循的规则的集合， 用G表示。L(G)表示由文法G构成的语言
6、V*:由字母表V中的符号组成的所有句子的集合,包括空句子 λ在内。例:V*=,01,001} 7、V+:不包括空句子在内的句子集合,即V+=V*-(A) 8、V;终止符,不能再分割的最简基元的集合,用小写字母 表示。Vr{ab,c} 9、Ⅴ:非终止符,由基元组成的子模式和句子的集合。用大 写字母表示。VN={ABC} r,V的关系:V1∩VN=Φ(空集) Vr∪VN=V(全部字母表) 10、产生式再写规则)P:存在于终止符和非终止符间的关系式 例:α→β,a∈VN,阝∈VVr 11、文法的数学定义:它是一个四元式,由四个参数构成 G=IVN VTP, SI
6、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}
二.短语结构文法 1。0型文法(无限制) 设文法G=( VVPS) 非终止符,用大写字母表示 Vr:终止符,用小写字符表示 P:产生式 S:起始符 产生式P:α→β,其中α∈,β∈va,β无任何限制 (V不包括空格V包括空格) 例:0型文法G=(VVpP,S) VN=S,A,B) ①S→aAbc②AbbA③Ac→Bbcc ④bB→Bb⑤aB-→aaA⑥aB→λ(空格)
二. 短语结构文法 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→λ(空格)
⑥ S→Aabc→abAC→ ab bbcc→ aBbbcc→bbcc 此文法可以产生:X=ab+2cn+2n0 X n=0 bbcc 由0型文法产生的语言称为0型语言 2.1型文法(上下文有关文法) 设文法G=( VPS) 产生式P:a1Aa21B02 其中A∈VN,β∈V,a1a2∈V a1Aa2sa1B02,或A≤B 由上下文有关文法构成的语言称为上下文有关语言, 用L(G1)表示,G1:上下文有关文法
S→Aa bc→abAc→abBbcc→aBbbcc→ bbcc 此文法可以产生：X=anb n+2c n+2 n≥0 X|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：上下文有关文法 ① ② ③ ④ ⑥
例:G=( VVP S) VN=S,B,C V=a, b, c) P:①S→aSBC②CB→BC③S→abC④bB→b ⑤bC→bc⑥cCcc 1S2→少1aSBC2,bBλ→bλ 对于S→aSBC ∵:a1=λ,a2=λ,A=S,B=aSBC,并且 Slasc ∴符合1型文法规则 对于bB→bb a1=b,a2=λ,A=B,B=b,并且B|≤b 也符合1型文法规则 产生式都符合1型文法的要求
例：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 λ1 Sλ2→λ1 aSBCλ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型文法的要求
S→→>aSBC→→ aabCBc→→ abbbCo→ aabbCo→> aabbcC→→ aabbcc X-a b 此文法G可产生的语言:L(G)={a"n-1,2} 假设基元 a 语言L(G)可以描述不同的三角型 XE abc X=a2b2c2 b a
S→aSBC→aabCBC→abbBCC→aabbCC→aabbcC→aabbcc ∴X=a2b 2c 2 此文法G可产生的语言：L(G)={anb nc n |n=1,2...} 假设基元 语言L(G)可以描述不同的三角型 X= abc X= a2b 2c 2 a b c ① ③ ② ④ ⑤ ⑥ a b c c c b b a a
2.2型文法(上下文无关文法) 设文法G=( VVPS) 产生式P:A→B其中A∈VN(且是单个的非终止符) β∈V+(可以是终止符,非终止符,不能是空格) 对产生式的限制比较严格 由上下文无关文法构成的语言称为上下文无关语言 例:文法G=( VPS) is,B, C) P:①S→aB②S→bA③A→a④A→aS ⑤A→bAA⑥B→b⑦B→bS⑧B→→aBB
2 . 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
①,aB→abS→abaB→abab abbA→→abba ②"bA→baS→baaB→baab ②babA→baba 例:G=( VLVPS) is, t,Fi Vr={a,+,*(,) P:①S→s+T②S→T③T→T*F④T→F ⑤F→(S)⑥F→a ⑥ S→S+T→T+T→F+T→a+T→a+T*F→a+F*F→a+a*F→→a+a*a
aB→abS→abaB→abab S abbA→abba bA→baS→baaB→baab babA→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→a S→S+T→T+T→F+T→a+T→a+T*F→a+F*F→a+a*F→a+a*a ① ⑦ ③ ④ ③ ⑥ ⑥ ① ① ② ② ② ① ② ④ ⑥ ③ ④ ⑥ ⑥
两种方法替换非终止符: ①最左推导:每次替换都是先从最左边的非终止符开始, 例如上边的例子。我们经常采用最左推导 ②最右推导:每次替换都是先从最右边的非终止符开始, 例如:S→S+T→S+F→S+a→T+a→F+a→a+a
两种方法替换非终止符： ① 最左推导：每次替换都是先从最左边的非终止符开始， 例如上边的例子。我们经常采用最左推导。 ② 最右推导：每次替换都是先从最右边的非终止符开始， 例如： S→S+T →S+F →S+a → T+a → F+a → a+a