基于Web的语法分析器的实现

第２７卷第ｌＪ期　

企业技术开发　

２００８年ｌ１月　

Ｖ０１．２７　Ｎ０．１ｌ　

ＴＥＣＨＮ０ＬＯＧＩＣＡＬ　ＤＥＶＥＬＯＰＭＥＮＴ　ＯＦ　ＥＮＴＥＲＰＲＩＳＥ　

Ｎ０ｖ．２ｏ０８　

于ｗｅｂ的语法分析器的实现　

李涛　

（国防科技大学计算机学院，湖南长沙４ｌ００８１）　

摘　要：基于脚本的ｗｅｂ交互模式是一种新的ｗｅｂ交互模式，通过这个模式，用户可以高效地输入大量复杂的数　

学逻辑公式或自定义脚本代码，通过脚本编译器进行翻译与执行。另外用户还可以对脚本语法进行动态修改．定　

制自己习惯的脚本语言进行工作，提高工作效率。　

关键词：编译器；ＡＮＴＬＲ；Ａ．ＩＡＸ；语法热修改　

中图分类号：ＴＰ３ｌ４　文献标识码：Ａ　文章编号：ｌ００６—８９３７（２００８）ｌｌ一０００３一ｏ４　

Ｔｈｅ　ｉｍｐｌｅｍｅｎｔａｔｉ０ｎ　０ｆ　ｇｒａｍｍａｒ　ａｎａｌｙｚｅｒ　ｂａｓｅｄ　０ｎ　Ｗｅｂ　

ＬＩ　Ｔａ０　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａ　ｎｅｗ　Ｗｅｂ　ｉｎｔｅｒａｃｔｉＶｅ　ｍｏｄｅ：　Ｗｅｂ—ｂａｓｅｄ　ｉｎｔｅｍｃｔｉｖｅ　ｓｃｒｉｐｔｉｎｇ　ｍｏｄｅ．　Ｕｓｅｒｓ　

ｃａｎ　ｉｎｐｕｔ　ｃｏｍｐｌｅｘ　ｍａｔｈｅｍａｔｉｃａｌ　ｌｏｇｉｃａｌ　ｆ０＿瑚ｕｌａ　ｅｍｃｉｅｎｔｌｙ　ｗｉｔｈ　ｔｈｉｓ　ｍｏｄｅ．Ｔｈｅ　ｐａｐｅｒ　ａｌｓｏ　ｐｒｅｓｅｎｔｓ　ａ　

ａ．ｍｍａｒ　ｄｙｎａｍｉｃ　ｍ０ｄｉｆｉｃａｔｉｏｎ　ｍｅｃｈａｎｉｓｍ，　ａＵｏｗｉｎｇ　ｕｓｅｒｓ　ｔｏ　ｃｕｓｔｏｍｉｚｅ　ｔｈｅ　ｇｒａｍｍａｒ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅｉｒ　ｏｗｎ　

ｈａｂｉｔｓ　ｓｃｒｉｐｔｉｎｇ　ｌａｎｇｕａｇｅ　ｗｉｔｈ０ｕｔ　ｒｅｓｔａｒｔ　ｗｅｂ　ｓｅｒｖｅｒ．　

Ｋ　ｌｙｗＯｒｔＩｓ：ｃ０ⅡＩｐｊｌｅｒ；ＡＮＴＬＲ；ＡＪＡＸ；ｇｒａｍｍａｒ　ｈｏｔ　ｍｏｄｉ　ｃａｔｉｏｎ　

随着计算机应用的普及，各行各业都开始拥有　中，做到即写即用可以免去重新打包发布和重启服　

自己的信息化系统，使用计算机进行工作的人也越　务器的繁琐步骤，提高了系统效率，降低因为重启　

来越多。人们对系统功能的需求会随着他们对系统　

系统而产生的类似数据丢失和无法恢复系统原有　

的熟悉而不断变化，如果通过重新编码来满足用户　运行环境之类的问题。本文对以上两个功能的实现　

新的需求会让系统的开发周期无限延长，开发成本　

进行了研究。　

