编译器如何理解代码？语法解析的两种方法详解

前言

你有没有想过，当你写下一行代码：

result = 1 + 2 * 3

编译器是怎么知道先算 2 * 3，再算 1 + 6 的？

这就是语法解析（Syntax Parsing）要做的事情。今天，我用最简单的方式，带你理解这个过程。

一、语法解析是什么？

想象你在读一个句子：

“小明吃苹果”

你的大脑会自动分析：

主语：小明
谓语：吃
宾语：苹果

语法解析就是让计算机也能这样"理解"代码的结构。

1.1 解析的输入和输出

输入：一串符号（Token）

result = 1 + 2 * 3
↓ 分词后
[变量: result] [符号: =] [数字: 1] [符号: +] [数字: 2] [符号: *] [数字: 3]

输出：一棵树（语法树）

这棵树告诉我们：

最顶层是赋值操作 =
左边是变量 result
右边是加法 +
加法的右边是乘法 *（所以先算乘法）

1.2 为什么要用树？

因为树能清楚地表达优先级和层次关系：

树的越深层的节点，越先计算
乘法在加法下面，所以先算

二、两种解析方法

语法解析有两种主要方法：

自顶向下（Top-Down）：从树根开始，向下生长
自底向上（Bottom-Up）：从树叶开始，向上合并

让我们详细看看这两种方法。

三、自顶向下解析

3.1 核心思想

想象你在画画：

先画出树干（最外层结构）
再画大树枝（次级结构）
最后画树叶（具体内容）

这就是自顶向下：从整体到局部。

3.2 递归下降解析

这是最常用的自顶向下方法。原理很简单：

每个语法规则对应一个函数
函数调用其他函数，就像语法规则嵌套

示例：简单的数学表达式

假设我们的语法规则是：

表达式 → 项 + 项 | 项
项 → 因子 * 因子 | 因子
因子 → 数字 | (表达式)

用代码表示：

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0
    
    def parse_expression(self):
        """解析表达式：项 + 项 | 项"""
        left = self.parse_term()  # 先解析左边的项
        
        while self.current_token() == '+':
            self.consume('+')  # 吃掉 + 号
            right = self.parse_term()  # 解析右边的项
            left = ('+', left, right)  # 构建语法树节点
        
        return left
    
    def parse_term(self):
        """解析项：因子 * 因子 | 因子"""
        left = self.parse_factor()  # 先解析左边的因子
        
        while self.current_token() == '*':
            self.consume('*')  # 吃掉 * 号
            right = self.parse_factor()  # 解析右边的因子
            left = ('*', left, right)  # 构建语法树节点
        
        return left
    
    def parse_factor(self):
        """解析因子：数字 | (表达式)"""
        token = self.current_token()
        
        if token == '(':
            self.consume('(')
            expr = self.parse_expression()  # 递归解析括号内的表达式
            self.consume(')')
            return expr
        else:
            # 这是一个数字
            self.consume(token)
            return ('number', token)
    
    def current_token(self):
        """获取当前 token"""
        if self.pos < len(self.tokens):
            return self.tokens[self.pos]
        return None
    
    def consume(self, expected):
        """消耗一个 token"""
        if self.current_token() == expected:
            self.pos += 1
        else:
            raise Exception(f"期望 {expected}, 但得到 {self.current_token()}")

# 使用示例
tokens = ['1', '+', '2', '*', '3']
parser = Parser(tokens)
tree = parser.parse_expression()
print(tree)
# 输出：('+', ('number', '1'), ('*', ('number', '2'), ('number', '3')))

3.3 解析过程图解

让我们看看 1 + 2 * 3 是如何被解析的：

graph TD
    A[开始解析表达式] --> B[解析项]
    B --> C[解析因子: 1]
    C --> D[返回 number:1]
    D --> E{当前是 + 号?}
    E -->|是| F[消耗 + 号]
    F --> G[解析项: 2*3]
    G --> H[解析因子: 2]
    H --> I[返回 number:2]
    I --> J{当前是 * 号?}
    J -->|是| K[消耗 * 号]
    K --> L[解析因子: 3]
    L --> M[返回 number:3]
    M --> N[构建 * 节点]
    N --> O[返回 * 节点]
    O --> P[构建 + 节点]
    P --> Q[返回语法树]
    
    style A fill:#e1f5ff
    style Q fill:#d4edda

3.4 生成的语法树

