一種用于教學(xué)的SQL編譯器設(shè)計(jì)與實(shí)現(xiàn)

袁明磊,盛安元

(1.安徽國防科技職業(yè)學(xué)院，安徽 六安 221600； 2.六安大江信息技術(shù)有限公司，安徽 六安 221600)

?

一種用于教學(xué)的SQL編譯器設(shè)計(jì)與實(shí)現(xiàn)

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

(1.安徽國防科技職業(yè)學(xué)院，安徽 六安 221600； 2.六安大江信息技術(shù)有限公司，安徽 六安 221600)

摘要：SQL為數(shù)據(jù)庫的管理提供了極大的方便。目前已有一批優(yōu)秀的數(shù)據(jù)庫管理軟件，如Oracal、Mysql、SQL server、Access等，然而國內(nèi)數(shù)據(jù)庫管理軟件開發(fā)進(jìn)程緩慢，目前尚未出現(xiàn)一個(gè)商用的國產(chǎn)數(shù)據(jù)庫管理軟件。這說明國內(nèi)計(jì)算機(jī)教育方面存在“重理論，輕實(shí)踐”的問題。為了在教學(xué)中將編譯理論和編譯實(shí)踐相結(jié)合，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)簡化的基于FoxPro數(shù)據(jù)庫的SQL編譯器。該編譯器主要有詞法分析、語法分析、語義規(guī)約和數(shù)據(jù)庫文件操作等功能。

關(guān)鍵詞：詞法分析；語法分析；語句規(guī)約

0引言

1954年，IBM的John Backus帶領(lǐng)一批研究人員完成了世界上第一個(gè)編譯器的開發(fā)，將其命名為FORTRAN語言編譯器。在同一時(shí)期，Noam Chomsky也對(duì)自然語言的結(jié)構(gòu)進(jìn)行了研究，他將文法分為4類：0型文法、1型文法、2型文法和3型文法，最終使得編譯器的結(jié)構(gòu)異常簡單。目前對(duì)編譯器的研究主要集中在面向?qū)ο缶幾g、并行編譯、自動(dòng)編譯等技術(shù)方面。在編譯技術(shù)的發(fā)展過程中，國內(nèi)對(duì)編譯技術(shù)的研究處于一個(gè)較為落后的階段，我國尚未有一個(gè)較為成熟的編譯器產(chǎn)品出現(xiàn)[1]。本文主要探討一個(gè)基于FoxPro2.6文件格式的簡化的SQL編譯器的實(shí)現(xiàn)過程，本產(chǎn)品只是一個(gè)用于教學(xué)的實(shí)驗(yàn)產(chǎn)品，重點(diǎn)用來說明編譯器的基本原理。

FoxPro原名FoxBase，是美國Fox Software公司推出的數(shù)據(jù)庫產(chǎn)品，可在DOS上運(yùn)行，與xBase系列相容，最高版本為2.6。Fox Software被微軟收購后，加以發(fā)展, 使其可以在 Windows 上運(yùn)行, 并且更名為 Visual FoxPro[2]。

1總體設(shè)計(jì)

一個(gè)高級(jí)語言編譯器一般包括詞法分析、語法分析、語義分析、代碼生成、代碼優(yōu)化等過程。該編譯器主要完成的工作是將相應(yīng)的SQL語句進(jìn)行詞法分析、語法分析、語義分析，然后根據(jù)語義完成數(shù)據(jù)庫文件的創(chuàng)建或修改。

該編譯器支持以下5種語法：1)創(chuàng)建數(shù)據(jù)表： CTEATE TABLE 數(shù)據(jù)表名 (字段列表)；2)刪除數(shù)據(jù)表：DROP TABLE 數(shù)據(jù)表名；3)向數(shù)據(jù)表插入數(shù)據(jù)：INSERT INTO 數(shù)據(jù)表名 VALUE (字段值列表)；4)查詢數(shù)據(jù)：SELECT 字段列表 FROM 數(shù)據(jù)表名 WHERE 查詢條件 ；5)刪除數(shù)據(jù)表記錄信息：DELETE FROM (數(shù)據(jù)表名) WHERE 查詢條件。該編譯器的工作流程如圖1所示。

圖1　基于FoxPro2.6的SQL編譯器工作流程圖

2詞法分析的實(shí)現(xiàn)過程

