學習做一個編譯器應該怎麼開始？

我個人的學習經驗是先去找一個你用過的語言，例如C++或是Go之類的
然後找由它們實作的編譯器原始碼觀察，大致應該都能找到 lexer parser codegen(or execute-enigne)這些部份
接著找本基礎書籍來看(我推薦龍書或是Parr的程式語言實作模式)
一一對照實際程式跟理論怎麼接合的，一般來說在書裡通常只找得到殘缺的實際案例
所以找到一個優秀的實作非常重要，我認為Go本身的原始碼就非常值得閱讀
另外也有一些比較簡單的實作(如果你害怕一個大規模的編譯器很難追蹤跟看懂)
例如用Go實作的gisp，用Rust的dyon
以上專案都值得看過
Lexer的部份，我認為實作BrainFuck是非常適合的練習，我也有用Nim做了一個
因為狀態比較少，適合你專注於整體概念上，而不是被複雜的細節繞到暈頭轉向
Parser的部份我認為還是手刻比較方便，並不是說我不用工具，事實上我通常用工具
不過你是要學習，我認為工具對這階段來說並沒有意義
這部份可以嘗試寫出四則運算式的解析器
func parseDefine() *VarDefine {
    name := lex.Get()
    if name.Typ == ID {
        if lex.Get().Typ == ASSIGN {
            return &VarDefine{
                name: name,
                expr:  parseExpr(),
            }
        }
   }
}
上面的函式可以觀察出如何透過遞迴調用產生AST
AST? 我聽到你的疑問了
所謂AST就是抽象語法樹的意思，透過複數的AST互相包含(上述的變數宣告就包含運算式)抑或連貫(變數宣告就是連貫的)成為一支原始程式的中間表述法，進而簡化翻譯為目標語言的難度
因為我們可以宣告方法處理AST資料結構，然後迭代處理整個AST樹
例如函數的AST可能可以這樣定義
type FunctionAst struct {
    name string
    functionType TypeAst
    statements StatementsAst
}
func (f *Function) Codegen(module Module) {
    f := createFunction(module, name, functionType.Codegen(module))
    block := statements.Codegen(module)
    Insert(f, block)
}
可能會像這樣，不斷深入下一層的AST，直到完成翻譯工作
至於優化工作，那又是新的篇章了，期待下次介紹

ANTLR v4--入門

今天我想介紹一個強大有趣的工具--ANTLR

這個工具根據我們定義的文法產生處理原始碼的parser，當然不只是處理程式語言，你也可以用來處理其他資料

＝ 安裝

cd /usr/local/lib
sudo curl -O http://www.antlr.org/download/antlr-4.7-complete.jar
export CLASSPATH=".:/usr/local/lib/antlr-4.7-complete.jar:$CLASSPATH"
alias antlr4='java -jar /usr/local/lib/antlr-4.7-complete.jar'
alias grun='java org.antlr.v4.gui.TestRig'

之後會用到的通常是antlr4這支程式

因為它用來產生parser

＝ 開始

我們需要建立一個檔案叫xxx.g4，而裡頭的grammar就必須是grammar xxx;

舉例來說JSON.g4就會是

grammar JSON;

接下來我們談ANLTR的語法還有它如何運作

首先如果你接觸過v3以前的antlr，那麼你一定知道embbed action

不過這個版本的antlr並不需要全都使用embbed action來實現程式邏輯

反之它加入了xxxBaseListener來處理大部分的翻譯過程

你也可以選擇Visitor來實作，但是visitor需要顯式的調用Context，並不適合大型複雜的文法

Listener則能應付絕大多數的情況，它的API都是enterXxx跟exitXxx的格式，名稱相當直觀

＝ 約定

ANTLR要求Token使用大寫英文字母開頭，grammar則使用小寫

例如

NUM : [0-9]+ ;
ID : [a-z]+ ;

stat : ID '=' expr
    | expr
    ;

expr : NUM
    | ID
    ;

ID跟NUM都是token，stat跟expr則是文法規則

| 表示不同的可能

; 表示規則結束

可以看到如果我們想要辨別符號，必須用''包起來，除了符號，關鍵字也要這樣處理，像這樣

Class : 'class' ;

+ 表示一個或無限多個

* 表示沒有或無限多個

? 表示有或沒有

定義ID跟NUM時，我都使用了正規表達式來處理，這是為了方便而放入的功能

你也可以選擇

NUM : ('0' .. '9')+ ;

這種寫法

最後就是產生parser

antlr4 -Dlanguage=Cpp JSON.g4

-Dlanguage 指定產生什麼語言的parser

這裡是C++

如果不指定，那麼預設是Java

