前一篇用 dataclass 手工创建了一个表达式：

1
program = Add(Number(1), Add(Number(2), Number(3)))

这已经能演示解释器的基本形状，但它还绕开了一个关键步骤。真实程序通常从文本开始。读者写下的是 x + (2 + y) + 3，解释器需要先把这段文本变成结构化对象，后面的求值规则才有东西可操作。

本文做这件事：写一个很小的 tokenizer 和 parser，把字符串转成 AST（Abstract Syntax Tree，抽象语法树），再对 AST 求值。

程序文本进入系统后的三步

一段源码进入解释器后，可以先粗略拆成三步：

1
source text -> tokens -> AST -> value

source text 是原始字符串。tokens 是词法单元列表，比如数字、变量名、加号、括号。AST 是语法结构，表达“谁和谁相加”“括号包住哪一段”。value 是执行结果。

本文只实现一个小语言。它支持整数、变量、加法和括号：

1
2
3
1 + 2
x + 3
x + (2 + y) + 3

语法规则也保持很小：

1
2
expression = term ("+" term)*
term       = NUMBER | NAME | "(" expression ")"

这两行已经足够支撑一个递归下降 parser。读者熟悉 Java 的话，可以把它理解成手写版的“解析器前端”：先把字符串切成 token，再按语法规则组装对象。

AST 节点

先定义三种节点：数字、变量、加法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from dataclasses import dataclass


@dataclass(frozen=True)
class Number:
    value: int


@dataclass(frozen=True)
class Variable:
    name: str


@dataclass(frozen=True)
class Add:
    left: "Expression"
    right: "Expression"


Expression = Number | Variable | Add

Number(3) 表示数字字面量。Variable("x") 表示变量引用。Add(left, right) 表示加法表达式。

这样的定义有一个好处：程序结构可以直接打印、比较、传递。字符串 x + 3 进入 parser 后，会变成：

1
Add(Variable("x"), Number(3))

这时程序已经离开文本层，进入结构层。后面的解释器只需要处理 Number、Variable、Add 这几种节点。

模式提炼：文本层和结构层

text -> tokens -> nodes

很多工程系统都有同样分层。配置文件、SQL、表达式引擎、模板语言、规则 DSL 都会先把文本切成词，再组装成结构。文本适合人写，结构适合程序分析。

层次 适合谁 典型操作
文本 人 编写、阅读、复制
token parser 识别数字、标识符、符号
AST 解释器 / 编译器 求值、检查、优化、转换

Token 是更小的积木

tokenizer 负责把字符串切成词法单元。比如：

1
x + (2 + y)

会被切成：

1
NAME(x), +, (, NUMBER(2), +, NAME(y), ), EOF

先定义 token：

1
2
3
4
@dataclass(frozen=True)
class Token:
    type: str
    value: str

然后写 tokenizer：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import re


TOKEN_PATTERN = re.compile(r"\s*(?:(\d+)|([A-Za-z_]\w*)|(.))")


def tokenize(text: str) -> list[Token]:
    tokens = []

    for number, name, other in TOKEN_PATTERN.findall(text):
        if number:
            tokens.append(Token("NUMBER", number))
        elif name:
            tokens.append(Token("NAME", name))
        elif other in "+()":
            tokens.append(Token(other, other))
        else:
            raise SyntaxError(f"unexpected character: {other!r}")

    tokens.append(Token("EOF", ""))
    return tokens

这段 tokenizer 做了四件事：

  • 跳过空白。
  • 把连续数字识别成 NUMBER。
  • 把变量名识别成 NAME。
  • 把 +、(、) 保留为独立 token。

EOF 是输入结束标记。parser 读到它时，就知道后面没有内容了。

可以先跑一下：

1
print(tokenize("x + (2 + y)"))

输出类似：

1
[Token(type='NAME', value='x'), Token(type='+', value='+'), Token(type='(', value='('), Token(type='NUMBER', value='2'), Token(type='+', value='+'), Token(type='NAME', value='y'), Token(type=')', value=')'), Token(type='EOF', value='')]

Parser 按语法规则前进

