1. 实验概览与核心目标又到了编译原理实验课的时间这次我们面对的是Lab. 2一个承上启下的关键节点。如果说Lab. 1是让你熟悉编译器的“骨架”和基本流程那么Lab. 2就是让你亲手为这个骨架注入“肌肉”和“神经”构建一个真正能处理更复杂语法结构的二代编译器前端。很多同学看到“二代编译器”、“实验说明和要求”这样的标题可能会觉得枯燥但我想说这个实验恰恰是理解编译器如何从“识别单词”进化到“理解句子结构”的绝佳机会。它不再满足于简单的词法分析而是要求你实现一个完整的语法分析器Parser并构建出初步的抽象语法树AST。这个过程本质上是在教会计算机如何按照我们定义的规则文法去理解一段程序代码的层次和逻辑。简单来说这次实验的核心目标有三个第一深入理解上下文无关文法CFG及其在编译器中的核心地位第二掌握递归下降或自顶向下语法分析的基本思想和实现技巧第三亲手实现一个能处理赋值语句、算术表达式、控制流语句如if-else等基本程序结构的语法分析模块并输出结构化的AST。无论你未来是从事底层系统开发、语言工具链研发还是任何需要处理复杂结构化数据的领域这里锻炼出的“结构化思维”和“规则引擎构建”能力都至关重要。接下来我会结合常见的实现路径和踩坑经验带你一步步拆解这个实验。2. 实验环境搭建与工程结构解析工欲善其事必先利其器。在开始编码之前一个清晰、健壮且易于构建的工程环境能让你事半功倍避免后期在文件依赖和编译选项上浪费大量时间。从相关热词如“CMakeLists”、“msvc编译器”、“gnu gcc编译器怎么下载”可以看出工具链的选择和配置是大家的共同关切点。2.1 编译器与构建系统的选择对于编译原理实验我强烈推荐使用Clang/GCC CMake的组合。理由如下标准兼容性好Clang和GCC对现代C标准的支持非常积极能让你使用更清晰、更安全的语法如智能指针、范围for循环来管理AST节点等资源减少内存泄漏的风险。错误信息友好尤其是Clang其报错信息通常比MSVC更清晰能快速定位模板或类型相关的复杂错误这对实现泛型的词法/语法分析器辅助类很有帮助。跨平台性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路径和工具链带来的一些诡异问题。另一种方案是使用WSL2Windows 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标准为C17或更高便于使用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节点容器能极大简化代码并提升安全性。强制使用C17能确保你和助教的环境一致性。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次|表示选择第一步不是编码而是“消化”文法消除左递归上述Expr和Term规则是典型的左递归通过Expr - Expr Term的形式。直接递归下降解析器无法处理左递归会导致无限递归。你需要将其转换为等价的右递归形式。这是必须掌握的基础步骤。提取左公因子如果多个产生式有共同的前缀可能会造成预测分析时的冲突。需要提取公因子以简化预测逻辑。计算FIRST集和FOLLOW集这是为编写预测分析器递归下降或LL(1)分析器做理论准备。手动计算一遍能让你深刻理解分析器在某个非终结符处应该如何根据下一个输入符号lookahead token来决定使用哪个产生式。3.2 递归下降语法分析器设计递归下降是最直观、最适合手工实现的语法分析方法。其核心思想是为文法中的每一个非终结符如Program,Stmt,Expr编写一个对应的函数。这个函数负责从词法分析器Lexer获取Token流并尝试“匹配”该非终结符所对应的语法结构。以解析Expr - Term (( | -) Term)*为例 首先需要将左递归文法Expr - Expr Term | Term改写为右递归Expr - Term ExprExpr - Term Expr | - Term Expr | ε。对应的递归下降函数可能如下// ast.h 中定义节点类型 class BinaryOpNode : public ASTNode { public: std::string op; // , -, *, / std::unique_ptrASTNode left; std::unique_ptrASTNode right; // ... 构造函数和其他方法 }; // parser.cpp 中的实现 std::unique_ptrASTNode 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_uniqueBinaryOpNode(opToken.lexeme, std::move(leftNode), std::move(rightNode)); } return leftNode; } std::unique_ptrASTNode 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_uniqueBinaryOpNode(opToken.lexeme, std::move(leftNode), std::move(rightNode)); } return leftNode; } std::unique_ptrASTNode Parser::parseFactor() { std::unique_ptrASTNode node; if (currentToken.type TokenType::Identifier) { node std::make_uniqueVarNode(currentToken.lexeme); eat(TokenType::Identifier); } else if (currentToken.type TokenType::Number) { node std::make_uniqueNumNode(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; }关键设计与踩坑点Token的预读LookaheadParser类需要维护一个currentToken成员变量它总是代表当前待处理的Token。eat(TokenType type)函数负责消费当前Token并调用Lexer获取下一个Token更新currentToken。在parseExpr的while循环中我们正是通过查看currentToken来判断是否继续。错误恢复简单的reportSyntaxError并退出对实验来说可能足够但一个健壮的解析器应尝试进行错误恢复。例如在parseFactor中遇到意外Token时可以跳过一些Token直到遇到一个同步Token如;、}然后返回一个nullptr或错误节点让上层函数决定是否继续。这能让你一次运行发现多个语法错误。AST节点的所有权管理使用std::unique_ptrASTNode可以清晰地表达节点所有权的转移关系。当parseTerm返回一个节点时所有权转移给调用者。在创建BinaryOpNode时通过std::move将左右子树的所有权转移给新节点。这完全避免了手动new/delete可能带来的内存泄漏问题。左结合性的实现注意上面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_ptrASTNode lhs; std::unique_ptrASTNode rhs; BinaryOperation(std::string opStr, std::unique_ptrASTNode left, std::unique_ptrASTNode 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_ptrIdentifier var; std::unique_ptrASTNode value; Assignment(std::unique_ptrIdentifier id, std::unique_ptrASTNode val) : var(std::move(id)), value(std::move(val)) {} void accept(ASTVisitor visitor) override; }; // If语句节点 class IfStatement : public ASTNode { public: std::unique_ptrASTNode condition; std::unique_ptrASTNode thenBranch; std::unique_ptrASTNode elseBranch; // 可能为nullptr IfStatement(std::unique_ptrASTNode cond, std::unique_ptrASTNode thenBr, std::unique_ptrASTNode 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::vectorstd::unique_ptrASTNode 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_ptrASTNode。以解析赋值语句为例std::unique_ptrast::ASTNode Parser::parseAssignmentStmt() { // 当前Token应该是标识符 if (currentToken.type ! TokenType::Identifier) { reportSyntaxError(Expected identifier for assignment); return nullptr; } auto id std::make_uniqueast::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_uniqueast::Assignment(std::move(id), std::move(expr)); }构建时的常见问题悬空指针与移动语义注意std::move的使用。当将id和expr的所有权传递给Assignment节点后原来的id和expr指针就变为空。这是正确的避免了双重释放。错误处理与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输出字符串进行比较 }如何组织测试从简单到复杂先测单个数字、标识符再测简单表达式然后测赋值最后测if-else和嵌套块。测试边界和错误情况特意构造缺少分号、括号不匹配、操作符错误的输入确保你的解析器能给出合理而非崩溃的错误信息。自动化在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错误恢复当在某个非终结符如parseStmt中遇到意外Token时不要立即退出。定义一个该非终结符的同步Token集合例如对于语句同步Token可以是;或}。不断从输入中丢弃Token直到遇到一个同步Token或文件结束。然后尝试从该点继续解析。这样能报告同一源文件中的多个错误。同时努力让错误信息更具可读性。不仅报告“在第5行遇到语法错误”最好能指出“在第5行期望一个表达式但遇到了‘}’”。6.2 符号表的初步集成虽然Lab. 2的主要焦点是语法分析但你可以提前为Lab. 3语义分析做准备。在解析过程中当遇到变量声明如果你的语言有或变量使用时可以尝试将其名称插入一个简单的符号表std::unordered_mapstd::string, SymbolInfo或进行查询。这可以用于实现一些简单的语义检查比如“变量使用前是否已声明”如果语言要求先声明后使用。即使不报错构建一个记录所有标识符出现位置的符号表对后续实验也是极好的铺垫。6.3 支持更复杂的语法结构尝试扩展你的文法支持while循环、for循环甚至简单的函数定义和调用。这需要你设计新的AST节点类型并修改解析器。思考while循环的AST节点需要包含condition和body。for循环可以解析为init、condition、update和body四个部分或者考虑将其脱糖desugar为等价的while循环形式。函数调用foo(1, x2)可以设计为一个CallExpr节点包含被调函数名和一个参数表达式列表。这个过程会让你深刻体会到设计一门语言的语法和其AST表示是一项需要精心权衡的工作。