LL(1)语法分析器实现：从消除左递归到预测分析表与分析栈

简介：这份语法分析实验文档面向编译原理课程学习者与需要完成课程设计的学生，围绕算术表达式的语法检查与结构分析，给出从文法定义到程序实现的完整实验方案。文档共1个doc文件，压缩包约127KB，篇幅集中、便于查阅与打印。内容覆盖实验目的、算术表达式简化子集的BNF描述、LL(1)文法改写、预测分析表构造，以及C++源程序中的分析栈与剩余串输出、RIGHT/ERROR判定和典型错例测试；同时说明将词法分析与语法分析合并为完整程序，并要求对合法输入输出“RIGHT”、对错误输入给出“ERROR”及中间结果提示。读者可据此理解预测分析的基本流程，对照分析表梳理非终结符与终结符的匹配关系，并借鉴分析栈、符号栈的调试与排错思路。已有145人学习，适合作为语法分析实验的参考材料。

1. 从一份 Word 文档到一个能跑的分析器

互联网上能搜到的编译原理实验二资料，十份里有八份是同一份 Word 转出来的截图：全角括号混进代码、预测分析表行列错位、ε 产生式根本没写进表里，抄下来编译不过还找不到原因。这份《实验二--语法分析程序设计与实现》把 LL(1) 这条线完整走了一遍——从 G2[E] 算术表达式文法出发，消除左递归、提左公因子、手算 FIRST/FOLLOW、填 5×8 预测分析表，最后落到一个能在分析栈上逐步打印过程的语法分析程序。它解决的不是“懂不懂 LL(1)”这个概念问题，而是“表怎么填、栈怎么压、错了报在哪一格”。适合正在做编译原理课程设计、需要交一份有完整分析过程输出的人，也适合想把自顶向下分析从纸面推到代码里的自学者。

2. 把 G2[E] 改写成 LL(1) 文法：消除左递归与提左公因子的手算过程

拿到这份文档，第一件不能跳的事是把文法读懂。文档里给的 G2[E] 是教科书里最常见的算术表达式文法：

E -> T | E+T | E-T T -> F | T*F | T/F F -> i | (E)

它描述的语言没问题，但直接拿去做自顶向下分析会当场翻车。这一章把改写过程一步步算清楚，后面填表才有依据。

2.1 原始文法为什么不能直接做自顶向下

自顶向下分析的每一步都是从某个非终结符出发，看当前输入符号该选哪条候选式。这个“选”要能唯一确定，否则就要回溯。而 G2[E] 有两大障碍。

第一个是直接左递归。E -> E+T的右部第一个符号又是 E 自己。如果写成递归下降函数：

void E() { E(); match('+'); T(); } // 错误示范，调用即栈溢出

进入 E 的第一件事又是调用 E，没有任何输入被消耗，程序在几毫秒内就把调用栈打穿。消除左递归不是优化，是自顶向下的入场券。

