编译原理实验二：从文法到AST，构建递归下降语法分析器

1. 实验概览与核心目标

又到了编译原理实验课的时间，这次我们面对的是Lab. 2，一个承上启下的关键节点。如果说Lab. 1是让你熟悉编译器的“骨架”和基本流程，那么Lab. 2就是让你亲手为这个骨架注入“肌肉”和“神经”，构建一个真正能处理更复杂语法结构的二代编译器前端。很多同学看到“二代编译器”、“实验说明和要求”这样的标题可能会觉得枯燥，但我想说，这个实验恰恰是理解编译器如何从“识别单词”进化到“理解句子结构”的绝佳机会。它不再满足于简单的词法分析，而是要求你实现一个完整的语法分析器（Parser），并构建出初步的抽象语法树（AST）。这个过程，本质上是在教会计算机如何按照我们定义的规则（文法）去理解一段程序代码的层次和逻辑。

简单来说，这次实验的核心目标有三个：第一，深入理解上下文无关文法（CFG）及其在编译器中的核心地位；第二，掌握递归下降或自顶向下语法分析的基本思想和实现技巧；第三，亲手实现一个能处理赋值语句、算术表达式、控制流语句（如if-else）等基本程序结构的语法分析模块，并输出结构化的AST。无论你未来是从事底层系统开发、语言工具链研发，还是任何需要处理复杂结构化数据的领域，这里锻炼出的“结构化思维”和“规则引擎构建”能力都至关重要。接下来，我会结合常见的实现路径和踩坑经验，带你一步步拆解这个实验。

2. 实验环境搭建与工程结构解析

工欲善其事，必先利其器。在开始编码之前，一个清晰、健壮且易于构建的工程环境能让你事半功倍，避免后期在文件依赖和编译选项上浪费大量时间。从相关热词如“CMakeLists”、“msvc编译器”、“gnu gcc编译器怎么下载”可以看出，工具链的选择和配置是大家的共同关切点。

2.1 编译器与构建系统的选择

对于编译原理实验，我强烈推荐使用Clang++/GCC + CMake的组合。理由如下：

1. 标准兼容性好：Clang和GCC对现代C++标准的支持非常积极，能让你使用更清晰、更安全的语法（如智能指针、范围for循环）来管理AST节点等资源，减少内存泄漏的风险。
2. 错误信息友好：尤其是Clang，其报错信息通常比MSVC更清晰，能快速定位模板或类型相关的复杂错误，这对实现泛型的词法/语法分析器辅助类很有帮助。
3. 跨平台性：CMake作为构建系统，可以让你在Linux、macOS和Windows（通过MinGW或WSL）上保持几乎一致的开发体验。你只需要维护一个CMakeLists.txt文件。

如何搭建：

• Linux/macOS：通常系统自带或可通过包管理器（apt, brew）轻松安装gcc/g++或clang以及cmake。
• Windows：建议使用MSYS2 + MinGW-w64环境。在MSYS2中，你可以通过pacman安装mingw-w64-x86_64-gcc和mingw-w64-x86_64-cmake。这能提供一个类Unix的开发和终端环境，避免纯Windows路径和工具链带来的一些诡异问题。另一种方案是使用WSL2（Windows Subsystem for Linux），这能获得原生的Linux体验。

注意：尽量避免在Windows上直接使用Visual Studio的MSVC编译器进行此类实验，除非实验框架已明确适配。因为涉及Makefile、脚本或一些Unix风格的库调用时，MSVC环境可能需要额外的移植工作，容易分散你的核心精力。

2.2 CMakeLists.txt 的编写要点

你的项目根目录下应该有一个CMakeLists.txt文件。这是CMake的“总蓝图”。一个基础的配置如下：

