面向數(shù)據(jù)庫(kù)性能的SQL語(yǔ)句解析與翻譯

摘 要： 信息泄漏事件不斷發(fā)生使得數(shù)據(jù)庫(kù)安全的重要性不斷提高?；赟QL解析能夠?qū)崿F(xiàn)SQL到自然語(yǔ)言的翻譯，幫助非專(zhuān)業(yè)人員分析數(shù)據(jù)庫(kù)的訪問(wèn)活動(dòng)和識(shí)別風(fēng)險(xiǎn)。通過(guò)SQL詞法和語(yǔ)法的EBNF描述構(gòu)造了可以用于LL的規(guī)則輸入，使用ANTLR工具生成了SQL詞法和語(yǔ)法解析器。進(jìn)一步，SQL詞法和語(yǔ)法解析器實(shí)現(xiàn)了SQL語(yǔ)句到抽象語(yǔ)法樹(shù)的轉(zhuǎn)換。并通過(guò)解析抽象語(yǔ)法樹(shù)，將SQL語(yǔ)句翻譯成自然語(yǔ)言。最后，將SQL解析和翻譯功能應(yīng)用在數(shù)據(jù)庫(kù)防火墻和安全審計(jì)系統(tǒng)中。

關(guān)鍵詞： SQL解析； LL解析器； ANTLR； 抽象語(yǔ)法樹(shù)； SQL翻譯； 數(shù)據(jù)庫(kù)安全

中圖分類(lèi)號(hào)： TN918.91?34； TM417 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）11?0099?04

Abstract： The continuous occurrence of information leakage incidents makes the importance of database security improve constantly. The SQL parse can realize the translation from SQL to natural language， and help the non?specialized people to analyze the database access activities and identify the risks. The rule input applied to LL was constructed by means of EBNF description of SQL morphology and syntax. The SQL morphology and parser are generated with ANTLR tool， which can realize the conversion from SQL statement to abstract syntax tree. The SQL statement can be translated into natural language by parsing the abstract syntax tree. Finally， SQL parse and translation function are applied to the database firewall and safety audit system.

Keywords： SQL parse； LL parser； ANTLR； abstract syntax tree； SQL translation； database security

0 引 言

近幾年，信息泄漏事件頻繁發(fā)生，用戶對(duì)數(shù)據(jù)庫(kù)的安全性越來(lái)越關(guān)注。由于數(shù)據(jù)庫(kù)本身的復(fù)雜性，數(shù)據(jù)庫(kù)的管理運(yùn)行、日常維護(hù)和數(shù)據(jù)安全保護(hù)只能由專(zhuān)業(yè)的數(shù)據(jù)庫(kù)管理員進(jìn)行。但是，很多使用數(shù)據(jù)庫(kù)的人并不熟悉數(shù)據(jù)庫(kù)，甚至完全不了解數(shù)據(jù)庫(kù)。SQL分析技術(shù)能夠幫助用戶快速抽取SQL語(yǔ)句中的字段、表、視圖及對(duì)它們的操作，快速識(shí)別SQL語(yǔ)句的風(fēng)險(xiǎn)。同時(shí)基于SQL分析技術(shù)能夠?qū)QL語(yǔ)句翻譯成自然語(yǔ)言，使之更容易被理解，有助于實(shí)現(xiàn)安全控制。

早期的SQL解析使用Lex，Yacc的比較多。雖然Oracle已經(jīng)將ANTLR應(yīng)用在SQL Developer的IDE中，但是SQL Developer并非開(kāi)源使用。因此使用ANTLR進(jìn)行SQL解析的研究目前還很少，進(jìn)行SQL翻譯的工作還未見(jiàn)報(bào)道。在使用ANTLR解析SQL并且將結(jié)果進(jìn)行進(jìn)一步分析是一個(gè)新的嘗試。本文針對(duì)數(shù)據(jù)庫(kù)安全，基于LL文法，采用ANTLR工具，實(shí)現(xiàn)了SQL的詞法和語(yǔ)法解析器，并進(jìn)一步實(shí)現(xiàn)了SQL語(yǔ)句到自然語(yǔ)言的翻譯。最后，將SQL解析和翻譯功能應(yīng)用在數(shù)據(jù)庫(kù)防火墻和安全審計(jì)系統(tǒng)中，對(duì)于提高數(shù)據(jù)庫(kù)的安全防護(hù)能力具有很大的實(shí)際意義。

