如何用 Go 编写词法分析器

词法分析器是所有现代编译器的第一阶段，但是如何编写呢？让我们用 Go 从头开始构建一个。

什么是词法分析器？

词法分析器有时也称为扫描器，它读取源程序并将输入转换为标记流。这是编译过程中非常重要的一步，因为解析器使用这些标记来创建 AST（抽象语法树）。如果你不熟悉解析器和 AST 也不用担心，这篇文章将只专注于构建词法分析器。

词法分析器实战

在我们编写自己的词法分析器之前，让我们看一下 Go 的词法分析器，以便更好地了解“标记”的含义。你可以使用 Go 的 scanner package 来仔细查看 Go 的词法分析器到底发出了什么标记。这个 文档 中有实现这一点的示例。这是我们测试 scanner 的程序：

main.go

package main

import "fmt"

func main() {
    fmt.Println("Hello world!")
}

这是发出的标记：

输出

1:1     package "package"
1:9     IDENT    "main"
1:13    ;        "\n"
3:1        import    "import"
3:8        STRING  "\"fmt\""
3:13    ;        "\n"
5:1        func    "func"
5:6        IDENT    "main"
5:10    (        ""
5:11    )        ""
5:13    {        ""
6:2        IDENT    "fmt"
6:5        .        ""
6:6        IDENT    "Println"
6:13    (        ""
6:14    STRING    "\"Hello world!\""
6:28    )        ""
6:29    ;        "\n"
7:1        }        ""
7:2        ;        "\n"

第一列包含标记的位置，第二列是标记的类型，最后一列是标记的字面值。这里有一些重要的事情需要注意。首先，词法分析器不发出任何制表符或空格。这是因为 Go 的语法并不依赖于这些东西。另一件需要注意的事情是 IDENT 标记。基本上，在 Go 中任何不是关键字的东西都将被标记为标识符，伴随的字符串将被标记为字面值。

如果你想知道这些标记为什么有用，那是因为它们以解析器能够理解的方式表示源程序！

语言

现在我们已经在实践中了解了词法分析器，让我们从头开始构建自己的词法分析器！我们首先需要为编程语言定义语法。为简单起见，只包括一些不同的东西：

program → expr*

expr → assignment | infixExpr | int

assignment → id = expr ;

infixExp → expr infixOp expr ;