第二个是公共前缀。假设你把左递归简单删掉，改成E -> T | T+T | T-T，前两个候选式的 FIRST 集都含i和(。分析器读到i时无法区分该走T还是T+T，只能回溯。LL(1) 的判定条件就一条：同一非终结符的任意两个候选式，其 SELECT 集交集为空。左递归和公共前缀是破坏这条条件的两大元凶。

还有一个选型问题：递归下降写起来快，但实验要求“给出每一步分析过程”，包括分析栈、剩余串、所用产生式。递归下降的调用栈是运行时黑匣子，你没法在每步打印出来。所以我一般会选表驱动 LL(1) 预测分析器——栈是自己维护的字符串，每一步的栈内容、剩余输入、查表结果都能原样打印，正好对上实验报告要求的输出格式。

2.2 消除左递归与提取左公因子后的五条产生式

消除直接左递归的标准公式：把A -> Aα | β改写成A -> βA'、A' -> αA' | ε。套到 E 和 T 上：

E -> T | E+T | E-T => E -> TE' E' -> +TE' | -TE' | ε T -> F | T*F | T/F => T -> FT' T' -> *FT' | /FT' | ε F -> i | (E) F -> i | (E) （无左递归，无公共前缀，不动）

改写后每个非终结符的候选式首符都不同了，E 只有一条产生式，E' 的两个非 ε 候选式分别以+和-开头。到这里文法已经是 LL(1)。

这份文档用的是另一套符号名，把 E' 写成 G，T' 写成 S。第一次读容易被绕晕，对照关系如下：

完整五条（文档里的顺序）：

E -> TG G -> +TG | -TG | ε T -> FS S -> *FS | /FS | ε F -> (E) | i

提示：这份文档的原文排版在多处把非终结符名写串了，F->-TG、T->/FS、G->^FS都是错的，正确写法是G->-TG、S->/FS、S->*FS。它是 Word 转文本时符号错位导致的，不要照着抄。判断依据很简单：每条产生式左部的非终结符，必须和上一行改写结果对得上，否则 FIRST 集会算出矛盾的结果。

符号名的选择本身不影响正确性，但影响你后面查表。我建议直接用 E、G、T、S、F，因为文档里的分析表和代码都是按这个顺序来的，中途换名会让行列索引对不上。

2.3 FIRST 与 FOLLOW 集的手算核对表

填表之前必须把这两个集合算出来，而且要用笔在纸上算一遍，不要直接抄。原因很简单：这份文档给的分析表有若干空格是空的，你不自己算一遍就不知道是真的空还是漏填。

FIRST 集的规则：终结符的 FIRST 就是它自己；非终结符看它所有候选式右部的第一个符号，若第一个符号能推出 ε，则要把第二个符号的 FIRST 并进来，依此类推。

FOLLOW 集的规则：开始符号的 FOLLOW 含#；对产生式A -> αBβ，把 FIRST(β) 去掉 ε 后并入 FOLLOW(B)；若 β 能推出 ε 或 β 不存在，把 FOLLOW(A) 并入 FOLLOW(B)。

手算结果：

几个容易算错的地方值得单独说。

FOLLOW(E) 里为什么有)？因为F -> (E)，E 后面紧跟右括号。为什么有#？E 是开始符号。这两条都对。

FOLLOW(G) 为什么等于 FOLLOW(E)？因为 G 只出现在E -> TG的末尾，且 G 能推出 ε，所以 FOLLOW(E) 要并进 FOLLOW(G)；同时 T 在 G 前面不影响。同理 S 的 FOLLOW 包含 FOLLOW(T)，再加上 T 出现在E -> TG中间时 G 的 FIRST 去掉 ε——G 的 FIRST 是{+,-,ε}，去掉 ε 得{+,-}，所以 FOLLOW(T) 里有+和-。

FOLLOW(F) 最大，有六个符号。*和/来自S -> *FS和S -> /FS，F 后面紧跟 S，而 S 的 FIRST 去掉 ε 是{*,/}。+、-、)、#来自 FOLLOW(S) 通过T -> FS传导过来。

注意：FOLLOW 集只对能推出 ε 的非终结符在填表时起作用。G 和 S 都有 ε 产生式，所以它们所在行的 ε 列要按 FOLLOW 填；E、T、F 没有 ε 产生式，FOLLOW 集算出来只是用于传导，不直接进表。

2.4 用 SELECT 集校验 LL(1) 条件

SELECT 集是填表的直接依据：SELECT(A -> α)，若 α 不能推出 ε，就等于 FIRST(α)；若 α 能推出 ε，等于 (FIRST(α) - {ε}) ∪ FOLLOW(A)。

逐条算：

对照 LL(1) 条件检查：G 的三条候选式 SELECT 集分别是{+}、{-}、{),#}，两两不交；S 的四条是{*}、{/}、{+,-,),#}（ε 那条），也不交；F 的两条是{(}和{i}，不交。E 和 T 各只有一条产生式，天然满足。

结论：改写后的文法是 LL(1) 文法，可以无回溯地做自顶向下分析。这一步的验证不能省，很多同学的实验报告在这一步被问“你怎么知道它是 LL(1)”，答不上来就丢分。把上面这张 SELECT 表贴进报告，配上“任意同一左部产生式的 SELECT 集交集为空”这句话，就是完整论证。