graph TD
    PLUS["+"] --> NUM1["number: 1"]
    PLUS["+"] --> MUL["*"]
    MUL["*"] --> NUM2["number: 2"]
    MUL["*"] --> NUM3["number: 3"]
    
    style PLUS fill:#fff4e1
    style MUL fill:#fff4e1
    style NUM1 fill:#e8f5e9
    style NUM2 fill:#e8f5e9
    style NUM3 fill:#e8f5e9

3.5 优缺点

优点	缺点
✅ 代码直观，容易理解	❌ 不能处理左递归语法
✅ 容易手动实现	❌ 某些情况需要回溯
✅ 错误定位准确	❌ 对复杂语法支持有限
✅ 可以自定义错误信息	❌ 效率相对较低

四、自底向上解析

4.1 核心思想

这次反过来，想象你在拼图：

先找到边缘的碎片（最底层的符号）
把相关的碎片拼成小区域
把小区域拼成大区域
最后完成整幅图

这就是自底向上：从局部到整体。

4.2 移进-归约解析

这是最常用的自底向上方法。核心操作有两个：

移进（Shift）：把输入符号压入栈
归约（Reduce）：把栈顶的符号按语法规则合并

示例：解析 `1 + 2 * 3`

假设语法规则：

1. E → E + E
2. E → E * E
3. E → number

解析过程：

sequenceDiagram
    participant 输入
    participant 栈
    participant 动作
    
    Note over 输入: 1 + 2 * 3 $
    
    输入->>栈: 移进 1
    栈->>动作: 归约: number → E (规则3)
    Note over 栈: E
    
    输入->>栈: 移进 +
    Note over 栈: E +
    
    输入->>栈: 移进 2
    栈->>动作: 归约: number → E (规则3)
    Note over 栈: E + E
    
    输入->>栈: 移进 *
    Note over 栈: E + E *
    
    输入->>栈: 移进 3
    栈->>动作: 归约: number → E (规则3)
    Note over 栈: E + E * E
    
    栈->>动作: 归约: E * E → E (规则2)
    Note over 栈: E + E
    
    栈->>动作: 归约: E + E → E (规则1)
    Note over 栈: E
    
    Note over 动作: ✅ 解析成功！

4.3 代码实现

class ShiftReduceParser:
    def __init__(self, tokens, grammar):
        self.tokens = tokens + ['$']  # 添加结束符
        self.grammar = grammar  # 语法规则
        self.stack = ['$']  # 栈，初始有结束符
        self.pos = 0  # 输入位置
    
    def parse(self):
        """执行移进-归约解析"""
        print(f"{'步骤':<6} {'栈':<20} {'输入':<15} {'动作'}")
        print("-" * 60)
        
        step = 0
        while True:
            step += 1
            stack_str = ' '.join(self.stack)
            input_str = ' '.join(self.tokens[self.pos:])
            
            # 尝试归约
            reduced = self.try_reduce()
            if reduced:
                print(f"{step:<6} {stack_str:<20} {input_str:<15} 归约: {reduced}")
                continue
            
            # 尝试移进
            if self.pos < len(self.tokens):
                self.stack.append(self.tokens[self.pos])
                self.pos += 1
                print(f"{step:<6} {stack_str:<20} {input_str:<15} 移进")
            else:
                # 无法移进也无法归约
                if len(self.stack) == 2 and self.stack[1] == 'E':
                    print(f"{step:<6} {stack_str:<20} {input_str:<15} ✅ 接受")
                    return True
                else:
                    print(f"{step:<6} {stack_str:<20} {input_str:<15} ❌ 错误")
                    return False
    
    def try_reduce(self):
        """尝试归约栈顶"""
        # 检查每条语法规则
        for rule_name, rule in self.grammar.items():
            pattern = rule['pattern']
            # 检查栈顶是否匹配规则
            if len(self.stack) >= len(pattern):
                top = self.stack[-len(pattern):]
                if top == pattern:
                    # 归约：移除栈顶，压入结果
                    self.stack = self.stack[:-len(pattern)]
                    self.stack.append(rule['result'])
                    return f"{rule_name}: {' '.join(pattern)} → {rule['result']}"
        return None

# 定义语法规则
grammar = {
    'rule1': {'pattern': ['E', '+', 'E'], 'result': 'E'},
    'rule2': {'pattern': ['E', '*', 'E'], 'result': 'E'},
    'rule3': {'pattern': ['number'], 'result': 'E'},
}

# 预处理：把数字替换为 number
tokens = ['number', '+', 'number', '*', 'number']

parser = ShiftReduceParser(tokens, grammar)
parser.parse()

4.4 输出示例

