用go语言实现解释器
golang 编译原理
golang 编译原理
发布日期:   2023-06-03
文章字数:   30.9k
阅读时长:   151 分
阅读次数:  

1. 词法分析

1.1 词法分析

为了解释源代码,需要将其转换为易于理解的形式,最终对代码求值之前,需要两次转换源代码的表示形式

词法分析器的作用如下:

let x = 5 + 5; -> [LET,INDENTIFIER(“x”),EQUAL_SIGN,INTERGER(5),PLUS_SIGN,INTERGER(5),SEMICOLON]

不同词法分析器生成的词法单元会有区别

  • 空白字符不会被识别(python 等语言会)
  • 完整的词法分析器还可将行列号和文件名附加到词法单元中,后续语法分析可以更好地报错

1.2 定义词法单元

先定义词法分析器输出的词法单元

这是要解析的语句段(Monkey 语言)

let five = 5;
let ten = 10;

let add = fn(x,y) {
    x + y;
}

let result = add(five, ten);
  • 数字都是整数,按字面量处理,并赋予单独的类型
  • 变量名和数字等语言,统一用作标识符
  • 还有一些看着像标识符的,但实际是关键字,会特殊处理

定义 Token 数据结构,属性有 1.词法单元类型;2.字面量
词法单元类型定义为字符串,消耗一些性能,但是调试使用方便

// token/token.go
package token

// 词法单元类型
type TokenType string

// 词法单元
type Token struct {
    Type TokenType
    // 字面量
    Literal string
}

将词法单元类型定义为常量

const (
    // 特殊类型
    ILLEGAL = "ILLEGAL" // 未知字符
    EOF     = "EOF"     // 文件结尾

    // 标识符+字面量
    IDENT = "IDENT" // add, foobar, x, y
    INT   = "INT"   // 1343456

    // 运算符
    ASSIGN = "="
    PLUS   = "+"

    // 分隔符
    COMMA     = ","
    SEMICOLON = ";"

    LPAREN = "("
    RPAREN = ")"
    LBRACE = "{"
    RBRACE = "}"

    // 关键字
    FUNCTION = "FUNCTION"
    LET      = "LET"
)

1.3 词法分析器

词法分析器接收源代码(字符串),然后调用 NextToken()逐个遍历字符进行词法分析

生产环境,将文件名和行号附加到词法单元,最好使用 io.Reader 加上文件名来初始化词法分析器

// lexer/lexer.go
package lexer

type Lexer struct {
    input        string
    position     int  // 输入的字符串中的当前位置(指向当前字符)
    readPosition int  // 输入的字符串中的当前读取位置(指向当前字符串之后的一个字符(ch))
    ch           byte // 当前正在查看的字符
}

func New(input string) *Lexer {
    l := &Lexer{input: input}
    return l
}

// 读取下一个字符
func (l *Lexer) readChar() {
    if l.readPosition >= len(l.input) {
        l.ch = 0 // NUL的ASSII码(0)
    } else {
        // 读取
        l.ch = l.input[l.readPosition]
    }
    // 前移
    l.position = l.readPosition
    l.readPosition += 1
}
  • readChar 的作用是读取 input 中下个字符,然后将索引前推,NUL 字符的 ASCII 码是 0,表示”尚未读取任何内容”或”文件结尾”
  • 该分析器只支持 ASCII 字符,不能支持所有 Unicode 字符,如果要支持,则 l.ch 要改为 rune 类型,并且要修改读取下一个字符的方式,字符也有可能会是多字节,l.input[l.readPosition]将无法工作

在 New 中调用 readChar 以初始化

func New(input string) *Lexer {
    l := &Lexer{input: input}
    // 初始化 l.ch,l.position,l.readPosition
    l.readChar()
    return l
}

第一版 NextToken

// lexer/lexer.go
package lexer

import (
    "go-monkey-compiler/token"
)

// 创建词法单元的方法
func newToken(tokenType token.TokenType, ch byte) token.Token {
    return token.Token{
        Type:    tokenType,
        Literal: string(ch),
    }
}

// 根据当前的ch创建词法单元
func (l *Lexer) NextToken() token.Token {
    var tok token.Token

    switch l.ch {
    case '=':
        tok = newToken(token.ASSIGN, l.ch)
    case ';':
        tok = newToken(token.SEMICOLON, l.ch)
    case '(':
        tok = newToken(token.LPAREN, l.ch)
    case ')':
        tok = newToken(token.RPAREN, l.ch)
    case ',':
        tok = newToken(token.COMMA, l.ch)
    case '+':
        tok = newToken(token.PLUS, l.ch)
    case '{':
        tok = newToken(token.LBRACE, l.ch)
    case '}':
        tok = newToken(token.RBRACE, l.ch)
    case 0:
        tok.Literal = ""
        tok.Type = token.EOF
    }

    l.readChar()
    return tok
}

测试

// lexer/lexer_test.go
package lexer

import (
    "go-monkey-compiler/token"
    "testing"
)

func TestNextToken(t *testing.T) {
    input := `=+(){},;`

    tests := []struct {
        expectedType    token.TokenType
        expectedLiteral string
    }{
        {token.ASSIGN, "="},
        {token.PLUS, "+"},
        {token.LPAREN, "("},
        {token.RPAREN, ")"},
        {token.LBRACE, "{"},
        {token.RBRACE, "}"},
        {token.COMMA, ","},
        {token.SEMICOLON, ";"},
        {token.EOF, ""},
    }

    l := New(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)
        }
    }

}

go test ./lexer

添加标识符/关键字/数字的处理

// lexer/lexer.go
// 判断读取到的字符是不是字母
func isLetter(ch byte) bool {
    return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_'
}

// 读取字母(标识符/关键字)
func (l *Lexer) readIdentifier() string {
    position := l.position
    for isLetter(l.ch) {
        // 如果接下来还有字母,就一直移动指针到不是字母
        l.readChar()
    }
    return l.input[position:l.position]
}

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

    switch l.ch {
        // ...
    default:
        if isLetter(l.ch) {
            tok.Literal = l.readIdentifier()
            tok.Type = token.LookupIdent(tok.Literal)
            return tok
        } else {
            tok = newToken(token.ILLEGAL, l.ch)
        }
    }

    l.readChar()
    return tok
}

在 token.go 里添加识别关键字和用户定义标识符的方法

// 关键字map
var keywords = map[string]TokenType{
    "fn":  FUNCTION,
    "let": LET,
}

func LookupIdent(ident string) TokenType {
    // 从关键字map里找,找到了就说明是关键字
    if tok, ok := keywords[ident]; ok {
        return tok
    }
    // 标识符
    return IDENT
}

此时如果遇到空白字段,会报错 IDENT!=ILLEGAL,需要添加跳过空格的方法

// lexer/lexer.go

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

// 根据当前的ch创建词法单元
func (l *Lexer) NextToken() token.Token {
    var tok token.Token

    // 跳过空格
    l.skipWhitespace()

    switch l.ch {
        // ...
    }
    // ...
}

现在添加将数字转为词法单元的功能

数字的识别还可以是浮点数/16 进制/8 进制等,但是书中为了教学而简化了

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

// 判断是否是数字
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]
}

// 根据当前的ch创建词法单元
func (l *Lexer) NextToken() token.Token {
    var tok token.Token

    // 跳过空格
    l.skipWhitespace()

    switch l.ch {
        // ...
    default:
        if isLetter(l.ch) {
            tok.Literal = l.readIdentifier()
            tok.Type = token.LookupIdent(tok.Literal)
            // 因为readIdentifier会调用readChar,所以提前return,不需要后面再readChar
            return tok
        } else if isDigit(l.ch) {
            tok.Type = token.INT
            tok.Literal = l.readNumber()
            return tok
        } else {
            tok = newToken(token.ILLEGAL, l.ch)
        }
    }

    l.readChar()
    return tok
}

拓展测试用例,处理开头提到的那个 Monkey 代码段

// lexer/lexer_test.go
package lexer

import (
    "go-monkey-compiler/token"
    "testing"
)

func TestNextToken(t *testing.T) {
    input :=
        `
    let five = 5;
    let ten = 10;
    let add = fn(x,y) {
        x + y;
    };

    let result = add(five, ten);
    `

    tests := []struct {
        expectedType    token.TokenType
        expectedLiteral string
    }{
        {token.LET, "let"},
        {token.IDENT, "five"},
        {token.ASSIGN, "="},
        {token.INT, "5"},
        {token.SEMICOLON, ";"},
        {token.LET, "let"},
        {token.IDENT, "ten"},
        {token.ASSIGN, "="},
        {token.INT, "10"},
        {token.SEMICOLON, ";"},
        {token.LET, "let"},
        {token.IDENT, "add"},
        {token.ASSIGN, "="},
        {token.FUNCTION, "fn"},
        {token.LPAREN, "("},
        {token.IDENT, "x"},
        {token.COMMA, ","},
        {token.IDENT, "y"},
        {token.RPAREN, ")"},
        {token.LBRACE, "{"},
        {token.IDENT, "x"},
        {token.PLUS, "+"},
        {token.IDENT, "y"},
        {token.SEMICOLON, ";"},
        {token.RBRACE, "}"},
        {token.SEMICOLON, ";"},
        {token.LET, "let"},
        {token.IDENT, "result"},
        {token.ASSIGN, "="},
        {token.IDENT, "add"},
        {token.LPAREN, "("},
        {token.IDENT, "five"},
        {token.COMMA, ","},
        {token.IDENT, "ten"},
        {token.RPAREN, ")"},
        {token.SEMICOLON, ";"},
        {token.EOF, ""},
    }

    l := New(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)
        }
    }

}

1.4 拓展词法单元和词法分析器

添加对 == ! != - / * < > 和关键字 true false if else return 的支持
可分为

  • 单字符语法单元(如-,!)
  • 双字符语法单元(如==) <- 后续添加支持
  • 关键字语法定义(如 return)

添加对- / * < > 的支持
token 常量中添加新定义

const (
    // ...

    // 运算符
    ASSIGN   = "="
    PLUS     = "+"
    MINUS    = "-"
    BANG     = "!"
    ASTERISK = "*"
    SLASH    = "/"

    LT = "<"
    GT = ">"

    // ...
)

lexer.go 的 switch 中添加新的词法单元生成

// 根据当前的ch创建词法单元
func (l *Lexer) NextToken() token.Token {
    var tok token.Token

    // 跳过空格
    l.skipWhitespace()

    switch l.ch {
    case '=':
        tok = newToken(token.ASSIGN, l.ch)
    case '+':
        tok = newToken(token.PLUS, l.ch)
    case '-':
        tok = newToken(token.MINUS, l.ch)
    case '!':
        tok = newToken(token.BANG, l.ch)
    case '/':
        tok = newToken(token.SLASH, l.ch)
    case '*':
        tok = newToken(token.ASTERISK, l.ch)
    case '<':
        tok = newToken(token.LT, l.ch)
    case '>':
        tok = newToken(token.GT, l.ch)
    // ...
    }

    l.readChar()
    return tok
}

测试

// lexer/lexer_test.go
package lexer

import (
    "go-monkey-compiler/token"
    "testing"
)

func TestNextToken(t *testing.T) {
    input :=
        `
    let five = 5;
    let ten = 10;

    let add = fn(x, y) {
    x + y;
    };

    let result = add(five, ten);
    !-/*5;
    5 < 10 > 5;
    `

    tests := []struct {
        expectedType    token.TokenType
        expectedLiteral string
    }{
        {token.LET, "let"},
        {token.IDENT, "five"},
        {token.ASSIGN, "="},
        {token.INT, "5"},
        {token.SEMICOLON, ";"},
        {token.LET, "let"},
        {token.IDENT, "ten"},
        {token.ASSIGN, "="},
        {token.INT, "10"},
        {token.SEMICOLON, ";"},
        {token.LET, "let"},
        {token.IDENT, "add"},
        {token.ASSIGN, "="},
        {token.FUNCTION, "fn"},
        {token.LPAREN, "("},
        {token.IDENT, "x"},
        {token.COMMA, ","},
        {token.IDENT, "y"},
        {token.RPAREN, ")"},
        {token.LBRACE, "{"},
        {token.IDENT, "x"},
        {token.PLUS, "+"},
        {token.IDENT, "y"},
        {token.SEMICOLON, ";"},
        {token.RBRACE, "}"},
        {token.SEMICOLON, ";"},
        {token.LET, "let"},
        {token.IDENT, "result"},
        {token.ASSIGN, "="},
        {token.IDENT, "add"},
        {token.LPAREN, "("},
        {token.IDENT, "five"},
        {token.COMMA, ","},
        {token.IDENT, "ten"},
        {token.RPAREN, ")"},
        {token.SEMICOLON, ";"},
        {token.BANG, "!"},
        {token.MINUS, "-"},
        {token.SLASH, "/"},
        {token.ASTERISK, "*"},
        {token.INT, "5"},
        {token.SEMICOLON, ";"},
        {token.INT, "5"},
        {token.LT, "<"},
        {token.INT, "10"},
        {token.GT, ">"},
        {token.INT, "5"},
        {token.SEMICOLON, ";"},
    }

    l := New(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)
        }
    }
}

进一步拓展,添加新关键字的解析 true false if else return

将新关键字分别添加到 token 的常量列表和 keywords 关键字 map 里

const (
    // ...

    // 关键字
    FUNCTION = "FUNCTION"
    LET      = "LET"
    TRUE     = "TRUE"
    FALSE    = "FALSE"
    IF       = "IF"
    ELSE     = "ELSE"
    RETURN   = "RETURN"
)

// 关键字map
var keywords = map[string]TokenType{
    "fn":     FUNCTION,
    "let":    LET,
    "true":   TRUE,
    "false":  FALSE,
    "if":     IF,
    "else":   ELSE,
    "return": RETURN,
}

测试

// lexer/lexer_test.go
package lexer

import (
    "go-monkey-compiler/token"
    "testing"
)

func TestNextToken(t *testing.T) {
    input :=
        `
    let five = 5;
    let ten = 10;

    let add = fn(x, y) {
    x + y;
    };

    let result = add(five, ten);
    !-/*5;
    5 < 10 > 5;

    if (5 < 10) {
        return true;
    } else {
        return false;
    }
    `

    tests := []struct {
        expectedType    token.TokenType
        expectedLiteral string
    }{
        {token.LET, "let"},
        {token.IDENT, "five"},
        {token.ASSIGN, "="},
        {token.INT, "5"},
        {token.SEMICOLON, ";"},
        {token.LET, "let"},
        {token.IDENT, "ten"},
        {token.ASSIGN, "="},
        {token.INT, "10"},
        {token.SEMICOLON, ";"},
        {token.LET, "let"},
        {token.IDENT, "add"},
        {token.ASSIGN, "="},
        {token.FUNCTION, "fn"},
        {token.LPAREN, "("},
        {token.IDENT, "x"},
        {token.COMMA, ","},
        {token.IDENT, "y"},
        {token.RPAREN, ")"},
        {token.LBRACE, "{"},
        {token.IDENT, "x"},
        {token.PLUS, "+"},
        {token.IDENT, "y"},
        {token.SEMICOLON, ";"},
        {token.RBRACE, "}"},
        {token.SEMICOLON, ";"},
        {token.LET, "let"},
        {token.IDENT, "result"},
        {token.ASSIGN, "="},
        {token.IDENT, "add"},
        {token.LPAREN, "("},
        {token.IDENT, "five"},
        {token.COMMA, ","},
        {token.IDENT, "ten"},
        {token.RPAREN, ")"},
        {token.SEMICOLON, ";"},
        {token.BANG, "!"},
        {token.MINUS, "-"},
        {token.SLASH, "/"},
        {token.ASTERISK, "*"},
        {token.INT, "5"},
        {token.SEMICOLON, ";"},
        {token.INT, "5"},
        {token.LT, "<"},
        {token.INT, "10"},
        {token.GT, ">"},
        {token.INT, "5"},
        {token.SEMICOLON, ";"},
        {token.IF, "if"},
        {token.LPAREN, "("},
        {token.INT, "5"},
        {token.LT, "<"},
        {token.INT, "10"},
        {token.RPAREN, ")"},
        {token.LBRACE, "{"},
        {token.RETURN, "return"},
        {token.TRUE, "true"},
        {token.SEMICOLON, ";"},
        {token.RBRACE, "}"},
        {token.ELSE, "else"},
        {token.LBRACE, "{"},
        {token.RETURN, "return"},
        {token.FALSE, "false"},
        {token.SEMICOLON, ";"},
        {token.RBRACE, "}"},
    }

    l := New(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)
        }
    }
}

拓展,添加对!=和==的支持
添加常量

const (
    // ...

    EQ     = "=="
    NOT_EQ = "!="

    // ...
)

因为每次读入一个字符,所以不能直接 case !=来判别,应该复用!和=的判断分支,根据下一个字符来决定是返回=还是==

// 向前查看一个字符,但是不移动指针
func (l *Lexer) peekChar() byte {
    if l.readPosition >= len(l.input) {
        return 0
    } else {
        return l.input[l.readPosition]
    }
}

// 根据当前的ch创建词法单元
func (l *Lexer) NextToken() token.Token {
    var tok token.Token

    // 跳过空格
    l.skipWhitespace()

    switch l.ch {
    case '=':
        if l.peekChar() == '=' {
            // 记录当前ch (=)
            ch := l.ch
            l.readChar()
            literal := string(ch) + string(l.ch)
            tok = token.Token{Type: token.EQ, Literal: literal}
        } else {
            tok = newToken(token.ASSIGN, l.ch)
        }
    // ...
    case '!':
        if l.peekChar() == '=' {
            // 记录当前ch (!)
            ch := l.ch
            l.readChar()
            literal := string(ch) + string(l.ch)
            tok = token.Token{Type: token.NOT_EQ, Literal: literal}
        } else {
            tok = newToken(token.BANG, l.ch)
        }

    // ...
    }

    l.readChar()
    return tok
}

测试

// lexer/lexer_test.go
package lexer

import (
    "go-monkey-compiler/token"
    "testing"
)

func TestNextToken(t *testing.T) {
    input :=
        `
    let five = 5;
    let ten = 10;

    let add = fn(x, y) {
    x + y;
    };

    let result = add(five, ten);
    !-/*5;
    5 < 10 > 5;

    if (5 < 10) {
        return true;
    } else {
        return false;
    }

    10 == 10;
    10 != 9;
    `

    tests := []struct {
        expectedType    token.TokenType
        expectedLiteral string
    }{
        {token.LET, "let"},
        {token.IDENT, "five"},
        {token.ASSIGN, "="},
        {token.INT, "5"},
        {token.SEMICOLON, ";"},
        {token.LET, "let"},
        {token.IDENT, "ten"},
        {token.ASSIGN, "="},
        {token.INT, "10"},
        {token.SEMICOLON, ";"},
        {token.LET, "let"},
        {token.IDENT, "add"},
        {token.ASSIGN, "="},
        {token.FUNCTION, "fn"},
        {token.LPAREN, "("},
        {token.IDENT, "x"},
        {token.COMMA, ","},
        {token.IDENT, "y"},
        {token.RPAREN, ")"},
        {token.LBRACE, "{"},
        {token.IDENT, "x"},
        {token.PLUS, "+"},
        {token.IDENT, "y"},
        {token.SEMICOLON, ";"},
        {token.RBRACE, "}"},
        {token.SEMICOLON, ";"},
        {token.LET, "let"},
        {token.IDENT, "result"},
        {token.ASSIGN, "="},
        {token.IDENT, "add"},
        {token.LPAREN, "("},
        {token.IDENT, "five"},
        {token.COMMA, ","},
        {token.IDENT, "ten"},
        {token.RPAREN, ")"},
        {token.SEMICOLON, ";"},
        {token.BANG, "!"},
        {token.MINUS, "-"},
        {token.SLASH, "/"},
        {token.ASTERISK, "*"},
        {token.INT, "5"},
        {token.SEMICOLON, ";"},
        {token.INT, "5"},
        {token.LT, "<"},
        {token.INT, "10"},
        {token.GT, ">"},
        {token.INT, "5"},
        {token.SEMICOLON, ";"},
        {token.IF, "if"},
        {token.LPAREN, "("},
        {token.INT, "5"},
        {token.LT, "<"},
        {token.INT, "10"},
        {token.RPAREN, ")"},
        {token.LBRACE, "{"},
        {token.RETURN, "return"},
        {token.TRUE, "true"},
        {token.SEMICOLON, ";"},
        {token.RBRACE, "}"},
        {token.ELSE, "else"},
        {token.LBRACE, "{"},
        {token.RETURN, "return"},
        {token.FALSE, "false"},
        {token.SEMICOLON, ";"},
        {token.RBRACE, "}"},
        {token.INT, "10"},
        {token.EQ, "=="},
        {token.INT, "10"},
        {token.SEMICOLON, ";"},
        {token.INT, "10"},
        {token.NOT_EQ, "!="},
        {token.INT, "9"},
        {token.SEMICOLON, ";"},
        {token.EOF, ""},
    }

    l := New(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)
        }
    }
}

1.5 编写 REPL

REPL 即 Read-Eval-Print-Loop(读取-求值-打印循环)

REPL 读取输入,传给解释器求值,任何输出,并重复之前的步骤

这里是输入源代码,然后每次读取一行,直到遇到 EOF,期间输出词法生成器生成的词法单元

// repl/repl.go
package repl

import (
    "bufio"
    "fmt"
    "go-monkey-compiler/token"
    "go-monkey-compiler/lexer"
    "io"
)

const PROMPT = ">> "

func Start(in io.Reader, out io.Writer) {
    scanner := bufio.NewScanner(in)

    for {
        scanned := scanner.Scan()
        if !scanned {
            return
        }

        line := scanner.Text()
        l := lexer.New(line)

        for tok := l.NextToken(); tok.Type != token.EOF; tok = l.NextToken() {
            fmt.Fprintf(out, "%+v\n", tok)
        }
    }
}

创建 main.go,启动 REPL

// main.go
package main

import (
    "fmt"
    "go-monkey-compiler/repl"
    "os"
    "os/user"
)

func main() {
    user, err := user.Current()
    if err != nil {
        panic(err)
    }
    fmt.Printf("Hello %s! This is the Monkey programming language!\n", user.Username)
    fmt.Printf("Feel free to type in commands\n")
    repl.Start(os.Stdin, os.Stdout)
}

测试

2. 语法分析

2.1 语法分析器

语法分析器将输入的数据(通常是文本或词法单元形式的源代码)构建成一个数据结构(通常是某种解析树,抽象语法树…),同时检查语法是否正确

json,xml 等序列化语言的解析器和语法解析器(编程语言的)一样,都是把输入的文本构建成能表示这个输入的数据结构,但是 json 解析器的输入可以直接看出其数据结构{xx: ‘xxx’},而语法解析器却很难直接看出其解析生成的数据结构

