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

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

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

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

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

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

<pre><code class="lang-go hljs">// calc.go func calc(input string) int64 { } </code></code></pre>

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

<pre><code class="lang-go hljs">// 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) } } } </code></code></pre>

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

<h2>把句子变成一个一个单词</h2>

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

<pre><code class="lang-go hljs">const ( ILLEGAL = "ILLEGAL" EOF = "EOF" INT = "INT" PLUS = " " MINUS = "-" BANG = "!" ASTERISK = "*" SLASH = "/" LPAREN = "(" RPAREN = ")" ) </code></code></pre>

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

<pre><code class="lang-go hljs">type Token struct { Type string //对应我们上面的词元类型 Literal string // 实际的string字符 } type Lexer struct { input string // 输入 position int // 当前位置 readPosition int // 将要读取的位置 ch byte //当前字符 } func (l *Lexer) NextToken() Token { } </code></code></pre>

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

<pre><code class="lang-go hljs">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) } } } </code></code></pre>

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

<pre><code class="lang-go hljs">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 } </code></code></pre>

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

<pre><code class="lang-go hljs">func (l *Lexer) skipWhitespace() { for l.ch == ' ' || l.ch == '\t' || l.ch == '\n' || l.ch == '\r' { l.readChar() } } </code></code></pre>

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

<pre><code class="lang-go hljs">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] } </code></code></pre>

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

<pre><code class="lang-go hljs">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 } </code></code></pre>

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

<h2>把一个一个词元组成语法树</h2> <h3>什么是语法/语法树</h3>

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

<pre><code class="lang-go hljs"> / \ 1 2 </code></code></pre>

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

<h3>那么计算表达式的语法是什么</h3>

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

<pre><code class="lang-go hljs">type Expression interface { String() string } </code></code></pre>

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

<pre><code class="lang-go hljs">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() } </code></code></pre> <h3>解析器</h3>

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

<pre><code class="lang-go hljs">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 } </code></code></pre>

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

<pre><code class="lang-go hljs">func (p *Parser) ParseExpression(precedence int) Expression { } </code></code></pre> <h3>测试</h3>

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

<ol><li>针对单个数字例如<code>250</code>，我们进行以下测试。这个测试主要测试两个点，一个我们<code>ParseExpression</code>出来的是一个<code>InterLieralExpression</code>。另外一个这个<code>AST</code>节点的值为<code>250</code>。并且我们把<code>integerLiteral</code>的测试单独拿出来。之后可以服用</li> </ol><pre><code class="lang-go hljs">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 } </code></code></pre> <ol start="2"><li>针对前缀表达式例如<code>-250</code>, 我们进行一下测试. 这个测试主要测试两个点，一个我们<code>ParseExpression</code>出来的右值是<code>InterLieralExpression</code>。操作符是<code>-</code> </li> </ol><pre><code class="lang-go hljs">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) } </code></code></pre> <ol start="3"><li>对于中缀表达式如<code>5 5</code>,进行如下测试，当然我们加减乘除都测试一遍</li> </ol><pre><code class="lang-go hljs">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) } } </code></code></pre> <h3>实现</h3>

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

<pre><code class="lang-go hljs">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 } </code></code></pre> <h4>当遇到Integer Token</h4>

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

<pre><code class="lang-go hljs">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里面加上 </code></code></pre> <h4>当遇到<code> -*/</code> Token</h4>

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

<pre><code class="lang-go hljs">// 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) </code></code></pre>

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

<pre><code class="lang-go hljs">func (p *Parser) parsePrefixExpression() Expression { expression := &PrefixExpression{ Token: p.curToken, Operator: p.curToken.Literal, } p.nextToken() expression.Right = p.ParseExpression(PREFIX) return expression } </code></code></pre>

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

<pre><code class="lang-go hljs">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 } </code></code></pre> <h4>优先级</h4>

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

<pre><code class="lang-go hljs"> * / \ 4 / \ 1 3 </code></code></pre> <pre><code class="lang-go hljs"> / \ 1 * / \ 3 4 </code></code></pre>

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

<pre><code class="lang-go hljs">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, } </code></code></pre> <h4>当遇到<code>（ ）</code> Token</h4>

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

<pre><code class="lang-go hljs">// func NewParser p.registerPrefix(MINUS, p.parseGroupedExpression) </code></code></pre>

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

<pre><code class="lang-go hljs">func (p *Parser) parseGroupedExpression() Expression { p.nextToken() exp := p.ParseExpression(LOWEST) if !p.expectPeek(token.RPAREN){ return nil } return exp } </code></code></pre> <h4>递归主函数<code>ParseExpression</code> </h4>

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

<pre><code class="lang-go hljs">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 } </code></code></pre>

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

<h2>执行语法树得到结果</h2>

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

<pre><code class="lang-go hljs">func Calc(input string) int64 { lexer := NewLex(input) parser := NewParser(lexer) exp := parser.ParseExpression(LOWEST) return Eval(exp) } </code></code></pre>

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

<pre><code class="lang-go hljs">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 } } </code></code></pre>

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

<h2>总结</h2>

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