目前支援Java, C#, Python2|3, JavaScript, Go, C++, Swift

儘管選擇你習慣的那個

為什麼要學Antlr?
事實上編譯技術在很多地方都有用途
例如Firefox團隊為了加速JavaScript eval函式的執行速率，在編譯到eval時會進行預處理，讓JavaScript真的執行到這邊時已經少了許多工作
簡單一些的應用可能有：編寫DSL簡化開發工作
例如新增網路服務API，如果用特製的語言將工作進行簡化

routes:
    get "/":
        resp Page1

那麼我們實際上需要負擔的工作量就大幅縮小了吧！
而且亦便於未來的維護工作，而DSL最棒的要點就在於，我們往往無須實現完整的通用語言
比如我們可以在回傳的區塊回到Java語言

routes:
    get "/":
        @java {
            // ... Your java code
        }

這樣我們就不需要實現太過麻煩的東西
而一樣能享受DSL的方便度

lexer 原理解釋

因為Elz實在是一個遠超我一開始的預想的語言(最開始只是想了解編譯器，乾脆就開始設計新語言了)
打造花了我很多心思，Elz採用先從原始碼中取得詞素，再分析詞素的設計
這樣一來兩邊都可以降低實作的複雜度
分成lexer與parser兩大主軸工作之後，考慮到效能，我沒有採用lex這種吸引人的作法(其實一開始是有試過，最重要的問題是我覺得學那個好麻煩XD)
而是手刻這個部分，其中最重要的設計就是利用Golang的共時技巧，讓parser可以不用等待lexer的完成
這個技術的完成第一是寫出一個函數，建立一個lexer實體，接著用goroutine啟動(*lexer) run()這個函數，最後這個函數回傳這個lexer實體

run之中放著State Function迴圈
什麼是State Function? 它就是一個型別函數，不過它所指的函數回傳自己這個型別以作為狀態變遷的依據
stateFn定義如下:

type stateFn func(*Lexer) stateFn

什麼叫狀態變遷? 這樣有什麼好處?
讓我們回顧Lexer的原理，它接收一個字元串流，根據讀到的字元進行不同的操作，以得到詞素串流
所以不同的字元就是那個狀態啦!
而傳統的做法都像下面那樣

void LexAll(int state) {
  switch(state) {
  case number:
    LexNumber();
  case alphabra:
    LexIdentifier();
  // ...
  }
}

重複不斷的程式碼，而且我們一直在呼叫函數
那何不傳回我們想執行的下一個函式?
這就是State Function所想要表達的意思

func lexWhiteSpace(l *Lexer) stateFn {
    for r := l.next(); isSpace(r) || r=='\n'; l.next() {
        r = l.peek()
    }
    l.backup() // break mount's rune is not a space
    l.ignore() // because no emit, we need ignore will mount's pos runes

    switch r := l.next(); {
    case r == EOF:
        l.emit(ItemEOF)
        return nil
        // ...
    case r == '=':
        return lexEqualOp // =, ==
    case r == ':':
        l.emit(ItemColon)
        return lexWhiteSpace
    case r == '"' || r == '`' || r == '\'':
        return lexString // "string literal", `string literal`
    case '0' <= r && r <= '9':
        return lexNumber // 12323, 2.344
    case isAlphaNumeric(r):
        return lexIdentifiers // car, car_build
    default:
        panic(fmt.Sprintf("Don't know how to do with: %q", r))
    }
}

這是作為初始狀態的狀態函數內部實作(省略沒有辦法幫助你理解它的部分)

再看lexNumber

func lexNumber(l *Lexer) stateFn {
    firstDot := true
    for r := l.next(); ( '0' <= r && r <= '9' ) || r == '.'; r = l.next() {
        if r == '.' {
            if firstDot {
                firstDot = false
            } else {
                break
            }
        }
    }
    l.backup()

    l.emit(ItemNumber)
    return lexWhiteSpace
}

發現了嗎? 只要回傳初始狀態函數
由於我們不斷執行下一個狀態函數，所以我們就回到初始狀態了，而且不需要初始狀態碼跟初始狀態用的函數兩個東西來完成它

這時我們就要回到run的實現了
看看它有多麼的簡單

func (l *Lexer) run() {
    for l.state = lexWhiteSpace; l.state != nil; {
        l.state = l.state(l)
    }
    close(l.items)
}

得到一個狀態函數參考，然後執行狀態函數，就這麼簡單
// l.state是一個stateFn

我改用Ｃ＋＋實作了，不過這篇的技術還是很有趣，所以就留下來吧！
ps. 2017/12/29. 我現在還是用Go，只是先用antlr產生parser(開發速度)