和系统效率都无法保证。现在很多软件都提供了插　

件来对软件功能进行扩充，但是通过插件来扩充系　

ｌ需求介绍　

统功能难度较高，必须要有专业的程序员才可以完　现在常用的输入方法是用窗体控件，常用控件　

成。我们通过对一些系统使用情况的了解，发现用　

有下面几个：文本输入框（文本框，ＴｅｘｔＡｒｅａ等），主　

户扩展需求一般是对一些现有功能的重新组合，增　要是用来输入字符串或数字参数，但随意性较大，　

加一个全新功能模块的需求并不多。另外，我们调　

要保证程序稳定必须对输入进行验证；限制性输入　

查的几个行业都有他们自己习惯的行业语言。如果　

框（下拉列表和列表框等），让用户从多个备选项中　

能用这些简单直观并且用户熟悉的行业语言来定　选择需要的内容，这类控件一般是用来输入内容相　

制系统功能可以让用户掌握起来更加轻松，并且能　

对固定的数据，用这个控件可以精确地控制用户输　

快速的使用这些熟悉的语言对系统进行扩展，让用　

入，但如果需要输入的内容不在列表中的话，使用　

户可以在系统中自行增加一些需要的功能而不需　起来会比较麻烦。现在用户对数据输入的要求越来　

要对整个系统进行修改。　

越高，以某银行审计系统为例，该系统在每次审计　

现在的信息系统一般都是采用Ｂ／Ｓ结构，大部　

时需要从两个数据库几百个表中选择几个需要进　

分工作包括系统使用和系统管理都是在客户端的　

行审计的表和字段，将它们用算术和逻辑符号进行　

浏览器上完成的。如果能在Ｗｅｂ端直接对控制系　

组合后计算出结果并保存到另外的审计表中。如果　

统的语句进行定义并且马上将新语句添加到应用　

使用传统的窗体输人方式输人这样的表达式需要　

从列表框中找出表与字段，从下拉列表中选择需要　

收稿日期：２ｏ０８一ｏ９一Ｏ２　

作者简介：李涛（１９８Ｏ一），男，湖南长沙人，硕士研究生，研究方　

的算术和逻辑运算符，然后生成表达式，使用起来　

向：软件工程，分布式软件技术。　

非常繁琐。　

４　企业技术开发　２００８年ｌ１月　

鉴于常规输入法的几个局限：输入内容难以控制，　表名）　条件条件表达式　

查询列表：表达式（，表达式）　

条件表达式：表达式（（并且Ｉ或者）表达式）　

表达式：表名．字段名（（士ｌ—Ｉ　Ｉ／）表名．字段名｛　

规则中冒号“：”左边的内容就是规则名，冒号　

输入不够灵活。我们提出一个新的输入模式：基于　

ｗ。ｂ的脚本输入法。该模式由３个部分组成：一个　

文本输入框．可以在其中输入任意内容；一套词法　

与语法分析器，用来验证用户输入的正确性；一套　

语义分析器，用来理解用户输入并控制系统执行相　

应操作。另外，为了提高脚本的灵活性，我们增加了　

一

右边出现的如“查询”，“ｆ所有Ｉ查询列表１”等都属　

于语法元素，“『，表名１　”表示“表名”这个语法元素　

个脚本热修改模块，可以在修改了脚本语法定义　可以重复出现。“￥ｆ＋ｌ—Ｉ　Ｉ，１￥”表示４个算术符号中　

后直接将新语法应用到系统中而不必重启系统。　

２系统实现　

２．１用户界面　

为了提高脚本输入效率，减少输入错误，我们　

使用ＡＪＡｘ技术制作了一个文本输入组件，对用户　

的输入进行拼写检查并对输入的关键字进行着色，　

当验证语法出现问题时在输人文本相应位置会给　

出提示，方便用户查错。这个模块可以帮助用户在　

输入时发现自己的拼写错误并及时改正，这比完全　

依赖编译器对脚本进行分析找到错误后再提示用　

户进行更改的效率要高很多，也可以避免用户因为　

执行编译打断自己的思路。　