AST 抽象语法树,抽象是指 AST 省略了源代码可见的某些细节(如; \n // 空格 {} [] ()). 不过,并没有一个通用的 AST 格式

js 有 MagicLexer 和 MagicParser 工具来构建 AST(抽象语法树)

2.2 为什么不用语法分析器生成器

语法分析器生成器(如 yacc,bison,ANTLR)可以根据描述生成特定语言的语法解析器

它们使用的是上下文无关法(CFG),最常用的 CFG 格式符号是 BNF 或 EBNF

很多资料提到可以跳过语法分析器,这是因为语法分析器的研究非常透彻,有很多可以直接用的成果,当然,为了学习考虑,最好是自己写一个,当然,不会耗费太多时间

2.3 为 Monkey 语言编写语法分析器

语法分析主要有两种策略: 自上而下和自下而上. 每种策略都有很多变体(如自上而下的递归下降分析,Earley 分析,预测分析)

我们使用递归下降语法分析,是基于自上而下的运算符优先级分析法,发明人是沃恩·普拉特,所以也叫普拉特语法分析器

自上而下和自下而上的区别是,前者从构建 AST 的根节点开始,然后下降,后者则相反. 新手推荐使用自上而下的递归下降语法分析,这更接近我们对 AST 的认知和 AST 的构造方式

2.4 语法分析器的第一步: 解析 let 语句

正确解析原 let 语句,意味着语法分析器需要生成一个 AST,该 AST 可以准确表示原 let 语句中包含的信息

(先跳过带表达式的 let)

let 的语句形式: let <标识符> = <表达式>

语句不会产生值,而表达式会(如 5 产生 5,add(5,5)也会返回一个值)

具体的语句和表达式的定义要看是什么编程语言,有的语言函数字面量是表达式,有的语言则只能作为函数声明语句的一部分

此时,我们的 AST 需要两种不同节点: 表达式和语句

// ast/ast.go
package ast

// 每个节点都需要实现Node接口
type Node interface {
    // 返回与该节点关联的字面量(该方法仅用于调试和测试)
    TokenLiteral() string
}
type Statement interface {
    // 实现Node接口
    Node
    // 占位方法,可以让go编译器帮忙找出误用(如Expression用成Statement)
    statementNode()
}
type Expression interface {
    Node
    expressionNode()
}

第一个 Node 实现(根节点),每个 Monkey 程序都是一系列位于 Program.Statements 中的语句

// ast/ast.go
type Program struct {
    Statements []Statement
}

func (p *Program) TokenLiteral() string {
    if len(p.Statements) > 0 {
        return p.Statements[0].TokenLiteral()
    } else {
        return ""
    }
}

为了解析 let,需要一个字段代表字面量(被绑定
上一个值),一个字段代表 let 语句里产生值的表达式,一个字段代表词法单元(用于实现 TokenLiteral)

let 里的标识符不会产生值,但是为了简单,所以类型是 Identifier 的 ExpressionNode,在其他需要用到标识符产生的值的地方,可以直接复用 Identifier

// ast/ast.go
// 标识符
type Identifier struct {
    Token token.Token // token.IDENT词法单元
    Value string
}

func (i *Identifier) expressionNode() {}

func (i *Identifier) TokenLiteral() string { return i.Token.Literal }

// let语句
type LetStatement struct {
    Token token.Token // token.LET词法单元
    Name  *Identifier // 标识符
    Value Expression  // 产生值的表达式
}

func (ls *LetStatement) statementNode() {

}

func (ls *LetStatement) TokenLiteral() string { return ls.Token.Literal }

此时 let x = 5;解析后的 AST 为:

构造 AST

// parser/parser.go
package parser

import (
    "go-monkey-compiler/ast"
    "go-monkey-compiler/lexer"
    "go-monkey-compiler/token"
)

type Parser struct {
    l *lexer.Lexer

    curToken  token.Token
    peekToken token.Token
}

func New(l *lexer.Lexer) *Parser {
    p := &Parser{l: l}

    // 读取两个词法单元,设置peekToken和curToken
    p.nextToken()
    p.nextToken()

    return p
}

func (p *Parser) nextToken() {
    p.curToken = p.peekToken
    p.peekToken = p.l.NextToken()
}

func (p *Parser) ParserProgram() *ast.Program {
    return nil
}

l 是词法分析器实例指针,用于不断获取下一个词法单元

两个 Token 一个指向当前词法单元,一个指向下一个,下一个词法单元用于判断下一步

完善 parseProgram

// 解析语句
func (p *Parser) parseStatement() ast.Statement {
    switch p.curToken.Type {
    // 遇到LET开头就解析let语句
    case token.LET:
        return p.parseLetStatement()
    default:
        return nil
    }
}

// 解析源码,构建AST
func (p *Parser) ParserProgram() *ast.Program {
    // 构造根节点
    program := &ast.Program{}
    program.Statements = []ast.Statement{}

    for p.curToken.Type != token.EOF {
        // 解析语句
        stmt := p.parseStatement()
        if stmt != nil {
            program.Statements = append(program.Statements, stmt)
        }
        p.nextToken()
    }

    return program
}

完善辅助方法(此时 ParseProgram 里的 for 循环条件改为!p.curTokenIs(token.EOF))

// 判断parser当前token是否和传入的token类型一致
func (p *Parser) curTokenIs(t token.TokenType) bool {
    return p.curToken.Type == t
}

// 判断parser下一个token是否和传入的token类型一致
func (p *Parser) peekTokenIs(t token.TokenType) bool {
    return p.peekToken.Type == t
}

// 是否是期望的token类型
func (p *Parser) expectPeek(t token.TokenType) bool {
    // 是期望类型就前移指针
    if p.peekTokenIs(t) {
        p.nextToken()
        return true
    } else {
        return false
    }
}

// 解析let语句
func (p *Parser) parseLetStatement() *ast.LetStatement {
    stmt := &ast.LetStatement{Token: p.curToken}

    // 如果接下来不是标识符(如果是,指针前移)
    if !p.expectPeek(token.IDENT) {
        return nil
    }

    stmt.Name = &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}

    // 如果接下来不是=
    if !p.expectPeek(token.ASSIGN) {
        return nil
    }

    // TODO: 跳过对表达式的处理,直到遇见分号
    for !p.curTokenIs(token.SEMICOLON) {
        p.nextToken()
    }

    return stmt
}

测试

package parser

import (
    "go-monkey-compiler/ast"
    "go-monkey-compiler/lexer"
    "testing"
)

func TestLetStatements(t *testing.T) {
    input := `
    let x = 5;
    let y = 10;
    let foobar = 838383;
    `
    l := lexer.New(input)
    p := New(l)

    program := p.ParserProgram()
    if program == nil {
        t.Fatalf("ParserProgram() returned nil")
    }
    if len(program.Statements) != 3 {
        t.Fatalf("program.Statements does not contain 3 statements. got=%d", len(program.Statements))
    }

    tests:=[]struct {
        expressionIdentifier string
    }{
        {"x"},{"y"},{"foobar"},
    }
    for i,tt:=range tests{
        stmt:=program.Statements[i]
        if !testLetStatment(t,stmt,tt.expressionIdentifier){
            return
        }
    }
}
func testLetStatment(t *testing.T,s ast.Statement,name string)bool{
    if s.TokenLiteral()!="let"{
        t.Errorf("s.TokenLiteral not 'let'. got=%q",s.TokenLiteral())
        return false
    }

    letStmt,ok:=s.(*ast.LetStatement)
    if !ok{
        t.Errorf("s not *ast.LetStatement. got=%T",s)
        return false
    }

    if letStmt.Name.Value != name{
        t.Errorf("letStmt.Name.Value not '%s'. got=%s",name,letStmt.Name.Value)
        return false
    }

    if letStmt.Name.TokenLiteral()!=name{
        t.Errorf("letStmt.Name.TokenLiteral() not '%s'. got=%s",name,letStmt.Name.TokenLiteral())
        return false
    }

    return true
}

expectPeek 是断言函数,大部分语法分析器有很多断言函数,断言函数通过检查下一个词法单元的类型,确保词法单元顺序的正确性

但是,如果遇到错误的输入,会返回 nil,而 ParseProgram 会忽略这个语句,因此应该添加错误处理

type Parser struct {
    l *lexer.Lexer

    errors    []string
    curToken  token.Token
    peekToken token.Token
}

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

    // ...
}

func (p *Parser) Errors() []string {
    return p.errors
}

func (p *Parser) peekError(t token.TokenType) {
    msg := fmt.Sprintf("expected next token to be %s, got %s instead", t, p.peekToken.Type)
    p.errors = append(p.errors, msg)
}

在 expectPeek 里添加错误处理

// 是否是期望的token类型
func (p *Parser) expectPeek(t token.TokenType) bool {
    // 是期望类型就前移指针
    if p.peekTokenIs(t) {
        p.nextToken()
        return true
    } else {
        // 记录error
        p.peekError(t)
        return false
    }
}

测试(在创建 program 后进行 error 检查)

package parser

import (
    "go-monkey-compiler/ast"
    "go-monkey-compiler/lexer"
    "testing"
)

func checkParserError(t *testing.T, p *Parser) {
    errors := p.Errors()
    if len(errors) == -0 {
        return
    }

    t.Errorf("parser has %d errors", len(errors))
    for _, msg := range errors {
        t.Errorf("parser error: %q", msg)
    }
    t.FailNow()
}
func TestLetStatements(t *testing.T) {
    input := `
    let x = 5;
    let y = 10;
    let 838 383;
    `

    // ...

    program := p.ParserProgram()
    checkParserError(t, p)

    // ...
}

我们遇到错误不会马上停止,而是解析完再退出,也就是说可以一次运行就捕获所有异常

2.5 解析 return 语句

return 语句的结构: return <表达式>;

// ast/ast.go
type ReturnStatement struct {
    Token       token.Token // 'return'词法单元
    ReturnValue Expression
}

func (rs *ReturnStatement) statementNode()       {}
func (rs *ReturnStatement) TokenLiteral() string { return rs.Token.Literal }

parseStatement 接收 return 词法单元

// 解析return语句
func (p *Parser) parseReturnStatement() *ast.ReturnStatement {
    stmt := &ast.ReturnStatement{Token: p.curToken}

    p.nextToken()

    // TODO: 跳过对表达式的处理,直到分号
    for !p.curTokenIs(token.SEMICOLON) {
        p.nextToken()
    }

    return stmt
}

// 解析语句
func (p *Parser) parseStatement() ast.Statement {
    switch p.curToken.Type {
    // 遇到LET开头就解析let语句
    case token.LET:
        return p.parseLetStatement()
    // 遇到return开头就解析return语句
    case token.RETURN:
        return p.parseReturnStatement()
    default:
        return nil
    }
}

测试

func TestReturnStatement(t *testing.T) {
    input := `
    return 5;
    return 10;
    return 933 322;
    `
    l := lexer.New(input)
    p := New(l)

    program := p.ParseProgram()
    checkParserError(t, p)

    if len(program.Statements) != 3 {
        t.Fatalf("program.Statements does not contain 3 statements. got=%d", len(program.Statements))
    }

    for _, stmt := range program.Statements {
        returnStmt, ok := stmt.(*ast.ReturnStatement)
        if !ok {
            t.Errorf("stmt not *ast.ReturnStatement. got=%T", stmt)
            continue
        }
        if returnStmt.TokenLiteral() != "return" {
            t.Errorf("returnStmt.TokenLiteral not 'return'. got %q", returnStmt.TokenLiteral())
        }
    }
}

2.6 解析表达式

解析语句: 从左到右处理词法单元,然后期望或拒绝下一个词法单元,如果一切正常,最后就返回一个 AST 节点

解析表达式有两个大挑战

  • 运算符优先级 55+10 5(5+10)
  • 表达式中,相同的词法单元可能出现在多个位置,如 -5 - 10 (-出现了两次,但是意义不同) 5*(add(2,3) + 10) (两次括号意义不同)

2.6.1 Monkey 中的表达式

Monkey 中,除了 let 和 return 以外的所有内容都是表达式

  • 前缀运算符: -5 !true !false
  • 中缀运算符(二元运算符): 5+5 5-5 5/5 5*5
  • 比较运算符: foo == bar foo != bar foo < bar foo > bar
  • 括号
  • 调用表达式: add(2,3)
  • 标识符也是表达式
  • 函数字面量也是表达式: let add = fn(x,y){return x+y}
  • if 表达式: let res = if(10>5) {true} else {false}

2.6.2 自上而下的运算符优先级分析(普拉特解析法)

普拉特解析法,是基于上下文无关文法和 Backus-Naur-Form 语法分析器的替代方法

普拉特解析法与其他语法分析方法的主要区别在于: 普拉特并没有将解析函数与语法规则相关联,
而是将这些函数(语义代码 semantic code)与单个词法单元类型相关联,关键是,每种词法单元类型都可以具有两个与之相关联的解析函数,具体取决于词法单元的位置,如前缀或中缀

2.6.3 术语

  • 前缀运算符: 位于操作数前面的运算符(如 –5 –是递减,5 是操作数)
  • 后缀运算符: 位于操作数后面的运算符(如 foobar++) -> Monkey 没有该类型的运算符
  • 中缀运算符: 如 5*8
  • 运算符优先级(也可以称为运算顺序)

2.6.4 准备 AST

之前说 Monkey 只有 let 和 return 语句,但是现在要加上表达式语句,这只是一层封装,表达式语句并非真正的语句

添加表达式语句,是因为脚本语言大多支持一种只有表达式的单行语句(如 x+10)

// ast/ast.go
// 表达式语句(e.g. x+10)
type ExpressionStatement struct {
    Token      token.Token // 该表达式中第一个词法单元
    Expression Expression
}

func (es *ExpressionStatement) statementNode()       {}
func (es *ExpressionStatement) TokenLiteral() string { return es.Token.Literal }

给 AST 节点添加 String 方法,可以方便调试和比较 AST 节点

// ast/ast.go
type Node interface {
    // 返回与该节点关联的字面量(该方法仅用于调试和测试)
    TokenLiteral() string
    String() string
}

Program 实现 String 方法,先创建一个缓冲区,然后把每个 statement 的 String 存入,并最终转 String 返回

import (
    ...
    "bytes"
)

func (p *Program) String() string {
    var out bytes.Buffer

    for _, s := range p.Statements {
        out.WriteString(s.String())
    }

    return out.String()
}

为 LetStatement,ReturnStatement,ExpressionStatement 添加 String 方法

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 ""
}

为 Identifier 添加 String 方法

func (i *Identifier) String() string { return i.Value }

测试

package ast

import (
    "go-monkey-compiler/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())
    }
}

2.6.5 实现普拉特语法分析器

主要思想: 将解析函数(语义代码)和词法单元类型相关联,遇到某个词法单元类型时,就调用解析函数解析表达式,然后返回生成的 AST 节点,每个词法单元类型最大可以关联两个解析函数(前缀/中缀)

设置关联,这里的中缀表达式解析函数接收的是 所解析的中缀运算符左侧的内容,根据定义,前缀运算符的左侧为空,所有没有该参数

// parser/parser.go
type (
    prefixParseFn func() ast.Expression
    infixParseFn  func(ast.Expression) ast.Expression
)

给 Parser 添加前缀解析函数和中缀解析函数的 map [词法单元类型]解析函数

// 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
}

辅助函数,用来向 map 添加内容

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
}

2.6.6 标识符

拓展 parseStatement 方法,因为只有 let 和 return 语句,所以不是这两种的就是表达式语句

// 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
}

// 解析语句
func (p *Parser) parseStatement() ast.Statement {
    switch p.curToken.Type {
    // 遇到LET开头就解析let语句
    case token.LET:
        return p.parseLetStatement()
    // 遇到return开头就解析return语句
    case token.RETURN:
        return p.parseReturnStatement()
    // 解析表达式
    default:
        return p.parseExpressionStatement()
    }
}

定义优先级常量

// parser/parser.go
const (
    _ int = iota // 0
    LOWEST
    EQUALS     // ==
    LESSGEATER // > or <
    SUM        // +
    PRODUCT    // *
    PREFIX     // -X or !X
    CALL       // myFunction(X)
)

parseExpression,添加解析前缀表达式

// parser/parser.go
func (p *Parser) parseExpression(preceduece int) ast.Expression {
    // 获取前缀处理函数
    prefix := p.prefixParseFns[p.curToken.Type]
    if prefix == nil {
        return nil
    }
    // 调用处理函数,返回左侧表达式
    leftExp := prefix()

    return leftExp
}

创建时关联解析函数,curToken 在解析函数解析完时,会变成当前表达式类型中最后一个词法单元

// parser/parser.go
func (p *Parser) parseIdentifier() ast.Expression {
    return &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
}

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

    // 读取两个词法单元,设置peekToken和curToken
    p.nextToken()
    p.nextToken()

    // 关联解析函数
    p.prefixParseFns=make(map[token.TokenType]prefixParseFn)
    p.registerPrefix(token.IDENT,p.parseIdentifier)

    return p
}

测试

func TestIdentifierExpression(t *testing.T) {
    input := "foobar;"

    l := lexer.New(input)
    p := New(l)
    program := p.ParseProgram()
    checkParserError(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())
    }
}

2.6.7 整数字面量

整数字面量也是表达式,其产生的值就是整数本身

添加 IntegerLiteral 表达式

// 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 }

源码是字符串,需要将字符串”5”转为 int 类型

// parser/parser.go
// 解析函数-整数字面量-前缀
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
}

注册该解析函数到 token.INT 词法单元

// 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)

    return p
}

测试

func TestIntegerLiteralExpression(t *testing.T) {
    input := "5;"

    l := lexer.New(input)
    p := New(l)
    program := p.ParseProgram()
    checkParserError(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())
    }
}

2.6.8 前缀运算符

前缀运算符语法结构: <前缀运算符><表达式>;

定义 PrefixExpression 节点

// ast/ast.go
type PrefixExpression struct {
    Token    token.Token // 前缀词法单元 - !
    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()
}

添加对无法解析的语句的处理

// 无法解析的语句
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(preceduece int) ast.Expression {
    // 获取前缀处理函数
    prefix := p.prefixParseFns[p.curToken.Type]
    if prefix == nil {
        // 处理未知语句
        p.noPrefixParseFnError(p.curToken.Type)
        return nil
    }
    // 调用处理函数,返回左侧表达式
    leftExp := prefix()

    return leftExp
}

为前缀表达式编写解析函数并注册,会调用 nextToken,因为前缀表达式解析需要多个词法单元(如-5 需要-和 5),在 nextToken 之后,会再次调用 nextToken,此次也会进行表达式解析,而此次的解析传入的优先级是不同的,优先级后续会用到

nextToken 之后,新的词法单元(如 5->token.INT)会产生新的节点,并填充前缀表达式的 Right 字段

// 解析函数-前缀表达式-前缀
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
}

// 创建解析器
func New(l *lexer.Lexer) *Parser {
    // ...

    p.registerPrefix(token.BANG, p.parsePrefixExpression)
    p.registerPrefix(token.MINUS, p.parsePrefixExpression)

    return p
}

测试

func TestParsingPrefixExpressions(t *testing.T) {
    prefixTests := []struct {
        input        string
        operator     string
        integerValue int64
    }{
        {"!5;", "!", 5},
        {"-15", "-", 15},
    }

    for _, tt := range prefixTests {
        l := lexer.New(tt.input)
        p := New(l)
        program := p.ParseProgram()
        checkParserError(t, p)

        if len(program.Statements) != 1 {
            t.Fatalf("program.Statements does not contain %d statements. got=%d", 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 !testIntegerLiteral(t, exp.Right, tt.integerValue) {
            return
        }
    }
}

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
}

2.6.9 中缀运算符

语法结构: <表达式><中缀运算符><表达式>

因为中缀表达式两边有表达式,所以也可以叫二元表达式,而前缀表达式也可以叫一元表达式

定义 ast.InfixExpression

// ast/ast.go
// 中缀表达式
type InfixExpression struct {
    Token    token.Token // 运算符词法单元,如+
    Left     Expression
    Operator string
    Right    Expression
}

func (ie *InfixExpression) expressionNode()      {}
func (ie *InfixExpression) TokenLiteral() string { return ie.Token.Literal }
func (ie *InfixExpression) String() string {
    var out bytes.Buffer

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

    return out.String()
}

*定义优先级表和辅助方法

// parser/parser.go
// 优先级map
var precedences = map[token.TokenType]int{
    token.EQ:       EQUALS,
    token.NOT_EQ:   EQUALS,
    token.LT:       LESSGEATER,
    token.GT:       LESSGEATER,
    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
}

注册中缀解析函数

// 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()
    // 进入下一个词法单元然后填充Right
    p.nextToken()
    // 解析下一个表达式,并传入优先级
    expression.Right = p.parseExpression(precedence)

    return expression
}
// 创建解析器
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)

    return p
}

普拉特语法分析器的核心: parseExpression 最终版本

// 解析表达式
func (p *Parser) parseExpression(preceduece 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) && preceduece < p.peekPrecedence() {
        infix := p.infixParseFns[p.peekToken.Type]
        // 如果没有中缀解析函数->不是中缀表达式或没有解析
        if infix == nil {
            // 前面已经处理了前缀表达式,直接返回
            return leftExp
        }

        p.nextToken()

        // 解析中缀表达式
        leftExp = infix(leftExp)
    }
    return leftExp
}

测试

func TestParsingInfixExpressions(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},
        {"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()
        checkParserError(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
        }
    }
}
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))"},
        {"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()
        checkParserError(t, p)

        actual := program.String()
        if actual != tt.expected {
            t.Errorf("expected=%q, got=%q", tt.expected, actual)
        }
    }
}

2.7 普拉特解析的工作方式

普拉特论文里的 nuds(nuds denotations)对应我们的 prefixParseFn,leds 对应我们的 infixParseFns

例子 1+2+3 ,需要两个 InfixExpression,位置高的是{Left: {InfixExpression2},Right: 3},位置低的是 InfixExpression2:{Left: 1,Right: 2}

解析 1+时,先检查有无 1 的前缀处理函数,发现有,调用 parseIntegerLiteral,然后 parseExpression 将返回结果给了 leftExp

进入 parseExpression 的 for 循环,没到分号,并且 1 后面的+号优先级高于整数,所以先调用+号的中缀解析函数

for !p.parseTokenIs(token.SEMICOLON) && precedence < p.peekPrecedence(){}

此时调用 nextToken,指针前移,然后调用中缀函数处理+,将结果赋给 leftExp

infix := p.infixParseFns[p.peekToken.Type]
if infix == nil{
    return leftExp
}
p.nextToken()
leftExp = infix(leftExp)

