第2章简单语言翻译器

导读

本章是全书的实践起点，通过构建一个简单的翻译器，让读者亲手体验编译器的核心工作流程。我们将从一个最简单的算术表达式语言出发，逐步实现词法分析、语法分析和翻译功能，最终构建出一个能够正确计算和翻译表达式的完整程序。

本章的教学目标非常明确：通过一个具体的、可运行的例子，将第1章中介绍的抽象概念具体化。你将看到词法分析器如何将字符流转换为记号流，语法分析器如何根据文法规则构建语法树，以及翻译过程如何在语法分析的过程中完成。

选择简单语言作为起点有两个重要原因：第一，简单语言足够简洁，使我们能够聚焦于编译器的核心机制而非语言特性的复杂性；第二，简单语言包含了编译器设计的所有关键要素——记号、文法、语法树、翻译规则——为后续章节的深入学习奠定了实践基础。

在本章的学习过程中，建议你动手实现每一个示例代码，通过调试和测试来加深对编译过程的理解。纸上得来终觉浅，绝知此事要躬行。

核心概念详解

2.1 简单语言的定义

我们定义一个简单语言，它支持以下语法结构：

整数常量（如 42、100）
标识符（如 x、count）
算术运算（加 +、减 -、乘 *、除 /）
括号分组（如 (a + b) * c）
赋值语句（如 x = 10）

该语言的语法可以用如下BNF（巴科斯-诺尔范式）描述：

program     → stmt
stmt        → assign | expr
assign      → ID '=' expr
expr        → expr '+' term | expr '-' term | term
term        → term '*' factor | term '/' factor | factor
factor      → NUM | ID | '(' expr ')'

这个文法定义了一个典型的表达式语言，其中 expr 处理加减运算，term 处理乘除运算，factor 处理基本元素。这种分层结构自然地表达了运算符的优先级：乘除优先于加减，括号内的表达式优先计算。

2.2 词法分析器的实现

词法分析器（Scanner/Lexer）的任务是将输入的字符流转换为记号流。对于我们的简单语言，需要识别以下记号类型：

NUM     整数常量
ID      标识符
PLUS    '+'
MINUS   '-'
TIMES   '*'
DIV     '/'
LPAREN  '('
RPAREN  ')'
ASSIGN  '='
EOF     输入结束

词法分析器的核心实现如下：

python

class Token:
    def __init__(self, type, value=None):
        self.type = type
        self.value = value

class Lexer:
    def __init__(self, text):
        self.text = text
        self.pos = 0
        self.current_char = self.text[self.pos] if self.text else None

    def advance(self):
        self.pos += 1
        if self.pos < len(self.text):
            self.current_char = self.text[self.pos]
        else:
            self.current_char = None

    def skip_whitespace(self):
        while self.current_char and self.current_char.isspace():
            self.advance()

    def integer(self):
        result = ''
        while self.current_char and self.current_char.isdigit():
            result += self.current_char
            self.advance()
        return int(result)

    def identifier(self):
        result = ''
        while self.current_char and (self.current_char.isalnum() or self.current_char == '_'):
            result += self.current_char
            self.advance()
        return result

    def get_next_token(self):
        while self.current_char:
            if self.current_char.isspace():
                self.skip_whitespace()
                continue
            if self.current_char.isdigit():
                return Token('NUM', self.integer())
            if self.current_char.isalpha() or self.current_char == '_':
                return Token('ID', self.identifier())
            if self.current_char == '+':
                self.advance()
                return Token('PLUS')
            if self.current_char == '-':
                self.advance()
                return Token('MINUS')
            if self.current_char == '*':
                self.advance()
                return Token('TIMES')
            if self.current_char == '/':
                self.advance()
                return Token('DIV')
            if self.current_char == '(':
                self.advance()
                return Token('LPAREN')
            if self.current_char == ')':
                self.advance()
                return Token('RPAREN')
            if self.current_char == '=':
                self.advance()
                return Token('ASSIGN')
            raise Exception(f'非法字符: {self.current_char}')
        return Token('EOF')

词法分析器的关键设计决策包括：

空白字符处理：空白字符（空格、制表符、换行符）通常被忽略，仅作为记号之间的分隔符。

最长匹配原则：当多个记号可能匹配时，选择最长的匹配。例如，identifier 应该被识别为一个标识符，而不是多个单字符记号。

关键字识别：在某些语言中，关键字（如 if、while）需要与标识符区分。这通常在词法分析阶段完成，也可以在语法分析阶段处理。

2.3 语法分析器的实现

语法分析器（Parser）的任务是根据文法规则，将记号流组织成语法结构。我们采用递归下降分析法来实现语法分析器，因为这种方法直观易懂，且与文法规则有一一对应的关系。