顺带说一句，这套改写方法不只对算术表达式有效，任何消除左递归后的文法都可以照这个流程走一遍。区别只在于工作量：非终结符一多，手算 FIRST/FOLLOW 就容易串行，我一般会用表格一行一行推，推完再用一小段脚本核对，避免把错误带进分析表。

3. 预测分析表怎么填：从 SELECT 集到 5×8 表

有了 SELECT 集，分析表就是机械劳动。但机械劳动最容易出错，尤其是行列索引和 ε 的落位。这一章把表的结构、填法、以及在 C++ 里怎么固化下来讲透。

3.1 表结构设计与索引约定

表是二维的：行是非终结符，列是终结符，格子内容是“用哪条产生式”。规模由文法的符号集决定。

终结符集合按文档的约定是 8 个：i、+、-、*、/、(、)、#。其中#是输入串结束符，不算文法符号，但必须占一列，因为分析栈底也要放#，两者要对上。

非终结符 5 个：E、G、T、S、F。顺序很关键，一旦定下就不要改。我按文档的 E、G、T、S、F 排序，对应行号 0 到 4：

列号 0 到 7 对应i、+、-、*、/、(、)、#。

这里有个设计选择值得说：文档原来的代码用type C[10][10]直接存产生式对象，每个格子都是一个含char origin、char array[5]、int length的结构体，10×10 就是 100 个对象。这写法能用，但没必要——产生式总共就 10 条，表里存个整数编号就够了，既省空间，打印和调试时也好读。改成int table[5][8]，-1 表示出错，其余是产生式编号。

3.2 逐格填表与 ε 产生式的落位

填表规则一句话：对每条产生式A -> α，把SELECT(A -> α)里的每个终结符 a，在table[A][a]填上这条产生式的编号。

按编号 0 到 9 排产生式：

填出来的完整表：

空格就是出错位置，程序在这里报 ERROR。

这张表和文档原文给的分析表基本一致，但原文那版有几处会让人误判：它把 ε 写成^并且把 G 行)和#两列的格子填成了g2，含义是“用 G 的 ε 产生式”，逻辑上没错，只是符号^和 C++ 里能直接用的空串表示不一致，抄进代码后要额外写一段“如果栈顶是 ^ 就弹掉”的分支。我改成“空右部”的写法，压栈时长度为 0 自然什么都不压，少一个特殊分支就少一个 bug。

G 行和 S 行的 ε 落位是最容易漏的。G 的 ε 产生式按 FOLLOW(G) ={), #}填)和#两列；S 的 ε 产生式按 FOLLOW(S) ={+,-,),#}填四列。少填任何一格，正确串在对应位置就会被判成错误，表现为“明明是对的表达式，程序在收尾阶段报 ERROR”。

3.3 用 C++ 结构体与数组固化产生式和表

把产生式和表用代码写死，比在运行时算 SELECT 集简单得多，也更适合实验场景。真正要保证的是把编号和表内容对上。

