（计算机应用技术专业论文）基于确定状态机的abnf通用解析方法.pdf

中国科学技术大学硕士学位论文 摘要 扩展巴科斯范式( a b n f ，a u g m e n t e d b n f ) 是i n t e r n e t 工程任务组( i e t f ， i n t e r n e te n g i n e e r i n gt a s kf o r c e ) 在r f c 2 2 3 4 中给出的一个字符串模式匹配 的文法定义，它被广泛应用于各种网络协议的消息编码。i e t f 组织使用a b n f 定 义了多个协议的报文格式，例如会话初始协议、超文本传输协议等。要实现这些 基于a b n f 规则的协议栈，就涉及到如何对文本格式的协议报文进行解析。目前， 这类协议报文的解析都是基于专用方式，对于每个具体协议的一套a b n t 规则 集合，都需要自主地开发其解析模块，这也使得系统缺乏通用性。针对这些问题， 本文采用基于确定状态机的解析模型，来提供一种有效的通用解决方案。 主要工作有以下几个方面： 1 定义并分析了a b n f 范式、规则树及确定状态机之间的关系。 2 以a b n f 范式为基础，对规则树和确定状态机之间的关系进行建模，设 计了基于确定状态机的通用解析模型。 3 在v c 开发环境下实现了上述模型的核心算法，可以解析a b n f 规范下 的各种协议报文，例如s i p m e s s a g e ，h t t p 请求等。 4 分析了基于确定状态机的a b n f 解析模型的f 确性和通用性，论证了相 关核心算法的高效性。 基于确定状态机的a b n f 通用解析模型，不仅能实现对文本编码类协议报 文的高速解析，而且也适用于解码器的固化，文章最后提出了通用解析模型的固 化设计方案。 关键词：扩展巴克斯范式，规则树，会话初始协议，确定有穷状态机，定位集。 第2 页( 共6 6 页) 中国科学技术大学硕士学位论文 a b s t r a c t 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 sak i n do ff o r m a ts y n t a xf o rt e x t - b a s e d s t r i n gd e f i n e di nr f c2 2 3 4b yi e t f , i ti su s e dw i d e l yt oe n c o d ea l lk i n d so fn e t w o r k p r o t o c o lm e s s a g e ，i e t fh a sd e f i n e daf e w o fp r o t o c o l sm e s s a g ef o r m a t ，f o ri n s t a n c e ， s i p , h t t pe t c i no r d e rt oi m p l e m e n tt h e s ep r o t o c o ls t a c k sb a s e do na b n f , i ti s n e c e s s a r yt ot e a ro u th o w t op a r s et h e s et e x t b a s e dp r o t o c o lm e s s a g e s h o w e v e r ，m o s t o fi m p l e m e n t so ft h e s ep r o t o c o ls t a c k sa r eb a s e do ns p e c i a lp a t t e r nc u r r e n t l y , w h i c h m a k e sn a t u r a l i z a t i o no fp r o t o c o ls t a c k sb e c o m ev e r yd i f f i c u l t f o rt h e s ep r o b l e m s ，、。e a d o p tan e wp a r s i n gm o d e ln a m e dd f a m ( d e t e r m i n i s t i cf i n i t ea u t o m a t i o n ) t oo f f e r a ne f f e c t j v ea n du n i v e r s a 】s c h e m e t h em a i nw o r k sa sf o f l o w 1 d e f i n e dr e l a t i o n s h i p sb e t w e e na b n f ，r u l et r e ea n dd f a m 2 b a s e do na b n f ，w ec r e a t e dam o d e lo fr o l et r e e sa n dd f a m ，d e s i g n e d s p e c i a lp a r s i n gm o d e lo fp r o t o c o lm e s s a g eb a s e d d f a m 3 i nv ci d e ，w ei m p l e m e n t e dt h ec o r ea l g o r i t h mo f t h i sm o d e l ，w h i c hc a r lp a r s e a l lk i n d so fp r o t o c o lm e s s a g e sa c c o r d i n ga b n fs t a n d a r d i z a t i o ns u c ha ss i p m e s s a g e a n dh t t p - r e q u e s te t c 4 w ea n a l y s i z et h ec o r r e c t n e s sa n dg e n e r a l i z a t i o no ft h i sp a r s i n gm o d e l a tt h e s a m et i m e ，i t se f f i c i e n c yi sd e m o n s t r a t e d t h em o d e lb a s e d d f a mn o to n l yc a j lp a r s ep r o t o c o lt e x tm e s s a g ei nh i g hs p e e d ， b u ta l s oc a nb ep l u g e di nh a r d w a r ee a s i l y s o l i d i f y i n gd e s i g ns c h e m eo ft h i ss p e c i a l p a r s i n gm o d e li sp u tf o r w a r da tt h ee n do f t h i sa r t i c l e k e y w o r d ：a b n f , r u l et r e e ，s i p , d e t e r n i n i s t i cf i n n i t ea u t o m a t i o n ，l o c c a f i o n s e t 第3 页( 共6 6 页) 中国科学挂术大学硕士学位论文 第一章引言 1 1 选题背景及意义 扩展巴科斯范式是i n t e r n e t 工程任务组在r f c 2 2 3 4 中给出的一个字符串 模式匹配的文法定义。a b n f 是在原有巴克斯范式【2 】【3 】( b n f ) 基础上的扩展，它 同标准巴克斯范式的区别在于：命名规则、循环、选择、次序独立和值域。i e t f 组织使用a b n f 定义了多个协议中的报文格式，例如会话初始协议( s i p ，s e s s i o n i n i t i a t i o np r o t o c 0 1 ) 、超文本传输协议( h t t p ，h y p e r t e x tt r a n s f e r p r o t o c 0 1 ) 、邮件传输协议( m a i lt r a n s f e rp r o t o c 0 1 ) 等。要实现这些基于 a b n f 规则的文本编码类协议栈，就涉及到如何对文本格式的协议报文进行解析； 具体来说，解析工作通常包括：按照a b n f 规则对报文的正确性进行匹配验证， 对报文进行分解，提取其中的关键字段信息等。如何提供一种正确的、通用的和 高效的解析方法，是实现此类协议栈的核心和关键。 1 。2 当前的研究现状 与传统的基于二进制格式的协议报文相比较，文本编码类协议报文具有其自 身的特点，处理起来更加复杂。对于采用文本编码方式的协议报文，由于在a b n f 规范中引入了如循环、选择等规则，这使得报文格式更富有多变性，特别是其中 关键信息字段的起始位置和有效长度往往不是定值，因此，无法像基于二进制格 式的协议报文解析那样进行简单的定位和提取处理，通常需要进行更为复杂的字 符串查找与匹配操作。正因为如此，当对系统的性能要求很高时，对文本格式报 文的解析速度就提出了更高的要求。以基于s i p 协议的软交换系统的实现为例， 软交换系统面对的是百万量级的连接，据实际数据显示，s i p 协议栈的实现大约 4 0 的c p u 时间用于s i p 消息的解析工作，是目前协议栈实现的主要瓶颈之一。 对于协议栈的解析，目前常用的方法有两种：专用解析和通用解析。 所谓专用解析，是指解析过程只针对具体协议的具体报文格式。比如，一个 s i p 消息通常由多行组成，每行之间用c r l f ( 回车换行) 分隔。在解析时，程 第6 页( 共6 6 页1 中国科学技术大学硕士学位论文 序根据c r l f 把s i p 消息分成多个独立的行，对每一行再按照特定的分隔符解析 其中特定的域值( 比如：对于s i p 协议的f r o m ：s i p ：a l i c e ：1 2 3 u s t c e d u 头域来说， “ ”前是用户信息，“ ”后是主机名，它们都是关键域值信息) 。这种专用方 法的优点是效率高；但它对于每个具体协议的一套a b n f 规则集合，都需要自 主地重新开发其解析模块，缺乏通用性，解析的正确性也得不到保障，主要依赖 于开发人员对a b n f 规则理解的程度。 所谓通用解析，是指在具体实现的过程中，报文解析的语法逻辑严格遵循 a b n f 规范。因此，这种解析方法的正确性能得到保障，并且协议栈的通用性好； 但通常的实现方法中由于存在回溯，影响解析效率。 因此，我们的目标是设计一种高效的、不带回溯的通用解析方法，本文提出 一种基于确定状态机( d f a m ) 的通用解析模型，这是一种高效的、不带回溯的 通用解析方法，它可以解析所有符合a b n f 规范的网络协议报文。 1 3 研究目标及其方案 本文在分析规则树和确定有穷自动机之间逻辑关系的基础上，研究一种通用 的、高效的报文解析方法基于确定状态机的a b n f 通用解析方法。这种方 法独立于具体的协议，能够解析所有基于a b n f 编码的协议消息；同时，能够 通过配置协议消息的a b n f 规则集合，准确快速地解析相应的协议消息。 研究方案： 1 ) 研究正规式与有穷自动机的等价性、3 型文法与有穷自动机的等价性以 及l r ( k ) 分析方法与确定有穷自动机的等价性，论证有穷自动机在词法和语法分 析的过程中的重要作用。 2 ) 分析规则树和确定有穷自动机之间的逻辑关系。 3 ) 根据规则树和确定有穷自动之间的逻辑关系，提出基于确定状态机的 a b n f 通用解析方法的模型设计，实现模型的核心算法。 4 ) 结合s i p 、h t t p 协议对核一t l , 算法的正确性、通用性进行验证，并分析其 解析效率。 5 ) 为进一步加快解析速度、提高解析效率，文章最后设计了这种通用解析 第7 页( 共6 6 页) 中国科学技术太学硕士学位论文 序根据c r l f 把s i p 消息分成多个独立的行，对每一行再按照特定的分隔符解析 其中特定的域值( 比如：对于s i p 协议的f r o m ：s i p ：a l i c e ：1 2 3 u s t ee d u 头域来说， “ ”前是用户信息，“ ”后是主机名，它们都是关键域值信息) 。这种专用方 法的优点是效率高；但它对于每个具体协议的一套a b n f 规则集合，都需要自 主地重新开发其解析模块，缺乏通用性，解析的正确性也得不到保障，主要依赖 于开发人员对a b n f 规则理解的程度。 所谓通用解析，是指在具体实现的过程中，报文解析的语法逻辑严格遵循 a b n t 规范。因此，这种解析方法的正确性能得到保障，并且协议栈的通用性好： 但通常的实现方法中由于存在回溯，影响解析效率。 凼此，我们的目标是设计一种商效的、不带回溯的通用解析方法，本文提出 一种基于确定状态机( d f a m ) 的通用解析模型，这是一种商效的、不带同溯的 通用解析方法，它可以解析所有符合a b n f 规范的网络协议报文。 1 3 研究目标及其方案 本文在分析规则树和确定有穷自动机之间逻辑关系的基础上，研究种通用 的、高效的报文解析方法基于确定状态机的a b n f 通用解析方法。这种方 法独立于具体的协议，能够解析所有基于a b n f 编码的协议消息；同时，能够 通过配置协议消息的a b n f 规则集合，准确快速地解析相应的协议消息。 研究方案： 1 ) 研究正规式与有穷自动机的等价性、3 型文法与有穷自动机的等价性以 及l r ( k ) 分析方法与确定有穷自动机的等价性，论证有穷自动机在词法和语法分 析的过程中的重要作用。 2 ) 分析规则树和确定有穷自动机之间的逻辑关系。 3 ) 根据规则树和确定有穷自动之间的逻辑关系，提出基于确定状态机的 a n f 通用解析方法的模型设计，实现模型的核心算法。 4 ) 结合s i p 、h t t p 协议对核心算法的正确性、通用性进行验证，并分析其 解析效率。 5 ) 为进一步加快解析速度、提高解析效率，文章最后设计了这种通用解析 5 ) 为进步加快解析速度、提高解析效率，文章最后设计了这种通用解析 第7 页【共6 6 更) 中国科学技术大学硕士学位论文 模型的固化方案。 1 4 本文章节安排 全文共分六章，组织如下： 第一章引言，介绍选题背景及其意义，提出研究目标和方案。 第二章协议报文解析基础，概述扩展巴克斯范式a b n f ，介绍s i p 协议的 基础知识及应用前景。 第三章上下文无关文法及其分析方法，介绍常见的上下文无关文法：自上 而下分析和自下而上分析；通过研究正规式与有穷自动机的等价性、3 型文法与 有穷自动机的等价性以及l r ( k ) 分析方法与确定有穷自动机的等价性，说明了有 穷自动机在词法和语法分析的过程中的重要作用。 第四章基于确定状态机的a b n f 通用解析模型。详细阐述了通用解析方法 的模型设计，研究模型核心算法的实现。 第五章解析模型的核心算法分析，结合会话初始协议和超文本传输协议 等，验证了基于确定状态机的通用解析模型的正确性和通用性，并给出了测试结 果，分析了核心算法的效率，提出了这种通用解析模型的固化设计方案。 第六章结束语，对本文工作进行总结和回顾，提出了今后的研究方向。 1 5 本章小结 本章介绍了论文的选题背景及研究意义，在分析当前基于a b n f 的文本类 协议报文解析常见方法专用解析和通用解析的基础上，分析了这两种解拆方 法的优劣，提出了本文的研究目标“基于确定状态机的a b n f 通用解析方 法”，并且给出了具体的研究方案。 第8 页( 共6 6 页) 中国科学技术大学预士学位论文 第二章协议报文解析基础 本章将简要介绍协议报文解析方面的基础知识。包括扩展巴克斯范式a b n f 及会话初始协议s i p 方面的相关知识。 2 1 扩展巴克斯范式a b n f 简介 互联网技术规范经常需要定义一种格式化语法，并能自由地使用任何有用的 符号2 1 。多年来，巴克斯范式( b n f ) 的一个修订版，即扩展巴克斯范式，已经 在互联网许多规范中流行。标准巴克斯范式与扩展巴克斯范式的区别包括：命名 规则，循环，选择以及值域等。 扩展巴克斯范式的语法最初在r f c7 3 3 嘲中说明。s r ti n t e r n a t i o n a l 的k e n l h a r r e n s t i e n 负责将巴克斯范式重新编码成扩展巴克斯范式，这样使得其描 述更简短，并且更容易理解。 a b n f 范式的左部是一个非终结符，非终结符用尖括号括起。右部是由非终 结符和终结符组成的一个任意符号串。具有相同左部的产生规则可以共用一个左 部，各右部之间以竖直线“l ”分开。例如定义“标识符”的一组a b n f 公式为： ：= i f ：= a l b l c i i x l y l z ：= 0 1 1 1 2 1 3 1 1 8 1 9 a b n f 范式以递归方式描述语言中的各种成分，凡是遵循这种规则的协议 报文或程序，就可以保证它在语法和语义上的正确性。a b n f 规则以其科学、简 洁而明了的风格被广泛接受，成为描述各种程序设计语言的最常用的工具。 2 1 1a b n f 规则定义 1 a b n f 规则命名 每个a b n f 主规则及相应的子规则都有一个规则名，规则名是一个符号序 列，它以字母打头，后跟一个字母、数字或下划线的组合。a b n f 规则的规则名 大小写不敏感，例如规则名： $ 口 代表同一个规则。 2 a b n f 规则格式 第9 页( 共6 6 页) 中国科学技术大学硕士学位论文 一个规则是由下面的序列定义的：n a m e = e l e m e n t sc r l f 其中： 指规则名， 指- - 个或多个规则名或终结符， 是行结束标志，回车符后紧跟换行符。左式规则名和右式规则定义由一 个等号分隔开。元素由一个或多个规则名( 和或) 值的定义序列构成，这些规 则名( 和或) 值依照巴克斯范式的各种操作符( 例如连接、选择、循环等) 结 合在一起。 2 1 2a b n f 规则操作符 a b n f 规则操作符有以下九种形式，它们定义了a b n f 规则之间的逻辑关 系，即规则之间的语法和语义关系。 1 连接：规则1 规则2 通过列出一系列规则名，一条规则可用于定义一个简单有序的值串，即一连 串邻接的字符。例如，对于以下三条规则： 规则1 = x 6 1：a 规则2 = x 6 2 ；b 规则3 = f o ob a r f o o 那么，规则3 与小写字符串”a b a ”匹配。 线性空白字符：连接操作处于a b n f 范式解析模型的核心。一串相邻的字 符( 值) 根据扩展巴克斯范式定义的规则进行解析。 注意：a b n f 范式没有提供线性空白字符的隐式规范。任何希望允许在分界 符或字符串两边出现线性空白字符的语法必须显式说明。对于那些被更高层规则 多次使用的“核心”规则，提供这些空白字符常常是有用的。“核心”规则可以 编入一个词法分析器中，或者简单地作为主规则集的一部分。 2 选择：规则l ，规则2 由斜杠( “”) 分隔的元素表示选择关系。因此，f o o b a r 将接受 或者 。但要注意：一个包含字母字符的引用串，是用于说明选择字符的特殊形 式，它被解释为一个非终结符，该非终结符用所包含的字符，以指定的顺序但可 第1 0 页t 共6 6 页) 中国科学技术大学硕士学位论文 以是任意大小写的混合方式，来描述组合串集。 3 增式选择：规则1 = 1 规则2 在段落中指定一列选择有时会很方便。即，通过稍后的规则定义增加选择集， 一个初始规则可能匹配个或多个选择。这对于那些源于同一父规则集而其它方 面独立的规范尤其有用，如常出现于参数列表中。使用如下结构，a b n f 范式允 许如下方式的增式定义： o l d r u e - a d d i f 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 i r 2 r u l e s e t = a l t 3m l e s e t = a l l 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 l t 4 a l t 5 的意义相同 4 值域选择：c # # 删 通过使用连字符( “一”) 表明可选值域的方式，可以紧缩说明可选数值域。 因此：d t g i t = x 3 0 3 9 等同于d i g i t = 0 ，1 2 ”3 ，4 ，”5 ”，6 7 8 9 ”。 连接的数值和数值域不能在同一串中说明。一个数值可以用点号连接或使用 连字符说明一个值域。因此，为了在行序列结束之间说明个可打印的字符，说 明格式如下： c h a r - l i n e = x 0 d0 a x 2 0 7 1 3 x 0 d o a s 序列组：( 规则1 规则2 ) 序列组用小括号来表示，小括号里的元素看作一个单一的元素，因此，e l e m ( f o o ，b a r ) b l a ti n n ( e l e mf o ob l a t ) 或者( e l e mb a rb l m ) ；e l e mf o o b a rn a t 匹配( e l e mf o o ) 。r ( b a r b l a t ) 。 注意：当选择操作由多个规则名或文字组成时，强烈建议使用分组符( 括号) ， 而不要依赖于“空”间隔。因此推荐用盍u 下形式代替上述形式：f e l e m f o o ) ( b a r b l a t ) 。 6 不定循环：* 规则 操作符“”表示重复。其完整形式为： 4 e l e m e n t ，此处 和 是 可选的十进制数，表示元素出现至少 次，至多 次。默认值是0 和无穷。 因此* 允许e l e m e n t 出现任意多次：1 + 要求至少出现1 次； 3 * 3 只允许出现3 次；l * 2 允许出现1 次或2 次。 第n 面( 共“页) 中国科学技术大学硕士学位论文 7 指定循环：1 1 规则 如下形式的规则： e l e m e n t ，等同于 * c l c m e n t ，即， 正好 出现n 次；而2 d i g i t 表示一个2 位数，而3 a l p h a 表示一个3 字母的字符串。 8 可选序列：【规则】 方括弧表示一个可选的元素序列，它表示方括号中的元素可以出现0 次或者 1 次。例如 f o o b a r 等同于0 + 1 ( f o o b a r ) 。 9 注释 为了使读者准确理解文法的含义，a b n f 规范中使用分号( “；”) 作为注释， 分号开始一行直到行末被看成注释，它只起解释说明的作用，它对文法的语法和 语义没有任何影响。例如： d i g i t = x 3 0 - 3 9 ：数字o 到9 。 1 0 操作符优先级 上述a b n f 规则操作符具有以下优先级关系，从高到低排序为：字符串一 注释一 值域一 循环一 分组一 连接 选择。 2 1 3a b n f 核心规则 a b n f 范式的核心规则提供了一组规则的定义格式和方法，这种规则定义和 编码适用于某些互联网规范的核心词法分析器。 某些基本规则使用大写：如s p ，h t a b ，c r l f ，d i g i t ，a l p h a 等。 除n u l 以外的任何7 位u s a s c i i 字符。 回车：c r = x 0 d 。 互联网标准格式的换行：c r l f = c r l f 。 数字0 - 9 ：d i g i t _ x 3 0 - 3 9 ”( 双引号) ：d q u o t e = x 2 2 水平制表符：h t a b = x 0 9 换行：l f = x o a 线性空白字符( 过去的换行) ：l w s p = + ( w s p c r l fw s p ) 第1 2 页( 共6 6 页) 中国科学技术大学硕士学位论文 8 位数据：o c t e t = x 0 0 一f f 空格符：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 2 会话初始协议s i p 简介 2 2 1s i p 概述 会话初始协议( s i p ，s e s s i o ni n i t i a t i o np r o t o c 0 1 ) 是个基于文本的 应用层协议，用来在网络的不同实体之间建立、修改和终止多媒体会话8 】【9 】。 它提供了在远程实体之间建立通信的一个框架，包括名字地址服务、消息路由、 安全服务等等。该协议具有简单、灵活及扩展性好的特点，可用来架构基于s i p 的各种分布式系统，如实时股票价格跟踪、医疗事件监视以及车辆追踪等。此外， s i p 协议提供良好的q o s 支持，对于要在i p 网络上实现v o l p ( v o i c eo v e r i p ) 和 多媒体通信的n g n ( 下一代网络) 来讲，s i p 在应用上有独特的优势，将成为下 一代网络v o 口的重要解决方案。 s i p 主要提供了与建立和终止会话相关的五个方面的功能，它们是： 1 ) 用户定位：用于通信的终端系统的决定； 2 ) 用户可用性：被呼叫方参与通信的意愿的决定； 3 ) 用户能力：使用的媒体和媒体参数的决定； 4 ) 会话建立：“振铃”，呼口q 和被呼q 方会话参数的建立； 5 ) 会话管理：包括会话转移和终结会话，修改会话参数，以及调用业务等。 s i p 在实现上采用了三层结构，第一层是最底层，这一层是语法和编码编码 规范使用扩展b a c k u s - - n a y r 形式语法( a b n f ) 。第二层是传输层，它定义了网 络上一个客户机如何发送请求和接收响应，以及一个服务器如何接收请求和发送 响应。第三层是事务层，事务是s i p 的基本元素，一个事务是由客户机事务发送 给服务器事务的请求，以及对应此请求的从服务器事务发送给客户机事务的所有 响应组成的。事务层处理应用层重传，匹配响应到请求，以及应用层超时。 笫1 3 页( 共6 6 页) 中国科学技术大学硕士学位论文 作为一种新兴的i p 电话信令协议，s i p 协议己经被选为3 g ( 下一代的无线 通信核心网络) 的核心信令协议。s i p 可为用户提供实时的音频、视频甚至是游 戏数据，市场应用非常广泛。 2 2 2 基于a b n f 的s i p 报文格式 1 s i p 协议的a b n f 范式 s i p 协议是一个基于文本的协议，采用i s 0 1 0 6 4 6 以u t f 8 编码【7 1 ，l e f t 组 织定义了s i p 报文消息的a b n f 规则集。 基本规则是用大写字母表示的，比如s p ，l w s ，h t a b ，c r l f ，d i g i t ， a l p h a 等等。尖括号定义了规则的名字，使用方括号在语法上表示可选。 1 1u s - a s c i i 码字符集 a l p h a n u m = a l p h a d i g i t 2 ) 冒号为了把头域名和值分开，就需要使用冒号，根据上面的规则，允 许在冒号之前有空白，但是不允许有行分隔符，并且允许在冒号之后有空白，或 者行分隔符。h c o l o n 有如下定义：h c o l o n = + ( s p h t a b ) = ”s w s 。 3 1 注释 在s i p 头域中可以使用注释，注释放在一个圆括号中。只有在头域的定义允 许“c o m m e n t ”作为它们的头域值的一部分时，才可以使用注释；如果头域的定 义不允许使用注释，那么圆括号会被看作头域值的一部分。 2 s i p 消息结构 s i p 消息只有两种类型：请求消息和响应消息。两类消息都使用r f c 2 8 2 2 4 】 中定义的基本消息格式。每条s i p 消息由以下三部分组成，如图2 1 所示。 1 ) 消息起始行 每个s i p 消启、都由一个起始行( s t a r t 一1 i n e ) 开始。起始行传达消息类型与 协议版本，起始行可以是一请求行或状态行。 2 ) 消息头域 s i p 消息头域的格式，遵循r f c 2 8 2 2 4 1 中定义的通用形式。消息头域由一 个域名加上冒号( ”：“) 和域值三部分组成。 第1 4 甄( 共6 6 页) 中国科学技术大学硕士学位论文 3 ) 消息体：s i p 消息体的内容可独立于s i p 而存在，只要会话需要，任何类 型的会话方式都可以内嵌到消息体中，如音频、视频数据等。s i p 的消息体部分 采用s d p 协议进行描述【1 0 】。 起始行( s t a r t - l i n e ) 头域 + ( m e s s a g e h e a d e r ) c r l f 消息体( b o d y ) s t a r t l i n e = r e q u e s t - l i n e s l a t u s l i n e 必选。 一个或多个头域，必选。 空行指示头域的结束，必选。 消息体本身独立于s i p 协议 可以包含任何内容，如文本 图像，声音数据等。可选。 图2 1 基于a b n f 的s i p 报文格式 2 2 3s i p 报文常用解析方法及不足 常见的s i p 协议栈i i n 】 1 3 l 的实现，都是基于专用解析方式。与其它协议的 专用方案一样，它解析效率很高；但对于s i p 协议的一套a b n f 规则集合，需要 自主地重新开发其解析模块，这也使得系统缺乏通用性。 在第四章，我们提出的基于确定状态机的通用解析模型，将在s i p 协议的基 础上，详细阐述通用解析的模型设计、核心算法及其实现。 2 3 本章小结 本章详细介绍了扩展巴克斯范式a b n f 规范，主要说明了它的九种规则操 作符及其核心规则。在此基础上，引入了符合a b n f 编码规范的s i p 协议，介绍 了s i p 协议消息结构、报文编码及其应用前景，引出本文研究的研究内容“基 于确定状态机的a b n f 通用解析方法”。 第1 5 页( 共6 6 页) 中国科学技术大学硕士学位论文 第三章上下文无关文法及其分析方法 自从著名语言学家乔姆斯基( n o a mc h o m s k y ) 于1 9 5 6 年建立了形式语言的 描述以来，形式语言理论发展得很快。这种理论已成为计算机科学的理论基础 “l 。 乔姆斯基把文法分为四种类型，即0 型、l 型、2 型和3 型，0 型最强，3 型 最弱。它们的差别仅在于对产生式旅加不同的限制。如果对0 型文法的产生式加 以限制，可以得到另外的三种文法。 3 1 上下文无关文法 上下文无关文法，是指它定义的语法范畴( 或语法单位) 完全独立于这种范 畴可能出现的环境，即在处理这种文法的语言时，不必考虑它所处的上下文环境。 上下文无关文法通常采用标准巴科斯范式b n f 来表达。 一个上下文无关文法g 可定义为四元组：o = ( v t ，v n ，s ，p ) v ，为终结符非空有穷集合； v n 为非终结符号( 或语法实体，或变量) 非空有穷集合，且v t a v n = 中； s 是一个非终结符，称为文法的起始符号，至少要在一条产生式中作为左部 出现。 p 为产生式( 也称规则) 的非空有穷集合，且每个产生式型如： 一p 或旺：；p ， 其中a 、p ( v tl j v n ) ，a 称为规则的左部，b 称为规则的右部。这样的文 法g 称为0 型文法。 由上下文无关文法的定义可知，b n f 可以很好的表示上下文无关文法的产 生式规则。 3 2 上下文无关文法的分析方法 语法分析是编译程序的核心部分。语法分析的作用是：识别由词法分析给出 的单词符号序列是否是给定文法的正确句子。目前语法分析常用豹方法有自上面 第1 6 页( 共6 6 页) 中国科学技术大学硕士学位论文 下( 自顶向下) 分析和自下而上( 自底向上) 分析两大类。而自下而上分析又可 分为算符优先分析和l r ( k ) 分析，这些分析方法各有优缺点，是当今编译程序构 造的实用方法。 3 2 1 自上而下分析 自上而下分析法也称面向目标的分析方法，对任何输入串，试图用一切可能 的方法，从文法的开始符号( 根结点) 出发，自上而下，自左至右地为输入串建 立一棵分析树；或者说，为输入串寻找一个最左推导。从本质上说，这种分析过 程是种试探过程，即反复使用不同的产生式，企图推导出与输入的单词串完全 匹配的句子，如果输入串是给定文法的句子，则必能推出，反之必然出错。 自上而下的分析方法又可分为确定的和不确定的两种，确定的分析方法对文 法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分 析器，因而仍是目前常用的方法之一。不确定的方法是带回溯的分析方法，这种 方法实际上采用了一种穷尽一切可能选择的试探方法，当一个文法含有左递归 时，最好的办法是消除左递归，找出克服回溯的充分必要条件，从而构造递归下 降分析器。 1 确定的自上而下分析 确定的自上而下分析方法，首先要解决的的是：从文法的开始符号出发，对 于给定的输入符号串，如何根据当前的输入符号唯一地确定选用哪个产生式替换 相应非终结符往下推导，或构造一棵相应的语法树；若能够推导出给定的输入符 号串，或者能构造出一棵语法树，语法树叶子结点以从左向右的顺序连接恰好为 给定的输入符号串，那么，所给的输入符号串就是该文法的句子。这样的文法具 有如下两个特点： 1 ) 每个产生式的右部都由终结符号开始。 2 ) 如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。 显然，这样的文法在推导过程中，完全可以根据当前的输入符号决定选择哪 个产生式往下推导，因此分析过程是唯一确定的。 第1 7 页( 共6 6 页) 中国科学技术大学硕士学位论文 2 不确定的自上而下分析 这种分析方法适用的文法特点是： 1 ) 产生式的右部不全是由终结符开始。 2 ) 如果两个产生式左部相同，其右部是由不同的终结符或非终结符开始。 3 ) 文法中无e ( 空) 产生式。 不确定的分析方法实质上是一种含有左递归、带回溯的分析方法。该方法采 用穷尽一切可能选择的试探方法。当用一个候选式的右部去匹配输入串失败时， 一方面要注销该产生式产生的子树，修改输入指针，使其指向进入该产生式时的 初始位置，另一方面，要使己完成的语法分析工作推倒重来。此外，一个文法常 采用递归定义，当分析失败时，很难确定输入串中出错的确切位置。因此，为了 实现不带回溯的自上而下分析，在消除左递归的同时，任何一个非终结符的多个 候选式的首终结符集，必须两两不相交。 3 2 2 算符优先分析 算符优先分析是一种简单直观、广为使用的自下而上的分析方法，它特别有 利于分析表达式，而且很容易手工构造出高效的移进归约分析器。 算符优先分析的基本思想是：仿效算术表达式的计算过程而设计的一种语法 分析方法，该方法的关键在于确定算符( 终结符) 之间的优先关系和结合性，然 后利用这种关系，比较相邻运算符之间的优先关系，以确定可归约串并进行归约。 这种分析方法只规定算符之间的优先关系，也就是只考虑终结符之间的优先 关系，不考虑非终结符之间的优先关系。在归约过程中，只要找到可归约串就归 约，并不考虑归约到那个非终结符，算符优先分析的可归约串不一定是规范句型 的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串，是当前符 号栈中的符号和剩余的输入符号构成句型的最左短语。 3 2 3 l r ( k ) 分析 l r ( k ) 分析是种有效的自下而上的语法分析技术，它能分析一大类上下文 无关文法。其中，l 表示从左向右扫描输入串；r 是指构造最右推导的逆；k 指 第1 8 页( 共6 6 页) 中国科学技术大学硕士学位论文 在决定分析动作时向前看的符号个数，默认时k 为1 。l r ( k ) 分析器根据分析栈 的内容以及向前看k 个输入串的符号来决定分析器的动作，它由3 个部分组成： 1 ) 总控程序。也可以称为驱动程序，对所有的l r 分析器总控程序都是相同 的。 2 ) 分析表或分析函数。不同的文法分析表是不同的，同一个文法如果采用 的l r 分析器不同，分析表也将不同；分析表由动作表和状态转换表两个部分组 成，它们都可用二维数组表示。 3 ) 分析栈。分析栈包括文法符号栈和相应的状态栈，它们均是先进后出栈。 常见的l r ( k ) 模型结构包括一个输入缓冲区，一个分析栈，一个驱动程序和 一张分析表，分析表由动作表和转移表组成。l r ( k ) 分析器具有下述优点： ( 1 ) 识别所有能用上下文无关文法表示的程序设计语言的结构： ( 2 ) 最广义的无回溯移进归约分析法，且能和其它移进一归约分析法一样高 效地实现； ( 3 ) 使用l r ( k ) 分析方法分析的文法类，是用预测分析方法的文法类的真超 集： ( 4 ) 及时地发现语法错误，并能准确地指出出错的具体位置。 l r ( k ) 分析器的主要缺点是手工构造一l r 分析器( l rp a r s e r ) 工作量太大， 通常必须借助于l r 分析器的生成器( a nl rp a r s eg e n e r a t e r ) 。 3 3 有穷自动机简介 有穷自动机( 又称有穷状态机) 是具有离散输入、输出信号系统的一种数学 模型。该系统可处于有穷个内部状态中的任何一个状态，系统的当前状态概括了 以前输入的信息，这些信息对于确定系统对后来输入信息的行为是必需的。例如， 电梯的控制机构是有穷状态系统的一个例子。该系统并不需要记录所有以前的服 务要求，而仅需要知道现在是在几楼、运行的方向及尚未服务的请求。由词法分 析器的自动生成器产生的词法分析器，就是有穷自动机的具体实现。有穷自动机 可分为两类：不确定有穷自动机( n f a n ，n o n d e t e r m i n i s t i cf i n i t ea u t o m a t i o n ) 第1 9 页( 共6 6 页) 中国科学技术大学硕士学位论文 和确定有穷自动机( d f a m ，d e t e r m i n i s t i cf i n i t ea u t o m a t i o n ) ，其区别在于：对 于某个输入符号，从一个状态转换到另一个状态时，仅存在一种状态转换或多种 状态转换。 1 不确定的有穷自动机：n f a n 一个不确定的有穷自动机卜a n 是一个五元式： n = ( s ，6 ，s o ，f ) ，其中： s 是一个有穷状态集；是一个有穷输入字母表； 6 是状态转换函数，是s 到s 子集的映射； s o 是唯一的初始状态；f 是有穷接收状态集。 一个含有m 个状态和n 个输入符号的n f a n 可表示为如下的一张状态转换 图：m 个状态结点，每个结点可以通过若干条有向边与其它结点连接，每条有向 边用中的一个符号作标记，整个转换图至少含有一个初始状态以及若干个( 可 以是0 个) 接收状态结点，某些接收状态结点也可以是初始状态结点。 对于中的任何一个符号串旺，若存在一条从某个初始状态结点到某个接收 状态结点的通路，并且对于这条通路，所有有向边的标记符号依次连接成的符号 串等于，则称为n f a n 所识别。倘若n f a n 的某些结点既是初始状态结点又 是接收状态结点，或者存在一条从某个初始状态结点到某个接收状态结点的通 路，那么空字e 也为n f a n 所接受。 一个不确定的有穷自动机b p f a n 所能识别的语言l ( n ) 记为： l ( n ) = xx ( u e ) + ，6 ( s o ，x ) = q ，q n f 中) 。 2 确定的有穷自动机：d f a m 一个确定的有穷自动机m 是一个五元式： m = ( s ，6 ，s o ，f ) ，其中： s 是一个有穷状态集； 是字母表，是一个有穷输入符号集； 6 是单值转换函数，是s x 到s 的映射； s o 是唯一的初始状态，且s o s ： f 是有穷接收状态集，且f s 。 第2 0 页f 共6 6 页1 中国科学技术大学硕士学位论文 例如，设一d f a m = ( a ，b ，c ，d ) ， o ，1 ，6 ，a ，( a ) ) 且6 定义为： 6 ( a ，0 ) = d6 ( a ，1 ) = b 6 ( b ，0 ) = c6 ( b ，1 ) = a 6 ( c ，0 ) = b6 ( c ，1 ) = d 6 ( d ，0 ) = a6 ( d ，1 ) = c 该d f a m 识别由偶数个0 和偶数个“1 ”组成的符号串，其状态转换图如 3 1 所示。图中标有开始箭头的结点是初始状态，双园圈的结点代表接收状态。 对于中的任何符号串n ，若存在一条从初始状态到接收状态的通路，且这 条通路上所有的有向边的标记组成的符号串等于n ，则称n 可为d f a m 所识别。 例如，1 1 0 1 叭输入符号串能被图3 1 识别，而输入符号串1 1 1 0 1 则不能被识别。 1 图3 1 d f a m 的转换图 0 3 4 有穷自动机在词法和语法分析中的作用 有穷自动机作为一种识别装置，它能准确地识别正规集，即识别正规文法所 定义的语言的集合。我们可以从以下三个方面来说明有穷自动机在词法和语法分 析中的重要作用。 1 有穷自动机和正规式的等价性 对于正规式和有穷自动机，有如下两个重要的结论： 1 ) 设上一个符号串集v c + 是正规的，当且仅当存在一个上的不确定的 有穷自动机n ，使得v = l ( n ) 。 2 ) 对