1 SQL解析器

1.1 SQL詞法解析器實(shí)現(xiàn)

SQL語(yǔ)言的詞法主要分為標(biāo)識(shí)符、數(shù)字、注釋與提示、字符串、時(shí)間、區(qū)間和變量?；贏NTLR實(shí)現(xiàn)SQL詞法解析首先要定義詞法的fragment。所謂的fragment是詞的一部分，而不會(huì)出現(xiàn)在詞法解析的結(jié)果中。以數(shù)字和時(shí)間為例分析。

（1） 數(shù)字Number。在SQL語(yǔ)言中表示數(shù)值類(lèi)型。數(shù)值類(lèi)型包含整數(shù)部分、小數(shù)部分、符號(hào)部分、指數(shù)部分和類(lèi)型部分，其中指數(shù)部分是一個(gè)大寫(xiě)字母“E”或者一個(gè)小寫(xiě)字母“e”加一個(gè)帶有符號(hào)的整數(shù)，如果不帶符號(hào)默認(rèn)為“+”。數(shù)值類(lèi)型中，整數(shù)部分和小數(shù)部分必須包含其中之一，其他部分都是可選的，只包含小數(shù)部分時(shí)允許“.”出現(xiàn)在數(shù)值的最前面，例如“.5”表示“0.5”。數(shù)字的DFA表示如圖1所示。

（2） 時(shí)間Datetime。時(shí)間格式比較固定，必須由關(guān)鍵字DATE開(kāi)頭，后面是一個(gè)表示時(shí)間的字符串，如果不是表示時(shí)間的字符串，SQL語(yǔ)句認(rèn)為是錯(cuò)誤的語(yǔ)句。另外，時(shí)間戳也被認(rèn)為是一種時(shí)間格式，必須是由關(guān)鍵字TIMESTAMP開(kāi)頭，時(shí)間戳格式包含AT TIME ZONE可選結(jié)構(gòu)，表示時(shí)區(qū)。時(shí)間的DFA表示如圖2所示。

根據(jù)這七種類(lèi)型的自動(dòng)機(jī)表示將其轉(zhuǎn)換成對(duì)應(yīng)的EBNF表示。使用“*”、“+”替換DFA中的循環(huán)結(jié)構(gòu)，“*”表示可以跳過(guò)的循環(huán)結(jié)構(gòu)，“+”表示不可跳過(guò)的循環(huán)結(jié)構(gòu)。使用“|”表示DFA中的選擇結(jié)構(gòu)，在每個(gè)分支之間使用“|”表示選擇。使用“？”表示DFA中可跳過(guò)的結(jié)構(gòu)，將“？”放在可選結(jié)構(gòu)的后面。在每個(gè)單元上使用“（）”將不可拆分的部分包含在內(nèi)，就可以使用簡(jiǎn)單的EBNF語(yǔ)句描述復(fù)雜的DFA。另外，對(duì)于SQL的保留字要做單獨(dú)的識(shí)別。例如：select要定義成SELECT：S E L E C T；這樣select無(wú)論是“Select”還是“seLECT”都能識(shí)別出來(lái)。針對(duì)不同的SQL語(yǔ)句它的保留字也是不一樣的，需要單獨(dú)定義語(yǔ)法文件。 SQL語(yǔ)言中是不區(qū)分大寫(xiě)字母和小寫(xiě)字母的，在ANTLR中單獨(dú)的字母應(yīng)該被當(dāng)作碎片來(lái)定義，不能出現(xiàn)在最終的解析結(jié)果中，使用“fragment”修飾。字母包含鍵盤(pán)上所有能夠輸入的符號(hào)以及鍵盤(pán)上不能直接輸入的UNICODE字符。SQL語(yǔ)言中使用的數(shù)字是阿拉伯?dāng)?shù)字0～9，單獨(dú)的數(shù)字也要使用“fragment”修飾。

1.2 SQL語(yǔ)法解析器實(shí)現(xiàn)

