Golang 编译原理计算器(通俗易懂)

李海彬

发布于 2019-03-07 10:56:39

1K0

发布于 2019-03-07 10:56:39

文章被收录于专栏：Golang语言社区

作者：OhBonsai 來源：简书

本文不需要你掌握任何编译原理的知识。只需要看懂简单的golang语言即可，完整的代码示例在GIT

听到编译原理，就觉得很高大上。记得上大学时，这门课要记忆一些BNF,LEX,AST,CFG这些有的没的。一个听不懂，二个没兴趣。随着使用了几门语言之后，也尝试用编译原理的基本知识写过一个sql转es的工具之后。发现其实了解一点点编译原理的知识，能够提高我们的生产效率，做出一些很酷的小工具来。

本文将用golang和编译原理的基本技术实现一个计算器。虽然功能简单，网上也有很多人做过类似事情，但这篇博客会有三个优点：

我暂时没有找到有人用golang写
我会用最直白的语言去描述我们要做什么，这样当你阅读的时候，会发现该步骤和书中哪一步是对应的，帮助你更好的理解编译原理的知识。
我会用测试驱动整个博客和代码，会让大家看到如何慢慢得演化出这个计算器得解释器。就像小说中人物的黑化有一个发酵的过程才会好看，我希望在本文中能够让读者看到一个解释器编写发酵的过程。

目标

整体会实现一个函数，输入一个String, 输出一个int64。

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

而我们的终极目标是能够让我们的calc的方法能够通过以下的测试

 1// calc_test.go
 2func TestFinal(t *testing.T) {
 3    tests := []struct{
 4        input string
 5        expected int64
 6    }{
 7        {"5", 5},
 8        {"10", 10},
 9        {"-5", -5},
10        {"-10", -10},
11        {"5 + 5 + 5 + 5 - 10", 10},
12        {"2 * 2 * 2 * 2 * 2", 32},
13        {"-50 + 100 + -50", 0},
14        {"5 * 2 + 10", 20},
15        {"5 + 2 * 10", 25},
16        {"20 + 2 * -10", 0},
17        {"50 / 2 * 2 + 10", 60},
18        {"2 * (5 + 10)", 30},
19        {"3 * 3 * 3 + 10", 37},
20        {"3 * (3 * 3) + 10", 37},
21        {"(5 + 10 * 2 + 15 / 3) * 2 + -10", 50},
22    }
23
24    for _, tt := range tests{
25        res := Calc(tt.input)
26        if res != tt.expected{
27            t.Errorf("Wrong answer, got=%d, want=%d", res, tt.expected)
28        }
29    }
30}

我们运行这个测试，毫无疑问会失败。不过没关系，我们先把这个测试放到一边，我们从编译器最简单的开始。

把句子变成一个一个单词

首先我们注意到上面的测试中，我们包含多个字符。有1-9 +-*/()，并且-在数字前面表示这是一个负数。我们现在要做一个函数，将input的输入变成一个一个单词。那么一个计算输入有多少种单词呢？我们可以区分出以下几种。值得注意的是EOF表示结束,ILLEGAL表示非法字符。

 1const (
 2    ILLEGAL = "ILLEGAL"
 3    EOF = "EOF"
 4    INT = "INT"
 5
 6    PLUS = "+"
 7    MINUS = "-"
 8    BANG = "!"
 9    ASTERISK = "*"
10    SLASH = "/"
11
12    LPAREN = "("
13    RPAREN = ")"
14)

另外我们要设计一个读取字符器，更专业的名字叫做词法分析器。他的功能就是不断的读取每一个字符，然后生成我们的词元。注意我们有两个名词了，一个叫词元，一个叫词法分析器。我们都用结构体来描述他们。另外词法分析器的核心函数是NextToken()用于获取下一个词元。

 1type Token struct {
 2    Type string  //对应我们上面的词元类型
 3    Literal string // 实际的string字符
 4}
 5
 6type Lexer struct {
 7    input string // 输入
 8    position int   // 当前位置                                                                                                                                                                                                                                                                                                                                                                                               
 9    readPosition int  // 将要读取的位置
10    ch byte //当前字符
11}
12
13func (l *Lexer) NextToken() Token {
14}

