（计算机软件与理论专业论文）abnf编码协议消息通用解析方法的研究与实现.pdf

；筒蛭 摘要 扩充巴利撕范式a b n f 足干叶；，符m 模式p 雕的格，弋文法j t 义，被广泛使 刖j ：各利t 心用艮：刚络f _ ：f j 一泌消息的编码定义1 1 划a b n f 编i l t b f ( , j 叫络胁c 义_ i i j 息的 凳牮祈t 你足这类洳汉栈歼发托畦盎之，往诲流行凯泌栈交观f 1 1 ，般引对 孥f j 呐一议协食a b n f 规 j j j 集介漩汁争i i j 们斛卡斤梭块。采川这种譬川n 勺斛折 方法，解析协- 议消心时1 i 严格。l 1 1 i - i 。刈1 i 洳议拼篮最复”技解析模块。 本文竹先介纠j 7 扩允巴 ： 斯范式a b n f ，研究j 7 艾法分忻的理沦o 山0 点，提 j f ：r 种攮r 文法分析技术的a b n f 通川解析系统的设汁j 。火帆，案。 ：a b n f 通川解忻系统r fr ，汁先时输入的胁议_ f l j 息编码定义a b n f 舰! i ! 集合的简化处州， j 1 = 址、) ：_ r 刈j 、t1 i a b n f 脱 j 【i j 缇介的一： 投仃僻的州状数扒结构一觇圳州然“ 采川通川迎9 ”降n 0 斛牛j i 饵法，依科r ：埘删树刈m c 义潲，阻进“解析，动态7 f - i ，k 结粜 树保存觯析结粜。这种解析，j 法允沦帆n 斛析的控制流剃还足仃储解析结粜的数 4 一：ir 杉j 1 i i j ，亡十h l ，： ! h ! i 门a b n f 蹦m i j 0 j 6 i 力态确定f 1 0 ，返十r f 虹m * i f - ! j 卜，j i f 夺办 议i _ ：ja b n f 娥则集仑九灭，保证j 螂扭i 办法的迎刚性。 j 通常的擎朋解析疗法相比，a b n f 通川解析系统i 彳r 并性和通川性的特 点。剥。j 有代表性的s i p 协议避乱二较为伞| f | j 的消息解析测试，袭明a b n f 迎川 解析系统能够严格按照m 陂编定义进行消息解析：刈h t t p 羽1s m t p 以戍j e 他随机选取的a b n f 编的l 办议_ 7 i l j 。龃进”潲心解析测试，托叫a b n f 迎川m 1 ，十j i 系统能够l l ：确f 一解析1 ：川出议n q _ l j ， 关键湖： a b n f 范式，文法分析，卜卜文无关义法，递t 卜降分析 ! 里型兰垫垄查兰堡圭笙苎 垒! 坐竺! a b s t r a c t a u g m e n t e d b a c k u s - n a u rf o r m ( a b n f ) i sa k i n do ff o r m a t s y n t a x f o r t e x t - b a s e d s t r i n g ，a n d i su s e di n m a n ya p p l i c a t i o n l a y e r n e t w o r kp r o t o c o l sa s m e s s a g ec o d es y n t a x p a r s i n gt h ea b n f c o d e dp r o t o c o lm e s s a g e si st h ec o r ep a r to f t h ep r o t o c o ls t a c kd e v e l o p m e n t u s u a l l y ，f o rt h ea b n fr u l es e to fag i v e n p r o t o c o l ，a s p e c i a lm e s s a g ed e c o d e r i sd e v e l o p e di nt h ep r o t o c o ls t a c ki m p l e m e n t a t i o n b u tt h i s k i n do f s p e c i a ld e c o d e rc a n l tp a r s et h ep r o t o c o lm e s s a g e ss t r i c t l ya n di t i sn e e d e dt o d e v e l o pd i f f e r e n ts p e c i a ld e c o d e r sf o rd i f f e r e n tp r o t o c o l sr e p e a t e d l y i nt h i s t h e s i s ，a u g m e n t e db a c k u s - n a u rf o r m ( a b n f ) i si n t r o d u c e df i r s t l y t h r o u g h t h es t u d yo ft h et h e o r ya n dm a n yp a r s i n gm e t h o d so f g r a m m a rp a r s i n g , a n e wg e n e r a l p a r s i n gm e t h o d f o ra b n f - c o d e dm e s s a g e sw h i c hi sb a s e do nt h e g r a m m a r - p a r s i n gt e c h n i q u e s i s p r o p o s e d ， a n dt h ed e t a i l e d d e s i g n a n d i m p l e m e n t a t i o n i s p r e s e n t e d s o m e s t r a t e g i e s a r e a d o p t e d t o s i m p l i f y t h e o p e r a t i o n so f t h ea b n f r u l es e t ，a n df o rt h e s i m p l i f i e dr u l es e tar u l et r e e i sd e s i g n e d a c c o r d i n g t ot h er u l et r e e , t h e g e n e r a lr e c u r s i v e d e s c e n tp a r s i n ga l g o r i t h mp a r s e st h e i n p u tp r o t o c o lm e s s a g e sb o t ht h ef l o w - c o n t r o la n dt h ed a t as t r u c t u r ef o rt h ep a r s i n g r e s u l to ft h i sp a r s i n gm e t h o da r eg e n e r a t e dd y n a m i c a l l yf r o mt h ea b n fr u l e s e t t h a tm a k e st h ep a r s i n gm e t h o di n d e p e n d e n to f t h ec e r t a i np r o t o c o la b n fr u l es e t ， a n dc a nb eu s e df o ra l la b n f c o d e d p r o t o c o l s c o m p a r e dw i t ht h ew i d e l yu s e ds p e c i a ld e c o d i n gm e t h o d ，t h eg e n e r a la b n f p a r s i n gs y s t e mi ss t r i c t e ra n dp r o v i d e sam o r eg e n e r a lu s a g e t h r o u g ht h et h o r o u g h m e s s a g e d e c o d i n g t e s tt os t p , a g o o dr e p r e s e n t a t i v ea b n f c o d e dp r o t o c o l ，i ts h o w s t h a tt h eg e n e r a lp a r s i n gs y s t e mc a nd e c o d et h em e s s a g e ss t r i c t l ya c c o r d i n gt ot h e a b n fr u l es e t a n dt h r a u g ht h em e s s a g e - d e c o d i n gt e s tt ot r r t p , s m t p a n do t h e r p r o t o c o l ss e l e c t e ds t o c h a s t i c a l l y , i ta l s os h o w st h a tt h eg e n e r a lp a r s i n gs y s t e mc a n d e c o d et h em e s s a g e so f d i v e r s ea b n f e o d e d p r o t o c o l s k e yw o r d s ：a u g m e n t e db n f , g r a m m a r p a r s i n g ，c o n t e x t - f r e eg r a m m a r , r e c u r s i v e d e s c e n t p a r s i n g ! 曼型兰茎垄奎兰矍圭至兰 一 一墨二兰! 堕 第一章绪论 1 1研究背景与现状 1 9 6 0 年j o h n b a c k u s 和p e t e r n a u r 在a l g o l6 0 程序设计语言中首次提出了 标准巴科斯范式b a c k u s n a u rf o r m ( 简称b n f ) 【l 】，b n f 是一种用来定义语言 文法的元文法( m e t a s y n t a x ) ，可以形式化的精确描述语言。b n f 可以很好的定义 结构化语言的文法。采用b n f 描述语言文法，具有很好的准确性，减少了对于 语言的歧义理解，而且便于机器处理和分析语言。 。 针对不同类型的应用，出现了很多b n f 的派生范式。如i s oe b n f 2 和 e b n ff o rx m l 3 1 等等。其中，b n f 的一个派生范式一一扩充巴科斯范式 a u g m e n t e db n f ( 简称a b n f ) 在互联网的技术规范中被广泛采用，用来定义 格式化的文本消息报文。a b n f 范式平衡了压缩性和简单性，具有合理的表达 能力，采用a b n f 编码，协议消息报文含义一目了然，便于读者理解。a b n f 被广泛的应用于网络协议报文的编码定义中，如s m t p 、h t t p 、s i p 和m e g a c o 等，对a b n f 编码的网络协议消息的准确解析是这类协议的协议栈开发的重点 之一。 在目前流行的协议栈实现中，通常针对专门协议的一套a b n f 规则集合， 设计专用的解析模块来解析基于a b n f 编码的协议消息。在这些专用解析模块 一般采用以下的解析策略： ( 1 ) 从定义开始符号的起始规则开始，依据规则之问的引用关系。自顶向下 进行解析； ( 2 ) 对于一个规则的处理，就是对它的规则定义的右式中每一个子规则依次 进行处理，即对每个子规则设计一段程序代码或调用相应的函数。对于 重要的或结构复杂的规则，单独编写个函数来进行解析，方便被其他 规则重复调用： ( 3 ) 对于部分规则，根据开发人员对于协议规则的理解，依靠一些具有特征 性的字符来划分或识别某些子规则的对应的字符串，省略严格的形式化 文法识别刿断，简化对于子规则的解析。 采用这种专用的解析策略，能够鞍为快速的开发消息解析模块，但是存在 以下不足： 专用解析模块解析的正确性和严格性依赖于开发人员对协议a b n f 规则 的理解t 第1 页 中国科学技术大学硕士论文 第一章绪论 专用解析模块不具有通用性，对每个协议的一套a b n 下规则集合，都需 要重新开发解析模块； 专用解析模块只能应用于指定协议的指定版本，不便于协议实体的升 级。 因此设计一个a b n f 通用解析系统能够解析基于a b n f 编码的不同协 议的消息报文的通用性解析系统足非常必要的。 1 2 研究目标与方案 本文的目标是设计一种a b n f 通用解析系统，能够解析所有基于a b n f 编 码的协议消息，a b n f 通用解析系统独立于具体协议，能够通过配置协议消息 编码定义的a b n f 规则集合然后依据a b n f 规则集合对相应协议的消息进行 准确的解析。 本文采用的研究方案如下： ( 1 ) 对扩充巴科斯范式a b n f 的规则集合进行简化处理，使得在不改变协 议消息编码含义的前提下，简化a b t f 规则集合的操作； ( 2 ) 在简化处理后的a b n f 规则集合的基础上，根据规则之间的关系建立 一种规则的树状数据结构规则树，作为消息解析的依据； ( 3 ) 通过对文法分析理论和方法的研究，在规则树的基础上，设计种针对 基于a b n f 编码协议消息的通用解析算法，使得算法的控制流程与存 储解析结果的数据结构都是根据配置的a b n f 规则集合动态确定的 使解析系统具有与协议消息编码定义a b n f 规则集合无关的性质。 1 3 文章组织结构 本文共分七章： 第一章，概论研究工作背景。 第二章，介绍了扩充巴科斯范式a b n f 。 第三章，研究了文法分析的般理论与方法。 第四章，着重分析了扩充巴科斯范式a b n f 的特性，提出了基于a b n f 编码的协议消息的通用解析系统的设计方案。 第2 页 中国科学技术大学硕士论文第一章绪论 第五章，详细阐述了a b n f 通用解析系统的具体实现策略，介绍了相关核 心算法。 第六章，对a b n f 通用解析系统进行了通用性和严格性的测试，列出了相 应的测试结果。 第七章，对文中的研究工作进行总结和回顾，并展望未来的研究方向和内 容。 第3 页 中国科学技术大学硕士论文 第二章扩充巴科斯范式a b n f 第二章扩充巴科斯范式a b n f 扩充巴科斯范式a b n f 作为一种格式文法定义，被广泛应用在网络协议的 文本消息编码定义中。本章主要介绍了a b n f 的概念和相关的范式定义以及与 b n f 之间的关系等。 2 1 简介 扩充巴科斯范式a b n f ( a u g m e m e d b a c k u s n a u rf o r m ) 是在标准巴科斯范式 b n f 。f a a c k u s - n a u rf o r m ) 基础上扩充的格式文法定义。在早期的a r p a 网络中， 很多网络技术规范都包含了自己的a b n f 范式定义，这样的规范包括电子邮件 规范r f c 7 3 3 1 4 和之后的r f c 8 2 2 1 5 ，并且r f c 7 3 3 和r f c 8 2 2 中的a b n f 范式 定义逐渐成为a b n f 范式的公共引用。1 9 9 7 年，互联网工程任务组i e t f 在 r f c 2 2 3 4 1 6 提取整合了这些a b n f 规范定义，并作了修改和增强。与a s n 1 1 7 1 一样，a b n t 也是用来描述复杂的数据结构的，但a s n 1 主要用于描述二进制 编码，而a b n f 主要用于描述文本编码【8 】。目前版本的a b n f 平衡了压缩性和 简单性，具有合理的表达能力，正在被越来越多的应用于网络协议报文的编码 定义中。 2 2 规则定义 a b n f 文法定义是由套a b n f 规贝j j 集合构成，每条规则左式是规则名， 表示一个非终结符，右式是由若干个子规则通过各种操作符连接而成。子规则 可以是非终结符也可以是终结符，终结符就是字符或字符组，由非负整数表示。 1 ) 规则命名 规则名就是一个规则的名字，是一个符号序列，该符号序列以字母打头， 后跟个字母或数字或连字符( 下划线) 的组合，规则名大小写不敏感。 2 ) 规则格式 一个规则是由这样的序列定义的：r u l e n a m e = e l e m e n t sc r l f 此处r u l e n a m e 指规则名，e l e m e n t s 指一个或多个规则名或终结符通过各种 操作连接起来的规则序列，c r l f 代表回车换行是行结束标志，等号将规则名 和规则的定义分隔开。 3 ) 终结符 对于非终结符的定义最终将分解成串终结符组成的序列，终结符只出现 在规则定义的右式中。终结符是个字符或字符组，在扩充巴科斯范式中有以 下几种形式： 第4 页 中国科学技术大学硕士论文第二章扩充巴科斯范式a b n f 由带基的一个或多个非负整数来说明，如d 1 3和x 0 d x0 a ( 可以压缩表示成x 0 d0 a ) ： 由带基的非负整数的范围来说明，如x 3 0 3 9 ； 由引号包括的字符文本串来说明，如“s i p 2 0 ”。 在扩充巴科斯范式中，一个字符仅仅是一个非负整数，一个字符由带基的 数字字符说明，根据基来解释这些数字，从而确定字符。以下的基是目前已经 定义的： b ：b i n a r y二进制 d ：d e c i m a l 十进制 x ：h e x a d e c i m a l 十六进制 因此： c r= d 1 3 c r= x 0 d 分别说明t u s a s c i i 中回车符的十进制和十六进制的表示。 扩充巴科斯范式字符串形式的终结符对于大小写不敏感，并且这些串的字 符集使用u s a s c i i 字符集。因此： r u l e n a m e = ”a b c ”和 r u l e n a m e = ”a b c ” 将与“a b c ，“a b c ”，“a b c ”，“a b c ”，“a b e ”，“a b c ”，“a b c ”和“a b c ”相匹配。 为了说明某个规则是大小写敏感的，需要单独用数字来说明该规则使用的 字符。例如： r u l e n a m e = d 9 7 d 9 8 d 9 9 或r u l e n a m e= d 9 79 89 9 将仅与只由小写字符a b c 组成的串匹配。 2 3 操作符 在r f c 2 2 3 4 中，a b n f 定义了“连接”、“选择”、“增式选择”、“值域选择”、 “序列组”、“不定循环”、“指定循环”、“可选序列”和“注释9 种操作符。 1 ) 连接 连接操作处于扩充巴科斯范式解析模型的核心，通过列出一系列规则名， 一条规则可用于定义一个简单有序的值串即一连串邻接的字符。例如： f o o= x 6 1 ；a b a r= x 6 2 ；b m u m b l e = f o o b a r f o o 因此规则m u m b l e 与小写字符串”a b a t 匹配。 互联网规范过去允许隐含的线性空白字符( 包括空格符和水平制表符) ，即 在元素两边自由发展以及隐含打印线性空白符，但是扩充巴科斯范式规范没有 提供隐含线性空白字符，任何希望允许在分界符或字符串两边出现线性空白字 符的语法必须显式说明。对于那些被更高层规则多次使用的“核心，规则，在其 第5 页 中国科学技术大学硕士论文 第二章扩充巴科斯范式a b n f 中提供这些空白字符常常是有用的。 2 ) 选择 由斜杠( “) 分隔的元素之间是选择的关系，即可以选择其中的一个元素 ( 选择项) 来匹配。如： f o o b a r 将接受f o o 或b a r 。 3 ) 增式选择 分散的指定一列选择项有时会很方便，一个初始规则可能匹配一个或多个 选择项，然后通过稍后的增式选择的规则定义，增加新的选择项。这对于那些 源于同一父规则集而其他方面独立的规范非常方便。扩充巴科斯范式的增式定 义，使用如下结构： o l d r u l e= |a d d i t i o n a l a l t e r n a t i v e s 阂此规则集 r u l e s e t = a l t l a l t 2 r u l e s e t_ - a l t 3 r u l e s e t= | a l t 4 | a l t 5 与以下说明相同： r u l e s e t= a l t l a l t 2 ，a l t 3 ，a t 4 ，a l t 5 4 ) 值域选择 通过使用连字符( “- ”) 表明可选值域的方式。可以紧缩说明可选数值域。 因此： d i g i t= x 3 0 3 9 等同于： d l g 【t =0 “1 ”2 ”3 “4 ”5 ”“6 ”，”7 ”“8 “，”9 u 连接的数值域不能在同一串中说明，但可以用点号“”来表示数值的连接。 例如，回车换行说明格式如下： c r l f = x 0 d0 a 5 ) 序列组 序列组用小括号来表示，小括号里的元素看作一个单一的元素，其内容严 格排序。因此，e l e m ( f o o b a r ) b l a t 匹配e l e m f o o n a t 或e l e mb a r n a t 。 注意；当个选择项由多个规则名或文字组成时，使用序列组来分区贫， 从而避免读者的误解。因此对于e l e mf o o b a rb l a t 可以采用如下形式代替上述 形式： ( e l e mf o o ) ( b a rb l a t ) 。 6 ) 不定循环 在元素前的操作符“”表示重复。完整形式为： a * be l e m e n t 第6 页 中国科学技术大学硕士论文 第二章扩充巴科斯范式a b n i , 此处a 和b 是可选的十迸制值，表示元素出现至少a 次，至多b 次。 默认值a 是0 和b 是无穷大，囡此* e l e m e n t 允许e l e m e n t 出现任意次，包括 0 次；1 * e l e m e n t 表示e l e m e n t 至少出现1 次；3 * 3e l e m e n t 表示只允许3 次，而 1 + 2e l e m e n t 表示允许1 次或2 次。 7 ) 指定循环 如下形式的规则： ne l e m e n t等同于n 4ne l e m e n t 即e l e m e n t 正好出现n 次。因而2 d i g i t 是一个2 位数，而3a l p h a 是一 个3 字母字符串。 8 ) 可选序列 方括弧包括了一个可选元素序列，表示方括弧内的序列可以出现次或不 出现，如 f o ob a r 等同于0 4 l ( f o ob a r ) 。 9 ) 注释 分号表示注释，从分号开始，直到行末，都是注释内容。注释对规则的定 义的文法没有作用，只是便于读者理解规则。 如：d i g i t = x 3 0 3 9 ：d i g i t 包括0 到9 1 0 ) 操作符的优先级 上述各种操作具有以下优先级关系，优先级依次从高( 结合最紧密) 到低 ( 结合最松散) 字符串，名字格式 注释 值域 循环 分组，可选项 连接 选择 随意混用选择操作符与连接操作符，会引起混淆。通过使用序列分组操作 符可以显式表明连接分组。 2 4核心规则 对于那些被更高层规则多次使用的“核心”规则，r f c 2 2 3 4 给出一个特定 语法的方便的核心，这个核心规则集合作为规则子集，被很多协议消息的a b n f 编码的规则集合包含。核心规则定义如下： a l p h a= x 4 1 5 a x 6 1 7 a ：a - z a z b i t= 0 ，“l ” c h a r= x 0 1 7 f ：除n u l l 以外的任何7 位u s a s c i i 字符 c r= x 0 d ；回车 c r l f=crl f ；互联网标准格式的换行 c t l = x 0 0 1 f x 7 f ；控制字符 d i g i t= x 3 0 3 9 0 9 d q u o t e = x 2 2：”( 双引号) h e x d i g = d i g i t ，”a ”“b ”c ”，”d ”，”e ”，”f ” 第7 页 主里型兰垫查查兰堡圭堕兰 笙三童羔垄呈型堑兰苎竺竖 h t a b = x 0 9；水平制表符 l f= x 0 a：换行 l w s p= + ( w s p c r l f w s p ) ；线性空白字符( 过去的换行) o c t e t = x 0 0 f f ：8 位数据 s p= x 2 0：空格符 v c h a r = x 2 1 7 e：可见( 可打印) 字符 w s p= s p h t a b；空白字符 2 5与b n f 的关系 标准巴科斯范式b n f 通常b n f 用来表示上下文无关文法。 b b t p 的元符号有： ：= 或一表示“定义为”； i表示“或者”： 尖括号用来包括文法规则( 也被称为非终结符) 的名 称。 尖括号把非终结符和终结符区分开来，其中终结符就是由构成它的字符串 表示。在不引起混淆的情况下，非终结符外面的尖括号可以省略。一个定义非 终结符的b n f 规则具有如下形式： 非终结符一一组可选项， 其中，可选项是由终结符和非终结符连接构成，可选项之间由符号j 隔开。 例如，逻辑表达式的b n f 规则定义如下； l o g i c a l _ e x p r e s s i o n _ e x p r e s s i o n “” e x p r e s s i o n e x p r e s s i o n “& & ” e x p r e s s i o n 这表示逻辑表达式由两个e x p r e s s i o n 之间用“旷连接起来组成，或 由两个e x p r e s s i o n 之间用“& & ”连接起来组成。 a b n f 与b n f 的区别包括命名规则、循环、选择、次序独立以及值域选择 具体如下表2l 所示【9 】。 表21 a b n f 与b n f 的比较 子规受i j 出现的次数 群注 项目 选 可选l 类型规则 终结非终结 择 = 0 = lnn 到m组释 符符 【b n f ：= 无无无无无无无 i n t c g e r - l 】 【a b n f n a m e = 0 + l + 1 l * n n * m ( ) o + 1 第8 页 ! 望型兰垫查查兰堡主堕兰 苎三兰芝壅里型堑蔓茎竺 2 6协议消息的a b n f 定义 协议消息的a b n f 编码定义南一组a b n f 规则集合组成，其中起始规则左 边的开始非终结符定义了协议消息，规则之问的关系定义了协议消息的结构。 例如，下面是i p v 6 地址结构的a b n f 规则定义，i p v 6 a d d r e s s 是开始非终结 符，定义了i p v 6 协议的地址结构d o 。 i p v 6 a d d r e s s = h e x p a r t ”：”i p v 4 a d d r e s s 】 i p v 4 a d d r e s s = l4 3 d i g i t ”1 + 3 d i g i t ”1 + 3 d i g i t ”“1 + 3 d i g i t h e x p a r t = h e x s e q h e x s e q ”：” h e x s e q 】：” h e x s e q 】 h e x s e q = h e x 4 + r ”：”h e x 4 ) h e x 4 = l + 4 h e x d i g d i g i t = x 3 0 - 3 9 h e x d i g = d i g i t ，a ”b ”c ”d “e ”f ” 第9 页 皇里翌兰垫查奎兰堡圭丝兰 一兰三兰苎鎏墨墨坌i ! ! 堕 第三章文法及其分析方法 形式文法( 简称文法) 是精确描述形式语言的抽象结构，文法通过一组规 则来界定了一个由有限长度串的集合构成的语言。本章首先介绍文法的概念， 然后对文法中最重要的上下文无关文法理论作了介绍与分析，并对于上下文无 关文法的分析方法进行了讨论。 3 1文法简介 文法由以下四部分构成：终结符的有限集合，非终结符的有限集合，一组 产生式规则集合和开始符号。这样的文法定义了一种形式语言，语言的所有串 都有终结符构成，每个串都可以从开始符号的一个推导获得。 如果一个非终结符出现在个产生式规则的左部，则产生式称为该非终结 符的产生式。串是零个或者多个记号的序列，一个包含零个记号的串称为空最， 记为。从开始符号出发，反复替代产生式中非终结符( 用该非终结符的产生式 的右部来代替非终结符) ，这样文法可以产生一些串，由一个文法的开始符号产 生的串的集合形成了该文法定义的语言 1 1 】【1 2 】。 按照c h o m s k y 的分类法，文法可以分为四类，即0 型、1 型、2 型和3 型， 几类文法的区别在予对产生式施加了不同的限制【1 3 1 【1 4 】。就描述能力而言，0 型强于l 型，1 型强于2 型，2 型强于3 型。并且几种文法是自前向后包含的， 即0 型文法定义的语言包含了1 型文法定义的语言，1 型文法定义的语言包含 了2 型文法定义的语言，2 型文法定义的语言包含了3 型文法定义的语言。 0 型文法( 无限制文法) ，包含了所有的文法，该文法定义的语言等价 于图灵机能够识别的语言。 1 型文法( 上下文有关文法) ，定义了上下文有关语言，等价于线性的 非确定图灵机识别的语言。 2 型文法( 上下文无关文法) ，定义了上下文无关语言，等价于非确定 的自顶向下的自动机能够识别的语言，其产生式规则要求左式只有一个 非终结符。 3 型文法( 正规文法) ，定义了正规语言，等价于有限状态机能够识别 的语言，其产生式要求左式只有个非终结符，右式由一个终结符构成， 或由一个终结符与个非终结符构成。 在这些文法中，2 型文法和3 型文法即 匕下文无关文法和正规文法最为重要， 正规文法用来定义模式( p a t t e r n ) 和程序设计语言的词法结构，上下文无关文 第l o 页 中国科学技术大学硕士论文 第三章文法及其分析方法 法是程序设计语言编译和自然语言处理等领域的文法分析的理论基础。 表3l 文法的c h o m s k y 分类 文法语言识别语言的自动机产生式规则形式 0 型递归可列举的语言图灵机没有限制 1 型上下文有关语言 缄强行非确定图灵机 qa b ayb 2 型上下文无关语言非确定的自顶向下的自动机a v a a 或a ab 3 型正规语言有限状态机 a 一1 3a 3 2 上下文无关文法 3 2 1 上下文无关文法的概念 上下文无关文法，如名称所示，文法中个非终结符的推导与前后的其他 非终结符的推导没有关联，具有独立于上下文的性质。这种文法能够很好的表 达层次化结构的语法定义，上下文无关文法通常采用标准巴科斯b n f 来表达 【1 5 。 从形式上说，上下文无关文法g 是一个四元组 + 4 和5 t ( 3 + 4 ) 。这两个表达式的值是不同的，分别是1 9 和3 5 。 按照通常的算符优先顺序，第二种解释是不允许的。 图3 1 二义性文法的两棵分析树 o rs t r i n g 十4 由于具有多棵分析树的记号串通常具有多种含义，所以需要设计无二义性 文法，或在文法分析过程中增加额外的规定来解决文法分析过程的二义性问题。 第1 2 页 蛐川咖矗 个 蛐、， 4 + 呱、， 他 咖， ， 中国科学技术大学顽士论文第三章文法及其分析方法 3 2 4 左递归 如果文法g 具有一个非终结符a ，使得对某个串存在推导a aa ，则称 g 是左递归的。一些自顶向下的文法分析方法不能处理左递归文法，当出现左 递归产生式时会出现无限循环，采用这些文法分析方法时就需要消除左递归规 则。 对于简单的左递归产生式规则a a n j8 可以用下面两个不含左递归 产生式来代替： a 一口a a 一aa ，l 这种变换没有改变从a 推导出的串集合。 对于一般情况，无论有多少a 产生式，我们都可以用下面的技术来消除直 接左递归，首先把a 所有的产生式放在一起： a aqi i a a 21 iao 。ibl i b 2 f i b 。 其中，每个bi 都不以a 开头。然后用下面的产生式代替a 产生式： a bi a ，j b 2a i fb 。a a 一a 1a i a2 a 1 f q m 1 e 变换后的非终结符a 与变换前的非终结符a 导出同样的串集合，但已经没 有左递归了。 上面的方法可以消除直接左递归，但不能消除包括两步或多步推导的左递 归。如： s a a l ba a e fs dja 非终结符s 是左递归的，因为s = a a = s d a ，但不是直接左递归。对于这 种多步推导的左递归，需要进行非终结符的替换，将存在的间接左递归转换成 直接左递归然后采用上面的方法来消除直接左递归，从而消除文法中的间接 递归： 3 3 上下文无关文法的分析方法 使用分析树的概念。可以定义文法分析：一个文法生成的语言是它的由某 个分析树生成的串的集合，为给定的串找到一个分析树的过程称为这个串的文 法分析。 3 3 1 文法分析方法的分类 1 ) 文法分析的方向 文法分析方法根据分析的方向可以分为两种类型：自顶向下的方法 第1 3 页 中国科学技术大学硕士论文 第三章文法及其分析方法 ( t o p d o w n ) 和自底向上的方法( b o t t o m u p ) ，这是根据在构造语法分析树的过 程中节点的构造顺序划分的。自顶向下的方法首先从树的根节点开始构造，逐 层的向下构造树的节点，直到树的叶结点，这就是模拟从开始符号由产生式推 导出串的过程。自底向上的方法则相反，从树的叶结点开始构造，逐层向上的 构造，通过的相关联的已有子树根节点来构造包含这些子树的更大子树的根节 点，直到最后构造串对应的分析树的根节点，这是与由产生式产生字符串的过 程相反，从字符串规约到开始非终结符。 对于一个有以下规则组成的简单文法定义： s a bds a d b bcd d ( 3 2 ) 对于字符串“a b e d ”，自顶向下的分析和自底向上的分析过程分别如图3 2 和图33 所示： a o o oo 图3 2 自顶向下的分析方法 图3 3 自底向上的分析方法 第1 4 页 b b e b bc d d s a b d 纨芦0 ! 里型兰垫查盔兰堡! ：丝苎 墅三兰奎堕墨苎坌翌丝 2 ) 文法分析对于串的方向性要求 文法分析方法根据对于串的要求，可以分为无方向性( n o n - d i r e c t i o n a l ) 的 分析方法和有方向性( d i r e c t i o n a l ) 的分析方法。 有方向性的分析方法 有方向性的分析方法从左到右的处理输入记号，这样分析方法可以在待处 理串没有完全看见的情况下就开始分析，可以一边分析一边输入。这些有方向 性的分析方法从原理上来讲是基于一种分析自动机的，对于自顶向下的分析方 法自动机进行预测和匹配操作，对于自底向上的分析方法自动机进行移进和规 约操作。 而有方向性的分析方法根据在分析过程中是否有回溯操作可以分为两类： 确定性的分析方法和不确定的分析方法。 在文法分析过程中遇到多个分支选择时，确定性的分析方法根据当前已有 的信息和有限数目的后继记号，选择正确的分支。确定性的分析方法有l l 、 s l r 、l a l r 和l r 等，这类分析方法不需要回溯操作，效率高，但对于文法有 一些限制要求，只适用于一部分特殊的上下文无关文法的分析，如通常程序设 计语言的编译器构造。 而对于更一般的上下文无关文法，存在某些情况，在分析的过程中面临多 个选择分支时，无法从当前已有的信息和有限数目的后继记号来进行正确的选 择。这就需要对多个可能的分支都进行尝试，对于错误的分支也要继续向前分 析，直到在某个位置无法继续分析时才会报错返回。 不确定的分析方法通过搜索技术来遍历各种可能性，寻找一个或所有的合 法匹配。通常有两种搜索方法：深度优先搜索( d e p t h - f i r s ts e a r c h ) 和广度优先 搜索( b r e a d t h - f i r s t s e a r c h ) 。在深度优先搜索中，集中于一个部分解决的问题， 如果在某一点p 有多个分支，专心于某一个分支，并存储其它的分支为后来的 处理做准备。如果在继续处理过程中当前分支失败( 或成功，但需要求出所有 的合法匹配) ，必须返回到p 点，选择一个尚未处理的分支进行分析，这叫做回 溯操作。 在广度优先搜索中，同时处理一组部分解决的问题，通过对每一个部分解决 的问题的计算分析，获得新的一组部分解决的问题。如果遇到多个分支时，每个 部分解决的问题对每个分支创建一个拷贝放入问题组中。最后，问题集合就包含 所有合法匹配。 深度优先搜索仅仅需要正比于问题规模的存储空间，而广度优先搜索则可能 需要指数级的存储空间，但它首先发现最简单的匹配。两种搜索方法都需要指数 级的时间复杂度，如果需要更高的效率，就需要对搜索进行一些限制。 无方向性的分析方法 无方向性的分析方法要求待分析的串必须在分析前全部已经在缓冲区里， 第1 5 页 生里型兰塾查查兰堡主堡兰 墅三兰茎笙垦苎坌塑查鎏 可以以任意的顺序来访问待分析的串。这种分析方法不受串的顺序的约束，相 比于有方向性的分析方法，它可以在分析时能够得到更多的信息。 这种分析方法有两种：自顶向下的u n g e r 算法【1 6 】和自底 f c o c k e y 0 u n g e r k a s a m i 算法( 简称c y k 算法) 1 7 】。 表3 2 上下文无关文法的分析方法分类 i 自顶向下自底向上 无方向性的分析方法 u n g e rp a r s e r c y k p a b e r 有方预测，匹配自动机移进，规约自动机 向性不确定递归下降法限制性的广度优先搜索( 如 的分 e a r l e ) p a r s e r ) 析方 l l ( nl r ( k ) 法 确定( 线性的)l a l r ( 1 ) s l r ( i ) 3 3 2 常用的一般性上下文无关文法的分析方法 所谓般性上下文无关文法的分析方法，就是对分析的文法没有特殊的限 制，能够分析所有的上下文无关文法定义的语言。一般性的上下文无关文法常用 的分析方法主要有：u n g e r 方法、c y k 方法和e 刚e y 方法f 1 8 】，递归下降的方法【1 9 】。 1 1 u n g e r 方法 u n g e r 方法是自顶向下的分析方法。对于一个属于文法定义的语言的输入 串，它必须可以从开始符号导出，这等价于可以从开始符号的规则定义右式导 出。对于起始规则s t a r t a 1a 2 a 。，这就是说，a i 导出串的第一部分， a 2 导出串的第二部分，如此类推。 u n g e r 方法试图发现一个输入串的划分，来满足这种要求，这是一种递归 的问题，如果一个非终结符a ；导出串的一部分，那么必然存在该部分子串的 划分满足a i 的规则定义右式，然后依据a i 规则定义右式的子规则继续对该部 分子串进行戈0 分。这样一直向下划分，直到只剩下终结符，对于终结符直接与 输入的串进行比较即可。 对于上下文无关文法，u n g e r 方法最终能找到所有的合法匹配。 例如，对于文法： s a b a a la 2 b c 第1 6 页 ! 里型堂垫查奎堂堕主丝奎 墅三皇型墨茎坌塑互查 如图3 4 ，对于字符串a b c d ”，分析的起始状态a 所示t 根据规则s a b 进行以下的三种划分b ，c ，d ，对于情况2 ，根据规则a a l a 2 又可以继 续划分为两种子情况e ，f o 这样一直向下划分，最终进行非终结符与字符的比 较。 b e a c 图3 4 u n g e r 分析过程 f d 2 lc y k 方法 c y k 方法是一种自底向上的分析方法，c y k 方法能够处t 里c h o m s k y n o r m a l f o r m ( c n f ) 形式的上下文无关文法。c n f 形式的文法要求每一个产生式是下列两 种情况之一： a b ca a 其中a ，b 和c 是非终结符，a 是终结符。 通常形式的上下文无关文法都可以等价的改写为c n f 形式，因而c y k 方 法可以分析所有的上下文无关文法0 2 。 对于一个c n f 形式的上下文无关文法g ；( v t ，v n ，s ，p ) ，和串x ，c k y 算法决定g 能否到处x o 设x 长度为n ，x = x 1 x 2 x n 每个x i v t ( 1 i n ) 。令n i l ，j 】( 1 i j r 1 ) 代表n 的一个子集，对每一个n i ，j 1 中的元素 a 可以导出子串x l x i + l ，x j 。通过下面两个关系来