語(yǔ)法解析器實(shí)現(xiàn)過(guò)程中需要將所有的語(yǔ)言模式轉(zhuǎn)化為EBNF描述的規(guī)則語(yǔ)句。SQL語(yǔ)言的范式使用的是EBNF描述，要將其轉(zhuǎn)換成EBNF描述的規(guī)則。EBNF范式的好壞雖然不會(huì)影響到解析的效率，解析效率只與被解析的字符串的長(zhǎng)度有關(guān)系，但是會(huì)影響到解析器生成的效率。壞的EBNF規(guī)則會(huì)導(dǎo)致生成的過(guò)程中出現(xiàn)大量的遞歸調(diào)用和棧操作，生成的時(shí)間和內(nèi)存會(huì)成指數(shù)級(jí)增長(zhǎng)。所以EBNF的規(guī)則還是有很多細(xì)節(jié)需要注意。規(guī)則的深度不能太深，并且需要或關(guān)系的規(guī)則盡量將K值控制到最低，因?yàn)橐?guī)則生成的復(fù)雜度是（K*N）M。其中，K是向后查看的token數(shù)；N是或關(guān)系連接的多個(gè)規(guī)則；M是規(guī)則嵌套的層數(shù)。由于一個(gè)子規(guī)則經(jīng)常被多個(gè)規(guī)則引用，所以子規(guī)則會(huì)影響所有引用它的規(guī)則的生成效率。降低子規(guī)則的層數(shù)和減小K值是有效的提高生成效率的方法。N值一般難以降低，除非規(guī)則本身就有冗余，但是這種情況比較少見(jiàn)。

使用ANTLR將語(yǔ)法文件編譯成解析器，實(shí)現(xiàn)過(guò)程類(lèi)似于詞法分析。輸入由String變成tokens，ANTLR自身的語(yǔ)法不變。使用全部的語(yǔ)法生成語(yǔ)法解析器，在生成過(guò)程中系統(tǒng)采用LL（K）分析方法。ANTLR支持預(yù)測(cè)功能，可以在特定的地方使用預(yù)測(cè)。設(shè)置回溯位置，對(duì)輸入的tokens進(jìn)行預(yù)測(cè)，降低解析時(shí)間和消耗的資源。 解析的結(jié)果可以得到每一個(gè)token的屬性、內(nèi)容和值。再對(duì)生成的一維AST樹(shù)做遞歸下降，將AST樹(shù)的二維層次結(jié)構(gòu)補(bǔ)全，得到具有層次和附屬關(guān)系的二維語(yǔ)法樹(shù)。AST樹(shù)上的節(jié)點(diǎn)對(duì)于解析來(lái)說(shuō)并不都是必須的，在生成過(guò)程中將不需要的節(jié)點(diǎn)刪除，留下必須的結(jié)果，精簡(jiǎn)AST樹(shù)對(duì)于快速提取重要信息有很大的幫助。在AST樹(shù)生成的過(guò)程中直接嵌入SQL語(yǔ)句檢查代碼，同時(shí)可以在解析過(guò)程中直接根據(jù)token的類(lèi)型判斷輸入詞的意義，從而將SQL中最重要的表、視圖、字段直接提取出來(lái)，同時(shí)判斷出SQL的類(lèi)型和操作對(duì)象的類(lèi)型。更進(jìn)一步，將SQL中存在的安全隱患的類(lèi)似緩沖區(qū)溢出和SQL注入攻擊的風(fēng)險(xiǎn)直接檢測(cè)出來(lái)。

2 SQL翻譯

2.1 SQL語(yǔ)句AST的構(gòu)建

ANTLR語(yǔ)法解析的輸出結(jié)果就是抽象語(yǔ)法樹(shù)。將語(yǔ)法解析的結(jié)果設(shè)置為AST，ANTLR每一個(gè)規(guī)則解析之后就能生成AST結(jié)構(gòu)。默認(rèn)情況下生成一維語(yǔ)法樹(shù)，所有的結(jié)果在同一個(gè)層次上。如果需要自定義抽象語(yǔ)法樹(shù)的返回結(jié)果，需要在語(yǔ)法解析過(guò)程中加入AST 構(gòu)建規(guī)則。ANTLR的抽象語(yǔ)法樹(shù)構(gòu)建語(yǔ)法非常簡(jiǎn)單，標(biāo)準(zhǔn)語(yǔ)法只有三種：

（1） “^”，前面的符號(hào)作為父節(jié)點(diǎn)；

（2） “！”，前面的節(jié)點(diǎn)不出現(xiàn)在語(yǔ)法樹(shù)上；

