第28卷
湖北师范学院学报(自然科学版)Vo l 128第4期Journal of Hubei Nor m a l Unive rsity (N atura l Sc ience )No 14,2008
X M L 查询编译的预处理
汪崇文
(湖北师范学院教务处，湖北黄石　435002)
摘要:X ML 查询技术正逐渐成为X ML 应用中的关键技术。论文通过对X ML 查询语言X Que ry 特点的分析，在编译相关理论扩展的基础上，提出了X Query 语言编译中的预处理的解决方案，详细讨论了其词法分析与语法分析的方法和策略，对基于X Query 的开发应用起到了一定的引导和启发作用。
关键词:XQue ry 语言；编译原理；词法分析；语法分析
中图分类号:TP314  文献标识码:A  　文章编号:100922714(2008)0420073205
  X ML (Extensible Ma rkup Language)，即可扩展的标记语言，用来创造标记语言(比如H T ML )的元语言，是一套定义语义标记的规范，其目标是能够定义计算机和人都能方便识别的数据类型。随着网络应用的快速发展，符合X ML 规范的数据
(称为X ML 数据)已大量存在于当前的信息社会，尤其是电子商务、W eb 服务、数字图书馆等应用理念的进一步发展，使得X ML 类型的数据成为当前主流的数据形式。对X ML 数据的有效管理也随之成为当前数据库领域研究的热点。
自X ML1.0规范问世以来，相继出现了多种X ML 查询语言。如侧重数据库领域的Lorel 、X ML -QL 、Y A TL 、Quilt 、X ML -G L，侧重文档领域的XS L 、X QL 等，但都不能同时满足数据库和文档两方面的需求。鉴于非结构性数据的查询工作以及关系数据库自身的缺陷，人们需要一种更优化的数据查询语言。X Q ue ry 以其良好的设计和强大的功能扮演了这个角。它是一个从X ML 格式的文档中获取数据的查询语言，起源于Quil t，并将XPath2.0作为其子集，综合XPa th1.0、X QL 、X ML -QL 、S QL 和OQL 等诸多语言的特点。
X Q ue ry 工作组于1999年9月正式成立，其任务是创建一种灵活的查询语言以便于从X ML 文档中抽取数据[1]。目前W 3C 所公布的最新XQue ry 候选推荐标准是其2005年11月3日的版本，还在不断地修订和完善之中。作为一种新型的查询语言,X Q ue ry 汲取了其他多种查询语言的优点，适用于各种类型的X ML 数据源的查询，不仅查询功能强大，而且简洁灵活且易于实现。此外,XQue ry 还具有从多种数据库中检索信息的功能，能对各种数据和文档进行查询。关于XQuery 的最新信息可通过W 3C (H ttp://www .w3c .org/X ML /Q ue ry )获取。
X Q ue ry 是一种将查询表示成表达式的功能语言，构建在XPath 规范之上，其核心是能够通过XPath 表达式从文档中选择特殊的节点序列通过它所支持的多种表达式，其查询可以有各种不同的形式。各种X Query 表达式可以完全嵌套，也支持子查询。本文尝试着将编译相关理论应用到X Query 语言的解析中，并且还提出其预处理过程的一种解决方案。
1　XQue ry 的解析
  在X Query 技术的应用方式上，通常是在系统中引入X Q ue ry 的处理模块，称作X Q ue ry 引擎。它是查询请求和X ML 数据源之间的协调者，它从用户处取得源程序形式的查询请求，理解这些请求，将它收稿日期—3—作者简介汪崇文(—　)，男，湖北省黄石市人，主要研究方向为网络信息系统1
:2008011
:1980
们转化成对特定X ML 数据源如X ML 文档或X ML 数据库的操作并实施这些操作，最后返回处理得到的结果。X Q uery 引擎和查询请求者通过XQuery 源程序来进行交流，其中直接与源程序打交道的程序就是X Q uery 解析程序，其任务是通过分析用户给出的X Q uery 源程序，在语义层面上理解用户的查询请求，将这些查询请求转换成针对特定X ML 数据源的操作。
作为对一种程序设计语言的分析,X Q uery 源程序的解析过程仍然采用类似传统的高级程序设计语言编译程序的分析方法，通过词法分析、语法分析、语义分析等步骤[2]，将X Q ue ry 语言源程序翻译为一些便于在X ML 数据的实际存储结构上进行处理的操作。和传统高级程序设计语言的编译程序一样,X Query 的解析程序在内部实现上采用模块式结构，按编译过程的几个阶段分为词法分析模块、语法分析模块、语义分析模块、中间结果生成模块以及出错处理模块和符号表管理模块[3]。
X Q ue ry 解析程序的工作重点是对源程序的理解和翻译，因此在X Q ue ry 解析程序的组成结构中，语义分析和结果生成占有更重要的地位，而前端的词法分析部分和语法分析部分由于其工作是对源程序进行初步处理，将其以语法树的形式进行描述。因此,XQuery 解析过程中的词法分析和语法分析阶段可以称为解析的预处理阶段。预处理在解析过程中处于最前端，它的任务是对源程序进行初步处理，建立其语法树形式的语法结构描述。正则匹配到第一个关键字就停止
2　词法分析
2.1　词法规则的正则表达式表示
X Q ue ry 的记号分为几种不同的类型，每种类型记号的模式都有自己的特点。关键字、标识符、数字串以及字符串记号的模式所定义的串并不固定，因此对于这些记号需要用形式化的方式描述其模式，以便于建立相应数学模型，并将其转换为可操作的算法；而其他的记号由于它们的模式定义的就是固定的串，所以直接对其识别过程进行实现并不困难。需要特别注意的是X Q ue ry 中的注释，这种语言允许其注释的嵌套，因此虽然注释的模式定义的串并不固定，但由于正则表达式不能表示递归的结构，所以注释的模式不能采用形式化的方法进行描述，其识别过程仍然只能使用手动实现。
正则表达式采用其基本形式和三种基本运算来进行模式的描述，基本形式是正则表达式定义在之上的字母表中的单个字符。正则表达式通过选择、连结和重复三种运算在基本表达式上的组合表示模式，其中重复运算的优先级最高，连结运算次之，选择运算的优先级最低。为了表示的方便，又扩展了几种新的运算，分别是一个或多个重复、任意字符符号、字符范围表达式和可选结构。XQuery 的预处理中就是首先用正则表达式的扩展形式对记号的模式进行描述，例如标识符
的模式的正则表达式是:(letter |“_”)N a m eC har 3，这个表达式表示的串是以字母或下划线开始的由X ML 定义的N a m eC har 字符集中的字符组成的串。
2.2　正则表达式的自动机
在得到词法规则的正则表达式之后，通常采用有限状态自动机来描述正则表达式的匹配过程。有限状态自动机是一种描述特定算法的数学方法，它由状态和状态之间的若干转换组成[4]。根据有限状态自动机描述的算法构成的自动机器在读取输入时，根据输入的不同其内部在不同状态间进行转换。如果对应到程序流程图上，那么自动机的各个状态对应程序流程图中的各个分支点，状态之间的转换对应程序流程的中间处理过程，当自动机在接受状态上由于在输入字符上没有状态转换而停止，就表示从输入中得到一个记号。有限状态自动机分为确定性的(DFA )和非确定性的(NFA ),D F A 的特点是在一个状态上通过读入输入中的一个字符仅能转移到另外一个状态;N F A 中，在一个状态上通过读入输入中的一个字符可能存在到其他多个状态的转移，同时还可能存在不通过输入字符到达其他状态的转移。所以，如果能将正则表达式转化为确定性的有限状态自动机，就能推导出词法分析程序的流程图。
将正则表达式翻译成D F 的算法是通过中间构造，首先正则表达式派生出一个N F ，接着用该N F 构造一个同等的DF 。正则表达式翻译成NF 的做法是先为基本正则表达式和每种基本运算对
A A A A A
应一个结构，然后将这些结构连结起来形成一个NFA 。从N F A 得到DFA 的做法是消除N FA 中的ε-
转换，对其进行子集构造。以X Q ue r y 中的标识符为例，它的正则表达式是:(le tte r |“_”
)N a m eC har 3，它对应的N F A 如图1所示
。
图1　标识符的N F A
对其进行子集构造，过程是：首先构造初始状态的ε-闭包{1}—={1,2,3}，它在le tte r 上有{4}—
到={4,6,7,9}的转换，在字符“_”上有到={5,6,7,9}的转换。状态集{4}—和{5}—在N a m eC har 上有{8}—={8,9}的转换。状态集{8}—在N a m eC ha r 上有到自身的转换。因此，从图1所示的N F A 得到的D F A 如图2所示
。图2　标识符的D F A
2.3　自动机的实现策略
自动机的特点是状态和状态间的转换，因此自动机的实现应该表现自动机的这个特点。具体做法是通过一个变量来表示当前的状态，将整个自动机作为一个无限循环，在循环体中采用ca se 分支程序使程序在自动机的各状态间转换，当在输入中的下一个字符上不存在转换时退出这个循环。由于程序用一个变量保存了自动机的状态，因此在循环结束时可以知道是在接受状态上退出了循环还是在非接受状态上退出了循环，只有在接受状态上退出了循环才表示正确识别到了一个记号，否则表示识别过程发生了错误。实现的特点是无限循环体中的嵌套ca se 分支结构，如下所示。
  while (true )
{s witc h (state ){ca se 1:
s witc h(input){
ca se A:
sta te =2;shift input ;……de fault :g oto end;}……
}3　语法分析
3.1　文法推导和语法树
X Q ue ry 的语法是以EBNF 形式的上下文无关文法给出[5]。语法分析是通过对这些文法规则的推
导确定记号符号的正规串，推导就是在文法规则的右边选择的一个合适的替代结构，替换序列中出现在文法规则左边的名字的过程，它尝试演化出一个记号类型的序列以匹配实际输入的记号序列，如果能根据文法规则演化出一个记号类型序列，使之能与输入中的记号序列匹配，那么就说输入的记号序列是符合推导所使用的文法规则的。推导通常以一个结构名字开始，并以记号符号串结束。在推导的
每一个步骤中，使用来自文法规则的选择每一次生成一个替换。
设想在文法规则推导的过程中将构造一棵树，如果将每个符号都作为这颗树的一个节点，将每个非终结符在推导过程中所实际被替换的、符号序列中的符号作为该非终结符对应节点的子节点，则整个推导过程就构造了一棵多叉树。这颗树的每个非终端节点都对应了文法规则定义中的一个结构名，每个叶子节点都是一个终结符，并且对应到程序代码中的一个记号，同时这棵树每个非终端节点的子节点所构成的序列所对应的符号串，都对应推导所使用文法中的一条规则。在推导过程中产生的这颗树，表达了程序中各个记号间的语法关系，其结构对应于推导过程所使用的文法规则，因此称为语法树。例如，现有if表达式“if1OTH ER else OTHER”，从已知文法:
<statem ent>::=<if-statem ent>|OT HER
<if-sta tement>::=IF(<ex p>)<statem ent>[E LSE<sta te m ent>]
<e x p>::=0|1
推导的过程如下:
1)sta tem en t if-sta temen t
2)I F(exp)state m ent EL SE sta tem ent
3)I F(0)state m ent EL SE sta tem ent
4)I F(0)O THER ELSE state m ent
5)I F(0)O THER ELSE O THER
按照语法树的构造方法，这个推导过程中形成了如图3所示的语法树。
图3　if串的语法树
3.2　递归下降方法及其修正
语法树在文法推导的过程中形成，如果能进行自动的文法推导或文法分析，那么这个自动进行文法分析的程序就构成了
一个语法分析程序。本文讨论的算法是递归下降分析方法，它利用输入中的先行记号来预测输入串中的下一个结构，递归下降分析方法很常用，对于手写的分析程序最为合适。
递归下降分析的概念极为简单，就是将一个非终结符A的文法规则看作将识别A的一个过程的定义。A的文法规则的右边指出这个过程的代码结构：一个选择中的终结符与非终结符序列与相匹配的输入以及对其他过程的调用相对应，而选择与在代码中的替代情况相对应。以X Q ue ry文法中的Module D ec l规则为例，它的定义是:
<Module D ec l>::=MODUL E<StringL ite ral>
它的递归下降程序的流程是:
void module_dec l(){
m atc h(MODUL E);
m atc h(String Lite ra l);
}
递归下降方法有一个缺点，就是它仅检查输入中的一个先行记号，虽然在大多数情况下通过一个先行记号就能确定下一
个语法结构，但当文法较为复杂如在处理X Q ue ry语言时就会出现无法预测的情况。解决的办法是将各个选项的文法规则引入到这个规则的递归下降程序中来，根据各选项文法规则定义的不同，来确定可选项的选择。引入选项的文法规则后，由于这些选项的文法都是以终结符开Prolog
始，所以可以在的递归下降程序中根据输入中的先行记号来确定下一个语法结构。对于在选项
之间存在具有相同先行符号的情况，由于仅依据一个先行记号无法确定语法结构，因此通过检查多个先行记号确定程序的下一步流程。以X Q ue ry文法中的Prolog规则为例，它的定义是: <P rolog>::=<Ve rsion>?(<Nam e s pac e D ecl>|<X ML SpaceDec l>
|<Default Nam e s paceD ecl>|<Default CollationDecl>
|<Schem a I mpor t>|<Modu le I mpor t>|<VarDefn>
|<Validati on D ecl>)3<Func ti on De fn>3
其部分选择项的文法定义是:
<N a m e s paceDe cl>::=DECLAR E NAMESP ACE<NCN ame>“=”<String L ite ra l>
<X ML SpaceDec l>::=DECLARE X MLSP ACE“=”(PR ESERVE|STR IP)
在利用改进后的递归下降方法进行实现时，在程序流程中的体现是:
  void p rol og(){
……
s witc h(t oken){
ca se DECLARE:
if(che ck_next(1,NA M ESPACE)){
name s p ace_dec l();
}e lse if(check_next(1,X MLSP ACE)){
x m ls p ace_dec l();
}e lse{
erro r();
}
……
default:
erro r();
}
……
}
  由于在递归下降程序中引入了子结构的文法，所以这种修正方法的缺点是降低了程序各部分的独立性，使代码变得复杂和难以阅读。
  在对XQuery语言的特点进行的分析的基础上，描述了X Query引擎中XQuery解析程序的功能，说明了预处理阶段在解析过程中的地位和作用。
