SQL 語句解析過程詳解

SQL 語句解析過程詳解：

1．輸入SQL語句

2．詞法分析------flex

????????使用詞法分析器（由Flex生成）將 SQL 語句分解為一個個單詞，這些單詞被稱為“標記“。標記包括關鍵字、標識符、運算符、分隔符等。

2.1 flex 原理

1、使用 flex 工具定義正則表達式規則來匹配不同類型的詞法單元；例如，可以定義以下規則：

匹配關鍵字：SELECT、FROM、WHERE、HAVING等。
匹配標識符：由字母或下劃線開頭，后跟字母、數字或下劃線組成。
匹配運算符：比如=、<、>、+、等。
匹配常量：包括整數、浮點數、字符串等。

2、生成詞法分析器代碼：根據定義的詞法規則，使用Flex工具生成對應的詞法分析器代碼；

3、輸入查詢字符串：將要解析的查詢字符串作為輸入提供給同法分析器；

4、掃描和匹配：詞法分析器從輸入字符串中逐個讀取字符，并嘗試將其與定義的詞法規則進行匹配；

5、生成詞法單元：當詞法分析器匹配到一個詞法規則時，它會生成相應的詞法單元并返回給語法分析器。每個詞法單元通常包含兩部分信息：

詞法單元類型(token type)：表示該詞法單元的種類，比如關鍵字、標識符、運算符等；
詞法單元值(tokenvalue)：表示該詞法單元具體的取值；

6、繼續掃描：詞法分析器會持續從輸入字符串中讀取字符，并重復步驟4和步驟5，直到整個查詢字符串被完全解析為一系列詞法單元；

7、返回詞法單元序列：當整個查詢字符串都被解析后，詞法分析器將返回一個包含所有詞法單元的序列給語法分析器，供后續的語法分析處理；

2.2 flex 文件代碼結構

2.2.1 flex 文件介紹

1、flex文件代碼

%option noyywrap
%{
definition
%}%%
rules
%%
Code

（1）%option 指定 flex 掃描時的一些特性。yywrap 通常在多文件掃描時定義使用。常用的一些選項有：

Noyywrap：告訴flex不使用yywrap函數；
yylineno：會告訴flex生成一個名為yylineno的整型變量來保存當前的行號；
case-insensitive 正則表達式規則大小寫無關；

（2）definitio部分為定義部分，包括引入頭文件，變量聲明，函數聲明，注釋等，這部分會被原樣拷貝到輸出的.c文件中。

（3）rules部分定義詞法規則，使用正則表達式定義詞法，后面{}內則是掃描到對應詞法時的動作代碼；“|”是一個特殊符號，表示下一個模式應用相同的動作；正則表達式后面不指定動作，則相應的模式會被忽略。

（4）code部分為C語言的代碼。yylex為flex的函數，使用yylex開始掃描。

2.2.2 flex 文件常用變量

（1）yytext：詞法分析程序當前識別到的一些詞素，與轉換規則部分中的某個模式相匹配；

（2）yylength：詞法分析程序當前識別到的詞素的長度；

（3）yylval：yylval是在bison中定義的聯合類型變量（union），因為Flex生成的詞法分析程序yylex()需要向bison生成的語法分析器返回識別到的詞法單元，所以需要使用yylval來保存詞法單元的屬性值；

2.2.3 正則表達式

.????????匹配除換行符”\n”以外的任何單個字符；*????????匹配前面表達式的零個或多個拷貝；[]???????匹配括號中任意字符的字符類，如果第一個字符是 “^”，則匹配除括號中的字符以外的任意字符；“-” 指示一個字符范圍，例如“[0-9]”和“[0123456789]”含義相同；除了以 “\” 開始的轉義序列，元字符在括號內沒有任何含義；^?????? 作為正則表達式的行首匹配行的開頭，也用于方括號中的否定；$? ? ? ?作為正則表達式的行尾匹配行的結尾；\? ? ? ? 用于轉義元字符，也作為常用的C轉義序列的一部分，例如”\n”表示換行，“\*” 表示非元字符的星號；+? ? ? ?匹配前面的正則表達式一次或多次出現；？? ? ? 匹配前面的正則表達式零次或一次出現；|??????? ?匹配前面的正則表達式或隨后的正則表達式；“…”??引號中的每個字符解釋為字面意義，除C轉義序列外元字符會失去其特殊含義；()??????將一系列正則表達式組成一個新的正則表達式，例如(01)，表示字符序列 01；{}? ? ? 當括號中包含一個或兩個數字時，指示前面的模式允許被匹配多少次，例如{1，3}表示匹配字母一次到三次；

2.2.4 flex 文件具體案例

1、創建一個名為 lexer.l 的文件，其中包含詞法規則；