詞法分析的主要作用是按照詞法分析的規(guī)則，對(duì)讀入的字符串進(jìn)行第一階段的掃描，將字符串轉(zhuǎn)化為單詞屬性字的過程。最終將字符流轉(zhuǎn)化為詞法記號(hào)流。這個(gè)編譯器的關(guān)鍵字見表1。

表1　類FoxPro2.6的SQL編譯器關(guān)鍵字

該編譯器的界符和含義見表2所示。

表2　類FoxPro2.6的SQL編譯器的界符

該編譯器的運(yùn)算符和含義如表3所示。

表3　類FoxPro2.6的SQL編譯器的運(yùn)算符和含義表

該系統(tǒng)的常量主要有： 整數(shù)和字符串類型的常量。

系統(tǒng)的標(biāo)識(shí)符要符合如下規(guī)則：

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

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

C->A(A|B)*。

系統(tǒng)實(shí)現(xiàn)時(shí)，使用<詞法記號(hào), 屬性>這個(gè)二元組來描述一個(gè)詞法單元。該編譯器的詞法單元見表4所示。

詞法分析的過程下：1)首先讀取待編譯的文本文件；2)將文件讀取到Buf[MAXSIZE]數(shù)組內(nèi)；3)查找開始符“{”，“{”之前的所有內(nèi)容均為無效內(nèi)容，如果整個(gè)文本均無“{”則報(bào)錯(cuò)：“沒有開始符” ；4)依次取字符串，并判斷字符串的屬性值，記錄<詞法記號(hào),屬性>二元組到words[MAXSIZE]數(shù)組內(nèi)；5)記錄不合法的字符串，并將其記錄到一個(gè)錯(cuò)誤詞法記號(hào)數(shù)組內(nèi)；6)找到“}”，詞法分析結(jié)束。詞法分析完成后得到一個(gè)<詞法記號(hào), 屬性>二元組隊(duì)列。該隊(duì)列為語法分析提供基礎(chǔ)數(shù)據(jù)。

表4　類FoxPro2.6的SQL編譯器的詞法單元表

3語法分析

該系統(tǒng)的語法分析部分主要對(duì)5種語法的子句進(jìn)行分析,分析結(jié)果如下：

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

S->E:

E->CREATE TABLE 標(biāo)識(shí)符(A)

A->標(biāo)識(shí)符，A | ξ

2)DROPTANBLE <表名>

S2->E

E->DROPTABLE 標(biāo)識(shí)符

3)SELECT *|(列名，…)

FROM (表名)

WHERE子句AND|OR子句…

S3->E

E->SELECT A FROM 標(biāo)識(shí)符 B

A->*|標(biāo)識(shí)符，C|標(biāo)識(shí)符

C->標(biāo)識(shí)符，C|標(biāo)識(shí)符

B->ξ|WHERE D

D->I|IFD

I->G|GHI

H-> >|<|!|=

G->標(biāo)識(shí)符

4)INSERT

INTO(表名)

VALLE(值|…)；

S4->INSERT INTO 標(biāo)識(shí)符 VALLUE(A)

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

5)DELETE

FROM(表名)

WHERE子句

S5->E

E->DELETE FROM 標(biāo)識(shí)符

WHERE D

D->I|IFD

I->G|GHI

H-> >|<|!|=

G->標(biāo)識(shí)符

根據(jù)上面的構(gòu)造產(chǎn)生式，然后依據(jù)SLR技術(shù)來構(gòu)造分析表。

分析表的結(jié)構(gòu)用一個(gè)數(shù)組表示，數(shù)組中的值為1～101時(shí)表示將要進(jìn)行移進(jìn)操作。如果分析表中的值為0，就表示在歸約的過程中出現(xiàn)了錯(cuò)誤，要進(jìn)行相應(yīng)的處理，此時(shí)為了不使語法分析的過程中斷，在這里采用了忽略錯(cuò)誤子句的處理方法，即如果遇到錯(cuò)誤的句子就提示有語法錯(cuò)誤，然后跳到分號(hào)后的句子繼續(xù)進(jìn)行歸約。如果在分析表數(shù)組中遇到負(fù)數(shù)則執(zhí)行相應(yīng)的歸約操作。