cmake_minimum_required(VERSION 3.10) project(CompilerLab2 VERSION 1.0 LANGUAGES CXX) # 设置C++标准为C++17或更高，便于使用std::optional, std::variant等现代特性管理语法树节点 set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) # 如果你使用了第三方库，比如用于测试的catch2，可以在这里通过find_package或add_subdirectory引入 # find_package(Catch2 REQUIRED) # 将源代码文件添加到一个变量中，便于管理 set(SOURCES src/main.cpp src/lexer.cpp src/parser.cpp src/ast.cpp src/symbol_table.cpp ) # 将头文件目录包含进来 include_directories(${CMAKE_CURRENT_SOURCE_DIR}/include) # 生成可执行文件 add_executable(compiler_lab2 ${SOURCES}) # 链接库，如果有的话 # target_link_libraries(compiler_lab2 Catch2::Catch2) # 启用更严格的编译警告，帮助发现潜在问题 if(CMAKE_CXX_COMPILER_ID MATCHES "GNU|Clang") target_compile_options(compiler_lab2 PRIVATE -Wall -Wextra -Wpedantic) endif()

关键解析：

• set(CMAKE_CXX_STANDARD 17)：这条指令至关重要。现代C++特性如std::unique_ptr（用于AST节点所有权管理）、std::variant（可用于实现不同类型的AST节点容器）能极大简化代码并提升安全性。强制使用C++17能确保你和助教的环境一致性。
• include_directories：确保你的#include “parser.h”等语句能正确找到位于include/目录下的头文件。良好的头文件组织（如include/compiler/）是专业项目的标志。
• 警告选项-Wall -Wextra：在开发阶段打开所有警告，并将其视为错误（可以加上-Werror）是一个好习惯。它能强迫你写出更严谨的代码，很多隐蔽的bug（如符号不匹配、未使用的变量）会在编译阶段就被揪出来。

2.3 项目目录结构规划

一个清晰的结构有助于你管理越来越多的源代码文件。我建议采用如下结构：

compiler_lab2/ ├── CMakeLists.txt # 项目根CMake文件 ├── build/ # 构建目录（外部构建，不污染源码） ├── include/ # 所有头文件(.h/.hpp) │ └── compiler/ │ ├── lexer.h │ ├── parser.h │ ├── ast.h │ └── symbol_table.h ├── src/ # 所有源文件(.cpp) │ ├── main.cpp │ ├── lexer.cpp │ ├── parser.cpp │ ├── ast.cpp │ └── symbol_table.cpp ├── tests/ # 测试用例 │ ├── CMakeLists.txt # 测试子项目的CMake文件 │ └── test_parser.cpp ├── samples/ # 测试用的源代码样例 │ ├── simple_assign.src │ └── if_else.src └── README.md # 项目说明

为什么要外部构建？即在build/目录下运行cmake ..和make。这能保持源码目录的纯净，方便版本控制（.gitignore中忽略build/），并且可以同时为不同配置（Debug/Release）创建多个构建目录。

3. 从文法定义到语法分析器实现

这是本次实验最核心、最具挑战性的部分。你需要将实验手册中给出的或自己设计的上下文无关文法，转化为可以运行的代码。这个过程充满了设计决策。

3.1 理解实验给定的文法

实验说明中通常会给出一个用于描述简单类C语言子集的文法。例如，一个可能包含赋值、算术运算和if语句的文法片段：

Program -> StmtList StmtList -> Stmt StmtList | ε Stmt -> AssignStmt | IfStmt | Block AssignStmt -> IDENTIFIER '=' Expr ';' IfStmt -> 'if' '(' Cond ')' Stmt ('else' Stmt)? Block -> '{' StmtList '}' Expr -> Term (('+' | '-') Term)* Term -> Factor (('*' | '/') Factor)* Factor -> IDENTIFIER | NUMBER | '(' Expr ')' Cond -> Expr RelOp Expr RelOp -> '==' | '!=' | '<' | '>' | '<=' | '>='

（注：这里使用扩展的BNF表示，*表示0次或多次，?表示0次或1次，|表示选择）

第一步不是编码，而是“消化”文法：