递归下降分析器为文法中的每个非终结符创建一个对应的函数。例如，对于上面的文法，我们需要创建 program()、stmt()、expr()、term()、factor() 等函数。

python

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

    def eat(self, token_type):
        if self.current_token.type == token_type:
            self.current_token = self.lexer.get_next_token()
        else:
            raise Exception(f'语法错误: 期望 {token_type}, 得到 {self.current_token.type}')

    def factor(self):
        token = self.current_token
        if token.type == 'NUM':
            self.eat('NUM')
            return NumNode(token)
        elif token.type == 'ID':
            self.eat('ID')
            return VarNode(token)
        elif token.type == 'LPAREN':
            self.eat('LPAREN')
            node = self.expr()
            self.eat('RPAREN')
            return node

    def term(self):
        node = self.factor()
        while self.current_token.type in ('TIMES', 'DIV'):
            token = self.current_token
            if token.type == 'TIMES':
                self.eat('TIMES')
            elif token.type == 'DIV':
                self.eat('DIV')
            node = BinOpNode(node, token, self.factor())
        return node

    def expr(self):
        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(node, token, self.term())
        return node

    def parse(self):
        return self.stmt()

    def stmt(self):
        if self.current_token.type == 'ID':
            # 检查是否是赋值语句
            saved_pos = self.lexer.pos
            saved_token = self.current_token
            name = self.current_token.value
            self.eat('ID')
            if self.current_token.type == 'ASSIGN':
                self.eat('ASSIGN')
                expr = self.expr()
                return AssignNode(name, expr)
            # 回溯
            self.lexer.pos = saved_pos
            self.current_token = saved_token
        return self.expr()

2.4 抽象语法树（AST）

抽象语法树（Abstract Syntax Tree, AST）是源代码语法结构的一种树状表示。树的每个内部节点代表一个运算，叶子节点代表运算的操作数。

对于我们的简单语言，定义以下AST节点类型：

python

class ASTNode:
    pass

class NumNode(ASTNode):
    def __init__(self, token):
        self.token = token
        self.value = token.value

class VarNode(ASTNode):
    def __init__(self, token):
        self.token = token
        self.name = token.value

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

class AssignNode(ASTNode):
    def __init__(self, name, expr):
        self.name = name
        self.expr = expr

对于表达式 x = 3 + 4 * 2，构建的AST如下：

AssignNode
├── name: "x"
└── expr: BinOpNode(+)
    ├── left: NumNode(3)
    ├── op: PLUS
    └── right: BinOpNode(*)
        ├── left: NumNode(4)
        ├── op: TIMES
        └── right: NumNode(2)

AST的一个重要特性是它省略了语法中的冗余信息（如括号），只保留了语义上必要的结构。这使得AST比具体的语法树更加紧凑和易于处理。

2.5 翻译器的实现

翻译器通过遍历AST来执行翻译。我们使用访问者模式（Visitor Pattern）来实现翻译过程，这样可以方便地添加新的翻译功能而不修改AST节点的定义。

解释器（计算表达式值）：

python

class Interpreter:
    def __init__(self):
        self.variables = {}

    def visit(self, node):
        if isinstance(node, NumNode):
            return node.value
        elif isinstance(node, VarNode):
            if node.name in self.variables:
                return self.variables[node.name]
            raise Exception(f'未定义的变量: {node.name}')
        elif isinstance(node, BinOpNode):
            left = self.visit(node.left)
            right = self.visit(node.right)
            if node.op.type == 'PLUS':
                return left + right
            elif node.op.type == 'MINUS':
                return left - right
            elif node.op.type == 'TIMES':
                return left * right
            elif node.op.type == 'DIV':
                return left / right
        elif isinstance(node, AssignNode):
            value = self.visit(node.expr)
            self.variables[node.name] = value
            return value

目标代码生成器（生成三地址码）：

python

class CodeGenerator:
    def __init__(self):
        self.temp_count = 0
        self.instructions = []

    def new_temp(self):
        self.temp_count += 1
        return f't{self.temp_count}'

    def visit(self, node):
        if isinstance(node, NumNode):
            return str(node.value)
        elif isinstance(node, VarNode):
            return node.name
        elif isinstance(node, BinOpNode):
            left = self.visit(node.left)
            right = self.visit(node.right)
            temp = self.new_temp()
            op = node.op.type.lower()
            self.instructions.append(f'{temp} = {left} {op} {right}')
            return temp
        elif isinstance(node, AssignNode):
            value = self.visit(node.expr)
            self.instructions.append(f'{node.name} = {value}')