我们不着急实现。照例我们先设计我们的测试。这次我们要达到的目标是我们能够将句子分成特定的词元。

 1func TestTokenizer(t *testing.T) {
 2    input := `(5 + -10 * 2 + 15 / 3) * 2`
 3    tests := []struct {
 4        expectedType    string
 5        expectedLiteral string
 6    }{
 7        {LPAREN, "("},
 8        {INT, "5"},
 9        {PLUS, "+"},
10        {MINUS, "-"},
11        {INT, "10"},
12        {ASTERISK, "*"},
13        {INT, "2"},
14        {PLUS, "+"},
15        {INT, "15"},
16        {SLASH, "/"},
17        {INT, "3"},
18        {RPAREN, ")"},
19        {ASTERISK, "*"},
20        {INT, "2"},
21    }
22
23    l := NewLex(input)
24
25    for i, tt := range tests {
26        tok := l.NextToken()
27
28        if tok.Type != tt.expectedType {
29            t.Fatalf("tests[%d] - tokentype wrong. expected=%q, got=%q",
30                i, tt.expectedType, tok.Type)
31        }
32
33        if tok.Literal != tt.expectedLiteral {
34            t.Fatalf("tests[%d] - literal wrong. expected=%q, got=%q",
35                i, tt.expectedLiteral, tok.Literal)
36        }
37    }
38
39}

ok , 为了通过这个测试。我们来实现NextToken()这个函数，首先构建几个辅助函数。首先我们给lexer提供一个动作函数readChar。这个函数不断读取字符，并且更新结构体的值

1func (l *Lexer) readChar() {
2    if l.readPosition >= len(l.input) {
3        l.ch = 0
4    } else {
5        l.ch = l.input[l.readPosition]
6    }
7    l.position = l.readPosition
8    l.readPosition += 1
9}

另外再来一个skipWhitespace用于在读取时候直接跳过空白字符

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

其实我们读取词源挺简单的，除了像123这种几位数字，其他都是单个字符做一个词元。我们搞一个函数专门来读数字，不过我们先搞一个函数判断字符是不是数字,这里原理很简单，如果是数字不断读下一个，读到不是数字为止。

 1func isDigit(ch byte) bool {
 2    return '0' <= ch && ch <= '9'
 3}
 4
 5func (l *Lexer) readNumber() string {
 6    position := l.position
 7    for isDigit(l.ch) {
 8        l.readChar()
 9    }
10    return l.input[position:l.position]
11}

好了。我们可以开始写NextToken这个核心函数啦。其实很简单，一个switch当前字符，针对不同字符返回不同的Token结构值

 1func (l *Lexer) NextToken() Token {
 2    var tok Token
 3
 4    l.skipWhitespace()
 5
 6    switch l.ch {
 7    case '(':
 8        tok = newToken(LPAREN, l.ch)
 9    case ')':
10        tok = newToken(RPAREN, l.ch)
11    case '+':
12        tok = newToken(PLUS, l.ch)
13    case '-':
14        tok = newToken(MINUS, l.ch)
15    case '/':
16        tok = newToken(SLASH, l.ch)
17    case '*':
18        tok = newToken(ASTERISK, l.ch)
19    case 0:
20        tok.Literal = ""
21        tok.Type = EOF
22    default:
23        if isDigit(l.ch) {
24            tok.Type = INT
25            tok.Literal = l.readNumber()
26            return tok
27        } else {
28            tok = newToken(ILLEGAL, l.ch)
29        }
30    }
31
32    l.readChar()
33    return tok
34}

OK. 在运行测试，测试就通过了，每个input都变成了每个词元。接下来我们要高出一个ast用于运行。

把一个一个词元组成语法树

什么是语法/语法树

首先语法到底是什么？比如说中文中我爱你主谓宾三种词表示一个意思，而必须按照我爱你这三个字顺序来表达，而不是用爱你我这种顺序来说。这个规则便是语法。而表达的意思便是如何告诉计算机你要干什么。那什么是语法树呢？比如我们要计算机求1 + 2。你可以通过1 + 2这种中缀表达式写，或者是+ 12 这种前缀表达式来表达。但最后该语法的语言大概都会解析成一样的树

1     +
2   /    \
3   1    2

而这样的树就是语法树，表示源代码1+2或者+12的抽象语法结构。

那么计算表达式的语法是什么

首先我们定义两种情况。我们在有时候会见到这种语法++i。也就是某个操作符作为前缀与后面数字发生反应。同样还包括我们的-1。同时还有一种更加常见的情况1 + 2。操作符在中间。另外我只是是填写一个数字类似于12。这也是一个计算表达式。我们先把这三种情况都定义出来。首先统一使用一个接口。