接下来,保存左值和当前优先级,再次 nextToken(调用完,指针指向 2 和+),然后传递优先级(第一个+的优先级),再次使用 parseExpression

func (p *Parser) parseInfixExpression(left ast.Expression) ast.Expression {
    expression := &ast.InfixExpression{
        Token:    p.curToken,
        Operator: p.curToken.Literal,
        Left:     left,
    }

    precedence := p.curPrecedence()
    // 进入下一个词法单元然后填充Right
    p.nextToken()
    // 解析下一个表达式,并传入优先级
    expression.Right = p.parseExpression(precedence)

    return expression
}

parseExpression 先寻找前缀解析函数,此时 2 是 curToken,其解析函数返回整数字面量,但是此时 for 循环 peerToken(第二个)的优先级并不大于传入的(第一个+的优先级)优先级,所以直接返回 leftExp,作为第一次 parseInfix 的右值

此时回退到第一次 parseExpression 的 for 循环,优先级为 LOWEST(1 的优先级),继续循环,此时的 peekToken 的优先级是(第二个+),所以继续循环,而此时 leftExp 是刚才解析完的 InfixExpression{Left: 1,Right: 2}

此时,找到第二个+的中缀解析函数,再次 nextToken,传递 leftExp 调用该中缀解析函数,结果返回 ast.IntegerLiteral(3),将 ast 构建完成

for 循环条件里的 p.peekTokenIs(token.SEMICOLON)不是必须的,因为分号的优先级也是 LOWEST,如果循环到分号词法单元,也会退出循环

为了产生正确的 ast,则优先级高的应该出现在 ast 的高位,低的则处于低位

precedence 的值代表当前 parseExpression 中的右约束能力,右约束越强,则当前表达式和后续词法单元右边可以约束的词法单元|运算符|操作数越多,如果右约束为最大,则它的 leftExp 不会成为左节点

左约束能力则来自于 peekPrecedence 的调用,其返回值代表下一个运算符的左约束能力,如果下一个运算符或词法单元的左约束能力大于当前的右约束能力,则会从左到右融合当前和下一个运算符(或词法单元),最终传递给下一个运算符的 infixParseFn

Monkey 中的运算符优先级只是一个单独的值,没有分别定义左右约束能力(两者数值等同优先级),因此,如果需要实现+的右关联,需要调用 parseExpression 时降低其优先级

// 解析函数-中缀表达式-中缀
func (p *Parser) parseInfixExpression(left ast.Expression) ast.Expression {
    expression := &ast.InfixExpression{
        Token:    p.curToken,
        Operator: p.curToken.Literal,
        Left:     left,
    }

    precedence := p.curPrecedence()
    // 进入下一个词法单元然后填充Right
    p.nextToken()
    // 解析下一个表达式,并传入优先级
    // expression.Right = p.parseExpression(precedence)
    // 为了获取右关联特性,降低运算符优先级
    if expression.Operator == "+" {
        expression.Right = p.parseExpression(precedence - 1)
    } else {
        expression.Right = p.parseExpression(precedence)
    }

    return expression
}

此时,测试结果是右关联的

记得把代码改回去

2.8 拓展语法分析器

新的测试辅助函数,因为太麻烦所以不写了

2.8.1 布尔字面量

// ast/ast.go
type Boolean struct {
    Token token.Token
    Value bool
}

func (b *Boolean) expressionNode()      {}
func (b *Boolean) TokenLiteral() string { return b.Token.Literal }
func (b *Boolean) String() string       { return b.Token.Literal }

为布尔字面量提供前缀解析函数

// 解析函数-布尔字面量-前缀
func (p *Parser) parseBoolean() ast.Expression {
    return &ast.Boolean{Token: p.curToken, Value: p.curTokenIs(token.TRUE)}
}

// 创建解析器
func New(l *lexer.Lexer) *Parser {
    // ...

    p.registerPrefix(token.TRUE, p.parseBoolean)
    p.registerPrefix(token.FALSE, p.parseBoolean)

    // ...

    return p
}

2.8.2 分组表达式

括号可以给表达式分组,并修改优先级,不过括号并不是具体的 ast 节点类型,不需要添加 ast 定义

// parser/parser.go
// 解析函数-分组表达式(括号)-前缀
func (p *Parser) parseGroupedExpression() ast.Expression {
    p.nextToken()

    exp := p.parseExpression(LOWEST)

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

    return exp
}

// 创建解析器
func New(l *lexer.Lexer) *Parser {
    p := &Parser{l: l, errors: []string{}}

    // 读取两个词法单元,设置peekToken和curToken
    p.nextToken()
    p.nextToken()

    // 关联解析函数
    p.prefixParseFns = make(map[token.TokenType]prefixParseFn)
    p.registerPrefix(token.IDENT, p.parseIdentifier)
    p.registerPrefix(token.INT, p.parseIntegerLiteral)
    p.registerPrefix(token.BANG, p.parsePrefixExpression)
    p.registerPrefix(token.MINUS, p.parsePrefixExpression)
    p.registerPrefix(token.TRUE, p.parseBoolean)
    p.registerPrefix(token.FALSE, p.parseBoolean)
    p.registerPrefix(token.LPAREN, p.parseGroupedExpression)

    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)

    return p
}

2.8.3 if 表达式

语法结构 if (<条件>) <结果> else <可替代的结果>

这里的结果,是块语句,用{}包起来的多条语句

// ast/ast.go
type IfExpression struct {
    Token       token.Token     // if词法单元
    Condition   Expression      // 条件表达式
    Consequence *BlockStatement // 结果
    Alternative *BlockStatement // 可替换的结果
}

func (ie *IfExpression) expressionNode()      {}
func (ie *IfExpression) TokenLiteral() string { return ie.Token.Literal }
func (ie *IfExpression) String() string {
    var out bytes.Buffer

    out.WriteString("if")
    out.WriteString(ie.Condition.String())
    out.WriteString(" ")
    out.WriteString(ie.Consequence.String())

    if ie.Alternative != nil {
        out.WriteString("else ")
        out.WriteString(ie.Alternative.String())
    }

    return out.String()
}

type BlockStatement struct {
    Token      token.Token // '{'词法单元
    Statements []Statement
}

func (bs *BlockStatement) statementNode()       {}
func (bs *BlockStatement) TokenLiteral() string { return bs.Token.Literal }
func (bs *BlockStatement) String() string {
    var out bytes.Buffer

    for _, s := range bs.Statements {
        out.WriteString(s.String())
    }

    return out.String()
}

添加前缀解析函数

// parser/parser.go
func (p *Parser) parseIfExpression() ast.Expression {
    expression := &ast.IfExpression{Token: p.curToken}

    // if(
    if !p.expectPeek(token.LPAREN) {
        return nil
    }

    p.nextToken()
    // 解析if()里的表达式
    expression.Condition = p.parseExpression(LOWEST)

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

    // if(){
    if !p.expectPeek(token.LBRACE) {
        return nil
    }

    // 解析块内语句
    expression.Consequence = p.parseBlockStatement()

    return expression
}
func New(l *lexer.Lexer) *Parser {
    // ...

    p.registerPrefix(token.IF, p.parseIfExpression)

    // ...
}

解析块内语句

// 解析块内语句
func (p *Parser) parseBlockStatement() *ast.BlockStatement {
    block := &ast.BlockStatement{Token: p.curToken}
    block.Statements = []ast.Statement{}

    p.nextToken()

    // !}
    for !p.curTokenIs(token.RBRACE) && !p.curTokenIs(token.EOF) {
        stmt := p.parseStatement()
        if stmt != nil {
            block.Statements = append(block.Statements, stmt)
        }
        p.nextToken()
    }

    return block
}

解析 else 语句(else 是可选的,没有也不报错)

func (p *Parser) parseIfExpression() ast.Expression {
    // ...

    // 解析块内语句
    expression.Consequence = p.parseBlockStatement()

    if p.peekTokenIs(token.ELSE) {
        p.nextToken()

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

        expression.Alternative = p.parseBlockStatement()
    }

    return expression
}

2.8.4 函数字面量

语法结构: fn <参数列表><块语句>

参数列表: (<参数 1>,<参数 2>,…)

函数字面量是表达式节点

type FunctionLiteral struct {
    Token      token.Token // 'fn'词法单元
    Parameters []*Identifier
    Body       *BlockStatement
}

func (fl *FunctionLiteral) expressionNode()      {}
func (fl *FunctionLiteral) TokenLiteral() string { return fl.Token.Literal }
func (fl *FunctionLiteral) String() string {
    var out bytes.Buffer

    params := []string{}
    for _, p := range fl.Parameters {
        params = append(params, p.String())
    }

    out.WriteString((fl.TokenLiteral()))
    out.WriteString("(")
    out.WriteString(strings.Join(params, ", "))
    out.WriteString(") ")
    out.WriteString(fl.Body.String())

    return out.String()
}

注册前缀解析函数

// 解析函数参数列表
func (p *Parser) parseFunctionParameter() []*ast.Identifier {
    identifiers := []*ast.Identifier{}

    // fn()
    if p.peekTokenIs(token.RPAREN) {
        p.nextToken()
        return identifiers
    }

    p.nextToken()

    ident := &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
    identifiers = append(identifiers, ident)

    // fn(arg1,
    for p.peekTokenIs(token.COMMA) {
        p.nextToken() // arg2
        p.nextToken() // ,
        ident := &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
        identifiers = append(identifiers, ident)
    }

    // fn(arg1,arg2)
    if !p.expectPeek(token.RPAREN) {
        return nil
    }
    return identifiers
}

// 解析函数-函数表达式-前缀
func (p *Parser) parseFunctionLiteral() ast.Expression {
    lit := &ast.FunctionLiteral{}

    // fn(
    if !p.expectPeek(token.LPAREN) {
        return nil
    }

    lit.Parameters = p.parseFunctionParameter()

    // fn (args){
    if !p.expectPeek(token.LBRACE) {
        return nil
    }

    lit.Body = p.parseBlockStatement()

    return lit
}
// 创建解析器
func New(l *lexer.Lexer) *Parser {
    // ...

    p.registerPrefix(token.FUNCTION, p.parseFunctionLiteral)

    // ...
}

2.8.5 调用表达式

语法结构: <表达式>(<逗号分隔的表达式列表>)

// ast/ast.go
type CallExpression struct {
    Token     token.Token // '('词法单元
    Function  Expression  // 标识符或函数字面量
    Arguments []Expression
}

func (ce *CallExpression) expressionNode()      {}
func (ce *CallExpression) TokenLiteral() string { return ce.Token.Literal }
func (ce *CallExpression) String() string {
    var out bytes.Buffer

    args := []string{}
    for _, a := range ce.Arguments {
        args = append(args, a.String())
    }

    out.WriteString((ce.Function.String()))
    out.WriteString("(")
    out.WriteString(strings.Join(args, ", "))
    out.WriteString(") ")

    return out.String()
}

但使用调用表达式时(如 add(2,3)),括号处于中间位置,实际上需要中缀表达式来解析

// parser/parser.go
// 解析调用参数
func (p *Parser) parseCallArguments() []ast.Expression {
    args := []ast.Expression{}

    // add()
    if p.peekTokenIs(token.RPAREN) {
        p.nextToken()
        return args
    }

    p.nextToken()
    args = append(args, p.parseExpression(LOWEST))

    // add(2,
    for p.peekTokenIs(token.COMMA) {
        p.nextToken() // 3
        p.nextToken() // ) or ,
        args = append(args, p.parseExpression(LOWEST))
    }

    // add(2,3)
    if !p.expectPeek(token.RPAREN) {
        return nil
    }

    return args
}

// 解析函数-调用表达式-中缀
func (p *Parser) parseCallExpression(function ast.Expression) ast.Expression {
    exp := &ast.CallExpression{Token: p.curToken, Function: function}
    exp.Arguments = p.parseCallArguments()
    return exp
}
// 创建解析器
func New(l *lexer.Lexer) *Parser {
    // ...

    p.registerInfix(token.LPAREN,p.parseCallExpression)

    return p
}

此时还无法正确解析调用表达式,因为左括号没有优先级,没有足够的’黏性’,为此,需要添加优先级

// parser/parser.go
// 优先级map
var precedences = map[token.TokenType]int{
    token.EQ:       EQUALS,
    token.NOT_EQ:   EQUALS,
    token.LT:       LESSGEATER,
    token.GT:       LESSGEATER,
    token.PLUS:     SUM,
    token.MINUS:    SUM,
    token.SLASH:    PRODUCT,
    token.ASTERISK: PRODUCT,
    token.LPAREN: CALL,
}

语法分析器已经完成,接下来就是对之前留下的 todo 进行处理,然后拓展 REPL

2.8.6 删除 TODO

在解析 let 和 return 时,我们跳过了对表达式的处理

最终版 parseReturnStatement 和 parseLetStatement

// 解析let语句
func (p *Parser) parseLetStatement() *ast.LetStatement {
    stmt := &ast.LetStatement{Token: p.curToken}

    // 如果接下来不是标识符(如果是,指针前移)
    if !p.expectPeek(token.IDENT) {
        return nil
    }

    stmt.Name = &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}

    // 如果接下来不是=
    if !p.expectPeek(token.ASSIGN) {
        return nil
    }

    p.nextToken()

    stmt.Value = p.parseExpression(LOWEST)

    if p.peekTokenIs(token.SEMICOLON) {
        p.nextToken()
    }

    return stmt
}

// 解析return语句
func (p *Parser) parseReturnStatement() *ast.ReturnStatement {
    stmt := &ast.ReturnStatement{Token: p.curToken}

    p.nextToken()

    stmt.ReturnValue = p.parseExpression(LOWEST)

    for p.curTokenIs(token.SEMICOLON) {
        p.nextToken()
    }

    return stmt
}

2.9 RPPL

RLPL(read-lex-printLoop 读取-词法分析-打印循环)

目前还无法将词法分析(lex)替换为求值(evaluate),但是可以替换为语法分析(parse) -> RPPL

// repl/repl.go
// repl/repl.go
package repl

import (
    "bufio"
    "fmt"
    "go-monkey-compiler/lexer"
    "go-monkey-compiler/parser"
    "io"
)

const PROMPT = ">> "

func Start(in io.Reader, out io.Writer) {
    scanner := bufio.NewScanner(in)

    for {
        fmt.Fprintf(out, PROMPT)
        scanned := scanner.Scan()
        if !scanned {
            return
        }

        line := scanner.Text()
        l := lexer.New(line)
        p := parser.New(l)
        program := p.ParseProgram()
        if len(p.Errors()) != 0 {
            printParserErrors(out, p.Errors())
            continue
        }

        io.WriteString(out, program.String())
        io.WriteString(out, "\n")
    }
}

func printParserErrors(out io.Writer, errors []string) {
    for _, msg := range errors {
        io.WriteString(out, "\t"+msg+"\n")
    }
}

可以添加一个字符图形,如果遇到语法错误就打印

// repl/repl.go
package repl

import (
    "bufio"
    "fmt"
    "go-monkey-compiler/lexer"
    "go-monkey-compiler/parser"
    "io"
)

const PROMPT = ">> "

const MONKEY_FACE = `            __,__
   .--.  .-"     "-.  .--.
  / .. \/  .-. .-.  \/ .. \
 | |  '|  /   Y   \  |'  | |
 | \   \  \ 0 | 0 /  /   / |
  \ '- ,\.-"""""""-./, -' /
   ''-' /_   ^ ^   _\ '-''
       |  \._   _./  |
       \   \ '~' /   /
        '._ '-=-' _.'
           '-----'
`
const MALRED_LOGO = `
 __  __    __    __    ____  ____  ____
(  \/  )  /__\  (  )  (  _ \( ___)(  _ \
 )    (  /(__)\  )(__  )   / )__)  )(_) )
(_/\/\_)(__)(__)(____)(_)\_)(____)(____/

`
const ERROR_LOGO = ` ____  ____  ____  _____  ____
( ___)(  _ \(  _ \(  _  )(  _ \
 )__)  )   / )   / )(_)(  )   /
(____)(_)\_)(_)\_)(_____)(_)\_)

`

func Start(in io.Reader, out io.Writer) {
    scanner := bufio.NewScanner(in)
    io.WriteString(out, MALRED_LOGO)

    for {
        fmt.Fprintf(out, PROMPT)
        scanned := scanner.Scan()
        if !scanned {
            return
        }

        line := scanner.Text()
        l := lexer.New(line)
        p := parser.New(l)

        program := p.ParseProgram()
        if len(p.Errors()) != 0 {
            printParserErrors(out, p.Errors())
            continue
        }

        io.WriteString(out, program.String())
        io.WriteString(out, "\n")
    }
}

func printParserErrors(out io.Writer, errors []string) {
    io.WriteString(out, MONKEY_FACE)
    io.WriteString(out, ERROR_LOGO)
    io.WriteString(out, "Woops! We ran into some monkey business here!\n")
    for _, msg := range errors {
        io.WriteString(out, "\t"+msg+"\n")
    }
}

3. 求值

解释器的求值过程决定了一门编程语言的解释方式

3.2 求值策略

求值策略是不同编程语言的解释器实现中差异最大的地方,这里说一下,编译器和解释器的区别是会不会生成可执行文件,但是高度优化的编程语言里,两者没有非常清晰的界定

最直观最传统的方式是直接遍历 AST,访问每个节点并执行该节点的语义(实时执行),这种解释器被称为树遍历解释器,有时在求值步骤前,会进行少量优化,比如重写 AST(如删除未使用的变量绑定),或转换更适合递归和重复求值的另一个中间表示(IR)

其他类型的解释器也会遍历 AST,但是不是解释 AST 本身,而是先将其转换为字节码再解释. 字节码是 AST 的另一种中间表示,信息密度比 AST 高.各个解释器的字节码格式及其操作码(构成字节码的指令)各不相同.通常操作码与大多数汇编语言的助记符非常相似.大多数字节码定义包含用于 push 和 pop 执行栈操作的操作码.但是字节码不能直接在机器和操作系统上运行,而是要在解释器的虚拟机中运行.这比直接解释 AST 的性能好

还有一种策略,语法分析器不生成 AST,而是直接生成字节码.此时,解释和编译的边界就模糊了.

还有一些情况更难界定解释和编译,比如有的语言会解析源代码,构建 AST,生成字节码,然后执行之前,虚拟机即时将字节码编译为机器代码,而不是直接在虚拟机中执行字节码指定的操作,这就是所谓的 JIT(Just in Time)解释器/编译器

另外,有些解释器不生成字节码,而是递归遍历 AST,在执行某个特定分支前,节点会被编译成本地机器代码,然后 ‘即时’执行这些机器代码.有些则是特定分支多次求值后才会将该分支编译为机器代码

选择哪种策略主要取决于性能和可移植性的需求、所要解释的编程语言类型以及完成到什么程度.递归 AST 的树遍历解释器速度最慢,但是易于构建、拓展和总结,并且能使用宿主语言的地方就能使用它.

如果要生成字节码并用虚拟机求值,则速度会快很多,但是更复杂和更难构建.要添加 JIT 编译成机器代码的功能,则需要支持多种机器架构

选择何种策略,也会随着编程语言的发展而改变,.Ruby1.8 之前是树遍历,1.9 开始切换为虚拟机架构;WebKit 的 js 引擎 javascriptCore 和它的 Squirrelfish 解释器之前也是遍历 AST 并直接执行,2008 年切换到虚拟机和解释字节码的方式.

lua 的最初实现是解释器,生成字节码并在基于寄存器的虚拟机中执行.后来,有了 LuaJIT,用 JIT 将紧凑的字节码格式编译为针对不同体系结构且高度优化的机器代码

3.3 树遍历解释器

我们将实现树遍历解释器,会非常像 Lisp 解释器,受到《计算机程序的构造和解释》(SICP)中介绍的解释器的启发

该基本架构需要实现两项内容: 1.基于树遍历的求值器;2.在宿主语言 Go 中表示 Monkey 的值

求值器伪代码如下,这是一个函数,当 ast 节点为中缀表达式时,会递归调用自身两次,求出左右表达式的值

function eval(astNode){
    if (astNode is integerliteral){
        return astNode.integerValue
    } else if (astNode is booleanLiteral) {
        return astNode.booleanValue
    } else if (astNode is infixExpression) {
        leftEvaluated = eval(astNode.Left)
        rightEvaluated = eval(astNode.Right)
        if (astNode.Operator == "+") {
            return leftEvaluated + rightEvaluated
        } else if (ast.Operator == "-") {
            return leftEvaluated - rightEvaluated
        }
    }
}

返回值时什么类型,返回什么,取决于 Monkey 解释器将使用什么样的内部对象系统

3.4 表示对象

对象系统可以称为值系统或对象表示方法,重点是为 eval 函数返回的内容添加一个定义,需要一个系统来表示 AST 的值或表示在内存中对 AST 求值时生成的值

不同编程语言有不同内部表示,有的使用宿主语言的原生类型(整数、布尔值等)来表示所解释的语言的值,不进行任何封装;有些编程语言使用指针表示值或对象;有些则混合使用原生类型和指针

不同的原因有很多

  • 宿主语言不同: 比如 ruby 和 c 编写的解释器中,对字符串的实现就不同
  • 所解释的语言不同: 有的语言只需要原始数据类型,有些则需要列表、字典、数组等
  • 求值程序的执行速度和内存消耗的要求不同: 有的需要快速,所以不能使用臃肿的对象系统,如果编写自己的垃圾回收器则要考虑如何跟踪系统中的值

有很多种方法,了解它们的最佳方式,就是阅读源码(推荐 Wren 项目,有两种方式表示值,可以通过设置 WREN_NAN_TAGGING 来选择)

除了内部表示值,还需要考虑如何向用户公开这些值及其表示(提供什么样的”公共 API”).比如 java 提供了原始数据类型和引用类型,而 Ruby 的用户则无权访问原始数据类型,一切皆为对象,所有值都被封装到了内部表示中

3.4.1 对象系统基础

我们选择最简单的方法,当对源代码求值时,所有值都封装到符合 Object 接口的结构体中

// object/object.go
package object

type ObjectType string

type Object interface {
    Type() ObjectType
    Inspect() string
}

使用接口,则每种不同的值可以有不同的内部表示,现在有 3 种数据类型: 空值、布尔值、整数

3.4.2 整数

type Integer struct {
    Value int64
}

func (i *Integer) Inspect() string { return fmt.Sprintf("%d", i.Value) }

为了实现 Object 接口,需要 Type 方法,先定义 ObjectType,它们都是常量

type ObjectType string

const (
    INTEGER_OBJ = "INTEGER"
)

实现 Type 方法

func (i *Integer) Type() ObjectType { return INTEGER_OBJ }