#include <iostream> #include <iomanip> #include <string> #include <cstring> using namespace std; // 终结符与列号约定：i=0 +=1 -=2 *=3 /=4 (=5 )=6 #=7 const char TERM[8] = {'i','+','-','*','/','(',')','#'}; // 非终结符与行号约定：E=0 G=1 T=2 S=3 F=4 const char NONTERM[5] = {'E','G','T','S','F'}; const int TN = 8, NN = 5; // 产生式表：rhs 为空串代表 epsilon。编号与填表时严格一致 struct Prod { char lhs; const char* rhs; }; static const Prod PROD[10] = { {'E', "TG" }, // 0 {'G', "+TG" }, // 1 {'G', "-TG" }, // 2 {'G', "" }, // 3 epsilon {'T', "FS" }, // 4 {'S', "*FS" }, // 5 {'S', "/FS" }, // 6 {'S', "" }, // 7 epsilon {'F', "(E)" }, // 8 {'F', "i" } // 9 }; int table[NN][TN]; void buildTable() { // 全部先置 -1，代表出错格 for (int i = 0; i < NN; ++i) for (int j = 0; j < TN; ++j) table[i][j] = -1; // E 行：SELECT(E->TG) = {i, (} table[0][0] = 0; table[0][5] = 0; // G 行：+ 列用 1，- 列用 2，) 和 # 用 epsilon 产生式 3 table[1][1] = 1; table[1][2] = 2; table[1][6] = 3; table[1][7] = 3; // T 行：SELECT(T->FS) = {i, (} table[2][0] = 4; table[2][5] = 4; // S 行：* 和 / 用 5、6，其余 FOLLOW(S) 用 epsilon 产生式 7 table[3][1] = 7; table[3][2] = 7; table[3][3] = 5; table[3][4] = 6; table[3][6] = 7; table[3][7] = 7; // F 行：i 列用 9，( 列用 8 table[4][0] = 9; table[4][5] = 8; }

逻辑说明：PROD数组的下标就是产生式编号，table里存的是同一个编号。两处一旦有一处改了顺序，查表就会拿到错误的产生式——这种错误不会崩溃，只会默默输出错误的推导过程，是最难查的一类。

参数说明：rhs用const char*而不是char[5]，是因为只读常量串不需要拷贝；空串表示 ε，长度自然是 0。如果你习惯用'^'表示 ε，也能跑，但压栈时要多写一个if (X == '^')判断，容易在某个分支漏掉。

3.4 打印分析栈与剩余输入串的三段格式

实验报告要求输出“分析栈、符号栈、剩余串”等信息。格式对不齐，截图放上去很难看，老师也难核对。我一般用iomanip的setw固定列宽。

// 从栈底到栈顶打印分析栈。约定 string 左端是栈底，右端是栈顶 void printStack(const string& stk) { cout << left << setw(14) << stk; } // 打印剩余输入串：已匹配部分用空格占位，从当前指针位置开始显示 void printRest(const string& in, size_t pos) { cout << left << setw(16) << in.substr(pos); }

printStack直接输出整个 string，不做反转。原因是压栈时我就让栈底在左、栈顶在右，和课本画法一致，输出时不用二次处理。如果按数组模拟栈、top指向栈顶，打印时就要从下标 0 循环到top，这一点文档原来的print()就是这么做的，逻辑没问题，只是容易把top的边界写成<= top还是< top搞混。

printRest用substr(pos)而不是像文档那样先循环打空格对齐再打字符。substr更短，也不会因为空格数量算错让整列串位。列宽 16 是按最长测试串(i+i)*i-i/i#留的余量，实际的串更长就调大这个数。

4. 主控循环怎么写：分析栈、剩余串与错误定位

到这里文法、集合、分析表都齐了，剩下的是主控循环。很多实验代码在这一步翻车，不是逻辑不会，而是栈的方向搞反、ε 分支漏处理、输入串末尾忘了补#。这一章按执行顺序拆开讲。

4.1 栈的初始化与弹出方向约定

初始状态：分析栈里只有栈底符号#和开始符号E；输入指针指向第一个单词；剩余串是整条输入。

栈的表示有两种常见做法：字符数组加top指针，或者 C++ 的std::string当栈用。用string的好处是back()取栈顶、pop_back()弹栈、push_back()压栈，三个操作都是 O(1)，而且打印时直接输出整个 string 就是栈底到栈顶的顺序，不用额外循环。

初始化：

string stk = "#E"; // 左端 # 是栈底，右端 E 是栈顶 size_t pos = 0; // 输入串指针，指向当前待匹配的终结符

这个顺序必须和打印、查表保持一致。我见过有同学把stk初始化成"E#"，取栈顶用stk[0]，压栈用insert(0, ...)，也能跑，但每处下标都要反着想一遍，改一次错一次。约定一旦定下，全篇统一，别中途换。

4.2 终结符匹配分支与指针推进

