一种用于教学的SQL编译器设计与实现

袁明磊,盛安元

(1.安徽国防科技职业学院，安徽 六安 221600； 2.六安大江信息技术有限公司，安徽 六安 221600)



一种用于教学的SQL编译器设计与实现

袁明磊1,2,盛安元1,2

(1.安徽国防科技职业学院，安徽 六安 221600； 2.六安大江信息技术有限公司，安徽 六安 221600)

摘要：SQL为数据库的管理提供了极大的方便。目前已有一批优秀的数据库管理软件，如Oracal、Mysql、SQL server、Access等，然而国内数据库管理软件开发进程缓慢，目前尚未出现一个商用的国产数据库管理软件。这说明国内计算机教育方面存在“重理论，轻实践”的问题。为了在教学中将编译理论和编译实践相结合，设计并实现了一个简化的基于FoxPro数据库的SQL编译器。该编译器主要有词法分析、语法分析、语义规约和数据库文件操作等功能。

关键词：词法分析；语法分析；语句规约

0引言

1954年，IBM的John Backus带领一批研究人员完成了世界上第一个编译器的开发，将其命名为FORTRAN语言编译器。在同一时期，Noam Chomsky也对自然语言的结构进行了研究，他将文法分为4类：0型文法、1型文法、2型文法和3型文法，最终使得编译器的结构异常简单。目前对编译器的研究主要集中在面向对象编译、并行编译、自动编译等技术方面。在编译技术的发展过程中，国内对编译技术的研究处于一个较为落后的阶段，我国尚未有一个较为成熟的编译器产品出现[1]。本文主要探讨一个基于FoxPro2.6文件格式的简化的SQL编译器的实现过程，本产品只是一个用于教学的实验产品，重点用来说明编译器的基本原理。

FoxPro原名FoxBase，是美国Fox Software公司推出的数据库产品，可在DOS上运行，与xBase系列相容，最高版本为2.6。Fox Software被微软收购后，加以发展, 使其可以在 Windows 上运行, 并且更名为 Visual FoxPro[2]。

1总体设计

一个高级语言编译器一般包括词法分析、语法分析、语义分析、代码生成、代码优化等过程。该编译器主要完成的工作是将相应的SQL语句进行词法分析、语法分析、语义分析，然后根据语义完成数据库文件的创建或修改。

该编译器支持以下5种语法：1)创建数据表： CTEATE TABLE 数据表名 (字段列表)；2)删除数据表：DROP TABLE 数据表名；3)向数据表插入数据：INSERT INTO 数据表名 VALUE (字段值列表)；4)查询数据：SELECT 字段列表 FROM 数据表名 WHERE 查询条件 ；5)删除数据表记录信息：DELETE FROM (数据表名) WHERE 查询条件。该编译器的工作流程如图1所示。

图1　基于FoxPro2.6的SQL编译器工作流程图

2词法分析的实现过程

词法分析的主要作用是按照词法分析的规则，对读入的字符串进行第一阶段的扫描，将字符串转化为单词属性字的过程。最终将字符流转化为词法记号流。这个编译器的关键字见表1。

表1　类FoxPro2.6的SQL编译器关键字

该编译器的界符和含义见表2所示。

表2　类FoxPro2.6的SQL编译器的界符

该编译器的运算符和含义如表3所示。

表3　类FoxPro2.6的SQL编译器的运算符和含义表

该系统的常量主要有： 整数和字符串类型的常量。

系统的标识符要符合如下规则：

A->a|b|c…|A|B|C…|Z；

B->0|1|2|3…|9；

C->A(A|B)*。

系统实现时，使用<词法记号, 属性>这个二元组来描述一个词法单元。该编译器的词法单元见表4所示。

词法分析的过程下：1)首先读取待编译的文本文件；2)将文件读取到Buf[MAXSIZE]数组内；3)查找开始符“{”，“{”之前的所有内容均为无效内容，如果整个文本均无“{”则报错：“没有开始符” ；4)依次取字符串，并判断字符串的属性值，记录<词法记号,属性>二元组到words[MAXSIZE]数组内；5)记录不合法的字符串，并将其记录到一个错误词法记号数组内；6)找到“}”，词法分析结束。词法分析完成后得到一个<词法记号, 属性>二元组队列。该队列为语法分析提供基础数据。

