- 浏览: 37768 次
最新评论
作者:王东 就像是我们使用编译器编译c, cpp文件一样, 对查询语句的编译过程也分为了如下几部分: l 词法分析;
l 语法分析;
l 语义分析和检测;
l 查询重写;
l 生成查询计划;
l 挑选和优化查询计划; 这里主要是针对前三步进行说明。
当我们输入一个SQL语句时, CUBRID的查询编译器会按照类似代码编译器的方式进行工作。 1. 首先进行词法分析,词法分析的目标是将SQL语句进行扫描并分割成为一系列记号(Token),在CUBRID中,是使用Flex生成的文件进行词法分析的。Flex(fast lexical analyser generator)是一个自动的词法分析器生成器(参考附1)。在CUBRID中,有一个描述SQL词法的.l 文件,该文件描述了SQL语句中用的词汇。通过使用Flex,并输入.l 文件,将生成对应的可以用的编译的.c文件。词法分析的结果产生了各种记号(Token), 例如:关键字,标识符,字符串等等;
2. 接下来进行语法分析。语法分析是将词法分析产生的记号(Token)按照语法要求生成语法树(Syntax Tree)。CUBRID 中采用bison来进行语法分析(参考附录2)。类似于编译器中的表达式一样,不同的SQL语句,将被看作为不同表达式(Expression)。CUBRID中有一个描述语法的.y文件,该文件中包含表达式树是如何组织起来的代码。通过bison,并输入.y文件,生成对应可以用于编译的.c和.h文件。这样SQL就被组织成语法树的结构了。
3. 接下来就是对语法树进行语义检测(Semantic analysis and check)。因为语法分析中只是完成了对表达式语法层面的分析,并没有对真正这条语句的内容是否合法进行检测。 CUBRID 里面的Semantic check, 是对生成的语法树进行遍历和检查。由于树的节点不同,对每个节点的遍历算法也是不同的。语义检测的结果是对不满足输入的SQL语句进行过滤(提示报错),对语法树进行适当的扩充和删减,便与接下来的生成查询计划等工作。 接下来就进行查询重写,生成查询计划其他了操作。这里暂且不提。
下面就这三部分给出CUBRID中实现的三个例子。
例子1 CUBRID词法分析
.l 文件是由正则表达式和c语法组成的。
//定义段代码
%{
//定义include文件,宏,辅助函数,flex会跳过对这些的处理。
#include"csql_grammar.h"
#include"parse_tree.h"
#defineCSQL_MAXNAME256
staticintparser_yyinput_single_line(char* buff, intmax_size);
externintyyline;
//……
%}
// 词法规则段代码
%%
[sS][eE][lL][eE][cC][tT] { begin_token(yytext); returnSELECT; }
([a-zA-Z_#]|(\xa1[\xa2-\xee\xf3-\xfe])|([\xa2-\xfe][\xa1-\xfe])|(\x8e[\xa1-\xfe]))([a-zA-Z_#0-9]|(\xa1[\xa2-\xfe])|([\xa2-\xfe][\xa1-\xfe])|(\x8e[\xa1-\xfe]))*
{ begin_token(yytext);
if (strlen(yytext) >= 254)
yytext[254] = 0;
csql_yylval.cptr = pt_makename(yytext);
returnIdName;
}
%%
通过编辑.l文件,我们可以定义我们感兴趣的token。
生成的c代码,如下:
case 338:
YY_RULE_SETUP
#line 537 "../../src/parser/csql_lexer.l"
{ begin_token(yytext); returnSELECT; }
YY_BREAK
例子2CUBRID语法分析
.y 文件定义语法树表达方式, 其中包含了Token, rule type, rule的组织方式. 例子中,select 语句的节点中就包含很多内容。
/* Token define */
/*{{{*/
%tokenSELECT
%tokenIdName
/* define rule type (node) */
/*{{{*/
%type stmt_
%type create_stmt
%type select_stmt
stmt_
: create_stmt
{ $$ = $1; }
…
| select_stmt
{ $$ = $1; }
…
;
select_stmt
: SELECT /* $1 */
{{ /* $2 发现是select语句,就创建select节点*/ PT_NODE *node = parser_new_node (this_parser, PT_SELECT); … DBG_PRINT}} … select_list /* $5 */ {{ /* $6 创建select 选项的列表节点*/
PT_NODE *node = parser_top_select_stmt_node ();
if (node)
{
node->info.query.q.select.list = $5;
}
DBG_PRINT}}
opt_select_param_list /* $7 */
FROM /* $8 */
…
opt_where_clause /* $11 where语句对应的节点*/
…
opt_groupby_clause /* $14 group语句对应的节点*/
opt_having_clause /* $16 having语句对应的节点*/
…
{{
if (node)
{
node->info.query.into_list = $7; /* param_list */
node->info.query.q.select.where = $11;
node->info.query.q.select.group_by = $14;
node->info.query.q.select.having = $16;
…
}
$$ = node;
DBG_PRINT}}
;
}}
opt_where_clause
: /* empty */
{{
$$ = NULL;
DBG_PRINT}}
| WHEREsearch_condition
{{
parser_restore_ic ();
parser_restore_sysc ();
parser_restore_prc ();
parser_restore_cbrc ();
$$ = $2;
DBG_PRINT}}
;
看到这里大家应该明白了,这种类似递归的方式传递构造语法树的过程。最终构建的是一个以select节点为根节点的语法树。其中包含了q.select.list,where,group_by,having 等节点。
例子3 CUBRID语义检测
语法检测阶段拿到的就是一个语法树的指针。在CUBRID中这个语法树就是一个PT_NODE。该结构是包含了许多类型的节点,例如创建类型,select类型等等。PT_NODE 的类型和info 是匹配的。例如:如果Type = PT_CREATE_ENTITY, Info 则是PT_CREATE_ENITITY_INFO结构体。
其中PT_NODE类型的节点用于记录节点的类型,PT_XXX_INFO的节点是用于存储信息,里面可以包含数据,也可以再包含PT_NODE节点。
这样整个语法树就递归起来。每个节点本身是PT_NODE, 每个节点的Info 里面可以包含PT_NODE。
最终整个语法树的叶子节点必然是一个PT_NODE, 它的Info中不包含任何PT_NODE的PT_NODE节点。
而PT_NODE 在内存中的布局就类似如下:
简单的语义检测可以直接操作这个语法树,例如CUBRID中partition table by Hash, 其中partition的个数不能超过1024个。
复杂的语言检测有时候需要遍历语法树,可以采用递归的深度优先算法进行遍历。
CUBRID的遍历语法树的算法的主要逻辑是:
1 刚进入节点时:处理进入前回调函数:
2 根据PT_NODE 调用自己的节点对应的遍历函数;
通常遍历函数,就是依次遍历该节点包含的子节点,由于节点不同,每个节点的子节点个数都不一样。
根据需要遍历Next节点等等;
3 离开节点时:处理离开前回调函数
例如:检测遍历PT_NODE中提到的table都是必须数据库中存在的。可以遍历语法树,关注type=PT_SPEC的节点即可。
到此为止,相信大家已经明白CUBRID语法分析和检测的过程了。如果感兴趣的,请查看我们的开源项目CUBRID源代码(参考1).
附录:
附1:什么是Flex?
Flex是一个生成扫描器的工具,能够识别文本中的词法模式。Flex读入给定的输入文件,该文件为需要生成的扫描器的描述。此描述叫做规则,由正则表达式和 C代码对组成。当运行可执行文件的时候,它分析输入文件,为每一个正则表达式寻找匹配。当发现一个匹配时,它执行与此正则表达式相关的C代码。Flex 不是GNU工程,但是GNU为Flex 写了手册。
附2: 什么是bison?
GNU bison 是属于 GNU 项目的一个语法分析器生成器。Bison 把一个关于"向前查看从左到右最右"(LALR) 上下文无关文法的描述转化成可以分析该文法的 C 或 C++ 程序。它也可以为二义文法生成"通用的从左到右最右" (GLR)语法分析器。
Bison 基本上与 Yacc 兼容,并且在 Yacc 之上进行了改进。此软件的源代码是可自由获得的,在 GPL 下发布。
Flex 和Bison 常常结合一起使用。
参考: 1. CUBRID 官方站点: http://www.cubrid.org 2. Flex 介绍: http://en.wikipedia.org/wiki/Flex_lexical_analyser 3. Yacc 介绍: http://zh.wikipedia.org/zh-cn/Yacc 4. GUN 项目里bison主页: http://www.gnu.org/software/bison/ 6. Flex和Bison入门: http://code.google.com/p/msys-cn/wiki/ChapterFour
发表评论
-
C++字符串处理
2012-07-06 09:51 7731. string是类,不是 ... -
T-SQL 正则表达式(CLR 实现)
2012-07-06 09:44 903正则表达式在处理字符串方面有其特殊的优势,但是 T-SQL ... -
正则表达式(一):纠结的转义
2012-07-06 09:36 1020用过正则表达式的 ... -
关于skin++
2012-07-06 09:29 943用了一段时间 SKIN++ 我想说 SKIN++ 想说爱你 ... -
getElementById getElementsByTagName 练习
2012-07-05 20:44 635function ... -
Java组件开发
2012-07-03 13:42 690我先介绍几个在构 ... -
Java组件开发
2012-07-03 12:14 639我先介绍几个在构 ... -
Flex 导出文件通用处理
2012-07-02 10:07 620Style Definitions */ p.MsoNor ... -
Flex 4 新体验
2012-07-02 10:07 642直到最近才开始真 ... -
关于flex的资料
2012-07-02 10:07 5909====Adobe官方==== Adobe : ... -
Adobe Flex UIComponent LifeCycle
2012-07-02 10:07 694Adobe Flex UIComponent L ... -
Flex Ant
2012-07-02 09:41 576... -
重写组件遇到的问题
2012-07-01 09:24 601有时候重写组件的时候会遇到measure函数在调用 inv ... -
使用Flex和Actionscript开发Flash游戏――碰撞检测
2012-07-01 09:24 571这一部分,我们加 ... -
Flex: DataGroup 组件增加滚动条
2012-07-01 09:24 641本想用mx:List 实现一个联系人列表,无奈AS4不知怎 ... -
在Flex4中使用RemoteObjectAMF0来连接fluorine网关
2012-07-01 09:24 632RemoteObjectAMF0是一个开源组件,可以很方便 ... -
[转载]AIR/Flex学习笔记(2)
2012-06-30 11:11 637[转载]AIR/Flex学习笔记(2) ... -
flex 学习网站
2012-06-30 11:11 742flex 学习网站 2010年12月06日 flex20 ... -
TWaver Flex开发环境
2012-06-30 11:11 757TWaver Flex开发环境 2011 ... -
AIR/Flex学习笔记(1)
2012-06-30 11:11 683AIR/Flex学习笔记(1) 2010 ...
相关推荐
Cubrid 数据库管理员手册,Cubrid是韩国开发的一个开源的数据库,本手册为管理员使用手册。 网址:http://www.cubrid.com/
ngrinder的linux32位监控工具CUBRID-9.3-latest-linux.i386.sh
tables_cubrid.sql
CUBRID 是一个全面的 GPL/BSD 开源关系数据库管理系统,针对 Web 应用程序进行了高度优化。 CUBRID 正在用 C 语言开发。包括 HA、数据库分片、在线备份和企业就绪功能。 Node.js、JDBC、PHP/PDO、ODBC/OLEDB/.NET、...
Laravel开发-laravel-cubrid Laravel的Cubrid数据库连接程序
请参阅http://www.cubrid.org/cluster。 CUBRID Cluster是一个开源集群DBMS,具有较高的可扩展性,包括全局架构,分布式分区和负载平衡功能。 它是CUBRID项目的衍生项目,并得到NHN的支持。
这是 CUBRID 引擎项目 (sf.net/projects/cubrid) 的衍生项目,并开发 CUBRID API 以获得更好的支持。 该项目涵盖了 JDBC、PHP、ODBC、OLEDB、Ruby、Python 等。更多信息,请访问我们的网站:http://cubrid.org。
code-story-http.zip,这是我们能想到的最简单、最快、成熟的http服务器
ngrinder的linux64位监控工具,用于监控目标服务器的性能表现
CUBRID是针对Web应用程序高度优化的全面的GPL / BSD开源关系数据库管理系统。 CUBRID正在用C开发。包括HA,数据库分片,在线备份和企业就绪功能。 可以使用Node.js,JDBC,PHP / PDO,ODBC / OLEDB / .NET,Ruby,...
这个项目是关于开发一个 CUBRID 数据库的 web shell 接口,类似于 MongoDB web shell。 主要目标是以类似于 CSQL shell 的方式提供对数据库的轻松访问。
CUBRID 的 PHP MySQL 兼容接口。 这个 PHP 接口通过提供 MySQL PHP 函数和 SQL 兼容语法,促进了 MySQL 应用程序到 CUBRID 的移植。
发现可以改进的地方以及修改和提交代码来识别错误纠正整个代码中的错别字,包括注释粗斜纹自从2008年11月以开源许可(DBMS引擎:GPL v2,界面:BSD)发布源代码以来,CUBRID继续内部开发和开放开发,并在发布新版本...
该项目旨在通过开发 CUBRID Java 存储过程来增强 CUBRID 功能。
CUBRID:CUBRID是针对Web应用程序高度优化的全面的开源关系数据库管理系统
该项目的目标是针对其他知名开源数据库(例如 MySQL 或 PostgreSQL)衡量 CUBRID 数据库的性能。 将使用PHP和Java API接口库进行测量。
这是一种开源数据库 如果以后mysql 不行了 用这个还可以支持一段时间
该项目是一个用于显示 CUBRID 数据库设计模型的 Web 应用程序。 它会在您的浏览器中显示表格及其之间的关系。 它是使用 PHP 和 Silverlight 开发的。