2007年4月
电子器件
ChineseJournalOfElectronDevices
Vol.30 No.2Apr.2007
OnParsingofNMEA0183Protocol
QIANDe2jun,ZHANGZhe,HUChen
(NationalASICSystemEngineeringCenter,SoutheastUniversity,Nanjing210096,China)
Abstract:Themodule,parsingNMEA0183protocol,isacriticalpartintheguidingsystemsoftware.Therobusticityandefficiencyofthemoduleaffecttheperformanceoftheguidingsystemdirectly.ThedeepanalysisoftheNMEA0183protocolstructureandthecompilationtechnologycharacteristicleadstothemethodforparsingNMEA0183protocolusingthecompilationtechnology.Thewholeprocessiscomposedoffourphases:lexicalanaly2sis,syntaxanalysis,semanticanalysisandcodegeneration.Now,themethodhasbeenusedintheGPSguidingsys2temproduct.Thecorrespondingmoduleworksstablyinpractice,andmeetstherequestoftheproductlevel.Keywords:embeddedsystem;NMEA0183protocolparsing;compilationtechnology;GPSEEACC:6150M
NMEA0183协议解析
钱德俊,张 哲,胡 晨
(东南大学国家专用集成电路系统工程中心,南京210096)
摘 要:NMEA0183协议解析模块是导航系统中重要的软件模块,该模块的健壮性和高效性直接关系到整个导航系统的性
能.经过深入分析NMEA0183协议的结构和编译技术的特点,提出了一种利用编译技术解析NMEA0183协议的方法.整个解析过程分为四个阶段,分别对应于编译技术中的词法分析、语法分析、语义分析和代码生成.目前该方法已经应用到GPS导航产品中,实测表明解析模块稳定可靠,达到产品级要求.
关键词:嵌入式系统;NMEA0183协议解析;编译技术;GPS
中图分类号:TP391 文献标识码:A 文章编号:100529490(2007)0220698204 以导航技术为基础的各项应用在很大程度上提高了社会生产力,方便了人们的工作生活,对国民经济的发展有着重大意义.目前,我国广泛使用的是美国国防部开发的GPS(GlobalPositioningSystem)卫星导航系统[1].该系统由空间部分、地面监控部分和用户接收机三大部分组成[2],如图1所示.其中,GPS模块通过空间部分提供的信息计算出自己当前的位置速度等信息,然后将这些信息用NMEA0183协议封装[3],并通过串口发送给数据处理中心(通常为嵌入式系统)进行处理.接受并解析由GPS模块发送的数据是数据处理中心的一项重要任务,处理该任务的模块必须具备高可靠性(reli2
图1 GPS组成
ability)和高有效性(efficiency).如何正确高效地分析所接受的数据是每一个NMEA0183协议解析模块设计者所面临的问题.本文将编译技术运用到NMEA0183协议的解析中,实现了一种高效稳定的解析方法.
收稿日期:2006205209
作者简介:钱德俊(19822),男,硕士研究生,研究方向为微电子与固体电子学、嵌入式系统设计,Electronseu@gmail.com;
张 哲(19762),男,助教;
胡 晨(19672),男,东南大学电子工程系研究员.
8
第2期钱德俊,张 哲等:NMEA0183协议解析
699
1 可行性分析
1.1 NMEA0183协议简介[4]
NMEA0183协议是由美国国家海洋电子协会开
发、维护并发布的标准,用于航海远洋时使用的电子仪器之间的通信.目前大部分的GPS接受设备都遵循这一标准.该接口协议定义了在波特率为4800的串口数据总线上传输的电器信号需求、数据传输协议和时间,以及详细的句型格式.NMEA0183协议的数据以\"句子\"为单位进行发送,每个\"句子\"的结构如图2所示.假如数据域中的某个值无效,该值将被简单的忽略,但对应的\",\"仍需发送.
图2 NMEA0183协议消息结构
1.2 编译技术简介[5]
编译技术研究如何将一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价程序,它所执行的转换工作可以用图3来说明.
编译过程由词法分析、语法分析、语义分析和代码生成几个阶段组成,如图4所示.
图3 转换工作框图 图4 编译过程
其中,词法分析是编译过程的第一个阶段,这个阶段的任务是从左到右一个字符一个字符地读入源程序,对读入的字符流进行扫描和分解,从而识别出一个个单词.
语法分析是编译过程的第二个阶段,语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语,如\"程序\"、\"语句\"、\"表达式\"等.语法分析所依据的是语言的语法规则.
语义分析是审查源程序有无语义错误,为代码收集类型信息.
代码生成则是在语法分析和语义分析阶段的基
8
础上生成最终的目标程序.1.3 可行性分析
对NMEA0183协议进行分析不难发现符合NMEA0183协议的GPS报文与高级语言程序之间存在着如下共性:
①它们都由字符构成,字符是构成GPS报文和高级语言程序的最基本的单位.
②它们结构相似,都是由字符组成单词,再由单词组成语句,最后由语句组成报文或程序.③存在一种无二义的上下文无关文法对它们的进行描述.
由于上述共性的存在,我们可以利用编译技术对符合NMEA0183协议的GPS报文进行解析.从20世纪50年代编译技术的出现至今,编译技术已经发展得相当成熟[6],利用此技术对NMEA0183协议进行解析将可以有效地对解析性能进行控制.
2 解析过程介绍
导航应用只关注NMEA0183协议中定义的
GGA、GLL、GSA、GSV、RMC和VTG这五条语句.为方便描述,我们以较为常用的GGA和RMC这两条语句为例介绍NMEA0183协议的解析,把这两条语句组成的报文当成高级语言程序进行编译.描述的过程将使用编译技术中的术语.2.1 词法分析
词法分析由称为扫描程序的功能模块完成.扫描程序将GPS报文读作字符串并将其分为若干个单词记号.经过对图2中协议框架的分析,我们可以定义以下四类单词,分别为:保留字(如\"＄\"、\"GPG2GA\"、\"GPRMC\"、\",\"、\"3\"、\" 图5 单词识别DFA 其中,\"[]\"内为不可消耗的先行字符.与此对 应的获取单词的代码框架如下: readacharch; switch(ch){ 700 电 子 器 件 第30卷 case’ readacharch; if(ch==’ ) 返回单词\" 2.2 语法分析 语法分析的过程相对比较复杂.首先,我们给出GGA和RMC这两个句子的结构定义[4]并为组成它们的单词类型,如表1和表2所示. 表1 GGA数据格式名称 例子 类型 MessageIDGPGGAa UTCPosition161229.487cLatitude3723.2475 cN/SIndicatorN cLongitude12158.3416 cE/WIndicatorWcPositionFix1cSatellitesUsed 07cHDOP1.0cMSLAltitude 9.0cUnits M cGeoidSeparation cUnits McAgeofDiff.Corr.cDiff.Ref.StationID 0000cChecksum18c表2 RMC数据格式名称 例子 类型 MessageID GPRMCbUTCPosition 161229.487 cStatusA cLatitude3723.2475 cN/SIndicatorN cLongitude12158.3416 cE/WIndicator Wc 8 续表2 名称 例子 类型 SpeedOverGround0.13cCourseOverGround 309.62cDate 120598 cMagneticVariation cChecksum 10 c 针对仅仅包含GGA和RMC的GPS报文,我 们设计一个上下文无关的文法(Chomsky2型文法)G=(VN,VT,P,S)如下: VN={A、B} VT={＄、,、3、、#、a、b、c}P={S->A# A->ABA->BB->＄a,c,c,c,c,c,c,c,c,c,c,c,c,c,c3cλ B->＄b,c,c,c,c,c,c,c,c,c,c3c} 这里,代表单词\" 该文法既不是LL(1)文法也不是简单优先文法,所以不能采用自顶向下分析和简单优先分析法.注意到B的产生式右端第一个单词都为\"＄\",我们可以将该文法改为算符文法.修改后的文法如下: VN={A、B} VT={＄、,、3、、#、a、b、c}P={S->A# A->A＄BA->＄B B->a,c,c,c,c,c,c,c,c,c,c,c,c,c,c3c λB->b,c,c,c,c,c,c,c,c,c,c3c} 下面我们构造该算符文法的算符优先关系表.由B的两个产生式可以得出优先级相等的终结符,在表4中用\"=\"标记.为了计算非终结符中的不等优先关系,首先计算每个非终结符的FIRSTVT集合和LASTVT集合如下: FIRSTVT(S)={#、＄} FIRSTVT(A)={＄}FIRSTVT(B)={a、b} LASTVT(S)={#} LASTVT(A)={＄、λ}LASTVT(B)={λ} 对于<关系,列出以上文法中终结符在前非终结符在后的所有相邻符号对,并确定算符的<关系如下: 对＄B有:＄ 对A#有:LASTVT(A)># 第2期 钱德俊,张 哲等:NMEA0183协议解析701 对A＄有:LASTVT(A)>＄ 由以上对算符优先级的构造可知该文法中任意两个终结符对之间至多只有一种优先级关系存在,是一个算符优先文法,即OPG文法.表4中给出了算符优先级的构造结果.利用所构造的算符优先关系表,我们可以编程实现算符优先分析法,对该文法进行分析,程序框图如图6所示.图中,S为符号栈,用以寄存归约或待形成最左素短语的符号串,a为一个工作单元,用以存放当前读入的终结符. 表4 算符优先关系表 ＄ a、b, c p、v 3r λ #＄ > < > a、b = ,== c= p、v = 3 = r = λ > > # 2.3 语义分析和代码生成 与一般的编译程序相同,我们采用语法制导翻译方法进行语义分析,同时完成代码生成工作.由于文法比较简单,这部分工作也相对比较简单,无需构 造一般编译程序中所需要的符号表.此阶段的主要 图6 程序框架 8 工作是当语法分析中进行规约的同时检查相应的数据类型是否匹配,并把感兴趣的数据,如经度、纬度、速度等等,提取出来,转换成我们所希望的形式存储 或显示,程序框架见图6中虚线部分. 3 性能分析和测试 整个解析过程仅仅对GPS报文进行一次扫描,有着较高的解析效率.我们利用C++语言实现了 该解析算法,并在嵌入式平台上(PXA255处理器[7]+WindowsCE.NET操作系统[8])用该模块连续解析6000条GPS报文而未发现任何错误.我们将该方法用到了实际的车载导航系统中,效果很好.在实际应用中,我们让该程序模块连续工作10h,没有出现丢包、解析错误等不正常现象. 4 小结 本文针对NMEA0183协议的特点,引入编译技术,设计了基于编译技术的NMEA0183协议解析方法.测试表明该方法稳定可靠,可以保证长时间连续正常工作的要求.本文对其它字符协议报文解析模块的设计也有一定的参考意义.参考文献: [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/.NMEA0183StandardForInterfacing MarineElectronicDevices[EB/OL],Version2.30,March1,1998. [5] 张素琴,吕映芝,蒋维杜、编译原理[M]、第2版、北京:清华大 学出版社、2005[1211]. [6] 冯博琴,冯岚等译、(美)KennethC.Louden著,编译原理及实 践[M],第1版,北京:机械工业出版社,2000:1218. [7] IntelCorporation.IntelPXA255ProcessorDeveloper’sManual [S].March2003. [8] 陈向群,王雷,马洪兵、WindowsCE.NET系统分析及实验教 程[M]、第1版、北京:机械工业出版社、2003:1211. 因篇幅问题不能全部显示，请点此查看更多更全内容