1. 消除左递归：上述Expr和Term规则是典型的左递归（通过Expr -> Expr '+' Term的形式）。直接递归下降解析器无法处理左递归，会导致无限递归。你需要将其转换为等价的右递归形式。这是必须掌握的基础步骤。
2. 提取左公因子：如果多个产生式有共同的前缀，可能会造成预测分析时的冲突。需要提取公因子以简化预测逻辑。
3. 计算FIRST集和FOLLOW集：这是为编写预测分析器（递归下降或LL(1)分析器）做理论准备。手动计算一遍能让你深刻理解分析器在某个非终结符处，应该如何根据下一个输入符号（lookahead token）来决定使用哪个产生式。

3.2 递归下降语法分析器设计

递归下降是最直观、最适合手工实现的语法分析方法。其核心思想是为文法中的每一个非终结符（如Program,Stmt,Expr）编写一个对应的函数。这个函数负责从词法分析器（Lexer）获取Token流，并尝试“匹配”该非终结符所对应的语法结构。

以解析Expr -> Term (('+' | '-') Term)*为例： 首先，需要将左递归文法Expr -> Expr '+' Term | Term改写为右递归：Expr -> Term Expr'，Expr' -> '+' Term Expr' | '-' Term Expr' | ε。

对应的递归下降函数可能如下：

// ast.h 中定义节点类型 class BinaryOpNode : public ASTNode { public: std::string op; // "+", "-", "*", "/" std::unique_ptr<ASTNode> left; std::unique_ptr<ASTNode> right; // ... 构造函数和其他方法 }; // parser.cpp 中的实现 std::unique_ptr<ASTNode> Parser::parseExpr() { // 解析 Term auto leftNode = parseTerm(); // 循环处理后续的 (‘+’|‘-’) Term while (currentToken.type == TokenType::Plus || currentToken.type == TokenType::Minus) { auto opToken = currentToken; // 保存操作符 eat(currentToken.type); // 消费掉操作符Token auto rightNode = parseTerm(); // 创建新的二元操作节点，将之前的左节点作为其左子树 leftNode = std::make_unique<BinaryOpNode>(opToken.lexeme, std::move(leftNode), std::move(rightNode)); } return leftNode; } std::unique_ptr<ASTNode> Parser::parseTerm() { // 实现类似，处理 ‘*’ 和 ‘/’ auto leftNode = parseFactor(); while (currentToken.type == TokenType::Multiply || currentToken.type == TokenType::Divide) { auto opToken = currentToken; eat(currentToken.type); auto rightNode = parseFactor(); leftNode = std::make_unique<BinaryOpNode>(opToken.lexeme, std::move(leftNode), std::move(rightNode)); } return leftNode; } std::unique_ptr<ASTNode> Parser::parseFactor() { std::unique_ptr<ASTNode> node; if (currentToken.type == TokenType::Identifier) { node = std::make_unique<VarNode>(currentToken.lexeme); eat(TokenType::Identifier); } else if (currentToken.type == TokenType::Number) { node = std::make_unique<NumNode>(std::stoi(currentToken.lexeme)); eat(TokenType::Number); } else if (currentToken.type == TokenType::LeftParen) { eat(TokenType::LeftParen); node = parseExpr(); // 递归调用 parseExpr eat(TokenType::RightParen); // 必须匹配右括号 } else { // 报告语法错误：期望标识符、数字或左括号 reportSyntaxError("Expected identifier, number or '('"); } return node; }

关键设计与踩坑点：

