編譯基礎理論
最近在讀一本編譯相關的書《兩周自製腳本語言》，書中用Java來設計一種名為Stone的腳本語言。
一、語言處理器的結構
在下圖中，源程式碼首先將進行詞法分析，由一長串字元串細分為多個更小的字元串單元。分割後的字元串稱為單詞（token）。之後處理器將執行語法分析處理，把單詞的排列轉換為抽象語法樹。至此為止，解釋器與編譯器的處理方式相同。之後，編譯器將會把抽象語法樹轉換為其他語言，而解釋器將會一邊分析抽象語法樹一邊執行運算。
二、詞法分析
語言處理器的第一個組成部分是詞法分析器（lexical analyzer、lexer或scanner）。程式的源程式碼最初只是一長串字元串。從內部來看，源程式碼中的換行也能用專門的（不可見）換行符表示，因此整個源程式碼是一種相連的長字元串。這樣的長字元串很難處理，語言處理器通常會首先將字元串中的字元以單詞為單位分組，切割成多個子字元串。這就是詞法分析。JFlex工具可定義單詞並自動生成詞法分析器。
1）通過正則表達式定義單詞
要設計詞法分析器，首先要考慮每一種類型的單詞定義，規定怎樣的字元串才能構成一個單詞。
Stone語言支援三種類型的單詞，即標識符、整型字面量及字元串字面量。
（1）標識符（identifier）指的是變數名、函數名或類名等名稱。此外，+或-等運算符及括弧等標點符號也屬於標識符。還有保留字也作為標識符處理。
（2）整型字面量（integer literal）指的是127或2014等字元序列。
（3）字元串字面量（string literal）是一串用於表示字元串的字元序列。雙引號之間可以使用\n、\”與\\這三種類型的轉義字元。它們分別表示換行符、雙引號和反斜杠。
正則表達式（regular expression）是一種用於字元串模式匹配的書寫記號。接下來，我們藉助正則表達式來定義Stone語言的單詞。
（1）首先來定義整型字面量，它比較簡單。
[0-9]+
（2）然後定義標識符，最後的\p{Punct}表示與任意一個標點符號字元匹配，這是Java的正則語法。模式\|\|將會匹配||。由於|是正則表達式的元字元，因此在使用時必須在前面添加\來轉義。
[A-Z_a-z][A-Z_a-z0-9]*|==|<=|>=|&&|\|\||\p{Punct}
（3）最後需要定義的是字元串字面量。
"(\\"|\\\\|\\n|[^"])*"
2）設計詞法分析器
要利用這一功能設計詞法分析器，首先要準備一個下面這樣的正則表達式。
\s*((//.*)|(pat1)|(pat2)|pat3)?
其中，pat1是與整型字面量匹配的正則表達式，pat2與字元串字面量匹配，pat3則與標識符匹配。起始的\s與空字元匹配，\s*與0個及0個以上的空字元匹配。模式//.*匹配由//開始的任意長度的字元串，用於匹配程式碼注釋。於是，上述正則表達式能匹配任意個空白符以及連在其後的注釋、整型字面量、字元串字面量或標識符。又因為它最後以?結尾，所以僅由任意多個空白符組成的字元串也能與該模式匹配。
執行詞法分析時，語言處理器將逐行讀取源程式碼，從各行開頭起檢查內容是否與該正則表達式匹配，並在檢查完成後獲取與正則表達式括弧內的模式相匹配的字元串。
只要像這樣檢查一下哪一個括弧對應的不是null，就能知道行首出現的是哪種類型的單詞。之後再繼續用正則表達式匹配剩餘部分，就能得到下一個單詞。不斷重複該過程，詞法分析器就能獲得由源程式碼分割而得的所有單詞。
3）自動機
自動機（automaton）類似於一種極為簡單的電腦。它的內部包含了一個僅能記錄有限類型的值的記憶體，在接收新的輸入後，新值將由輸入值與當前值共同決定，並更新至記憶體中。自動機不支援包括四則運算或分支運算等在內的任何其他類型的運算。自動機程式實質是一張對應關係表，根據該表，我們能由輸入值及當前記憶體值的組合，得到需要保存至記憶體中的新值。
圖中的自動機與正則表達式[0-9][0-9]*等價。圓圈內的數字表示自動機記憶體記錄的當前值。圓圈（或其中的數字）稱為狀態。圖中的箭頭表示自動機在某一狀態下，如果收到箭頭旁標識的輸入，將轉換至箭頭指向的狀態（這一過程稱為轉換）。也就是說，如果圓圈內的數字是記憶體的當前值，且箭頭旁的數字是自動機接受的輸入，那麼記憶體的值將被更新為箭頭指向的圓圈內的數字。
任何正則表達式都能轉化為與之等價的有限狀態機，也就是說自動機定能僅包含有限個圓圈。事實上，圓圈內的數字並沒有特殊的含義。它們僅僅用於區分不同的圈圈。因此，有些圖中的圓圈內不寫數字。該圖最為根本的一點在於，圓圈的數量有限（因此稱為有限狀態自動機）。
字元串匹配的執行將從起始狀態，即圖中的狀態1開始。自動機將從字元串頭部開始逐一輸入字元，並據此改變狀態，最終抵達停止狀態，即圖中的狀態2。執行途中如果找不到符合要求的箭頭就會出現錯誤，字元串匹配失敗。
狀態2是一個停止狀態，其中，我們應當關注的是狀態2上標有的箭頭。可以看到，該自動機的狀態2依然能夠接受數字輸入並繼續執行。由於箭頭從狀態2出發又回到該狀態，因此無論輸入幾次，自動機將始終處於狀態2。只要輸入內容是數字，自動機的執行將不斷循環。
要判斷正則表達式是否與整個字元串匹配，程式需要檢查字元串的最後一個字元輸入後，自動機是否處於停止狀態。如果沒有到達停止狀態，或中途出錯，則表示字元串與正則表達式不匹配。
下面我們再來看一個自動機的例子。這次我們嘗試將一條更加複雜的正則表達式改寫為自動機。
\s*([0-9][0-9]*|[A-Za-z][A-Za-z0-9]*|=|==)
下圖是與該正則表達式等價的自動機，它含有5種狀態。其中，狀態1是開始狀態，其餘都是停止狀態。當自動機處於狀態1時，它能根據輸入的內容在4種模式中選擇，並轉換至相應的狀態。如果輸入的是空白符，自動機將保持狀態1，直至接受到與某種模式匹配的字元。
由於模式=與==的首字元相同，因此對於這兩種模式，自動機都將轉換至狀態4。如果下一個字元不是=，匹配將就此結束。如果自動機繼續接受了一個字元=，就將轉換至狀態5並結束。狀態5沒有轉換至其他狀態的箭頭，因此無論之後的輸入是什麼，匹配過程都會直接結束，不會進行判斷。
三、語法分析
語言處理器在詞法分析階段將程式分割為單詞後，將開始構造抽象語法樹。抽象語法樹（AST，Abstract Syntax Tree）是一種用於表示程式結構的樹形結構。構造抽象語法樹的過程稱為語法分析，依然屬於語言處理器的前半階段。經過詞法分析後，程式已經被分解為一個個單詞。語法分析的主要任務是分析單詞之間的關係，如判斷哪些單詞屬於同一個表達式或語句，以及處理左右括弧（單詞）的配對等問題。語法分析的結果能夠通過抽象語法樹來表示。這一階段還會檢查程式中是否含有語法錯誤。
1）抽象語法樹
用樹形結構來表現語法分析的結果，即通過對象來表示程式中的語句與表達式。接下來我們試著用抽象語法樹來表示下面的Stone語言程式。
13 + x * 2
只要將這個程式理解為算式13+x*2，即13與(x*2)的和即可。圖下是它的對象形式表示，是一棵抽象語法樹。
圖上方的單詞序列是詞法分析階段得到的結果。通過語法分析，就能得到如圖所示的由對象形式表現的樹形結構。圖中的矩形表示對象。矩形上半部分顯示的是類名。箭頭表示的是欄位，箭頭旁邊顯示的文字是欄位名。矩形下半部分列出的也是欄位。
BinaryExpr對象用於表示雙目運算表達式。雙目運算指的是四則運算等一些通過左值和右值計算新值的運算。
圖中含有兩個BinaryExpr對象，其中一個用於表示乘法運算x*2，另一個用於表示加法運算13加x*2。加法運算的左側是整型字面量13，它是一個NumberLiteral對象。右側是x*2，它是另一個BinaryExpr對象。這樣通過對象來表示運算符的左值與右值的方式能一目了然地顯示各自表示的內容。
表達式x*2左側的x是一個變數名，因此能用Name對象來表示。右側的2是一個整型字面量，因此以NumberLiteral對象表示。
上圖形如一棵上下顛倒的樹，因此這種數據結構通常被稱為樹形結構。圖中的矩形（對象）稱為節點（node），箭頭稱為樹枝或邊。圖的上方的BinaryExpr對象稱為根節點。NumberLiteral對象及Name對象這類不含樹枝的節點被稱為葉節點。如果一個節點含有若干樹枝，樹枝連接的節點就是該節點的子節點，它們與該節點組成的整體稱為子樹。
在很多教材中，抽象語法樹會用更加簡潔的形式表示，如下圖所示，樹形結構通過箭頭呈現。這種表示樹形結構的方式沒有限定具體的實現方式。
抽象語法樹僅用於表示語法分析的結果，因此通過詞法分析得到的單詞並不一定要與抽象語法樹的節點一一對應。抽象語法樹是一種去除了多餘資訊的抽象樹形結構。
(13 + x) * 2
對這樣一個表達式來說，它與之前的例子不同，包含了括弧。乘法運算的左值不再是x而是13+x。一般來講，這段程式的抽象語法樹如下圖所示。葉節點和中間的節點都不含括弧。
2）BNF
要構造抽象語法樹，語言處理器首先要知道將會接收哪些單詞序列（即需要處理怎樣的程式），並確定希望構造出怎樣的抽象語法樹。通常，這些設定由程式設計語言的語法決定。
語法規定了單詞的組合規則，例如，雙目運算表達式應該由哪些單片語成，或是if語句應該具有怎樣的結構等。而程式設計語言的語法通常會包含諸如if語句的執行方式，或通過extends繼承類時將執行哪些處理等規則。
下面的程式碼清單採用了一種名為BNF（Backus-NaurForm，巴科斯範式）的書寫方式，這是一種用於表示上下文無關文法的語言。準確來講，這裡使用的書寫方式更接近BNF的擴展版本EBNF（Extended BNF，擴展巴科斯範式）。一般都會用Yacc這類工具來生成基於BNF的語法分析器。
factor: NUMBER|"("expression")"
term: factor{("*"|"/")factor}
expression: term{("+"|"-")term}
BNF中用到的元符號如下表所示。
| {pat} | 模式pat至少重複0次 |
| [pat] | 與重複出現0次或1次的模式pat匹配 |
| pat1|pat2 | 與pat1或pat2匹配 |
| () | 將括弧內視為一個完整的模式 |
乍一看，BNF與正則表達式區別很大，但兩者的思維方式類似。BNF與正則表達式都用於表述某種模式，以檢查序列的內容。
在BNF的表達規則中，冒號（:）左側所寫的內容能夠用於表示與在冒號右側所寫的模式相匹配的單詞序列。例如，第1行的規則中，factor（因子）意指與右側模式匹配的單詞序列。冒號左側出現的諸如factor這樣的符號稱為非終結符或元變數。
與非終結符相對的是終結符，它們是一些事先規定好的符號，表示各種單詞。在程式碼清單中，NUMBER這種由大寫字母組成的名稱，以及由雙引號”括起的諸如”(“的符號就是終結符。NUMBER表示任意一個整型字面量單詞，”(“表示一個內容為左括弧的單詞。
冒號右側的模式中也包含了若干個終結符或非終結符。與正則表達式一樣，模式中也能使用上表列出的那些特殊符號。
例如，在程式碼清單第1行的規則中，factor能表示NUMBER（1個整型字面量單詞），或由左括弧、expression（表達式）及右括弧依次排列而成的單詞序列。expression是一個非終結符，第3行對其下了定義。因此，由左括弧、與expression匹配的單詞序列，及右括弧這些單片語成的單詞序列能與factor模式匹配。
如果冒號右側的模式中僅含有終結符，BNF與正則表達式沒有什麼區別。此時，兩者唯一的不同僅在於具體是以單詞為單位檢查匹配還是以字元為單位檢查。
另一方面，如果右側含有類似於expression這樣的非終結符，與該部分匹配的單詞序列必須與另外定義的expression模式匹配。非終結符可以理解為常用模式的別稱，在定義其他模式時能夠引用這些非終結符。模式中包含非終結符是BNF的特徵之一。
程式碼清單第2行中的term（項）表示一種由factor與運算符「*」或「/」構成的序列，其中factor至少出現一次，運算符則必須夾在兩個factor之間。由於「{}」括起來的模式將至少重複出現0次，因此，第2行的規則直譯過來就是：與模式term匹配的內容，或是一個與factor相匹配的單詞序列，或是在一個與factor相匹配的單詞序列之後，由運算符「*」或「/」以及factor構成的組合再重複若干次得到的序列。
第3行的規則也是類似。expression表示一種由term（對term對應的單詞序列）與運算符「+」或「-」構成的序列，其中term至少出現一次，運算符則必須夾在兩個term之間。結合所有這些規則，可以發現與模式expression匹配的就是通常的四則運算表達式，只不過單詞的排列順序做了修改。也就是說，與該模式匹配的單詞序列就是一個expression。反之，如果單詞序列與模式expression不匹配，則會發生語法錯誤（syntax error）。
那麼，接下來讓我們來看一個具體的例子。表達式
13 + 4 * 2
經過詞法分析後將得到如下的單詞序列。
NUMBER "+" NUMBER "*" NUMBER
整個單詞序列與程式碼清單中的模式expression匹配。如下圖所示，該單詞序列的局部與非終結符factor及term的模式匹配，整個序列則明顯與模式expression匹配。整型字面量13與factor匹配的同時也與term匹配。根據語法規則，單獨的整型字面量單詞能與factor匹配，單個factor又能與term匹配。
在程式碼清單中，expression、term與factor是範圍逐層縮小的組成單位，不過需要注意的是，factor能夠重新回到（由括弧括起的）expression。這種具有循環結構的遞歸定義也是BNF的一個特徵。
3）語法分析與抽象語法樹
在使用BNF來表示語法之後，就能藉助它們進行語法分析，並構造抽象語法樹。語法分析用於查找與模式匹配的單詞序列。查找得到的單詞序列是一個具有特定含義的單片語。分組後的單詞能繼續與其他單片語一起做模式匹配，組成更大的分組。
通常，抽象語法樹用於表示語法分析的結果，因此需要表現出這些分組之間的包含關係。下圖是根據程式碼清單中的四則運算規則，對13+4*2進行語法分析後得到的結果，以及根據該結果構造的抽象語法樹。圖的左上方是語法分析的結果，右下方是構造的抽象語法樹，正好上下顛倒。抽象語法樹中的13或+等節點表示與相應單詞對應的葉節點。可以看到，語法規則中出現的終結符都是抽象語法樹的葉節點。非終結符term與factor也是抽象語法樹的節點。
抽象語法樹的子樹表示的是語法分析中得到的單片語。子樹是更大的樹中的一部分。例如，與非終結符term模式匹配的分組能夠構成一棵子樹，它的根節點是表示非終結符term，與相應單詞匹配的葉節點都是其子節點。右側的term與4、*及2匹配，它們是以term為根節點的子樹的葉節點。4與2同時也與模式factor匹配，因此term與4、2之間插入了一個表示factor的節點。至於13，它和term、factor通過一條直線相連，也是一棵以term為根節點、13為葉節點的符合語法規則的子樹。