1  type Expression interface {
2    String() string
3}

这个接口没什么特别的含义。另外我们依据上面考虑的三种情况实现三个结构体，另外都实现了String方法。

 1 type IntegerLiteralExpression struct {
 2    Token Token
 3    Value int64
 4}
 5
 6func (il *IntegerLiteralExpression) String() string { return il.Token.Literal }
 7
 8type PrefixExpression struct {
 9    Token    Token
10    Operator string
11    Right    Expression
12}
13
14func (pe *PrefixExpression) String() string {
15    var out bytes.Buffer
16
17    out.WriteString("(")
18    out.WriteString(pe.Operator)
19    out.WriteString(pe.Right.String())
20    out.WriteString(")")
21
22    return out.String()
23}
24
25type InfixExpression struct {
26    Token    Token
27    Left     Expression
28    Operator string
29    Right    Expression
30}
31
32func (ie *InfixExpression) String() string {
33    var out bytes.Buffer
34
35    out.WriteString("(")
36    out.WriteString(ie.Left.String())
37    out.WriteString(" ")
38    out.WriteString(ie.Operator)
39    out.WriteString(" ")
40    out.WriteString(ie.Right.String())
41    out.WriteString(")")
42
43    return out.String()
44}

解析器

我们定义完了上面几种expression情况。接下来用一个结构parser来把我们的字符串变成expression。parser里面包含我们上一步的lexer。以及存储error的数组。当前的词元和下一个词元。另外针对于上面提到的两种不同的expression。利用不同的处理方法。

 1type Parser struct {
 2    l *lexer.Lexer
 3    errors []string
 4    curToken token.Token
 5    peekToken token.Token
 6    prefixParseFns map[token.TokenType]prefixParseFn
 7    infixParseFns map[token.TokenType]infixParseFn
 8}
 9
10// 往结构体里面筛处理方法
11func (p *Parser) registerPrefix(tokenType token.TokenType, fn prefixParseFn) {
12  p.prefixParseFns[tokenType] = fn
13}
14func (p *Parser) registerInfix(tokenType token.TokenType, fn infixParseFn) {
15  p.infixParseFns[tokenType] = fn
16}

另外我们的核心函数是将lexer要变成ast，这个核心函数是ParseExpression

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

测试

好啦，准备工作已经做完了。那么开始写测试。我们刚才分析计算表达式只有三个语法。我们针对三个语法做三个简单测试

1. 针对单个数字例如250，我们进行以下测试。这个测试主要测试两个点，一个我们ParseExpression出来的是一个InterLieralExpression。另外一个这个AST节点的值为250。并且我们把integerLiteral的测试单独拿出来。之后可以服用

 1func TestIntegerLiteralExpression(t *testing.T) {
 2    input := "250"
 3    var expectValue int64 = 250
 4
 5    l := NewLex(input)
 6    p := NewParser(l)
 7
 8
 9    checkParseErrors(t, p)
10    expression := p.ParseExpression(LOWEST)
11    testInterLiteral(t, expression, expectValue)
12}
13
14
15func testInterLiteral(t *testing.T, il Expression, value int64) bool {
16    integ, ok := il.(*IntegerLiteralExpression)
17    if !ok {
18        t.Errorf("il not *ast.IntegerLiteral. got=%T", il)
19        return false
20    }
21
22    if integ.Value != value {
23        t.Errorf("integ.Value not %d. got=%d", value, integ.Value)
24        return false
25    }
26    return true
27}

2. 针对前缀表达式例如-250, 我们进行一下测试. 这个测试主要测试两个点，一个我们ParseExpression出来的右值是InterLieralExpression。操作符是-

 1func TestParsingPrefixExpression(t *testing.T) {
 2    input := "-15"
 3    expectedOp := "-"
 4    var expectedValue int64 =  15
 5
 6
 7    l := NewLex(input)
 8    p := NewParser(l)
 9    checkParseErrors(t, p)
10
11    expression := p.ParseExpression(LOWEST)
12    exp, ok := expression.(*PrefixExpression)
13
14    if !ok {
15        t.Fatalf("stmt is not PrefixExpression, got=%T", exp)
16    }
17
18    if exp.Operator != expectedOp {
19        t.Fatalf("exp.Operator is not %s, go=%s", expectedOp, exp.Operator)
20    }
21
22    testInterLiteral(t, exp.Right, expectedValue)
23}