（3） “?>^（……）”，“?>”左側(cè)是語(yǔ)法解析語(yǔ)句，右側(cè)是抽象語(yǔ)法樹(shù)生成語(yǔ)句，括號(hào)內(nèi)是一棵子樹(shù)，第一個(gè)符號(hào)是樹(shù)的根，其他元素是第一個(gè)元素的子節(jié)點(diǎn)。例如：（A+B）?> ^（+A B）。

由于SQL語(yǔ)言是結(jié)構(gòu)化的查詢語(yǔ)句，在構(gòu)建抽象語(yǔ)法樹(shù)上有先天的優(yōu)勢(shì)。構(gòu)建語(yǔ)法樹(shù)時(shí)只需要考慮SQL中查詢的主體，忽略不需要的部分，其中最重要的就是表、字段、視圖和在表、字段、視圖上的操作。查詢語(yǔ)句是SQL語(yǔ)句中最復(fù)雜的語(yǔ)句，可以使用嵌套和遞歸的方式，語(yǔ)法結(jié)構(gòu)十分靈活。由于其他語(yǔ)言相比于查詢語(yǔ)言簡(jiǎn)單很多。本節(jié)用查詢語(yǔ)句舉例說(shuō)明SQL語(yǔ)句抽象語(yǔ)法樹(shù)生成過(guò)程。

2.2 AST轉(zhuǎn)換成自然語(yǔ)言

SQL語(yǔ)句的語(yǔ)言結(jié)構(gòu)更接近英文的語(yǔ)言結(jié)構(gòu)，與中文的語(yǔ)言結(jié)構(gòu)差別較大，簡(jiǎn)單的對(duì)關(guān)鍵字替換不考慮語(yǔ)義是不能達(dá)到翻譯效果的，只會(huì)讓結(jié)果更加匪夷所思，舉例說(shuō)明：

SELECT concat（select user （），′??′，database（））， name FROM TABLE（SELECT date， user， action， name FROM logs WHERE id=if（ascii（substr（（SELECT user（））），1，1）=1），1，0）） WHERE ‘a(chǎn)dmin’in （SELECT name FROM user）；

直接替換翻譯結(jié)果為：

查詢concat（查詢user （），′??′， database （））， name從邏輯表（查詢date， user， action， name從logs條件滿足id等于if（ascii（substr（（查詢user（）），1，1））等于1，1，0）條件滿足‘a(chǎn)dmin’在（查詢name從user）。

使用樹(shù)解析器將抽象語(yǔ)法樹(shù)轉(zhuǎn)換成自然語(yǔ)言。由于抽象語(yǔ)法樹(shù)采用遞歸的方式表示語(yǔ)法結(jié)構(gòu)，在解析的過(guò)程中也使用遞歸的方式，并將語(yǔ)法習(xí)慣調(diào)整為漢語(yǔ)語(yǔ)言的語(yǔ)法習(xí)慣。在轉(zhuǎn)換的過(guò)程中補(bǔ)充虛詞和連接詞，增加語(yǔ)言的連貫性。最后對(duì)翻譯結(jié)果進(jìn)行格式化，增加縮進(jìn)便于閱讀。考慮漢語(yǔ)的閱讀習(xí)慣，可以將較長(zhǎng)的句子翻譯成子句的形式，最后，根據(jù)數(shù)據(jù)庫(kù)建模表和數(shù)據(jù)庫(kù)方法表，可以將翻譯結(jié)果中的方法名、字段名、表名等翻譯成中文，翻譯時(shí)只要判斷出被翻譯內(nèi)容的類(lèi)型，然后查找相應(yīng)的數(shù)據(jù)表，就能將剩下的英文部分翻譯成中文，生成最終結(jié)果為：

模塊1：

查詢獲取用戶方法（user）的執(zhí)行結(jié)果的返回?cái)?shù)據(jù)

模塊2：

從用戶表（user）中查詢姓名字段（name）的返回?cái)?shù)據(jù)

條件1：

標(biāo)識(shí)字段（id）等于條件判斷方法（if）[轉(zhuǎn)換成ascii編碼方法（ascii）[子串方法（substr）[{模塊1}，1，1]的返回結(jié)果]]的返回結(jié)果等于1，1，0]的返回結(jié)果

條件2：

字串‘a(chǎn)dmin’在[{模塊2}]里

模塊3：

從日志表（logs）中查詢滿足{條件1}條件的日期字段（date）和用戶字段（user）和動(dòng)作字段（action）和姓名字段（name）的返回?cái)?shù)據(jù)