步骤   栈                   输入            动作
------------------------------------------------------------
1      $                    number + number * number $ 移进
2      $ number             + number * number $ 归约: rule3: number → E
3      $ E                  + number * number $ 移进
4      $ E +                number * number $ 移进
5      $ E + number         * number $ 归约: rule3: number → E
6      $ E + E              * number $ 移进
7      $ E + E *            number $ 移进
8      $ E + E * number     $ 归约: rule3: number → E
9      $ E + E * E          $ 归约: rule2: E * E → E
10     $ E + E              $ 归约: rule1: E + E → E
11     $ E                  $ ✅ 接受

4.5 优缺点

优点	缺点
✅ 可以处理左递归	❌ 实现复杂
✅ 效率高（LR解析器）	❌ 难以手动编写
✅ 功能强大	❌ 错误信息不够友好
✅ 支持复杂的语法	❌ 调试困难

五、两种方法对比

5.1 图解对比

自顶向下：

graph TD
    A[表达式] --> B[项]
    A --> C[+]
    A --> D[项]
    B --> E[因子: 1]
    D --> F[项]
    D --> G[*]
    D --> H[因子: 3]
    F --> I[因子: 2]
    
    style A fill:#e1f5ff
    style B fill:#fff4e1
    style D fill:#fff4e1

方向：从根节点向下展开

自底向上：

graph TD
    E1["number: 1"] --> E2["E"]
    E3["number: 2"] --> E4["E"]
    E5["number: 3"] --> E6["E"]
    E4 --> E7["E"]
    E6 --> E7
    PLUS["+"] --> E7
    E2 --> E8["E (最终)"]
    E7 --> E8
    MUL["*"] --> E8
    
    style E8 fill:#d4edda

方向：从叶子节点向上合并

5.2 适用场景

场景	推荐方法	原因
手写解析器	自顶向下	代码直观，容易实现
编译器课程作业	自顶向下	便于理解原理
工业级编译器	自底向上（LR）	功能强大，效率高
解释器	自顶向下	错误信息友好
IDE 语法检查	自顶向下	可以实时反馈

5.3 常见的解析器

自顶向下：

LL(1)：简单，常用于教学
LL(k)：看 k 个符号决定下一步
递归下降：最常见，如 GCC 的 C++ 解析器

自底向上：

LR(0)：最基础，功能有限
SLR(1)：简单 LR，有改进
LR(1)：功能强大，被广泛使用
LALR(1)：LR(1) 的优化版本，如 Yacc、Bison

六、实战示例：解析简单的算术表达式

让我们写一个完整的解析器，计算算术表达式：

import re

class ArithmeticParser:
    """算术表达式解析器 - 使用递归下降"""
    
    def __init__(self, text):
        self.tokens = self.tokenize(text)
        self.pos = 0
    
    def tokenize(self, text):
        """分词：把字符串转换成 token 列表"""
        tokens = []
        for match in re.finditer(r'\d+|\+|\-|\*|\/|\(|\)', text):
            token = match.group()
            # 如果是数字，转换成整数
            if token.isdigit():
                tokens.append(('number', int(token)))
            else:
                tokens.append(('op', token))
        return tokens
    
    def current_token(self):
        """获取当前 token"""
        if self.pos < len(self.tokens):
            return self.tokens[self.pos]
        return None
    
    def consume(self, expected_type=None, expected_value=None):
        """消耗一个 token"""
        token = self.current_token()
        if token is None:
            raise Exception("意外的输入结束")
        
        if expected_type and token[0] != expected_type:
            raise Exception(f"期望类型 {expected_type}, 但得到 {token[0]}")
        
        if expected_value and token[1] != expected_value:
            raise Exception(f"期望 {expected_value}, 但得到 {token[1]}")
        
        self.pos += 1
        return token
    
    def parse(self):
        """开始解析"""
        result = self.parse_expression()
        if self.current_token() is not None:
            raise Exception("还有未解析的内容")
        return result
    
    def parse_expression(self):
        """解析表达式：处理 + 和 -"""
        left = self.parse_term()
        
        while self.current_token() and self.current_token()[1] in ['+', '-']:
            op = self.consume('op')[1]
            right = self.parse_term()
            
            if op == '+':
                left = left + right
            else:
                left = left - right
        
        return left
    
    def parse_term(self):
        """解析项：处理 * 和 /"""
        left = self.parse_factor()
        
        while self.current_token() and self.current_token()[1] in ['*', '/']:
            op = self.consume('op')[1]
            right = self.parse_factor()
            
            if op == '*':
                left = left * right
            else:
                left = left / right
        
        return left
    
    def parse_factor(self):
        """解析因子：数字或括号表达式"""
        token = self.current_token()
        
        if token[0] == 'number':
            return self.consume()[1]
        elif token[1] == '(':
            self.consume('op', '(')
            result = self.parse_expression()
            self.consume('op', ')')
            return result
        else:
            raise Exception(f"意外的 token: {token}")