3. 对于中缀表达式如5+5,进行如下测试，当然我们加减乘除都测试一遍

 1func TestParsingInfixExpression(t *testing.T) {
 2    infixTests := []struct{
 3        input string
 4        leftValue int64
 5        operator string
 6        rightValue int64
 7    }{
 8        {"5 + 5;", 5, "+", 5},
 9        {"5 - 5;", 5, "-", 5},
10        {"5 * 5;", 5, "*", 5},
11        {"5 / 5;", 5, "/", 5},
12    }
13
14    for _, tt := range infixTests {
15        l := NewLex(tt.input)
16        p := NewParser(l)
17        checkParseErrors(t, p)
18
19        expression := p.ParseExpression(LOWEST)
20        exp, ok := expression.(*InfixExpression)
21
22        if !ok {
23            t.Fatalf("exp is not InfixExpression, got=%T", exp)
24        }
25
26        if exp.Operator != tt.operator {
27            t.Fatalf("exp.Operator is not %s, go=%s", tt.operator, exp.Operator)
28        }
29
30        testInterLiteral(t, exp.Left, tt.leftValue)
31        testInterLiteral(t, exp.Right, tt.rightValue)
32    }
33}

实现

上面测试写完了，我们就要开始实现了。首先想象一下，我们将input变成了一个一个的词元，接下来我们对于一个又一个的词元进行处理。我们用到的算法叫做pratt parser。这里具体不展开来讲，有兴趣自己阅读。对于每一个词元，我们都有两个函数去处理她infixParse或者prefixParse。选择哪个函数取决于你在哪个位置。首先我们写一个初始化的函数newParser。

 1func NewParser(l *Lexer) *Parser {
 2    p := &Parser{
 3        l:      l,
 4        errors: []string{},
 5    }
 6
 7    p.prefixParseFns = make(map[string]prefixParseFn)
 8    p.infixParseFns = make(map[string]infixParseFn)
 9
10    p.nextToken()
11    p.nextToken()
12    return p
13}

当遇到Integer Token

考虑当我们遇到IntegerExpression时候，就是250 这样当都一个字符。我们注册一下这种情况的处理函数p.registerPrefix(INT, p.parseIntegerLiteral)。处理函数这里非常简单，我们直接返回一个IntegerLiteralExpression。

 1func (p *Parser) parseIntegerLiteral() Expression {
 2
 3    lit := &IntegerLiteralExpression{Token: p.curToken}
 4
 5    value, err := strconv.ParseInt(p.curToken.Literal, 0, 64)
 6    if err != nil {
 7        msg := fmt.Sprintf("could not parse %q as integer", p.curToken.Literal)
 8        p.errors = append(p.errors, msg)
 9        return nil
10    }
11
12    lit.Value = value
13    return lit
14}
15
16// 在newParser里面加上

**当遇到`+-*/` Token**

我们支持-5 这种形式。同时我们支持5 -1这种形式。我们在newParser里面注册两个处理函数。同样我们遇到+ * /其他三个token。采用parseInfixExpression

1// func NewParser
2    p.registerPrefix(MINUS, p.parsePrefixExpression)
3
4    p.registerInfix(MINUS, p.parseInfixExpression)
5
6    p.registerInfix(PLUS, p.parseInfixExpression)
7    p.registerInfix(MINUS, p.parseInfixExpression)
8    p.registerInfix(SLASH, p.parseInfixExpression)
9    p.registerInfix(ASTERISK, p.parseInfixExpression)

如何实现parsePrefixExpression很简单，获取当前Token。也就是-。下一个TOken是数字。我们递归使用ParseExpression解析出来。不出错的话。这里解析出来的是一个IntegerLiteral

 1func (p *Parser) parsePrefixExpression() Expression {
 2
 3    expression := &PrefixExpression{
 4        Token:    p.curToken,
 5        Operator: p.curToken.Literal,
 6    }
 7    p.nextToken()
 8    expression.Right = p.ParseExpression(PREFIX)
 9    return expression
10}

