编译世界初探：从一个简单的计算器解释器开始

当你第一次在计算器上输入 `3 + 5 * 2` 并看到结果 `13` 时，你可能从未想过这个简单的动作背后隐藏着一个复杂而精妙的世界。数字和运算符从键盘进入，经过一系列转换，最终变成内存中的数值和CPU的指令序列。这个过程，就是编译的雏形。它并非现代计算机的偶然产物，而是人类将抽象思维转化为机器可执行指令的必然路径。从巴比伦的泥板到ENIAC的插线板，从打孔卡片到交互式IDE，我们一直在追求更高效、更可靠地“翻译”人类意图。本章将带你亲手构建一个仅支持加减乘除的微型计算器解释器，见证一段源代码如何被剖析、理解并执行。这不仅是技术的演练，更是对“计算”本质的一次哲学探问：当我们说“计算”时，我们究竟在说什么？是符号的 Manipulation，还是意义的传递？通过这个小小的计算器，我们将窥见编译原理的宏大叙事——一个关于语言、规则与自动化的永恒故事。

1.1 第一个编译器：一个四则运算解释器的完整实现

让我们从零开始，用 Python 构建一个能够直接执行四则运算表达式的解释器。这个解释器将完成从字符流到数值结果的完整旅程，涵盖编译过程最核心的三个阶段：词法分析（Lexical Analysis）、语法分析（Syntax Analysis）和解释执行（Interpretation）。我们将采用递归下降解析（Recursive Descent Parsing）这一经典且直观的技术，因为它能最清晰地展现“结构识别”的思维过程。

1.1.1 问题定义与输入输出

我们的计算器需要处理如下形式的表达式：

• 整数常量（如 `42`, `-7`）
• 二元运算符：加法 `+`、减法 `-`、乘法 `*`、除法 `/`
• 支持括号 `()` 改变运算优先级
• 允许空白字符（空格、制表符、换行）随意出现

例如，输入字符串 `" 3 + 5 * (10 - 4) / 2 "` 应输出数值 `18.0`。注意，我们遵循标准的算术优先级：乘除优先于加减，括号内优先。

1.1.2 词法分析：将字符流转化为标记流

词法分析是编译过程的第一道关卡，其任务是将原始的字符序列（源代码）分割成有意义的词法单元（Token）。每个 Token 包含两个基本信息：类型（Type）和值（Literal Value）。对于我们的计算器，我们需要定义以下 Token 类型：

| Token 类型 | 正则表达式模式 | 示例值 | | :--- | :--- | :--- | | `INTEGER` | `[0-9]+` | `42`, `7` | | `PLUS` | `+` | `+` | | `MINUS` | `-` | `-` | | `MUL` | `\*` | `*` | | `DIV` | `/` | `/` | | `LPAREN` | `\(` | `(` | | `RPAREN` | `\)` | `)` | | `EOF` | (文件结束) | (无) |

我们编写一个 `Lexer` 类来执行此任务。其核心是一个指针，扫描输入字符串，根据当前字符匹配相应的正则模式，生成下一个 Token。空白字符将被跳过。

```python import re

class Token: def __init__(self, type, value): self.type = type # token 类型，如 'INTEGER', 'PLUS' self.value = value # token 的值，如 42, '+'

def __repr__(self): return f"Token({self.type}, {repr(self.value)})"

class Lexer:

定义 token 规格：类型 -> 正则表达式模式

TOKEN_SPEC = [ ('INTEGER', r'\d+'), # 整数 ('PLUS', r'\+'), # 加号 ('MINUS', r'-'), # 减号 ('MUL', r'\*'), # 乘号 ('DIV', r'/'), # 除号 ('LPAREN', r'\('), # 左括号 ('RPAREN', r'\)'), # 右括号 ('SKIP', r'\s+'), # 空白符（跳过） ]

def __init__(self, text): self.text = text self.pos = 0 # 当前扫描位置 self.current_token = None

def get_next_token(self): """从输入文本中获取下一个 token""" text = self.text

如果已到达末尾，返回 EOF token

if self.pos >= len(text): return Token('EOF', None)

尝试匹配所有 token 规格

for token_type, pattern in self.TOKEN_SPEC: regex = re.compile(pattern) match = regex.match(text, self.pos) if match: value = match.group(0) self.pos = match.end() # 移动指针

跳过空白符，不生成 token

if token_type == 'SKIP': return self.get_next_token()

对于 INTEGER，将字符串转换为整数

if token_type == 'INTEGER': value = int(value)

return Token(token_type, value)

如果没有任何模式匹配，则发生词法错误

raise Exception(f'非法字符在位置 {self.pos}: {text[self.pos]}') ```

关键思想：词法分析器本质上是一个有限状态自动机（Finite State Automaton）。每个正则表达式模式对应一个状态转移路径。例如，扫描到数字 `'3'` 后，状态会保持在“读取整数”模式，直到遇到非数字字符（如 `+`），才完成一个 `INTEGER` Token 的生成。这种“最长匹配”原则（如 `"123"` 应匹配为一个 `INTEGER` 而非三个 `INTEGER`）是词法分析的核心规则。

1.1.3 语法分析：构建抽象语法树（AST）