1. Token的预读（Lookahead）：Parser类需要维护一个currentToken成员变量，它总是代表当前待处理的Token。eat(TokenType type)函数负责消费当前Token，并调用Lexer获取下一个Token更新currentToken。在parseExpr的while循环中，我们正是通过查看currentToken来判断是否继续。
2. 错误恢复：简单的reportSyntaxError并退出对实验来说可能足够，但一个健壮的解析器应尝试进行错误恢复。例如，在parseFactor中遇到意外Token时，可以跳过一些Token直到遇到一个同步Token（如;、}），然后返回一个nullptr或错误节点，让上层函数决定是否继续。这能让你一次运行发现多个语法错误。
3. AST节点的所有权管理：使用std::unique_ptr<ASTNode>可以清晰地表达节点所有权的转移关系。当parseTerm返回一个节点时，所有权转移给调用者。在创建BinaryOpNode时，通过std::move将左右子树的所有权转移给新节点。这完全避免了手动new/delete可能带来的内存泄漏问题。
4. 左结合性的实现：注意上面parseExpr的写法，它天然地实现了左结合性。1 + 2 + 3会被解析为((1 + 2) + 3)。如果你错误地写成先递归调用parseExpr再处理当前操作符，就会变成右结合，导致计算顺序错误。

4. 抽象语法树（AST）的设计与构建

AST是语法分析的核心产出物，它是源代码语法结构的抽象表示，去掉了诸如分号、括号等不直接影响程序语义的细节，只保留关键的操作符、操作数和结构信息。一个设计良好的AST是后续语义分析、中间代码生成的基础。

4.1 AST节点的类层次结构设计

通常采用面向对象的多态来设计AST节点。定义一个基类ASTNode，然后为每种语法结构派生一个具体的节点类。

// include/compiler/ast.h #pragma once #include <string> #include <memory> #include <vector> namespace compiler { namespace ast { class ASTNode { public: virtual ~ASTNode() = default; // 一个通用的访问接口，用于后续的遍历（如打印、语义检查） virtual void accept(class ASTVisitor& visitor) = 0; }; // 字面量节点 class NumberLiteral : public ASTNode { public: int value; explicit NumberLiteral(int val) : value(val) {} void accept(ASTVisitor& visitor) override; }; class Identifier : public ASTNode { public: std::string name; explicit Identifier(const std::string& id) : name(id) {} void accept(ASTVisitor& visitor) override; }; // 二元操作节点 class BinaryOperation : public ASTNode { public: std::string op; // "+", "-", "*", "/", "==", "<", etc. std::unique_ptr<ASTNode> lhs; std::unique_ptr<ASTNode> rhs; BinaryOperation(std::string opStr, std::unique_ptr<ASTNode> left, std::unique_ptr<ASTNode> right) : op(std::move(opStr)), lhs(std::move(left)), rhs(std::move(right)) {} void accept(ASTVisitor& visitor) override; }; // 赋值语句节点 class Assignment : public ASTNode { public: std::unique_ptr<Identifier> var; std::unique_ptr<ASTNode> value; Assignment(std::unique_ptr<Identifier> id, std::unique_ptr<ASTNode> val) : var(std::move(id)), value(std::move(val)) {} void accept(ASTVisitor& visitor) override; }; // If语句节点 class IfStatement : public ASTNode { public: std::unique_ptr<ASTNode> condition; std::unique_ptr<ASTNode> thenBranch; std::unique_ptr<ASTNode> elseBranch; // 可能为nullptr IfStatement(std::unique_ptr<ASTNode> cond, std::unique_ptr<ASTNode> thenBr, std::unique_ptr<ASTNode> elseBr = nullptr) : condition(std::move(cond)), thenBranch(std::move(thenBr)), elseBranch(std::move(elseBr)) {} void accept(ASTVisitor& visitor) override; }; // 语句块节点 class Block : public ASTNode { public: std::vector<std::unique_ptr<ASTNode>> statements; void accept(ASTVisitor& visitor) override; }; // 访问者模式基类 class ASTVisitor { public: virtual ~ASTVisitor() = default; virtual void visit(NumberLiteral& node) = 0; virtual void visit(Identifier& node) = 0; virtual void visit(BinaryOperation& node) = 0; virtual void visit(Assignment& node) = 0; virtual void visit(IfStatement& node) = 0; virtual void visit(Block& node) = 0; }; } // namespace ast } // namespace compiler

设计考量：