3.4.3 布尔值

// object/object.go
const (
    INTEGER_OBJ = "INTEGER"
    BOOLEAN_OBJ = "BOOLEAN"
)

type Boolean struct {
    Value bool
}

func (b *Boolean) Inspect() string  { return fmt.Sprintf("%t", b.Value) }
func (b *Boolean) Type() ObjectType { return BOOLEAN_OBJ }

3.4.4 空值

托尼·霍尔在 ALGOL W 语言中引入了空引用，将其称为“价值十亿美元的错误”,不实现 null,可以让语言更安全,但是会监督对于 null 的警惕意识,所以这里依然实现

// object/object.go
const (
    INTEGER_OBJ = "INTEGER"
    BOOLEAN_OBJ = "BOOLEAN"
    NULL_OBJ    = "NULL"
)

type Null struct{}

func (n *Null) Inspect() string  { return "null" }
func (n *Null) Type() ObjectType { return NULL_OBJ }

3.5 求值表达式

每个 ast 节点都可以作为 Eval 函数的输入(因此可以在 AST 的任意部分求值时调用 Eval,而且可以递归使用),然后 eval 会返回一个 object.Object,每个节点求值的方式不同,由 Eval 决定

先实现自求值表达式,也就是处理字面量,字面量的值就是它自己(如 IntegerNode(5)->5)

3.5.1 整数字面量

// evaluate/evaluate.go
package evaluator

import (
    "go-monkey-compiler/ast"
    "go-monkey-compiler/object"
)

func Eval(node ast.Node) object.Object {
    switch node := node.(type) {
    case *ast.IntegerLiteral:
        return &object.Integer{Value: node.Value}
    }
    return nil
}

此时测试,Eval 返回的会是 nil,因为 Eval 没有遍历,而只是等待 ast.IntegerLiteral,我们需要让他每次都从树的顶部开始遍历,然后求值

// evaluate/evaluate.go
func evalStatements(stmts []ast.Statement) object.Object {
    var result object.Object

    for _, statement := range stmts {
        result = Eval(statement)
    }

    return result
}

func Eval(node ast.Node) object.Object {
    switch node := node.(type) {
    // 语句 -> 继续遍历
    // 根节点
    case *ast.Program:
        return evalStatements(node.Statements)
    // 表达式语句
    case *ast.ExpressionStatement:
        return Eval(node.Expression)
    // 表达式 -> 求值
    case *ast.IntegerLiteral:
        return &object.Integer{Value: node.Value}
    }
    return nil
}

测试

package evaluator

import (
    "go-monkey-compiler/lexer"
    "go-monkey-compiler/object"
    "go-monkey-compiler/parser"
    "testing"
)

func TestEvalIntegerExpression(t *testing.T) {
    ts := []struct {
        input    string
        expected int64
    }{
        {"5", 5},
        {"10", 10},
    }
    for _, tt := range ts {
        eval := testEval(tt.input)
        testIntegerObject(t, eval, tt.expected)
    }
}
func testEval(input string) object.Object {
    l := lexer.New(input)
    p := parser.New(l)
    pro := p.ParseProgram()
    return Eval(pro)
}
func testIntegerObject(t *testing.T, obj object.Object, expected int64) bool {
    res, ok := obj.(*object.Integer)
    if !ok {
        t.Errorf("obj is not int")
        return false
    }
    if res.Value != expected {
        t.Errorf("obj has wrong val`")
        return false
    }
    return true
}

3.5.2 完成 REPL

func Start(in io.Reader, out io.Writer) {
    scanner := bufio.NewScanner(in)
    io.WriteString(out, MALRED_LOGO)

    for {
        fmt.Fprintf(out, PROMPT)
        scanned := scanner.Scan()
        if !scanned {
            return
        }

        line := scanner.Text()
        l := lexer.New(line)
        p := parser.New(l)

        program := p.ParseProgram()
        if len(p.Errors()) != 0 {
            printParserErrors(out, p.Errors())
            continue
        }

        evaluated := evaluator.Eval(program)
        if evaluated != nil {
            io.WriteString(out, evaluated.Inspect())
            io.WriteString(out, "\n")
        }
    }
}

3.5.3 布尔字面量

func Eval(node ast.Node) object.Object {
    switch node := node.(type) {
    // 语句 -> 继续遍历
    // 根节点
    case *ast.Program:
        return evalStatements(node.Statements)
    // 表达式语句
    case *ast.ExpressionStatement:
        return Eval(node.Expression)
    // 表达式 -> 求值
    case *ast.IntegerLiteral:
        return &object.Integer{Value: node.Value}
    case *ast.Boolean:
        return &object.Boolean{Value: node.Value}
    }
    return nil
}

测试

func TestEvalBooleanExpression(t *testing.T) {
    ts := []struct {
        input    string
        expected bool
    }{
        {"true", true},
        {"false", false},
    }
    for _, tt := range ts {
        eval := testEval(tt.input)
        testBooleanObject(t, eval, tt.expected)
    }
}
func testBooleanObject(t *testing.T, obj object.Object, expected bool) bool {
    res, ok := obj.(*object.Boolean)
    if !ok {
        t.Errorf("obj is not boolean")
        return false
    }
    if res.Value != expected {
        t.Errorf("obj has wrong val")
        return false
    }
    return true
}

但是 true 和 false 每次都要创建一个新的对象,而布尔只有两种情况,所以可以将创建新对象,改为对 true 和 false 对象的引用

// evaluate/evaluate.go
var (
    TRUE  = &object.Boolean{Value: true}
    FALSE = &object.Boolean{Value: false}
)

// ...

func nativeBooleanObject(input bool) *object.Boolean {
    if input {
        return TRUE
    }
    return FALSE
}

func Eval(node ast.Node) object.Object {
    switch node := node.(type) {
    // 语句 -> 继续遍历
    // 根节点
    case *ast.Program:
        return evalStatements(node.Statements)
    // 表达式语句
    case *ast.ExpressionStatement:
        return Eval(node.Expression)
    // 表达式 -> 求值
    case *ast.IntegerLiteral:
        return &object.Integer{Value: node.Value}
    case *ast.Boolean:
        return nativeBooleanObject(node.Value)
    }
    return nil
}

3.5.4 空值

var (
    NULL  = &object.Null{}
    TRUE  = &object.Boolean{Value: true}
    FALSE = &object.Boolean{Value: false}
)

3.5.5 前缀表达式

!的求值

// !操作符求值
func evalBangOperatorExpression(right object.Object) object.Object {
    switch right {
    case TRUE:
        return FALSE
    case FALSE:
        return TRUE
    case NULL:
        return TRUE
    default:
        return FALSE
    }
}

// 解析前缀 ! -
func evalPrefixExpression(operator string, right object.Object) object.Object {
    switch operator {
    case "!":
        return evalBangOperatorExpression(right)
    default:
        return NULL
    }
}

func Eval(node ast.Node) object.Object {
    // ...
    case *ast.PrefixExpression:
        right := Eval(node.Right)
        return evalPrefixExpression(node.Operator, right)
    // ...
}

测试

func TestBangOperator(t *testing.T) {
    ts := []struct {
        input    string
        expected bool
    }{
        {"!true", false},
        {"!false", true},
        {"!5", false},
        {"!!true", true},
        {"!!false", false},
        {"!!5", true},
    }
    for _, tt := range ts {
        eval := testEval(tt.input)
        testBooleanObject(t, eval, tt.expected)
    }
}

-的求值

// -操作符求值(前缀)
func evalMinusPrefixOperatorExpression(right object.Object) object.Object {
    if right.Type() != object.INTEGER_OBJ {
        return NULL
    }

    value := right.(*object.Integer).Value
    return &object.Integer{Value: -value}
}

// 解析前缀 ! -
func evalPrefixExpression(operator string, right object.Object) object.Object {
    switch operator {
    case "!":
        return evalBangOperatorExpression(right)
    case "-":
        return evalMinusPrefixOperatorExpression(right)
    default:
        return NULL
    }
}

测试

func TestEvalIntegerExpression(t *testing.T) {
    ts := []struct {
        input    string
        expected int64
    }{
        {"5", 5},
        {"10", 10},
        {"-5",-5},
        {"-10", -10},
    }
    for _, tt := range ts {
        eval := testEval(tt.input)
        testIntegerObject(t, eval, tt.expected)
    }
}

3.5.6 中缀表达式

有 8 种中缀表达式,根据产生的值的类型分为 产生数值型(+ - * /) 和 产生布尔型(> < == !=)

先实现产生数值型的解析

// 解析两侧是数字的正则表达式(eg. 2*2)
func evalIntegerInfixExpression(operator string, left, right object.Object) object.Object {
    leftVal := left.(*object.Integer).Value
    rightVal := right.(*object.Integer).Value

    switch operator {
    case "+":
        return &object.Integer{Value: leftVal + rightVal}
    case "-":
        return &object.Integer{Value: leftVal - rightVal}
    case "*":
        return &object.Integer{Value: leftVal * rightVal}
    case "/":
        return &object.Integer{Value: leftVal / rightVal}
    default:
        return NULL
    }
}

// 解析中缀表达式
func evalInfixExpression(operator string, left, right object.Object) object.Object {
    switch {
    case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ:
        return evalIntegerInfixExpression(operator, left, right)
    default:
        return NULL
    }
}

func Eval(node ast.Node) object.Object {
    switch node := node.(type) {
    // ...
    case *ast.InfixExpression:
        left := Eval(node.Left)
        right := Eval(node.Right)
        return evalInfixExpression(node.Operator, left, right)
    }
    return nil
}

测试

func TestEvalIntegerExpression(t *testing.T) {
    ts := []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 ts {
        eval := testEval(tt.input)
        testIntegerObject(t, eval, tt.expected)
    }
}

产生布尔型

// 解析两侧是数字的正则表达式(eg. 2*2)
func evalIntegerInfixExpression(operator string, left, right object.Object) object.Object {
    leftVal := left.(*object.Integer).Value
    rightVal := right.(*object.Integer).Value

    switch operator {
    case "+":
        return &object.Integer{Value: leftVal + rightVal}
    case "-":
        return &object.Integer{Value: leftVal - rightVal}
    case "*":
        return &object.Integer{Value: leftVal * rightVal}
    case "/":
        return &object.Integer{Value: leftVal / rightVal}
    case "<":
        return &object.Boolean{Value: leftVal < rightVal}
    case ">":
        return &object.Boolean{Value: leftVal > rightVal}
    case "==":
        return &object.Boolean{Value: leftVal == rightVal}
    case "!=":
        return &object.Boolean{Value: leftVal != rightVal}
    default:
        return NULL
    }
}

测试

func TestEvalBooleanExpression(t *testing.T) {
    ts := []struct {
        input    string
        expected bool
    }{
        {"true", true},
        {"false", false},
        {"1 < 2", true},
        {"1 > 2", false},
        {"1 < 1", false},
        {"1 > 1", false},
        {"1 == 1", true},
        {"1 != 1", false},
        {"1 == 2", false},
        {"1 != 2", true},
    }
    for _, tt := range ts {
        eval := testEval(tt.input)
        testBooleanObject(t, eval, tt.expected)
    }
}

现在只能解析两侧为整型的中缀表达式,现在添加解析两侧为布尔的中缀表达式

// 解析中缀表达式
func evalInfixExpression(operator string, left, right object.Object) object.Object {
    switch {
    case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ:
        return evalIntegerInfixExpression(operator, left, right)
    // 这里可以直接对比是因为布尔型都是复用true和false两个对象的指针(地址),可以直接比对地址来看是否相等
    case operator == "==":
        return nativeBooleanObject(left == right)
    case operator == "!=":
        return nativeBooleanObject(left != right)
    default:
        return NULL
    }
}

这里可以直接对比是因为布尔型都是复用 true 和 false 两个对象的指针(地址),可以直接比对地址来看是否相等,如果是整型则不能,因为每个整型都是创建新的对象

3.6 条件语句

唯一难点在于: 根据条件决定对哪部分进行求值

如何判真/成立?条件表达式的结果必须是 true 还是真值(比如非空和非 false)

monkey 的策略是,不一定必须 true,非空和非 false 也行

// 解析中缀表达式
func evalInfixExpression(operator string, left, right object.Object) object.Object {
    switch {
    case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ:
        return evalIntegerInfixExpression(operator, left, right)
    // 这里可以直接对比是因为布尔型都是复用true和false两个对象的指针(地址),可以直接比对地址来看是否相等
    case operator == "==":
        return nativeBooleanObject(left == right)
    case operator == "!=":
        return nativeBooleanObject(left != right)
    default:
        return NULL
    }
}

// if判真策略(真值[true,!false,!null]为成立)
func isTruthy(obj object.Object) bool {
    switch obj {
    case NULL:
        return false
    case TRUE:
        return true
    case FALSE:
        return false
    default:
        return true
    }
}

// 解析If表达式
func evalIfExpression(ie *ast.IfExpression) object.Object {
    condition := Eval(ie.Condition)

    if isTruthy(condition) {
        return Eval(ie.Consequence)
    } else if ie.Alternative != nil {
        return Eval(ie.Alternative)
    } else {
        return NULL
    }
}

func Eval(node ast.Node) object.Object {
    switch node := node.(type) {
    // 语句 -> 继续遍历
    // 根节点
    case *ast.Program:
        return evalStatements(node.Statements)
    // 块语句
    case *ast.BlockStatement:
        return evalStatements(node.Statements)
    // IF语句
    case *ast.IfExpression:
        return evalIfExpression(node)
    // 表达式语句
    case *ast.ExpressionStatement:
        return Eval(node.Expression)
    // 表达式 -> 求值
    case *ast.IntegerLiteral:
        return &object.Integer{Value: node.Value}
    case *ast.Boolean:
        return nativeBooleanObject(node.Value)
    case *ast.PrefixExpression:
        // 如果一直是!或-,就会一直Eval,直到遇到其他类型,多次执行!或-
        right := Eval(node.Right)
        return evalPrefixExpression(node.Operator, right)
    case *ast.InfixExpression:
        left := Eval(node.Left)
        right := Eval(node.Right)
        return evalInfixExpression(node.Operator, left, right)
    }
    return nil
}

测试

func testNullObject(t *testing.T, obj object.Object) bool {
    if obj != NULL {
        t.Errorf("obj is not null. got=%T (%+v)", obj, obj)
        return false
    }
    return true
}
func TestIfElseExpression(t *testing.T) {
    ts := []struct {
        input    string
        expected interface{}
    }{
        {"if (true) { 10 }", 10},
        {"if (false) {10}", nil},
        {"if (1){10}", 10},
        {"if (1<2){10}", 10},
        {"if (1>2){10}", nil},
        {"if (1>2){10} else {20}", 20},
        {"if (1<2){10} else {20}", 10},
    }
    for _, tt := range ts {
        eval := testEval(tt.input)
        integer, ok := tt.expected.(int)
        if ok {
            testIntegerObject(t, eval, int64(integer))
        } else {
            testNullObject(t, eval)
        }
    }
}

3.7 return 语句

为了实现 return,需要求值器传递一个”返回值”,每当遇到 return,就将要返回的值封装到一个对象,根据该返回值决定是否继续求值

const (
    INTEGER_OBJ      = "INTEGER"
    BOOLEAN_OBJ      = "BOOLEAN"
    NULL_OBJ         = "NULL"
    RETURN_VALUE_OBJ = "RETURN_VALUE"
)

type ReturnValue struct {
    Value Object
}

func (rv *ReturnValue) Type() ObjectType { return RETURN_VALUE_OBJ }
func (rv *ReturnValue) Inspect() string  { return rv.Value.Inspect() }

return 的重点在于使用时间和使用方式

// 解析语句
func evalStatements(stmts []ast.Statement) object.Object {
    var result object.Object

    for _, statement := range stmts {
        result = Eval(statement)

        // 如果是return语句的结果,就返回return的值
        if returnValue, ok := result.(*object.ReturnValue); ok {
            return returnValue.Value
        }
    }

    return result
}
func Eval(node ast.Node) object.Object {
    switch node := node.(type) {
    // 语句 -> 继续遍历
    // ...
    // Return语句
    case *ast.ReturnStatement:
        // 对返回值进行求值
        val := Eval(node.ReturnValue)
        return &object.ReturnValue{Value: val}
    // ...
    }
}

在 evalProgramStatements 和 evalBlockStatements 中,会使用 evalStatements 对语句进行求值,如果遇到 object.ReturnValue,则会解封 ReturnValue 并返回封装的值,然后不再继续求值,这很重要

测试

func TestReturnStatements(t *testing.T) {
    ts := []struct {
        input    string
        expected int64
    }{
        {"return 10;", 10},
        {"return 10; 9;", 10},
        {"return 2*5; 9;", 10},
        {"9; return 2*5; 9;", 10},
    }
    for _, tt := range ts {
        eval := testEval(tt.input)
        testIntegerObject(t, eval, tt.expected)
    }
}

但是,如果出现 if () {if(){return } return },这种需要跟踪很长的(嵌套),则有可能出问题,需要进一步跟踪,防止最外层直接 return

将 evalStatement 改名为 evalProgram

// 解析program
func evalProgram(program *ast.Program, env *object.Environment) object.Object {
    var result object.Object

    for _, statement := range program.Statements {
        result = Eval(statement, env)

        switch result := result.(type) {
        case *object.ReturnValue:
            return result.Value
        case *object.Error:
            return result
        }
    }

    return result
}

func Eval(node ast.Node) object.Object {
    switch node := node.(type) {
    // 语句 -> 继续遍历
    // 根节点
    case *ast.Program:
        return evalProgram(node)
    // ...
    }
}

块语句改为使用 evalBlockStatement 求值

// 对块语句进行求值
func evalBlockStatement(block *ast.BlockStatement) object.Object {
    var result object.Object

    for _, statement := range block.Statements {
        result = Eval(statement)

        // 如果是return,则返回object.ReturnValue
        if result != nil && result.Type() == object.RETURN_VALUE_OBJ {
            return result
        }
    }
    return result
}

func Eval(node ast.Node) object.Object {
    switch node := node.(type) {
    // 语句 -> 继续遍历
    // 根节点
    case *ast.Program:
        return evalProgram(node.Statements)
    // 块语句
    case *ast.BlockStatement:
        return evalBlockStatement(node)
    // ...
    }
    return nil
}

这里(块语句内)不解包返回值(如果直接解包,会返回字面量,从而会继续执行,直到外层的 return 返回了 ReturnValue),而是检查每个求值结果的 Type,如果是 object.RETURN_VALUE_OBJ,就返回给*object.ReturnValue,无需解包其 value,这样如果有外部块语句,就会停止执行,并冒泡至 evalProgram,最后在这里解包

3.8 错误处理

真正的错误处理不是指用户定义的异常,而是指处理程序内部的错误处理流程.用于处理错误的运算符、不支持的操作以及执行期间可能发生的其他用户错误或内部错误

错误处理和 return 的实现基本相同,因为它们都会终止对一系列语句的求值

定义错误对象

const (
    INTEGER_OBJ      = "INTEGER"
    BOOLEAN_OBJ      = "BOOLEAN"
    NULL_OBJ         = "NULL"
    RETURN_VALUE_OBJ = "RETURN_VALUE"
    ERROR_OBJ        = "ERROR"
)

type Error struct {
    Message string
}

func (e *Error) Type() ObjectType { return ERROR_OBJ }
func (e *Error) Inspect() string  { return "ERROR: " + e.Message }

生产环境的解释器应该提供堆栈跟踪信息,并添加错误发生位置的行号和列号.但是这需要在词法分析器中添加,这里没有,所以 Error 对象只附带一条报错信息

辅助函数,帮助创建 Error

func newError(format string, args ...interface{}) *object.Error {
    return &object.Error{Message: fmt.Sprintf(format, args...)}
}

修改之前需要异常处理的地方

// evaluate/evaluate.go
// -操作符求值(前缀)
func evalMinusPrefixOperatorExpression(right object.Object) object.Object {
    if right.Type() != object.INTEGER_OBJ {
        return newError("unknown operator: -%s", right.Type())
    }

    value := right.(*object.Integer).Value
    return &object.Integer{Value: -value}
}

// 解析前缀 ! -
func evalPrefixExpression(operator string, right object.Object) object.Object {
    switch operator {
    case "!":
        return evalBangOperatorExpression(right)
    case "-":
        return evalMinusPrefixOperatorExpression(right)
    default:
        return newError("unknown operator %s%s"+operator, right.Type())
    }
}

// 解析两侧是数字的正则表达式(eg. 2*2)
func evalIntegerInfixExpression(operator string, left, right object.Object) object.Object {
    leftVal := left.(*object.Integer).Value
    rightVal := right.(*object.Integer).Value

    switch operator {
    case "+":
        return &object.Integer{Value: leftVal + rightVal}
    case "-":
        return &object.Integer{Value: leftVal - rightVal}
    case "*":
        return &object.Integer{Value: leftVal * rightVal}
    case "/":
        return &object.Integer{Value: leftVal / rightVal}
    case "<":
        return nativeBooleanObject(leftVal < rightVal)
    case ">":
        return nativeBooleanObject(leftVal > rightVal)
    case "==":
        return nativeBooleanObject(leftVal == rightVal)
    case "!=":
        return nativeBooleanObject(leftVal != rightVal)
    default:
        return newError("unknown operator: %s %s %s", left.Type(), operator, right.Type())
    }
}

// 解析中缀表达式
func evalInfixExpression(operator string, left, right object.Object) object.Object {
    switch {
    case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ:
        return evalIntegerInfixExpression(operator, left, right)
    // 这里可以直接对比是因为布尔型都是复用true和false两个对象的指针(地址),可以直接比对地址来看是否相等
    case operator == "==":
        return nativeBooleanObject(left == right)
    case operator == "!=":
        return nativeBooleanObject(left != right)
    case left.Type() != right.Type():
        return newError("type mismatch: %s %s %s", left.Type(), operator, right.Type())
    default:
        return newError("unknown operator %s %s %s", left.Type(), operator, right.Type())
    }
}

func newError(format string, args ...interface{}) *object.Error {
    return &object.Error{Message: fmt.Sprintf(format, args...)}
}

// 解析program
func evalProgram(stmts []ast.Statement) object.Object {
    var result object.Object

    for _, statement := range stmts {
        result = Eval(statement)

        switch result := result.(type) {
        case *object.ReturnValue:
            return result.Value
        case *object.Error:
            return result
        }
    }

    return result
}

// 对块语句进行求值
func evalBlockStatement(block *ast.BlockStatement) object.Object {
    var result object.Object

    for _, statement := range block.Statements {
        result = Eval(statement)

        if result != nil {
            rt := result.Type()
            if rt == object.RETURN_VALUE_OBJ || rt == object.ERROR_OBJ {
                return result
            }
        }
    }
    return result
}

