从实验报告到可复用项目用CMake重构预测分析语法分析器记得第一次完成编译原理实验时那种能跑就行的代码现在想来简直不堪回首。全局变量散落各处所有功能挤在单个cpp文件里测试用例直接写在main函数中——这大概是许多同学实验代码的常态。本文将分享如何将一个典型的课程实验代码重构为符合现代C工程标准的项目重点介绍CMake项目组织、类封装设计、STL容器优化和单元测试实践。1. 从单文件到模块化CMake项目结构设计原始实验代码通常将所有内容堆砌在单个cpp文件中这种结构对于小型实验尚可接受但当代码量增长到数百行时就会变得难以维护。我们首先用CMake建立合理的项目结构predictive-parser/ ├── CMakeLists.txt ├── include/ │ ├── grammar.h │ ├── parser.h │ └── symbol.h ├── src/ │ ├── grammar.cpp │ ├── parser.cpp │ ├── symbol.cpp │ └── main.cpp └── tests/ ├── CMakeLists.txt └── parser_test.cpp对应的顶层CMakeLists.txt关键配置cmake_minimum_required(VERSION 3.15) project(PredictiveParser LANGUAGES CXX) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) add_library(parser_lib src/grammar.cpp src/parser.cpp src/symbol.cpp ) target_include_directories(parser_lib PUBLIC include) add_executable(parser_main src/main.cpp) target_link_libraries(parser_main PRIVATE parser_lib) enable_testing() add_subdirectory(tests)这种结构带来几个显著优势编译隔离修改实现文件(.cpp)不会引起不必要的头文件重新编译清晰的接口头文件成为模块的自然文档可测试性库目标可以轻松链接到测试程序提示在CLion等IDE中这种结构会自动生成对应的项目视图使代码导航更加直观2. 从过程式到面向对象核心类的设计与封装原始实验代码通常使用松散的结构体和全局函数我们将这些元素封装为具有明确职责的类2.1 Grammar类设计class Grammar { public: explicit Grammar(std::istream rule_input); const std::unordered_setchar non_terminals() const; const std::unordered_setchar terminals() const; const std::vectorProduction productions() const; char epsilon() const { return epsilon_; } char start_symbol() const { return start_symbol_; } private: std::unordered_setchar non_terminals_; std::unordered_setchar terminals_; std::vectorProduction productions_; char epsilon_; char start_symbol_; };关键改进封装性所有数据成员私有通过方法暴露必要接口资源管理使用istream作为输入不限定于特定文件格式明确的常量epsilon和start_symbol作为类不变式2.2 PredictiveParser类设计class PredictiveParser { public: explicit PredictiveParser(const Grammar grammar); bool parse(const std::string input); const auto first_sets() const { return first_sets_; } const auto follow_sets() const { return follow_sets_; } const auto parse_table() const { return parse_table_; } private: void build_first_sets(); void build_follow_sets(); void build_parse_table(); const Grammar grammar_; std::unordered_mapchar, SymbolSet first_sets_; std::unordered_mapchar, SymbolSet follow_sets_; ParseTable parse_table_; };这个设计体现了几个重要原则单一职责解析器只负责分析过程不处理文法定义不变式保护通过const引用持有Grammar避免意外修改计算延迟FIRST/FOLLOW集和预测表在构造时自动构建3. 性能优化STL容器的选择与应用原始实现中的数据结构选择往往不够考究我们通过合理选择STL容器获得更好的性能3.1 预测分析表的数据结构原始代码使用unordered_mapuint16_t, int来存储产生式索引这种设计有两个问题键值压缩/解压带来额外开销无法直接表达无产生式的情况改进方案using ParseTable std::unordered_map char, std::unordered_mapchar, std::optionalProduction ; // 查询示例 if (auto it parse_table_.find(non_terminal); it ! parse_table_.end()) { if (auto prod it-second.find(terminal); prod ! it-second.end()) { return prod-second; // 返回optionalProduction } } return std::nullopt;这种设计具有更好的表达性和类型安全性同时保持了O(1)的查询复杂度。3.2 FIRST/FOLLOW集的存储优化原始实现为每个符号维护独立的结构体我们改为使用嵌套的unordered_mapstruct SymbolSet { std::unordered_setchar symbols; bool contains_epsilon{false}; }; using SymbolSets std::unordered_mapchar, SymbolSet; // 使用示例 bool has_empty_production first_sets_[non_terminal].contains_epsilon; for (char terminal : first_sets_[symbol].symbols) { // 处理每个终结符 }这种结构减少了内存碎片同时保持了高效的集合操作性能。4. 质量保障单元测试与持续集成实验代码通常缺乏系统测试我们引入Google Test框架建立自动化测试体系4.1 测试夹具设计class PredictiveParserTest : public ::testing::Test { protected: void SetUp() override { std::stringstream rules; rules EATBF\n*()i\nE TA\nA TA\nA $\nT FB\nB *FB\nB $\nF (E)\nF i; grammar_ std::make_uniqueGrammar(rules); parser_ std::make_uniquePredictiveParser(*grammar_); } std::unique_ptrGrammar grammar_; std::unique_ptrPredictiveParser parser_; };4.2 关键测试案例TEST_F(PredictiveParserTest, FirstSetsCalculation) { const auto first parser_-first_sets(); // 验证终结符的FIRST集 EXPECT_EQ(first.at().symbols, std::unordered_set{}); // 验证非终结符的FIRST集 EXPECT_EQ(first.at(F).symbols, std::unordered_set{(, i}); // 验证包含ε的情况 EXPECT_TRUE(first.at(A).contains_epsilon); } TEST_F(PredictiveParserTest, ParseValidInput) { EXPECT_TRUE(parser_-parse(i*ii)); EXPECT_TRUE(parser_-parse((ii)*i)); } TEST_F(PredictiveParserTest, ParseInvalidInput) { EXPECT_FALSE(parser_-parse(i**i)); EXPECT_FALSE(parser_-parse((i*k))); }4.3 集成CLion与CMake在tests/CMakeLists.txt中添加find_package(GTest REQUIRED) add_executable(parser_tests parser_test.cpp ) target_link_libraries(parser_tests PRIVATE parser_lib GTest::GTest GTest::Main ) include(GoogleTest) gtest_discover_tests(parser_tests)这样在CLion中可以直接运行和调试测试测试结果会集成在IDE的测试窗口中。5. 工程化扩展从实验到实用工具完成基本重构后我们可以进一步扩展项目功能使其成为真正可复用的语法分析工具5.1 错误处理与诊断class ParseError : public std::runtime_error { public: ParseError(size_t pos, char expected, char actual) : runtime_error(format_message(pos, expected, actual)), position_(pos), expected_(expected), actual_(actual) {} size_t position() const { return position_; } char expected() const { return expected_; } char actual() const { return actual_; } private: static std::string format_message(size_t pos, char expected, char actual) { std::ostringstream oss; oss Parse error at position pos : expected expected , got actual ; return oss.str(); } size_t position_; char expected_; char actual_; };5.2 语法树生成class SyntaxNode { public: explicit SyntaxNode(char symbol) : symbol_(symbol) {} void add_child(std::unique_ptrSyntaxNode child) { children_.push_back(std::move(child)); } void print(std::ostream os, size_t indent 0) const { os std::string(indent, ) symbol_ \n; for (const auto child : children_) { child-print(os, indent 2); } } private: char symbol_; std::vectorstd::unique_ptrSyntaxNode children_; };5.3 命令行界面使用CLI11库添加友好的命令行接口#include CLI/CLI.hpp int main(int argc, char** argv) { CLI::App app{Predictive Parser for LL(1) Grammars}; std::string grammar_file; app.add_option(-g,--grammar, grammar_file, Grammar rule file) -required() -check(CLI::ExistingFile); std::string input_file; app.add_option(-i,--input, input_file, Input string file) -check(CLI::ExistingFile); bool show_tree{false}; app.add_flag(-t,--tree, show_tree, Show syntax tree); CLI11_PARSE(app, argc, argv); std::ifstream grammar_stream(grammar_file); Grammar grammar(grammar_stream); PredictiveParser parser(grammar); if (!input_file.empty()) { std::ifstream input_stream(input_file); std::string input(std::istreambuf_iteratorchar{input_stream}, {}); try { bool result parser.parse(input); std::cout Parse result: (result ? success : failure) \n; } catch (const ParseError e) { std::cerr e.what() \n; return EXIT_FAILURE; } } return EXIT_SUCCESS; }重构过程中最深刻的体会是良好的工程实践不是负担而是长期维护的保障。当项目结构清晰、职责分明时添加新功能或调试问题都变得事半功倍。特别是引入单元测试后修改代码时有了可靠的回归保障这种信心是原始实验代码无法提供的。
从实验报告到可复用项目：我用CMake重构了一个预测分析语法分析器
发布时间：2026/6/6 12:51:30
从实验报告到可复用项目用CMake重构预测分析语法分析器记得第一次完成编译原理实验时那种能跑就行的代码现在想来简直不堪回首。全局变量散落各处所有功能挤在单个cpp文件里测试用例直接写在main函数中——这大概是许多同学实验代码的常态。本文将分享如何将一个典型的课程实验代码重构为符合现代C工程标准的项目重点介绍CMake项目组织、类封装设计、STL容器优化和单元测试实践。1. 从单文件到模块化CMake项目结构设计原始实验代码通常将所有内容堆砌在单个cpp文件中这种结构对于小型实验尚可接受但当代码量增长到数百行时就会变得难以维护。我们首先用CMake建立合理的项目结构predictive-parser/ ├── CMakeLists.txt ├── include/ │ ├── grammar.h │ ├── parser.h │ └── symbol.h ├── src/ │ ├── grammar.cpp │ ├── parser.cpp │ ├── symbol.cpp │ └── main.cpp └── tests/ ├── CMakeLists.txt └── parser_test.cpp对应的顶层CMakeLists.txt关键配置cmake_minimum_required(VERSION 3.15) project(PredictiveParser LANGUAGES CXX) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) add_library(parser_lib src/grammar.cpp src/parser.cpp src/symbol.cpp ) target_include_directories(parser_lib PUBLIC include) add_executable(parser_main src/main.cpp) target_link_libraries(parser_main PRIVATE parser_lib) enable_testing() add_subdirectory(tests)这种结构带来几个显著优势编译隔离修改实现文件(.cpp)不会引起不必要的头文件重新编译清晰的接口头文件成为模块的自然文档可测试性库目标可以轻松链接到测试程序提示在CLion等IDE中这种结构会自动生成对应的项目视图使代码导航更加直观2. 从过程式到面向对象核心类的设计与封装原始实验代码通常使用松散的结构体和全局函数我们将这些元素封装为具有明确职责的类2.1 Grammar类设计class Grammar { public: explicit Grammar(std::istream rule_input); const std::unordered_setchar non_terminals() const; const std::unordered_setchar terminals() const; const std::vectorProduction productions() const; char epsilon() const { return epsilon_; } char start_symbol() const { return start_symbol_; } private: std::unordered_setchar non_terminals_; std::unordered_setchar terminals_; std::vectorProduction productions_; char epsilon_; char start_symbol_; };关键改进封装性所有数据成员私有通过方法暴露必要接口资源管理使用istream作为输入不限定于特定文件格式明确的常量epsilon和start_symbol作为类不变式2.2 PredictiveParser类设计class PredictiveParser { public: explicit PredictiveParser(const Grammar grammar); bool parse(const std::string input); const auto first_sets() const { return first_sets_; } const auto follow_sets() const { return follow_sets_; } const auto parse_table() const { return parse_table_; } private: void build_first_sets(); void build_follow_sets(); void build_parse_table(); const Grammar grammar_; std::unordered_mapchar, SymbolSet first_sets_; std::unordered_mapchar, SymbolSet follow_sets_; ParseTable parse_table_; };这个设计体现了几个重要原则单一职责解析器只负责分析过程不处理文法定义不变式保护通过const引用持有Grammar避免意外修改计算延迟FIRST/FOLLOW集和预测表在构造时自动构建3. 性能优化STL容器的选择与应用原始实现中的数据结构选择往往不够考究我们通过合理选择STL容器获得更好的性能3.1 预测分析表的数据结构原始代码使用unordered_mapuint16_t, int来存储产生式索引这种设计有两个问题键值压缩/解压带来额外开销无法直接表达无产生式的情况改进方案using ParseTable std::unordered_map char, std::unordered_mapchar, std::optionalProduction ; // 查询示例 if (auto it parse_table_.find(non_terminal); it ! parse_table_.end()) { if (auto prod it-second.find(terminal); prod ! it-second.end()) { return prod-second; // 返回optionalProduction } } return std::nullopt;这种设计具有更好的表达性和类型安全性同时保持了O(1)的查询复杂度。3.2 FIRST/FOLLOW集的存储优化原始实现为每个符号维护独立的结构体我们改为使用嵌套的unordered_mapstruct SymbolSet { std::unordered_setchar symbols; bool contains_epsilon{false}; }; using SymbolSets std::unordered_mapchar, SymbolSet; // 使用示例 bool has_empty_production first_sets_[non_terminal].contains_epsilon; for (char terminal : first_sets_[symbol].symbols) { // 处理每个终结符 }这种结构减少了内存碎片同时保持了高效的集合操作性能。4. 质量保障单元测试与持续集成实验代码通常缺乏系统测试我们引入Google Test框架建立自动化测试体系4.1 测试夹具设计class PredictiveParserTest : public ::testing::Test { protected: void SetUp() override { std::stringstream rules; rules EATBF\n*()i\nE TA\nA TA\nA $\nT FB\nB *FB\nB $\nF (E)\nF i; grammar_ std::make_uniqueGrammar(rules); parser_ std::make_uniquePredictiveParser(*grammar_); } std::unique_ptrGrammar grammar_; std::unique_ptrPredictiveParser parser_; };4.2 关键测试案例TEST_F(PredictiveParserTest, FirstSetsCalculation) { const auto first parser_-first_sets(); // 验证终结符的FIRST集 EXPECT_EQ(first.at().symbols, std::unordered_set{}); // 验证非终结符的FIRST集 EXPECT_EQ(first.at(F).symbols, std::unordered_set{(, i}); // 验证包含ε的情况 EXPECT_TRUE(first.at(A).contains_epsilon); } TEST_F(PredictiveParserTest, ParseValidInput) { EXPECT_TRUE(parser_-parse(i*ii)); EXPECT_TRUE(parser_-parse((ii)*i)); } TEST_F(PredictiveParserTest, ParseInvalidInput) { EXPECT_FALSE(parser_-parse(i**i)); EXPECT_FALSE(parser_-parse((i*k))); }4.3 集成CLion与CMake在tests/CMakeLists.txt中添加find_package(GTest REQUIRED) add_executable(parser_tests parser_test.cpp ) target_link_libraries(parser_tests PRIVATE parser_lib GTest::GTest GTest::Main ) include(GoogleTest) gtest_discover_tests(parser_tests)这样在CLion中可以直接运行和调试测试测试结果会集成在IDE的测试窗口中。5. 工程化扩展从实验到实用工具完成基本重构后我们可以进一步扩展项目功能使其成为真正可复用的语法分析工具5.1 错误处理与诊断class ParseError : public std::runtime_error { public: ParseError(size_t pos, char expected, char actual) : runtime_error(format_message(pos, expected, actual)), position_(pos), expected_(expected), actual_(actual) {} size_t position() const { return position_; } char expected() const { return expected_; } char actual() const { return actual_; } private: static std::string format_message(size_t pos, char expected, char actual) { std::ostringstream oss; oss Parse error at position pos : expected expected , got actual ; return oss.str(); } size_t position_; char expected_; char actual_; };5.2 语法树生成class SyntaxNode { public: explicit SyntaxNode(char symbol) : symbol_(symbol) {} void add_child(std::unique_ptrSyntaxNode child) { children_.push_back(std::move(child)); } void print(std::ostream os, size_t indent 0) const { os std::string(indent, ) symbol_ \n; for (const auto child : children_) { child-print(os, indent 2); } } private: char symbol_; std::vectorstd::unique_ptrSyntaxNode children_; };5.3 命令行界面使用CLI11库添加友好的命令行接口#include CLI/CLI.hpp int main(int argc, char** argv) { CLI::App app{Predictive Parser for LL(1) Grammars}; std::string grammar_file; app.add_option(-g,--grammar, grammar_file, Grammar rule file) -required() -check(CLI::ExistingFile); std::string input_file; app.add_option(-i,--input, input_file, Input string file) -check(CLI::ExistingFile); bool show_tree{false}; app.add_flag(-t,--tree, show_tree, Show syntax tree); CLI11_PARSE(app, argc, argv); std::ifstream grammar_stream(grammar_file); Grammar grammar(grammar_stream); PredictiveParser parser(grammar); if (!input_file.empty()) { std::ifstream input_stream(input_file); std::string input(std::istreambuf_iteratorchar{input_stream}, {}); try { bool result parser.parse(input); std::cout Parse result: (result ? success : failure) \n; } catch (const ParseError e) { std::cerr e.what() \n; return EXIT_FAILURE; } } return EXIT_SUCCESS; }重构过程中最深刻的体会是良好的工程实践不是负担而是长期维护的保障。当项目结构清晰、职责分明时添加新功能或调试问题都变得事半功倍。特别是引入单元测试后修改代码时有了可靠的回归保障这种信心是原始实验代码无法提供的。
模式的完整流程)