• 使用std::unique_ptr：明确父子节点的所有权关系，子节点随父节点销毁而销毁，生命周期管理简单清晰。
• 访问者模式（Visitor Pattern）：这是处理AST遍历和操作的经典模式。它为AST节点结构和在这些结构上执行的操作之间提供了松耦合。你可以为不同的任务（如打印AST、类型检查、代码生成）创建不同的Visitor子类，而无需修改节点类本身。这比在每个节点类里添加print(),typeCheck()等方法要优雅和可扩展得多。
• 节点类型的粒度：BinaryOperation节点同时用于算术和关系运算，通过op字段区分。这简化了节点类型，但可能在语义分析阶段需要额外判断。你也可以选择拆分成ArithmeticOp和RelationalOp。

4.2 在语法分析过程中构建AST

构建AST的过程与递归下降解析过程是深度交织的。每个解析函数（如parseExpr,parseStmt）在成功匹配语法规则后，不再只是返回true/false，而是返回一个构造好的std::unique_ptr<ASTNode>。

以解析赋值语句为例：

std::unique_ptr<ast::ASTNode> Parser::parseAssignmentStmt() { // 当前Token应该是标识符 if (currentToken.type != TokenType::Identifier) { reportSyntaxError("Expected identifier for assignment"); return nullptr; } auto id = std::make_unique<ast::Identifier>(currentToken.lexeme); eat(TokenType::Identifier); // 消费 ‘=’ if (currentToken.type != TokenType::Assign) { reportSyntaxError("Expected '=' after identifier"); return nullptr; } eat(TokenType::Assign); // 解析等号右边的表达式 auto expr = parseExpr(); // 消费 ‘;’ if (currentToken.type != TokenType::Semicolon) { reportSyntaxError("Expected ';' after expression"); return nullptr; } eat(TokenType::Semicolon); // 构建并返回Assignment节点 return std::make_unique<ast::Assignment>(std::move(id), std::move(expr)); }

构建时的常见问题：

1. 悬空指针与移动语义：注意std::move的使用。当将id和expr的所有权传递给Assignment节点后，原来的id和expr指针就变为空。这是正确的，避免了双重释放。
2. 错误处理与AST完整性：在遇到语法错误时，除了报告错误，还要决定返回什么。返回nullptr是一种方式，但上层调用者需要能处理这种情况。更复杂的错误恢复策略可能会创建一种特殊的ErrorNode并插入到AST中，以便后续阶段能收集所有错误。

5. 测试驱动开发与调试技巧

“我的解析器能跑，但结果不对”是实验中最常见的情况。建立一个系统化的测试和调试流程，比盲目修改代码高效得多。

5.1 编写单元测试

不要只依赖一个庞大的main.cpp和手动输入。为你的Lexer和Parser编写单元测试。使用像Catch2、Google Test这样的测试框架会让这件事变得简单。

例如，为Parser写一个测试：

// tests/test_parser.cpp #define CATCH_CONFIG_MAIN #include <catch2/catch.hpp> #include "../include/compiler/parser.h" #include "../include/compiler/lexer.h" #include <sstream> TEST_CASE("Parser can parse simple assignment", "[parser]") { std::string input = "x = 42;"; std::istringstream iss(input); compiler::Lexer lexer(iss); compiler::Parser parser(lexer); auto ast = parser.parseProgram(); // 假设parseProgram返回整个程序的AST根节点 REQUIRE(ast != nullptr); // 进一步检查AST的结构，例如通过一个PrintVisitor输出字符串进行比较 }

如何组织测试：

1. 从简单到复杂：先测单个数字、标识符，再测简单表达式，然后测赋值，最后测if-else和嵌套块。
2. 测试边界和错误情况：特意构造缺少分号、括号不匹配、操作符错误的输入，确保你的解析器能给出合理（而非崩溃）的错误信息。
3. 自动化：在CMakeLists.txt中配置好测试目标，使得每次构建后可以一键运行所有测试。

5.2 可视化调试：打印AST

实现一个简单的PrintVisitor，以缩进或树形结构打印AST，这是最直观的调试手段。

// src/print_visitor.cpp class PrintVisitor : public ast::ASTVisitor { int indentLevel = 0; std::ostream& out; void printIndent() { for (int i = 0; i < indentLevel; ++i) out << " "; } public: explicit PrintVisitor(std::ostream& os) : out(os) {} void visit(ast::NumberLiteral& node) override { printIndent(); out << "Number(" << node.value << ")\n"; } void visit(ast::Identifier& node) override { printIndent(); out << "Identifier(" << node.name << ")\n"; } void visit(ast::BinaryOperation& node) override { printIndent(); out << "BinaryOp(" << node.op << ")\n"; indentLevel++; node.lhs->accept(*this); node.rhs->accept(*this); indentLevel--; } void visit(ast::Assignment& node) override { printIndent(); out << "Assignment\n"; indentLevel++; node.var->accept(*this); node.value->accept(*this); indentLevel--; } // ... 实现其他节点的visit方法 };

在main函数中解析完程序后，使用PrintVisitor打印AST，你可以清晰地看到解析出的结构是否与预期一致。例如，对于a = 1 + 2 * 3;，你应该看到类似：

Assignment Identifier(a) BinaryOp(+) Number(1) BinaryOp(*) Number(2) Number(3)

这能立刻帮你判断操作符优先级和结合性是否正确。

5.3 使用调试器深入跟踪

当测试失败或打印结果异常时，不要只是盯着代码看。使用GDB（或IDE集成的调试器）设置断点，单步跟踪解析过程。

• 关键断点：设在各个parseXXX函数的入口和返回处。
• 观察变量：重点关注currentToken的内容，以及递归调用栈的深度。常见的bug包括：
  • Token消费遗漏或多余：在某个分支忘记调用eat，或者在错误恢复时多跳过了Token。
  • 递归深度爆炸：通常是由于左递归未消除，或递归结束条件有误，导致栈溢出。
  • AST节点链接错误：在构建复杂节点（如IfStatement）时，thenBranch或elseBranch指针可能被错误地赋值或移动。

6. 进阶挑战与扩展思考

完成基础要求后，如果你有余力，可以尝试以下扩展，这能让你对编译器的理解更深一层。

6.1 错误恢复与错误信息友好化

基础的解析器在遇到第一个语法错误时就可能停止。实现一个简单的恐慌模式（Panic Mode）错误恢复：

1. 当在某个非终结符（如parseStmt）中遇到意外Token时，不要立即退出。
2. 定义一个该非终结符的同步Token集合（例如对于语句，同步Token可以是;或}）。
3. 不断从输入中丢弃Token，直到遇到一个同步Token或文件结束。
4. 然后尝试从该点继续解析。这样能报告同一源文件中的多个错误。