# 测试
expressions = [
    "1 + 2",
    "1 + 2 * 3",
    "(1 + 2) * 3",
    "10 - 3 * 2",
    "20 / 4 + 1",
]

for expr in expressions:
    parser = ArithmeticParser(expr)
    result = parser.parse()
    print(f"{expr} = {result}")

6.1 输出结果

1 + 2 = 3
1 + 2 * 3 = 7
(1 + 2) * 3 = 9
10 - 3 * 2 = 4
20 / 4 + 1 = 6.0

6.2 解析过程分析

让我们看看 (1 + 2) * 3 的解析过程：

graph TD
    A[parse_expression] --> B[parse_term]
    B --> C[parse_factor]
    C --> D["遇到 ( , 进入括号"]
    D --> E[parse_expression]
    E --> F[parse_term]
    F --> G[parse_factor: 1]
    G --> H["返回 1"]
    H --> I["遇到 + , 继续"]
    I --> J[parse_term]
    J --> K[parse_factor: 2]
    K --> L["返回 2"]
    L --> M["计算 1 + 2 = 3"]
    M --> N["遇到 ) , 退出括号"]
    N --> O["返回 3"]
    O --> P["遇到 * , 继续"]
    P --> Q[parse_factor: 3]
    Q --> R["返回 3"]
    R --> S["计算 3 * 3 = 9"]
    S --> T["返回 9"]
    
    style A fill:#e1f5ff
    style T fill:#d4edda

七、常见问题

Q1：为什么 `1 + 2 * 3` 先算乘法？

因为我们的语法规则定义了优先级：

表达式 → 项 + 项      (加法在外层)
项 → 因子 * 因子      (乘法在内层)

越在内层的规则，越先被解析，所以乘法优先级更高。

Q2：什么是左递归？为什么自顶向下不能处理？

左递归：语法规则直接或间接地以自己开头

E → E + E  ❌ 这是左递归！

问题：

def parse_E():
    parse_E()  # 无限递归！
    ...

解决方案：

E → E + T | T      改为：E → T + E'
E' → + T E' | ε    (ε 表示空)

Q3：如何选择解析方法？

flowchart TD
    A[需要实现解析器] --> B{语法是否复杂?}
    B -->|简单| C[自顶向下<br/>递归下降]
    B -->|复杂| D{需要高性能吗?}
    D -->|是| E[自底向上<br/>LR/LALR]
    D -->|否| F[自顶向下<br/>使用解析器生成器]
    
    C --> G[手写代码]
    E --> H[使用 Yacc/Bison]
    F --> I[使用 ANTLR]
    
    style C fill:#d4edda
    style E fill:#d4edda
    style F fill:#d4edda

八、总结

核心概念

语法解析：把代码转换成语法树
自顶向下：从树根开始，递归下降
自底向上：从树叶开始，移进归约

选择建议

学习/教学：用自顶向下（递归下降）
手写解析器：用自顶向下
工业级应用：用自底向上（LR/LALR）
快速开发：用解析器生成器（ANTLR、Yacc）

进阶学习

想深入学习编译器，推荐：

《编译原理》（龙书）
《Engineering a Compiler》
Stanford 编译器课程（Coursera）

扩展阅读

希望这篇文章能帮你理解语法解析的基本原理。编译器虽然复杂，但核心思想其实很简单！

前言#

一、语法解析是什么？#

1.1 解析的输入和输出#

1.2 为什么要用树？#

二、两种解析方法#

三、自顶向下解析#

3.1 核心思想#

3.2 递归下降解析#

示例：简单的数学表达式#

3.3 解析过程图解#

3.4 生成的语法树#

3.5 优缺点#

四、自底向上解析#

4.1 核心思想#

4.2 移进-归约解析#

示例：解析 1 + 2 * 3#

4.3 代码实现#

4.4 输出示例#

4.5 优缺点#

五、两种方法对比#

5.1 图解对比#

5.2 适用场景#

5.3 常见的解析器#

六、实战示例：解析简单的算术表达式#

6.1 输出结果#

6.2 解析过程分析#

七、常见问题#

Q1：为什么 1 + 2 * 3 先算乘法？#

Q2：什么是左递归？为什么自顶向下不能处理？#

Q3：如何选择解析方法？#

八、总结#

核心概念#

选择建议#

进阶学习#

扩展阅读#

前言