模塊4：

邏輯表[{模塊3}]

模塊5：

查詢方法用戶方法（user）執(zhí)行結(jié)果的返回?cái)?shù)據(jù)

模塊6：

連接字符串方法（concat）[{模塊5}， ′??′， 方法數(shù)據(jù)（database）的執(zhí)行結(jié)果]的執(zhí)行結(jié)果

主查詢：

從{模塊4}中查詢滿足{條件2}條件的{模塊6}和姓名字段（name）的返回?cái)?shù)據(jù)。

翻譯過(guò)程中需要調(diào)整語(yǔ)序，語(yǔ)序的調(diào)整主要使用棧實(shí)現(xiàn)，將需要調(diào)整語(yǔ)序的句子放入棧中，返回時(shí)再?gòu)臈Ｖ腥〕?。?shù)解析器翻譯的過(guò)程如下：

（1） 當(dāng)前指針在根節(jié)點(diǎn)，獲取節(jié)點(diǎn)，判斷節(jié)點(diǎn)類(lèi)型，類(lèi)型不一樣，Tree Walker進(jìn)入不同的解析模塊，這里以SELECT語(yǔ)句為例；

（2） 獲取一個(gè)子節(jié)點(diǎn)，判斷節(jié)點(diǎn)的類(lèi)型；

（3） 如果是SELECT語(yǔ)句，那么就調(diào)用select_tree_walker，然后調(diào)整語(yǔ)序，執(zhí)行stack.push操作，將結(jié)果先緩存。如果是FROM語(yǔ)句，調(diào)用from_tree_walker的結(jié)果放入output流中。如果是WHERE語(yǔ)句，調(diào)用where_tree_walker，調(diào)用stack.pop將SELECT語(yǔ)句出棧，和WHERE語(yǔ)句合并格式，結(jié)果放入到output流中；

（4） tree_waker是一個(gè)遞歸的過(guò)程，在解析過(guò)程中，將查詢的條件和子模塊生成獨(dú)立的翻譯模塊；

（5） tree_waker在執(zhí)行的過(guò)程中遇到需要查詢建模表和函數(shù)表的情況，將查詢的結(jié)果輸出；

（6） 重復(fù)步驟（2）～步驟（5）過(guò)程，直到input流為空。

Tree Walker對(duì)部分葉節(jié)點(diǎn)的翻譯規(guī)則如表1所示。

3 系統(tǒng)實(shí)現(xiàn)與效果分析

本系統(tǒng)目前已在數(shù)據(jù)庫(kù)審計(jì)和防火墻產(chǎn)品有所應(yīng)用，數(shù)據(jù)庫(kù)審計(jì)與防火墻引擎設(shè)置界面如圖3所示。要對(duì)數(shù)據(jù)庫(kù)進(jìn)行審計(jì)或者建立防火墻，先要添加數(shù)據(jù)庫(kù)引擎。審計(jì)數(shù)據(jù)獲取方式有很多種，在設(shè)置界面進(jìn)行設(shè)置。

規(guī)則設(shè)置界面部分截圖如圖4所示。規(guī)則可以設(shè)置表、字段、SQL類(lèi)型等，SQL解析中能夠獲取的所有信息都可以在規(guī)則界面上設(shè)置。通過(guò)對(duì)SQL語(yǔ)句進(jìn)行解析獲取語(yǔ)句的類(lèi)型，然后對(duì)不同類(lèi)型的SQL語(yǔ)句設(shè)置不同的規(guī)則。

檢索界面如圖6所示?？梢詫?duì)審計(jì)日志進(jìn)行檢索，獲取數(shù)據(jù)庫(kù)用戶的操作行為。

告警界面如圖7所示。SQL語(yǔ)句觸發(fā)告警規(guī)則就會(huì)產(chǎn)生告警，在告警界面上可以查看告警細(xì)節(jié)。

圖7中select 1 from db_queue_tables where 1=2，其中條件1=2是常量比較，判定SQL語(yǔ)句可能是SQL注入語(yǔ)句，產(chǎn)生高風(fēng)險(xiǎn)告警。然后通過(guò)SQL翻譯將SQL語(yǔ)句翻譯成對(duì)應(yīng)的中文，select 1 from db_queue_tables where 1=2的翻譯結(jié)果為“從表dba_queue_tabkes中查詢滿足條件1=2的值1的返回結(jié)果”。

