本文不需要你掌握任何編譯原理的知識。 只需要看懂簡單的golang語言即可， 完整的代碼示例在GIT, 代碼是從writing an interpreter in go這本書抽取了簡單的部分出來, 如果需要進一步了解,請詳閱此書.

聽到編譯原理，就覺得很高大上。記得上大學時，這門課要記憶一些BNF,LEX,AST,CFG這些有的沒的。一個聽不懂，二個沒興趣。隨著使用了幾門語言之后，也嘗試用編譯原理的基本知識寫過一個sql轉es的工具之后。發(fā)現(xiàn)其實了解一點點編譯原理的知識，能夠提高我們的生產(chǎn)效率，做出一些很酷的小工具來。

本文將用golang和編譯原理的基本技術實現(xiàn)一個計算器。雖然功能簡單，網(wǎng)上也有很多人做過類似事情，但這篇博客會有三個優(yōu)點：

• 我暫時沒有找到有人用golang寫
• 我會用最直白的語言去描述我們要做什么，這樣當你閱讀的時候，會發(fā)現(xiàn)該步驟和書中哪一步是對應的，幫助你更好的理解編譯原理的知識。
• 我會用測試驅動整個博客和代碼，會讓大家看到如何慢慢得演化出這個計算器得解釋器。就像小說中人物的黑化有一個發(fā)酵的過程才會好看，我希望在本文中能夠讓讀者看到一個解釋器編寫發(fā)酵的過程。

目標

整體會實現(xiàn)一個函數(shù)，輸入一個String, 輸出一個int64。

// calc.go
func calc(input string) int64 {
}

而我們的終極目標是能夠讓我們的calc的方法能夠通過以下的測試

// calc_test.go
func TestFinal(t *testing.T) {
    tests := []struct{
        input string
        expected int64
    }{
        {"5", 5},
        {"10", 10},
        {"-5", -5},
        {"-10", -10},
        {"5 + 5 + 5 + 5 - 10", 10},
        {"2 * 2 * 2 * 2 * 2", 32},
        {"-50 + 100 + -50", 0},
        {"5 * 2 + 10", 20},
        {"5 + 2 * 10", 25},
        {"20 + 2 * -10", 0},
        {"50 / 2 * 2 + 10", 60},
        {"2 * (5 + 10)", 30},
        {"3 * 3 * 3 + 10", 37},
        {"3 * (3 * 3) + 10", 37},
        {"(5 + 10 * 2 + 15 / 3) * 2 + -10", 50},
    }

    for _, tt := range tests{
        res := Calc(tt.input)
        if res != tt.expected{
            t.Errorf("Wrong answer, got=%d, want=%d", res, tt.expected)
        }
    }
}

我們運行這個測試，毫無疑問會失敗。不過沒關系，我們先把這個測試放到一邊，我們從編譯器最簡單的開始。

把句子變成一個一個單詞

首先我們注意到上面的測試中，我們包含多個字符。有1-9 +-*/()，并且-在數(shù)字前面表示這是一個負數(shù)。我們現(xiàn)在要做一個函數(shù)，將input的輸入變成一個一個單詞。那么一個計算輸入有多少種單詞呢？我們可以區(qū)分出以下幾種。值得注意的是EOF表示結束,ILLEGAL表示非法字符。

const (
    ILLEGAL = "ILLEGAL"
    EOF = "EOF"
    INT = "INT"

    PLUS = "+"
    MINUS = "-"
    BANG = "!"
    ASTERISK = "*"
    SLASH = "/"

    LPAREN = "("
    RPAREN = ")"
)

另外我們要設計一個讀取字符器，更專業(yè)的名字叫做詞法分析器。他的功能就是不斷的讀取每一個字符，然后生成我們的詞元。注意我們有兩個名詞了，一個叫詞元，一個叫詞法分析器。我們都用結構體來描述他們。另外詞法分析器的核心函數(shù)是NextToken()用于獲取下一個詞元。

type Token struct {
    Type string  //對應我們上面的詞元類型
    Literal string // 實際的string字符
}

type Lexer struct {
    input string // 輸入
    position int   // 當前位置                                                                                                                                                                                                                                                                                                                                                                                               
    readPosition int  // 將要讀取的位置
    ch byte //當前字符
}

func (l *Lexer) NextToken() Token {
}

