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 | ET | E-T T - F | T*F | T/F F - i | (E)它描述的语言没问题但直接拿去做自顶向下分析会当场翻车。这一章把改写过程一步步算清楚后面填表才有依据。2.1 原始文法为什么不能直接做自顶向下自顶向下分析的每一步都是从某个非终结符出发看当前输入符号该选哪条候选式。这个“选”要能唯一确定否则就要回溯。而 G2[E] 有两大障碍。第一个是直接左递归。E - ET的右部第一个符号又是 E 自己。如果写成递归下降函数void E() { E(); match(); T(); } // 错误示范调用即栈溢出进入 E 的第一件事又是调用 E没有任何输入被消耗程序在几毫秒内就把调用栈打穿。消除左递归不是优化是自顶向下的入场券。第二个是公共前缀。假设你把左递归简单删掉改成E - T | TT | T-T前两个候选式的 FIRST 集都含i和(。分析器读到i时无法区分该走T还是TT只能回溯。LL(1) 的判定条件就一条同一非终结符的任意两个候选式其 SELECT 集交集为空。左递归和公共前缀是破坏这条条件的两大元凶。还有一个选型问题递归下降写起来快但实验要求“给出每一步分析过程”包括分析栈、剩余串、所用产生式。递归下降的调用栈是运行时黑匣子你没法在每步打印出来。所以我一般会选表驱动 LL(1) 预测分析器——栈是自己维护的字符串每一步的栈内容、剩余输入、查表结果都能原样打印正好对上实验报告要求的输出格式。2.2 消除左递归与提取左公因子后的五条产生式消除直接左递归的标准公式把A - Aα | β改写成A - βA、A - αA | ε。套到 E 和 T 上E - T | ET | 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 写成 GT 写成 S。第一次读容易被绕晕对照关系如下教科书写法文档写法含义产生式EGE 的后缀G - TG | -TG | εTST 的后缀S - *FS | /FS | ε完整五条文档里的顺序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)。手算结果非终结符FIRST 集FOLLOW 集E{ i, ( }{ ), # }G{ , -, ε }{ ), # }T{ i, ( }{ , -, ), # }S{ *, /, ε }{ , -, ), # }F{ i, ( }{ *, /, , -, ), # }几个容易算错的地方值得单独说。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 - /FSF 后面紧跟 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)。逐条算产生式SELECT 集E - TG{ i, ( }G - TG{ }G - -TG{ - }G - ε{ ), # }T - FS{ i, ( }S - *FS{ * }S - /FS{ / }S - ε{ , -, ), # }F - (E){ ( }F - i{ i }对照 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行号非终结符0E1G2T3S4F列号 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 排产生式编号产生式0E - TG1G - TG2G - -TG3G - ε4T - FS5S - *FS6S - /FS7S - ε8F - (E)9F - i填出来的完整表i-*/()#E00G1233T44S775677F98空格就是出错位置程序在这里报 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; // 终结符与列号约定i0 1 -2 *3 /4 (5 )6 #7 const char TERM[8] {i,,-,*,/,(,),#}; // 非终结符与行号约定E0 G1 T2 S3 F4 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 是按最长测试串(ii)*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 -stdc11 -O2 -o parser parser.cpp四组测试覆盖两个正确串和三个错误串输入串预期结果触发分支ii*i#RIGHT正常推导含 ε 产生式(ii)*i#RIGHT嵌套括号F - (E) 被调用两次i#ERROR非终结符 T 遇到#表中该格为 -1i(i)#ERROR栈顶)与输入(不匹配(i*i#ERROR缺少右括号收尾时栈顶)对#第二组值得跑一遍看输出ii*i#的推导里 G 和 S 都用到了 ε 产生式正好验证 FOLLOW 集填的那几列有没有填对。如果程序在第 15 步之后卡住或者报错问题一定出在table[1][7]或table[3][7]这两格。运行方式echo ii*i# | ./parser5. 排错清单LL(1) 分析器最容易翻车的五个地方下面五条都是我自己或身边人真踩过的现象、原因、解决按顺序写清楚照着对号入座基本能定位到具体行。5.1 正确表达式被判 ERROR且出错位置很靠后现象ii*i#跑到十步之后突然报“查表无产生式”前面几步看着都对。原因多半是 G 行或 S 行的 ε 列漏填。G 的 ε 产生式要填)和#两列S 的 ε 产生式要填、-、)、#四列。漏任意一格推导走到那个符号时查表拿到 -1。另一种可能是把 FOLLOW 集算错比如把 FOLLOW(G) 当成了{,-,) }漏了#。解决把第 3.2 节的表和你的buildTable()逐格对一遍重点数 G 行和 S 行有几个非空。G 行应该有 4 个非空格S 行应该有 6 个。数完再跑问题基本就没了。5.2 第一组测试就死循环栈越压越长现象程序不报错也不结束输出了几百行以后被手动中断分析栈长度一直在涨。原因两个典型。一是压栈写成了正序E - TG压完以后栈顶是 GG 又有 ε 产生式弹掉之后又回到 TT 又展开成 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 换了非终结符顺序表全错位现象代码和表单独看都对合起来就是不对ii#报错而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#这种缺右括号的情况走的是终结符匹配失败分支正常输入根本触发不到。解决准备一张错例矩阵至少覆盖三种错误类型非法字符如ii#、查表无产生式如i#、终结符不匹配如i(i)#、(i*i#。每种跑一遍把报错位置和错误信息贴进报告这比多写两百字原理说明管用。6. 从实验报告到可信验证三张对照表加一个对拍脚本代码能跑不等于对。我交这类实验前会做三件事成本不高但能挡住绝大多数“我明明测过”的尴尬。第一件是手算推导对齐。挑最短的ii#在纸上按文法一步步写推导每一步的当前句型记下来然后和程序输出的分析栈逐步对照。程序栈里存的是还没展开的符号串纸上写的是当前句型两者差一个“已匹配前缀”。把已匹配前缀补到栈左边两边应该完全一致。对不上就说明某一步的压栈顺序有问题比起盯着代码找这样定位快得多。第二步是错例矩阵覆盖。我一般会按下表把每条错误分支至少走一遍错误类型输入样例期望的报错点非法字符ii#读入预检阶段连续运算符ii#非终结符 T 遇查表失败括号不配对(i*i#栈顶)对#不匹配空括号()#非终结符 F 遇)查表失败运算符结尾i#非终结符 T 遇#查表失败第三步是对拍。手写测试用例覆盖有限随机串才能压出边界问题。用 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], inputbody #\n, capture_outputTrue, textTrue).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的判断搞乱。从那以后我每次做这种带分析过程输出的实验都是先把手算推导表、错例矩阵、对拍脚本三样跑一遍截图留档再动笔写报告。代码可能写错表也可能填错但三条独立路径同时对的概率很低——真碰上了那说明这次是真懂了。希望帮到你。本文还有配套的精品资源点击获取

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

相关推荐

车站售票管理系统数据库课设：事务并发防超卖与验收骨架

Oracle开放式基金交易平台数据库设计：七表约束与PL/SQL存储过程

中文字体font-family字体栈：跨平台写法与排查

更多资讯

WebAssembly逆向实战：荔枝网Wasm加密参数分析

输入受限双端队列的特性与应用解析

AI开发者的新操作系统：Skills技术原理与实战指南

OpenRig：基于Node.js与tmux的本地AI工作流调度范式

Claude Skills 本质是 MCP 协议下的可验证能力契约

自考论文写作利器：8款AI工具实测与组合使用指南

今日更新

猫狗目标检测数据集：VOC/COCO/YOLO三格式一体化实战包

HDU2017多校标程复现：算法竞赛工程化真题沙盒

Codex Sandbox 隔离环境拆解：AI Agent 的临时实验室如何运作

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？