袁明磊,盛安元

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

?

一種用于教學(xué)的SQL編譯器設(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ā)進程緩慢，目前尚未出現(xiàn)一個商用的國產(chǎn)數(shù)據(jù)庫管理軟件。這說明國內(nèi)計算機教育方面存在“重理論，輕實踐”的問題。為了在教學(xué)中將編譯理論和編譯實踐相結(jié)合，設(shè)計并實現(xiàn)了一個簡化的基于FoxPro數(shù)據(jù)庫的SQL編譯器。該編譯器主要有詞法分析、語法分析、語義規(guī)約和數(shù)據(jù)庫文件操作等功能。

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

0引言

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

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

1總體設(shè)計

一個高級語言編譯器一般包括詞法分析、語法分析、語義分析、代碼生成、代碼優(yōu)化等過程。該編譯器主要完成的工作是將相應(yīng)的SQL語句進行詞法分析、語法分析、語義分析，然后根據(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詞法分析的實現(xiàn)過程

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

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

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

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

該編譯器的運算符和含義如表3所示。

表3　類FoxPro2.6的SQL編譯器的運算符和含義表

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

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

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

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

C->A(A|B)*。

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

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

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

3語法分析

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

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

S->E:

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

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

2)DROPTANBLE <表名>

S2->E

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

3)SELECT *|(列名，…)

FROM (表名)

WHERE子句AND|OR子句…

S3->E

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

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

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

B->ξ|WHERE D

D->I|IFD

I->G|GHI

H-> >|<|!|=

G->標(biāo)識符

4)INSERT

INTO(表名)

VALLE(值|…)；

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

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

5)DELETE

FROM(表名)

WHERE子句

S5->E

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

WHERE D

D->I|IFD

I->G|GHI

H-> >|<|!|=

G->標(biāo)識符

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

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

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

歸約過程中要用到一個非常關(guān)鍵的手動構(gòu)造的SLR表，用一個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},

……

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

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

該部分的入口參數(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]用于記錄在詞法分析時所分析的單詞信息、單詞所處的行列和單詞的屬性。

struct word_type

{

charword_name[10];

intcol;

intline;

inttype;

}words[MAXSIZE];

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

struct param

{

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

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

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

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

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

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

};

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

classLexicalAnalysis

{

private:

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

int ticket1;//標(biāo)識當(dāng)前已讀單詞的個數(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; //歸約時結(jié)構(gòu)體

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

public:

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

{

top=0;

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

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

ticket1=0;

//對歸約公式輔助值的初始化

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

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

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

……

}

};

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

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

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

文件整體描述部分共占32個字節(jié)，各字節(jié)意義如下：第1字節(jié)為數(shù)據(jù)庫標(biāo)志(03H)，若有Memo字段，此字段就是F5H。第2～4字節(jié)為最后一次修改的日期，格式是年、月、日。第5～8字節(jié)為記錄個數(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é)外都保留。

文件整體描述部分之后緊接著字段描述部分，每一個字段用32個字節(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)描述部分有一個終止標(biāo)志(0D)，緊接此終止標(biāo)志之后就是記錄部分，記錄部分按文本格式存放[3]。

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

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

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

6結(jié)語

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

參考文獻

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

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

[3] 姜靈敏.FoxPro2.6程序設(shè)計應(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

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

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

中圖分類號：TP311.131

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

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

收稿日期：2015-11-16

doi:10.3969/j.issn.1009-8984.2016.01.026

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