我們不著急實現(xiàn)。照例我們先設計我們的測試。這次我們要達到的目標是我們能夠將句子分成特定的詞元。

func TestTokenizer(t *testing.T) {
    input := `(5 + -10 * 2 + 15 / 3) * 2`
    tests := []struct {
        expectedType    string
        expectedLiteral string
    }{
        {LPAREN, "("},
        {INT, "5"},
        {PLUS, "+"},
        {MINUS, "-"},
        {INT, "10"},
        {ASTERISK, "*"},
        {INT, "2"},
        {PLUS, "+"},
        {INT, "15"},
        {SLASH, "/"},
        {INT, "3"},
        {RPAREN, ")"},
        {ASTERISK, "*"},
        {INT, "2"},
    }

    l := NewLex(input)

    for i, tt := range tests {
        tok := l.NextToken()

        if tok.Type != tt.expectedType {
            t.Fatalf("tests[%d] - tokentype wrong. expected=%q, got=%q",
                i, tt.expectedType, tok.Type)
        }

        if tok.Literal != tt.expectedLiteral {
            t.Fatalf("tests[%d] - literal wrong. expected=%q, got=%q",
                i, tt.expectedLiteral, tok.Literal)
        }
    }

}

ok , 為了通過這個測試。我們來實現(xiàn)NextToken()這個函數(shù)，首先構建幾個輔助函數(shù)。
首先我們給lexer提供一個動作函數(shù)readChar。這個函數(shù)不斷讀取字符，并且更新結構體的值

func (l *Lexer) readChar() {
    if l.readPosition >= len(l.input) {
        l.ch = 0
    } else {
        l.ch = l.input[l.readPosition]
    }
    l.position = l.readPosition
    l.readPosition += 1
}

另外再來一個skipWhitespace用于在讀取時候直接跳過空白字符

func (l *Lexer) skipWhitespace() {
    for l.ch == ' ' || l.ch == '\t' || l.ch == '\n' || l.ch == '\r' {
        l.readChar()
    }
}

其實我們讀取詞源挺簡單的，除了像123這種幾位數(shù)字，其他都是單個字符做一個詞元。我們搞一個函數(shù)專門來讀數(shù)字，不過我們先搞一個函數(shù)判斷字符是不是數(shù)字,這里原理很簡單，如果是數(shù)字不斷讀下一個，讀到不是數(shù)字為止。

func isDigit(ch byte) bool {
    return '0' <= ch && ch <= '9'
}

func (l *Lexer) readNumber() string {
    position := l.position
    for isDigit(l.ch) {
        l.readChar()
    }
    return l.input[position:l.position]
}

好了。我們可以開始寫NextToken這個核心函數(shù)啦。其實很簡單，一個switch當前字符，針對不同字符返回不同的Token結構值

func (l *Lexer) NextToken() Token {
    var tok Token

    l.skipWhitespace()

    switch l.ch {
    case '(':
        tok = newToken(LPAREN, l.ch)
    case ')':
        tok = newToken(RPAREN, l.ch)
    case '+':
        tok = newToken(PLUS, l.ch)
    case '-':
        tok = newToken(MINUS, l.ch)
    case '/':
        tok = newToken(SLASH, l.ch)
    case '*':
        tok = newToken(ASTERISK, l.ch)
    case 0:
        tok.Literal = ""
        tok.Type = EOF
    default:
        if isDigit(l.ch) {
            tok.Type = INT
            tok.Literal = l.readNumber()
            return tok
        } else {
            tok = newToken(ILLEGAL, l.ch)
        }
    }

    l.readChar()
    return tok
}

OK. 在運行測試，測試就通過了，每個input都變成了每個詞元。接下來我們要高出一個ast用于運行。

把一個一個詞元組成語法樹

什么是語法/語法樹

首先語法到底是什么？比如說中文中我愛你主謂賓三種詞表示一個意思，而必須按照我愛你這三個字順序來表達，而不是用愛你我這種順序來說。這個規(guī)則便是語法。而表達的意思便是如何告訴計算機你要干什么。
那什么是語法樹呢？比如我們要計算機求1 + 2。你可以通過1 + 2這種中綴表達式寫，或者是+ 12 這種前綴表達式來表達。但最后該語法的語言大概都會解析成一樣的樹

     +
   /    \
   1    2