2.6 语法制导翻译

语法制导翻译（Syntax-Directed Translation, SDT）是将语法分析与翻译过程紧密结合的一种方法。在语法制导翻译中，每个文法产生式都关联有语义规则（或翻译规则），当语法分析器识别出该产生式时，就执行相应的语义动作。

对于我们的简单语言，语法制导翻译的规则如下：

产生式                    语义动作
─────────────────────────────────────────────
expr → expr₁ + term    { expr.place = newtemp();
                          gen(expr.place '=' expr₁.place '+' term.place) }
expr → expr₁ - term    { expr.place = newtemp();
                          gen(expr.place '=' expr₁.place '-' term.place) }
expr → term            { expr.place = term.place }
term → term₁ * factor  { term.place = newtemp();
                          gen(term.place '=' term₁.place '*' factor.place) }
term → term₁ / factor  { term.place = newtemp();
                          gen(term.place '=' term₁.place '/' factor.place) }
term → factor          { term.place = factor.place }
factor → NUM           { factor.place = NUM.value }
factor → ID            { factor.place = ID.entry }
factor → ( expr )      { factor.place = expr.place }

语法制导翻译的核心思想是：语法结构和语义动作是紧密关联的。当我们识别出一个语法结构时，就可以立即执行与之关联的语义动作。这种方法使得翻译过程与语法分析过程自然融合。

重要知识点

2.7 递归下降分析法的局限性

递归下降分析法虽然直观易懂，但存在一些局限性：

左递归问题：如果文法包含左递归产生式（如 A → Aα），递归下降分析器会陷入无限递归。必须消除左递归才能使用递归下降分析法。

回溯问题：当多个产生式以相同的符号开头时，可能需要回溯。例如，如果文法同时包含 stmt → ID '=' expr 和 stmt → expr，当看到 ID 时无法立即判断应该选择哪个产生式。

错误恢复困难：递归下降分析器在遇到错误时，错误恢复相对困难，因为错误可能在递归调用的深层发生。

2.8 LL(1) 文法

为了避免递归下降分析法的局限性，我们通常要求文法满足 LL(1) 条件：

第一个 L：从左到右扫描输入
第二个 L：产生最左推导
1：使用1个输入符号的前瞻来决定分析动作

一个文法是 LL(1) 的，当且仅当对于每个非终结符 A 的任意两个不同产生式 A → α | β，满足以下条件：

α 和 β 不能推导出以相同终结符开头的串

α 和 β 不能同时推导出空串 ε

如果 β 可以推导出 ε，则 α 不能推导出以 FOLLOW(A) 中终结符开头的串

2.9 预测分析表

对于 LL(1) 文法，可以构造预测分析表来驱动语法分析。预测分析表是一个二维数组 M[A, a]，其中 A 是非终结符，a 是终结符。表项 M[A, a] 存储当遇到非终结符 A 和输入符号 a 时应该使用的产生式。

预测分析器的结构包括：

一个输入缓冲区
一个符号栈（初始包含 #S，S 是开始符号，# 是结束标记）
一个预测分析表

分析过程：

查看栈顶符号 X 和当前输入符号 a

如果 X = a = #，分析成功

如果 X = a ≠ #，弹出栈顶，前进到下一个输入符号

如果 X 是非终结符，查表 M[X, a]，用对应的产生式右部替换栈顶的 X

其他情况，报告错误

2.10 属性文法

属性文法（Attribute Grammar）是上下文无关文法的扩展，它为文法的每个符号关联属性，并为每个产生式关联属性计算规则。属性文法提供了一种形式化的方法来描述语言的语义。

属性分为两类：

综合属性（Synthesized Attribute）：节点的值由其子节点的属性值计算得出（自底向上）
继承属性（Inherited Attribute）：节点的值由其父节点或兄弟节点的属性值计算得出（自顶向下）

例如，在表达式求值中，每个节点有一个 val 属性：

产生式                      语义规则
─────────────────────────────────────────────
E → E₁ + T               { E.val = E₁.val + T.val }
E → T                    { E.val = T.val }
T → T₁ * F               { T.val = T₁.val * F.val }
T → F                    { T.val = F.val }
F → NUM                  { F.val = NUM.value }

这里 val 是综合属性，因为它从子节点向父节点传播。

常见误区

误区一：词法分析和语法分析可以合并

虽然词法分析和语法分析在概念上是分开的，但在某些简单场景中，可以将两者合并。然而，这种合并会导致代码难以维护和扩展。保持两者的分离是编译器设计的最佳实践，因为：

词法规则和语法规则本质不同
分离后各自可以独立优化
便于代码复用和测试