表4　类FoxPro2.6的SQL编译器的词法单元表

3语法分析

该系统的语法分析部分主要对5种语法的子句进行分析,分析结果如下：

1)CREATE TABLE<表名>(属性列，…)

S->E:

E->CREATE TABLE 标识符(A)

A->标识符，A | ξ

2)DROPTANBLE <表名>

S2->E

E->DROPTABLE 标识符

3)SELECT *|(列名，…)

FROM (表名)

WHERE子句AND|OR子句…

S3->E

E->SELECT A FROM 标识符 B

A->*|标识符，C|标识符

C->标识符，C|标识符

B->ξ|WHERE D

D->I|IFD

I->G|GHI

H-> >|<|!|=

G->标识符

4)INSERT

INTO(表名)

VALLE(值|…)；

S4->INSERT INTO 标识符 VALLUE(A)

A->字符串，A|字符串

5)DELETE

FROM(表名)

WHERE子句

S5->E

E->DELETE FROM 标识符

WHERE D

D->I|IFD

I->G|GHI

H-> >|<|!|=

G->标识符

根据上面的构造产生式，然后依据SLR技术来构造分析表。

分析表的结构用一个数组表示，数组中的值为1～101时表示将要进行移进操作。如果分析表中的值为0，就表示在归约的过程中出现了错误，要进行相应的处理，此时为了不使语法分析的过程中断，在这里采用了忽略错误子句的处理方法，即如果遇到错误的句子就提示有语法错误，然后跳到分号后的句子继续进行归约。如果在分析表数组中遇到负数则执行相应的归约操作。

如果数组中的值为200～204，就表明此时已经归约成功了，就调用相应的数据库文件操作函数。

归约过程中要用到一个非常关键的手动构造的SLR表，用一个101行47列的数组来表示SLR表。表的结构如下所示(由于表的值是不允许改变的所以将它定义为const 类型)：

const int analyse_table[101][47]

{{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},

……

}; //手动构造的分析表；

具体归约的过程如图2所示，该模型的核心部分是一张分析表，这张分析表包括两部分：一部分是“动作”ACTION表，另一部分是状态转换表GOTO表。他们都是二维数组。ACTION[s,a]规定了当状态s面临输入符号a时应采取什么动作，GOTO[s,X]规定了状态s面临文法符号Xn(终结符号或非终结符) 时下一个状态是什么。该分析器的总控程序的任何一步操作只需依照栈顶状态和现在输入的符号a执行ACTION[s,a]所规定的动作。

该部分的入口参数是：从词法分析传来的words[MAXSIZE]结构体数组。

出口操作是：调用数据库操作函数用到的全体参数。

图2　SLR分析器模型

4系统用到的主要数据结构

1)word_num的作用是纪录词法分析过程遇到的单词数量。

2)words[MAXSIZE]用于记录在词法分析时所分析的单词信息、单词所处的行列和单词的属性。

struct word_type

{

charword_name[10];

intcol;

intline;

inttype;

}words[MAXSIZE];

3)操作数据库文件的参数结构，用一个结构体纪录，在调用CREATE, DROP,SELECT,INSERT,DELETE时，该结构体都是有效的。其中table_name用来纪录要操作表的名字，other_char用来纪录其余的标识符，在不同的调用中有不同的含义。compare[10]用于记录where子句中的比较符号如:>,<,=,!=; logic[10] 用于记录where子句中的逻辑符号AND OR；num用于记录接收标识符的个数;cmp_num用于记录接收比较值的个数。

struct param

{

chartable_name[10];//记录建立表的名字

charother_char[20][10];//记录在归约的过程中其他的标识符

int compare[10];//记录在归约过程中的比较符的值；

int logic[10] ;//用于接收逻辑符的值，AND与OR

int num;//用于记录接收标识符的个数

int cmp_num;//接收比较值的个数

};

4)语法分析类，刻画语法分析的过程，需要定义当前处理到了第几句话和当前已经读取的单词的个数。

classLexicalAnalysis

