編譯器入門,語法分析,資料結構

編譯程式分為哪幾個階段

語法分析的目的，是構建抽象語法樹（AST）。

在語法分析之前，需要先準備與AST有關的資料結構，也就是程式語言教程裡經常提到的型別、變數、運算子、表示式、語句、函式、作用域等。

編譯器內還多了一個，抽象語法樹的節點。

這些資料結構設計起來複雜的地方在於，他們之間是有關聯的，而且有時候還比較緊密。

怎麼解耦合，是設計時的要點。

1，型別與變數，

型別聲明瞭變數，變數也就有了型別。

型別與變數，是互相關聯的。

乍一看是用型別去宣告變數，但不是所有的型別都是基本型別，還有自定義的類。

類裡也是可以有變數的，同時類還可以宣告變數（即類的物件），類的物件還可以作為其他類的成員變數。

型別與變數，是在資料結構設計時，需要第一個解耦合的點。否則，就只能支援簡單型別了，而沒法支援複雜資料結構。

一般的辦法就是，在型別type和變數variable的資料結構裡都包含一個整數字段，當這個整數相同時，表示變數的基本型別是某個型別。

變數還可以是指標、陣列等擴充套件型別，所以變數variable的資料結構裡還需要記錄是幾級指標，陣列的話還要同時記錄陣列的維數和每一維的大小。

如果變數宣告時沒有指定陣列大小，則需要後續初始化時確定，可以先把陣列大小設定為-1，然後留到語義分析時再回填。

如果是多維陣列，沒有指定的維數只能有一維，否則程式沒法根據初始化資料確定陣列的真實大小。

常量，就是設定了const標示的變數。因此，變數variable裡需要有一個const標示。

variable還需要有一個literal標示用來區分是常量字面值，還是用const關鍵字宣告的變數。

字面值是不能賦值的，但const指標是可以用同類型變數的地址給它賦值的，只是不能修改它的內容，即不能賦值解引用。

int a = 1；

const int * p = &a；

是可以的，但不能*p = 2；

這個檢查可以留到語義分析時去做，語法分析以構建AST為主。

2，變數與表示式，

變數可以在宣告之後緊跟著賦值運算子=進行初始化，初始化的資料可以來自於一個表示式expr。

表示式，是由變數、常量、運算子組成，這裡就有了耦合。

一個可行的解決辦法是，藉助AST的節點。

變數宣告，和變數初始化是兩個步驟。

宣告的變數只需要記錄在當前作用域scope，並不需要生成運算程式碼，如果沒有語句使用它的話。

變數的初始化，是一個含有賦值運算的表示式語句，是需要生成程式碼的。

需要生成程式碼，就需要為它生成一個AST節點，並且標示該節點是需要生成程式碼的。

表示式對應的是一個AST的節點，該節點的子節點就是表示式的內容，可以有多級子節點來表示複雜的表示式。

AST的節點，也可以只指向一個變數，它是表示式的葉子節點。這還解決了同一個變數被多個表示式多次使用的問題。

即，表示式的節點使用AST的節點node，然後用node指向變數，而不是直接使用變數本身。

變數的初始化表示式，是當前塊的一個節點。變數本身，則記錄在當前塊的作用域裡。

例如，如下程式碼，main函式的程式碼塊裡要有表示式a = 1的節點，它的作用域裡要記錄變數a和常量1。

int main（）

{

int a = 1；

}

3，表示式與語句，

if語句的條件就是一個表示式，返回一個bool。

if塊與else塊，則是一個語句塊，也是可以含有表示式的，還可以含有其他語句。

4，函式，

函式是一個特殊的節點，他含有一個作用域，和一個語句塊。

在書寫程式碼時，這兩個是寫到一起的，更符合人的讀寫習慣，但在語法分析時則是分開的。

因為一個變數不能多次宣告，但可以多次使用，所以同一個作用域裡的同名變數只能有一個，但指向該變數的節點可以有多個，並且在AST中出現在不同的位置。

5，節點的型別，

AST的節點node自然要有不同的型別，以分別對應函式、表示式、運算子、if語句、while語句、for語句，以及最常見的順序語句，即順序塊block。

main函式的函式體就是一個順序塊，他裡面可以包含各種分支和迴圈語句定義的其他塊，形成複雜的程式流程。

6，AST所需的資料結構列表：

type ，variable，expr，block，scope，function，node。

function和block都有scope。

expr，block，function，都是特別的node。

type和variable，則隸屬於不同的scope。

node是AST的基類，它還需要有指向父節點的指標parent，和子節點的指標列表childs。

7，運算子，

是一個單獨的結構operator，裡面記錄運算子的型別，名字，優先順序，結合性，等等。

在構成表示式時，和變數一樣用node節點去指向它，只是運算子的node可以有子節點，且子節點個數等於運算子的目數。

單目運算子1個子節點，雙目運算子2個子節點，etc。