而這樣的樹就是語法樹，表示源代碼1+2或者+12的抽象語法結構。

那么計算表達式的語法是什么

首先我們定義兩種情況。我們在有時候會見到這種語法++i。也就是某個操作符作為前綴與后面數(shù)字發(fā)生反應。同樣還包括我們的-1。同時還有一種更加常見的情況1 + 2。操作符在中間。另外我只是是填寫一個數(shù)字類似于12。這也是一個計算表達式。 我們先把這三種情況都定義出來。
首先統(tǒng)一使用一個接口。

type Expression interface {
    String() string
}

這個接口沒什么特別的含義。另外我們依據(jù)上面考慮的三種情況實現(xiàn)三個結構體，另外都實現(xiàn)了String方法。

type IntegerLiteralExpression struct {
    Token Token
    Value int64
}

func (il *IntegerLiteralExpression) String() string { return il.Token.Literal }

type PrefixExpression struct {
    Token    Token
    Operator string
    Right    Expression
}

func (pe *PrefixExpression) String() string {
    var out bytes.Buffer

    out.WriteString("(")
    out.WriteString(pe.Operator)
    out.WriteString(pe.Right.String())
    out.WriteString(")")

    return out.String()
}

type InfixExpression struct {
    Token    Token
    Left     Expression
    Operator string
    Right    Expression
}

func (ie *InfixExpression) String() string {
    var out bytes.Buffer

    out.WriteString("(")
    out.WriteString(ie.Left.String())
    out.WriteString(" ")
    out.WriteString(ie.Operator)
    out.WriteString(" ")
    out.WriteString(ie.Right.String())
    out.WriteString(")")

    return out.String()
}

解析器

我們定義完了上面幾種expression情況。接下來用一個結構parser來把我們的字符串變成expression。parser里面包含我們上一步的lexer。以及存儲error的數(shù)組。當前的詞元和下一個詞元。另外針對于上面提到的兩種不同的expression。利用不同的處理方法。

type Parser struct {
    l *lexer.Lexer
    errors []string
    curToken token.Token
    peekToken token.Token
    prefixParseFns map[token.TokenType]prefixParseFn
    infixParseFns map[token.TokenType]infixParseFn
}

// 往結構體里面篩處理方法
func (p *Parser) registerPrefix(tokenType token.TokenType, fn prefixParseFn) {
  p.prefixParseFns[tokenType] = fn
}
func (p *Parser) registerInfix(tokenType token.TokenType, fn infixParseFn) {
  p.infixParseFns[tokenType] = fn
}

另外我們的核心函數(shù)是將lexer要變成ast，這個核心函數(shù)是ParseExpression

func (p *Parser) ParseExpression(precedence int) Expression {
}

測試

好啦，準備工作已經(jīng)做完了。那么開始寫測試。我們剛才分析計算表達式只有三個語法。我們針對三個語法做三個簡單測試

1. 針對單個數(shù)字例如250，我們進行以下測試。這個測試主要測試兩個點，一個我們ParseExpression出來的是一個InterLieralExpression。另外一個這個AST節(jié)點的值為250。并且我們把integerLiteral的測試單獨拿出來。之后可以服用

func TestIntegerLiteralExpression(t *testing.T) {
    input := "250"
    var expectValue int64 = 250

    l := NewLex(input)
    p := NewParser(l)


    checkParseErrors(t, p)
    expression := p.ParseExpression(LOWEST)
    testInterLiteral(t, expression, expectValue)
}

 
func testInterLiteral(t *testing.T, il Expression, value int64) bool {
    integ, ok := il.(*IntegerLiteralExpression)
    if !ok {
        t.Errorf("il not *ast.IntegerLiteral. got=%T", il)
        return false
    }

    if integ.Value != value {
        t.Errorf("integ.Value not %d. got=%d", value, integ.Value)
        return false
    }
    return true
}

2. 針對前綴表達式例如-250, 我們進行一下測試. 這個測試主要測試兩個點，一個我們ParseExpression出來的右值是InterLieralExpression。操作符是-