调用 Eval 时检查错误信息,以免错误导出传递,导致在发生错误很远的地方报错

// 解析If表达式
func evalIfExpression(ie *ast.IfExpression) object.Object {
    condition := Eval(ie.Condition)
    if isError(condition) {
        return condition
    }

    // ...
}
func Eval(node ast.Node) object.Object {
    switch node := node.(type) {
    // 语句 -> 继续遍历
    // 根节点
    case *ast.Program:
        return evalProgram(node.Statements)
    // 块语句
    case *ast.BlockStatement:
        return evalBlockStatement(node)
    // Return语句
    case *ast.ReturnStatement:
        // 对返回值进行求值
        val := Eval(node.ReturnValue)
        // 判断该中断是不是Error引发的
        if isError(val) {
            return val
        }
        return &object.ReturnValue{Value: val}
    // ...
    case *ast.PrefixExpression:
        // 如果一直是!或-,就会一直Eval,直到遇到其他类型,多次执行!或-
        right := Eval(node.Right)
        // 判断该中断是不是Error引发的
        if isError(right) {
            return right
        }
        return evalPrefixExpression(node.Operator, right)
    case *ast.InfixExpression:
        left := Eval(node.Left)
        // 判断该中断是不是Error引发的
        if isError(left) {
            return left
        }
        right := Eval(node.Right)
        // 判断该中断是不是Error引发的
        if isError(right) {
            return right
        }
        return evalInfixExpression(node.Operator, left, right)
    }
    return nil
}
func isError(obj object.Object) bool {
    if obj != nil {
        return obj.Type() == object.ERROR_OBJ
    }
    return false
}

3.9 绑定与环境

添加对 let 语句的支持,为解释器添加绑定功能.除了 let,还需要支持对标识符求值

let x = 25; 不仅需要对 let 求值,而且需要保证 let 之后,后续对标识符求值也是 25

func Eval(node ast.Node) object.Object {
    switch node := node.(type) {
    // 语句 -> 继续遍历
    // 根节点
    case *ast.Program:
        return evalProgram(node.Statements)
    // 块语句
    case *ast.BlockStatement:
        return evalBlockStatement(node)
    // Let语句
    case *ast.LetStatement:
        val := Eval(node.Value)
        if isError(val) {
            return val
        }
        // ?
    // ...
    }
    return nil
}

接下来要做什么?就是要跟踪 let 产生的值,val 需要和 node.Name.Value 绑定

这里要用到’环境’,它其实是一个将字符串和对象关联的哈希映射,可以在环境中用关联的名称来跟踪值

// object/environment.go
package object

type Environment struct {
    store map[string]Object
}

func NewEnvironment() *Environment {
    s := make(map[string]Object)
    return &Environment{store: s}
}

func (e *Environment) Get(name string) (Object, bool) {
    obj, ok := e.store[name]
    return obj, ok
}

func (e *Environment) Set(name string, value Object) Object {
    e.store[name] = value
    return value
}

这里不直接使用 map,而是选择封装,后续会有用处

现在,将 env 通过参数传递给 eval 使用

每次调用 Eval 应该得到新环境

// evaluate/evaluate_test.go
func testEval(input string) object.Object {
    l := lexer.New(input)
    p := parser.New(l)
    pro := p.ParseProgram()
    env := object.NewEnvironment()
    return Eval(pro, env)
}

跟踪求值

func evalIdentifier(node *ast.Identifier, env *object.Environment) object.Object {
    val, ok := env.Get(node.Value)
    if !ok {
        return newError("identifier not found: " + node.Value)
    }
    return val
}

func Eval(node ast.Node, env *object.Environment) object.Object {
    switch node := node.(type) {
    // 语句 -> 继续遍历
    // 根节点
    case *ast.Program:
        return evalProgram(node.Statements)
    // 块语句
    case *ast.BlockStatement:
        return evalBlockStatement(node)
    // Let语句
    case *ast.LetStatement:
        val := Eval(node.Value, env)
        if isError(val) {
            return val
        }
        // 关联标识符和值
        env.Set(node.Name.Value, val)
    // 标识符
    case *ast.Identifier:
        return evalIdentifier(node, env)
    // ...
    }
    return nil
}

测试

func TestErrorHandling (t *testing.T ) {
    ts := []struct {
        input           string
        expectedMessage string
    } {
        // ...
        {"foobar;", "identifier not found: foobar"},
    }
    for _, tt := range ts {
        eval := testEval(tt.input)
        errobj, ok := eval.(*object.Error)
        if !ok {
            t.Errorf("no error obj returned. got=%T(%+v)", eval, eval)
            return
        }
        if errobj.Message != tt.expectedMessage {
            t.Errorf("wrong error msg: expected=%q, got=%q", tt.expectedMessage, errobj.Message)
            return
        }
    }
}
func TestLetStatement(t *testing.T) {
    ts := []struct {
        input    string
        expected int64
    }{
        {"let a = 5; a;", 5},
        {"let a = 5 * 5; a;", 25},
        {"let a = 5; let b = a; b;", 5},
        {"let a=5;let b = a; let c = a + b + 5;c;", 15},
    }
    for _, tt := range ts {
        testIntegerObject(t, testEval(tt.input), tt.expected)
    }
}

3.10 函数和函数调用

将实现传递函数、高阶函数、闭包等功能

需要完成两件事,1.对象系统中定义函数的内部表示;2.在 Eval 中添加对函数调用的支持

1.函数的内部表示;之所以需要内部表示,是因为函数和其他值一样可以绑定到变量、用于表达式、传递给其他函数、从其他函数中返回一个函数;函数也需要用某种形式来表示,才能传递、赋值和返回函数

type FunctionLiteral struct {
    Token      token.Token // 'fn'词法单元
    Parameters []*Identifier
    Body       *BlockStatement
}

看一下 ast 中对函数的定义,函数对象不需要 token,但是需要 Parameters 和 Body,因为没有函数体就不能对函数求值,没有参数就无法对函数体求值,除了参数和函数体,还需要 env 字段

// object/object.go
type Function struct {
    Parameters []*ast.Identifier
    Body       *ast.BlockStatement
    Env        *Environment
}

func (f *Function) Type() ObjectType { return FUNCTION_OBJ }
func (f *Function) Inspect() string {
    var out bytes.Buffer

    params := []string{}
    for _, p := range f.Parameters {
        params = append(params, p.String())
    }

    out.WriteString("fn")
    out.WriteString("(")
    out.WriteString(strings.Join(params, ", "))
    out.WriteString(") {\n}")
    out.WriteString(f.Body.String())
    out.WriteString("\n}")

    return out.String()
}

因为给函数对象一个 env 字段,所以函数有了自己独立的内部环境,可以形成闭包

func Eval(node ast.Node, env *object.Environment) object.Object {
    switch node := node.(type) {
    // 语句 -> 继续遍历
    // 根节点
    case *ast.Program:
        return evalProgram(node.Statements, env)
    // 块语句
    case *ast.BlockStatement:
        return evalBlockStatement(node, env)
    // Let语句
    case *ast.LetStatement:
        val := Eval(node.Value, env)
        if isError(val) {
            return val
        }
        // 关联标识符和值
        env.Set(node.Name.Value, val)
    // 标识符
    case *ast.Identifier:
        return evalIdentifier(node, env)
    // 函数语句
    case *ast.FunctionLiteral:
        params := node.Parameters
        body := node.Body
        return &object.Function{Parameters: params, Body: body, Env: env}
    // ...
    }
    return nil
}

测试

func TestFunctionObject(t *testing.T) {
    input := "fn(x) { x + 2;};"
    eval := testEval(input)
    fn, ok := eval.(*object.Function)
    if !ok {
        t.Fatalf("object is not function")
        return
    }
    if len(fn.Parameters) != 1 {
        t.Fatalf("function has wrong parameters")
        return
    }
    if fn.Parameters[0].String() != "x" {
        t.Fatalf("parameters is not 'x'")
        return
    }
    expectedBody := "(x + 2)"
    if fn.Body.String() != expectedBody {
        t.Fatalf("body is not '(x + 2)'")
        return
    }
}

添加对函数的求值

func Eval(node ast.Node, env *object.Environment) object.Object {
    switch node := node.(type) {
    // ...
    // 调用函数
    case *ast.CallExpression:
        function := Eval(node.Function, env)
        if isError(function) {
            return function
        }
    // ...
    }
    return nil
}

获取调用的函数,不管是标识符还是定义函数,都会返回函数对象;为了使用函数对象,需要先对调用表达式的参数进行求值(add(4+1,1+4)->add(5,5))

func evalExpressions(exps []ast.Expression, env *object.Environment) []object.Object {
    var result []object.Object

    for _, e := range exps {
        evaluated := Eval(e, env)
        if isError(evaluated) {
            return []object.Object{evaluated}
        }
        result = append(result, evaluated)
    }

    return result
}

func Eval(node ast.Node, env *object.Environment) object.Object {
    switch node := node.(type) {
    // ...
    // 调用函数
    case *ast.CallExpression:
        function := Eval(node.Function, env)
        if isError(function) {
            return function
        }
        args := evalExpressions(node.Arguments, env)
        if len(args) == 1 && isError(args[0]) {
            return args[0]
        }
    // ...
    }
    return nil
}

调用函数,需要对函数体求值,但是不能直接使用块语句求值,因为函数体包含参数,用块语句的方法解析会有未知参数错误

函数参数不能直接添加到当前环境,而是应该保留已有的绑定,同时添加新的绑定,这叫”拓展已有的环境”.这样需要创建新的环境实例,还有一个指向待拓展环境的指针

当新环境 Get 时,如果新环境没有,则会往上一层环境去找,相当于拓展了环境边界

// object/environment.go
package object

type Environment struct {
    store map[string]Object
    // 外层包裹自己的环境
    outer *Environment
}

func NewEnvironment() *Environment {
    s := make(map[string]Object)
    return &Environment{store: s, outer: nil}
}

// 创建新环境,父级为outer
func NewEnclosedEnvironment(outer *Environment) *Environment {
    env := NewEnvironment()
    env.outer = outer
    return env
}

func (e *Environment) Get(name string) (Object, bool) {
    obj, ok := e.store[name]
    if !ok && e.outer != nil {
        obj, ok = e.outer.Get(name)
    }
    return obj, ok
}

func (e *Environment) Set(name string, value Object) Object {
    e.store[name] = value
    return value
}

现在的环境分为了内部和外部,相当于划分了变量的作用域

现在,如果函数调用时有新的实参绑定,则创建新环境(使用函数自带的环境),然后将绑定添加到该环境

// 解包函数返回值(如果不接包,会冒泡,然后停止后续的语句求值)
func unwrapReturnValue(obj object.Object) object.Object {
    if returnValue, ok := obj.(*object.ReturnValue); ok {
        return returnValue.Value
    }
    return obj
}

// 拓展环境
func extendFunctionEnv(fn *object.Function, args []object.Object) *object.Environment {
    env := object.NewEnclosedEnvironment(fn.Env)

    for paramIdx, param := range fn.Parameters {
        env.Set(param.Value, args[paramIdx])
    }

    return env
}

// 函数体求值
func applyFunction(fn object.Object, args []object.Object) object.Object {
    function, ok := fn.(*object.Function)
    if !ok {
        return newError("not a function: %s", fn.Type())
    }

    extendedEnv := extendFunctionEnv(function, args)
    evaluated := Eval(function.Body, extendedEnv)
    return unwrapReturnValue(evaluated)
}

func Eval(node ast.Node, env *object.Environment) object.Object {
    switch node := node.(type) {
    // ...
    // 调用函数
    case *ast.CallExpression:
        function := Eval(node.Function, env)
        if isError(function) {
            return function
        }
        args := evalExpressions(node.Arguments, env)
        if len(args) == 1 && isError(args[0]) {
            return args[0]
        }

        return applyFunction(function, args)
    // ...
    }
    return nil
}

可以看出,我们现在可以使用闭包了,闭包是指函数隔离出其中定义的环境,并会随时附带.每当调用函数时便可以访问其所附带的环境

这里的 newAdder 是高阶函数,高阶函数是指返回其他函数或将其他函数作为参数的函数

当我们调用 addTwo,它求值不是在当前环境求值,而是在函数环境中求值,这是通过拓展定义函数时的环境并将其传递给 Eval()实现的

此时,函数也可作为参数


3.11 如何处理垃圾

一段代码:

let counter = fn(x){
    if (x>100) {
        return true;
    }else{
        let foo = 9999;
        counter(x + 1);
    }
};

如果跟踪 integer 对象,会发现这段代码产生了约 400 个 integer 对象,但是我们这里的 foo(以及 x+1 的求值)并没有使用,却占用了大量空间

我们的对象存放在内存中,如果创建过多对象,会占用非常多的内存

我们直接借用了 Go 的垃圾回收器,不需要自己写

GC 涉及很多算法和实现,而且 Go 默认不支持手动管理内存,所以这里不实现自己的 GC

4. 拓展解释器

4.1 数据类型和函数

现在只能使用整数和布尔,我们需要拓展

拓展性的数据类型的过程: 添加新的词法单元类型、修改词法分析器、拓展语法分析器、向求值器和对象系统添加新的数据类型

有很多数据类型在 Go 有实现,所以无需我们从零开始实现,只需要让这些数据结构在我们的语言中可用就行

4.2 字符串

字符串是一个字符序列.是头等值,可用绑定给标识符,可用在函数调用中作为参数,可用由函数返回.还要能支持中缀运算符+,进行字符串拼接

4.2.1 在词法分析器中支持字符串

字符串字面量结构: “<字符序列>”

我们给每个字符串生产 1 个词法单元,当然,某些特定情况或语法分析器中,它们将字符串分析成引号包裹的有些 token.IDENT 词法单元.

// token/token.go
const (
    // ...

    STRING = "STRING" // "hello"

    // ...
)

func (l *Lexer) readString() string {
    position := l.position + 1
    for {
        l.readChar()
        if l.ch == '"' || l.ch == 0 {
            break
        }
    }
    return l.input[position:l.position]
}

// 根据当前的ch创建词法单元
func (l *Lexer) NextToken() token.Token {
    var tok token.Token

    // 跳过空格
    l.skipWhitespace()

    switch l.ch {
    case '"':
        tok.Type = token.STRING
        tok.Literal = l.readString()
    // ...
    }

    l.readChar()
    return tok
}

测试

// lexer/lexer_test.go
func TestNextToken(t *testing.T) {
    input := `
    // ...
    "foobar0"
    "foo bar"
    `

    tests := []struct {
        expectedType    token.TokenType
        expectedLiteral string
    }{
        // ...
        {token.STRING, "foobar0"},
        {token.STRING, "foo bar"},
        {token.EOF, ""},
    }

    l := New(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)
        }
    }
}

4.2.2 字符串语法分析

// ast/ast.go
type StringLiteral struct {
    Token token.Token
    Value string
}

func (sl *StringLiteral) expressionNode()      {}
func (sl *StringLiteral) TokenLiteral() string { return sl.Token.Literal }
func (sl *StringLiteral) String() string       { return sl.Token.Literal }

注册前缀解析函数进行 string 的解析

func (p *Parser) parseStringLiteral() ast.Expression {
    return &ast.StringLiteral{Token: p.curToken, Value: p.curToken.Literal}
}
func New(l *lexer.Lexer) *Parser {
    p := &Parser{l: l, errors: []string{}}
    // ...
    p.registerPrefix(token.STRING, p.parseStringLiteral)
    // ...
    return p
}

测试

// parser/parser_test.go
func TestStringLiteralExpression(t *testing.T) {
    input := `"hello world"`
    l := lexer.New(input)
    p := New(l)
    program := p.ParseProgram()
    checkParserErrors(t, p)
    stmt := program.Statements[0].(*ast.ExpressionStatement)
    literal, ok := stmt.Expression.(*ast.StringLiteral)
    if !ok {
        t.Fatalf("exp not *ast.StringLiteral. got=%T", stmt.Expression)
    }
    if literal.Value != "hello world" {
        t.Errorf("literal.value not %q. got=%q", "hello world", literal.Value)
    }
}

4.2.3 字符串求值

// object/object.go
type String struct {
    Value string
}

func (s *String) Type() ObjectType { return STRING_OBJ }
func (s *String) Inspect() string {
    return s.Value
}

func Eval(node ast.Node, env *object.Environment) object.Object {
    switch node := node.(type) {
    // ...
    case *ast.StringLiteral:
        return &object.String{Value: node.Value}
    // ...
    }
    return nil
}

测试

func TestStringLiteral(t *testing.T) {
    input := `"hello world"`
    eval := testEval(input)
    str, ok := eval.(*object.String)
    if !ok {
        t.Fatalf("object is not string. got=%T(%+v)", eval, eval)
    }
    if str.Value != "hello world" {
        t.Errorf("string has wrong value. got=%q", str.Value)
    }
}

4.2.4 字符串连接

// evaluator/evaluator.go
// 解析字符串中缀操作
func evalStringInfixExpression(operator string, left, right object.Object) object.Object {
    if operator != "+" {
        return newError("unknown operator: %s %s %s", left.Type(), operator, right.Type())
    }
    leftVal := left.(*object.String).Value
    rightVal := right.(*object.String).Value
    return &object.String{Value: leftVal + rightVal}
}

// 解析中缀表达式
func evalInfixExpression(operator string, left, right object.Object) object.Object {
    switch {
    case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ:
        return evalIntegerInfixExpression(operator, left, right)
    // 这里可以直接对比是因为布尔型都是复用true和false两个对象的指针(地址),可以直接比对地址来看是否相等
    case operator == "==":
        return nativeBooleanObject(left == right)
    case operator == "!=":
        return nativeBooleanObject(left != right)
    case left.Type() == object.STRING_OBJ && right.Type() == object.STRING_OBJ:
        return evalStringInfixExpression(operator, left, right)
    case left.Type() != right.Type():
        return newError("type mismatch: %s %s %s", left.Type(), operator, right.Type())
    default:
        return newError("unknown operator: %s %s %s", left.Type(), operator, right.Type())
    }
}

测试

func TestErrorHandling(t *testing.T) {
    ts := []struct {
        input           string
        expectedMessage string
    }{
        //...
        {`"hello" - "world`, "unknown operator: STRING - STRING"},
    }
    for _, tt := range ts {
        eval := testEval(tt.input)
        errobj, ok := eval.(*object.Error)
        if !ok {
            t.Errorf("no error obj returned. got=%T(%+v)", eval, eval)
            return
        }
        if errobj.Message != tt.expectedMessage {
            t.Errorf("wrong error msg: expected=%q, got=%q", tt.expectedMessage, errobj.Message)
            return
        }
    }
}
func TestStringConcatenation(t *testing.T) {
    input := `"hello" +" " +"world"`
    eval := testEval(input)
    str, ok := eval.(*object.String)
    if !ok {
        t.Fatalf("object is not String. got=%T(%+v)", eval, eval)
    }
    if str.Value != "hello world" {
        t.Errorf("string has wrong value. got=%q", str.Value)
    }
}

4.3 内置函数

内置函数不是有用户定义,也不是由该语言编写的,而是直接内置于解释器和语言本身的函数,向用户提供语言本身不具备的功能

内置函数的定义必须要接收 0~多个 Object,然后返回一个 Object

// 对象类型常量
const (
    // ...
    BUILTIN_OBJ      = "BUILTIN"
)
type BuiltinFunction func(args ...Object) Object
type Builtin struct {
    Fn BuiltinFunction
}

func (b *Builtin) Type() ObjectType { return BOOLEAN_OBJ }
func (b *Builtin) Inspect() string  { return "builtin function" }

len

该内置函数的作用是返回字符串中的字符数目

要让内置函数可以被识别,需要将它们添加到顶层的 env 中,然后传递给 eval

// evaluator/builtins.go
package evaluator

import (
    "malang/object"
)

var builtins = map[string]*object.Builtin{
    "len": &object.Builtin{
        Fn: func(args ...object.Object) object.Object {
            return NULL
        },
    },
}

为了使用该环境,需要修改 evalIdentifier 函数.如果当前环境没有该函数,就在内置函数的环境中查找

// 对标识符求值
func evalIdentifier(node *ast.Identifier, env *object.Environment) object.Object {
    if val, ok := env.Get(node.Value); ok {
        return val
    }
    if builtin, ok := builtins[node.Value]; ok {
        return builtin
    }
    return newError("identifier not found: " + node.Value)
}

为了能够调用,需要让 applyFunction 能处理*object.Builtin 和 object.BuiltinFunction

func applyFunction(fn object.Object, args []object.Object) object.Object {
    switch fn := fn.(type) {
    case *object.Function:
        extendedEnv := extendFunctionEnv(fn, args)
        evaluated := Eval(fn.Body, extendedEnv)
        return unwrapReturnValue(evaluated)
    case *object.Builtin:
        return fn.Fn(args...)
    default:
        return newError("not a function: %s", fn.Type())
    }
}

完善 len 函数

// evaluator/builtins.go
var builtins = map[string]*object.Builtin{
    "len": &object.Builtin{
        Fn: func(args ...object.Object) object.Object {
            if len(args) != 1 {
                return newError("wrong number of arguments. got=%d, want=1", len(args))
            }
            switch arg := args[0].(type) {
            case *object.String:
                return &object.Integer{Value: int64(len(arg.Value))}
            default:
                return newError("argument to `len` not supported. got %s", args[0].Type())
            }
        },
    },
}

测试

func TestBuiltinFunctions(t *testing.T) {
    ts := []struct {
        input    string
        expected interface{}
    }{
        {`len("")`, 0},
        {`len("four")`, 4},
        {`len("hello world")`, 11},
        {`len(1)`, "argument to `len` not supported. got INTEGER"},
        {`len("one","two")`, "wrong number of arguments. got=2, want=1"},
    }
    for _, tt := range ts {
        eval := testEval(tt.input)
        switch expected := tt.expected.(type) {
        case int:
            testIntegerObject(t, eval, int64(expected))
        case string:
            errobj, ok := eval.(*object.Error)
            if !ok {
                t.Errorf("obj is not error.")
                continue
            }
            if errobj.Message != expected {
                t.Errorf("wrong error message.")
            }
        }
    }
}

4.4 数组

在 Monkey 中,数组是含有多个元素的有序列表,其中元素类型可以不同.数组中每个元素可以单独访问,数组用字面量形式构建,以逗号分割列表中的元素,并用方括号括起来

用索引访问数组涉及新的运算符: 索引运算符 array[index]

还要让 len 支持数组,然后添加一些用于数组的内置函数

4.4.1 在词法分析器中支持数组

需要添加对[]的支持

1.定义新的词法单元