{

private:

int sentence;//记录当前归约到了第几句话

int ticket1;//标识当前已读单词的个数

int top;//栈顶指针

int stack[100][2];//栈；

struct guiyue_help r1,r2,r3,r4,r5,r6,r7,r8,r9,r10,r11,r12,r13,r14,r21,r22,r23,r31,r41,r42,r51,r52,r53,r54,r55,r56,r57,r58,r59,r60; //归约时结构体

struct param x;//在归约时记录参数的数组

public:

SyntaxAnalysis()//语法分析的构造函数

{

top=0;

sentence=1; //记录句子的值

//记录读入的单词标识

ticket1=0;

//对归约公式辅助值的初始化

r1.length=1; r1.type=39;

r2.length=3; r2.type=39;

r3.length=3; r3.type=41;

……

}

};

5数据库文件的创建或修改

该模块主要包括5个函数，分别完成创建数据表文件、删除数据表文件、查询数据记录、插入数据记录、删除数据记录的功能。这5个函数根据接收的参数对数据库dbf文件进行读写操作，这部分是按照dbf文件格式对文件进行操作。

FoxPro表文件由结构描述和数据记录两大部分组成。而结构描述部分又分为文件整体描述部分和字段描述部分。

文件整体描述部分共占32个字节，各字节意义如下：第1字节为数据库标志(03H)，若有Memo字段，此字段就是F5H。第2～4字节为最后一次修改的日期，格式是年、月、日。第5～8字节为记录个数。第9～10字节为结构描述部分的长度。第11～12字节为记录长度。第29字节是结构复合索引文件的标志，若建立了结构索引文件，该字节为1，否则为0。第13～32字节除29字节外都保留。

文件整体描述部分之后紧接着字段描述部分，每一个字段用32个字节描述其字段名、字段类型、字段宽度、小数位。字段描述部分各字节的意义为：第1～11字节为字段名。第12字节为字段的数据类型。第13～16字节表示内存地址。第17字节表示字段宽度。第18字节表示小数位数。第19、20字节为FoxPro网络专用。第21字节表示工作区。第24字节为SET FIELDS标志。其余字节保留。

库文件结构描述部分有一个终止标志(0D)，紧接此终止标志之后就是记录部分，记录部分按文本格式存放[3]。

按照以上格式，就可以对dbf文件进行读写操作。下面以创建为例介绍如何实现对dbf文件的操作。

void create(param x) //建立dbf文件的函数

首先按照文件整体描述的格式，用putc()函数和fprintf()函数一个字节一个字节地初始化前32个字节，紧接着进行初始化字段描述部分，在第12字节的时候统一规定字段的属性为字符型。其他字节按照FroxPro格式要求读写。

6结语

实践证明该系统可以实现对简单的SQL语句进行分析，并可以生成Foxpro2.6格式的文件。该系统可以作为编译原理教学时的实验范例，将复杂的编译原理和编程实践进行结合，提高编译原理课程的教学效果。

参考文献

[1] 魏乐. 一个简单语言编译器的设计与实现[J]. 成都信息工程学院学报,2007, 22(3): 312-316.

[2] 简聪海.高等C的解析[M].天津：天津大学出版社，1996.

[3] 姜灵敏.FoxPro2.6程序设计应用与技巧[M].北京：人民邮电出版社，1997.

The Design and Implementation of a SQL Compiler for Teaching

YUAN Ming-lei, etc.

(AnhuiVocationalCollegeofDefenseTechnology,LiuanAnhui221600,China)

Abstract：SQL provides a great convenience for the management of the database. At present, there is a number of excellent database management software, such as Oracal, Mysql, SQL, server, access, etc.. However, the development of database management software in China is slow, and there is not yet a commercial database management software by now. This shows that there is a problem of “emphasizing theory, neglecting practice” in computer education in China. In order to combine the computing theory and computing practice during teaching process, the design and implementation of a simple FoxPro database based SQL compiler are realized in this article. The compiler mainly has lexical analysis, syntax analysis, semantic specification, database file operations, and other functions.

Key words：lexical analysis; syntax analysis; statement specification

文献标志码：A

文章编号：1009-8984(2016)01-0114-05

中图分类号：TP311.131

作者简介：袁明磊(1985-)，男(汉)，江苏徐州，硕士，讲师

基金项目：安徽国防科技职业学院院级质量工程项目(gf2015ck03)

收稿日期：2015-11-16

doi:10.3969/j.issn.1009-8984.2016.01.026

主要研究计算机应用。