%{
#include <stdio.h>
%}%%
SELECT                  { printf("Keyword: SELECT\n"); }
FROM                    { printf("Keyword: FROM\n"); }
WHERE                   { printf("Keyword: WHERE\n"); }
AND                     { printf("Keyword: AND\n"); }
OR                      { printf("Keyword: OR\n"); }[0-9]+                  { printf("Number: %s\n"， yytext); }[A-Za-z_][A-Za-z0-9_]*  { printf("Identifier: %s\n"， yytext); }
[=><]+                  { printf("Operator: %s\n"， yytext); }
[ \t\n]                 ; // Skip whitespace.                       { printf("Unknown: %s\n"，yytext); }%%int main() {    yylex();   return 0;
}

2、使用 flex 命令編譯 lexer.l 文件，生成詞法分析器代碼?

（1）執行下列語句生成詞法分析器代碼

flex lexer.l

（2）詞法分析器生成結果

lex.yy.c

（3）編譯生成的詞法分析器代碼，生成可執行文件

gcc -o lexer lex.yy.c -lfl

（4）運行可執行文件并輸入一些算術表達式進行測試

./lexer輸入：SELECT * FROM table;

（5）執行結果如下

說明：

-ll：這是舊版本的Flex生成器（例如Flex 2.5.4）的鏈接選項。它指示鏈接器將使用名為 libl.a 或 libl.so 的庫文件。在以前的版本中，Flex生成的詞法分析器的默認名稱是 lex.yy.c，而庫文件的名稱以 "l" 開頭，因此使用 -ll 是一種傳統的方式。
-lg：這是新版本的Flex生成器（例如Flex 2.5.35）的鏈接選項。類似于舊版本的 -ll，它指示鏈接器使用名為 libg.a 或 libg.so 的庫文件。這種新方式是為了避免與其他工具和庫發生命名沖突。
-lfl：這是一個與Flex生成的詞法分析器庫相關的選項。-lfl 表示鏈接器將使用名為 libfl.a 或 libfl.so 的庫文件。這個庫包含了Flex所需的運行時支持函數。

注意：

????????如果 flex 詞法分析器對 .l 進行編譯時報錯:

????????/opt/h/devtoolset-11/root/usr/ibexec/gcex86.64-redhat-linux/11/ld: cannot find -lfn

解決方案：

????????該錯誤表明鏈接器無法找到名為 -if 的庫文件。這通常是因為在您的系統上缺少libfl庫，或者庫文件的路徑未正確配置。要解決這個問題，您可以嘗試以下步驟：

1、確認庫是否已安裝:首先，請確保您的系統上已安裝了libfl庫。您可以嘗試使用包管理器來安裝它。在基于Red Hat的系統中，您可能需要執行類似于以下的命令:

yum install flex-devel

2、檢查庫文件路徑:如果庫已安裝，但鏈接器仍然找不到它，可能是因為庫文件的路徑未正確配置。您可以嘗試手動指定庫文件的路徑。例如，假設libfl庫文件位于/usr/lib64目錄下，您可以使用以下方式鏈接：

gcc -o my program lex.yy.c -L/usr/lib64 -1f1

3、更新庫文件緩存:如果您最近安裝了libfl庫，但鏈接器仍然找不到它，您可能需要更新庫文件緩存。運行以下命令以更新庫文件緩存：

sudo ldconfig

3．語法分析------bison

????????使用語法分析器（由 Bison 生成）根據語法規則進行語法分析，生成抽象語法樹。語法樹是一種樹形結構，它表示 SQL 語句的語法結構。語法分析器會檢查語法樹是否符合 SQL 語法規則，如果不符合，則會拋出語法錯誤。

3.1 bison原理

3.2 bison文件代碼結構

1、bison文件代碼

%{
// C 代碼和頭文件的聲明
#include <stdio.h>
// 在這里可以定義全局變量和函數等
%}
// Bison 的選項部分
%option verbose   		// 控制 Bison 解析器的詳細輸出// Bison 的聲明部分    
%token NAME       	    // 定義終結符或標記的名稱
%token NUMBER%left ‘+’ ‘-‘           // 定義運算符的優先級和結合性
%left ‘*’ ‘/’%{
// 在這里可以編寫更多的 C 代碼
%}// Bison 的規則部分%%
// 語法規則的定義
expression : expression '+' expression           | expression '-' expression           | expression '*' expression           | expression '/' expression           | '(' expression ')'           | NUMBER           ;
// 更多的語法規則...
%%// C 代碼部分（選項中的 %{ ... %} 和規則部分中的 %% 之間的部分）
// 在這里可以編寫與語法規則相關的 C 代碼
int main() {    yyparse();  // 調用 Bison 生成的解析函數    return 0;
}

? bison文件的書寫格式與flex文件的書寫格式基本一致，只是規則的定義語法不同。

3.3 規則語法介紹

（1）終結符（Terminals）

