一种通用高效语法分析器的设计与实现

《一种通用高效语法分析器的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据lSSN1009—3044ComputerKnowtedgeAndTechnology电脑知识与技术V01．5，No．2January2009，ppA32—433E—mail：edu尬CCCC．net．cahttp：／／www．dnzs．net．enTel：+86．．551—-56909635690964一种通用高效语法分析器的设计与实现肖增良．何锫(长沙理工大学计算机与通信工程学院，潮南长沙410076)摘要：针对大型应用软件中嵌入脚本语言问题，提出了一种快捷而通用的语法分析器设计与实现方法。建立了脚本语言文法的描述规范；设计并实现了语法分析的算法。实例表明，该算法实

2、现的语法分析器完全可以迭到工程要求。关键词：脚本语言：BNF文法：语法分析器；delphi中图分类号：TP311文献标识码：A文章编号：1009-3044(2009)02—0432-02DesigningandImplementingofACommonandHighlyEfficientParserX

3、AOZeng-Liang，HEPd(TheInstituteofComputerandCommunicationEngineering，ChangshaUniversityofScienceandTechnology，Changsha410076，Chjna)Abstract：F

4、orembeddedscripringlanguageproblemoflarge—scaleapplicationsoftware，afastanduniversalgrammaranalyzerisdesignedandimplemented。Firstofa11，asc却tinglanguagetodescribethegrammarrolesisestablished；thenaparsingalgorithmsisdesignedandira-plemented，ExamplesshowthatthealgunthmofthegrammaranalyzerCanbea

5、chievedengineeringrequirements．Keywords：stopringlanguage；BNFgrammar；grammaranalyzer；delphi1引言随着计算机应用的发展，应用软件的功能越来越强大，需求越来复杂。为应对这种复杂需求，许多大型应用软件都提供脚本以支持用户定制与扩展软件功能。如动画制作软件Flash、3DSMax等，以及各种工业组态软件。研制语法分析器，可以使用YAC011以及LALRt≈自动生成。但使用上述丁具存在两个缺点：～是生成的分析器效率较低，二是需按生成工具的要求改写文法【3】。语法分析自动生成器方面的研究工作，国内完全

6、处于空白状态13】。所以进行通用高效语法分析器的研究T作具有较大的理论及实用价值。2脚本语言文法的描述规范巴科斯范式(BNF)是描述语法规则的一种形式化方法，该方法引入了“元符号”来定义文法。本文为了增强文法的描述能力。在设计脚本语言的时，引入了一些新的“元符号”，扩展了巴科斯范式的语法描述规则，见表l。3语法分析器设计与实现3．1重要的数据结构设计设计语法分析器时，采用集合结构来管理文法中的非终结符及相应的产生式，每个集合元素包含两个域：非终结符标识串和产生式串。语法分析的结果采用多叉树结构保存，其结点结构如图1所示。3．2语法分析算法图2为语法分析器的功能结构．为提高分析效

7、率及通用性。算法中没有使用分析表．而是直接使用文法规则进行规约和移动。分析算法采用改进的LR分析算法，其流程如图3所示。输八缓冲区

8、

9、

10、一表1文法描述元符号定义元符号定义元荷号定义一非终结符面表示字母()括号内的语_)老成分可以重复。#表示教罕或者，为车部可由多个在郁定义““表示置定支字【1表示括号内的成钎为任选项‘‘空格．表示一个或多十空桔定上荷l表硅亨持串(1表示圜卞舌号内的成分忱先～表示任何字符R表_，r=逛q稚导图1多又树结点开始输入缓冲区结束：>—叶痞主文法规则结束、＼／No室新馕取文隆规则根据文法规则分别进行匹配处理读入下一个输入荷号与方挂规刚项图3语法分析算法流程

11、图收稿日期：2008—10—25作者简介：肖增良(1969-)，男，湖南郡阳人，讲师，硕士，主要研究方向：软件工程，人工智能；何锫(1963一)，男，教授，博士，主要研究方向：软件工程，计算机科学理论。432-·人工■健爰识别技术-·--·本拦目责任编辑：唐一东万方数据肖增良等：一种通用高效语法分析器的设计与实现4应用实例语法分析器是基于Hoare逻辑的交互构造型时序语言验证系统l蝴的重要子系统，我们采用上述算法设计并实现，以delphiI锄l作为开发T具．分析运行结果如图4所示。系统的运行