func TestParsingPrefixExpression(t *testing.T) {
    input := "-15"
    expectedOp := "-"
    var expectedValue int64 =  15


    l := NewLex(input)
    p := NewParser(l)
    checkParseErrors(t, p)

    expression := p.ParseExpression(LOWEST)
    exp, ok := expression.(*PrefixExpression)

    if !ok {
        t.Fatalf("stmt is not PrefixExpression, got=%T", exp)
    }

    if exp.Operator != expectedOp {
        t.Fatalf("exp.Operator is not %s, go=%s", expectedOp, exp.Operator)
    }

    testInterLiteral(t, exp.Right, expectedValue)
}

3. 對于中綴表達式如5+5,進行如下測試，當然我們加減乘除都測試一遍

func TestParsingInfixExpression(t *testing.T) {
    infixTests := []struct{
        input string
        leftValue int64
        operator string
        rightValue int64
    }{
        {"5 + 5;", 5, "+", 5},
        {"5 - 5;", 5, "-", 5},
        {"5 * 5;", 5, "*", 5},
        {"5 / 5;", 5, "/", 5},
    }

    for _, tt := range infixTests {
        l := NewLex(tt.input)
        p := NewParser(l)
        checkParseErrors(t, p)

        expression := p.ParseExpression(LOWEST)
        exp, ok := expression.(*InfixExpression)

        if !ok {
            t.Fatalf("exp is not InfixExpression, got=%T", exp)
        }

        if exp.Operator != tt.operator {
            t.Fatalf("exp.Operator is not %s, go=%s", tt.operator, exp.Operator)
        }

        testInterLiteral(t, exp.Left, tt.leftValue)
        testInterLiteral(t, exp.Right, tt.rightValue)
    }
}

實現(xiàn)

上面測試寫完了，我們就要開始實現(xiàn)了。首先想象一下，我們將input變成了一個一個的詞元， 接下來我們對于一個又一個的詞元進行處理。我們用到的算法叫做pratt parser。這里具體不展開來講，有興趣自己閱讀。對于每一個詞元，我們都有兩個函數(shù)去處理她infixParse或者prefixParse。選擇哪個函數(shù)取決于你在哪個位置。首先我們寫一個初始化的函數(shù)newParser。

func NewParser(l *Lexer) *Parser {
    p := &Parser{
        l:      l,
        errors: []string{},
    }

    p.prefixParseFns = make(map[string]prefixParseFn)
    p.infixParseFns = make(map[string]infixParseFn)

    p.nextToken()
    p.nextToken()
    return p
}

當遇到Integer Token

考慮當我們遇到IntegerExpression時候，就是250 這樣當都一個字符。我們注冊一下這種情況的處理函數(shù)p.registerPrefix(INT, p.parseIntegerLiteral)。 處理函數(shù)這里非常簡單，我們直接返回一個IntegerLiteralExpression。

func (p *Parser) parseIntegerLiteral() Expression {

    lit := &IntegerLiteralExpression{Token: p.curToken}

    value, err := strconv.ParseInt(p.curToken.Literal, 0, 64)
    if err != nil {
        msg := fmt.Sprintf("could not parse %q as integer", p.curToken.Literal)
        p.errors = append(p.errors, msg)
        return nil
    }

    lit.Value = value
    return lit
}

// 在newParser里面加上

當遇到+-*/ Token

我們支持-5 這種形式。同時我們支持5 -1這種形式。我們在newParser里面注冊兩個處理函數(shù)。同樣我們遇到+ * /其他三個token。采用parseInfixExpression

// func NewParser
    p.registerPrefix(MINUS, p.parsePrefixExpression)

    p.registerInfix(MINUS, p.parseInfixExpression)

    p.registerInfix(PLUS, p.parseInfixExpression)
    p.registerInfix(MINUS, p.parseInfixExpression)
    p.registerInfix(SLASH, p.parseInfixExpression)
    p.registerInfix(ASTERISK, p.parseInfixExpression)

如何實現(xiàn)parsePrefixExpression很簡單，獲取當前Token。也就是-。下一個TOken是數(shù)字。我們遞歸使用ParseExpression解析出來。不出錯的話。這里解析出來的是一個IntegerLiteral

func (p *Parser) parsePrefixExpression() Expression {

    expression := &PrefixExpression{
        Token:    p.curToken,
        Operator: p.curToken.Literal,
    }
    p.nextToken()
    expression.Right = p.ParseExpression(PREFIX)
    return expression
}

parseInfixExpression差不多情況。但是有一個輸入?yún)?shù)left。比如1 + 2。1就是left