如果數(shù)組中的值為200～204，就表明此時(shí)已經(jīng)歸約成功了，就調(diào)用相應(yīng)的數(shù)據(jù)庫文件操作函數(shù)。

歸約過程中要用到一個(gè)非常關(guān)鍵的手動(dòng)構(gòu)造的SLR表，用一個(gè)101行47列的數(shù)組來表示SLR表。表的結(jié)構(gòu)如下所示(由于表的值是不允許改變的所以將它定義為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},

……

}; //手動(dòng)構(gòu)造的分析表；

具體歸約的過程如圖2所示，該模型的核心部分是一張分析表，這張分析表包括兩部分：一部分是“動(dòng)作”ACTION表，另一部分是狀態(tài)轉(zhuǎn)換表GOTO表。他們都是二維數(shù)組。ACTION[s,a]規(guī)定了當(dāng)狀態(tài)s面臨輸入符號(hào)a時(shí)應(yīng)采取什么動(dòng)作，GOTO[s,X]規(guī)定了狀態(tài)s面臨文法符號(hào)Xn(終結(jié)符號(hào)或非終結(jié)符) 時(shí)下一個(gè)狀態(tài)是什么。該分析器的總控程序的任何一步操作只需依照棧頂狀態(tài)和現(xiàn)在輸入的符號(hào)a執(zhí)行ACTION[s,a]所規(guī)定的動(dòng)作。

該部分的入口參數(shù)是：從詞法分析傳來的words[MAXSIZE]結(jié)構(gòu)體數(shù)組。

出口操作是：調(diào)用數(shù)據(jù)庫操作函數(shù)用到的全體參數(shù)。

圖2　SLR分析器模型

4系統(tǒng)用到的主要數(shù)據(jù)結(jié)構(gòu)

1)word_num的作用是紀(jì)錄詞法分析過程遇到的單詞數(shù)量。

2)words[MAXSIZE]用于記錄在詞法分析時(shí)所分析的單詞信息、單詞所處的行列和單詞的屬性。

struct word_type

{

charword_name[10];

intcol;

intline;

inttype;

}words[MAXSIZE];

3)操作數(shù)據(jù)庫文件的參數(shù)結(jié)構(gòu)，用一個(gè)結(jié)構(gòu)體紀(jì)錄，在調(diào)用CREATE, DROP,SELECT,INSERT,DELETE時(shí)，該結(jié)構(gòu)體都是有效的。其中table_name用來紀(jì)錄要操作表的名字，other_char用來紀(jì)錄其余的標(biāo)識(shí)符，在不同的調(diào)用中有不同的含義。compare[10]用于記錄where子句中的比較符號(hào)如:>,<,=,!=; logic[10] 用于記錄where子句中的邏輯符號(hào)AND OR；num用于記錄接收標(biāo)識(shí)符的個(gè)數(shù);cmp_num用于記錄接收比較值的個(gè)數(shù)。

struct param

{

chartable_name[10];//記錄建立表的名字

charother_char[20][10];//記錄在歸約的過程中其他的標(biāo)識(shí)符

int compare[10];//記錄在歸約過程中的比較符的值；

int logic[10] ;//用于接收邏輯符的值，AND與OR

int num;//用于記錄接收標(biāo)識(shí)符的個(gè)數(shù)

int cmp_num;//接收比較值的個(gè)數(shù)

};

4)語法分析類，刻畫語法分析的過程，需要定義當(dāng)前處理到了第幾句話和當(dāng)前已經(jīng)讀取的單詞的個(gè)數(shù)。

classLexicalAnalysis

{

private:

int sentence;//記錄當(dāng)前歸約到了第幾句話

int ticket1;//標(biāo)識(shí)當(dāng)前已讀單詞的個(gè)數(shù)

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; //歸約時(shí)結(jié)構(gòu)體

struct param x;//在歸約時(shí)記錄參數(shù)的數(shù)組

public:

SyntaxAnalysis()//語法分析的構(gòu)造函數(shù)

{

top=0;

sentence=1; //記錄句子的值

//記錄讀入的單詞標(biāo)識(shí)

ticket1=0;

//對(duì)歸約公式輔助值的初始化

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

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

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

……

}

};

5數(shù)據(jù)庫文件的創(chuàng)建或修改