infixOp → + | - | \ | /*

任何粗体被称为 terminal，意味着它不能被进一步扩展。在构建词法分析器时，terminals 在构建词法分析器时非常重要，稍后我们将看到这一点。语法可以这样读取：

程序是零个或多个表达式组成的列表。表达式可以是赋值、中缀表达式或整数等等。

在构建解析器时，语法变得更加重要，但是现在定义语法很重要，这样才能知道词法分析器应该发出哪些标记！

标记

上面的语法使我们可以定义词法分析器在扫描时应发出的标记。标记只是 terminals！我们还将包括一个 EOF 和 ILLEGAL 标记，以便分别表示程序的结束和语言中不合法的字符。

lexer.go

type Token int

const (
    EOF = iota
    ILLEGAL
    IDENT
    INT
    SEMI // ;

    // 中缀操作
    ADD // +
    SUB // -
    MUL // *
    DIV // /

    ASSIGN // =
)

var tokens = []string{
    EOF:     "EOF",
    ILLEGAL: "ILLEGAL",
    IDENT:   "IDENT",
    INT:     "INT",
    SEMI:    ";",

    // 中缀操作
    ADD: "+",
    SUB: "-",
    MUL: "*",
    DIV: "/",

    ASSIGN: "=",
}

func (t Token) String() string {
    return tokens[t]
}

扫描输入

现在我们准备扫描源程序并发出一些标记！首先，我们将创建一个保留某些状态的 Lexer 结构：

lexer.go

type Position struct {
    line   int
    column int
}

type Lexer struct {
    pos    Position
    reader *bufio.Reader
}

func NewLexer(reader io.Reader) *Lexer {
    return &Lexer{
        pos:    Position{line: 1, column: 0},
        reader: bufio.NewReader(reader),
    }
}

调用者需要创建带有适当源文件的 reader，并在创建 Lexer 时将其作为参数传递。

接下来，添加一个每次返回单个标记的 Lex 函数。然后，调用者将能够连续调用 Lex，直到返回 EOF 标记。首先，处理输入文件末尾的情况。

lexer.go

// Lex 扫描输入中的下一个标记。返回标记的位置，标记的类型和字面值。
func (l *Lexer) Lex() (Position, Token, string) {
    // 循环直到返回一个标记为止
    for {
        r, _, err := l.reader.ReadRune()
        if err != nil {
            if err == io.EOF {
                return l.pos, EOF, ""
            }

            // 在这一点上我们无能为力，编译器应该将原始错误返回给用户
            panic(err)
        }
    }
}

然后，添加一些逻辑来处理语法中的一些更基本的 terminals。我们可以使用 switch 语句来检查是否遇到了以下 terminals 之一：

lexer.go

func (l *Lexer) Lex() (Position, Token, string) {
    // 循环直到返回一个标记位置
    for {
        …
        // 将列更新为新读取的字符的位置
        l.pos.column++

        switch r {
        case '\n':
            l.resetPosition()
        case ';':
            return l.pos, SEMI, ";"
        case '+':
            return l.pos, ADD, "+"
        case '-':
            return l.pos, SUB, "-"
        case '*':
            return l.pos, MUL, "*"
        case '/':
            return l.pos, DIV, "/"
        case '=':
            return l.pos, ASSIGN, "="
        default:
            if unicode.IsSpace(r) {
                continue
            }
        }
    }
}

func (l *Lexer) resetPosition() {
    l.pos.line++
    l.pos.column = 0
}

这使我们可以对除标识符和整数之外的所有内容进行 lex，这非常简洁！接下来我们处理整数。我们需要检测是否看到了数字。如果有的话，扫描后面剩下的数字来标记这个整数。

lexer.go

func (l *Lexer) Lex() (Position, Token, string) {
    // 循环直到返回一个标记为止
    for {
        …
        switch r {
        …
        default:
            if unicode.IsSpace(r) {
                continue
            } else if unicode.IsDigit(r) {
                // 备份并让 lexInt 重新扫描 int 的开头
                startPos := l.pos
                l.backup()
                lit := l.lexInt()
                return startPos, INT, lit
            }
        }
    }
}

func (l *Lexer) backup() {
    if err := l.reader.UnreadRune(); err != nil {
        panic(err)
    }

    l.pos.column--
}

// lexInt 扫描输入直到整数的结尾，然后返回字面值。
func (l *Lexer) lexInt() string {
    var lit string
    for {
        r, _, err := l.reader.ReadRune()
        if err != nil {
            if err == io.EOF {
                return lit
            }
        }

        l.pos.column++
        if unicode.IsDigit(r) {
            lit = lit + string(r)
        } else {
            // 不是整型
            l.backup()
            return lit
        }
    }
}

如你所见，lexInt 仅扫描所有连续的数字，然后返回字面值。处理标识符可以用类似的方式完成，但是，我们应该定义标识符中哪些字符有效。对于我们的语言，我们只允许使用大写和小写字母，其他所有内容都应视为 ILLEGAL 标记。

lexer.go

// Lex 扫描输入中的下一个标记。它返回标记的位置，标记的类型和字面值。
func (l *Lexer) Lex() (Position, Token, string) {
    // 循环直到返回一个标记为止
    for {
        ...
        switch r {
        ...
        default:
            if unicode.IsSpace(r) {
                continue
            } else if unicode.IsDigit(r) {
                // 备份并让 lexInt 重新扫描 int 的开头
                startPos := l.pos
                l.backup()
                lit := l.lexInt()
                return startPos, INT, lit
            } else if unicode.IsLetter(r) {
                // 备份并让 lexIdent 重新扫描 ident 的开头
                startPos := l.pos
                l.backup()
                lit := l.lexIdent()
                return startPos, IDENT, lit
            } else {
                return l.pos, ILLEGAL, string(r)
            }
        }
    }
}

// lexIdent 扫描输入，直到标识符结尾，然后返回字面值。
func (l *Lexer) lexIdent() string {
    var lit string
    for {
        r, _, err := l.reader.ReadRune()
        if err != nil {
            if err == io.EOF {
                // 到达标识符末尾
                return lit
            }
        }

        l.pos.column++
        if unicode.IsLetter(r) {
            lit = lit + string(r)
        } else {
            // 扫描到标识符中没有的东西
            l.backup()
            return lit
        }
    }
}

请务必注意，词法分析不会捕获诸如未定义的变量或无效的语法之类的错误。它唯一关心的是词法正确性（即我们的语言中允许使用的字符）。下面是运行词法分析器并查看输出的方法：

lexer.go

func main() {
    file, err := os.Open("input.test")
    if err != nil {
        panic(err)
    }

    lexer := NewLexer(file)
    for {
        pos, tok, lit := lexer.Lex()
        if tok == EOF {
            break
        }

        fmt.Printf("%d:%d\t%s\t%s\n", pos.line, pos.column, tok, lit)
    }
}

如果通过运行 go run lexer.go 并使用以下输入运行我们的词法分析器，你将看到发出了标记！

input.test

a = 5;
b = a + 6;
c + 123;
5+12;

输出

1:1     IDENT    a
1:3        =        =
1:5        INT        5
1:6        ;        ;
2:1        IDENT    b
2:3        =        =
2:5        IDENT    a
2:7        +        +
2:9        INT        6
2:10    ;        ;
3:1        IDENT    c
3:3        +        +
3:5        INT        123
3:8        ;        ;
4:1        INT        5
4:2        +        +
4:3        INT        12
4:5        ;        ;

希望你能从这篇文章中学到一些东西，我也很乐意在评论区听到你的反馈。这篇文章的所有代码都可以在我的 GitHub 上找到。里面还包含我未介绍的单元测试。