个人看法，我认为解析表达式是我写解析器最有意思的部分。作为我们仅仅看到的，解析语句是相当直观。我们通过“左到右”tokens，期望或拒绝下一个token，如果一切合适我们将返回一个AST节点。
解析表达式，在另一方面，包含了更多挑战。运算符优先级可能是第一个想到的，最好用一个例子来说明。让我们说我们要解析以下算数表达式：
5 * 5 + 10我们在这里想要一个表达式像这样的AST:
((5 * 5) + 10)也就是说，5 * 5在AST里需要变得更深并且在添加之前进行评估。为了生产一个看起来像这样的AST，解析器已经知道操作运算符*比+更高有优先级。这是对操作运算符最常见的例子了，但是也有许多种同样重要的实例。考虑一下这个表达式：
5 * (5 + 10)这里的括号将5和10组合在一起，并给它们一个“优先级”,现在必须在乘法之前评估加法。那是因为括号具有比*更高的优先级。我们很快就会看到，还有一些案例优先级起着至关重要的作用。
另一个大的挑战是在表达式里有相同种类的tokens能发生在许多位置。和这个相反，let token仅仅只能发生在let语句的开头，这使得很容易确定语句的其余部分应该是什么。现在看这个表达式：
-5 - 10这里的-操作符发生在表达式的开头，作为一个前缀操作符，并且然后作为中间的中缀运算符。此处出现了相同挑战的变体：
5 * (add(2,3) + 10)即使你可能不认识括号作为运算符，它们给我们带来了和以前例子里相同的问题。本例中的一组外括号比表示分组表达式。内部对表示“调用表达式”。token位置的有效性现在取决于上下文、前后的token以及它们的优先级。
在 Monkey 编程语言中，除了let和return语句之外，所有的东西都是一个表达式。 这些表达方式多种多样。
Monkey设计前缀运算符的表达式：
-5
!true
!false并且当然它还有中缀运算符(或中间运算符)
5 + 5
5 - 5
5 / 5
5 * 5除了这些基本的算术运算符外，还有下面的比较运算符:
foo == bar
foo != bar
foo < bar
foo > bar并且当然，作为我们之前看到的，我们能使用括号给表达式分组并影响评估顺序：
5 * (5 + 5)
((5 + 5) * 5) * 5然后是调用表达式：
add(2, 3)
add(add(2, 3), add(5, 10))
max(5, add(5, (5 * 5)))也有标识符表达式:
foo * bar / foobar
add(foo, bar)在Monkey中的函数是第一类公民，使得，函数字面量也是表达式。我们能使用let语句去绑定给函数一个名字。函数字面量仅仅只是语句中的表达式：
let add = fn(x, y) { return x + y };并且在这里我们使用一个函数字面量代替标识符:
fn(x, y) { return x + y }(5, 5)
(fn(x) { return x }(5) + 10 ) * 10与许多广泛使用的编程语言相比，我们在Monkey中也有“if 表达式”：
let result = if (10 > 5) { true } else { false };
result // => true看着所有这些不同形式的表达式，很明显我们需要一种非常好的方法来正确解析它们，并以可理解和可扩展的方式进行解析。我们根据当前token做什么的就方法不会让我们走得很远-至少不是不想扯掉我们的头发。这就是Vaughan Partt的用武之地。
在他的论文上“自顶而下的运算符优先级”Vaughan Pratt提出一种解析表达式，用他的话说：
[…] is very simple to understand, trivial to implement, easy to use, extremely efficient in practice if not in theory, yet flexible enough to meet most reasonable syntactic needs of users […]
[…] 非常容易理解，易于实现，易于使用，效率极高,在实践中，如果不是理论上，但足够灵活以满足用户最合理的语法需求 […]
论文发表于1973年，但是在此后的许多年里，Partt提出的想法没有大量的追随者。直到最近几年，其他程序员才重新发现了Partt的论文，写了他并使Partt的解析方法越来越受欢迎。Douglas Crockford 的（“JavaScript: The Good Parts”成名）文章称为(自定而下运算符优先级，展示了如何将 Pratt 的想法转化为 JavaScript（Crockford 在构建 JSLint 时所做的）。 然后是优秀的“游戏编程模式”一书的作者 Bob Nystrom 强烈推荐的文章，它通过提供简洁的 Java 示例代码使 Pratt 的方法非常易于理解和遵循。
三者描述的解析方式称为自顶而下运算符优先级解析或Partt解析是作为基于上下无关文法和Backus-Naur-Form的解析器的替代方案而发明的。
这也是主要区别：而不是关联解析函数(想想我们的parseLetStatement方法)与语法规则(在BNF或EBNF中定义)，Pratt将这些函数(他称之为“语义代码”)与单个token类型相关联。这个想法的一个关键部分是每个token类型可以有两个与之关联的解析函数，这取决于token的位置 - 中缀或前缀。
我猜这还是没有什么意义。我们从来没有看到如何联系解析函数和语法规则，所以使用token 类型的想法而不是这些规则的想法并没有注册为任何真正新颖或具有启发性的东西。老实说：在编写本书时，我正面临着先有鸡还是先有蛋的问题。用抽象术语解释这个算法会更好吗？然后显示实现，可能会导致您在页面之间跳来跳去，或者显示带有以下解释的实现，导致您可能跳过实现而没有从解释中得到更多？
答案是，我决定，拒绝这两种想法。我们将要代替的是开始实现我们解析器的表达式解析部分。那我们就来仔细看看在它和它之间的算法。之后我们将扩展并完成它，以便它能够解析所有Monkey中可能的表达式。
在我们开始编写任何代码之前，让我们先弄懂技术。
一个前缀运算符是一个在操作数前面的运算符。例如：
--5这里的运算符是--(递减)，操作符是整数文字5，运算符是前缀位置。
一个后缀运算符是一个在操作数后方的运算符。例如:
foobar++这里的运算符是++(递增)，操作数是标识符foobar和在后方位置的运算符。我们将绑定的Monkey解释器将不会有后缀运算符。不是因为技术限制，而是纯粹为了限制本书的范围。
现在，中缀运算符在两个整数5和8中间的位置。中缀运算符出现在二分表达式中-运算符有两个操作数。
我们已经偶然发现并且稍后会再次找到的另一个术语是运算符优先级。 替代术语是操作顺序，它应该更清楚地说明运算符优先级描述的是什么：不同的运算符具有哪些优先级。 规范的例子是这个，我们之前看到过：
5 + 5 * 10表达式的记过是55而不是100.并且因为*运算符有一个更高的优先级，一个“高排位”。它比起+运算符更重要。它得到评估在其他运算符之前。我有事认为运算符优先级作为“运算符粘性”，运算符旁边的操作数“坚持”了多少。
这里有许多基本术语：前缀，后缀，中缀运算符和优先级。但更重要的是我们稍后会记住这些简单的定义，我们将在其他地方使用这些术语。但是现在，让我们打字并写代码！
我们需要为表达式解析做的第一件事是准备我们的 AST。 正如我们之前看到的，Monkey 中的程序是一系列语句。 有些是 let 语句，有些是 return 语句。 我们需要在 AST 中添加第三种类型的语句：表达式语句。
这可能听起来很困惑，在我告诉你let和return语句是Monkey中仅有的语句后。但是一个表达式语句不是真正的特殊语句;它是仅由一个表达式组成的语句。这只是一个包装。我们需要它，因为它是在Monkey中编写以下代码是完全合法的：
let x = 5;
x + 10;第一行是let语句，第二行是一个表达式语句。其他语言没有这些表达式语句，但大多数脚本语言有。这使得仅由一行表达式的组成称为可能。所以让我们添加这个节点类型给我们的AST：
// ast/ast.go
type ExpressionStatement struct {
Token token.Token // the first token of the expression
Expression Expression
}
func (es *ExpressionStatement) statementNode() {}
func (es *ExpressionStatement) TokenLiteral() string { return es.Token.Literal }ast.ExpressionStatement类型由两个字段：每个节点都有的Token字段，和其中包含表达式的Expression字段。ast.ExpressionStatement实现了ast.Statement接口，这意味着我们可以将它添加到ast.Program的Statements切片中。这就是我们添加ast.ExpressionStatement的全部原因。
随着ast.ExpressionStatement的定义我们可以继续解析器的工作。但相反，让我们通过向AST节点添加String()方法，让我们的生活变得更轻松。这将使我们打印用于调试的AST节点并将它们与其他AST节点进行比较。这将在测试中非常方便！
我们将使String()方法成为ast.Node接口的一部分：
// ast/ast.go
type Node interface {
TokenLiteral() string
String() string
}现在在我们ast包中的每个节点类型都已经实现了方法。随着这个改变，我们的代码将无法编译，因为编译器抱怨我们的AST节点不完全实现新的节点接口。让我们从 *ast.Program 开始，先添加它的 String() 方法：
// ast/ast.go
import (
// [...]
"bytes"
)
func (p *Program) String() string {
var out bytes.Buffer
for _, s := range p.Statements {
out.WriteString(s.String())
}
return out.String()
}这个方法没有做太多。它仅仅创建一个缓冲区并且写下每个String方法给他的每个语句的值。并且然后它返回缓冲区作为一个字符。. 、它将大部分工作委托给 *ast.Program 的声明。
“真正的工作”发生在我们三种语句类型 ast.LetStatement、ast.ReturnStatement 和 ast.ExpressionStatement 的 String() 方法中。
// ast/ast.go
func (ls *LetStatement) String() string {
var out bytes.Buffer
out.WriteString(ls.TokenLiteral() + " ")
out.WriteString(ls.Name.String())
out.WriteString(" = ")
if ls.Value != nil {
out.WriteString(ls.Value.String())
}
out.WriteString(";")
return out.String()
}
func (rs *ReturnStatement) String() string {
var out bytes.Buffer
out.WriteString(rs.TokenLiteral() + " ")
if rs.ReturnValue != nil {
out.WriteString(rs.ReturnValue.String())
}
out.WriteString(";")
return out.String()
}
func (es *ExpressionStatement) String() string {
if es.Expression != nil {
return es.Expression.String()
}
return ""
}稍后，当我们可以完全构建表达式时，将取消 nil 检查。现在我们只需要向 ast.Identifier 添加最后一个 String() 方法：
// ast/ast_test.go
package ast
import (
"monkey/token"
"testing"
)
func TestString(t *testing.T) {
program := &Program{
Statements: []Statement{
&LetStatement{
Token: token.Token{Type: token.LET, Literal: "let"},
Name: &Identifier{
Token: token.Token{Type: token.IDENT, Literal: "myVar"},
Value: "myVar",
},
Value: &Identifier{
Token: token.Token{Type: token.IDENT, Literal: "anotherVar"},
Value: "anotherVar",
},
},
},
}
if program.String() != "let myVar = anotherVar;" {
t.Errorf("program.String() wrong. got=%q", program.String())
}
}在这个测试中我们手动构建了AST。在为解析器编写测试时，我们不会对解析器产生的AST进行断言。处于演示目的，这个测试向我们展示了如何为我们的解析器添加另一个易于阅读的测试层。这在解析表达式时会特别方便。所以好消息是：准备工作已经完成！是时候编写一个Pratt解析器了。
一个Pratt解析器主要想法是联系解析函数(Prate称之为“语义代码”) 与token类型的关联。每当遇到此标记类型时，都会调用解析函数来解析当前适当的表达式并返回表示它的AST节点。每种token类型最多可以有两个与之关联的解析函数，具体取决于token是在前缀还是中缀位置中找到。
我们要做的第一件事是建立联系。我们定义两种类型的函数一个前缀解析函数和一个中缀解析函数。
// parser/parser.go
type (
prefixParseFn func() ast.Expression
infixParseFn func(ast.Expression) ast.Expression
)这两种函数类型都返回一个ast.Expression，因为这就是我们要解析的内容。但是仅仅中缀函数有一个参数：另一个ast.Expression。这个参数是被解析的中缀运算符的“左侧”。前缀运算符没有左边，前定义。我知道这还没有什么意义，但请耐心等待，即将看到它是如何运行的。所以现在，仅仅记住当我们遇到关联的token时会调用prefixParseFns输入前缀位置，当我们在中缀位置遇到token类型时调用 infixParseFn 。
为了我们的解析器得到正确的prefixParseFn 或 infixParseFn对于正确的token类型，我们为Parser结构添加两个maps。
// parser/parser.go
type Parser struct {
l *lexer.Lexer
errors []string
curToken token.Token
peekToken token.Token
prefixParseFns map[token.TokenType]prefixParseFn
infixParseFns map[token.TokenType]infixParseFn
}随着maps存在，我们就能检查是否合适的map(中缀或前缀)有一个和curToken.Type联系的解析函数。
我们还为 Parser 提供了两个辅助方法，用于向这些maps添加条目：
// parser/parser.go
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
}现在我们准备得到算法的核心。
我们将可能开始最简单的表达式在Monkey语言中：标识符。使用在表达式语句中的标识符看起来像这样：
foobar;当然，foobar是可变的并且标识符也是其他表达式的内容，所以仅仅在表达式语句：
add(foobar,barfoo);
foobar + barfoo;
if (foobar) {
//[...]
}在这里我们有标识符作为函数调用的参数，作为中缀表达式中的操作数和作为独立表达式作为条件的一部分。它们可以在所有这些上下文中使用，因为标识符像表达式，就像1 + 2一样。就像其他表达式标识符一样产生一个值：它们评估为它们所绑定的值。
我们将开始一个测试：
// parser/parser_test.go
func TestIdentifierExpression(t *testing.T) {
input := "foobar;"
l := lexer.New(input)
p := New(l)
program := p.ParseProgram()
checkParserErrors(t, p)
if len(program.Statements) != 1 {
t.Fatalf("program has not enough statements. got=%d",
len(program.Statements))
}
stmt, ok := program.Statements[0].(*ast.ExpressionStatement)
if !ok {
t.Fatalf("program.Statements[0] is not ast.ExpressionStatement. got=%T",
program.Statements[0])
}
ident, ok := stmt.Expression.(*ast.Identifier)
if !ok {
t.Fatalf("exp not *ast.Identifier. got=%T", stmt.Expression)
}
if ident.Value != "foobar" {
t.Errorf("ident.Value not %s. got=%s", "foobar", ident.Value)
}
if ident.TokenLiteral() != "foobar" {
t.Errorf("ident.TokenLiteral not %s. got=%s", "foobar",
ident.TokenLiteral())
}
}有好多行啊，但主要是繁重的工作。我们解析我们的输入foobar；检查错误解析器，对*ast.Program节点中的语句数进行断言然后检查program.Statements中的语句是否是 *ast.ExpressionStatement。然后我们检查 *ast.ExpressionStatement.Expression是一个 *ast.Identifier。最后我们检查我们的标识符是否具有正确的“foobar”值。
当然，解析测试失败了：
$ go test ./parser
--- FAIL: TestIdentifierExpression (0.00s)
parser_test.go:110: program has not enough statements. got=0
FAIL
FAIL monkey/parser 0.007s解析不知道关于表达式中的任何东西。我们需要写一个parseExpression方法。
我们要做的第一件事是扩展解析器的parseStatement()方法，为了它解析表达式语句。由于 Monkey 中只有两种真正的语句类型是 let 和 return 语句，如果我们没有这其他两种语句之一，我们会尝试解析表达式语句：
// parser/parser.go
func (p *Parser) parseStatement() ast.Statement {
switch p.curToken.Type {
case token.LET:
return p.parseLetStatement()
case token.RETURN:
return p.parseReturnStatement()
default:
return p.parseExpressionStatement()
}
}parseExpressionStatement方法看起来像：
// parser/parser.go
func (p *Parser) parseExpressionStatement() *ast.ExpressionStatement {
stmt := &ast.ExpressionStatement{Token: p.curToken}
stmt.Expression = p.parseExpression(LOWEST)
if p.peekTokenIs(token.SEMICOLON) {
p.nextToken()
}
return stmt
}我们已经知道了联系：我们构建我们的AST节点并且然后尝试填充它的字段通过调用其他的解析函数。在这种情况下，虽然有一些区别：我们调用parseExpression()，它还不错现在，因为常量LOWEST，它还不存在，然后我们检查一个可选的分号。是的，这是可选的。如果peekToken是一个token SEMICOLON，我们前进所以它是curToken。如果它不存在，那也没关系，如果它不存在，我们不会向解析器添加错误。 那是因为我们希望表达式语句具有可选的分号（这使得稍后在 REPL 中键入诸如 5 + 5 之类的内容更容易）。
如果我们现在运行测试，我们可以看到编译失败了，因为LOWESST没有找到。那就对了，我们现在开始添加它，通过给Monkey编程语言定义优先级：
// parser/parser.go
const (
_ int = iota
LOWEST
EQUALS // ==
LESSGREATER // > or <
SUM // +
PRODUCT // *
PREFIX // -X or !X
CALL // myFunction(X)
)在这里我们使用iota来给出以下递增数字的常量作为值。空白标识符_取0值以下常量被赋值为1到7.其中我们使用的数字无关紧要，但顺序与彼此之间的关系很重要。我们希望从这些常量中得到的答案是：“*运算符是否比==运算符更高的优先级？前缀运算符是否比调用表达式具有更高的优先级？”
在parseExpressionStatement中，我们尽可能低的优先级传递给parseExpression,因为我们还没有解析任何东西，我们无法比较优先级。很快就会有更多意义，我保证。让我们编写parseExpression：
// parser/parser.go
func (p *Parser) parseExpression(precedence int) ast.Expression {
prefix := p.prefixParseFns[p.curToken.Type]
if prefix == nil {
return nil
}
leftExp := prefix()
return leftExp
}这是第一个版本。 它所做的只是检查我们是否在前缀位置有一个与 p.curToken.Type 相关联的解析函数。 如果我们这样做，它会调用这个解析函数，如果不是，它返回 nil。 目前它是这样做的，因为我们还没有将任何token与任何解析函数相关联。 这是我们的下一步：
// parser/parser.go
func New(l *lexer.Lexer) *Parser {
// [...]
p.prefixParseFns = make(map[token.TokenType]prefixParseFn)
p.registerPrefix(token.IDENT, p.parseIdentifier)
// [...]
}
func (p *Parser) parseIdentifier() ast.Expression {
return &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
}我们修改了New函数去初始化prefixParseFns map在Parser和注册一个解析函数：如果我们遇到了一个token类型未token.IDENT 解析函数就调用在*Parser中的parseIdentifier方法。
parseIdentifier方法没有做许多。它仅仅返回一个*ast.Identifier，在Token字段中包含当前token，在Value中返回token的字面值。它不推进token，也不调用nextToken。这很重要。我们所有的解析函数，prefixParseFn 或 infixParseFn，都将遵循这个协议：从 curToken 是你关联的 token 的类型开始，然后返回 curToken 作为你的表达式类型的最后一个标记。 永远不要将token推进得太远。
不管你信不信，我们的测试通过了：
$ go test ./parser
ok monkey/parser 0.007s我们成功解析了一个标识符表达式！ 好的！ 但是，在我们离开电脑之前，找个人，自豪地告诉他们，让我们屏住呼吸再写一些解析函数。
与标识符几乎一样容易解析的是整数文字，如下所示：
5;是的，这就是它。整数文字是表达式。它们产生的值是整数本身。再次，想象在哪些地方可以出现整数文字来理解它们为什么是表达式：
let x = 5;
add(5, 10);
5 + 5 + 5;我们能使用一些其他表达式代替整数文字在这里并且它将仍然有效：标识符、调用表达式、分组表达式、函数文字等。所有的表达类型可以互换，整数文字就是其中之一。整数文字的测试用例看卡里与标识符的测试用例非常相似：
// parser/parser_test.go
func TestIntegerLiteralExpression(t *testing.T) {
input := "5;"
l := lexer.New(input)
p := New(l)
program := p.ParseProgram()
checkParserErrors(t, p)
if len(program.Statements) != 1 {
t.Fatalf("program has not enough statements. got=%d",
len(program.Statements))
}
stmt, ok := program.Statements[0].(*ast.ExpressionStatement)
if !ok {
t.Fatalf("program.Statements[0] is not ast.ExpressionStatement. got=%T",
program.Statements[0])
}
literal, ok := stmt.Expression.(*ast.IntegerLiteral)
if !ok {
t.Fatalf("exp not *ast.IntegerLiteral. got=%T", stmt.Expression)
}
if literal.Value != 5 {
t.Errorf("literal.Value not %d. got=%d", 5, literal.Value)
}
if literal.TokenLiteral() != "5" {
t.Errorf("literal.TokenLiteral not %s. got=%s", "5",
literal.TokenLiteral())
}
}就像在标识符的测试用例中一样，我们使用一个简单的输入，将它提供给解析器，然后检查解析器没有遇到任何错误并在*ast.Program.Statements中生成正确数量的语句。然后我们添加一个断言，即第一条语句是 *ast.ExpressionStatement。最后我们期待一个格式良好的 *ast.IntegerLiteral。测试不会编译，因为 *ast.IntergerLiteral还不存在。定义它很容易：
// ast/ast.go
type IntegerLiteral struct {
Token token.Token
Value int64
}
func (il *IntegerLiteral) expressionNode() {}
func (il *IntegerLiteral) TokenLiteral() string { return il.Token.Literal }
func (il *IntegerLiteral) String() string { return il.Token.Literal }*ast.IntegerLiteral 实现了 ast.Expression 接口，就像 *ast.Identifier 一样，但在结构本身上与 ast.Identifier 有显着区别：Value 是一个 int64 而不是字符串。 这是将包含整数文字在源代码中表示的实际值的字段。 当我们构建 *ast.IntegerLiteral 时，我们必须将 *ast.IntegerLiteral.Token.Literal 中的字符串（类似于“5”）转换为 int64。
最好的做的方式是在解析函数中和token.INT联系起来，叫做parseIntegerLiteral:
// parser/parser.go
import (
// [...]
"strconv"
)
func (p *Parser) parseIntegerLiteral() ast.Expression {
lit := &ast.IntegerLiteral{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
}像parseIdentifier方法简单。唯一不同的是调用strconv.Parselnt,它将p.curToken.Literal中的字符串转换为int64。然后int64被保存到Value字段，我们返回新构造的*ast.IntegerLiteral节点。如果这不起作用，我们会在解析器的错误字段中添加一个新错误。
但是测试还没有运行：
$ go test ./parser
--- FAIL: TestIntegerLiteralExpression (0.00s)
parser_test.go:162: exp not *ast.IntegerLiteral. got=<nil>
FAIL
FAIL monkey/parser 0.008s我们有nil代替一个*ast.IntegerLiteral在我们的AST。原因就是parseExpression无法为 token.INT 类型的标记找到 prefixParseFn。。为了让测试通过，我们所要做的就是注册我们的 parseIntegerLiteral 方法：
// parser/parser.go
func New(l *lexer.Lexer) *Parser {
// [...]
p.prefixParseFns = make(map[token.TokenType]prefixParseFn)
p.registerPrefix(token.IDENT, p.parseIdentifier)
p.registerPrefix(token.INT, p.parseIntegerLiteral)
// [...]
}随着ParseIntegerLiteral注册了，parseExpression现在知道如何处理token.INT token，调用 parseIntegerLiteral 并返回它的返回值，一个 *ast.IntegerLiteral。 这次测试通过了：
$ go test ./parser
ok monkey/parser 0.007s我认为是时候说：我们顺利运行了！ 标识符和整数文字都在包里，让我们更进一步，解析前缀运算符。
在Monkey语言中有两种前缀运算符:!和-。它们的用法与您对其他语言的期望非常相似：
-5;
!foobar;
5 + -10;它们遵循的使用结构：
<prefix operator><expression>;是的，好吧。一些表达式能遵循一个前缀运算符作为一个文字。这些是有效的:
!isGreaterThanZero(2);
5 + -add(5, 5);这意味着前缀运算符表达式的 AST 节点必须足够灵活以 指向任何表达式作为其操作数。
但首先，这是前缀运算符或“前缀表达式”的测试用例：
// parser/parser_test.go
func TestParsingPrefixExpressions(t *testing.T) {
prefixTests := []struct {
input string
operator string
value interface{}
}{
{"!5;", "!", 5},
{"-15;", "-", 15},
{"!foobar;", "!", "foobar"},
{"-foobar;", "-", "foobar"},
{"!true;", "!", true},
{"!false;", "!", false},
}
for _, tt := range prefixTests {
l := lexer.New(tt.input)
p := New(l)
program := p.ParseProgram()
checkParserErrors(t, p)
if len(program.Statements) != 1 {
t.Fatalf("program.Statements does not contain %d statements. got=%d\n",
1, len(program.Statements))
}
stmt, ok := program.Statements[0].(*ast.ExpressionStatement)
if !ok {
t.Fatalf("program.Statements[0] is not ast.ExpressionStatement. got=%T",
program.Statements[0])
}
exp, ok := stmt.Expression.(*ast.PrefixExpression)
if !ok {
t.Fatalf("stmt is not ast.PrefixExpression. got=%T", stmt.Expression)
}
if exp.Operator != tt.operator {
t.Fatalf("exp.Operator is not '%s'. got=%s",
tt.operator, exp.Operator)
}
if !testLiteralExpression(t, exp.Right, tt.value) {
return
}
}
}这个测试函数，再一次，有很多行:(有两个原因：手动闯进错误信息t.Errorf占用了一些空间，我们正在使用表驱动的测试方法。原因是它结尾我们节省了两个测试用例，但是重复每个案例的完整测试意味着很多行。而且由于背后逻辑的测试断言相同，我们共享测试设置。两个测试用例(!5和-15作为输入)不同之处在于预期的运算符和整数值(我们在prefixTests中定义)。
在测试函数中，我们遍历我们的测试输入片段并对根据解耦狗的prefixTests切片中定义的值生成AST。正如你所见，最后我们使用一个名为testIntegerLiteral的辅助函数来测试这里的Right值是否是正确的整数文字。我们在这里介绍这个辅助函数，所以测试用例的终点是*ast.PrefixExpression及其字段，我们很快就会再次需要它。它看起来像这样：
// parser/parser_test.go
func testIntegerLiteral(t *testing.T, il ast.Expression, value int64) bool {
integ, ok := il.(*ast.IntegerLiteral)
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
}
if integ.TokenLiteral() != fmt.Sprintf("%d", value) {
t.Errorf("integ.TokenLiteral not %d. got=%s", value,
integ.TokenLiteral())
return false
}
return true
}这里没有什么新东西，我们之前在 TestIntegerLiteralExpression 中见过。 但现在它隐藏在一个小的辅助函数后面，使这些新测试更具可读性。正如预期的那样，测试甚至无法编译：
$ go test ./parser
# monkey/parser
parser/parser_test.go:210: undefined: ast.PrefixExpression
FAIL monkey/parser [build failed]我们需要定义ast.PrefixExpression节点：
//ast/ast.go
type PrefixExpression struct {
Token token.Token // The prefix token, e.g. !
Operator string
Right Expression
}
func (pe *PrefixExpression) expressionNode() {}
func (pe *PrefixExpression) TokenLiteral() string { return pe.Token.Literal }
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()
}这没有包含一些惊讶。*ast.PrefixExpression节点有两个值得注意的字段：运算符和右侧。运算符是一个字符串，将包含“-”或“！”。 右侧的 字段包含运算符右侧的表达式。
在 String() 方法中，我们特意在运算符及其操作数周围添加括号，即 Right 中的表达式。 这让我们可以看到哪些操作数属于哪个操作符。
随着*ast.PrefixExpression定义了，测试现在失败了因为一个奇怪的错误新奇：
$ go test ./parser
--- FAIL: TestParsingPrefixExpressions (0.00s)
parser_test.go:198: program.Statements does not contain 1 statements. got=2
FAIL
FAIL monkey/parser 0.007s为什么program.Statements包含一个语句而不是预期的两个？原因是parseExpression还不能识别我们的前缀运算符，只是返回nil。program.Statements不包含一个语句，而值包含一个nil。
我们能比这个做的更好，我们能扩展我们的解析器并且parseExpression方法给我们更好地错误信息当错误发生的时候：
// parser/parser.go
func (p *Parser) noPrefixParseFnError(t token.TokenType) {
msg := fmt.Sprintf("no prefix parse function for %s found", t)
p.errors = append(p.errors, msg)
}
func (p *Parser) parseExpression(precedence int) ast.Expression {
prefix := p.prefixParseFns[p.curToken.Type]
if prefix == nil {
p.noPrefixParseFnError(p.curToken.Type)
return nil
}
leftExp := prefix()
return leftExp
}小的辅助函数noPrefixParseFnError只是添加一个错误格式给我们解析器的错误字段。但是它足以使错误测试变得更好：
$ go test ./parser
--- FAIL: TestParsingPrefixExpressions (0.00s)
parser_test.go:227: parser has 1 errors
parser_test.go:229: parser error: "no prefix parse function for ! found"
FAIL
FAIL monkey/parser 0.010s现在很清楚我们必须做什么：为前缀表达式编写一个解析函数并将其注册到我们的解析器中。
// parser/parser.go
func New(l *lexer.Lexer) *Parser {
// [...]
p.registerPrefix(token.BANG, p.parsePrefixExpression)
p.registerPrefix(token.MINUS, p.parsePrefixExpression)
// [...]
}
func (p *Parser) parsePrefixExpression() ast.Expression {
expression := &ast.PrefixExpression{
Token: p.curToken,
Operator: p.curToken.Literal,
}
p.nextToken()
expression.Right = p.parseExpression(PREFIX)
return expression
}对于token.BANG和token.MINUS我们注册了与prefixParseFn相同的方法：新创建的parsePrefixExpression。这个方法构建了一个AST节点，在这个例子中是*ast.PrefixExpression，就像我们之前看到的解析函数一样。但是它做了一些不同的事情：它实际上通过调用p.nextToken()来推进我们的token！
当 parsePrefixExpression 被调用时，p.curToken 是 token.BANG 或 token.MINUS 类型，否则它不会被调用。 但是为了正确解析像 -5 这样的前缀表达式，必须“消耗”多个标记。 所以在使用p.curToken构建一个*ast.PrefixExpression节点后，该方法将token推进，再次调用parseExpression。这次以前缀运算符的优先级作为参数。 它仍然未使用，但我们很快就会看到它的好处以及如何使用它。
现在，当 parseExpression 被 parsePrefixExpression 调用时，token已经提前，当前标记是前缀运算符之后的标记。 在 -5 的情况下，当 parseExpression 被调用时，p.curToken.Type 是 token.INT。 parseExpression 然后检查注册的前缀解析函数并找到 parseIntegerLiteral，它构建一个 *ast.IntegerLiteral 节点并返回它。 parseExpression 返回这个新构造的节点，parsePrefixEx=pression 使用它来填充 *ast.PrefixExpression 的 Right 字段。
是的，这次成功了，我们的测试通过了:
$ go test ./parser
ok monkey/parser 0.007s注意我们的解析函数的“协议”是如何在这里发挥作用的： parsePrefixExpression 开始 p.curToken 是前缀运算符的标记，它返回 p.curToken 是前缀表达式的操作数，它是表达式的最后一个标记。 token得到足够先进，效果很好。 整洁的事情是多少行代码为此需要。 威力在于递归方法。
当然， parseExpression 中的优先级参数令人困惑，因为它没有被使用。 但是我们已经看到了关于它的用法的一些重要内容：值根据调用者的知识和上下文而变化。 parseExpressionStatement（这里开始表达式解析的顶级方法）对优先级一无所知，只使用 LOWEST。 但是 parsePrefixExpression 将 PREFIX 优先级传递给 parseExpression，因为它正在解析一个前缀表达式。
现在我们将看到如何使用 parseExpression 中的优先级。 因为现在我们要解析中缀表达式。
下一步我们将解析这八个中缀运算符：
5 + 5;
5 - 5;
5 * 5;
5 / 5;
5 > 5;
5 < 5;
5 == 5;
5 != 5;不要对这里的5困扰。作为前缀运算符表达式，我们能使用一些表达式左侧和右侧使用任何语句。
<expression> <infix operator> <expression>因为两个操作数(左和右)，这些表达式有时成为“二分表达式”(而我们的前缀表达式成为“一元表达式”)。尽管我们可以在运算符的任一侧使用任何表达式，但我们将首先编写一个仅使用整数文字作为操作数的测试。一旦我们可以通过测试，我们将延长它包含更多的操作数类型。在这：
func TestParsingInfixExpressions(t *testing.T) {
infixTests := []struct {
input string
leftValue interface{}
operator string
rightValue interface{}
}{
{"5 + 5;", 5, "+", 5},
{"5 - 5;", 5, "-", 5},
{"5 * 5;", 5, "*", 5},
{"5 / 5;", 5, "/", 5},
{"5 > 5;", 5, ">", 5},
{"5 < 5;", 5, "<", 5},
{"5 == 5;", 5, "==", 5},
{"5 != 5;", 5, "!=", 5},
}
for _, tt := range infixTests {
l := lexer.New(tt.input)
p := New(l)
program := p.ParseProgram()
checkParserErrors(t, p)
if len(program.Statements) != 1 {
t.Fatalf("program.Statements does not contain %d statements. got=%d\n",
1, len(program.Statements))
}
stmt, ok := program.Statements[0].(*ast.ExpressionStatement)
if !ok {
t.Fatalf("program.Statements[0] is not ast.ExpressionStatement. got=%T",
program.Statements[0])
}
exp, ok := stmt.Expression.(*ast.InfixExpression)
if !ok {
t.Fatalf("exp is not ast.InfixExpression. got=%T", stmt.Expression)
}
if !testIntegerLiteral(t, exp.Left, tt.leftValue) {
return
}
if exp.Operator != tt.operator {
t.Fatalf("exp.Operator is not '%s'. got=%s",
tt.operator, exp.Operator)
}
if !testIntegerLiteral(t, exp.Right, tt.rightValue) {
return
}
}
}这个测试几乎是 TestParsingPrefixExpressions 的直接副本，除了我们现在对结果 AST 节点的 Right 和 Left 字段进行断言。 在这里，表驱动方法为我们提供了很大的优势，当我们将测试扩展为也包括标识符时，我们很快就会使用它。当然，测试失败，因为它们找不到 *astInfixExpression 的定义。 为了获得真正失败的测试，我们定义了 ast.InfixExpression：
// ast/ast.go
type InfixExpression struct {
Token token.Token // The operator token, e.g. +
Left Expression
Operator string
Right Expression
}
func (oe *InfixExpression) expressionNode() {}
func (oe *InfixExpression) TokenLiteral() string { return oe.Token.Literal }
func (oe *InfixExpression) String() string {
var out bytes.Buffer
out.WriteString("(")
out.WriteString(oe.Left.String())
out.WriteString(" " + oe.Operator + " ")
out.WriteString(oe.Right.String())
out.WriteString(")")
return out.String()
}就像 ast.PrefixExpression 一样，我们定义 ast.InfixExpression 来实现 ast.Expression和 ast.Node 接口，通过定义 expressionNode()、TokenLiteral() 和 String() 方法。 与 ast.PrefixExpression 的唯一区别是名为 Left 的新字段，它可以保存任何表达式。
有了这个，我们就可以构建和运行我们的测试了。 测试甚至返回我们的一个自己的新错误消息：
$ go test ./parser
--- FAIL: TestParsingInfixExpressions (0.00s)
parser_test.go:246: parser has 1 errors
parser_test.go:248: parser error: "no prefix parse function for + found"
FAIL
FAIL monkey/parser 0.007s但该错误信息具有欺骗性。 它说“没有找到 + 的前缀解析函数”。 问题 是我们不希望我们的解析器为 + 找到前缀解析函数。 我们希望它找到一个 中缀解析函数。
这就是我们从“我猜它很整洁”到“哇，这很漂亮”的关键，因为我们现在需要完成我们的 parseExpression 方法。 为此，我们首先需要一个优先级表和一些辅助方法：
// parser/parser.go
var precedences = map[token.TokenType]int{
token.EQ: EQUALS,
token.NOT_EQ: EQUALS,
token.LT: LESSGREATER,
token.GT: LESSGREATER,
token.PLUS: SUM,
token.MINUS: SUM,
token.SLASH: PRODUCT,
token.ASTERISK: PRODUCT,
}
// [...]
func (p *Parser) peekPrecedence() int {
if p, ok := precedences[p.peekToken.Type]; ok {
return p
}
return LOWEST
}
func (p *Parser) curPrecedence() int {
if p, ok := precedences[p.curToken.Type]; ok {
return p
}
return LOWEST
}优先级在我们的优先级表：它联系token类型用它们的优先级。优先级值本身就是我们之前定义的常量，随着递增的整数值。 例如这张表现在可以告诉我们 + (token.PLUS) 和 - (token.MINUS) 有相同的优先级，低于*（token.ASTERISK）和/（token.SLASH）的优先级。
peekPrecedence 方法返回与令牌类型关联的优先级p.peekToken。 如果没有找到 p.peekToken 的优先级，则默认为 LOWEST，最低的任何运算符都可以拥有的可能优先级。 curPrecedence 方法做同样的事情，但对于 p.curToken。
下一步是为我们所有的中缀运算符注册一个中缀解析函数：
// parser/parser.go
func New(l *lexer.Lexer) *Parser {
// [...]
p.infixParseFns = make(map[token.TokenType]infixParseFn)
p.registerInfix(token.PLUS, p.parseInfixExpression)
p.registerInfix(token.MINUS, p.parseInfixExpression)
p.registerInfix(token.SLASH, p.parseInfixExpression)
p.registerInfix(token.ASTERISK, p.parseInfixExpression)
p.registerInfix(token.EQ, p.parseInfixExpression)
p.registerInfix(token.NOT_EQ, p.parseInfixExpression)
p.registerInfix(token.LT, p.parseInfixExpression)
p.registerInfix(token.GT, p.parseInfixExpression)
// [...]
}我们的曲目中已经有了 registerInfix 方法，现在我们终于可以使用它了。 每一个中缀运算符与称为 parseInfixExpression 的相同解析函数相关联，它看起来像这样：
// parser/parser.go
func (p *Parser) parseInfixExpression(left ast.Expression) ast.Expression {
expression := &ast.InfixExpression{
Token: p.curToken,
Operator: p.curToken.Literal,
Left: left,
}
precedence := p.curPrecedence()
p.nextToken()
expression.Right = p.parseExpression(precedence)
return expression
}这里的显着区别是，与 parsePrefixExpression 相比，这个新方法接受一个参数，一个名为 left 的 ast.Expression。 它使用这个参数来构造一个*ast.InfixExpression 节点，左侧位于左侧字段中。 然后它分配优先级当前token（它是中缀表达式的运算符）到局部变量的优先级，在通过调用 nextToken 并用另一个对 parseExpression 的调用填充节点的 Right 字段来推进标记之前 - 这次传入运算符标记的优先级。是时候拉开帷幕了。 这是我们的 Pratt 解析器的核心，这是最终版本解析表达式：
// parser/parser.go
func (p *Parser) parseExpression(precedence int) ast.Expression {
prefix := p.prefixParseFns[p.curToken.Type]
if prefix == nil {
p.noPrefixParseFnError(p.curToken.Type)
return nil
}
leftExp := prefix()
for !p.peekTokenIs(token.SEMICOLON) && precedence < p.peekPrecedence() {
infix := p.infixParseFns[p.peekToken.Type]
if infix == nil {
return leftExp
}
p.nextToken()
leftExp = infix(leftExp)
}
return leftExp
}And, boom! 我们的测试通过了，全绿了, baby:
$ go test ./parser
ok monkey/parser 0.006s我们现在正式能够正确解析中缀运算符表达式！ 等等，什么？ 刚刚到底发生了什么？ 这是如何运作的？
显然 parseExpression 现在做了一些更多的事情。 我们已经知道它如何找到与当前标记相关联的 prefixParseFn 并调用它。 我们已经在前缀运算符、标识符和整数文字中看到了这项工作。
新鲜的是 parseExpression 中间的循环。 在循环体中的方法尝试为下一个标记查找 infixParseFns。 如果找到这样的函数，它会调用它，传递在由 prefixParseFn 作为参数返回的表达式中。 它再次完成所有这一切 直到遇到具有更高优先级的token。这很好用。 查看这些使用具有不同优先级的多个运算符的测试以及字符串形式的 AST 如何正确表示这一点：
// parser/parser_test.go
func TestOperatorPrecedenceParsing(t *testing.T) {
tests := []struct {
input string
expected string
}{
{
"-a * b",
"((-a) * b)",
},
{
"!-a",
"(!(-a))",
},
{
"a + b + c",
"((a + b) + c)",
},
{
"a + b - c",
"((a + b) - c)",
},
{
"a * b * c",
"((a * b) * c)",
},
{
"a * b / c",
"((a * b) / c)",
},
{
"a + b / c",
"(a + (b / c))",
},
{
"a + b * c + d / e - f",
"(((a + (b * c)) + (d / e)) - f)",
},
{
"3 + 4; -5 * 5",
"(3 + 4)((-5) * 5)",
},
{
"5 > 4 == 3 < 4",
"((5 > 4) == (3 < 4))",
},
{
"5 < 4 != 3 > 4",
"((5 < 4) != (3 > 4))",
},
{
"3 + 4 * 5 == 3 * 1 + 4 * 5",
"((3 + (4 * 5)) == ((3 * 1) + (4 * 5)))",
},
}
for _, tt := range tests {
l := lexer.New(tt.input)
p := New(l)
program := p.ParseProgram()
checkParserErrors(t, p)
actual := program.String()
if actual != tt.expected {
t.Errorf("expected=%q, got=%q", tt.expected, actual)
}
}
}他们都通过了！ 这非常了不起，不是吗？ 不同的 *ast.InfixExpressions 是正确嵌套，由于我们在 String() 中使用了括号，我们可以观察到AST 节点的方法。
如果您正在挠头并想知道所有这些是如何工作的，请不要担心。 我们现在 将仔细研究我们的 parseExpression 方法。
| < 2.5解析返回语句 | > 2.7Pratt解析是如何运行的？ |
|---|