循环每一轮先取栈顶 X 和当前输入符号 a，然后分两种情况。X 是终结符时，只有两种可能：和 a 相等，匹配成功，弹栈并把输入指针后移一位；不相等，当场报错，把当前位置打出来。

// 查字符在终结符表里的列号，找不到返回 -1 int idxTerm(char c) { for (int k = 0; k < TN; ++k) if (TERM[k] == c) return k; return -1; } // 查字符在非终结符表里的行号 int idxNon(char c) { for (int k = 0; k < NN; ++k) if (NONTERM[k] == c) return k; return -1; }

匹配分支的判断不要写成if (X == a) ... else if (X == '#') ...这种混合顺序。#本身也是终结符，在表里占一列，如果先判#再判相等，逻辑还能对；但如果先判相等、再判#却没处理“两边都是 #”的情况，就会在最后一步死循环。正确顺序是：先判X == '#' && a == '#'接受，再判X == a匹配推进，最后才是报错。

报错信息要带位置，这是实验报告里“必要的出错说明信息”那条要求。位置用pos表示已匹配的字符个数，从 0 开始计数，报错时同时打印“期望什么、实际读到什么”。

4.3 非终结符查表、逆序压栈与 ε 的自然消失

X 是非终结符时，用 X 的行号和 a 的列号去查表。查到 -1 直接报错；查到产生式编号 p，先弹掉栈顶的 X，再把PROD[p].rhs逆序压栈。

逆序是这一章最关键的一句。以E -> TG为例，右部是T然后G。分析栈是后进先出，要让 T 先被处理，T 必须在栈顶，所以压栈顺序是：先压 G，再压 T。反过来写，栈顶变成 G，程序会先拿 G 去匹配输入，整条推导立刻错乱。

stk.pop_back(); // 弹掉左部符号 const char* rhs = PROD[p].rhs; for (int k = (int)strlen(rhs) - 1; k >= 0; --k) stk.push_back(rhs[k]); // 从右往左压，右部第一个符号最后进栈变成栈顶

ε 产生式的处理在这里天然正确：strlen(rhs)是 0，循环一次都不执行，相当于把左部符号弹掉就结束了。这就是为什么不用在每个分支里写“如果右部是 ε 就跳过”——它本来就不产生任何压栈动作。文档原来的代码里有一段if (A[top] == '^') top--;，是因为它把'^'当成真实字符压进了栈，才需要专门弹一次。两种写法都对，但用空串的那版少一个状态，出错面更小。

4.4 完整可编译代码与四组测试用例

把上面的碎片拼成完整程序。为了能直接用g++编译，头文件统一用<iostream>、<string>、<cstring>、<iomanip>，不写.h。