词法分析生成了扁平的 Token 序列，如 `[INTEGER(3), PLUS, INTEGER(5), MUL, INTEGER(2)]`。但这并未表达出运算符之间的结构关系（即 `5` 和 `2` 先乘，结果再与 `3` 加）。语法分析的使命就是从这线性序列中识别出嵌套的结构，并构建一棵能反映此结构的树——抽象语法树（Abstract Syntax Tree, AST）。

我们的表达式语法可以用上下文无关文法（Context-Free Grammar, CFG）描述。对于支持加减乘除和括号的表达式，一个经典的文法如下（采用巴科斯范式，BNF）：

``` expr : term ((PLUS | MINUS) term)* term : factor ((MUL | DIV) factor)* factor : INTEGER | LPAREN expr RPAREN ```

这个文法的精妙之处在于它自然体现了运算符优先级：

• `expr` 处理加减（低优先级）
• `term` 处理乘除（高优先级）
• `factor` 处理原子（整数或括号内的子表达式）

因此，`3 + 5 * 2` 会被解析为 `expr(term(3), PLUS, term(factor(5), MUL, factor(2)))`，其 AST 结构为：

```mermaid graph TD A[expr] --> B[term] A --> C[PLUS] A --> D[term] B --> E[factor] E --> F[INTEGER: 3] D --> G[factor] G --> H[INTEGER: 5] D --> I[MUL] D --> J[factor] J --> K[INTEGER: 2] ```

我们将编写一个 `Parser` 类，根据上述文法，以递归下降的方式实现解析器。每个非终结符（`expr`, `term`, `factor`）对应一个解析方法。解析器维护一个当前 Token 指针，并提供一个 `eat(token_type)` 方法用于“消耗”一个预期类型的 Token，否则报错。

```python class Parser: def __init__(self, lexer): self.lexer = lexer self.current_token = self.lexer.get_next_token()

def error(self, msg="语法错误"): raise Exception(msg)

def eat(self, token_type): """检查当前 token 类型，若匹配则消耗，否则报错""" if self.current_token.type == token_type: self.current_token = self.lexer.get_next_token() else: self.error(f"期望 {token_type}, 实际得到 {self.current_token.type}")

def factor(self): """factor : INTEGER | LPAREN expr RPAREN""" token = self.current_token if token.type == 'INTEGER': self.eat('INTEGER') return NumNode(token.value) # 创建数字节点 elif token.type == 'LPAREN': self.eat('LPAREN') node = self.expr() # 递归解析括号内的表达式 self.eat('RPAREN') return node else: self.error("期望整数或左括号")

def term(self): """term : factor ((MUL | DIV) factor)*""" node = self.factor()

while self.current_token.type in ('MUL', 'DIV'): token = self.current_token if token.type == 'MUL': self.eat('MUL') elif token.type == 'DIV': self.eat('DIV')

node = BinOpNode(left=node, op=token, right=self.factor())

return node

def expr(self): """expr : term ((PLUS | MINUS) term)*""" node = self.term()

while self.current_token.type in ('PLUS', 'MINUS'): token = self.current_token if token.type == 'PLUS': self.eat('PLUS') elif token.type == 'MINUS': self.eat('MINUS')

node = BinOpNode(left=node, op=token, right=self.term())

return node

def parse(self): """解析入口，返回 AST 根节点""" return self.expr()

定义 AST 节点类

class NumNode: """表示整数字面量的节点""" def __init__(self, value): self.value = value def __repr__(self): return f"Num({self.value})"

class BinOpNode: """表示二元运算的节点：左操作数、运算符、右操作数""" def __init__(self, left, op, right): self.left = left self.op = op # Token 对象，如 Token('PLUS', '+') self.right = right def __repr__(self): return f"BinOp({self.left}, {self.op.type}, {self.right})" ```

递归下降解析的思维模型：想象你正在阅读一个嵌套的数学表达式。你的眼睛（解析器）从左向右移动。当你看到一个数字（`factor`），你记住它。接着，如果看到乘除号（`term` 的循环），你立即知道需要再读一个数字作为右操作数，并构建一个乘法节点，将之前的数字作为左操作数。如果看到加减号（`expr` 的循环），同理构建加减节点。括号则像一个“递归调用”：遇到 `(`，你暂停当前层次，进入一个新的 `expr` 解析，直到遇到 `)` 才返回。这种预测性（每个函数知道接下来可能遇到什么 Token）和递归性（处理嵌套结构）是递归下降解析的精髓。

1.1.4 解释执行：遍历 AST 并求值

现在我们得到了一棵 AST，例如 `3 + 5 * 2` 的 AST 是 `BinOp(Num(3), PLUS, BinOp(Num(5), MUL, Num(2)))`。如何得到结果？很简单：遍历这棵树，自底向上计算每个节点的值。这是一个典型的访问者模式（Visitor Pattern）应用。我们为每个 AST 节点类型定义一个 `eval()` 方法。

```python class AST: """AST 节点的基类（可选，用于统一接口）""" def eval(self): raise NotImplementedError

class NumNode(AST): def __init__(self, value): self.value = value def eval(self): return self.value def __repr__(self): return f"Num({self.value})"

class BinOpNode(AST): def __init__(self, left, op, right): self.left = left self.op = op self.right = right def eval(self):

先计算左右子节点的值（递归）

left_val = self.left.eval() right_val = self.right.eval()

根据运算符执行计算

if self.op.type == 'PLUS': return left_val + right_val elif self.op.type == 'MINUS':