误区二：AST就是语法树

具体语法树（Concrete Syntax Tree, CST）和抽象语法树（AST）是不同的。CST严格按照文法产生式构建，包含了所有语法细节（包括括号、分隔符等）。AST则省略了冗余信息，只保留语义上必要的结构。例如，对于表达式 (a + b)，CST会包含括号节点，而AST直接表示为 BinOp(+, a, b)。

误区三：递归下降只能处理简单文法

递归下降分析法可以处理任何 LL(k) 文法，而不仅仅是简单文法。通过适当的技术（如前瞻符号、记忆化等），递归下降可以处理相当复杂的文法。事实上，许多工业级编译器（如GCC、Clang、Rust编译器）都使用递归下降分析法或其变体。

误区四：翻译只能在语法分析之后进行

语法制导翻译表明翻译可以在语法分析的过程中同步进行。实际上，许多编译器采用"单遍"策略，在语法分析的同时完成翻译工作。当然，复杂的翻译（如全局优化）确实需要完整的中间表示。

实践应用

2.11 构建一个完整的翻译器

让我们将所有组件组合起来，构建一个完整的翻译器：

python

class Translator:
    def __init__(self, text):
        self.lexer = Lexer(text)
        self.parser = Parser(self.lexer)
        self.interpreter = Interpreter()
        self.codegen = CodeGenerator()

    def interpret(self):
        ast = self.parser.parse()
        result = self.interpreter.visit(ast)
        return result

    def generate_code(self):
        ast = self.parser.parse()
        self.codegen.visit(ast)
        return self.codegen.instructions

# 使用示例
text = "x = 3 + 4 * 2"
translator = Translator(text)

# 解释执行
result = translator.interpret()
print(f"结果: {result}")  # 输出: 结果: 11

# 生成代码
instructions = translator.generate_code()
for inst in instructions:
    print(inst)
# 输出:
# t1 = 4 * 2
# t2 = 3 + t1
# x = t2

2.12 翻译器在现实世界的应用

本章介绍的翻译器技术在实际软件中有广泛应用：

计算器应用：手机和电脑上的计算器应用内部就使用了类似的表达式解析和求值技术。

电子表格：Excel等电子表格软件需要解析和计算公式表达式，其核心就是一个翻译器。

配置解析：许多配置文件格式（如JSON、YAML）的解析器本质上也是翻译器。

模板引擎：Web开发中的模板引擎（如Jinja2、EJS）将模板语言翻译为HTML输出。

SQL引擎：数据库系统需要将SQL查询翻译为查询执行计划。

2.13 扩展翻译器的功能

本章的翻译器可以方便地扩展：

添加新的运算符：如幂运算 **、取模 %、一元负号 -

添加新的数据类型：如浮点数、字符串、布尔值

添加控制流：如条件语句 if-else、循环语句 while

添加函数定义：如 def f(x) = x * 2

生成不同的目标代码：如生成JavaScript代码、Python代码、甚至汇编代码

每种扩展都需要相应地修改文法、词法分析器、语法分析器和翻译规则。

本章小结

本章通过构建一个简单语言翻译器，将编译原理的核心概念具体化。我们学习了以下关键内容：

词法分析器的实现：将字符流转换为记号流，处理空白字符、数字、标识符和运算符。

递归下降语法分析器：为每个文法产生式创建对应的分析函数，自顶向下地构建语法结构。

抽象语法树（AST）：用树状结构表示源代码的语法结构，是翻译过程的核心数据结构。

翻译的实现：通过遍历AST完成解释执行或代码生成，使用访问者模式实现可扩展的翻译架构。

语法制导翻译：将语义动作与文法产生式关联，在语法分析过程中同步完成翻译。

属性文法：为文法符号关联属性，用形式化的方法描述语言语义。

本章的翻译器虽然简单，但包含了编译器的所有核心组件。后续章节将在此基础上深入探讨每个组件的理论基础和实现技术。

第2章 简单语言翻译器

导读

核心概念详解

2.1 简单语言的定义

2.2 词法分析器的实现

2.3 语法分析器的实现

2.4 抽象语法树（AST）

2.5 翻译器的实现

2.6 语法制导翻译

重要知识点

2.7 递归下降分析法的局限性

2.8 LL(1) 文法

2.9 预测分析表

2.10 属性文法

常见误区

误区一：词法分析和语法分析可以合并

误区二：AST就是语法树

误区三：递归下降只能处理简单文法

误区四：翻译只能在语法分析之后进行

实践应用

2.11 构建一个完整的翻译器

2.12 翻译器在现实世界的应用

2.13 扩展翻译器的功能

本章小结

第2章简单语言翻译器