????????終結符是語法規則中的基本符號，通常是語言中的關鍵字、運算符、標識符等。可以使用%token來定義終結符。以下是一個示例：

%token NUMBER 
%token PLUS MINUS TIMES DIVIDE 
%token IDENTIFIER 
%token SEMICOLON

????????在這個示例中，我們定義了幾個終結符，包括數字（NUMBER）、加號（PLUS）、減號（MINUS）、乘號（TIMES）、除號（DIVIDE）、標識符（IDENTIFIER）和分號（SEMICOLON）等。終結符是語法規則中的基本符號，代表語言中的最小單元或詞匯元素。終結符在語法分析的過程中與輸入字符串的實際內容進行匹配，幫助構建解析樹或語法分析樹。在 Bison 文件中，終結符通常以大寫字母或使用引號括起來的字符串表示。

（2）非終結符（Non-terminals）

????????非終結符表示語法規則中的抽象結構，可以由其他非終結符和/或終結符組成。您可以使用?%type?來定義非終結符的類型。以下是一個示例：

%type <expr> expression%type <term> term%type <factor> factor

????????在這個示例中，我們定義了三個非終結符 expression、term 和 factor，并指定了它們的類型。這些類型標記可以在產生式的操作部分使用，以便對解析樹節點進行更復雜的操作。非終結符在語法分析樹中代表了一些更高級的結構，可以用來執行語義操作、構建解析樹，并幫助描述語言的抽象語法結構。在 Bison 文件中，非終結符通常以小寫字母開頭。

????????終結符和非終結符在 Bison 文件中共同定義了語法規則，幫助我們描述和分析特定編程語言或語言的一部分。終結符代表了實際的詞法單元，而非終結符則代表了更高層次的語法結構。通過將終結符和非終結符組合起來，我們可以創建復雜的語法規則，用于生成和解析語言的有效字符串。

（3）“文法”

????????“文法”是一組規則，用于描述編程語言或語言的語法結構。這些規則定義了語言的句法（syntax），即哪些組合是有效的、合法的語句和表達式，以及它們如何組合在一起。文法規則使用產生式（productions）的形式來表示，其中包含終結符（terminals）和非終結符（non-terminals）的組合。

????????文法規則在 Bison 文件中是使用 BNF（巴科斯-諾爾范式）或 EBNF（擴展巴科斯-諾爾范式）的形式表示的。BNF 是一種形式化的表示方法，用于定義上下文無關文法（Context-Free Grammar），這些文法用于指定編程語言的語法規則。

expression : expression '+' term| expression '-' term| term;

（4） %start

????????%start 指令用于指定文法的起始非終結符。起始非終結符是語法分析的入口點，也就是從哪個語法規則開始構建解析樹或語法分析樹。

%start program%%statements : statement| statements statement;statement : assignment| if_statement| while_statement| /* ... other statement types ... */ ;

????????%start program 指定了起始非終結符為 program。這意味著語法分析將從 program 規則開始，逐步展開其他非終結符，最終構建解析樹。在實際語法規則中，起始非終結符的選擇取決于您想要分析的語言的語法結構。

（5）$

????????在語法規則中，$ 用于引用當前產生式的右側的符號或值。例如，在產生式的右側，$1 表示該產生式右側的第一個元素（終結符或非終結符），$2表示第二個元素，依此類推。這些引用用于將產生式右側的值傳遞給產生式左側。注意：生產式的起始下標為1。

（6）$$

????????在語法規則中，$$ 用于引用當前產生式的結果。當 Bison 解析器完成一個產生式的分析并計算出其結果時，該結果會被賦值給 $$。這通常用于構建解析樹的節點或為更高層次的語法規則提供結果。

（7）|

????????| 用于表示多個產生式之間的選擇。它在上下文無關文法中用于定義非終結符的不同產生式形式。每個產生式通過豎線分隔，表示它們是該非終結符的可能形式之一。

3.4 bison文件具體案例

1、創建一個名為parser.l的文件，其中包含詞法規則；

%{
#include <stdio.h>
#include <stdlib.h>
%}//定義終結符
%token SELECT INSERT UPDATE DELETE FROM WHERE 
%token INTO VALUES SET
%token ID INT STRING%%//定義規則statement: SELECT columns FROM table WHERE condition ';'| INSERT INTO table '(' columns ')' VALUES '(' values ')' ';'| UPDATE table SET assignments WHERE condition ';'| DELETE FROM table WHERE condition ';';columns: ID| columns '，' ID;table: ID;assignments: ID '=' value| assignments '，' ID '=' value;values: value| values '，' value;value: INT| STRING;condition: ID '=' value;%%int main() {yyparse();return 0;
}int yyerror(const char *s) {printf("Error: %s\n"， s);return 0;
}

2、使用 bison 命令編譯 lexer.l 文件