parseInfixExpression差不多情况。但是有一个输入参数left。比如1 + 2。1就是left

 1func (p *Parser) parseInfixExpression(left Expression) Expression {
 2
 3    expression := &InfixExpression{
 4        Token:    p.curToken,
 5        Operator: p.curToken.Literal,
 6        Left:     left,
 7    }
 8
 9    precedence := p.curPrecedence()
10    p.nextToken()
11
12    expression.Right = p.ParseExpression(precedence)
13
14    return expression
15}

优先级

考虑这样一种情况1 + 3 * 4。如果解析成语法树。我们可以有两种解法

1            * 
2         /      \
3        +       4
4      /    \
5     1      3

1            + 
2         /      \
3        1       *
4               /    \
5             3      4

按照我们小学教育，我们应该选择下面的解法。也就是说乘法比加法要有更高的优先级。或者说在我们的语法树中乘法要比加法处于更高的位置。我们定义出以下几个级别的优先级，与各符号对应的优先级

 1      const (
 2    _ int = iota
 3    LOWEST
 4    SUM         // +, -
 5    PRODUCT     // *, /
 6    PREFIX      // -X
 7    CALL        // (X)
 8)
 9
10var precedences = map[string]int{
11    PLUS:     SUM,
12    MINUS:    SUM,
13    SLASH:    PRODUCT,
14    ASTERISK: PRODUCT,
15    LPAREN:   CALL,
16}

当遇到`（）` Token

我们支持(1 + 5) * 3 这种形式。这个时候我们强制提升了1 + 5的优先级。我们采用一个处理函数parseGroupedExpression

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

如何实现用()来提升优先级，其实就是强制读取()内的内容

1func (p *Parser) parseGroupedExpression() Expression {
2    p.nextToken()
3    exp := p.ParseExpression(LOWEST)
4
5    if !p.expectPeek(token.RPAREN){
6        return nil
7    }
8    return exp
9}

递归主函数`ParseExpression`

我们通过当前优先级和下一个token的优先级进行对比，如果这个优先级比下一个优先级别低，那就变成infix。用parseInfixExpression处理。如果这个优先级等于或者比下一个优先级高，那就变成了prefix。用parsePrefixExpression处理

 1func (p *Parser) ParseExpression(precedence int) Expression {
 2    prefix := p.prefixParseFns[p.curToken.Type]
 3    returnExp := prefix()
 4
 5    for precedence < p.peekPrecedence() {
 6        infix := p.infixParseFns[p.peekToken.Type]
 7        if infix == nil {
 8            return returnExp
 9        }
10
11        p.nextToken()
12        returnExp = infix(returnExp)
13    }
14
15    return returnExp
16}

当然还有一些辅助函数，这里不再赘述。运行一下测试，?通过啦

执行语法树得到结果

这里我们直接要开始搞定我们最开始的测试啦。首先我们丰富一下主函数。

1func Calc(input string) int64 {
2    lexer := NewLex(input)
3    parser := NewParser(lexer)
4
5    exp := parser.ParseExpression(LOWEST)
6    return Eval(exp)
7}

关键就是我们的Eval函数啦。这里很简单，因为我们有三种Expression。对于不同的Expression做不同的处理方法

 1func Eval(exp Expression) int64 {
 2    switch node := exp.(type) {
 3    case *IntegerLiteralExpression:
 4        return node.Value
 5    case *PrefixExpression:
 6        rightV := Eval(node.Right)
 7        return evalPrefixExpression(node.Operator, rightV)
 8    case *InfixExpression:
 9        leftV := Eval(node.Left)
10        rightV := Eval(node.Right)
11        return evalInfixExpression(leftV, node.Operator, rightV)
12    }
13
14    return 0
15}
16
17func evalPrefixExpression(operator string, right int64) int64{
18    if operator != "-" {
19        return 0
20    }
21    return -right
22}
23
24
25func evalInfixExpression(left int64, operator string, right int64) int64 {
26
27    switch operator {
28    case "+":
29        return left + right
30    case "-":
31        return left - right
32    case "*":
33        return left * right
34    case "/":
35        if right != 0{
36            return left / right
37        }else{
38            return 0
39        }
40    default:
41        return 0
42    }
43}

在运行一下测试，搞定。。。

总结

当然这里有很多东西没讲述，比如错误处理。但是我相信从上面走下来，比较容易理解编译原理的一些概念。

版权申明：内容来源网络，版权归原创者所有。除非无法确认，我们都会标明作者及出处，如有侵权烦请告知，我们会立即删除并表示歉意。谢谢。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-02-13，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 Golang语言社区微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度