const (
    // ...
    LBRACKET = "["
    RBRACKET = "]"
    // ...
)

2.拓展语法分析器的测试套件

func TestNextToken(t *testing.T) {
    input :=
        `
    let five = 5;
    let ten = 10;

    let add = fn(x, y) {
    x + y;
    };

    let result = add(five, ten);
    !-/*5;
    5 < 10 > 5;

    if (5 < 10) {
        return true;
    } else {
        return false;
    }

    10 == 10;
    10 != 9;

    "foobar0"
    "\nfoo bar"
    [1,2];
    `

    tests := []struct {
        expectedType    token.TokenType
        expectedLiteral string
    }{
        // ...
        {token.LBRACKET, "["},
        {token.INT, "1"},
        {token.COMMA, ","},
        {token.INT, "2"},
        {token.RBRACKET, "]"},
        {token.SEMICOLON, ";"},
        {token.EOF, ""},
    }

    // ...
}

3.拓展 NextToken

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

    // 跳过空格
    l.skipWhitespace()

    switch l.ch {
    // ...
    case '[':
        tok = newToken(token.LBRACKET, l.ch)
    case ']':
        tok = newToken(token.RBRACKET, l.ch)
    // ...
    }

    l.readChar()
    return tok
}

4.4.2 数组字面量语法分析

定义数组字面量的 AST 节点

type ArrayLiteral struct {
    Token    token.Token // [词法单元
    Elements []Expression
}

func (al *ArrayLiteral) expressionNode()      {}
func (al *ArrayLiteral) TokenLiteral() string { return al.Token.Literal }
func (al *ArrayLiteral) String() string {
    var out bytes.Buffer

    elements := []string{}
    for _, el := range al.Elements {
        elements = append(elements, el.String())
    }

    out.WriteString("[")
    out.WriteString(strings.Join(elements, ", "))
    out.WriteString("]")

    return out.String()
}

在词法分析器中注册一个新的前缀处理函数

func (p *Parser) parseExpressionList(end token.TokenType) []ast.Expression {
    list := []ast.Expression{}

    if p.peekTokenIs(end) {
        p.nextToken()
        // []
        return list
    }

    p.nextToken()
    list = append(list, p.parseExpression(LOWEST))

    // [
    for p.peekTokenIs(token.COMMA) {
        p.nextToken() // [1
        p.nextToken() // [1,
        list = append(list, p.parseExpression(LOWEST))
    }

    if !p.expectPeek(end) {
        return nil
    }

    return list
}

// 解析函数-数组字面量-前缀
func (p *Parser) parseArrayLiteral() ast.Expression {
    array := &ast.ArrayLiteral{Token: p.curToken}
    array.Elements = p.parseExpressionList(token.RBRACKET)
    return array
}

// 创建解析器
func New(l *lexer.Lexer) *Parser {
    p := &Parser{l: l, errors: []string{}}

    // ...
    p.registerPrefix(token.LBRACKET, p.parseArrayLiteral)
    // ...
    return p
}

修改 parseCallExpression

func (p *Parser) parseCallExpression(function ast.Expression) ast.Expression {
    exp := &ast.CallExpression{Token: p.curToken, Function: function}
    exp.Arguments = p.parseExpressionList(token.RPAREN)
    return exp
}

测试

// parser/parser.go
func TestParsingArrayLiterals(t *testing.T) {
    input := `[1, 2*2,3+3]`

    l := lexer.New(input)
    p := New(l)
    program := p.ParseProgram()
    checkParserErrors(t, p)
    stmt, ok := program.Statements[0].(*ast.ExpressionStatement)
    array, ok := stmt.Expression.(*ast.ArrayLiteral)
    if !ok {
        t.Fatalf("exp not ast.ArrayLiteral. got=%T", stmt.Expression)
    }
    if len(array.Elements) != 3 {
        t.Fatalf("len(array.Elements) not 3. got=%d", len(array.Elements))
    }
    testIntegerLiteral(t, array.Elements[0], 1)
    testInfixExpression(t, array.Elements[1], 2, "*", 2)
    testInfixExpression(t, array.Elements[2], 3, "+", 3)
}

4.4.3 索引运算符表达式语法分析

语法结构: <表达式>[<表达式>]

1.定义新的 AST 节点

type IndexExpression struct {
    Token token.Token // '['词法单元
    Left  Expression
    Index Expression
}

func (ie *IndexExpression) expressionNode()      {}
func (ie *IndexExpression) TokenLiteral() string { return ie.Token.Literal }
func (ie *IndexExpression) String() string {
    var out bytes.Buffer

    out.WriteString("(")
    out.WriteString(ie.Left.String())
    out.WriteString("[")
    out.WriteString(ie.Index.String())
    out.WriteString("])")

    return out.String()
}

2.parseExpression 解析 left 和 index 表达式

索引运算符必须具有最高的优先级

将 myArr[0]中的[视为中缀运算符,myArr 视为左操作数,0 视为右操作数

// parser/parser.go
const (
    _ int = iota // 0
    LOWEST
    EQUALS     // ==
    LESSGEATER // > or <
    SUM        // +
    PRODUCT    // *
    PREFIX     // -X or !X
    CALL       // myFunction(X)
    INDEX      // array[index]
)

// 优先级map
var precedences = map[token.TokenType]int{
    // ...
    token.LBRACKET: INDEX,
}
// 解析函数-索引运算符-中缀
func (p *Parser) parseIndexExpression(left ast.Expression) ast.Expression {
    exp := &ast.IndexExpression{Token: p.curToken, Left: left}

    p.nextToken()
    exp.Index = p.parseExpression(LOWEST)

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

    return exp
}

// 创建解析器
func New(l *lexer.Lexer) *Parser {
    p := &Parser{l: l, errors: []string{}}

    // ...
    p.registerInfix(token.LBRACKET, p.parseIndexExpression)

    // 读取两个词法单元,设置peekToken和curToken
    p.nextToken()
    p.nextToken()

    return p
}

测试

func TestOperatorPrecedenceParsing(t *testing.T) {
    tests := []struct {
        input    string
        expected string
    }{
        // ...
        {
            "a * [1, 2, 3, 4][b * c] * d",
            "((a * ([1, 2, 3, 4][(b * c)])) * d)",
        },
        {
            "add(a * b[2], b[1], 2 * [1, 2][1])",
            "add((a * (b[2])), (b[1]), (2 * ([1, 2][1])))",
        },
    }

    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)
        }
    }
}
func TestParsingIndexExpressions(t *testing.T) {
    input := "myArr[1+1]"
    l := lexer.New(input)
    p := New(l)
    program := p.ParseProgram()
    checkParserErrors(t, p)
    stmt, ok := program.Statements[0].(*ast.ExpressionStatement)
    indexExp, ok := stmt.Expression.(*ast.IndexExpression)
    if !ok {
        t.Fatalf("exp not *ast.IndexExpression. got=%T", stmt.Expression)
    }
    if !testIdentifier(t, indexExp.Left, "myArr") {
        return
    }
    if !testInfixExpression(t, indexExp.Index, 1, "+", 1) {
        return
    }
}

4.4.4 数组字面量求值

只需要将数组映射到 Go 的切片就能省去很多工作.

定义一个 object.Array 类型,作为求值返回的结果

// object/object.go
type Array struct {
    Elements []Object
}

func (ao *Array) Type() ObjectType { return ARRAY_OBJ }
func (ao *Array) Inspect() string {
    var out bytes.Buffer

    elements := []string{}
    for _, e := range ao.Elements {
        elements = append(elements, e.Inspect())
    }

    out.WriteString("[")
    out.WriteString(strings.Join(elements, ", "))
    out.WriteString("]")

    return out.String()
}

eval 函数求值

func Eval(node ast.Node, env *object.Environment) object.Object {
    switch node := node.(type) {
    // 语句 -> 继续遍历
    // 根节点
    case *ast.Program:
        return evalProgram(node, env)
    // 块语句
    case *ast.BlockStatement:
        return evalBlockStatement(node, env)
    // Let语句
    case *ast.LetStatement:
        val := Eval(node.Value, env)
        if isError(val) {
            return val
        }
        // 关联标识符和值
        env.Set(node.Name.Value, val)
    // 标识符
    case *ast.Identifier:
        return evalIdentifier(node, env)
    // 函数语句
    case *ast.FunctionLiteral:
        params := node.Parameters
        body := node.Body
        return &object.Function{Parameters: params, Body: body, Env: env}
    // 调用函数
    case *ast.CallExpression:
        function := Eval(node.Function, env)
        if isError(function) {
            return function
        }
        args := evalExpressions(node.Arguments, env)
        if len(args) == 1 && isError(args[0]) {
            return args[0]
        }

        return applyFunction(function, args)
    // Return语句
    case *ast.ReturnStatement:
        // 对返回值进行求值
        val := Eval(node.ReturnValue, env)
        // 判断该中断是不是Error引发的
        if isError(val) {
            return val
        }
        return &object.ReturnValue{Value: val}
    // IF语句
    case *ast.IfExpression:
        return evalIfExpression(node, env)
    // 表达式语句
    case *ast.ExpressionStatement:
        return Eval(node.Expression, env)
    // 表达式 -> 求值
    case *ast.IntegerLiteral:
        return &object.Integer{Value: node.Value}
    // 布尔型
    case *ast.Boolean:
        return nativeBooleanObject(node.Value)
    // 字符串
    case *ast.StringLiteral:
        return &object.String{Value: node.Value}
    // 数组
    case *ast.ArrayLiteral:
        elements := evalExpressions(node.Elements, env)
        if len(elements) == 1 && isError(elements[0]) {
            return elements[0]
        }
        return &object.Array{Elements: elements}
    // 前缀表达式
    case *ast.PrefixExpression:
        // 如果一直是!或-,就会一直Eval,直到遇到其他类型,多次执行!或-
        right := Eval(node.Right, env)
        // 判断该中断是不是Error引发的
        if isError(right) {
            return right
        }
        return evalPrefixExpression(node.Operator, right)
    // 中缀表达式
    case *ast.InfixExpression:
        left := Eval(node.Left, env)
        // 判断该中断是不是Error引发的
        if isError(left) {
            return left
        }
        right := Eval(node.Right, env)
        // 判断该中断是不是Error引发的
        if isError(right) {
            return right
        }
        return evalInfixExpression(node.Operator, left, right)
    }
    return nil
}

4.4.5 索引运算符表达式求值

索引运算符的左操作数是任何表达式,索引本身也可以是任何表达式,要先对这两个表达式进行求值,然后才能对索引本身求值

// evaluator/evaluator.go
// 数组索引求值
func evalArrayIndexExpression(array, index object.Object) object.Object {
    arrayObj := array.(*object.Array)
    idx := index.(*object.Integer).Value
    max := int64(len(arrayObj.Elements) - 1)
    if idx < 0 || idx > max {
        return NULL
    }
    return arrayObj.Elements[idx]
}

// 索引表达式求值
func evalIndexExpression(left, index object.Object) object.Object {
    switch {
    case left.Type() == object.ARRAY_OBJ && index.Type() == object.INTEGER_OBJ:
        return evalArrayIndexExpression(left, index)
    default:
        return newError("index operator not supported: %s", left.Type())
    }
}
func Eval(node ast.Node, env *object.Environment) object.Object {
    switch node := node.(type) {
    // ...
    // 索引表达式
    case *ast.IndexExpression:
        left := Eval(node.Left, env)
        if isError(left) {
            return left
        }
        index := Eval(node.Index, env)
        if isError(index) {
            return index
        }
        return evalIndexExpression(left, index)
    // ...
    return nil
}

测试

func TestArrayIndexExpression(t *testing.T) {
    ts := []struct {
        input    string
        expected interface{}
    }{
        {"[1,2,3][0]", 1},
        {"[1,2,3][1]", 2},
        {"[1,2,3][2]", 3},
        {"let i = 0; [1][i];", 1},
        {"[1,2,3][1+1]", 3},
        {"let myArr=[1,2,3]; myArr[2];", 3},
        {"let myArr=[1,2,3]; myArr[0]+myArr[1]+myArr[2];", 6},
        {"let myArr = [1,2,3]; let i = myArr[0]; myArr[i];",2},
        {"[1,2,3][3]",nil},
        {"[1,2,3][-1]",nil},
    }
    for _,tt:=range ts{
        eval:=testEval(tt.input)
        integer,ok:=tt.expected.(int)
        if ok{
            testIntegerObject(t,eval,int64(integer))
        }else {
            testNullObject(t,eval)
        }
    }
}

4.4.6 为数组添加内置函数

修改 len 函数,让它可以用于数组

// evaluator/builtins.go
var builtins = map[string]*object.Builtin{
    "len": &object.Builtin{
        Fn: func(args ...object.Object) object.Object {
            if len(args) != 1 {
                return newError("wrong number of arguments. got=%d, want=1", len(args))
            }
            switch arg := args[0].(type) {
            case *object.String:
                return &object.Integer{Value: int64(len(arg.Value))}
            case *object.Array:
                return &object.Integer{Value: int64(len(arg.Elements))}
            default:
                return newError("argument to `len` not supported. got %s", args[0].Type())
            }
        },
    },
    // todo: 文件读写 网络编程
}

first 函数

var builtins = map[string]*object.Builtin{
    // ...
    // 传入数组,返回第一个元素
    "first": &object.Builtin{
        Fn: func(args ...object.Object) object.Object {
            if len(args) != 1 {
                return newError("wrong number of arguments. got=%d, want=1", len(args))
            }
            if args[0].Type() != object.ARRAY_OBJ {
                return newError("argument to `first` must be ARRAY. got %s", args[0].Type())
            }
            arr := args[0].(*object.Array)
            if len(arr.Elements) > 0 {
                return arr.Elements[0]
            }
            return NULL
        },
    },
    //
}

last 函数

var builtins = map[string]*object.Builtin{
    // ...
    // 传入数组,返回最后一个元素
    "last": &object.Builtin{
        Fn: func(args ...object.Object) object.Object {
            if len(args) != 1 {
                return newError("wrong number of arguments. got=%d, want=1", len(args))
            }
            if args[0].Type() != object.ARRAY_OBJ {
                return newError("argument to `last` must be ARRAY. got %s", args[0].Type())
            }
            arr := args[0].(*object.Array)
            length := len(arr.Elements)
            if len(arr.Elements) > 0 {
                return arr.Elements[length-1]
            }
            return NULL
        },
    },
}

在其他语言中称为 cdr(Scheme)或 tail,而我们称为 rest

var builtins = map[string]*object.Builtin{
    // ...
    // 传入数组,返回除了第一个元素以外的所有元素,返回的是新分配的数组
    "rest": &object.Builtin{
        Fn: func(args ...object.Object) object.Object {
            if len(args) != 1 {
                return newError("wrong number of arguments. got=%d, want=1", len(args))
            }
            if args[0].Type() != object.ARRAY_OBJ {
                return newError("argument to `rest` must be ARRAY. got %s", args[0].Type())
            }
            arr := args[0].(*object.Array)
            length := len(arr.Elements)
            if len(arr.Elements) > 0 {
                newElements := make([]object.Object, length-1, length-1)
                copy(newElements, arr.Elements[1:length])
                return &object.Array{Elements: newElements}
            }
            return NULL
        },
    },
}

push 函数,将新元素添加到数组的末尾,不修改旧数组,返回的是新数组.数组在 Monkey 里不可变的

var builtins = map[string]*object.Builtin{
    // ...
    // 向数组末尾添加新元素,返回一个新数组
    "push": &object.Builtin{
        Fn: func(args ...object.Object) object.Object {
            if len(args) != 2 {
                return newError("wrong number of arguments. got=%d, want=2", len(args))
            }
            if args[0].Type() != object.ARRAY_OBJ {
                return newError("argument to `push` must be ARRAY. got %s", args[0].Type())
            }
            arr := args[0].(*object.Array)
            length := len(arr.Elements)

            newElements := make([]object.Object, length+1, length+1)
            copy(newElements, arr.Elements)
            newElements[length] = args[1]
            return &object.Array{Elements: newElements}
        },
    },
}

4.4.7 测试驱动数组

可以通过现有的内置函数实现 map,reduce,sum 方法

let map = fn(arr,f) {
    let map_iter = fn(arr, accumulated) {
        if (len(arr) == 0) {
            accumulated;
        } else {
            map_iter(rest(arr), push(accumulated, f(first(arr))));
        };
    };
    map_iter(arr,[]);
};
let reduce = fn(arr,initial,f){
    let reduce_iter = fn(arr,res){
        if (len(arr) == 0) {
            res
        }else{
            reduce_iter(rest(arr),f(res,first(arr)));
        }
    };
    reduce_iter(arr,initial);
}
let sum = fn(arr){
    reduce(arr, 0, fn(initial, el) { initial + el });
}

4.5 哈希表

哈希表->哈希字面量: 用花括号括起来的键值对,列表中的键值对用逗号分隔.用冒号区分键和值

哈希表的键都是字符串,并且可以通过索引运算符表达式从哈希表获取值(索引可以是数字、字符串、布尔值)

4.5.1 哈希字面量词法分析

{“name”: “john”,”age”: 12}

将 { } , : 转换为词法单元,前三个处理过了,这里处理:

// token/token.go
const (
    // ...
    COLON     = ":"
    // ...
)

// lexer/lexer.go
func (l *Lexer) NextToken() token.Token {
    var tok token.Token

    // ...
    case ':':
        tok = newToken(token.COLON, l.ch)
    // ...
    }

    l.readChar()
    return tok
}

测试

// lexer/lexer_test.go
func TestNextToken(t *testing.T) {
    input :=
        `
    let five = 5;
    let ten = 10;

    let add = fn(x, y) {
    x + y;
    };

    let result = add(five, ten);
    !-/*5;
    5 < 10 > 5;

    if (5 < 10) {
        return true;
    } else {
        return false;
    }

    10 == 10;
    10 != 9;

    "foobar0"
    "\nfoo bar"
    [1,2];

    {"foo": "bar"}
    `

    tests := []struct {
        expectedType    token.TokenType
        expectedLiteral string
    }{
        // ...
        {token.LBRACE, "{"},
        {token.STRING, "foo"},
        {token.COLON, ":"},
        {token.STRING, "bar"},
        {token.RBRACE, "}"},
        {token.EOF, ""},
    }

    l := New(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)
        }
    }
}

4.5.2 哈希字面量语法分析

语法结构: {<表达式> : <表达式>, <表达式> : <表达式>, … }

// ast/ast.go
type HashLiteral struct {
    Token token.Token // '{'词法单元
    Pairs map[Expression]Expression
}

func (hl *HashLiteral) expressionNode()      {}
func (hl *HashLiteral) TokenLiteral() string { return hl.Token.Literal }
func (hl *HashLiteral) String() string {
    var out bytes.Buffer

    pairs := []string{}
    for key, val := range hl.Pairs {
        pairs = append(pairs, key.String()+":"+val.String())
    }

    out.WriteString("{")
    out.WriteString(strings.Join(pairs, ", "))
    out.WriteString("}")

    return out.String()
}