我们在某银行审计系统项目中应用了这个输　

入模式来接收我们定义的中文查询语句脚本。用户　

可以不受限制的在输入框中输人任意内容，但是如　

果输入的内容与规定的语法不符，输入框会在相应　

的位置用特殊的颜色将内容标识出来，这时用户可　

以对那些系统不能理解的内容一目了然。　

要对内容进行限定，我们首先要定义系统能够　

接受的语法，然后定义语法的语法规则（既元语　

法），使用扩展ＢＮ　ＦＩｌＪ文法。定义语法规则的元语法　

格式为：规则名：规则内容。　

规则名是一串有意义的字符串，用来标识这个　

规则；规则内容由规则名、终结符（它们都被当成语　

法元素）和操作符组成。操作符有括号“（”和“）”，括　

号中的内容可以被看成一个独立的语法元素，有自　

己的规则名，终结符和操作符组合；短竖线“￥ｌ￥”是　

选择操作符，它左边和右边的内容只有一个能够出　

现；方括号“ｆ”和“１”是可选操作符，其中的内容可　

有可无；星号“：ｌ＝’，是闭包，它一般紧接在一个语法元　

素后面出现，用来表示这个语法元素可以有０到无　

穷大次重复出现；加号“＋”和星号类似，只是语法元　

素至少出现一次。根据这个元语法，我们可以定义　

出查询语句语法规则的简化版本：　

查询语句：查询（所有ｌ查询列表）来自表名（，　

选择１个来连接２个字段进行运算。其中表名，字　

段名，表达式等规则在语法文件的其他地方进行了　

定义。　

当用户输入“查询”关键字时，输入框将“查询”　

二字变成蓝色并显示出来，同时根据语法定义列出　

“查询”关键字后可用的其他成分：系统中存在的所　

有表名（因为查询列表必定是以表名．字段名开　

头），关键字“所有”，用户可以选择需要的内容，也　

可以通过键盘直接输入。因为系统中可能会有很多　

张表，对于一个熟练的操作员，直接输入需要的内　

容所花费的时间是从列表中选择花费时间的ｌ，１０。　

当用户熟悉这种脚本输入方式后能够极大提高他　

们操作系统的输入效率。　

２．２词法分析和语法分析　

因为我们定义的脚本语言是一种受限语言，我　

们无法像使用窗体控件输人那样直接看到用户每　

部分输入的内容，而且用户也可能因为输入错误造　

成输入的脚本无法被计算机理解执行，因此我们必　

须在用户输入完成后对输入内容进行检查，判断输　

入内容是否符合我们定义的词法与语法。如果输入　

错误，给出错误提示，如果输入正确就将程序执行　

需要的参数从脚本中提取出来交给程序进行处理。　

分析用户输入主要分为两步：词法分析和语法分析。　

词法分析的任务是从左至右逐个字符对源程　

序进行扫描，判断字符是否能被接受，并且产生单　

词符号，将字符串源程序转换为单词符号串的中间　

程序。词法分析器就是用来执行词法分析的程序ｆ２】。　

要进行词法分析首先要定义元语法，它一般表　

现为如下的形式：　

Ｒｉ：Ｐｉ｛Ａｉ｝；　

其中Ｒｉ是识别规则名；　是用正规表达式定　

义的词法规则；Ａ；定义了如果该规则匹配成功后要　

执行的动作。　

词法分析一般有两个步骤：首先进行预处理，　

去掉无意义的字符，如多余的空白，回车符等和与　

程序执行无关的注释代码；然后对标识符、常数、操　

第２７卷第ｌ１期　李涛：基于ｗｅｂ的语法分析器的实现　５　

作符等进行识别。识别方法是：从左到右逐个扫描　

输入串，寻找能够匹配规则的最长子串，如果匹配　

法规则中查找，如果有匹配的语法规则则进行规约，　

同时生成一个由语法元素到语法规则的连接，其中　

成功就将该子串截下来放到一个ＴＯＫＥＮ缓冲区，　

析器。由识别规则产生词法分析器Ｊａｖａ代码的工　

语法元素为叶子节点，语法规则为根节点：如果不　

