[編譯器的研究]文獻探討

在 MIT 的課程「6.035 電腦語言工程(SMA 5502),2005秋季課程」(註1)提到
課程裡要完成的 5 項工作，連接起來就會完成一個編譯器。
這 5 項工作是

掃描器和解析器、
語義檢查器、
代碼生成器、
資料流程優化器、
指令優化器

編譯器的工作裡，一開始是 scanner 及 parser (掃描器和解析器)。

scanner 的工作是把一連串的字元(character)，轉換成一連串的token。(註2)(註3)
stream of characters --> stream of tokens
sequence fo tokens 是compiler所在乎的部份。

<---
(註1)：http://www.myoops.org/main.php?act=course&id=1946
(註2)：來源：http://www.myoops.org/twocw/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-035Fall-2005/EF1122A1-77A5-49CA-8BF6-EF6C9AC64F42/0/2scanerparsr_prj.pdf
(註3)：token 的定義是可被當成處理的單元，它是由一連串的字元(sequence of character)所組成。
---->

parser 的工作是把一連串的token轉換成語言中的entities。
且把language的結構建構出來，通常的表達方式是樹狀結構。

在scanner及parser所產生的結果，可以用來替原始碼上色(註4)。

<----
(註4)：http://www.cnblogs.com/Ninputer/archive/2011/06/07/2074632.html
---->

從字元轉換成 token 需要辨認recognize。
這個層級通常在regular language的範圍內。因此使用 DFA，NFA 的方式來實作。
或者利用現成的 regular expression 模組來做，但是無法處理 recursive。
所以自己寫 DFA/NFA 來處理是必須要會的。

例如一般程式語言會有保留字，及變數id。
這兩個是不同的意義，遇到保留字要做的事與遇到變數要做的事是不同的。
像是在c++語言裡面

string string1;

DFA，NFA做的工作是辨認，有一個 string 的字出現在第0個位置，是保留字。
有一個 string1 的字出現在第7個位置，是變數id
因為規則不同，所以需要兩個 DFA/NFA 來處理。
而一般的程式語言，會需要很多的意義。例如：

保留字
變數id
註解
常數
空白
分行
...

之前課本(註5)學寫的 DFA/NFA 的能力，是等待輸入結束後，
看最後一個state留在哪裡來判斷是否有被辨視到。
而對應於整串的程式語言，就不能等輸入結束後才來判斷。
針對這樣的需求，DFA/NFA 需要被修正。

需求是輸入還沒結束前，就判斷是否有辨認到屬於哪個類別。
並且在多個辨認都成立的狀況下，選擇最長辨認。
舉前面的例子，當一看到 string 的時候就當做辨認到 string 的話，
string string1 會被認為兩個 string 的保留字及一個 1 的常數。
因此， DFA/NFA 要一直辨視到失敗為止，
然後檢查最後一個 accept 的 state 是否存在。
若存在，才能算是正確的辨認。

<---
(註5)：introduction to the theory of computation
--->

一個來自MIT上課程中，說明的 scanner 的工作應該是做到以下的轉換：

語言範例：
class Program {
    // uninformative comment
    void main() {
      callout("printf", "%d", 42);
    }
}

轉換結果：(原始結果沒有換行，為了排版才換行)
CLASS IDEN("Program") LBRACE VOID IDEN("main") LPAREN RPAREN LBRACE
CALLOUT LPAREN STR("printf") COMMA STR("%d") COMMA NUM(42) RPAREN
SEMI RBRACE RBRACE

在這個講義中，有趣的是，本來要用手寫的 scanner，後來可用 JLex 產生。

到了 parser 的階段，parse algorithm 有幾種，分類的方法也有好幾種。
按照處理 input 及 derivation 的方向來分，傳統的有 LL，LR。
按照組成 tree 的順序來分，有 top-down 及 bottom-up。
按照處理 transition 的方法來分，有 tabular 及 non-tabular。(註6)
按照 parser code 是誰寫的有分，hand-made 及 generator。

<----
(註6)：http://people.few.eur.nl/pijls/parsing.pdf
---->

LL parser指的是從左邊開始處理字元(parse from left)，
從左邊開始建構(construct leftmost derivation)，
它自然就是屬於 top-down parser。
這種的 parser 可以使用 recursive descent，程式碼可用人來寫。
也可以轉化 grammer 成 parsing table 來查詢。
parsing table 可用手工或是用 generator 產生。
LL recursive descent 這種方法可以處理的 language
只是 context-free language 的一部份子集而不是全部，
因此有強化版本的 LL(k)版本，這種方法，會先偷看下 k 個輸入來判斷 state，
大多教科書舉例都是 LL(1) 的。
但是 LL(k) 仍然無法滿足所有的 context-free language。
(再延申下去還有LL(*)，使用 regular expression 檢查下個 input)
兩種 LL parser 在製作 grammer 的時候，要注意 left recursion 的問題，
有固定的方法重排 grammer 以解決這個問題。
否則會出現 conflicts 的問題。
因為 LL 的 parser 處理邏輯非常直覺，教學上常會拿來當作範例，
容易用人來寫，也比較容易被人看懂。
(當然也有用 parser generator 產生的 LL parser。)

另一種傳統是 LR parser，從左邊開始處理字元(parse from left)，
從右邊開始建構(construct rightmost derivation)，
是屬於 bottom-up parser。
這種的 parser 可以使用 recursive ascent
但是大多數的實作上都是使用 generator 產生 parsing table，
所以大多數的是 tabular parser。
LR 在不進行偷看動作(lookahead)的時候(也就是 LR(0))，處理的 language 就比較廣，
但是還是會遇到無法處理的 grammer。
LR 的 parser 的程式碼相對比較複雜，比較難用人來寫，
同時 parser 的錯誤與 grammer 的錯誤比較難分別，
在 parse input 的時候可以產生比較清楚的錯誤訊息，但是難在 parser 要判斷發生哪種錯誤。(註7)

<----
(註7)：http://en.wikipedia.org/wiki/LR_parser
---->