int main() { buildTable(); string in; if (!(cin >> in)) return 1; // 保证输入串以 # 结尾，这是栈底符号能对上的前提 if (in.empty() || in.back() != '#') in += '#'; // 输入合法性预检，非法字符直接拦掉，不进入分析循环 for (size_t k = 0; k < in.size(); ++k) { if (idxTerm(in[k]) < 0) { cout << "输入串含非法字符: " << in[k] << "，位置 " << k << endl; return 1; } } string stk = "#E"; size_t pos = 0; int step = 1; cout << left << setw(6) << "步骤" << setw(14) << "分析栈" << setw(16) << "剩余输入串" << "动作/所用产生式" << endl; while (true) { char X = stk.back(); char a = in[pos]; cout << left << setw(6) << step++ ; printStack(stk); printRest(in, pos); // 1. 两边同时到栈底/串尾，接受 if (X == '#' && a == '#') { cout << "接受（RIGHT）" << endl; break; } int t = idxTerm(X); if (t >= 0) { // 2. 栈顶是终结符：必须与当前输入相等 if (X == a) { cout << "匹配 " << a << endl; stk.pop_back(); ++pos; } else { cout << "ERROR：栈顶终结符 " << X << " 与输入符号 " << a << " 不匹配，位置 " << pos << endl; return 2; } } else { // 3. 栈顶是非终结符：查预测分析表 int row = idxNon(X); int col = idxTerm(a); int p = (row >= 0 && col >= 0) ? table[row][col] : -1; if (p < 0) { cout << "ERROR：非终结符 " << X << " 遇到输入符号 " << a << " 查表无产生式，位置 " << pos << endl; return 3; } cout << X << " -> " << (strlen(PROD[p].rhs) ? PROD[p].rhs : "ε") << endl; stk.pop_back(); const char* rhs = PROD[p].rhs; for (int k = (int)strlen(rhs) - 1; k >= 0; --k) stk.push_back(rhs[k]); } } return 0; }

编译命令：

g++ -std=c++11 -O2 -o parser parser.cpp

四组测试，覆盖两个正确串和三个错误串：

第二组值得跑一遍看输出：i+i*i#的推导里 G 和 S 都用到了 ε 产生式，正好验证 FOLLOW 集填的那几列有没有填对。如果程序在第 15 步之后卡住或者报错，问题一定出在table[1][7]或table[3][7]这两格。

运行方式：

echo "i+i*i#" | ./parser

5. 排错清单：LL(1) 分析器最容易翻车的五个地方

下面五条都是我自己或身边人真踩过的，现象、原因、解决按顺序写清楚，照着对号入座基本能定位到具体行。

5.1 正确表达式被判 ERROR，且出错位置很靠后

现象：i+i*i#跑到十步之后突然报“查表无产生式”，前面几步看着都对。

原因：多半是 G 行或 S 行的 ε 列漏填。G 的 ε 产生式要填)和#两列，S 的 ε 产生式要填+、-、)、#四列。漏任意一格，推导走到那个符号时查表拿到 -1。另一种可能是把 FOLLOW 集算错，比如把 FOLLOW(G) 当成了{+,-,) }漏了#。

解决：把第 3.2 节的表和你的buildTable()逐格对一遍，重点数 G 行和 S 行有几个非空。G 行应该有 4 个非空格，S 行应该有 6 个。数完再跑，问题基本就没了。

5.2 第一组测试就死循环，栈越压越长

现象：程序不报错也不结束，输出了几百行以后被手动中断，分析栈长度一直在涨。

原因：两个典型。一是压栈写成了正序，E -> TG压完以后栈顶是 G，G 又有 ε 产生式，弹掉之后又回到 T，T 又展开成 FS，形成循环。二是消除左递归时改错了产生式右部，比如把E -> TG写成了E -> ETG，那跟没消除左递归是一样的效果，只是从递归调用变成了栈膨胀。

解决：先打印前三步的栈内容看一眼。正确的第一步是#E变成#GT，如果看到#ETG或者#TG，就是压栈方向或产生式本身写错了。压栈循环一定是从rhs末尾往开头遍历。

5.3 输入串末尾没补#，程序在最后一步越界

现象：前面全对，输出到“接受”之前崩了，或者报一个和输入内容完全无关的错误。

原因：in[pos]在pos等于in.size()时越界。std::string的operator[]不做边界检查，读到的是内存里的随机值，表现为莫名其妙的符号。原始文档的读入循环是do { cin >> ch; B[j] = ch; j++; } while (ch != '#');，只要用户不输#就无限读下去。

解决：读入之后立刻补一次if (in.back() != '#') in += '#';，并且不要信任用户一定输对。另外在主循环开头加一句if (pos >= in.size()) { 报错; break; }兜底，比让程序崩在随机内存上好得多。

5.4 换了非终结符顺序，表全错位

现象：代码和表单独看都对，合起来就是不对，i+i#报错而i*i#反而通过。

原因：NONTERM数组的定义顺序和buildTable()里写的行号没对上。比如NONTERM写成{'E','T','G','S','F'}，但table[1]填的还是 G 的产生式，那 G 和 T 的行就互换了一半。这种错误不会崩溃，只会让某些串碰巧通过，是最隐蔽的一类。