这个动作直到所有语法元素都读入并完成规约。在　

读取语法元素的同时将那些与翻译无关的信息去　

掉，当所有规约完成后得到的语法树即为抽象语法　

树。　

执行动作　，完成后将得到的单词符号交给语法分　存在匹配的语法规则则读人下一个语法元素，重复　

作由ＡＮＴＬＲ自动完成。　

语法分析的任务是在词法分析识别出单词符　

号串的基础上判定程序的语法结构是否符合语法　

规则。词法分析分为自上而下分析法和自下而上分　

析法，我们在这里采用的是自上而下分析法，即从　

开始符号出发向下推导最终得到输入的句子。　

要构造有效的自上而下分析器我们首先要定　

义几个概念：假定有文法Ｇ＝（ｖ　，ｖ　，Ｓ，Ｐ），当Ａ∈ｖ　

时有Ａ一　．Ｉ仅　１．．・ｌ仅　∈Ｐ。对所有Ａ∈ｖ　的每个候　

选仅，定义它的终结首符集ＦＩＲＳＴ（仅）为：ＦＩＲＳＴ（仅）　

＝

｛ａ｝　ａ…，ａ∈ｖ。｝；定义ＦＯＬＬＯｗ（Ａ）为：Ｆ０Ｌ—　

ＬＯｗ（Ａ）＝｛ａｆｓ　…Ａａ．．・，ａ∈ｖ　｝。则满足以下条件　

的文法称为ＬＬ（１）文法，可以构造有效的自上而下　

分析器：文法不包含左递归；若Ａ　０【。ｌ　Ｉ．．・ｌ　０【　则　

ＦＩＲＳＴ（０【ｉ）ｎＦＩＲｓＴ（０【ｉ）＝　（ｉ≠ｉ）；对每个非终结符　

Ａ，若￡∈ＦＩＲｓＴ（Ａ）贝０　ＦＩＲｓＴ（　ｉ）ｎＦＩＲＳＴ（　ｉ）＝　。　

对于ＬＬ（１）文法可以用下面的算法进行推导：　

假定要用非终结符Ａ进行匹配，输入的符号为ａ，Ａ　

的所有产生式为Ａ一０【。Ｉ仪　１．．・ｌ　０【　。　

①若０【∈ＦＩＲｓＴ（仅ｉ），则指派仅ｉ去执行匹配任　

务。　

②若ａ不属于任何一个候选首符集，则　

ｉ．若８属于某个ＦＩＲｓＴ（　ｉ）且ａ∈ＦＯＬＬ０ｗ　

（Ａ）￥则让Ａ与自动匹配；　

ｉｉ．否则，ａ的出现是一种语法错误。　

语法分析器由ＡＮＴＬＲ根据产生式按照以上算　

法自动生成。　

２．３翻译器　

如果用户脚本通过了词法分析和语法分析，表　

示用户输入符合我们预先定义的语法规则，我们就　

可以根据规则将需要的语法元素提取出来作为控　

制系统运行的参数。比如在前面讲到的银行审计系　

统中，用户输入的自定义中文查询语句最终需要被　

翻译成正规的ＳＱＬ查询语言［３】交给数据库去执行。　

而这个翻译任务在经过语法分析器将各个语法元　

素分离出来生成抽象语法树后就可以由翻译器轻　

松完成了。　

抽象语法树的构造方法如下：从输入串中每次　

读取一个语法元素，将所有已读取的语法元素在语　

通过语法分析器找到的中文表名可以直接从　

数据库中得到对应的英文表名，而中文关键字（如　

“并且”，“或者”等）也可以直接翻译成英文。　

之所以要先进行语法分析将语法元素分离，就　

是能够从自定义语法中提取出语法元素重新组合　

成目标语言。假设系统中定义了这样一个语法：“合　

并表ｌ，表２，表３…．，表ｎ存到表０”用来对多个结　

构相同的表进行合并，在标准Ｓ０Ｌ中没有类似的　

表合并语法，必须通过从相关表中提取所有数据再　

插入到目标表来完成相关操作。操作语句为【４］：　