最新流量界面如圖8所示。在最新流量界面可以實(shí)時(shí)顯示最新的SQL操作，隨時(shí)監(jiān)控SQL操作動(dòng)態(tài)?；赟QL解析和翻譯的數(shù)據(jù)庫(kù)審計(jì)和防火墻產(chǎn)品可以在審計(jì)模式對(duì)操作進(jìn)行溯源，起到對(duì)不法分子進(jìn)行震懾的作用。防火墻模式可以通過(guò)阻斷方式對(duì)風(fēng)險(xiǎn)進(jìn)行控制，從而提升數(shù)據(jù)庫(kù)系統(tǒng)的安全性。

4 結(jié) 論

本文通過(guò)分析標(biāo)準(zhǔn)SQL語(yǔ)言的詞法規(guī)則和語(yǔ)法規(guī)則，并基于ANTLR設(shè)計(jì)并實(shí)現(xiàn)了SQL詞法解析器和語(yǔ)法解析器；使用SQL詞法解析器和語(yǔ)法解析器實(shí)現(xiàn)了SQL語(yǔ)句輔助分析功能，實(shí)現(xiàn)了SQL語(yǔ)句的詞法分析和語(yǔ)法樹(shù)生成；通過(guò)解析語(yǔ)法樹(shù)提取SQL信息并將SQL語(yǔ)句翻譯成自然語(yǔ)言；并將SQL解析和翻譯的功能應(yīng)用在數(shù)據(jù)庫(kù)綜合審計(jì)系統(tǒng)中。SQL解析和翻譯模塊已經(jīng)被應(yīng)用在商業(yè)數(shù)據(jù)庫(kù)防火墻和安全審計(jì)系統(tǒng)中，并且被部署到多個(gè)數(shù)據(jù)中心。系統(tǒng)可以監(jiān)控?cái)?shù)據(jù)庫(kù)的所有活動(dòng)，阻斷危險(xiǎn)操作和攻擊，從而達(dá)到增強(qiáng)數(shù)據(jù)庫(kù)安全的目的，為保障數(shù)據(jù)庫(kù)及信息系統(tǒng)的安全逐步發(fā)揮作用。

本文設(shè)計(jì)了一種基于反激式直流變換器的動(dòng)力電池均衡電路，給出了系統(tǒng)建模方法，并在PSIM環(huán)境下完了系統(tǒng)仿真電路，針對(duì)8種典型非均衡狀態(tài)進(jìn)行了全面的仿真實(shí)驗(yàn)，最后通過(guò)實(shí)驗(yàn)證明了系統(tǒng)建模的有效性。由于建模過(guò)程忽略了變換器磁阻、磁滯、磁飽和現(xiàn)象，同時(shí)簡(jiǎn)化了電路寄生參數(shù)，需要進(jìn)一步完善。

參考文獻(xiàn)

[1] 張博，類(lèi)艷春，廉小偉.數(shù)據(jù)庫(kù)安全漏洞淺析[J].保密科學(xué)技術(shù)，2012（3）：23?25.

[2] 劉三獻(xiàn).基于ANTLR的Gaussian詞法分析器和語(yǔ)法分析器的分析與設(shè)計(jì)[D].蘭州：蘭州大學(xué)，2009.

[3] 閆紅巖.SQL語(yǔ)句分析及數(shù)據(jù)庫(kù)安全研究[J].貴陽(yáng)：貴州大學(xué)，2006.

[4] 侯智斌，孫彥飛，呂曹芳.基于入侵容忍技術(shù)的數(shù)據(jù)庫(kù)安全策略研究[J].現(xiàn)代電子技術(shù)，2011，34（7）：78?80.

[5] PARR T， FISHER K. LL （*）： the foundation of the ANTLR parser generator [C]// Proceedings of 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation. [S.l.]： ACM， 2011： 425?436.

[6] SALOMAA K， YU S. NFA to DFA transformation for finite languages over arbitrary alphabets [C]// Proceedings of 1996 First International Workshop on Implementing Automata. London： Springer， 1996： 149?158.

[7] LOUDEN K C. Compiler construction： principles and practice [M]. New York： Cengage Learning， 2000： 21?148.

[8] DATE C J， DARWEN H. A guide to the SQL standard [M]. New York： Addison?Wesley， 1987.