添加前缀解析函数(解析{)

// parser/parser.go
func (p *Parser) parseHashLiteral() ast.Expression {
    hash := &ast.HashLiteral{Token: p.curToken}
    hash.Pairs = make(map[ast.Expression]ast.Expression)

    for !p.peekTokenIs(token.RBRACE) {
        p.nextToken()
        // {"key"
        key := p.parseExpression(LOWEST)

        // {"key":
        if !p.expectPeek(token.COLON) {
            return nil
        }

        // {"key":"val"
        p.nextToken()
        val := p.parseExpression(LOWEST)
        hash.Pairs[key] = val

        if !p.peekTokenIs(token.RBRACE) && !p.expectPeek(token.COMMA) {
            return nil
        }
    }
    // {"key":"val","key1":"val1"}
    if !p.expectPeek(token.RBRACE) {
        return nil
    }
    return hash
}
func New(l *lexer.Lexer) *Parser {
    p := &Parser{l: l, errors: []string{}}

    // ...
    p.registerPrefix(token.LBRACE, p.parseHashLiteral)
    // ...
    // 读取两个词法单元,设置peekToken和curToken
    p.nextToken()
    p.nextToken()

    return p
}

测试

func TestParsingHashLiteralsStringKeys(t *testing.T) {
    input := `{"one": 1, "two": 2, "three": 3}`

    l := lexer.New(input)
    p := New(l)
    pro := p.ParseProgram()
    checkParserErrors(t, p)

    stmt := pro.Statements[0].(*ast.ExpressionStatement)
    hash, ok := stmt.Expression.(*ast.HashLiteral)
    if !ok {
        t.Fatalf("exp is not ast.HashLiteral. got=%T", stmt.Expression)
    }

    if len(hash.Pairs) != 3 {
        t.Errorf("hash.Pairs has wrong length. got=%d", len(hash.Pairs))
    }

    expected := map[string]int64{
        "one":   1,
        "two":   2,
        "three": 3,
    }

    for k, v := range hash.Pairs {
        literal, ok := k.(*ast.StringLiteral)
        if !ok {
            t.Errorf("key is not ast.StringLiteral. got=%T", stmt.Expression)
        }

        expectedValue := expected[literal.String()]

        testIntegerLiteral(t, v, expectedValue)
    }
}
func TestParsingEmptyHashLiteral(t *testing.T) {
    input := "{}"

    l := lexer.New(input)
    p := New(l)
    pro := p.ParseProgram()
    checkParserErrors(t, p)

    stmt := pro.Statements[0].(*ast.ExpressionStatement)
    hash, ok := stmt.Expression.(*ast.HashLiteral)
    if !ok {
        t.Fatalf("exp is not ast.HashLiteral. got=%T", stmt.Expression)
    }

    if len(hash.Pairs) != 0 {
        t.Errorf("hash.Pairs has wrong length: %d", len(hash.Pairs))
    }
}

func TestParsingHashLiteralsIntegerKeys(t *testing.T) {
    input := `{1: 1, 2: 2, 3: 3}`

    l := lexer.New(input)
    p := New(l)
    program := p.ParseProgram()
    checkParserErrors(t, p)

    stmt := program.Statements[0].(*ast.ExpressionStatement)
    hash, ok := stmt.Expression.(*ast.HashLiteral)
    if !ok {
        t.Fatalf("exp is not ast.HashLiteral. got=%T", stmt.Expression)
    }

    expected := map[string]int64{
        "1": 1,
        "2": 2,
        "3": 3,
    }

    if len(hash.Pairs) != len(expected) {
        t.Errorf("hash.Pairs has wrong length. got=%d", len(hash.Pairs))
    }

    for key, value := range hash.Pairs {
        integer, ok := key.(*ast.IntegerLiteral)
        if !ok {
            t.Errorf("key is not ast.IntegerLiteral. got=%T", key)
            continue
        }

        expectedValue := expected[integer.String()]

        testIntegerLiteral(t, value, expectedValue)
    }
}
func TestParsingHashLiteralsWithExpressions(t *testing.T) {
    input := `{"one": 0 + 1, "two": 10 - 8, "three": 15 / 5}`

    l := lexer.New(input)
    p := New(l)
    program := p.ParseProgram()
    checkParserErrors(t, p)

    stmt := program.Statements[0].(*ast.ExpressionStatement)
    hash, ok := stmt.Expression.(*ast.HashLiteral)
    if !ok {
        t.Fatalf("exp is not ast.HashLiteral. got=%T", stmt.Expression)
    }

    if len(hash.Pairs) != 3 {
        t.Errorf("hash.Pairs has wrong length. got=%d", len(hash.Pairs))
    }

    tests := map[string]func(ast.Expression){
        "one": func(e ast.Expression) {
            testInfixExpression(t, e, 0, "+", 1)
        },
        "two": func(e ast.Expression) {
            testInfixExpression(t, e, 10, "-", 8)
        },
        "three": func(e ast.Expression) {
            testInfixExpression(t, e, 15, "/", 5)
        },
    }

    for key, value := range hash.Pairs {
        literal, ok := key.(*ast.StringLiteral)
        if !ok {
            t.Errorf("key is not ast.StringLiteral. got=%T", key)
            continue
        }

        testFunc, ok := tests[literal.String()]
        if !ok {
            t.Errorf("No test function for key %q found", literal.String())
            continue
        }

        testFunc(value)
    }
}

4.5.3 哈希对象

拓展对象系统

问题: 看代码

let hash = {"name": "Monkey"}
hash["name"]

第一行,如果将数据存入了 Pairs(map[Object]Object),那么在第二行取值时,用于索引表达式里的索引(“name”)被解析为新的 String 对象,虽然和第一行的 key 一样,值都是 name,但是却是两个不同的对象,所以无法从中取到值

第一种解决方法是添加对键的判断,如果是 Object.String,就用 Value 进行比较,但是这样会把键的查找时间从 O(1)变为 O(n)

另一种方法是键 Pairs 定义为 map[string]Object,用*object.String 的 Value 作为键,但是这样就不能使用整数和布尔作为键了

另一种方法是,提供为 object 生成可用于比较的键,不同类型的 object 要有不同的哈希键

type HashKey struct {
    Type  ObjectType
    Value uint64
}

func (b *Boolean) HashKey() HashKey {
    var value uint64

    if b.Value {
        value = 1
    } else {
        value = 0
    }

    return HashKey{Type: b.Type(), Value: value}
}

func (i *Integer) HashKey() HashKey {
    return HashKey{Type: i.Type(), Value: uint64(i.Value)}
}

func (s *String) HashKey() HashKey {
    h := fnv.New64a()
    h.Write([]byte(s.Value))

    return HashKey{Type: s.Type(), Value: h.Sum64()}
}

现在可以进行比较,但是不同 Value 的字符串仍然可能生成相同的哈希值.不过概率很小,这种情况就是哈希碰撞,可以用开放寻址法或单链法解决.

测试

// object/object_test.go
package object

import "testing"

func TestStringHashKey(t *testing.T){
    hello1:=&String{Value: "Hello World"}
    hello2:=&String{Value: "Hello World"}
    diff1:=&String{Value: "My name is johnny"}
    diff2:=&String{Value: "My name is johnny"}

    if hello1.HashKey() != hello2.HashKey() {
        t.Errorf("strings with same content have different hash keys")
    }
    if diff1.HashKey() != diff2.HashKey() {
        t.Errorf("strings with same content have different hash keys")
    }

    if hello1.HashKey() == diff1.HashKey(){
        t.Errorf("strings with different content have same hash keys")
    }
}

定义新的 object.Hash 并使用新的 HashKey 类型

// object/object.go
type HashPair struct {
    Key   Object
    Value Object
}

type Hash struct {
    Pairs map[HashKey]HashPair
}

func (h *Hash) Type() ObjectType { return HASH_OBJ }

使用 HashPair 而不直接键 Pairs 定义为 map[HashKey]Object 是因为,需要在打印时(Inspect)输出原始的 key 值

func (h *Hash) Inspect() string {
    var out bytes.Buffer

    pairs := []string{}
    for _, pair := range h.Pairs {
        pairs = append(pairs, fmt.Sprint("%s: %s", pair.Key, pair.Value.Inspect()))
    }

    out.WriteString("{")
    out.WriteString(strings.Join(pairs, ", "))
    out.WriteString("}")

    return out.String()
}

定义一个接口,方便检查给定对象是否可以用作哈希表的键 key

// object/object.go
type Hashable interface {
    HashKey() HashKey
}

4.5.4 哈希字面量求值

// evaluator/evaluator.go
func evalHashLiteral(node *ast.HashLiteral, env *object.Environment) object.Object {
    pairs := make(map[object.HashKey]object.HashPair)

    for keyNode, valueNode := range node.Pairs {
        // 解析hash[key] -> 标识符 -> 求值
        key := Eval(keyNode, env)
        if isError(key) {
            return key
        }
        // (是否可以)转为hashable类型 -> 是 -> 转
        // key是否可以求hash(只有int和string,bool可以)
        hashKey, ok := key.(object.Hashable)
        if !ok {
            return newError("unusable as hash key: %s", key.Type())
        }
        // 解析hash[key] = value
        value := Eval(valueNode, env)
        if isError(value) {
            return value
        }
        hashed := hashKey.HashKey()
        pairs[hashed] = object.HashPair{Key: key, Value: value}
    }
    return &object.Hash{Pairs: pairs}
}

func Eval(node ast.Node, env *object.Environment) object.Object {
    switch node := node.(type) {
    // ...
    // 哈希表
    case *ast.HashLiteral:
        return evalHashLiteral(node, env)
    // ...
    }
    return nil
}

测试

// evaluator/evaluator_test.go
func TestHashLiterals(t *testing.T) {
    input := `let two = "two";
    {
        "one": 10-9,
        two: 1+1,
        "thr"+"ee": 6/2,
        4: 4,
        true: 5,
        false: 6
    }
    `
    eval := testEval(input)
    res, ok := eval.(*object.Hash)
    if !ok {
        t.Fatalf("eval didn't return hash. got=%T(%+v)", eval, eval)
    }
    exp := map[object.HashKey]int64{
        (&object.String{Value: "one"}).HashKey():   1,
        (&object.String{Value: "two"}).HashKey():   2,
        (&object.String{Value: "three"}).HashKey(): 3,
        (&object.Integer{Value: 4}).HashKey():      4,
        TRUE.HashKey():                             5,
        FALSE.HashKey():                            6,
    }
    if len(res.Pairs) != len(exp) {
        t.Fatalf("hash has wrong num of pairs: %d", len(res.Pairs))
    }
    for expKey, expVal := range exp {
        pair, ok := res.Pairs[expKey]
        if !ok {
            t.Errorf("no pair for given key in pairs")
        }
        testIntegerObject(t, pair.Value, expVal)
    }
}

4.5.5 哈希索引表达式求值

在 evalIndexExpression 里添加对 hash 索引表达式的处理

// evaluator/evaluator.go
func evalIndexExpression(left, index object.Object) object.Object {
    switch {
    case left.Type() == object.ARRAY_OBJ && index.Type() == object.INTEGER_OBJ:
        return evalArrayIndexExpression(left, index)
        // 哈希索引表达式
    case left.Type() == object.HASH_OBJ:
        return evalHashIndexExpression(left, index)
    default:
        return newError("index operator not supported: %s", left.Type())
    }
}

求值

func evalHashIndexExpression(hash, index object.Object) object.Object {
    hashObj := hash.(*object.Hash)

    k, ok := index.(object.Hashable)
    if !ok {
        return newError("unusable as hash key: %s", index.Type())
    }

    pair, ok := hashObj.Pairs[k.HashKey()]
    if !ok {
        return NULL
    }

    return pair.Value
}

测试

// evaluator/evaluator.go
func TestHashIndexExpression(t *testing.T) {
    ts := []struct {
        input string
        exp   interface{}
    }{
        {
            `{"foo": 5}["foo"]`,
            5,
        },
        {
            `{"foo": 5}["bar"]`,
            nil,
        },
        {
            `let key = "foo"; {"foo": 5}[key]`,
            5,
        },
        {
            `{}["foo"]`,
            nil,
        },
        {
            `{5: 5}[5]`,
            5,
        },
        {
            `{true: 5}[true]`,
            5,
        },
        {
            `{false: 5}[false]`,
            5,
        },
    }
    for _, tt := range ts {
        eval := testEval(tt.input)
        integer, ok := tt.exp.(int)
        if ok {
            testIntegerObject(t, eval, int64(integer))
        } else {
            testNullObject(t, eval)
        }
    }
}

4.6 大结局

实现 put 函数,用来向控制台打印数据.put 只打印,不产生值(所以会输出 puts 里的内容以及 null)

var builtins = map[string]*object.Builtin{
    // ...
    "puts": &object.Builtin{
        Fn: func(args ...object.Object) object.Object {
            for _, arg := range args {
                fmt.Println(arg.Inspect())
            }

            return NULL
        },
    },
    // ...
}

5 遗失的篇章: Monkey 的宏系统

5.1 宏系统

宏系统是指与宏相关的编程语言特性,宏可分为两大类: 文本替换宏和语法宏系统

文本替换宏系统比较简单,例子有 c 预处理器,在 c 代码中,可以用单独的宏生成和修改 c 代码,工作原理就是在 c 编译器编译和生成代码之前,先单独解析和求值这种语言

文本替换宏对代码的影响仅限于文本层面,更像是模板系统

语法宏系统不是将代码作为文本,而是将代码视为数据(比如 AST 使用的也不是字符串,而是数据结构)

以 Elixir 的 quote 为例.

quote do: 10 + 5;
{:+, [context: Elixir, import: Kernel],[10, 5]}

这里中缀表达式 10+5 在 do 块中作为单个参数传递给 quote.但是不同的是,这里不会对 10+5 求值.而是让 quote 返回一个表达这个表达式的数据结构,并且可以被代码访问

如果需要用 quote 构建一个 AST 节点,其中使用了标识符(绑定了数字字面量),这样的话是不行的,因为 quote 不会对标识符求值,所以我们需要一个 unquote 来对字面量求值,让 quote 使用该标识符的值

iex(6)> my_number = 99
99
iex(7)> quote do: 10 + 5 + unquote(my_number)
{:+,[context: Elixir,import: Kernel],
[{:+,[context: Elixir,import: Kernel],[10,5],99}]}

unquote 用来”跳出”quote 上下文并对其中的代码进行求值

quote 和 unquote 都是 Elixir 提供的工具,用于控制代码的求值时机和求值方式,并将代码转化为数据.大多数情况下它们是在宏里使用

Elixir 中还可以使用 defmacro 来定义宏,下面的例子是将使用+运算符的中缀表达式转换为使用-的中缀表达式

defmodule MacroExample do
    defmacro plus_to_minus(expression) do
        args = elem(expression,2)
        quote do
            unquote(Enum.at(args,0)) - unquote(Enum.at(args,1))
        end
    end
end

最重要的一点: 作为参数传递给宏的所有内容都相当于在 quote 中,也就是说,宏的参数不进行求值,可以像任何其他数据一样访问

5.2 Monkey 的宏系统

我们需要实现 quote,unquote,宏字面量 macro

宏字面量看起来像函数字面量,一旦将宏绑定名称,就可以像函数一样调用,只是求值方式不同,在参数传递给宏的主体之前不会进行求值

5.3 quote

quote 函数只在宏中使用，调用时不对参数求值，而是返回表示参数的 AST 节点

如何实现：先从返回值入手。对于 monkey 内部实现的函数来说，其返回值类型都是 object.Object，eval 函数要求传递进来的每个 Monkey 值都是 object.Object，该函数本身也返回一个 object.Object

为了让 quote 返回 ast.Node，需要封装，传递的是一个包含 ast.Node 的 object.Object

// object/object.go

const (
    // ...

    QUOTE_OBJ = "QUOTE"

)

type Quote struct {
    Node ast.Node
}

func (q *Quote) Type() ObjectType { return QUOTE_OBJ }
func (q *Quote) Inspect() string  { return "QUOTE(" + q.Node.String() + ")" }

eval 函数会对表达式求值，即使定义 quote 内置函数，该函数的参数也会被求值，和我们宏的使用目的是冲突的

应该修改 eval 的一部分代码，避免对 quote 表达式的参数求值

// evaluator/evaluator.go
func Eval(node ast.Node, env *object.Environment) object.Object {
    switch node := node.(type) {
    // ...
    // 调用函数
    case *ast.CallExpression:
        if node.Function.TokenLiteral() == "quote" {
            return quote(node.Arguments[0])
        }
        // ...
    // ...
    }
    return nil
}

这里只检查了 TokenLiteral 方法，来判断是不是 quote 调用，如果是，就将传递给 quote 的单个参数再传递给另一个同样名为 quote 的函数，前面提到的 quote 只能使用一个参数

// evaluator/quote_unquote.go
package evaluator

import (
    "malang/ast"
    "malang/object"
)

func quote(node ast.Node) object.Object {
    return &object.Quote{Node: node}
}

测试

package evaluator

import (
    "malang/object"
    "testing"
)

func TestQuote(t *testing.T) {
    ts := []struct {
        input    string
        expected string
    }{
        {
            `quote(5)`,
            `5`,
        },
        {
            `quote(5 + 8)`,
            `(5 + 8)`,
        },
        {
            `quote(foobar)`,
            `foobar`,
        },
        {
            `quote(foobar + barfoo)`,
            `(foobar + barfoo)`,
        },
    }

    for _, tt := range ts {
        eval := testEval(tt.input)
        quote, ok := eval.(*object.Quote)
        if !ok {
            t.Fatalf("expected *object.Quote. got=%T (%+v)", eval, eval)
        }
        if quote.Node == nil {
            t.Fatalf("quote.Node is nil")
        }
        if quote.Node.String() != tt.expected {
            t.Errorf("not equa. got=%q, want %q", quote.Node.String(), tt.expected)
        }
    }
}

5.4 unquote

unquote 可以对 quote 调用中的表达式求值

由于 unquote 调用只在 quote 调用的参数中使用，因此 eval 方法无法对 unquote（作为 quote 的参数）求值，不能依赖 eval 的递归性质查找 unquote 调用并对其求值。

必须遍历传给 quote 的参数，从中找到 unquote 的调用，进而用 eval 对 unquote 的参数求值。

5.4.1 遍历树

首先要遍历 AST，找到对 unquote 的调用并将调用的参数传递给 eval。在对参数求值后，将用 eval 调用的结果替换 unquote 有关的整个*ast.CallException

问题是，这样需要将*ast.CallExpression 节点替换为 Eval 的返回值(object.Object)，解决方案是将 unquote 调用的结果转换为新的 AST 节点，用新的 AST 节点替换（修改）现有的 unquote 调用

为了手动解析 unquote，需要写一个遍历 AST 并按需修改和替换 ast.Node 的通用函数

  1. 第一步

    // ast/modify_test.go
package ast

import (
    "reflect"
    "testing"
)

func TestModify(t *testing.T) {
    one := func() Expression { return &IntegerLiteral{Value: 1} }
    two := func() Expression { return &IntegerLiteral{Value: 2} }

    tureOneIntoTwo := func(node Node) Node {
        integer, ok := node.(*IntegerLiteral)
        if !ok {
            return node
        }
        if integer.Value != 1 {
            return node
        }
        integer.Value = 2
        return integer
    }

    ts := []struct {
        input    Node
        expected Node
    }{
        {
            one(),
            two(),
        },
        {
            &Program{
                Statements: []Statement{
                    &ExpressionStatement{Expression: one()},
                },
            },
            &Program{
                Statements: []Statement{
                    &ExpressionStatement{Expression: two()},
                },
            },
        },
    }

    for _, tt := range ts {
        modified := Modify(tt.input, tureOneIntoTwo)
        equal := reflect.DeepEqual(modified, tt.expected)
        if !equal {
            t.Errorf("not equal. got=%#v, want=%#v", modified, tt.expected)
        }
    }
}

    在测试前定义了 one 和 two 两个辅助函数，返回封装了数字的 *ast.IntegerLiteral，不用再重复创建整数字面量

    定义 turnOneIntoTwo 函数，检查传入的 node，如果是字面量 1 就改为 2，用来测试修改 node 节点的操作

    // ast/modify.go
package ast

type ModifierFunc func(Node) Node

func Modify(node Node, modifier ModifierFunc) Node {
    switch node := node.(type) {
    case *Program:
        for i, statement := range node.Statements {
            node.Statements[i], _ = Modify(statement, modifier).(Statement)
        }
    case *ExpressionStatement:
        node.Expression, _ = Modify(node.Expression, modifier).(Expression)
    }
    return modifier(node)
}

    ast.Modify 做了两件事

    第一是递归遍历给定的 ast.Node 的子节点。如果这些节点有子节点，就让每个子节点调用 ast.Modify，也就是递归

    递归可以把作为调用参数的节点替换成调用返回的节点。

    最后，让得到的 Node 调用 modifier，返回结果。如果只调用 modifier(node)，然后执行 return node，那么只是修改了节点，而没有替换 AST 中的节点

    最后一行的另一个作用是停止递归

  2. 完成遍历

    // ast/modify_test.go
package ast

import (
    "reflect"
    "testing"
)

func TestModify(t *testing.T) {
    one := func() Expression { return &IntegerLiteral{Value: 1} }
    two := func() Expression { return &IntegerLiteral{Value: 2} }

    tureOneIntoTwo := func(node Node) Node {
        integer, ok := node.(*IntegerLiteral)
        if !ok {
            return node
        }
        if integer.Value != 1 {
            return node
        }
        integer.Value = 2
        return integer
    }

    ts := []struct {
        input    Node
        expected Node
    }{
        {
            one(),
            two(),
        },
        {
            &Program{
                Statements: []Statement{
                    &ExpressionStatement{Expression: one()},
                },
            },
            &Program{
                Statements: []Statement{
                    &ExpressionStatement{Expression: two()},
                },
            },
        },
        {
            &InfixExpression{Left: one(), Operator: "+", Right: two()},
            &InfixExpression{Left: two(), Operator: "+", Right: two()},
        },
        {
            &InfixExpression{Left: two(), Operator: "+", Right: one()},
            &InfixExpression{Left: two(), Operator: "+", Right: two()},
        },
        {
            &PrefixExpression{Operator: "-", Right: one()},
            &PrefixExpression{Operator: "-", Right: two()},
        },
        {
            &IndexExpression{Left: one(), Index: one()},
            &IndexExpression{Left: two(), Index: two()},
        },
        {
            &IfExpression{
                Condition: one(),
                Consequence: &BlockStatement{
                    Statements: []Statement{
                        &ExpressionStatement{Expression: one()},
                    },
                },
                Alternative: &BlockStatement{
                    Statements: []Statement{
                        &ExpressionStatement{Expression: one()},
                    },
                },
            },
            &IfExpression{
                Condition: two(),
                Consequence: &BlockStatement{
                    Statements: []Statement{
                        &ExpressionStatement{Expression: two()},
                    },
                },
                Alternative: &BlockStatement{
                    Statements: []Statement{
                        &ExpressionStatement{Expression: two()},
                    },
                },
            },
        },
        {
            &ReturnStatement{ReturnValue: one()},
            &ReturnStatement{ReturnValue: two()},
        },
        {
            &LetStatement{Value: one()},
            &LetStatement{Value: two()},
        },
        {
            &FunctionLiteral{
                Parameters: []*Identifier{},
                Body: &BlockStatement{
                    Statements: []Statement{
                        &ExpressionStatement{Expression: one()},
                    },
                },
            },
            &FunctionLiteral{
                Parameters: []*Identifier{},
                Body: &BlockStatement{
                    Statements: []Statement{
                        &ExpressionStatement{Expression: two()},
                    },
                },
            },
        },
        {
            &ArrayLiteral{Elements: []Expression{one(), one()}},
            &ArrayLiteral{Elements: []Expression{two(), two()}},
        },
    }

    for _, tt := range ts {
        modified := Modify(tt.input, tureOneIntoTwo)
        equal := reflect.DeepEqual(modified, tt.expected)
        if !equal {
            t.Errorf("not equal. got=%#v, want=%#v", modified, tt.expected)
        }
    }

    hashLiteral := &HashLiteral{
        Pairs: map[Expression]Expression{
            one(): one(),
            two(): two(),
        },
    }

    Modify(hashLiteral, tureOneIntoTwo)

    for k, v := range hashLiteral.Pairs {
        k, _ := k.(*IntegerLiteral)
        if k.Value != 2 {
            t.Errorf("value is not %d, got=%d", 2, k.Value)
        }
        v, _ := v.(*IntegerLiteral)
        if v.Value != 2 {
            t.Errorf("value is not %d, got=%d", 2, v.Value)
        }
    }
}

    // ast/modify.go
package ast

type ModifierFunc func(Node) Node

func Modify(node Node, modifier ModifierFunc) Node {
    switch node := node.(type) {
    case *Program:
        for i, statement := range node.Statements {
            node.Statements[i], _ = Modify(statement, modifier).(Statement)
        }
    case *ExpressionStatement:
        node.Expression, _ = Modify(node.Expression, modifier).(Expression)
    case *InfixExpression:
        node.Left, _ = Modify(node.Left, modifier).(Expression)
        node.Right, _ = Modify(node.Right, modifier).(Expression)
    case *PrefixExpression:
        node.Right, _ = Modify(node.Right, modifier).(Expression)
    case *IndexExpression:
        node.Left, _ = Modify(node.Left, modifier).(Expression)
        node.Index, _ = Modify(node.Index, modifier).(Expression)
    case *IfExpression:
        node.Condition, _ = Modify(node.Condition, modifier).(Expression)
        node.Consequence, _ = Modify(node.Consequence, modifier).(*BlockStatement)
        if node.Alternative != nil {
            node.Alternative, _ = Modify(node.Alternative, modifier).(*BlockStatement)
        }
    case *BlockStatement:
        for i, _ := range node.Statements {
            node.Statements[i], _ = Modify(node.Statements[i], modifier).(Statement)
        }
    case *ReturnStatement:
        node.ReturnValue, _ = Modify(node.ReturnValue, modifier).(Expression)
    case *LetStatement:
        node.Value, _ = Modify(node.Value, modifier).(Expression)
    case *FunctionLiteral:
        for i, _ := range node.Parameters {
            node.Parameters[i] = Modify(node.Parameters[i], modifier).(*Identifier)
        }
        node.Body, _ = Modify(node.Body, modifier).(*BlockStatement)
    case *ArrayLiteral:
        for i, _ := range node.Elements {
            node.Elements[i], _ = Modify(node.Elements[i], modifier).(Expression)
        }
    case *HashLiteral:
        newPairs := make(map[Expression]Expression)
        for k, v := range node.Pairs {
            newk, _ := Modify(k, modifier).(Expression)
            newv, _ := Modify(v, modifier).(Expression)
            newPairs[newk] = newv
        }
        node.Pairs = newPairs
    }
    return modifier(node)
}

    下划线表示未完成的动作，我们没有确认类型转换是否出错。

5.4.2 替换 unquote 调用

每当 quote 中遇到 ast.Node，就交给 ast.Modify 处理，将 unquote 替换

package evaluator

import (
    "malang/ast"
    "malang/object"
)

func quote(node ast.Node) object.Object {
    return &object.Quote{Node: node}
}

func evalUnquoteCalls(quoted ast.Node) ast.Node {
    return ast.Modify(quoted, func(node ast.Node) ast.Node {
        if !isUnquoteCall(node) {
            return node
        }

        call, ok := node.(*ast.CallExpression)
        if !ok {
            return node
        }

        if len(call.Arguments) != 1 {
            return node
        }

        return node
    })
}

func isUnquoteCall(node ast.Node) bool {
    callExpression, ok := node.(*ast.CallExpression)
    if !ok {
        return false
    }

    return callExpression.Function.TokenLiteral() == "unquote"
}

为了对 unquote 的参数求值，需要调用 eval 方法，这需要有一个 *object.Evironment，在调用 quote 时，我们已经有一个环境，只需要修改 eval 的 case 分支，把环境添加到对 quote 的调用中

func Eval(node ast.Node, env *object.Environment) object.Object {
    switch node := node.(type) {
    case *ast.CallExpression:
        if node.Function.TokenLiteral() == "quote" {
            return quote(node.Arguments[0], env)
        }
    // ...
    }
}

package evaluator

import (
    "malang/ast"
    "malang/evaluator"
    "malang/object"
)

func quote(node ast.Node, env *object.Environment) object.Object {
    node = evalUnquoteCalls(node, env)
    return &object.Quote{Node: node}
}

func evalUnquoteCalls(quoted ast.Node, env *object.Environment) ast.Node {
    return ast.Modify(quoted, func(node ast.Node) ast.Node {
        // ...

        return Eval(call.Arguments[0], env)
    })
}

// ...

quote 函数返回*object.Quote，其中包含未求值的 ast.Node。可以调用 unquote 来对表达式求值。求值结果替换表达 unquote 调用表达式的 ast.Node。这个求值结果是由 eval 返回的 object.Object

为了替换 unquote 调用并将结果插入未求值的 ast.Node 中，必须在将其转换为 ast.Node

package evaluator

import (
    "fmt"
    "malang/ast"
    "malang/object"
    "malang/token"
)

func quote(node ast.Node, env *object.Environment) object.Object {
    node = evalUnquoteCalls(node, env)
    return &object.Quote{Node: node}
}

func evalUnquoteCalls(quoted ast.Node, env *object.Environment) ast.Node {
    return ast.Modify(quoted, func(node ast.Node) ast.Node {
        // ...

        unquoted := Eval(call.Arguments[0], env)
        return convertObjectToASTNode(unquoted)
    })
}

func convertObjectToASTNode(obj object.Object) ast.Node {
    switch obj := obj.(type) {
    case *object.Integer:
        t := token.Token{
            Type:    token.INT,
            Literal: fmt.Sprintf("%d", obj.Value),
        }
        return &ast.IntegerLiteral{Token: t, Value: obj.Value}

    default:
        return nil
    }
}

// ...

convertObjectToASTNode 函数创建了与某个 obj 对于的 ast.Node。还创建了一个 token.Token，因为 ast.Node 方法的 String 方法依赖这些词法单元。

// 添加两个测试用例
        {
            `
            let foobar = 8;
            quote(foobar)
            `,
            `foobar`,
        },
        {
            `
            let foobar = 8;
            quote(unquote(foobar))
            `,
            `8`,
        },

第二个测试是测试是否可以使用环境里的值

接下来完善 convertObjectToASTNode，让他可以转换更多类型的对象

// 测试
        {
            `quote(unquote(true))`,
            `true`,
        },
        {
            `quote(unquote(true == false))`,
            `false`,
        },
        {
            `quote(unquote(quote(4 + 4)))`,
            `(4 + 4)`,
        },
        {
            `
            let quotedInfixExpression = quote(4 + 4);
            quote(unquote(4 + 4) + unquote(quotedInfixExpression))
            `,
            `(8 + (4 + 4))`,
        },

func convertObjectToASTNode(obj object.Object) ast.Node {
    switch obj := obj.(type) {
    case *object.Integer:
        t := token.Token{
            Type:    token.INT,
            Literal: fmt.Sprintf("%d", obj.Value),
        }
        return &ast.IntegerLiteral{Token: t, Value: obj.Value}
    case *object.Boolean:
        var t token.Token
        if obj.Value {
            t = token.Token{Type: token.TRUE, Literal: "true"}
        } else {
            t = token.Token{Type: token.FALSE, Literal: "false"}
        }
        return &ast.Boolean{Token: t, Value: obj.Value}
    case *object.Quote:
        return obj.Node

    default:
        return nil
    }
}

当前只实现 Modify 修改子节点，而不更新父节点的 Token，这会导致节点的 String 方法输出的信息和节点不一致，甚至出现其他错误

convertObjectToASTNode 会实时创建新的词法单元，如果词法单元需要包含有关其来源的信息，如文件名或行号，就必须更新，对于动态创建的词法单元来说，可能非常困难

5.5 宏扩展

当前的解释器有一系列步骤：首先将源代码给词法分析器编译转换为词法单元；然后通过语法分析器将词法单元转换为 AST；最后 Eval 递归求值 AST 中的节点，逐个处理每条语句和表达式。相当于有 3 个独立步骤：词法分析、语法分析、求值。从数据结构的角度看，分别是字符串到词法单元、词法单元到 AST、AST 到输出

接下来要再添加一个阶段，宏扩展阶段。位于语法分析和求值之间。

“宏扩展”意味着要对源代码中所有宏的调用求值，并用求值的返回值替换原来的宏，宏的处理流程是将源代码作为输入，然后返回源代码，也就是调用宏之后会得到展开的源代码，因为每次调用都可能会生成更多的源代码

需要以可访问的形式表示源代码。只有语法分析器完成其工作后才会得到可访问的 AST。这就是为什么在语法分析阶段后添加宏扩展阶段，同时还要在求值之前添加宏扩展，因为修改不会再次求值的源代码没有意义

从数据结构的角度看，宏扩展阶段获取 AST 并对其进行修改

第一步是遍历 AST 并找到所有宏定义，宏定义只是一条 let 语句，其中的值是一个宏字面量

let maMacro = macro(x, y) { quote(x) + unquote(y); }

第二步是找到对宏的调用并对其求值。和 eval 的区别是，对宏调用求值的阶段，在对宏主体求值前不会对宏调用的参数求值，宏调用的参数在宏主体中会以未求值的 ast.Node 形式访问。即宏要与未求值的 AST 打交道

求值完成后，必须将宏调用的结果重新插回 AST

5.5.1 macro 关键字

添加 macro 词法单元

// token/token.go
const (
    // ...
    MACRO = "MACRO"
)

// 关键字map
var keywords = map[string]TokenType{
    // ...
    "macro":  MACRO,
}

// lexel/lexer_test.go
package lexer

import (
    "malang/token"
    "testing"
)

func TestNextToken(t *testing.T) {
    input :=
        `
    // ...
    macro(x, y) { x + y; };
    `

    tests := []struct {
        expectedType    token.TokenType
        expectedLiteral string
    }{
        // ...
        {token.MACRO, "macro"},
        {token.LPAREN, "("},
        {token.IDENT, "x"},
        {token.COMMA, ","},
        {token.IDENT, "y"},
        {token.RPAREN, ")"},
        {token.LBRACE, "{"},
        {token.IDENT, "x"},
        {token.PLUS, "+"},
        {token.IDENT, "y"},
        {token.SEMICOLON, ";"},
        {token.RBRACE, "}"},
        {token.SEMICOLON, ";"},
        {token.EOF, ""},
    }

    // ...
}

5.5.2 宏字面量语法分析

宏字面量和函数字面量定义基本一致

// ast/ast.go
type MacroLiteral struct {
    Token      token.Token
    Parameters []*Identifier
    Body       *BlockStatement
}

func (ml *MacroLiteral) String() string {
    var out bytes.Buffer

    params := []string{}
    for _, p := range ml.Parameters {
        params = append(params, p.String())
    }

    out.WriteString(ml.TokenLiteral())
    out.WriteString("(")
    out.WriteString(strings.Join(params, ", "))
    out.WriteString(")")
    out.WriteString(ml.Body.String())

    return out.String()
}
func (ml *MacroLiteral) TokenLiteral() string { return ml.Token.Literal }
func (ml *MacroLiteral) expressionNode()      {}

给 token.MACRO 注册一个新的 prefixParseFn 来解析宏字面量

// parser/parser.go
// 解析宏
func (p *Parser) parseMacroLiteral() ast.Expression {
    lit := &ast.MacroLiteral{Token: p.curToken}

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

    lit.Parameters = p.parseFunctionParameter()

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

    lit.Body = p.parseBlockStatement()

    return lit
}

// 创建解析器
func New(l *lexer.Lexer) *Parser {
    // ...

    p.registerPrefix(token.MACRO, p.parseMacroLiteral)

    // ...
}

测试

func TestMacroLiteralParsing(t *testing.T) {
    input := `macro(x, y) { x + y; }`

    l := lexer.New(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("statement is not ast.ExpressionStatement. got=%T", program.Statements[0])
    }

    macro, ok := stmt.Expression.(*ast.MacroLiteral)
    if !ok {
        t.Fatalf("stmt.Expression is not ast.MacroLiteral. got=%T", stmt.Expression)
    }

    if len(macro.Parameters) != 2 {
        t.Fatalf("macro literal parameters wrong. want 2, got=%d\n", len(macro.Parameters))
    }

    testLiteralExpression(t, macro.Parameters[0], "x")
    testLiteralExpression(t, macro.Parameters[1], "y")

    if len(macro.Body.Statements) != 1 {
        t.Fatalf("macro.Body.Statements has not 1 statements. got=%d\n", len(macro.Body.Statements))
    }

    bodyStmt, ok := macro.Body.Statements[0].(*ast.ExpressionStatement)
    if !ok {
        t.Fatalf("macro body stmt is not ast.ExpressionStatement. got=%T", macro.Body.Statements[0])
    }

    testInfixExpression(t, bodyStmt.Expression, "x", "+", "y")
}

5.5.3 定义宏

现在的词法分析器和语法分析器可以构建 ast.MacroLiteral 了，接下来就是从 AST 中提取所有宏定义并保存，宏扩展阶段的第一步是从 AST 中提取所有宏定义并保存，第二部是对其求值

// object/object.go
const (
    // ...
    Macro_OBJ        = "MACRO"
)

type Macro struct {
    Parameters []*ast.Identifier
    Body       *ast.BlockStatement
    Env        *Environment
}

func (m *Macro) Type() ObjectType { return Macro_OBJ }
func (m *Macro) Inspect() string {
    var out bytes.Buffer

    params := []string{}
    for _, p := range m.Parameters {
        params = append(params, p.String())
    }

    out.WriteString("macro")
    out.WriteString("(")
    out.WriteString(strings.Join(params, ", "))
    out.WriteString(") {\n")
    out.WriteString(m.Body.String())
    out.WriteString("\n}")

    return out.String()
}

在 AST 中查找宏定义并将其从 AST 中删除。

以下的第二句并不是宏定义

let myMacro = macro(x) {x}
let anotherNameForMyMacro = myMacro

如果是宏定义就传递给 addMacro，以便将宏定义添加到环境

// evaluator/macro_expansion.go
package evaluator

import (
    "malang/ast"
    "malang/object"
)

func DefineMacros(program *ast.Program, env *object.Environment) {
    definitions := []int{}

    // 查找宏定义
    for i, statement := range program.Statements {
        if isMacroDefinition(statement) {
            addMacro(statement, env)
            definitions = append(definitions, i)
        }
    }

    // 删除宏定义
    for i := len(definitions) - 1; i >= 0; i = i - 1 {
        definitionIndex := definitions[i]
        program.Statements = append(
            program.Statements[:definitionIndex],
            program.Statements[definitionIndex+1:]...,
        )
    }
}

// 决定什么是宏定义
func isMacroDefinition(node ast.Statement) bool {
    letStatement, ok := node.(*ast.LetStatement)
    if !ok {
        return false
    }
    _, ok = letStatement.Value.(*ast.MacroLiteral)
    if !ok {
        return false
    }

    return true
}

// 将宏定义绑定到env
func addMacro(stmt ast.Statement, env *object.Environment) {
    letStatement, _ := stmt.(*ast.LetStatement)
    macroLiteral, _ := letStatement.Value.(*ast.MacroLiteral)

    macro := &object.Macro{
        Parameters: macroLiteral.Parameters,
        Env:        env,
        Body:       macroLiteral.Body,
    }

    env.Set(letStatement.Name.Value, macro)
}

测试

// evaluator/macro_expansion_test.go
package evaluator

import (
    "malang/ast"
    "malang/lexer"
    "malang/object"
    "malang/parser"
    "testing"
)

func TestDefineMacros(t *testing.T) {
    input := `
    let number = 1;
    let function = fn(x, y) { x + y };
    let mymacro = macro(x, y) { x + y; };
    `

    env := object.NewEnvironment()
    program := testParseProgram(input)

    DefineMacros(program, env)

    if len(program.Statements) != 2 {
        t.Fatalf("Wrong number of statements. got=%d", len(program.Statements))
    }

    _, ok := env.Get("number")
    if ok {
        t.Fatalf("number should not be defined")
    }
    _, ok = env.Get("function")
    if ok {
        t.Fatalf("function should not be defined")
    }

    obj, ok := env.Get("mymacro")
    if !ok {
        t.Fatalf("macro not in environment")
    }

    macro, ok := obj.(*object.Macro)
    if !ok {
        t.Fatalf("object is not Macro. got=%T (%+v)", obj, obj)
    }

    if len(macro.Parameters) != 2 {
        t.Fatalf("Wrong number of macro parameters. got=%d", len(macro.Parameters))
    }

    if macro.Parameters[0].String() != "x" {
        t.Fatalf("parameter is not 'x'. got=%q", macro.Parameters[0])
    }

    if macro.Parameters[1].String() != "y" {
        t.Fatalf("parameter is not 'y'. got=%q", macro.Parameters[1])
    }

    expectedBody := "(x + y)"

    if macro.Body.String() != expectedBody {
        t.Fatalf("body is not %q. got=%q", expectedBody, macro.Body.String())
    }
}

func testParseProgram(input string) *ast.Program {
    l := lexer.New(input)
    p := parser.New(l)
    return p.ParseProgram()
}

5.5.4 展开宏

宏展开意味着对宏的调用求值，并将求值结果重新插回 AST 中替换原始的调用表达式

和 unquote 的工作方式非常接近，unquote 调用中只有其中的单个参数会被求值，而宏调用需要对宏的主体求值，还要让参数在环境中可用

ExpandMacros 用 ast.Modify 来遍历 AST，查找宏调用，然后对宏调用表达式求值

ExpandMacros 接受参数，并在 quoteArgs 的帮助下将他们转换为*object.Quote。然后使用 extendMacroEnv 来扩展宏的环境，并将调用的参数绑定到宏字面量的参数名称中。

现在参数处于已引用状态，环境也扩展了，接下来 ExpandMacros 使用 Eval 来对传入的新环境的宏主体求值。ExpandMacros 返回已引用的 AST 节点作为求值结果。因此该函数不是修改节点，而是用求值结果替换了宏调用，也就是展开了宏

// evaluator/macro_expansion.go
// 展开宏
func ExpandMacros(program ast.Node, env *object.Environment) ast.Node {
    return ast.Modify(program, func(node ast.Node) ast.Node {
        callExpression, ok := node.(*ast.CallExpression)
        if !ok {
            return node
        }

        macro, ok := isMacroCall(callExpression, env)
        if !ok {
            return node
        }

        args := quoteArgs(callExpression)
        evalEnv := extendMacroEnv(macro, args)

        evaluated := Eval(macro.Body, evalEnv)

        quote, ok := evaluated.(*object.Quote)
        if !ok {
            panic("we only support returning AST-nodes from macros ")
        }

        return quote.Node
    })
}

func isMacroCall(
    exp *ast.CallExpression,
    env *object.Environment,
) (*object.Macro, bool) {
    identifier, ok := exp.Function.(*ast.Identifier)
    if !ok {
        return nil, false
    }

    obj, ok := env.Get(identifier.Value)
    if !ok {
        return nil, false
    }

    macro, ok := obj.(*object.Macro)
    if !ok {
        return nil, false
    }

    return macro, true
}

func quoteArgs(exp *ast.CallExpression) []*object.Quote {
    args := []*object.Quote{}

    for _, a := range exp.Arguments {
        args = append(args, &object.Quote{Node: a})
    }

    return args
}

func extendMacroEnv(
    macro *object.Macro,
    args []*object.Quote,
) *object.Environment {
    extended := object.NewEnclosedEnvironment(macro.Env)

    for paramIdx, param := range macro.Parameters {
        extended.Set(param.Value, args[paramIdx])
    }

    return extended
}

测试

// evaluator/macro_expansion_test.go
func TestExpandMacros(t *testing.T) {
    ts := []struct {
        input    string
        expected string
    }{
        {
            `
            let infixExpression = macro() { quote(1 + 2); };

            infixExpression();
            `,
            `(1 + 2)`,
        },
        {
            `
            let reverse = macro(a, b) { quote(unquote(b) - unquote(a)); };

            reverse(2 + 2, 10 - 5);
            `,
            `(10 - 5) - (2 + 2)`,
        },
    }
    for _, tt := range ts {
        expected := testParseProgram(tt.expected)
        program := testParseProgram(tt.input)

        env := object.NewEnvironment()
        DefineMacros(program, env)
        expanded := ExpandMacros(program, env)

        if expanded.String() != expected.String() {
            t.Errorf("not equal. want=%q, got=%q", expected.String(), expanded.String())
        }
    }
}

5.5.5 强大的 unless 宏

unless 宏通常是所有介绍宏的资料中的第一个宏。因为它易于理解和实现，且可以演示宏系统的工作方式和目的。另外，还能展示普通函数的局限性和宏的优越性，让用户能够使用看起来像内置函数，但实际上是宏的结构来扩展编程语言

看看本书语言的 unless 演示

if (10 > 5) {
    puts("yes, 10 is greater than 5")
} else {
    puts("holy monkey, 10 is not greater than 5?!")
}

如果内置了 unless

unless (10 > 5) {
    puts("yes, 10 is greater than 5")
} else {
    puts("holy monkey, 10 is not greater than 5?!")
}

添加 unless 意味着：添加新的词法单元类型，修改词法分析器，使用新的解析函数扩展语法分析器以便构建新的表示 unless 表达式的 AST 节点，然后想 Eval 函数添加新的 case 分支来处理新的节点

但是现在已经有宏，不必再拓展 monkey 本身

unless(10 > 5, puts("nope, not greater"), puts("yep, greater"));
// 输出 yep greater

如果 unless 是普通函数，则参数里的 puts 会先求值，然后输出”nope, not greater”、”yep, greater”

我们来测试

func TestExpandMacros(t *testing.T) {
    // ...
        {
            `
            let unless = macro(condition, consequence, alternative) {
                quote(if (!(unquote(condition))){
                    unquote(consequence);
                } else {
                    unquote(alternative);
                });
            };

            unless(10 > 5, puts("not greater"), puts("greater"));
            `,
            `if (!(10 > 5)) { puts("not greater") } else { puts("greater") }`,
        },
    // ...
}

5.6 扩展 REPL

为 REPL 添加一个仅供宏使用的独特环境

func Start(in io.Reader, out io.Writer) {
    scanner := bufio.NewScanner(in)
    env := object.NewEnvironment()
    macroEnv := object.NewEnvironment()
    io.WriteString(out, MALRED_LOGO)
    // 加载标准库
    std := util.LoadStd()
    l := lexer.New(std)
    p := parser.New(l)
    program := p.ParseProgram()
    evaluator.Eval(program, env)

    for {
        fmt.Fprintf(out, PROMPT)
        scanned := scanner.Scan()
        if !scanned {
            return
        }

        line := scanner.Text()
        l := lexer.New(line)
        p := parser.New(l)

        program := p.ParseProgram()
        if len(p.Errors()) != 0 {
            printParserErrors(out, p.Errors())
            continue
        }

        evaluator.DefineMacros(program, macroEnv)
        expanded := evaluator.ExpandMacros(program, macroEnv)

        // evaluated := evaluator.Eval(expanded, env)
        evaluated := evaluator.Eval(expanded, env)

        if evaluated != nil {
            io.WriteString(out, evaluated.Inspect())
            io.WriteString(out, "\n")
        }
    }
}

5.7 关于宏的一些畅想

宏系统可以做很神奇的事情，比如编写用来生成代码的代码

待改进：缺乏对错误处理和调试的支持、卫生宏（macro hygiene）

目前只能将表达式传递给 quote 和 unquote，不能在 quote 调用中使用 return 或 let

如果将 quote 和 unquote 分别使用单独的关键字并生成自己的 AST 节点，则可以在任意调用中使用任意 AST 节点作为参数，拓展语法分析器。可以传入表达和语句。

如果可以将块语句传给 quote/unquote 调用，就可以

quote() {
    let one = 1;
    let two = 2;
    one + two;
}

如果函数调用的参数不需要括号？如果标识符可以包含特殊符字符？如果标识符可以解析为自身？如果每个函数可以接受一个额外的*ast.BlockStatement 作为参数？……

关键在于，语法分析器给出的规则决定了什么是有效的语法，也很大程度上影响宏的表现力和能力。修改这些规则就同时改变了宏的功能。

另一个对宏系统的功能有重大影响的是其访问、修改、构建 AST 节点的能力。比如有 left 和 right 可以分别返回 AST 节点的左右子节点

let plusToMinus = macro(infixExpression) {
    quote(unquote(left(infixExpression)) - unquote(right(infixExpression)))
}

最终畅想：如果 AST 是用与该语言其他部分相同的数据结构来构建的，会如何，比如 AST 完全用 object 的 Array、Hash、String、Integer 构建

赏

  转载请注明: malred-blog 用go语言实现解释器

  目录