“ＩＮＳＥＲＴ　ＩＮＴＯ表０（字段ｌ…，字段ｍ）ＳＥＬＥＣＴ字　

段ｌ…．，字段ｍ　ＦＲ０Ｍ表ｌ　ＵＮＩＯＮ　ＡＬＬ　ＳＥＬＥＣＴ　

字段１…．，字段ｍ　ＦＲ０Ｍ表２…．”，这里假设所有表　

都有ｍ个字段。通过语法分析，得到需要合并表名　

和目标表名，然后从数据库中获取这些表的结构，　

如果结构不同合并操作就无法执行，如果结构相同　

再根据得到的表名构造ＳＱＬ语句。　

进行语法分析的另一个目的是为了避免在翻　

译时因为直接替换而将内容错误的替换掉。假设用　

户输人这样一段内容来计算所有员工的实际工资：　

查询员工表．工资加员工表．奖金加ｆ员工　

表．加班时间乘员工表．加班工资１　

来自员工表　

如果不进行分析就直接替换会无法区别作为　

运算符的“加”和作为字段名称的“员工表．加班工　

资”中的“加”，如果替换操作符的动作在替换字段　

名动作之前，“员工表．加班工资”会被替换成“员工　

表．＋班工资”，替换的结果无法执行。而在完成语法　

分析后作为运算符的“加”和作为字段名称的“加”　

就不会被混淆，只要针对运算符进行“加”与“＋”的　

替换，针对字段名进行字段名的替换就可以精确的　

完成翻译。　

２．４动态加载语法　

允许脚本语法热修改让拥有权限的用户可以　

在需要的时候为系统定义新的语法来适应新业务　

的需要。虽然很多脚本语言能通过定义函数的方式　

６　企业技术开发　２（）ｏ８年ｌ】月　

来扩展语言的适用范围，提高使用效率。但直接从　

３结论　

语法层面为语言增加新命令进行扩展在形式上可　

现在的Ｂ／ｓ系统一般都是通过表单与用户进　

以更加自由，不必限定于某个固定的函数形式，从　

行交流，如果遇到输入的数据量大、数据种类过多　

而脚本可读性也更高。然而不加控制地由用户自行　

或者进行数据查找和流程控制需要输入非常复杂　

修改扩展语法定义必然会导致语法文件不断膨胀，　

的条件语句和控制命令时，界面会变得非常复杂，　

解析效率也会随之降低。通过限制语法文件大小和　

操作也很繁琐。如果要重复上次表单的操作必须将　

控制语法文件修改权限可以在一定程度上延缓这　

所有表单控件中的数据重新选择输入，其他用户要　

个现象的出现。另外，由于任何授权用户都可以对　

从多如牛毛的控件中了解命令输入者的意图也是　

语法进行修改，不可避免地会对语法产生破坏。如　

非常不方便的，这就是为什么很多操作都要求用户　

用户ａ在一次修改语法规则时因为误操作删除了　

在设定完后必须写操作文档的原因。使用脚本进行　

个规则文件，那么在恢复这个文件前所有用户都　

操作简单直观，输入的命令直接体现了用户的意图，　

将无法使用这套规则。还有如果用户ａ和用户ｂ同　

不需要用户再另外编辑文档来对操作进行描述。而　

时对同一个语法文件进行了修改并保存，必定会有　

且如果要重复操作只要将脚本粘贴到新位置即可　

个用户的修改被另一个用户覆盖掉。通过版本控　

重复上一次操作。另外，通过自定义控制脚本可以　

制功能在每次用户修改语法文件时首先对待修改　

使用用户最熟悉的行业语言来对系统进行控制，用　

的语法文件进行备份就可以尽量避免用户对系统　

户接受起来也会更快一些。　

造成这样的破坏。　

实现脚本语法热修改主要有以下三步：第一　

参考文献：　

步，首先通过ＡＮＴＬＲ的编译ＡＰＩ对语法进行编译，　

一

一

这个编译过程就是对语法定义的内容进行词法和　

语法分析，判断它是否符合元语法，然后根据元语　