parser 的任务是消费 token，并组装 AST。它像一个带游标的对象，始终看着当前位置的 token。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Parser:
    def __init__(self, tokens: list[Token]):
        self.tokens = tokens
        self.position = 0

    def current(self) -> Token:
        return self.tokens[self.position]

    def consume(self, token_type: str) -> Token:
        token = self.current()

        if token.type != token_type:
            raise SyntaxError(f"expected {token_type}, got {token.type}")

        self.position += 1
        return token

current() 查看当前 token。consume() 检查当前 token 是否符合预期，符合就前进一步。

接下来把语法规则翻译成方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def parse(self) -> Expression:
    expression = self.expression()
    self.consume("EOF")
    return expression

def expression(self) -> Expression:
    expression = self.term()

    while self.current().type == "+":
        self.consume("+")
        expression = Add(expression, self.term())

    return expression

def term(self) -> Expression:
    token = self.current()

    if token.type == "NUMBER":
        return Number(int(self.consume("NUMBER").value))

    if token.type == "NAME":
        return Variable(self.consume("NAME").value)

    if token.type == "(":
        self.consume("(")
        expression = self.expression()
        self.consume(")")
        return expression

    raise SyntaxError(f"unexpected token: {token}")

这几段代码几乎逐字对应前面的语法：

1
2
expression = term ("+" term)*
term       = NUMBER | NAME | "(" expression ")"

expression() 先解析一个 term，然后只要后面还有加号，就继续读下一个 term，并把旧表达式和新 term 组合成 Add。这会让 1 + 2 + 3 形成左结合结构：

1
Add(Add(Number(1), Number(2)), Number(3))

term() 处理三种情况：数字、变量、括号。括号里又是一整个 expression，所以它会递归调用 expression()。

外面再包一层便捷函数：

1
2
def parse(text: str) -> Expression:
    return Parser(tokenize(text)).parse()

求值需要环境

数字可以直接求值，加法可以递归求值，变量需要一个环境。环境就是变量名到值的映射。

1
2
3
4
5
6
7
8
9
10
def evaluate(expression: Expression, environment: dict[str, int]) -> int:
    match expression:
        case Number(value):
            return value
        case Variable(name):
            return environment[name]
        case Add(left, right):
            return evaluate(left, environment) + evaluate(right, environment)
        case _:
            raise TypeError(f"unknown expression: {expression!r}")

现在可以把文本、AST、求值串起来：

1
2
3
4
program = parse("x + (2 + y) + 3")

print(program)
print(evaluate(program, {"x": 10, "y": 5}))

输出：

1
2
Add(left=Add(left=Variable(name='x'), right=Add(left=Number(value=2), right=Variable(name='y'))), right=Number(value=3))
20

第一行是 AST。第二行是求值结果。变量 x 从环境里取到 10，变量 y 取到 5，整个表达式得到 20。

模式提炼：语法规则和运行环境分离

parse(text) -> AST
evaluate(AST, environment) -> value

parser 只关心文本结构，求值器才关心变量值。把这两件事拆开以后，同一棵 AST 可以在不同环境下求值。

1
2
3
4
program = parse("x + 1")

print(evaluate(program, {"x": 1}))
print(evaluate(program, {"x": 100}))

输出：

1
2
2
101

这就是环境的作用。程序结构固定，环境改变，结果随之改变。后面讲变量、赋值和小步语义时，这个分离会继续出现。

完整代码

下面是完整文件，可以保存为 tiny_ast.py 直接运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
from dataclasses import dataclass
import re


@dataclass(frozen=True)
class Number:
    value: int


@dataclass(frozen=True)
class Variable:
    name: str


@dataclass(frozen=True)
class Add:
    left: "Expression"
    right: "Expression"


Expression = Number | Variable | Add


@dataclass(frozen=True)
class Token:
    type: str
    value: str


TOKEN_PATTERN = re.compile(r"\s*(?:(\d+)|([A-Za-z_]\w*)|(.))")


