语法分析C++实现：预测分析表、栈式驱动与验收避坑)
简介这份文档面向计算机专业编译原理课程实验学习者聚焦语法分析程序的设计与实现帮助读者在完成词法扫描器后继续对单词序列做语法检查与结构分析。内容围绕算术表达式简化子集展开涵盖算符优先、递归下降、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 → ET的左递归是怎么被消掉的2.1 从 G2 到 G2左递归消除与提取公因子实验给的原始文法 G2[E] 长这样E → T | ET | E-T T → F | T*F | T/F F → i | (E)问题出在E → ET和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) {*, /, , -, #, )}。整理成表非终结符FIRSTFOLLOWE(,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-*/()#EE→TG空空空空E→TG空空G空G→TGG→-TG空空空G→εG→εTT→FS空空空空T→FS空空S空S→εS→εS→*FSS→/FS空S→εS→εFF→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 行只有下标 0i和 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]取第一个待分析字符栈里压入#和Etop指向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]顺序反了会漏掉一个字符症状是ii#这种最简单的东西都能报错。第三件是非终结符展开。先遍历v2拿到行号m再遍历v1拿到列号n查C[m][n]。有产生式就把右部逆序压栈——因为栈是后进先出右部第一个符号应该最后压入才能最先被处理。E → TG压完栈里是#GTT在栈顶下一步就该展开T了和图解推导完全一致。压完再检查栈顶是不是^是就top--把 ε 抹掉等价于“这个非终结符什么都没产生”。拿ii*i#走一遍输出应该是这样0 #E ii*i# E-TG 1 #GT ii*i# T-FS 2 #GSF ii*i# F-i 3 #GSi ii*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 → ii匹配之后栈里剩#输入指针也停在#上此时判 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.hiostream.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 -stdc11 -o parser parser.cpp-stdc11其实用不上新特性写不写都行写上是为了避免某些环境下默认标准的差异。编完直接./parser运行Windows 下则是parser.exe。程序启动后会打印一行提示告诉你只能分析由i、、-、*、/、(、)构成、以#结尾的串然后等你输入。提示输入的时候注意cin ch是逐字符读取并且会跳过空白所以i i * i #这种带空格的写法和ii*i#效果完全一样。这一点在测试时挺方便但也意味着你没法用空格来构造“非法字符”的错例。4.2 正确用例和错例的验收清单实验要求里明确写了“供测试的例子应包括符合语法规则的语句及分析程序能判别的若干错例”。下面这几组是我每次都会跑的覆盖了文法里每一条产生式输入串期望输出覆盖的产生式i#RIGHTE→TG, T→FS, F→i, G→ε, S→εii#RIGHTG→TGi-i-i#RIGHTG→-TG验证左结合i*i/i#RIGHTS→*FS, S→/FS(ii)*i#RIGHTF→(E)验证嵌套((i))#RIGHTF→(E) 的递归嵌套i#ERROR加减号右侧缺运算对象(ii#ERROR右括号缺失i i#ERROR两个运算对象之间缺运算符#ERROR空串不是该文法的句子前六条都应该走到acc!后四条应该在某个步骤打出“出错”。跑(ii)*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这样的单词串写个小脚本把它翻译成ii*i这种单字符形式存成文本文件再把程序的输入重定向过去./parser tokens.txttokens.txt里就一行ii*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()否则在某些编译选项下会直接拒绝。坑二输入忘了打#程序看起来像卡死。现象是敲完ii*i按回车光标停在那里不动没有任何输出等多久都没反应。原因在读入循环写的是do { cin ch; ... } while (ch ! #);没有#这个循环就永远不退出一直在等下一个字符。解决办法是输入时务必以#结尾或者在读入循环里加一个计数器超过B数组容量就报“输入过长”退出。后一种做法更稳妥因为它同时防住了B[30]溢出的问题——一个超过 30 个字符的表达式会直接把栈外的内存写花症状是程序跑飞或者输出乱码比卡死更难查。5.2 分析表映射与文法改动引入的坑坑三改了个运算符顺序正确的表达式全报 ERROR。现象是原来的ii#能跑通往v1里加了个%之后连ii#都开始报错而且报错位置很靠前往往第一步展开就挂了。原因是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::vectorchar用push_back/pop_back自动扩容同时把 ε 的处理抽成一个显式判断别依赖“栈顶恰好是^”这种隐式约定。真要保留数组至少把容量提到 256 并在压栈前加边界检查。5.3 接受判定与错误恢复的坑坑五错例被判成 RIGHT或者一出错就什么中间结果都看不到。现象有两种。一种是输入ii#、本文还有配套的精品资源点击获取 
长河君 · 2026/10/31 15:09:21 · 阅读 1.2k LL(1)语法分析C++实现：预测分析表、栈式驱动与验收避坑
简介这份文档面向计算机专业编译原理课程实验学习者聚焦语法分析程序的设计与实现帮助读者在完成词法扫描器后继续对单词序列做语法检查与结构分析。内容围绕算术表达式简化子集展开涵盖算符优先、递归下降、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 → ET的左递归是怎么被消掉的2.1 从 G2 到 G2左递归消除与提取公因子实验给的原始文法 G2[E] 长这样E → T | ET | E-T T → F | T*F | T/F F → i | (E)问题出在E → ET和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) {*, /, , -, #, )}。整理成表非终结符FIRSTFOLLOWE(,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-*/()#EE→TG空空空空E→TG空空G空G→TGG→-TG空空空G→εG→εTT→FS空空空空T→FS空空S空S→εS→εS→*FSS→/FS空S→εS→εFF→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 行只有下标 0i和 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]取第一个待分析字符栈里压入#和Etop指向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]顺序反了会漏掉一个字符症状是ii#这种最简单的东西都能报错。第三件是非终结符展开。先遍历v2拿到行号m再遍历v1拿到列号n查C[m][n]。有产生式就把右部逆序压栈——因为栈是后进先出右部第一个符号应该最后压入才能最先被处理。E → TG压完栈里是#GTT在栈顶下一步就该展开T了和图解推导完全一致。压完再检查栈顶是不是^是就top--把 ε 抹掉等价于“这个非终结符什么都没产生”。拿ii*i#走一遍输出应该是这样0 #E ii*i# E-TG 1 #GT ii*i# T-FS 2 #GSF ii*i# F-i 3 #GSi ii*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 → ii匹配之后栈里剩#输入指针也停在#上此时判 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.hiostream.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 -stdc11 -o parser parser.cpp-stdc11其实用不上新特性写不写都行写上是为了避免某些环境下默认标准的差异。编完直接./parser运行Windows 下则是parser.exe。程序启动后会打印一行提示告诉你只能分析由i、、-、*、/、(、)构成、以#结尾的串然后等你输入。提示输入的时候注意cin ch是逐字符读取并且会跳过空白所以i i * i #这种带空格的写法和ii*i#效果完全一样。这一点在测试时挺方便但也意味着你没法用空格来构造“非法字符”的错例。4.2 正确用例和错例的验收清单实验要求里明确写了“供测试的例子应包括符合语法规则的语句及分析程序能判别的若干错例”。下面这几组是我每次都会跑的覆盖了文法里每一条产生式输入串期望输出覆盖的产生式i#RIGHTE→TG, T→FS, F→i, G→ε, S→εii#RIGHTG→TGi-i-i#RIGHTG→-TG验证左结合i*i/i#RIGHTS→*FS, S→/FS(ii)*i#RIGHTF→(E)验证嵌套((i))#RIGHTF→(E) 的递归嵌套i#ERROR加减号右侧缺运算对象(ii#ERROR右括号缺失i i#ERROR两个运算对象之间缺运算符#ERROR空串不是该文法的句子前六条都应该走到acc!后四条应该在某个步骤打出“出错”。跑(ii)*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这样的单词串写个小脚本把它翻译成ii*i这种单字符形式存成文本文件再把程序的输入重定向过去./parser tokens.txttokens.txt里就一行ii*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()否则在某些编译选项下会直接拒绝。坑二输入忘了打#程序看起来像卡死。现象是敲完ii*i按回车光标停在那里不动没有任何输出等多久都没反应。原因在读入循环写的是do { cin ch; ... } while (ch ! #);没有#这个循环就永远不退出一直在等下一个字符。解决办法是输入时务必以#结尾或者在读入循环里加一个计数器超过B数组容量就报“输入过长”退出。后一种做法更稳妥因为它同时防住了B[30]溢出的问题——一个超过 30 个字符的表达式会直接把栈外的内存写花症状是程序跑飞或者输出乱码比卡死更难查。5.2 分析表映射与文法改动引入的坑坑三改了个运算符顺序正确的表达式全报 ERROR。现象是原来的ii#能跑通往v1里加了个%之后连ii#都开始报错而且报错位置很靠前往往第一步展开就挂了。原因是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::vectorchar用push_back/pop_back自动扩容同时把 ε 的处理抽成一个显式判断别依赖“栈顶恰好是^”这种隐式约定。真要保留数组至少把容量提到 256 并在压栈前加边界检查。5.3 接受判定与错误恢复的坑坑五错例被判成 RIGHT或者一出错就什么中间结果都看不到。现象有两种。一种是输入ii#、本文还有配套的精品资源点击获取