法将语法定义翻译成ｉａｖａ代码；第二步，通过ｊｄｋ１．５　

提供的ｉａｖａ编译器ＡＰ１将ＡＮＴＬＲ编译后的ｉａｖａ　

文件编译成ｃｌａｓｓ字节码；最后通过ｉａｖａ的动态加载　

机制将生成的ｃｌａｓｓ文件加载到内存，如图ｌ所示。　

【ｌ】史胜辉．Ａｊａｘ技术在ｗＥＢ客户端开发中的应用［Ｊ】．中国　

管理信息化，２０Ｏ６，９ｆ６）：８８．　

ｆ２】陈火旺，刘春林，谭庆平，等．程序设计语言编译原理ｆＭＩ．　

北京：国防Ｔ业　版社，２００Ｏ．　

『３１　Ｉ）ｎｎａｌｄ　Ｄ．Ｃｈａｍｂｅｒｌｉｎ　ａｎｄ　Ｒａｙｍ０ｎｄ　Ｆ．Ｂ０ｙｃｅ．ＳＥＱＵＥＬ：　

Ａ　ＳＴＲＵＣＴＵＲＥＤ　ＥＮＧＬＩＳＨ　ＱＵＥＲＹ　ＬＡＮＧＵＡＧＥ　ｆＪ】　．

Ｐｍｃ．ＡＣＭ　ＳＩＧＭ０Ｄ　Ｗ０ｒｋｓｈ（１ｆ】ｏｎ　Ｄａ【ａ　

｛陬面　

＿一Ｊ　

Ｉ　Ｊ　ａ编译器ｌ　Ｄｅｓ（‘ｒｉ　ｐＩｉ０ｎ，Ａｃ　ｃｅｓｓ　ａｎｄ　ｃｏｎｔｍｌ，Ａｎｎ　

Ａｒｂｏｒ，Ｍｉｃｈｉｇａｎ，ｌ９７４，（１　１）：２４９．　

【４】Ｓｙｈａｓｅ，Ｉｎｃ．１Ｉｒａｎｓａｃｔ—ｓＱＬ用户指南　

［Ｍ］．　Ｓｙｂａｓｅ　Ａ（１ａｐ　ｔｉｖｅ　Ｓｅｒｖｅｒ　Ｅｎｔｅ卜　

Ｊ　

Ｉ　

获取规则代码　ｌ　

『　’　规则代码　１　

／

ｓｅ，２００１．　

／／１　编译Ｊａｖａ代码　

将规则一　弋码翻译成Ｊａｖａ代毋　

＼＼　

［５１　Ｍｉｃｈａｅｌ　Ｌ．ｓ（・０ｔｔ．程序设计语言——　

实践之路［Ｍ】．Ｍｏｒｇａｎ　Ｋａｕｆｎｌａｎｎ，２００７．　

［６】Ｂｍｃｅ　ｗ．Ｐｅｒｒｙ．Ａ＿ＪＡｘ　Ｈａｃｋｓ：Ｔｉｐｓ　

＆　ｒ０ｏｌｓ　ｆ０ｒ　Ｃｒｅａｔｉｎｇ　Ｒｅｓｐｏｎｓｉｖｅ　Ｗｅｂ　

部署编译器　

Ｕ’　

Ｓｉｔｅｓ【Ｍ】．Ｏ’Ｒｅｉｌｌｙ　Ｍｅｄｉａ，Ｉｎｃ．２０ｏ７．　

［７］金龙飞．通用可扩展编译器前端生成　

图１编辑规则自动生成编译器　

器的设计与实现【Ｄ】．长春：吉林大学，　

２００５．　

［８】戴侃，杨小虎．基于Ｊ２ＥＥ和ＦＬＥｘ技　

术构建ＲＩｘ系统的探索与实现ＩＪＪ．微　

电子与计算机，２００３，２３ｆ５１：２２．　

《企业技术开发　投稿邮　箱：ｈｎｑｙ＠ｈｎｓｔ唔ｏｖ．ｃｎ　

ｈｎｑｙ４４６２２３　１＠１　２６．ｃ０ｍ