def tokenize(text: str) -> list[Token]:
    tokens = []

    for number, name, other in TOKEN_PATTERN.findall(text):
        if number:
            tokens.append(Token("NUMBER", number))
        elif name:
            tokens.append(Token("NAME", name))
        elif other in "+()":
            tokens.append(Token(other, other))
        else:
            raise SyntaxError(f"unexpected character: {other!r}")

    tokens.append(Token("EOF", ""))
    return tokens


class Parser:
    def __init__(self, tokens: list[Token]):
        self.tokens = tokens
        self.position = 0

    def current(self) -> Token:
        return self.tokens[self.position]

    def consume(self, token_type: str) -> Token:
        token = self.current()

        if token.type != token_type:
            raise SyntaxError(f"expected {token_type}, got {token.type}")

        self.position += 1
        return token

    def parse(self) -> Expression:
        expression = self.expression()
        self.consume("EOF")
        return expression

    def expression(self) -> Expression:
        expression = self.term()

        while self.current().type == "+":
            self.consume("+")
            expression = Add(expression, self.term())

        return expression

    def term(self) -> Expression:
        token = self.current()

        if token.type == "NUMBER":
            return Number(int(self.consume("NUMBER").value))

        if token.type == "NAME":
            return Variable(self.consume("NAME").value)

        if token.type == "(":
            self.consume("(")
            expression = self.expression()
            self.consume(")")
            return expression

        raise SyntaxError(f"unexpected token: {token}")


def parse(text: str) -> Expression:
    return Parser(tokenize(text)).parse()


def evaluate(expression: Expression, environment: dict[str, int]) -> int:
    match expression:
        case Number(value):
            return value
        case Variable(name):
            return environment[name]
        case Add(left, right):
            return evaluate(left, environment) + evaluate(right, environment)
        case _:
            raise TypeError(f"unknown expression: {expression!r}")


if __name__ == "__main__":
    program = parse("x + (2 + y) + 3")

    print(program)
    print(evaluate(program, {"x": 10, "y": 5}))

运行：

1
python tiny_ast.py

输出：

1
2
Add(left=Add(left=Variable(name='x'), right=Add(left=Number(value=2), right=Variable(name='y'))), right=Number(value=3))
20

Java 程序员的迁移表

Python 组件 Java 对照 作用
Token record Token(TokenType type, String value) 词法单元
Parser.position parser 游标字段 记录读到哪里
consume() expect(TokenType type) 检查并推进 token
expression() 递归下降方法 按语法规则组装 AST
`Number Variable Add`
environment: dict[str, int] Map<String, Integer> 变量绑定表

Java 里通常会把 TokenType 写成 enum，把 parser 拆成多个文件，再给错误信息带上行列号。本文先把这些工程细节压低，保留解析器的骨架。

常见误解

第一个误解是把 AST 当成字符串的漂亮包装。AST 的价值在结构。x + (2 + y) 里的括号不会作为普通字符留在 AST 里；它影响的是树的形状。树形一旦确定，求值器只看节点关系。

第二个误解是把 parser 和 evaluator 混在一起写。小实验里确实可以边读边算，但《计算的本质》后面要比较小步语义、大步语义和指称语义。拆成 AST 后，同一份程序结构可以交给不同语义规则解释。

第三个误解是把变量值塞进 AST。Variable("x") 保存的是变量名，10 来自环境。程序结构和运行时绑定分开，才能解释“同一段程序在不同环境下得到不同结果”。

练习

第一，给语言增加乘法。目标是让 2 + 3 * 4 输出 14，并让 * 的优先级高于 +。提示：把语法改成：

1
2
3
4
expression = addition
addition   = multiplication ("+" multiplication)*
multiplication = term ("*" term)*
term       = NUMBER | NAME | "(" expression ")"

第二，给 tokenizer 增加减号 -，并实现二元减法节点 Subtract。

第三，把 SyntaxError 的错误信息改得更具体。比如输入 x + ) 时，报出当前 token 和当前位置。

下一篇进入求值规则。现在已经有 AST，接下来可以写两种解释器：一种直接求出结果，另一种每次只把程序推进一步。大步语义和小步语义的差异会从代码里显出来。

参考资料