用Go语言自制解释器
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

1.3　词法分析器

在开始编写代码之前，先了解本节的目标。在本节中，我们将编写词法分析器。词法分析器将源代码作为输入，并输出对应的词法单元。词法分析器会遍历输入的字符，然后逐个输出识别出的词法单元。这个过程既无须用到缓冲区，也无须保存词法单元，只会用到一个名为NextToken()的方法来输出下一个词法单元。

也就是说，词法分析器在接收源代码之后，会在其中重复调用NextToken()，逐个字符遍历源代码来生成词法单元。这里的源代码还是使用字符串，因此可以省去不少处理工作。再次提醒，在生产环境中，应该将文件名和行号附加到词法单元中，以便更好地跟踪可能出现的词法分析错误和语法分析错误。在这种情况下，最好使用io.Reader加上文件名来初始化词法分析器。但因为这样做会增加复杂性，所以这里从简单处着手，仅使用字符串作为输入，忽略文件名和行号。

经过这些分析，现在词法分析器的任务就很清楚了。接下来创建一个新语言包并添加第一个测试。测试可以重复运行，以获取词法分析器当前的工作状态信息。这里依然从简单处着手，后面随着词法分析器功能的完善，测试用例也会随之扩展：

// lexer/lexer_test.go

package lexer

import (
    "testing"

    "monkey/token"
)

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
# monkey/lexer
lexer/lexer_test.go:27: undefined: New
FAIL    monkey/lexer [build failed]

首先，定义New()函数，用来返回*Lexer。

// lexer/lexer.go
package lexer

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

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

Lexer中的大多数字段很容易理解，但position和readPosition的含义可能让人困惑。两者都可以用作索引来访问input中的字符，例如l.input[l.readPosition]。这里之所以用两个“指针”来指向所输入的字符串，是因为词法分析器除了查看当前字符，还需要进一步“查看”字符串，即查看字符串中的下一个字符。readPosition始终指向所输入字符串中的“下一个”字符，position则指向所输入字符串中与ch字节对应的字符。

第一个辅助方法是readChar()，读懂这个方法就能理解这些字段了：

// lexer/lexer.go

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

readChar的目的是读取input中的下一个字符，并前移其在input中的位置。这个过程的第一件事就是检查是否已经到达input的末尾。如果是，则将l.ch设置为0，这是NUL字符的ASCII编码，用来表示“尚未读取任何内容”或“文件结尾”。如果还没有到达input的末尾，则将l.ch设置为下一个字符，即l.input[l.readPosition]指向的字符。

之后，将l.position更新为刚用过的l.readPosition，然后将l.readPosition加1。这样一来，l.readPosition就始终指向下一个将读取的字符位置，而l.position始终指向刚刚读取的位置。这个特性很快就会派上用场。

在谈到readChar时，值得指出的是，该词法分析器仅支持ASCII字符，不能支持所有的Unicode字符。这么做也是为了让事情保持简单，让我们能够专注于解释器的基础部分。如果要完全支持Unicode和UTF-8，就要将l.ch的类型从byte改为rune，同时还要修改读取下一个字符的方式。因为字符此时可能为多字节，所以l.input[l.readPosition]将无法工作。除此之外，还需要修改其他一些后面会介绍的方法和函数。这里将在Monkey中全面支持Unicode和表情符号作为练习留给读者来实现。

在New()函数中使用readChar，初始化l.ch、l.position和l.readPosition，以便在调用NextToken()之前让*Lexer完全就绪：

// lexer/lexer.go

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

此时运行测试会发现，调用New(input)后一切正常，但现在还缺少NextToken()方法。下面就通过添加第一版的NextToken()来解决这个问题：

// lexer/lexer.go

package lexer

import "monkey/token"

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
}

func newToken(tokenType token.TokenType, ch byte) token.Token {
    return token.Token{Type: tokenType, Literal: string(ch)}
}

这就是NextToken()方法的基本结构。它首先检查了当前正在查看的字符l.ch，根据具体的字符来返回对应的词法单元。在返回词法单元之前，位于所输入字符串中的指针会前移，所以之后再次调用NextToken()时，l.ch字段就已经更新过了。最后，名为newToken的小型函数可以帮助初始化这些词法单元。

运行测试，可以看到测试通过：

$ go test ./lexer
ok      monkey/lexer 0.007s

很好！现在来扩展测试用例，让其开始处理Monkey源代码：

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

    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, ""},
    }
// [...]
}

注意，现在测试用例中的input发生了变化，看起来像是Monkey语言的子集。它不仅包含所有已经能成功转换成词法单元的符号，还有一些新内容，如标识符、关键字和数字。这些新内容会导致测试失败。

先处理标识符和关键字。对于这两者，词法分析器需要识别当前字符是否为字母。如果是，则还需要读取标识符/关键字的剩余部分，直到遇见非字母字符为止。读取完该标识符/关键字之后，还需要判断它到底是标识符还是关键字，以便使用正确的token.TokenType。因此第一步是扩展switch语句：

// lexer/lexer.go

import "monkey/token"

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

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

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

