NMEA0183协议解析

第 30 卷 　第 2 期 2007 年 4 月 　　　 电 子 器 件 Chinese J ournal Of Elect ron Devices 　　 Vol . 30 　No. 2 Ap r . 2007 On Parsing of NMEA0183 Protocol Q I A N De2j un , Z H A N G Zhe , H U Chen ( N ational A S I C S ystem Engineering Center , S outheast Universit y , N anj ing 210096 , China) Abstract :The module , parsing NMEA0183 protocol , is a critical part in the guiding system software. The robusticity and efficiency of the module affect the performance of the guiding system directly. The deep analysis of the NMEA0183 protocol structure and the compilation technology characteristic leads to the method for parsing NMEA0183 protocol using the compilation technology. The whole process is composed of four phases : lexical analy2 sis , syntax analysis , semantic analysis and code generation. Now , the method has been used in the GPS guiding sys2 tem product. The corresponding module works stably in practice , and meets the request of the product level. Key words :embedded system ; NM EA0183 protocol parsing ; compilation technology ; GPS EEACC :6150M NMEA0183 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 解析 钱德俊 ,张　哲 ,胡　晨 (东南大学国家专用集成电路系统工程中心 ,南京 210096) 收稿日期 :2006205209 作者简介 :钱德俊 (19822 ) ,男 ,硕士研究生 ,研究方向为微电子与固体电子学、嵌入式系统设计 ,Elect ronseu @gmail. com ; 张 　哲 (19762) ,男 ,助教 ; 胡 　晨 (19672) ,男 ,东南大学电子工程系研究员. 摘 　要 :NM EA0183 协议解析模块是导航系统中重要的软件模块 ,该模块的健壮性和高效性直接关系到整个导航系统的性 能. 经过深入分析 NMEA0183 协议的结构和编译技术的特点 ,提出了一种利用编译技术解析 NMEA0183 协议的方法. 整个 解析过程分为四个阶段 ,分别对应于编译技术中的词法分析、语法分析、语义分析和代码生成. 目前该方法已经应用到 GPS 导 航产品中 ,实测表明解析模块稳定可靠 ,达到产品级要求. 关键词 :嵌入式系统 ; NM EA0183 协议解析 ;编译技术 ; GPS 中图分类号 :TP391 　　 文献标识码 :A 　　文章编号 :100529490( 2007) 0220698204 　　以导航技术为基础的各项应用在很大程度上提 高了社会生产力 ,方便了人们的工作生活 ,对国民经 济的发展有着重大意义. 目前 ,我国广泛使用的是美 国国防部开发的 GPS ( Global Positioning System) 卫星导航系统[1 ] . 该系统由空间部分、地面监控部分 和用户接收机三大部分组成[2 ] ,如图 1 所示. 其中 , GPS 模块通过空间部分提供的信息计算出自己当 前的 位 置 速 度 等 信 息 , 然 后 将 这 些 信 息 用 NM EA0183 协议封装[3 ] ,并通过串口发送给数据处 理中心 (通常为嵌入式系统) 进行处理. 接受并解析 由 GPS 模块发送的数据是数据处理中心的一项重 要任务 ,处理该任务的模块必须具备高可靠性 ( reli2 ability)和高有效性 (efficiency) . 如何正确高效地分析所接受的数据是每一个 NM EA0183 协议解析模块设计者所面临的问题. 本文将编译技术运用到NM EA0183 协议的解析中 ,实现了一种高效稳定的解析方法. 图 1 　GPS 组成 1 　可行性分析 1. 1 　NMEA0183 协议简介[ 4] NMEA0183 协议是由美国国家海洋电子协会开 发、维护并发布的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 ,用于航海远洋时使用的电子 仪器之间的通信. 目前大部分的 GPS 接受设备都遵 循这一标准. 该接口协议定义了在波特率为 4800 的 串口数据总线上传输的电器信号需求、数据传输协议 和时间 ,以及详细的句型格式. NMEA0183 协议的数 据以"句子"为单位进行发送 ,每个"句子"的结构如图 2 所示.假如数据域中的某个值无效 ,该值将被简单 的忽略 ,但对应的" ,"仍需发送. 图 2 　NM EA0183 协议消息结构 1 . 2 　编译技术简介[5 ] 编译技术研究如何将一种语言 (称作源语言)书 写的程序翻译成另一种语言 (称作目标语言)的等价 程序 ,它所执行的转换工作可以用图 3 来说明. 编译过程由词法分析、语法分析、语义分析和代 码生成几个阶段组成 ,如图 4 所示. 图 3 　转换工作框图 　　图 4 　编译过程 其中 ,词法分析是编译过程的第一个阶段 ,这个 阶段的任务是从左到右一个字符一个字符地读入源 程序 ,对读入的字符流进行扫描和分解 ,从而识别出 一个个单词. 语法分析是编译过程的第二个阶段 ,语法分析 的任务是在词法分析的基础上将单词序列分解成各 类语法短语 ,如"程序" 、"语句" 、"表达式"等. 语法分 析所依据的是语言的语法规则. 语义分析是审查源程序有无语义错误 ,为代码 收集类型信息. 代码生成则是在语法分析和语义分析阶段的基 础上生成最终的目标程序. 1 . 3 　可行性分析 对 NM EA0183 协议进行分析不难发现符合 NM EA0183 协议的 GPS 报文与高级语言程序之间 存在着如下共性 : ①它们都由字符构成 ,字符是构成 GPS 报文 和高级语言程序的最基本的单位. ②它们结构相似 ,都是由字符组成单词 ,再由 单词组成语句 ,最后由语句组成报文或程序. ③存在一种无二义的上下文无关文法对它们 的进行描述. 由于上述共性的存在 ,我们可以利用编译技术 对符合 NM EA0183 协议的 GPS 报文进行解析. 从 20 世纪 50 年代编译技术的出现至今 ,编译技术已 经发展得相当成熟[6 ] ,利用此技术对 NM EA0183 协议进行解析将可以有效地对解析性能进行控制. 2 　解析过程介绍 导航应用只关注 NM EA0183 协议中定义的 GGA、GLL 、GSA、GSV、RMC 和 V T G 这五条语 句. 为方便描述 ,我们以较为常用的 GGA 和 RMC 这两条语句为例介绍 NM EA0183 协议的解析 ,把 这两条语句组成的报文当成高级语言程序进行编 译. 描述的过程将使用编译技术中的术语. 2 . 1 　词法分析 词法分析由称为扫描程序的功能模块完成. 扫 描程序将 GPS 报文读作字符串并将其分为若干个 单词记号. 经过对图 2 中协议框架的分析 ,我们可以 定义以下四类单词 ,分别为 :保留字 (如" ＄" 、" GP G2 GA" 、" GPRMC" 、" ," 、" 3 " 、" < CR > < L F > ") 、地 址、值和校验和. 在此基础上 ,我们设计了一个识别 这些单词的确定性有穷自动机 DFA 如图 5 所示. 图 5 　单词识别 DFA 其中 ," [ ]"内为不可消耗的先行字符. 与此对 应的获取单词的代码框架如下 : read a char ch ; switch ( ch ) { 996第 2 期 钱德俊 ,张 　哲等 :NM EA0183 协议解析 case ’ < CR >’ : 　　read a char ch ; 　　if ( ch = =’ < L F >’ ) 　　　返回单词" < CR > < L F > " ; 　　else 　　　报错 ; 　　break ; case ’ ＄’ : 　　返回单词" ＄" ; 　　break ; case ’ ,’ : 　　返回单词" ," ; 　　break ; case ’ 3’ : 　　返回单词" 3 " ; 　　break ; default : 　　读取字符 ,直到碰到不可消耗的先行字符 ; 　　将不可消耗的先行字符返还 ,留待下次读取 ; 　　if ( " GP GGA"或" GP GGA" ) 　　　返回单词" GP GGA"或" GP GGA" ; 　　else 　　　将所有读到的字符作为单词返回 ; 　　break ; } 2 . 2 　语法分析 语法分析的过程相对比较复杂. 首先 ,我们给出 GGA 和 RMC 这两个句子的结构定义[4 ] 并为组成 它们的单词类型 ,如表 1 和表 2 所示. 表 1 　GGA数据格式 名称 例子 类型 Message ID GP GGA a U TC Position 161229. 487 c Latitude 3723. 2475 c N/ S Indicator N c Longitude 12158. 3416 c E/ W Indicator W c Position Fix 1 c Satellites Used 07 c HDOP 1. 0 c MSL Altitude 9. 0 c Unit s M c Geoid Separation c Unit s M c Age of Diff . Corr. c Diff . Ref . Station ID 0000 c Checksum 18 c 表 2 　RMC数据格式 名称 例子 类型 Message ID GPRMC b U TC Position 161229. 487 c Status A c Latitude 3723. 2475 c N/ S Indicator N c Longitude 12158. 3416 c E/ W Indicator W c 续表 2 名称 例子 类型 Speed Over Ground 0. 13 c Course Over Ground 309. 62 c Date 120598 c Magnetic Variation c Checksum 10 c 　　针对仅仅包含 GGA 和 RMC 的 GPS 报文 ,我 们设计一个上下文无关的文法 (Chomsky 2 型文法) G = (VN ,V T ,P ,S)如下 : VN = { A、B } 　　V T = { ＄、,、3 、、# 、a、b、c } P = { S - > A # A - > AB A - > B B - > ＄a ,c ,c ,c ,c ,c ,c ,c ,c ,c ,c ,c ,c ,c ,c 3 cλ　 B - > ＄b ,c ,c ,c ,c ,c ,c ,c ,c ,c ,c 3 c } 这里 , 代表单词" < CR > < L F > " , # 代表报文 结束字符 ,a 代表" GP GGA" ,b 代表" GPRMC" ,c 代 表句子中的各个数据域或校验和 ,如表 1 和表 2 所 示. 这些数据域的值可以是相应的数据也可以为 (代表该域为空) . 该文法既不是 LL (1) 文法也不是简单优先文 法 ,所以不能采用自顶向下分析和简单优先分析法. 注意到 B 的产生式右端第一个单词都为" ＄" ,我们 可以将该文法改为算符文法. 修改后的文法如下 : VN = { A、B } V T = { ＄、,、3 、、# 、a、b、c } P = { S - > A # A - > A ＄B A - > ＄B B - > a ,c ,c ,c ,c ,c ,c ,c ,c ,c ,c ,c ,c ,c ,c 3 cλ B - > b ,c ,c ,c ,c ,c ,c ,c ,c ,c ,c 3 c } 下面我们构造该算符文法的算符优先关系表. 由 B 的两个产生式可以得出优先级相等的终 结符 ,在表 4 中用" = "标记. 为了计算非终结符中的 不等 优 先 关 系 , 首 先 计 算 每 个 非 终 结 符 的 FIRSTV T 集合和 LASTV T 集合如下 : 　　FIRSTV T(S) = { # 、＄} 　　　　　　　 FIRSTV T(A) = { ＄} FIRSTV T(B) = { a、b } LASTV T(S) = { # } LASTV T(A) = { ＄、λ} LASTV T(B) = {λ} 对于 <关系 ,列出以上文法中终结符在前非终结 符在后的所有相邻符号对 ,并确定算符的 <关系如下 : 　　对 ＄B 有 : ＄< FIRSTV T (B) 　　　　　　 对于 >关系 ,列出以上文法中非终结符在前终结 符在后的所有相邻符号对 ,并确定算符的 >关系如下 : 对 A # 有 :LASTV T(A) > # 　　　　　　 007 电 　子 　器 　件 第 30 卷 对 A ＄有 :LASTV T(A) > ＄ 由以上对算符优先级的构造可知该文法中任意 两个终结符对之间至多只有一种优先级关系存在 , 是一个算符优先文法 ,即 OP G 文法. 表 4 中给出了 算符优先级的构造结果. 利用所构造的算符优先关 系表 ,我们可以编程实现算符优先分析法 ,对该文法 进行分析 ,程序框图如图 6 所示. 图中 ,S 为符号栈 , 用以寄存归约或待形成最左素短语的符号串 ,a 为 一个工作单元 ,用以存放当前读入的终结符. 表 4 　算符优先关系表 ＄ a、b , c p、v 3 r λ # ＄ > < > a、b = , = = c = p、v =3 = r = λ > > # 2 . 3 　语义分析和代码生成 与一般的编译程序相同 ,我们采用语法制导翻 译方法进行语义分析 ,同时完成代码生成工作. 由于 文法比较简单 ,这部分工作也相对比较简单 ,无需构 造一般编译程序中所需要的符号表 . 此阶段的主要 图 6 　程序框架 工作是当语法分析中进行规约的同时检查相应的数 据类型是否匹配 ,并把感兴趣的数据 ,如经度、纬度、 速度等等 ,提取出来 ,转换成我们所希望的形式存储 或显示 ,程序框架见图 6 中虚线部分. 3 　性能分析和测试 整个解析过程仅仅对 GPS 报文进行一次扫描 , 有着较高的解析效率. 我们利用 C + + 语言实现了 该解析算法 ,并在嵌入式平台上 ( PXA255 处理器[7 ] + Windows CE. N ET 操作系统[8 ] )用该模块连续解 析 6 000 条 GPS 报文而未发现任何错误. 我们将该 方法用到了实际的车载导航系统中 ,效果很好. 在实 际应用中 ,我们让该程序模块连续工作 10 h ,没有 出现丢包、解析错误等不正常现象. 4 　小结 本文针对 NM EA0183 协议的特点 ,引入编译 技术 ,设计了基于编译技术的 NM EA0183 协议解 析方法. 测试表明该方法稳定可靠 ,可以保证长时间 连续正常工作的要求. 本文对其它字符协议报文解 析模块的设计也有一定的参考意义. 参考文献 : [ 1 ] 　李长真、GPS 全球定位系统 [ J ]、现代物理知识、2000 , 12 (C00) :90292. [ 2 ] 　刘喜珍 ,郝义德、GPS 技术及其在农业中的应用[J ]、北京农业 科学、1999 年、17 卷、第 6 期、7210. [ 3 ] 　张文军、GPS 与嵌入式系统软硬件接口及导航信息提取软件 [J ]、计算机工程、2005 ,31 (18) :2102212. [ 4 ] 　http :/ / www. nmea. org/ . NMEA 0183 Standard For Interfacing Marine Electronic Devices [ EB/ OL ] , Version 2. 30 , March 1 , 1998. [ 5 ] 　张素琴 ,吕映芝 ,蒋维杜、编译原理 [ M ]、第 2 版、北京 :清华大 学出版社、2005[ 1211 ] . [ 6 ] 　冯博琴 ,冯岚等译、(美) Kennet h C. Louden 著 , 编译原理及实 践[ M ] , 第 1 版 ,北京 :机械工业出版社 ,2000 :1218. [ 7 ] 　Intel Corporation. Intel PXA255 Processor Developer’s Manual [ S] . March 2003. [ 8 ] 　陈向群 ,王雷 ,马洪兵、Windows CE. N ET 系统分析及实验教 程[ M ]、第 1 版、北京 :机械工业出版社、2003 :1211. 107第 2 期 钱德俊 ,张 　哲等 :NM EA0183 协议解析