简介:这份文档面向计算机专业编译原理课程实验学习者,聚焦语法分析程序的设计与实现,帮助读者在完成词法扫描器后继续对单词序列做语法检查与结构分析。内容围绕算术表达式简化子集展开,涵盖算符优先、递归下降、LL(1)、SLR(1)、LR(1)等方法的选择思路,并给出LL(1)文法的改写、预测分析表构造、C++源程序及分析栈与剩余串输出过程,也提示了合法语句与若干错例的测试要求。压缩包仅含1个doc文件,约127KB,适合作为实验过程参考或课程设计底稿,便于对照理解FIRST/FOLLOW、分析表填充与RIGHT/ERROR判定。已有145人学习,可帮助读者较快搭建语法分析实验框架并排查分析过程中的结构错误。
1. 从一份编译原理实验作业说起:这套 LL(1) 语法分析程序能判断什么、不能判断什么
编译原理上到语法分析这一章,很多人都有同一个卡点:黑板上的 FIRST/FOLLOW 会算,预测分析表会填,真让自己写一个能跑的语法分析程序就卡住了。这份实验二源码就是一份完整答案——用 C++ 写的 LL(1) 预测分析程序,吃进去的是实验一扫描器吐出的单词串(UCON、PL、MU、ID这一类),吐出来的是每一步的分析栈、剩余串、所用产生式,收尾打RIGHT或ERROR。
它只处理算术表达式这一个子集,文法一共五行,但整套机制是完整的:左递归消除、FIRST/FOLLOW、预测分析表、栈式驱动器,一个都不少。适合两类人读:一门课正卡在这次验收上、需要照着跑通的;以及想拿这份代码当最小可运行 LL(1) 引擎,往后自己接词法分析、生成语法树、加错误恢复的。互联网上流传的几个版本都能编、都能跑,但坑藏在细节里,这些坑不影响交作业,却会在你二次开发时集中爆出来。
2. 文法改造与分析表落位:E → E+T的左递归是怎么被消掉的
2.1 从 G2 到 G2':左递归消除与提取公因子
实验给的原始文法 G2[E] 长这样:
E → T | E+T | E-T T → F | T*F | T/F F → i | (E)问题出在E → E+T和T → T*F。这两个产生式右部第一个符号就是左部自己,属于直接左递归。LL(1) 是自顶向下、从左往右扫描、每次看一个输入符号的打法,碰到左递归会无限展开下去,栈永远压不完。所以第一步必须把文法改造成等价的非左递归形式。
通用的改造公式是:把A → Aα | β改写成A → βA'、A' → αA' | ε。套到 E 上,β是T,α有两项+T和-T,于是得到E → TG、G → +TG | -TG | ε。T 层同理,T → FS、S → *FS | /FS | ε。F 层本身没有左递归,只是把i和(E)两个候选留着。
改造完的文法就是代码里那五个非终结符的来源:
E → TG G → +TG | -TG | ε T → FS S → *FS | /FS | ε F → (E) | i这里有个容易被忽略的设计点:为什么要引入 G 和 S 两个新非终结符,而不是把加减乘除都塞进一个?因为原始文法有优先级——乘除高于加减。分层以后,G 层只负责加减,S 层只负责乘除,F 层负责括号和运算对象,优先级被结构本身固化下来了。左结合性也保住了:a-b-c会被解析成(a-b)-c,因为 G 的展开是尾递归形式,先出现的减号先结合。这两个特性在改造文法时必须一起验证,光把左递归消掉、层级搞错,程序照样输出 RIGHT,但语义结构已经错了。
改造后还有个副作用值得说清:引入了 ε 产生式。G 和 S 都可能推出空串,这意味着分析栈在展开它们之后,符号会“凭空消失”一个。代码里用^这个字符代表 ε,入栈后立刻top--把它抹掉,这是后面读主循环时第一个要盯住的地方。
2.2 FIRST 与 FOLLOW:预测分析表每一格是怎么定下来的
表能不能填对,全看两个集合算得准不准。按改造后的文法逐条推:
FIRST(E) = FIRST(T) = FIRST(F) = {(, i},因为 E 和 T 的第一个符号都只能顺着往下推到 F。FIRST(G) = {+, -, ε},G 的两个非空产生式以+、-打头,第三个是 ε。FIRST(S) = {*, /, ε},同理。FOLLOW(E) = {#, )}:#是输入结束符,)来自F → (E)里 E 后面那个右括号。FOLLOW(G) = FOLLOW(E) = {#, )},因为 G 在E → TG的末尾,且 G 自身可空。FOLLOW(T) = FIRST(G)\{ε} ∪ FOLLOW(E) = {+, -, #, )}。FOLLOW(S) = FOLLOW(T) = {+, -, #, )},S 在T → FS的末尾。FOLLOW(F) = FIRST(S)\{ε} ∪ FOLLOW(S) = {*, /, +, -, #, )}。
整理成表:
| 非终结符 | FIRST | FOLLOW |
|---|---|---|
| E | (,i | #,) |
| G | +,-,ε | #,) |
| T | (,i | +,-,#,) |
| S | *,/,ε | +,-,#,) |
| F | (,i | *,/,+,-,#,) |
填表规则两条:对A → α,若a ∈ FIRST(α),把产生式填进M[A, a];若ε ∈ FIRST(α),对每个b ∈ FOLLOW(A),也把这条产生式填进M[A, b]。
照着规则走一遍,能得到一个很直观的结论:E、T、F 三行的非空格子只出现在i和(两列,因为它们只可能以这两个符号开头;G 行的格子出现在+、-、)、#四列,前两个来自 FIRST,后两个来自 FOLLOW(ε 产生式);S 行的格子出现在*、/和 FOLLOW(S) 的四个符号上。这个规律不是巧合,它直接决定了代码里表数组每一行哪几个下标有值,改文法时如果忘了同步改下面这些下标,程序会立刻从 RIGHT 变成 ERROR。
代码里那张C[5][8]的二维数组,行顺序是E, G, T, S, F,列顺序是i, +, -, *, /, (, ), #。填完以后大概长这样(空表示该格无产生式,原文用字符N标记):
| i | + | - | * | / | ( | ) | # | |
|---|---|---|---|---|---|---|---|---|
| E | E→TG | 空 | 空 | 空 | 空 | E→TG | 空 | 空 |
| G | 空 | G→+TG | G→-TG | 空 | 空 | 空 | G→ε | G→ε |
| T | T→FS | 空 | 空 | 空 | 空 | T→FS | 空 | 空 |
| S | 空 | S→ε | S→ε | S→*FS | S→/FS | 空 | S→ε | S→ε |
| F | F→i | 空 | 空 | 空 | 空 | F→(E) | 空 | 空 |
提示:这张表就是整个程序的“黑匣子”。任何一次 ERROR 输出,先去表里对着当时的栈顶非终结符和当前输入符号找格子在不在,九成的问题在这一步就能定位。
2.3 数据结构落位:分析栈、剩余串、产生式对象
文法算清楚了,接下来是拿什么装。原始代码用了四个全局角色:
char A[30]; // 分析栈 char B[30]; // 剩余输入串 char v1[20] = {'i','+','-','*','/','(',')','#'}; // 终结符表 char v2[20] = {'E','G','T','S','F'}; // 非终结符表 int j = 0, b = 0, top = 0, l = 0; // l 为输入串长度A 是分析栈,用数组模拟,top指向当前栈顶下标,栈底是A[0] = '#'。B 是输入串,一次性读进来后靠指针b往后推。这两个数组都是 30 个字符的定长 char 数组,这个数字后面会成为一个隐患。
产生式用了一个最简单的结构体来装:
struct type { char origin; // 产生式左部,大写非终结符 char array[5]; // 产生式右部字符序列 int length; // 右部字符个数 };三个字段各有分工。origin用来在输出时打印E->TG这样的形式,同时也是判断“这个格子是不是空的”的依据——建表时先把所有格子的origin赋成'N',查到'N'就说明该格无产生式,直接进错误分支。array长度给 5 是够的,最长的一条产生式(E)只有 3 个字符,ε 用单个'^'表示,length记 1。
为什么用 char 而不是一个带类型的 token 结构?因为实验一只要求输出UCON,PL,UCON,MU,ID这种单词串,进到这个程序之前已经被映射成了i和运算符。用单字符换来的是代码极短、调试时肉眼可读,代价是丢掉词法信息、没法区分不同的标识符,也就没法在后面生成有意义的语法树。这个取舍在做实验时是对的,在二次开发时就必须改掉。
3. 核心代码逐段拆解:一个字符从进栈到匹配的完整链路
3.1 产生式对象初始化与预测分析表的填充
程序一进来先把十一条产生式全部实例化成对象。原文写法比较笨,一条一条赋值,我把它整理成下面这个样子,逻辑和原文完全一致,只是把赋值语句按文法分组了:
type e, g, g1, g2, t, s, s1, s2, f, f1; // 每个对象对应一条产生式 type C[10][10]; // 预测分析表 // E → TG e.origin = 'E'; strcpy(e.array, "TG"); e.length = 2; // G → +TG | -TG | ε g.origin = 'G'; strcpy(g.array, "+TG"); g.length = 3; g1.origin = 'G'; strcpy(g1.array, "-TG"); g1.length = 3; g2.origin = 'G'; g2.array[0] = '^'; g2.length = 1; // '^' 代表 ε // T → FS t.origin = 'T'; strcpy(t.array, "FS"); t.length = 2; // S → *FS | /FS | ε s.origin = 'S'; strcpy(s.array, "*FS"); s.length = 3; s1.origin = 'S'; strcpy(s1.array, "/FS"); s1.length = 3; s2.origin = 'S'; s2.array[0] = '^'; s2.length = 1; // F → (E) | i f.origin = 'F'; strcpy(f.array, "(E)"); f.length = 3; f1.origin = 'F'; f1.array[0] = 'i'; f1.length = 1;这段代码的关键在于length字段必须和array里有效字符数严格一致。strcpy会带上结尾的\0,而g2、s2、f1这种手动赋值单个字符的,array[1]及之后是未初始化的垃圾值,靠length截断才不会读到脏数据。后面逆序入栈的循环写的是for (j = cha.length - 1; j >= 0; j--),一旦length写错,压进栈里的就是一串垃圾字符,症状是分析到一半突然报 ERROR,很难反查。
接下来建表。先全部清成'N',再按 2.2 节推出来的结论逐格填:
for (m = 0; m <= 4; m++) for (n = 0; n <= 7; n++) C[m][n].origin = 'N'; // 先把 5×8 全部标成空 // 行序 E G T S F,列序 i + - * / ( ) # C[0][0] = e; C[0][5] = e; // E 行:i 和 ( C[1][1] = g; C[1][2] = g1; C[1][6] = g2; C[1][7] = g2; // G 行 C[2][0] = t; C[2][5] = t; // T 行:i 和 ( C[3][1] = s2; C[3][2] = s2; C[3][3] = s; C[3][4] = s1; C[3][6] = s2; C[3][7] = s2; // S 行 C[4][0] = f1; C[4][5] = f; // F 行:i 和 (逐行对一遍就能确认它和 2.2 节的表是完全吻合的。第 0 行只有下标 0(i)和 5(()有值,第 1 行是下标 1、2、6、7,第 3 行是 1、2、3、4、6、7。这组下标是整个程序里最脆弱的地方——它同时编码了v1、v2两个字符表的顺序。v1里i排第 0 位、+排第 1 位,C表的列就必须按这个顺序排;v2里E排第 0 位、G排第 1 位,C表的行也必须按这个顺序。两边任何一处顺序调换,表就整体错位,程序会在完全正确的输入上报 ERROR。
提示:如果打算改文法扩充运算符,别去动
v1、v2的顺序,直接在末尾追加新符号,然后把C表的维度、清空循环的上界和后面所有硬编码下标一起往上加。顺序一动,等于把表推倒重来。
3.2 主循环:栈顶是终结符和非终结符的分叉处理
读入部分比较直接:一个do-while循环用cin >> ch逐字符读,读到#停,中途遇到不在终结符表里的字符直接报“输入串中有非法字符”并exit(1)。读完之后l = j记长度,ch = B[0]取第一个待分析字符,栈里压入#和E,top指向E。
真正干活的是下面这个循环。为了让逻辑清楚,我把原文的花括号和缩进理顺了一下,并把flag的重置提前到每轮开头(原文是在匹配成功后重置,效果一样但容易看漏):
do { x = A[top--]; // 弹出栈顶,top 此时已指向新栈顶 cout << k++ << "\t\t"; flag = 0; for (j = 0; j <= 7; j++) // 判断 x 是不是终结符 if (x == v1[j]) { flag = 1; break; } if (flag == 1) { /* 分支 A:栈顶是终结符 */ if (x == '#') { // 栈顶到 #,认为分析成功 finish = 1; cout << "acc!" << endl; getchar(); // 让控制台窗口停住,方便看结果 exit(1); } if (x == ch) { // 与当前输入符匹配 print(); print1(); cout << "匹配" << endl; ch = B[++b]; // 吃掉一个输入符 } else { // 终结符对不上 print(); print1(); cout << "出错" << endl; exit(1); } } else { /* 分支 B:栈顶是非终结符,查表展开 */ for (j = 0; j <= 4; j++) if (x == v2[j]) { m = j; break; } // 行号 for (j = 0; j <= 7; j++) if (ch == v1[j]) { n = j; break; } // 列号 cha = C[m][n]; if (cha.origin != 'N') { // 该格有产生式 print(); print1(); cout << cha.origin << "->"; for (j = 0; j < cha.length; j++) cout << cha.array[j]; cout << "\n"; for (j = cha.length - 1; j >= 0; j--) // 右部逆序入栈 A[++top] = cha.array[j]; if (A[top] == '^') top--; // ε 不占栈位 } else { // 表格为空,语法错误 print(); print1(); cout << "出错" << endl; exit(1); } } } while (finish == 0);这段代码做了三件事,值得一行一行掰开看。
第一件是弹出栈顶。x = A[top--]先取值再自减,所以取完之后top指向的是“弹出之后的栈顶”。这个顺序决定了后面print()里为什么写a <= top + 1——它要打印的是弹出之前的栈内容,top + 1正好是被弹出的那个符号还占着的位置。看起来像下标越界,其实是故意留的。我见过有人把它“修”成a <= top,结果每次输出的分析栈都少一个符号,和教科书上的推导过程对不上,验收时被判了错。
第二件是终结符匹配。走这条路说明栈顶已经是一个不可再展开的符号,只能和当前输入字符硬碰。碰上了就b++推进输入指针,碰不上就报错。注意ch = B[++b]而不是ch = B[b++],顺序反了会漏掉一个字符,症状是i+i#这种最简单的东西都能报错。
第三件是非终结符展开。先遍历v2拿到行号m,再遍历v1拿到列号n,查C[m][n]。有产生式就把右部逆序压栈——因为栈是后进先出,右部第一个符号应该最后压入才能最先被处理。E → TG压完栈里是#GT,T在栈顶,下一步就该展开T了,和图解推导完全一致。压完再检查栈顶是不是'^',是就top--把 ε 抹掉,等价于“这个非终结符什么都没产生”。
拿i+i*i#走一遍,输出应该是这样:
0 #E i+i*i# E->TG 1 #GT i+i*i# T->FS 2 #GSF i+i*i# F->i 3 #GSi i+i*i# 匹配 4 #GS +i*i# S->^ 5 #G +i*i# G->+TG 6 #GT+ +i*i# 匹配 7 #GT i*i# T->FS 8 #GSF i*i# F->i 9 #GSi i*i# 匹配 10 #GS *i# S->*FS 11 #GSF* *i# 匹配 12 #GSF i# F->i 13 #GSi i# 匹配 14 #GS # S->^ 15 #G # G->^ 16 # # acc!这份输出可以直接当验收标准用。步骤数、每一步的分析栈内容和剩余串都必须对得上,一旦中间某步多一个^或者少一个符号,说明length字段或者逆序入栈的循环写错了。
3.3 出错分支与中间结果输出,以及那个没有校验的acc
两个输出函数是配套的,print()打分析栈,print1()打剩余串并做对齐:
void print() { // 输出分析栈 for (int a = 0; a <= top + 1; a++) cout << A[a]; cout << "\t\t"; } void print1() { // 输出剩余输入串 for (int jj = 0; jj < b; jj++) cout << " "; // 用空格补出已读走部分的宽度 for (int jj = b; jj <= l; jj++) cout << B[jj]; cout << "\t\t\t"; }print1()里那两个循环是有讲究的。第一个循环按已读长度b补空格,第二个循环从b打到l,这样剩余串在视觉上会随着输入指针右移而左移,读者一眼就能看出“已经吃掉了几个字符”。对齐靠的是等宽字体,换个字体或者控制台用比例字体就会歪,这算是原始版本的一个观感缺陷,不影响正确性。b <= l里那个等号保证最后一个#也会被打出来。
每个错误出口都是同一个套路:print(); print1(); cout << "出错" << endl; exit(1);。先把当前的分析栈和剩余串打出来,再退出。这个设计对应实验要求里那句“显示分析至此所得的中间结果”,是有意义的——它让你知道分析是在哪一步卡住的。但exit(1)是个硬伤:进程直接没了,后面的输入再也处理不了,也拿不到任何返回值去做批量测试。
然后是 3.2 节里那个x == '#'的分支。它只检查了“栈顶是不是#”,没检查“当前输入符是不是也已经是#”。正常情况下这两件事同时成立:输入i#,展开完E → TG、T → FS、F → i,i匹配之后栈里剩#,输入指针也停在#上,此时判 acc 没问题。可如果输入是ii#这种明显非法的串呢?第一个i匹配完,S → ε、G → ε一路消掉,栈里同样只剩#,而输入指针还停在第二个i上——程序照样打acc!,把错误串判成了 RIGHT。这个漏洞不修,错例测试里只要放一条ii#就会露馅。
4. 编译与验收:把这份 C++ 源码跑到输出 RIGHT 的完整步骤
4.1 编译环境与那三个被时代抛下的头文件
原文开头是这么三行:
#include <iostream.h> #include <stdio.h> #include <stdlib.h> #include <string.h><iostream.h>是 C++ 标准化之前的写法,VC++ 6.0 时代的东西。现在随便一个 g++ 或 clang 都会直接报fatal error: iostream.h: No such file or directory。互联网上流传的几个版本几乎都保留了这个头,所以第一步必须改:
#include <iostream> #include <cstring> #include <cstdlib> using namespace std;改完还要注意main的返回值。原文写的是void main(),在部分编译器上会警告甚至在严格模式下拒绝编译,顺手改成int main()并在末尾return 0;更稳妥。除此之外代码本身用的是很朴素的 C 风格写法,strcpy、cout、exit混用,标准 C++ 编译器都能吃下来,不需要额外的库。
编译命令就一行:
g++ -std=c++11 -o parser parser.cpp-std=c++11其实用不上新特性,写不写都行,写上是为了避免某些环境下默认标准的差异。编完直接./parser运行,Windows 下则是parser.exe。程序启动后会打印一行提示,告诉你只能分析由i、+、-、*、/、(、)构成、以#结尾的串,然后等你输入。
提示:输入的时候注意
cin >> ch是逐字符读取并且会跳过空白,所以i + i * i #这种带空格的写法和i+i*i#效果完全一样。这一点在测试时挺方便,但也意味着你没法用空格来构造“非法字符”的错例。
4.2 正确用例和错例的验收清单
实验要求里明确写了“供测试的例子应包括符合语法规则的语句,及分析程序能判别的若干错例”。下面这几组是我每次都会跑的,覆盖了文法里每一条产生式:
| 输入串 | 期望输出 | 覆盖的产生式 |
|---|---|---|
i# | RIGHT | E→TG, T→FS, F→i, G→ε, S→ε |
i+i# | RIGHT | G→+TG |
i-i-i# | RIGHT | G→-TG,验证左结合 |
i*i/i# | RIGHT | S→*FS, S→/FS |
(i+i)*i# | RIGHT | F→(E),验证嵌套 |
((i))# | RIGHT | F→(E) 的递归嵌套 |
i+# | ERROR | 加减号右侧缺运算对象 |
(i+i# | ERROR | 右括号缺失 |
i i# | ERROR | 两个运算对象之间缺运算符 |
# | ERROR | 空串不是该文法的句子 |
前六条都应该走到acc!,后四条应该在某个步骤打出“出错”。跑(i+i)*i#的时候特别值得盯一眼步骤数——括号嵌套会让栈深度明显变长,如果这里出现栈内容错乱,多半是A[30]快撑不住了,只是还没越界。
还有一种情况要单独提:i i#这条,在未修正 3.3 节那个acc判定漏洞之前,程序会输出 RIGHT。这不是你代码写错了,是原始版本的逻辑缺陷。验收时如果老师拿这条来试,就得先把判定补上:把if (x == '#')改成if (x == '#' && ch == '#'),这样栈顶到#但输入还有剩余时,会落进下面的x == ch判断,'#' != 'i',正常报错。
4.3 和实验一扫描器对接:两种做法
实验要求第 2 条写的是“将词法、语法分析合在一起构成一个完整的程序”。原始代码其实没做这件事,它直接让用户敲i和运算符,把词法分析那一步跳过了。真要对接实验一的扫描器,有两种做法,复杂度差得挺远。
第一种是离线对接,适合只想过验收的。实验一输出的是UCON,PL,UCON,MU,ID这样的单词串,写个小脚本把它翻译成i+i*i这种单字符形式,存成文本文件,再把程序的输入重定向过去:
./parser < tokens.txttokens.txt里就一行i+i*i#。这样两边程序完全不动,中间加一层格式转换。缺点是每次改测试用例都要手工转一遍,而且cin >> ch会把换行和空格都跳掉,多行输入会被拼成一行,遇到需要分条测试的场景就不方便。
第二种是在线对接,把词法分析器做成一个函数塞进来。核心改动是定义一个取下一个 token 的函数,替换掉主循环里的ch = B[++b]:
// 从扫描器取下一个 token,返回对应的单字符表示 char nextToken() { Token tk = scanner.next(); // 实验一扫描器的接口 switch (tk.kind) { case TOK_UCON: case TOK_ID: return 'i'; // 常量和变量都归约为 i case TOK_PLUS: return '+'; case TOK_MINUS: return '-'; case TOK_STAR: return '*'; case TOK_SLASH: return '/'; case TOK_LP: return '('; case TOK_RP: return ')'; case TOK_EOF: return '#'; default: return '?'; // 非法 token,交给语法分析器报错 } }这里的关键决策是把UCON和ID都映射成i。原始文法里F → i只有一个候选,不区分常量和变量,所以映射是安全的。一旦你想区分(比如后面要生成三地址码,常量可以直接进常量表,变量要查符号表),就得把文法改成F → UCON | ID,终结符表、预测分析表、列数全都要跟着扩。这个改动不算大,但牵一发动全身,建议先把单字符版本跑通再去动它。
对接时还要处理一个错位问题:语法分析器是“看一个、用一个”,标准 LL(1) 只需要一个向前看符号,所以nextToken()必须能缓存当前 token。简单做法是维护一个cur变量,初始化时取一次,每次匹配成功后取下一次,别在判断分支里反复调next(),否则一个 token 会被消费两次。
5. 避坑与排查:这套 LL(1) 分析器最常翻车的五个地方
5.1 编译与输入阶段的坑
坑一:iostream.h找不到,或者改了头文件之后strcpy报错。
现象是编译直接中断,报fatal error: iostream.h: No such file or directory;把#include <iostream.h>改成#include <iostream>之后,又冒出一堆strcpy was not declared in this scope。
原因是<iostream.h>属于标准前的旧头文件,现代编译器只认<iostream>;而strcpy声明在<cstring>里,旧代码靠<string.h>隐含引入,换成 C++ 风格头文件后这条路径断了。
解决办法是把四个头文件整体换成#include <iostream>、#include <cstring>、#include <cstdlib>,再补一行using namespace std;。不要图省事只改第一个,后面几个会连环报错。另外void main()一并改成int main(),否则在某些编译选项下会直接拒绝。
坑二:输入忘了打#,程序看起来像卡死。
现象是敲完i+i*i按回车,光标停在那里不动,没有任何输出,等多久都没反应。
原因在读入循环写的是do { cin >> ch; ... } while (ch != '#');,没有#这个循环就永远不退出,一直在等下一个字符。
解决办法是输入时务必以#结尾,或者在读入循环里加一个计数器,超过B数组容量就报“输入过长”退出。后一种做法更稳妥,因为它同时防住了B[30]溢出的问题——一个超过 30 个字符的表达式会直接把栈外的内存写花,症状是程序跑飞或者输出乱码,比卡死更难查。
5.2 分析表映射与文法改动引入的坑
坑三:改了个运算符顺序,正确的表达式全报 ERROR。
现象是原来的i+i#能跑通,往v1里加了个%之后,连i+i#都开始报错,而且报错位置很靠前,往往第一步展开就挂了。
原因是v1、v2这两个数组的顺序和C表的行列下标是硬绑定的。C[0][0] = e这一句里的两个0,分别意味着“第 0 行是 E”和“第 0 列是i”。只要在v1中间插入一个符号,i之后所有符号的列号都往后挪了一位,可C表里的硬编码下标没动,整张表就错位了。
解决办法是两条:要么只往数组末尾追加新符号,绝不动已有顺序;要么把填表的下标全部改成用查表函数算出来的变量,比如C[idxNonTerm('E')][idxTerm('i')] = e;,让代码自己去对齐。后者改动量大但一劳永逸,尤其是文法还要继续扩的时候值得做。
坑四:^处理漏了,分析栈里堆满 ε,最后栈溢出。
现象是分析过程能跑很多步,但栈内容越来越长,^符号越积越多,最后程序崩溃或者输出一堆乱码。
原因有两个层面。表层是if (A[top] == '^') top--;这一句被漏写或者写错了位置——它必须紧跟在逆序入栈之后、且只检查一次栈顶。深层原因是char A[30]这个定长数组太小,即使 ε 处理正确,一个深度嵌套的表达式(比如七八层括号)也能把栈撑到 30 以上,越界写会直接踩坏旁边的B数组。
解决办法是把A从定长 char 数组换成std::vector<char>,用push_back/pop_back自动扩容;同时把 ε 的处理抽成一个显式判断,别依赖“栈顶恰好是^”这种隐式约定。真要保留数组,至少把容量提到 256 并在压栈前加边界检查。
5.3 接受判定与错误恢复的坑
坑五:错例被判成 RIGHT,或者一出错就什么中间结果都看不到。
现象有两种。一种是输入ii#、
本文还有配套的精品资源,点击获取