简介一套涵盖C源程序压缩与解压、自动机、文法问题处理器及TINY扩充语言语法树生成的编译原理课程设计项目包面向计算机相关专业学生、教师及编译原理自学者可作为课程作业、毕业设计或项目初期的完整参考。压缩包共272个文件约72.55MB包含C源码.cpp、头文件.h、可执行程序.exe、动态链接库.dll、TINY语言样例.tny、实验报告与文档.docx/.pdf及演示图片.png等源码、文档、二进制样例分层存放便于按模块检索对照学习。当前已有143人学习下载。全部代码经过运行测试功能正常答辩评审平均分达96分适合基础薄弱者对照调试除了完整源代码、文档说明与实验报告还整理了语法树生成、自动机处理等关键模块的测试数据下载后可按需修改扩展用于其他编译原理课题或课设演练。1. 这个编译原理作业到底在做什么压缩、自动机、文法处理器和TINY其实是一条链一份典型的编译原理作业往往会凑齐这么几样C源程序的压缩与解压、自动机的设计与实现、文法问题处理器、TINY扩充语言的语法树生成外加文档说明、实验报告和可执行程序。乍看是五个独立小任务实际上是一条完整的编译器前置链路压缩器本质上是词法分析器的状态机雏形文法处理器为语法分析扫掉左递归和冲突TINY语法树则是整条流水线的最终产出。适合正在赶课程作业、准备复试上机或者想拿一个“有源码、有报告、能运行”的完整项目当模板的读者。这篇笔记不打算讲教科书式的编译原理而是按我实际做这类作业的顺序把每个模块怎么设计、参数怎么定、坑在哪一次说清楚。2. C源程序压缩与解压用状态机做词法级压缩用行号映射做可逆还原2.1 作业里的“压缩”不是ZIP而是把C源文件压成“仅保留Token”不少第一次做这个题的同学会理解成用 Huffman 或 LZ77 做字节级压缩方向直接就偏了。编译原理作业里的“压缩”目标是把 C 源程序里的注释、空白字符、换行全部去掉同时保留字符串字面量、字符字面量和转义序列的原始内容得到的产物是一个“只含词法有效字符”的紧凑文本。为什么要拿 C 当样本因为 C 的注释有两种//和/* */字符串里有转义符\字符字面量里有反斜杠这些都是训练状态机的天然素材比拿纯文本文件做压缩更能体现编译原理课的意图。压缩之后的文本并不适合人类阅读所以作业还要求“解压”。这里的解压不是把原始文件逐字节还原——那在信息论上做不到因为你已经丢掉了排版信息。解压要做的是把压缩产物恢复成一个可读、可编译、且每个有效字符的行列坐标与原文件一致的代码文本。也就是说压缩时记录行号映射表解压时按映射表重建行号和列号。2.2 压缩器核心带字符串感知的注释剥离状态机压缩器的核心是一个状态机而不是一串正则替换。如果你用正则先把//替换掉再去掉/* */字符串里的a//b会被误删成ab代码语义直接破坏。状态机把当前所处的词法区域分成五种状态普通代码、行注释、块注释、双引号字符串、单引号字符。#include string #include vector #include cctype enum CompileState { CODE, // 普通代码区 LINE_COMMENT, // 行注释 // BLOCK_COMMENT, // 块注释 /* */ STRING, // 双引号字符串 ... CHAR_LITERAL // 单引号字符 ... }; struct SourceMapEntry { int dstPos; // 压缩结果中的字符偏移 int srcLine; // 原文件行号 int srcCol; // 原文件列号 }; std::string compressCpp(const std::string src, std::vectorSourceMapEntry dstMap) { std::string out; CompileState st CODE; size_t i 0; int line 1, col 0; while (i src.size()) { char c src[i]; char n (i 1 src.size()) ? src[i 1] : \0; if (st CODE) { if (c / n /) { st LINE_COMMENT; i 2; continue; } if (c / n *) { st BLOCK_COMMENT; i 2; continue; } if (c ) { st STRING; out c; dstMap.push_back({(int)out.size() - 1, line, col}); i; continue; } if (c \) { st CHAR_LITERAL; out c; dstMap.push_back({(int)out.size() - 1, line, col}); i; continue; } if (!std::isspace(static_castunsigned char(c))) { out c; dstMap.push_back({(int)out.size() - 1, line, col}); } } else if (st LINE_COMMENT) { if (c \n) { st CODE; line; col 0; i; continue; } } else if (st BLOCK_COMMENT) { if (c * n /) { st CODE; i 2; continue; } if (c \n) { line; col 0; i; continue; } } else if (st STRING || st CHAR_LITERAL) { out c; dstMap.push_back({(int)out.size() - 1, line, col}); if (c \\ n ! \0) { out n; dstMap.push_back({(int)out.size() - 1, line, col 1}); i 2; continue; } if ((st STRING c ) || (st CHAR_LITERAL c \)) { st CODE; } } if (c \n) { line; col 0; } else { col; } i; } return out; }这段代码的逻辑说明压缩器从CODE状态开始遇到//进行注释状态遇到/*进步注释状态遇到引号进字符串或字符状态。在字符串状态里如果遇到反斜杠就把反斜杠和下一个字符一起复制避免\被当成字符串结束符。普通状态下的空格、制表符、换行全部丢弃非空白字符原样拷贝并记录它在压缩产物里的位置。这样得到的压缩文本本质上就是一份去掉注释和空白的 Token 序列文本。参数说明dstMap是解压的关键每个有效字符都有一条映射记录。dstPos用out.size() - 1表示当前字符在压缩结果里的下标srcLine和srcCol记录它在原文件中的行列。注意换行计数放在两个地方一处是状态分支内部行注释遇换行恢复状态一处是末尾统一更新行列两处不能漏漏了行号映射就会错位。2.3 解压不是还原原文而是还原可读代码与行号映射解压函数的输入是压缩产物和映射表输出是带换行和缩进的可读文本。做法很简单遍历压缩产物查映射表拿到每个字符在原文件的行列先把行号补齐再把列号补齐然后输出字符。#include algorithm std::string expandCpp(const std::string compressed, const std::vectorSourceMapEntry dstMap) { std::string out; int curLine 1, curCol 0; for (size_t i 0; i compressed.size(); i) { auto it std::lower_bound( dstMap.begin(), dstMap.end(), (int)i, [](const SourceMapEntry e, int pos) { return e.dstPos pos; }); if (it ! dstMap.end() it-dstPos (int)i) { while (curLine it-srcLine) { out \n; curLine; curCol 0; } while (curCol it-srcCol) { out ; curCol; } } out compressed[i]; curCol; } return out; }逻辑说明lower_bound按dstPos查找到当前字符对应原文件坐标随后用换行把当前行号拉到目标行号用空格把列号拉到目标列号。还原结果不追求和原文件排版一致但每个非空白字符的行列坐标与原文件完全一致。实验报告里如果贴“编译报错 line 7, col 10”能直接对上原文件位置。参数说明dstMap必须按dstPos升序排列压缩时push_back天然保证这一点。如果压缩掉的注释跨越几十行解压时会一次性补几十个换行这在作业规模下没有问题。更省空间的做法是只记录“行号变化”而不记录每行的每列但那个实现复杂度会高不少作业阶段用全量映射表最简单可靠。注意这个压缩器没有处理预处理器指令#include和宏定义#会作为普通字符保留。TINY 语言一般没有预处理器所以问题不大如果你要压缩真实 C 工程还需要把#开头的一行整体保留否则宏定义会被拆得七零八落。3. 自动机与词法分析器一张状态迁移表走完C与TINY的词法3.1 为什么手写DFA而不是直接上自动化工具很多同学会问词法分析不是有 Flex 吗为什么还要手写自动机。Flex 生成的代码是一个黑匣子实验报告里要画状态图、贴转移表、说明终态含义这些 Flex 都给不了你。手写 DFA 之后压缩器里的状态机会无缝升级成词法分析器压缩器识别注释和字符串词法分析器识别标识符、数字、运算符和关键字两者共用同一个“当前状态 当前字符 - 下一状态”的框架。答辩时老师问“压缩器和词法分析器什么关系”你可以直接说压缩器是 DFA 的一个受限实例这种回答比“都是状态机”有说服力得多。3.2 状态迁移表与字符分类DFA的C表示词法分析器先把输入字符归类成有限几个类别再用二维数组表示状态迁移表。行是当前状态列是字符类别值是跳转到的下一个状态-1 表示无迁移。enum CharClass { CC_LETTER, CC_DIGIT, CC_OP, CC_SPACE, CC_QUOTE, CC_INVALID }; enum DfaState { S_START, S_ID, S_NUM, S_OP, S_STRING, S_CHAR, S_LINE_COMMENT, S_BLOCK_COMMENT }; int classify(char c) { if (std::isalpha(c) || c _) return CC_LETTER; if (std::isdigit(c)) return CC_DIGIT; if (c || c - || c * || c / ) return CC_OP; if (std::isspace(c)) return CC_SPACE; if (c || c \) return CC_QUOTE; return CC_INVALID; } int trans[8][6] { // LETTER DIGIT OP SPACE QUOTE INVALID { S_ID, S_NUM, S_OP, S_START, S_STRING, -1 }, // S_START { S_ID, S_ID, -1, -1, -1, -1 }, // S_ID { -1, S_NUM, -1, -1, -1, -1 }, // S_NUM { -1, -1, S_OP, -1, -1, -1 }, // S_OP { -1, -1, -1, -1, -1, -1 }, // S_STRING (单独处理) { -1, -1, -1, -1, -1, -1 }, // S_CHAR (单独处理) { -1, -1, -1, -1, -1, -1 }, // S_LINE_COMMENT (单独处理) { -1, -1, -1, -1, -1, -1 }, // S_BLOCK_COMMENT (单独处理) };逻辑说明S_START遇到字母或下划线进S_ID遇到数字进S_NUM遇到运算符进S_OP遇到引号进S_STRING或S_CHAR。S_ID状态里数字可以继续被吸收var1是合法标识符但从S_NUM状态遇到字母必须报错123abc不是合法数字。字符串、字符、注释三个状态没有放进二维表是因为它们需要“看下一个字符”才能判断转义和结束这种向后看逻辑放进表里会让状态数翻倍不划算。参数说明trans表里S_STRING、S_CHAR两行全部是 -1表示这些状态不参与查表迁移而是由驱动循环里的分支处理。作业报告里画状态图时这八个状态都要出现在图上字符串状态的转移条件写明“非引号非反斜杠”即可。这张表还要加一个终态标记数组比如bool isFinal[] {false, true, true, true, true, true, true, true}只有S_ID、S_NUM、S_OP是真正产出 Token 的终态字符串和注释算“路过”的中间态。3.3 Token产出与最长匹配词法分析器驱动循环的核心是“尽可能多地消费字符直到状态无法迁移为止”这就是编译原理里说的最长匹配。struct Token { DfaState type; std::string lexeme; int line, col; }; std::vectorToken lexTiny(const std::string code) { std::vectorToken tokens; size_t i 0; int line 1, col 0; while (i code.size()) { // 跳过空白 if (std::isspace(code[i])) { if (code[i] \n) line; i; col; continue; } DfaState st S_START; std::string lexeme; int startLine line, startCol col; while (i code.size()) { CharClass cc classify(code[i]); int next trans[st][cc]; if (next -1) break; // 无法迁移停止消费 st (DfaState)next; lexeme code[i]; if (code[i] \n) line; i; col; } if (lexeme.empty()) { // 非法字符记录错误并跳过 fprintf(stderr, line %d: unexpected char %c\n, line, code[i]); i; col; continue; } if (st S_ID) { // 先查关键字表命中就是关键字Token否则就是标识符 tokens.push_back({keywords.count(lexeme) ? KW : ID, lexeme, startLine, startCol}); } else if (st S_NUM) { tokens.push_back({NUM, lexeme, startLine, startCol}); } else if (st S_OP) { tokens.push_back({OP, lexeme, startLine, startCol}); } } return tokens; }逻辑说明内层循环的终止条件是“查表得到 -1”。这意味着当前字符无法被刚消费出的词素继续吸收循环退出已经积累的lexeme作为一个完整 Token 输出。对于 TINY 这种小语言-和--的区分需要特别处理如果trans[S_OP][CC_OP]还是S_OP形如会被连成一个 Token。TINY 文法里没有运算符所以这里trans[3][2] S_OP会导致x被识别成x和如果不想这样把trans[S_OP][CC_OP]改成 -1 即可代价是、这种双字符运算符也要单独设计终态。参数说明keywords是一个std::setstd::string运行时查表决定if、then、else、end、repeat、until、read、write、for、to、do这些保留字。这里要注意一个玄学问题C 标准库里没有内置关键字表你需要自己初始化漏一个关键字在语法分析阶段才会暴露前期很难发现。3.4 非法字符处理词法阶段的非法字符比如、#会导致查表迁移失败上面的代码在lexeme.empty()分支里处理打印错误信息跳过这个字符继续分析后面的代码。这种策略叫“错误恢复”比直接终止整个词法分析更实用能让实验报告里展示出多个错误同时被检出的效果。如果要做得更好可以在跳过非法字符后把当前位置当成一个新 Token 的开始重新进入主循环这样abcdef会得到abc和def两个标识符中间夹一条错误记录。4. 文法问题处理器与TINY语法树生成从左递归消除到递归下降AST4.1 文法问题处理器到底处理哪几类问题文法问题处理器这个名字听起来大实际核心就是四件事判断文法是否存在左递归并消除它、提取公共左因子、计算 FIRST 集与 FOLLOW 集、判定文法是否为 LL(1) 文法。这四件事全部是给语法分析器做前置准备的。TINY 语言的文法相对干净stmt - if stmt | repeat stmt | ...天然没有直接左递归但你扩充exp时几乎必然写出exp - exp term这种教科书式左递归处理器就是解决这个问题。作业里最稳妥的交法是一个独立的输入输出程序读入一组产生式输出消除左递归后的产生式、FIRST/FOLLOW 集合、以及 LL(1) 判定结果。4.2 消除左递归直接左递归和间接左递归都逃不掉先看最简单的直接左递归。文法A - A alpha | beta消除结果是A - beta A和A - alpha A | epsilon。代码层面产生式用std::mapchar, std::vectorstd::string表示左部是非终结符字符右部是一个字符串数组每个字符串是一种候选式。#include map #include set #include vector #include string using Grammar std::mapchar, std::vectorstd::string; Grammar eliminateLeftRecursion(Grammar g) { std::vectorchar symbols; for (auto kv : g) symbols.push_back(kv.first); std::mapchar, int idx; for (size_t i 0; i symbols.size(); i) idx[symbols[i]] i; for (size_t i 0; i symbols.size(); i) { char Ai symbols[i]; // 第一步间接左递归替换 for (size_t j 0; j i; j) { char Aj symbols[j]; std::vectorstd::string newRhs; for (const auto rhs : g[Ai]) { if (!rhs.empty() rhs[0] Aj) { for (const auto ajRhs : g[Aj]) { newRhs.push_back(ajRhs rhs.substr(1)); } } else { newRhs.push_back(rhs); } } g[Ai] newRhs; } // 第二步消除直接左递归 A - A alpha | beta std::vectorstd::string alpha, beta; for (const auto rhs : g[Ai]) { if (!rhs.empty() rhs[0] Ai) { alpha.push_back(rhs.substr(1)); } else { beta.push_back(rhs); } } if (alpha.empty()) continue; // 生成新非终结符作业里用 ASCII 倒退找空位 char newNt Z; while (g.count(newNt)) newNt--; newNt A (symbols.size() 1); // 或者用名字池更稳妥 std::vectorstd::string newA; for (auto b : beta) newA.push_back(b newNt); g[Ai] newA; std::vectorstd::string newNtRhs; for (auto a : alpha) newNtRhs.push_back(a newNt); newNtRhs.push_back(); // epsilon 用空串表示 g[newNt] newNtRhs; } return g; }逻辑说明间接左递归A - B alphaB - A beta比直接左递归隐蔽得多。处理办法是先给所有非终结符按出现顺序编号然后扫描产生式对于A_i - A_j gamma且j i的情况把A_j的所有候选式展开替换进A_i的右部。这样替换之后左递归只可能表现为“首符是自己”的直接形式再用第二步消除。参数说明外层循环结束后字母表扩张会产生新的非终结符代码里用A (symbols.size() 1)生成ASCII 越界风险只会在 20 个以上非终结符时出现作业规模一般没问题。如果想做得严谨用一个字符串名字池Ai_1、Ai_2替换单字符是标准做法。空串表示 epsilon后续 FIRST/FOLLOW 计算里要专门识别。4.3 FIRST与FOLLOW集的不动点计算FIRST 集合的计算代码是编译原理课的经典不动点迭代逻辑非常固定。std::mapchar, std::setchar computeFirst(const Grammar g) { std::mapchar, std::setchar first; for (auto kv : g) first[kv.first] {}; bool changed true; while (changed) { changed false; for (auto kv : g) { char A kv.first; for (const auto rhs : kv.second) { bool allEps true; for (size_t k 0; k rhs.size(); k) { char X rhs[k]; if (g.count(X)) { // X 是非终结符 size_t old first[A].size(); first[A].insert(first[X].begin(), first[X].end()); if (first[A].size() ! old) changed true; if (!first[X].count( )) { allEps false; break; } } else { // X 是终结符 size_t old first[A].size(); first[A].insert(X); if (first[A].size() ! old) changed true; allEps false; break; } } if (allEps) { size_t old first[A].size(); first[A].insert( ); // epsilon 用空格字符占位 if (first[A].size() ! old) changed true; } } } } return first; }逻辑说明循环停止条件是“所有集合都不再变化”这就是不动点。第一轮迭代时FIRST 集合只包含各产生式右部开头的终结符第二轮开始非终结符的 FIRST 集被传播到其它产生式里直到稳定。allEps表示当前候选式的所有符号都可能推导出空串此时把 epsilon 加入左部非终结符的 FIRST 集。参数说明用 当 epsilon 占位符是偷懒做法打印时要if (s ) std::cout epsilon转换。FOLLOW 集的计算框架和 FIRST 完全一样区别是多了两条规则A - alpha B beta时把 FIRST(beta)除 epsilon 外加入 FOLLOW(B)A - alpha B或 FIRST(beta) 含 epsilon 时把 FOLLOW(A) 加入 FOLLOW(B)。FOLLOW 集初始时开始符号的 FOLLOW 集要加入结束标记$这也是作业报告里最容易漏的一条。4.4 由无左递归文法搭建AST节点语法树生成的前提是 AST 节点要统一、好打印。这里我用一个 Node 结构体而不是类继承体系原因很简单作业只需要建树、遍历、打印三个操作用type字符串区分节点类型就够了。#include iostream #include vector struct Node { std::string type; // Program IfStmt ForStmt AssignStmt Op Num ... std::string value; // 终结符的值变量名、数字、运算符 std::vectorNode* children; // 子节点 }; Node* makeNode(const std::string type, const std::string val ) { Node* n new Node; n-type type; n-value val; return n; }参数说明value只对叶子节点有意义比如Num节点的值是42Op节点的值是。内部节点的value一般留空。内存管理上所有节点用new分配整棵树用完以后递归删除即可作业规模不用担心性能。TINY 扩充语言的文法我一般按这个来program :: stmt_list stmt_list :: stmt ; stmt_list | stmt stmt :: if_stmt | repeat_stmt | for_stmt | assign_stmt | read_stmt | write_stmt if_stmt :: if exp then stmt_list else stmt_list end | if exp then stmt_list end repeat_stmt :: repeat stmt_list until exp assign_stmt :: id : exp read_stmt :: read id write_stmt :: write exp for_stmt :: for id : exp to exp do stmt_list end exp :: term ( term | - term )* term :: factor ( * factor | / factor )* factor :: ( exp ) | number | id这里我给的是已经消除左递归、适合递归下降的版本。exp的写法从exp - exp term改成了exp - term ( term)*等价于教科书里的右递归改写但实现更直观。4.5 递归下降建树一个非终结符一个函数递归下降的核心是“每个非终结符对应一个解析函数函数开头贪婪匹配该非终结符的候选式”。有了文法处理器消除左递归后递归下降不会出现无限递归。Token lookahead; // 当前TokenlexTiny产出的Token流里逐个读取 void advance() { // 从Token流里取下一个Token跳过EOF } void expect(TokenType t) { if (lookahead.type ! t) { fprintf(stderr, line %d: expected %d, got %s\n, lookahead.line, t, lookahead.lexeme.c_str()); throw std::runtime_error(parse error); } advance(); } Node* parseExp() { Node* n parseTerm(); while (lookahead.type OP_PLUS || lookahead.type OP_MINUS) { Node* op makeNode(Op, lookahead.lexeme); advance(); Node* rhs parseTerm(); op-children.push_back(n); // 左操作数 op-children.push_back(rhs); // 右操作数 n op; } return n; } Node* parseTerm() { Node* n parseFactor(); while (lookahead.type OP_MUL || lookahead.type OP_DIV) { Node* op makeNode(Op, lookahead.lexeme); advance(); Node* rhs parseFactor(); op-children.push_back(n); op-children.push_back(rhs); n op; } return n; } Node* parseIf() { Node* n makeNode(IfStmt); expect(KW_IF); n-children.push_back(parseExp()); expect(KW_THEN); n-children.push_back(parseStmtList()); if (lookahead.type KW_ELSE) { advance(); n-children.push_back(parseStmtList()); } expect(KW_END); return n; }逻辑说明parseExp先解析一个term然后看下一个 Token 是不是或-是则把已解析的左子树和新的右子树挂到Op节点下。这种循环写法等价于右递归但不会爆栈而且人类阅读时更容易理解“同一优先级左结合”的语义。parseIf对else的处理是“看到才建分支看不到跳过”TINY 用end关键字终止 if 语句所以悬空 else 问题在文法层面就被绕开了。expect是整条链路里最值得花时间的函数。它负责断言当前 Token 的类型不匹配就抛出带行号的异常。实验报告里贴一张line 5: expected then, got do这样的报错截图比贴十段原理更有说服力。4.6 树形打印与人工核对void printTree(Node* n, int depth) { if (!n) return; for (int i 0; i depth; i) std::cout ; std::cout n-type; if (!n-value.empty()) std::cout ( n-value ); std::cout \n; for (Node* ch : n-children) printTree(ch, depth 1); }逻辑说明打印输出按两空格一层缩进Num(42)、Op()这种叶子节点一目了然。作业报告里要求贴语法树样例的直接截这个输出就行。要注意的是打印前先验证树的整体形状比如a b * c应该打印成以为根、左子树是a、右子树是*的结构如果打印结果相反说明parseExp和parseTerm的调用层级反了这是递归下降最常见的翻车现场。5. 编译原理作业避坑压缩器、文法处理器、语法树最容易翻车的五个地方5.1 字符串字面量里的//被压缩器砍掉现象压缩后的代码里std::string s http://example.com;变成了std::string s http代码无法编译。原因压缩器状态机没有进入字符串状态看到//就把后面的内容当注释剥离了而实际上两个斜杠在字符串字面量内部。解决压缩器的状态机遇到双引号时一定要切换进STRING状态在字符串状态内//和/*都是普通字符。测试用例里必须包含a//b、//、/* not comment */这三种输入压缩解压后逐一对比字符串内容。把这条用例写进实验报告老师会认为你真的考虑过词法边界。5.2 解压后报错行号对不上原文件现象解压出的代码用编译器编译报错说line 3有语法错误打开原文件一看line 3是一行空注释真正的问题在line 17。原因压缩阶段丢弃了所有换行解压如果只按固定格式输出所有有效字符都挤在一行里行号彻底失效。编译器的报错行号定位自然全错。解决压缩时维护SourceMapEntry映射表解压时按映射重建行列。实验报告里可以专门验证写一个在line 10故意留错的测试程序压缩解压后编译器报错行号依然是10。这个验证结果放进报告就是实打实的效果截图。5.3 消除间接左递归时直接跑死循环现象程序运行到eliminateLeftRecursion长时间不返回CPU 占满最后只能强制结束。原因处理间接左递归时没有按非终结符编号排序。A - B alpha、B - A beta两条产生式互相替换第一次把B展开成A beta alpha第二次又把A展开成B alpha beta alpha无限膨胀。解决先把非终结符定一个编号外层循环里只处理A_i - A_j gamma且j i的情况。这样每轮替换都会把右部首符替换成编号更大的符号循环次数有上限不会死循环。代码里的j i条件是核心不是可有可无的优化。5.4 FIRST集合算着算着就不收敛现象实验报告里 FIRST 集的数据每次运行都不一样第一遍FIRST(E) {id, num}第二遍变成{id, num, epsilon}第三遍又变了。原因用递归函数直接计算 FIRST 而不是用不动点迭代非终结符之间的相互依赖导致集合在递归返回时还没完全稳定或者递归出口写错epsilon 被重复传播。解决统一改成while (changed)风格的不动点迭代。每次循环把所有产生式全部扫一遍本轮没有任何集合发生变化才退出。注意 epsilon 的加入条件只有当某个候选式的全部符号都能推导出空串时epsilon 才加入左部非终结符的 FIRST 集。任何一个符号不能推导出 epsilon这个候选式就不能贡献 epsilon。5.5 表达式优先级在AST里串了现象输入a b * c打印出的语法树是(a, *(b, c))正确但改成a * b c后变成*(a, (b, c))优先级反了。原因parseExp里 while 循环直接调parseExp而不是parseTerm导致加法和乘法在同一层递归右结合性被错误地当成了左结合处理。解决严格按文法层级建立函数调用关系parseExp调parseTermparseTerm调parseFactor。加法运算符只能出现在parseExp层乘法运算符只能出现在parseTerm层数字和括号只能出现在parseFactor层。层级对了优先级就对了这是递归下降里少有的“结构即正确”的环节。6. 验收与加分三类验证方法决定这份作业能不能拿优秀作业交之前我习惯跑三组验证每一组都能暴露一类问题。第一组验证压缩解压的可逆性。准备一个test.cpp里面故意包含带//的字符串、带转义引号的字符、横跨三行的块注释压缩后解压逐字符对比原始代码里每个有效字符的行列坐标。这组验证过了压缩器基本稳了。第二组验证文法处理器的正确性。构造一个带直接左递归和间接左递归的小文法跑完处理器后写一个断言函数扫描所有产生式确保没有任何右部以左部非终结符开头同时 FIRST/FOLLOW 集合连续跑五次结果一致。第三组验证 TINY 语法树。写一个覆盖 if、repeat、for、表达式嵌套的测试程序解析后打印 AST人工核对每一层节点归属。write (1 2) * 3;必须打印成*( (1,2), 3)而不是(1, *(2,3))。加分项有两个。一个是给打印函数加一个dot输出模式把 AST 转成 Graphviz 的格式报告里放一张自动生成的状态图或语法树图视觉效果比缩进文本高一档。另一个是让文法处理器输出预测分析表再用这张表驱动一个表驱动的预测分析器把“文法处理器”和“语法树生成”真正串成一条流水线。我就是这么做的先在实验报告里放消除左递归前后的文法对照再放递归下降 AST 打印结果中间用 FIRST/FOLLOW 集合的数据撑起理论部分整个作业的完成度看起来就不是“交差”而是“做得完整”。这个方案适合课程设计也适合复试面试时拿来讲清楚自己处理过什么问题。希望帮到你。本文还有配套的精品资源点击获取