详细描述了X Q ue ry解析程序中词法分析和语法分析两个功能模块的任务。在词法分析阶段，分析了X Q uery语言的词
法构成特点，给出了XQuery词法规则的正则表达式的例子，解释了构造它的有限状态自动机表示的过程。在语法分析阶段，说明了语法分析的方法即文法推导，介绍了递归下降分析方法和在X Q ue ry的语法分析程序对这种方法的修正。递归下降方法十分强大，但当文法变得复杂时程序往往复杂而难以实现。下一步的工作，就是在语法分析上引入更为形式化的分析方法，实现具有更高性能和可维护性的语法分析程序。
参考文献:
[1]Scott Boag,Don Chambe rlin,Ma ry F Fernandez,e t al.XQue ry1.0:An X ML Que ry L anguage[M].Cambr idge:
W3C,2003.
[2]Kene th C Louden.编译原理与实践[M](冯博琴，译).北京：机械工业出版社,2000.
[3]谢铉洋.X ML查询语言X Query的编译实现[D].合肥：安徽大学,2003.
[4]陈文宇，欧　齐，程　炼.形式语言与自动机[M].北京：人民邮电出版社,2005.
[5]Jon Kleinberg,Eva Ta rdos.算法设计[M](张立昂，屈婉玲，译).北京：清华大学出版社,2006.
Pr epr ocessi ng i n com p ila ti on of the X ML quer y
WAN G Chong2wen
(Acade m ic Service Sect i on,Hube i Nor m al Un iversity,Huangshi　435002,Ch ina)
Abstr a c t:The X ML que ry technol ogy is beco m ing a i m portan t pa rt as in the app licati ons using X ML techno l ogy.The s olu tion of p reproce ssing in comp ila ti on of the X Que ry language is ba sed on the extensi on of the co mp iler theorie s.This s olu tion can be use d on an i mp lementa ti on of XQuery p rocess o r.
Key wor d s:X Query language;co m pile r theory;lexic al ana lysis;syntax analysis

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。