該模塊主要包括5個(gè)函數(shù)，分別完成創(chuàng)建數(shù)據(jù)表文件、刪除數(shù)據(jù)表文件、查詢數(shù)據(jù)記錄、插入數(shù)據(jù)記錄、刪除數(shù)據(jù)記錄的功能。這5個(gè)函數(shù)根據(jù)接收的參數(shù)對(duì)數(shù)據(jù)庫dbf文件進(jìn)行讀寫操作，這部分是按照dbf文件格式對(duì)文件進(jìn)行操作。

FoxPro表文件由結(jié)構(gòu)描述和數(shù)據(jù)記錄兩大部分組成。而結(jié)構(gòu)描述部分又分為文件整體描述部分和字段描述部分。

文件整體描述部分共占32個(gè)字節(jié)，各字節(jié)意義如下：第1字節(jié)為數(shù)據(jù)庫標(biāo)志(03H)，若有Memo字段，此字段就是F5H。第2～4字節(jié)為最后一次修改的日期，格式是年、月、日。第5～8字節(jié)為記錄個(gè)數(shù)。第9～10字節(jié)為結(jié)構(gòu)描述部分的長度。第11～12字節(jié)為記錄長度。第29字節(jié)是結(jié)構(gòu)復(fù)合索引文件的標(biāo)志，若建立了結(jié)構(gòu)索引文件，該字節(jié)為1，否則為0。第13～32字節(jié)除29字節(jié)外都保留。

文件整體描述部分之后緊接著字段描述部分，每一個(gè)字段用32個(gè)字節(jié)描述其字段名、字段類型、字段寬度、小數(shù)位。字段描述部分各字節(jié)的意義為：第1～11字節(jié)為字段名。第12字節(jié)為字段的數(shù)據(jù)類型。第13～16字節(jié)表示內(nèi)存地址。第17字節(jié)表示字段寬度。第18字節(jié)表示小數(shù)位數(shù)。第19、20字節(jié)為FoxPro網(wǎng)絡(luò)專用。第21字節(jié)表示工作區(qū)。第24字節(jié)為SET FIELDS標(biāo)志。其余字節(jié)保留。

庫文件結(jié)構(gòu)描述部分有一個(gè)終止標(biāo)志(0D)，緊接此終止標(biāo)志之后就是記錄部分，記錄部分按文本格式存放[3]。

按照以上格式，就可以對(duì)dbf文件進(jìn)行讀寫操作。下面以創(chuàng)建為例介紹如何實(shí)現(xiàn)對(duì)dbf文件的操作。

void create(param x) //建立dbf文件的函數(shù)

首先按照文件整體描述的格式，用putc()函數(shù)和fprintf()函數(shù)一個(gè)字節(jié)一個(gè)字節(jié)地初始化前32個(gè)字節(jié)，緊接著進(jìn)行初始化字段描述部分，在第12字節(jié)的時(shí)候統(tǒng)一規(guī)定字段的屬性為字符型。其他字節(jié)按照FroxPro格式要求讀寫。

6結(jié)語

實(shí)踐證明該系統(tǒng)可以實(shí)現(xiàn)對(duì)簡單的SQL語句進(jìn)行分析，并可以生成Foxpro2.6格式的文件。該系統(tǒng)可以作為編譯原理教學(xué)時(shí)的實(shí)驗(yàn)范例，將復(fù)雜的編譯原理和編程實(shí)踐進(jìn)行結(jié)合，提高編譯原理課程的教學(xué)效果。

參考文獻(xiàn)

[1] 魏樂. 一個(gè)簡單語言編譯器的設(shè)計(jì)與實(shí)現(xiàn)[J]. 成都信息工程學(xué)院學(xué)報(bào),2007, 22(3): 312-316.

[2] 簡聰海.高等C的解析[M].天津：天津大學(xué)出版社，1996.

[3] 姜靈敏.FoxPro2.6程序設(shè)計(jì)應(yīng)用與技巧[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

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1009-8984(2016)01-0114-05

中圖分類號(hào)：TP311.131

作者簡介：袁明磊(1985-)，男(漢)，江蘇徐州，碩士，講師

基金項(xiàng)目：安徽國防科技職業(yè)學(xué)院院級(jí)質(zhì)量工程項(xiàng)目(gf2015ck03)

收稿日期：2015-11-16

doi:10.3969/j.issn.1009-8984.2016.01.026

主要研究計(jì)算機(jī)應(yīng)用。