解决：不要用数字字面量直接写行号。定义一个枚举或者用#define把RE、RG、RT、RS、RF映射到 0 到 4，填表和查表都用这些名字。改一次顺序，编译器帮你在所有引用处改。另外在第 3.4 节那种打印格式里把行号也打出来，调试时一眼能看出是行错了还是列错了。

5.5 只测了正确串，错例分支一行没跑

现象：程序对三个正确表达式都输出 RIGHT，交上去被问“错误处理在哪”，答不上来。

原因：实验要求明确写了“供测试的例子应包括符合语法规则的语句，及分析程序能判别的若干错例”，只测正确串等于只验证了一半。而且错例分支往往藏着真正的 bug——比如(i*i#这种缺右括号的情况，走的是终结符匹配失败分支，正常输入根本触发不到。

解决：准备一张错例矩阵，至少覆盖三种错误类型：非法字符（如i&i#）、查表无产生式（如i+#）、终结符不匹配（如i(i)#、(i*i#）。每种跑一遍，把报错位置和错误信息贴进报告，这比多写两百字原理说明管用。

6. 从实验报告到可信验证：三张对照表加一个对拍脚本

代码能跑不等于对。我交这类实验前会做三件事，成本不高，但能挡住绝大多数“我明明测过”的尴尬。

第一件是手算推导对齐。挑最短的i+i#，在纸上按文法一步步写推导，每一步的当前句型记下来，然后和程序输出的分析栈逐步对照。程序栈里存的是还没展开的符号串，纸上写的是当前句型，两者差一个“已匹配前缀”。把已匹配前缀补到栈左边，两边应该完全一致。对不上就说明某一步的压栈顺序有问题，比起盯着代码找，这样定位快得多。

第二步是错例矩阵覆盖。我一般会按下表把每条错误分支至少走一遍：

第三步是对拍。手写测试用例覆盖有限，随机串才能压出边界问题。用 Python 写一个几十行的递归下降参考实现，不用管分析过程，只回答“接受还是不接受”，再让 C++ 程序和它逐个比对。

import random, subprocess def expr(s, i): i = term(s, i) if i is None: return None while i < len(s) and s[i] in '+-': i = term(s, i + 1) if i is None: return None return i def term(s, i): i = factor(s, i) if i is None: return None while i < len(s) and s[i] in '*/': i = factor(s, i + 1) if i is None: return None return i def factor(s, i): if i >= len(s): return None if s[i] == 'i': return i + 1 if s[i] == '(': j = expr(s, i + 1) if j is not None and j < len(s) and s[j] == ')': return j + 1 return None def accept(s): return expr(s, 0) == len(s) random.seed(7) ops = '+-*/' bad = 0 for _ in range(300): n = random.randint(1, 7) body = ''.join(random.choice('i()' + ops) for _ in range(n)) mine = accept(body) out = subprocess.run(['./parser'], input=body + ' #\n', capture_output=True, text=True).stdout theirs = 'RIGHT' in out if mine != theirs: bad += 1 print('不一致:', body, '参考实现:', mine, '程序:', theirs) print('不一致条数:', bad)

参考实现用的是消除左递归之后的等价形式，直接按原始文法的递归下降写：E -> T {(+|-) T}，T -> F {(*|/) F}，F -> i | (E)。它和表驱动版本走的是同一套语法，只是实现路径不同，正好用来交叉验证。300 条随机串里如果出现不一致，基本可以断定是分析表某个格子填错了——随机串会大量触发括号嵌套和连续运算符，比手写用例更容易撞上漏填的格。

参数上有一点要提醒：subprocess.run的input末尾必须带换行，否则cin >> in会一直等 EOF；程序里有exit分支，正常结束和报错退出都要靠capture_output接住，不然输出会混到测试脚本自己的 stdout 里，把RIGHT的判断搞乱。

从那以后我每次做这种带分析过程输出的实验，都是先把手算推导表、错例矩阵、对拍脚本三样跑一遍，截图留档，再动笔写报告。代码可能写错，表也可能填错，但三条独立路径同时对的概率很低——真碰上了，那说明这次是真懂了。希望帮到你。

本文还有配套的精品资源，点击获取