(db)資料庫語句執行(2)-語法分析與預處理
本文將介紹資料庫查詢編譯器中的語法分析和預處理，該步驟是查詢的第一個步驟，即將語句進行語法分析得到語法分析樹，並進行相關的預處理。
1. 語法分析
語法分析的工作就是接收類似SQL的語言語句文本，並將之轉換成語法分析樹的數據結構。
1.1 語法分析樹基本概念
語法分析樹的節點可以分成兩種：
1）原子（葉）節點
語法成本（如關鍵字），關係或屬性的名字，常數，括弧，運算符，以及其他模式成分。
2）語法類節點
在一個查詢中起相似作用的查詢子成分所形成的族的名稱。例如，<Query>表示select from where形式的查詢；<Condition>是指在where之後的表達式；
其子節點通常是該語言的語法規則之一進行描述。
1.2 一個小例子的規則定義
如select查詢語句的一個子集規則：
1) 查詢
這條簡單的語句只是支持以下的規則，不支持GROUP BY，HAVING等。
<Query> := SELECT <SelList> FROM <FromList> WHERE <Condition>
- <SelList>：為選擇列表；
- <FromList>：為數據源的列表（From列表）；
- <Condition>：為數據過濾的條件；
2）選擇列表
下面是選擇列表的規則，表示選擇列表可以是一個屬性加上逗號和另一個選擇列表；或者就是一個屬性。
<SelList> := <Attribute>, <SelList>
<SelList> := <Attribute>
3）From列表
From列表與選擇列表相似，表示可以有單個關係，或者一個關係，逗號和另一個From列表組成。
<FromList> := <Relation>, <FromList>
<FromList> := <Relation>
4）條件
條件的推倒語法如下，即可以是一個條件，AND和另一個條件；單個屬性，IN和一個Query；屬性，=，屬性；屬性， Like， Pattern四個推倒語法。
<Condition> := <Condition> AND <Condition>
<Condition> := <Attribute> IN (Query)
<Condition> := <Attribute> = <Attribute>
<Condition> := <Attribute> LIKE <Pattern>
5）基本語法類
如上面出現的<Attribute>, <Relation>, <Pattern> 不是通過規則定義的，而是通過代表的原子規則定義的。
1.3 一個例子的語法分析樹
根據以上定義的規則，定義以下兩個關係：
StarsIn(movieTitle, movieYear, startName);
MovieStar(name, address, gender, birthdate);
對於以下需求：查找出生於1960年影星拍攝的電影名，可以有以下兩條語句：
SELECT movieTitle FROM StarsIn WHERE starName IN (SELECT name FROM MovieStar WHERE birthdate LIKE 1960%)
和
SELECT movieTitle FROM StarsIn, MovieStar WHERE starName = name AND birthdate LIKE 1960%
這條Query對應的語法分析樹分別如下（左/右）：
2. 預處理
預處理是將語法分析樹作進一步處理的過程，主要包括以下幾點：
- 如果查詢語句中用到的關係實際上是一個視圖View，那麼用到該關係的地方必須用該視圖的語法樹來代替；
- 檢查關係的使用，即From出現的關係必須是當前模式中的關係或視圖；
- 檢查與解析屬性的使用，在SELECT或WHERE子句中提到的每個屬性必須是當前範圍中某一個關係的屬性，如果在語句中沒有顯式地附加到屬性上，典型的查詢處理器此時通過給屬性加上它所引用關係的信息來解析每一屬性；
- 檢查類型，所有屬性的類型比較與其使用相適應。
本文主要介紹了語法分析和語句的預處理，其他相關知識，將在後續中介紹。
參考文章/書本：
- 《資料庫系統基礎教程》
- 《資料庫系統實現》
- 《資料庫系統概念》
推薦閱讀：