func (p *Parser) parseInfixExpression(left Expression) Expression {

    expression := &InfixExpression{
        Token:    p.curToken,
        Operator: p.curToken.Literal,
        Left:     left,
    }

    precedence := p.curPrecedence()
    p.nextToken()

    expression.Right = p.ParseExpression(precedence)

    return expression
}

優(yōu)先級

考慮這樣一種情況1 + 3 * 4。如果解析成語法樹。我們可以有兩種解法

            * 
         /      \
        +       4
      /    \
     1      3

            + 
         /      \
        1       *
               /    \
             3      4
  

按照我們小學教育，我們應該選擇下面的解法。也就是說乘法比加法要有更高的優(yōu)先級?；蛘哒f在我們的語法樹中乘法要比加法處于更高的位置。我們定義出以下幾個級別的優(yōu)先級，與各符號對應的優(yōu)先級

const (
    _ int = iota
    LOWEST
    SUM         // +, -
    PRODUCT     // *, /
    PREFIX      // -X
    CALL        // (X)
)

var precedences = map[string]int{
    PLUS:     SUM,
    MINUS:    SUM,
    SLASH:    PRODUCT,
    ASTERISK: PRODUCT,
    LPAREN:   CALL,
}

當遇到（ ） Token

我們支持(1 + 5) * 3 這種形式。這個時候我們強制提升了1 + 5的優(yōu)先級。我們采用一個處理函數(shù)parseGroupedExpression

// func NewParser
    p.registerPrefix(MINUS, p.parseGroupedExpression)

如何實現(xiàn)用()來提升優(yōu)先級，其實就是強制讀取()內(nèi)的內(nèi)容

func (p *Parser) parseGroupedExpression() Expression {
    p.nextToken()
    exp := p.ParseExpression(LOWEST)

    if !p.expectPeek(token.RPAREN){
        return nil
    }
    return exp
}

遞歸主函數(shù)ParseExpression

我們通過當前優(yōu)先級和下一個token的優(yōu)先級進行對比，如果這個優(yōu)先級比下一個優(yōu)先級別低，那就變成infix。用parseInfixExpression處理。如果這個優(yōu)先級等于或者比下一個優(yōu)先級高，那就變成了prefix。用parsePrefixExpression處理

func (p *Parser) ParseExpression(precedence int) Expression {
    prefix := p.prefixParseFns[p.curToken.Type]
    returnExp := prefix()

    for precedence < p.peekPrecedence() {
        infix := p.infixParseFns[p.peekToken.Type]
        if infix == nil {
            return returnExp
        }

        p.nextToken()
        returnExp = infix(returnExp)
    }

    return returnExp
}

當然還有一些輔助函數(shù)，這里不再贅述。運行一下測試，??通過啦

執(zhí)行語法樹得到結果

這里我們直接要開始搞定我們最開始的測試啦。首先我們豐富一下主函數(shù)。

func Calc(input string) int64 {
    lexer := NewLex(input)
    parser := NewParser(lexer)

    exp := parser.ParseExpression(LOWEST)
    return Eval(exp)
}

關鍵就是我們的Eval函數(shù)啦。這里很簡單，因為我們有三種Expression。對于不同的Expression做不同的處理方法

func Eval(exp Expression) int64 {
    switch node := exp.(type) {
    case *IntegerLiteralExpression:
        return node.Value
    case *PrefixExpression:
        rightV := Eval(node.Right)
        return evalPrefixExpression(node.Operator, rightV)
    case *InfixExpression:
        leftV := Eval(node.Left)
        rightV := Eval(node.Right)
        return evalInfixExpression(leftV, node.Operator, rightV)
    }

    return 0
}

func evalPrefixExpression(operator string, right int64) int64{
    if operator != "-" {
        return 0
    }
    return -right
}


func evalInfixExpression(left int64, operator string, right int64) int64 {

    switch operator {
    case "+":
        return left + right
    case "-":
        return left - right
    case "*":
        return left * right
    case "/":
        if right != 0{
            return left / right
        }else{
            return 0
        }
    default:
        return 0
    }
}

在運行一下測試，搞定。。。

總結

當然這里有很多東西沒講述，比如錯誤處理。但是我相信從上面走下來，比較容易理解編譯原理的一些概念。