《编译原理》课程教学资源（PPT课件讲稿）第六章 句法结构模式识别

第六章句法结构模式识别 形式语言概述 文法推断 句法分析 自动机理论 误差校正句法分析

形式语言概述 文法推断 句法分析 自动机理论 误差校正句法分析 第六章 句法结构模式识别

61句法模式识别概述 模式用句子形式描述,结构信息十分重要。 模式 句子 子模式 词组 基元 单词 组合关系 自然语言的文法 句法模式识别用小而简单的基元与语法规则描述和识别 大而复杂的模式,通过对基元的识别,进而识别子模式,最终 识别复杂模式 符合某个文法的所有句子的集合 个模式类

6.1 句法模式识别概述 模式用句子形式描述，结构信息十分重要。 模式 子模式 基元 句子 词组 单词 组合关系 自然语言的文法 句法模式识别用小而简单的基元与语法规则描述和识别 大而复杂的模式，通过对基元的识别，进而识别子模式，最终 识别复杂模式。 符合某个文法的所有句子的集合 一个模式类

句子 墙壁f 名词短语 动词短语 冠词 名词动词 副词 D 地板g E The girl studies hard 景物A (b) 子 物体B 背景C 模; 式 三棱柱D长方体E 地墙 板|壁,基 g1f|元 基 面 面‖面‖面 元a‖角 形 图6.1景物结构描述 b 与英文句子句法描述的对比

（a） 句子 名词短语 冠词 动词短语 名词 动词 副词 The girl studies hard （b） 墙壁 f 地板 g E D B b a d c e 景物 A 物体 B 背景 C 三棱柱 D 长方体 E 面 a 三 角 形 b 面 c 面 d 面 e 地 板 g 墙 壁 f 子 模 式 基 元 基 元 （c） 图6.1 景物结构描述 与英文句子句法描述的对比

句法模式识别系统的组成: 图象 分割 模式 句法 输入图象预处理 或分解 描述 分析分类结果 (模式) 和描述 识别 学 基元和 文法 训练样本 关系选择 推断 句法模式识别存在的主要问题: *基元选择尚无通用的方法; *文法推断理论远不及统计学习发展得成熟。 句法模式识别的理论基础:形式语言 20世纪50年代中期乔姆斯基( Chomsky)

句法模式识别系统的组成： 输入图象 （模式） 分类结果 和描述 模式 描述 基元和 关系选择 图象 预处理 分割 或分解 句法 分析 识别 学习 文法 推断 训练样本 句法模式识别的理论基础：形式语言 20世纪50年代中期乔姆斯基（Chomsky）。 * 基元选择尚无通用的方法； * 文法推断理论远不及统计学习发展得成熟。 句法模式识别存在的主要问题：

§6-2形式语言概述 、基本概念 1、字母表:与所研究的问题有关的符号集合 B V1=A, B, C, D], V2a, b, c, d] 2、句子(链):由字母表中的符号所组成的有限长度的符号串。 3、句子(链的长度:所包含的符号数目。例:|ab3c3=9 4、语言:由字母表中的符号组成的句子集合,用L表示。 例:字母表v={a,b 1={ ab, aab. abab}有限语言 L2={a"bhm=012}无限语言 5、文法:在一种语言中,构成句子所必须遵循的规则的集合, 用G表示。L(G)表示由文法G构成的语言

§6-2 形式语言概述 一、基本概念 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中的符号组成的所有句子的集合,包括空句子 A在内。例:V={A,01,001} 7、V+:不包括空句子在内的句子集合,即V=V-(入) 8、V1;终止符,不能再分割的最简基元的集合,用小写字母 表示。Vr{a,b,c 9、V:非终止符,由基元组成的子模式和句子的集合。用大 写字母表示。VN={AB,C} V,Ⅵ的关系:V∩V=(空集) Vr∪V=∨(全部字母表) 10、产生式(再写规则)P:存在于终止符和非终止符间的关系式。 例:α→β,a∈M,β∈WⅥ 11、文法的数学定义:它是一个四元式,由四个参数构成 G=VN.VI P,S]

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}

终止符组成的字符串: 用英文字母表尾部的小写字母x,y,v,w等表示 终止符和非终止符组成的混合字符串 用希腊字母a,B,y等表示。 性质:V∪vx=V(字母表)V∩V=p(空集) P:生成式的有限集。用文法产生句子时的重写规则 P:a→>B 字符串 替换 字符串 S:起始符,代表模式本身,特殊的非终止符 用生成式构成句子时,必须由左边是S的生成式开始

终止符和非终止符组成的混合字符串： 用英文字母表尾部的小写字母x，y，v，w等表示。 终止符组成的字符串： 用希腊字母α，β，γ等表示。 性质： VN VT =V （字母表） VN VT =  （空集） P：生成式的有限集。用文法产生句子时的重写规则。 P： →  字符串 替换 字符串 S：起始符，代表模式本身，特殊的非终止符。 用生成式构成句子时，必须由左边是S的生成式开始

一种语言有一种文法,由文法G构成的语言用L(G表示: L(G)={x|x∈V,且S→x} 文法G构成的句子V中字符组成的文法G的 由终止符组成所有句子的集合推导关系 “≥”零次或多次地应用推导关系 “S→x”:句子x从起始符S开始利用文法G的生成式, 经逐步推导得到

一种语言有一种文法，由文法G构成的语言用L(G)表示： ( ) { | , } * L G x x V S x G T  =  且  文法G构成的句子 由终止符组成 VT中字符组成的 所有句子的集合 文法G的 推导关系 “   G ” ：零次或多次地应用推导关系 G  “ S x G   ”：句子 x 从起始符 S 开始利用文法 G 的生成式， 经逐步推导得到

例61给定文法G=(V,Vr,P,S),其中VN={A,B,S}, r={a,b,c},P的各生成式为 ①S→ac,②A→、aAc,③A>B ④B→>bB,⑤B>b 判断x=abc是否属于语言L(G)? Hl: SaAc aaAcc aaBcc aabcc 是 说明: 利用文法构成句子时,除第一个生成式必须利用左边 为起始符S的生成式外,其余生成式使用的先后次序及重 复使用的次数都不受限制

例 6.1 给定文法 G (V ,V , P, S ) = N T ，其中 V {A, B, S} N = ， V {a, b, c} T = ，P 的各生成式为 ①S →aAc，② A→aAc，③ A → B ④ B →bB ，⑤ B →b 判断 x = aabcc 是否属于语言 L(G ) ？ S aAcaaAccaaBcc aabcc ① ② ③ ⑤ 利用文法构成句子时，除第一个生成式必须利用左边 为起始符 S 的生成式外，其余生成式使用的先后次序及重 复使用的次数都不受限制。 是 说明： 解：

短语结构文法 0型文法(无限制) 设文法G=(VAVr,P,S) VN:非终止符,用大写字母表示 Vr:终止符,用小写字符表示 P:产生式 s:起始符 生式P:α→β,其中α∈V,β∈Vα,β无任何限制 (V不包括空格,V包括空格) 例:0型文法G=(NV,P,S) N=S, A,B] P:①S→aAbc②Ab→bA③Ac→Bbcc ④bB→Bb⑤aB→aAaB-→N(空格)

二. 短语结构文法 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→λ(空格)