func isLetter(ch byte) bool {
    return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_'
}

这里的switch语句中添加了一个default分支，因此只要l.ch不是前面可识别的字符，就可以检查是不是标识符了。这里还添加了用于生成token.ILLEGAL词法单元的代码。如果代码走到此处，就将不知道如何处理的字符声明成类型为token.ILLEGAL的词法单元。

isLetter辅助函数用来判断给定的参数是否为字母。值得注意的是，这个函数虽然看起来简短，但意义重大，其决定了解释器所能处理的语言形式。比如示例中包含ch =='_'，这意味着下划线_会被视为字母，允许在标识符和关键字中使用。因此可以使用诸如foo_bar之类的变量名。其他编程语言甚至允许在标识符中使用问号和感叹号。如果读者也想这么做，那么可以修改这个isLetter函数。

readIdentifier()函数顾名思义，就是读入一个标识符并前移词法分析器的扫描位置，直到遇见非字母字符。

在switch语句的default分支中，使用readIdentifier()设置了当前词法单元的Literal字段，但Type还没有处理。现在let、fn或foobar之类的标识符已经被读取，还需要将语言的关键字和用户定义标识符区分开来，因此需要一个函数来为现有的词法单元字面量返回正确的TokenType。添加这个函数最合适的地方是在token包中。

// token/token.go

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

func LookupIdent(ident string) TokenType {
    if tok, ok := keywords[ident]; ok {
        return tok
    }
    return IDENT
}

LookupIdent通过检查关键字表来判断给定的标识符是否是关键字。如果是，则返回关键字的TokenType常量。如果不是，则返回token.IDENT，这个TokenType表示当前是用户定义的标识符。

有了这些，现在就可以完成标识符和关键字的词法分析了：

// lexer/lexer.go

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)
        }
    }
// [...]
}

这里需要用return tok语句提前退出，因为在调用readIdentifier()时会重复调用readChar()，并将readPosition和position字段前移到当前标识符的最后一个字符之后，所以无须在后续的switch语句中再次调用readChar()。

现在运行测试，可以看到let被正确识别了，但是测试仍然失败：

$ go test ./lexer
--- FAIL: TestNextToken (0.00s)
  lexer_test.go:70: tests[1] - tokentype wrong. expected="IDENT", got="ILLEGAL"
FAIL
FAIL    monkey/lexer 0.008s

问题出在下一个词法单元上：原本预期是IDENT词法单元，其Literal字段中是five，而这里得到的是ILLEGAL词法单元。出现这种情况是因为let和five之间有空白字符。在 Monkey 语言中，空白字符仅用作词法单元的分隔符，没有任何意义，因此需要添加代码直接跳过空白：

// lexer/lexer.go

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

    l.skipWhitespace()

    switch l.ch {
// [...]
}

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

很多分析器中有这个简单的辅助函数，它有时称为eatWhitespace，有时称为consumeWhiteSpace，还有时是完全不同的名称。这个函数实际跳过的字符根据具体分析的语言会有所不同。例如在某些语言的实现中，会为换行符创建词法单元，如果它们不在词法单元流中的正确位置，就会抛出解析错误。不过这里没有处理换行符，是为了简化后面的语法分析步骤。

添加了skipWhitespace()后，词法分析器会停在测试代码中let five = 5;的5这里。是的，词法分析器还不能将数字转换为词法单元。现在来添加这个功能。

就像之前处理标识符那样，现在需要在switch语句的default分支中添加更多功能：

// lexer/lexer.go

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)
            return tok
        } else if isDigit(l.ch) {
            tok.Type = token.INT
            tok.Literal = l.readNumber()
            return tok
        } else {
            tok = newToken(token.ILLEGAL, l.ch)
        }
    }
// [...]
}

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

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

从中可以看到，刚刚添加的代码和上面读取标识符和关键字的代码很像。readNumber方法与readIdentifier几乎完全相同，除了其中使用的是isDigit而不是isLetter。当然，也可以创建一个characteridentifying函数同时处理这两种情况，但为了简洁和易于理解，这里还是分开处理。

isDigit函数与isLetter一样简单，只是判断传入的内容是否为Latin字符集中0和9之间的数字。

添加完成后，测试就能通过了：

$ go test ./lexer
ok      monkey/lexer 0.008s

你是否注意到，readNumber中简化了很多处理？它只能读取整数，忽略了浮点数、十六进制数、八进制数，这也意味着 Monkey 语言不支持这些特性。当然，这样做的原因还是出于教学目的，所以限定了介绍内容的范围。

现在可以庆祝了，我们成功地将测试用例中的一段 Monkey 语言代码转换成了词法单元！

有了这次胜利，就能很容易地扩展词法分析器，来解析更多的 Monkey 源代码。

本周热推：
算法训练营：海量图解+竞赛刷题（入门篇）Visual Basic编程：从基础到实践（第2版）Android传感器开发与智能设备案例实战名师讲坛：Java微服务架构实战（SpringBoot+SpringCloud+Docker+RabbitMQ）Excel VBA活用范例实用手册（畅销升级版）
上一章目录下一章