同时，努力让错误信息更具可读性。不仅报告“在第5行遇到语法错误”，最好能指出“在第5行，期望一个表达式，但遇到了‘}’”。

6.2 符号表的初步集成

虽然Lab. 2的主要焦点是语法分析，但你可以提前为Lab. 3（语义分析）做准备。在解析过程中，当遇到变量声明（如果你的语言有）或变量使用时，可以尝试将其名称插入一个简单的符号表（std::unordered_map<std::string, SymbolInfo>）或进行查询。这可以用于实现一些简单的语义检查，比如“变量使用前是否已声明”（如果语言要求先声明后使用）。即使不报错，构建一个记录所有标识符出现位置的符号表，对后续实验也是极好的铺垫。

6.3 支持更复杂的语法结构

尝试扩展你的文法，支持while循环、for循环，甚至简单的函数定义和调用。这需要你设计新的AST节点类型，并修改解析器。思考：

• while循环的AST节点需要包含condition和body。
• for循环可以解析为init、condition、update和body四个部分，或者考虑将其脱糖（desugar）为等价的while循环形式。
• 函数调用foo(1, x+2)可以设计为一个CallExpr节点，包含被调函数名和一个参数表达式列表。

这个过程会让你深刻体会到，设计一门语言的语法和其AST表示是一项需要精心权衡的工作。