简介《实验二--语法分析程序设计与实现.doc》是一份面向编译原理课程的实验文档聚焦语法分析程序的设计、编制与调试适合正在完成词法分析后需要实现 LL(1)、递归下降、算符优先等典型分析方法的本科学生参考。文档以算术表达式简化子集为分析对象给出了 BNF 定义及 LL(1) 文法改写过程并提供了完整的 C 源程序、预测分析表填充逻辑、分析栈和剩余串的输出设计以及“RIGHT/ERROR”判定与出错说明的中间结果展示思路能够帮助读者对照掌握自上而下语法分析的实现细节。压缩包内仅含 1 个 doc 文件整体大小 127KB内容精炼、针对性强。该文档已有 143 人学习下载可辅助实验二的程序调试验证也可作为实验报告的写作框架参考。1. 语法分析程序设计与实现为什么 LL(1) 用“最笨”的查表法判定句法第一次接触语法分析程序设计与实现容易以为编译器在这里“读懂”了算术表达式——理解优先级、结合性、括号配对。真实情况远没有那么浪漫LL(1) 分析器不计算、不推理只做三件事——读一个输入符号查一张二维预测分析表决定栈顶非终结符如何展开。这样一套机械流程却能精确判定ii*i#是合法句子而ii#在第二个处直接报错。反直觉的是看起来和数学定义一一对应的文法E → ET | E-T | T恰恰是自顶向下分析的死敌推导 E 要先推导 E循环永远走不完。于是必须改写成右递归形态E → T G、G → TG | -TG | ^分析才能跑起来。搞懂这张表和这个栈就抓住了编译前端最核心的骨架。2. 文法改写左递归为什么是 LL(1) 的死穴FIRST 与 FOLLOW 如何铺平预测表2.1 左递归自顶向下分析的第一道鬼打墙LL(1) 的全称是Left-to-right scan从左到右扫描输入、Leftmost derivation最左推导、1token lookahead向前看一个输入符号。它要求分析器在每一个推导步骤里只看当前输入符号就能唯一确定该用哪条产生式展开栈顶的非终结符。而左递归产生式E → E T恰恰破坏了这种“唯一性”想展开 E先看到右部第一个符号还是 E于是又得展开 E又看到 E陷入无限循环。即使加上向前看 1 个符号的缓冲也无法跳出这个循环因为根本走不到产生式里的任何终结符。这就是为什么原始文法 G2[E] 不能直接用于 LL(1)。原始定义写的是E → T | ET | E-T T → F | T*F | T/F F → i | (E)三个非终结符里E 和 T 都带左递归。如果把这份文法直接喂给自顶向下分析器分析ii*i#时第一步就卡死栈顶 E 该选E→T还是E→ET输入是i两条产生式看起来都“可能”实际根本无法机械判定。消除左递归不是可选项而是 LL(1) 能跑起来的前提条件。2.2 从 G2[E] 到 LL(1) 文法E → T G、T → F S 的变换逻辑消除左递归有标准套路对形如A → Aα | β的规则改写成A → βA和A → αA | ^其中^表示空串也就是“到此为止不再展开”。套到 G2[E] 上E 的产生式里非左递归的起点是 Tα 是T和-T于是得到E → T G G → T G | -T G | ^ T → F S S → *F S | /F S | ^ F → (E) | i这份代码里用G扮演E的角色用S扮演T的角色。从语义上看G是“加减号的尾巴”它先看有没有或-有就继续吃掉一个项再接尾巴没有就变成空S同理负责吃掉*和/。这种右递归形态保证每一步展开的右部第一个符号要么是终结符要么是能继续推进的非终结符推导不会回到自己头上。需要注意F → (E)里出现了括号包围的 E这不是左递归——括号是终结符它阻断了“推导又回到 E 自己”的路径。分析(ii)#时栈顶 F 遇到输入(查表知道走F → (E)压入括号和 E下一次循环栈顶变成(先匹配掉括号再进入括号内的表达式分析。这正是设计者挑选这个文法做实验的原因它同时覆盖了递归嵌套、运算符优先级分层和空产生式三种典型情况。2.3 FIRST 集与 FOLLOW 集手工算一遍表的每个格子才有出处预测分析表不是拍脑袋填的。每个格子 M[A, a] 是否填入产生式A → α由两个集合决定FIRST(α)表示 α 能推导出的所有可能句首终结符如果 α 能推导出空串还要看FOLLOW(A)——所有合法句型中可能紧跟 A 之后的终结符集合。这份实验代码虽然没有显式写出集合计算但分析表每一格的填法背后都是这两套集合。非终结符FIRSTFOLLOWE{ i, ( }{ ), # }G{ , -, ^ }{ ), # }T{ i, ( }{ , -, ), # }S{ *, /, ^ }{ , -, ), # }F{ i, ( }{ *, /, , -, ), # }FOLLOW 的计算最能体现“继承”关系E → T G中 T 后面跟的是 GFIRST(G)里去掉空串得到{, -}所以这两个符号进入FOLLOW(T)G 又能推导出空串说明 T 也可能是句子的结尾部分于是FOLLOW(E) {), #}也并入FOLLOW(T)。同理T → F S把{*, /}和FOLLOW(T)传给FOLLOW(F)。这套推导链一旦算错分析表就会填错程序就会把合法输入判成 ERROR——这是后面避坑章节要展开的经典翻车点。3. 预测分析表每个格子怎么来的空槽位为什么意味着“此路不通”3.1 表的结构与两条填表规则这份程序的预测分析表是 5 行 8 列行下标 0 到 4 对应非终结符E, G, T, S, F列下标 0 到 7 对应终结符i, , -, *, /, (, ), #。每个格子存一条产生式记录格子为空表示“当前输入符号不该出现在这个非终结符的推导里”。程序用origin N作为空槽哨兵查表时一旦取出origin N的记录立即判定输入串不是句子。填表规则只有两条。规则一对产生式A → α若终结符 a 属于FIRST(α)就把这条产生式填入M[A, a]。规则二若 α 能推导出空串则对 b ∈FOLLOW(A)把A → α填入M[A, b]。规则二专门处理空产生式的落点它们不落在 FIRST 能覆盖的列那些列已经被带终结符的产生式占了而是落在 FOLLOW 集合里——这个语义后面讲^时会再展开。3.2 从填表代码反推表的全貌代码里的填表部分是直接赋值结构清晰// 行下标0E, 1G, 2T, 3S, 4F // 列下标0i, 1, 2-, 3*, 4/, 5(, 6), 7# C[0][0] e; C[0][5] e; // E → TG填在 i 和 ( 列 C[1][1] g; C[1][2] g1; // G → TG | -TG C[1][6] g2; C[1][7] g2; // G → ^FOLLOW(G) 里有 ) 和 # C[2][0] t; C[2][5] t; // T → FS C[3][1] s2; C[3][2] s2; // S → ^遇到 - 时乘除尾巴退场 C[3][3] s; C[3][4] s1; // S → *FS | /FS C[3][6] s2; C[3][7] s2; // S → ^遇到 ) # 时退场 C[4][0] f1; C[4][5] f; // F → i | (E)对照 2.3 的集合表逐格看会发现完全对得上E行的两个格子来自FIRST(TG) {i, (}G行前两格来自FIRST(TG)和FIRST(-TG)后两格来自空产生式的规则二S行最值得看——它既在*和/列填了实质产生式又在 - ) #四列填了空产生式这四列恰好是FOLLOW(S)。把整张表摊开就是这样的行\列i-*/()#EE→TGE→TGGG→TGG→-TGG→^G→^TT→FST→FSSS→^S→^S→*FSS→/FSS→^S→^FF→iF→(E)这张表其实就是整个分析器的“大脑”循环体是固定的变化全在表里。想支持新的语法结构不一定改循环代码改表就行——这是表驱动分析最迷人的地方。3.3 空产生式 ^预测表里的“降压阀”^不是真正的终结符也不是输入串里会出现的字符它只是“这条产生式右部为空”的记号。为什么需要它看G → ^的语义E 的推导是E → T GT 负责吃掉第一个项G 负责吃掉后面所有 项或- 项。如果输入到这里已经没有加号或减号了G 就必须主动退出让栈顶变成下一个要处理的符号。没有^分析走到表达式末尾时会发现 G 既没法匹配当前字符也查不到可用的表项只能报错。^的本质是“显式的推导终止”让非终结符在合适的时机体面退场。代码里对空产生式的处理有两处关键判断。第一处是查表后判断cha.origin ! N保证空产生式也是合法表项第二处是逆序入栈后判断栈顶是不是^是则弹掉for (j (cha.length - 1); j 0; j--) { A[top] cha.array[j]; // 逆序入栈 } if (A[top] ^) { top--; // 空串不进栈等价于什么都没压 }这段代码有个容易看走眼的细节逆序入栈后栈顶恰好是产生式右部第一个符号。对^这种 length 为 1 的右部压完之后栈顶是^top--把它弹掉效果就是“压了个寂寞”。如果忘了这个判断^会被当成普通栈符号继续参与循环下一步就会被判定为“既不是终结符也不是非终结符”程序行为就会变成玄学。3.4 type 对象产生式如何变成可查的数据产生式在这里被封装成一个结构体三个字段分别回答“左部是谁”“右部长什么样”“右部有多长”。class type { public: char origin; // 产生式左部大写非终结符 char array[5]; // 产生式右部字符串 int length; // 右部字符个数 }; e.origin E; strcpy(e.array, TG); e.length 2; // E → TG t.origin T; strcpy(t.array, FS); t.length 2; // T → FS g.origin G; strcpy(g.array, TG); g.length 3; // G → TG g1.origin G; strcpy(g1.array, -TG); g1.length 3; // G → -TG g2.origin G; g2.array[0] ^; g2.length 1; // G → ^把我整理过的这段和原始代码对照能看出两个实用设计第一origin虽然可以用行下标推出来但单独存一份可以方便打印E→TG这种调试信息第二array用固定长度 5是因为所有产生式右部最长不过 3 个字符留点余量省得越界。分析表C[10][10]声明成 10×10 也是同样的思路——实际只用 5×8多出来的格子只是闲置换来的是写代码时不用时刻提防数组越界。这类“宽裕声明”是实验代码的常见风格别把它当成最优做法。4. 栈驱动的分析循环#E 初始栈、终结符匹配、逆序入栈如何跑完一次推导4.1 数据结构的三个指针top、b、ch 的分工整个分析过程只有三个可变状态top指向分析栈A的栈顶b指向剩余输入串B的当前位置ch是B[b]的缓存值。初始化时栈里先压入#和E#是栈底标记E是文法的开始符号输入串读入时也在末尾补一个#。于是出现一个容易混淆的点——代码里有两个#一个在栈底一个在输入串末端。它们不是同一个东西栈里的#表示“推导的终点”输入串的#表示“源程序的终点”。只有当栈顶弹出#且当前输入符号也是#时两者相遇才输出接受标记acc!。// print()打印分析栈 for (a 0; a top 1; a) cout A[a]; // print1()打印剩余串先输出 b 个空格对齐 for (j 0; j b; j) cout ; for (j b; j l; j) cout B[j];print1 里的对齐空格不是装饰输出表格有四列步骤、分析栈、剩余串、产生式剩余串会随b前进而缩短先打b个空格能让当前输入符号的位置在视觉上保持对齐分析步骤表读起来才直观。4.2 主循环的分叉终结符匹配与非终结符展开主循环每轮第一步固定是x A[top--]取出栈顶符号top 减一。随后遍历终结符表v1判断x是不是终结符结果记在flag里。这个flag只在每轮循环内有效但并不需要在循环开头重置——因为终结符分支匹配成功后会显式置回 0非终结符分支不修改它逻辑上刚好自洽。这里的流程可以概括成do { x A[top--]; // 弹出栈顶符号 if (x 是终结符) { if (x #) finish 1; // 栈底 # 遇到输入 #接受 else if (x ch) ch B[b]; // 与当前输入匹配指针前移 else 报错退出; } else { 查预测分析表 C[m][n]; if (表项非空) 逆序入栈; else 报错退出; } } while (!finish);值得留意的是print()打印分析栈时循环条件是a top 1也就是会把刚弹出的x也画进去。所以输出表格里分析栈的“栈顶”其实多画了一位这位正是当前正在处理的符号。这不是 bug而是为了让分析过程在表格里可视化读者盯着一行输出能同时看到已推导出的栈内容和正被展开的符号。另外实验文档的输出要求写的是RIGHT/ERROR代码实际输出的是acc!/出错。题目描述和实现措辞不一致但判定逻辑并无差别对照代码时以acc!为准。4.3 逆序入栈的细节为什么压入顺序和产生式右部完全相反查表命中后有两件事先打印所用产生式再逆序入栈。逆序的原因是下一次循环立刻就要取栈顶为了让推导顺序保持从左到右产生式右部α的最后一个符号必须先压入第一个符号最后压入、最先弹出。看E → TG的展开右部是先T后G入栈却先压G再压T下一轮弹出的就是T正好匹配“先推导 T 再推导 G”的顺序。// 产生式右部逆序压栈保证下次弹出的恰好是右部第一个符号 for (j (cha.length - 1); j 0; j--) { A[top] cha.array[j]; } // 若右部只有空串标记 ^压进去之后立刻弹掉等于什么都没压 if (A[top] ^) { top--; }理解这段的另一个角度是把它当下推自动机的一次状态迁移栈顶非终结符被替换成产生式右部输入指针不动而终结符匹配是另一类迁移——栈顶终结符和输入符号对消输入指针前进。两类迁移交替进行直到栈里只剩#且输入也到#自动机到达接受态。4.4 用 ii*i# 完整跑一遍17 次循环的现场回放把前面所有机制串起来手动推演一遍。输入串ii*i#分析栈初始为#E当前输入符号是i。下表列出每步的动作和动作后的状态步骤动作动作后的分析栈底→顶动作后的剩余串1E→TG#GTii*i#2T→FS#GSFii*i#3F→i#GSiii*i#4匹配 i#GSi*i#5S→^#Gi*i#6G→TG#GTi*i#7匹配 #GTi*i#8T→FS#GSFi*i#9F→i#GSii*i#10匹配 i#GS*i#11S→*FS#GSF**i#12匹配 *#GSFi#13F→i#GSii#14匹配 i#GS#15S→^#G#16G→^##17匹配 #空#输出 acc!第 5 步最容易看懵S 是乘除法尾巴遇到却走了S→^。原因在于T → F S里 S 已经处理完属于这个项的所有乘除法不属于它必须立刻退场把栈顶让给 G 来处理加减号。这正是空产生式“在该退场时主动消失”的现场示范。5. 避坑指南这份 LL(1) 程序从能跑到跑对的五个踩坑记录5.1 输入串带空格cin 的空白跳过让剩余串错位现象按文档提示输入i i #程序要么在某个匹配步骤莫名报错要么读到的字符和你输入的完全对不上。原因代码用cin ch逐字符读入会跳过所有空白字符空格和回车不会被存进B数组导致剩余串长度和实际输入不一致。解决看懂程序提示里的限定——“只能对由i、、-、*、/、(、)构成的以#结束的字符串进行分析”意味着输入必须连写、中间不含空格。如果要支持带空格的表达式得改用cin.get()按字符原样读入并单独对空白做过滤。5.2 空产生式的 ^ 忘了弹栈栈顶变成“不存在的符号”现象分析过程前十几步一切正常到表达式末尾突然输出“出错”且报错时栈顶显示一个^。原因逆序入栈后没有执行if (A[top] ^) top--;^被当成普通符号留在栈里。它不是终结符不在v1里也不是非终结符不在v2里查表逻辑根本无法处理它。解决在入栈后立即检查栈顶遇到^就弹掉。调试时也可以加一条断言任何时刻栈里都不应该出现^。5.3 表项漏填一格合法输入被判 ERROR 的“玄学”现象输入i(i)#在某个步骤查表得到空槽程序报 ERROR但用手工推导明明能推出这个句子。原因分析表填表时漏了某个格子。最典型的是漏填E行在(列的E→TG——因为 E 能被括号开头的表达式触发但填表代码里C[0][5] e;很容易被眼滑跳过。解决对照 2.3 的 FIRST/FOLLOW 表逐行核对更靠谱的办法是把表打印出来和手工推导的预期逐格比对。这类错误最坑的地方在于它不是每次必现只有输入恰好走到那个格子时才触发看起来神出鬼没实际上就是表本身有洞。5.4 一遇错误就 exit(1)中间结果还没打全程序就没了现象错误输入时屏幕上只闪出一行“出错”分析栈、剩余串、出错位置全没看清程序就退出了。原因代码里错误分支的处理是print(); print1(); cout出错; exit(1);——打印完当前状态立刻结束进程没有给任何继续观察的机会这也和实验要求里“显示分析至此所得的中间结果”不完全吻合。解决把exit(1)换成return或break让主函数走完收尾逻辑进阶做法是做最简单的恐慌模式错误恢复从栈顶弹出非终结符继续分析剩余输入一次跑完列出所有错误位置。5.5 把 getchar() 当成逻辑的一部分现象程序在acc!之后停住要再敲一次回车才退出有人以为这是 bug有人以为这是死循环。原因原代码在acc!后写了getchar(); exit(1);getchar()只是让窗口在程序结束前暂停方便在命令行环境里看到输出与语法分析逻辑无关。解决自己改写时可以直接删掉getchar()如果保留心里清楚它是“人性化暂停”而不是分析器的一部分。分析器的真正出口只有两个接受态finish1和错误分支的退出。6. 设计取舍表驱动 LL(1) 与递归下降的界限以及分析器工具为什么不受影响6.1 同一张文法两种引擎改表 vs 改函数这份代码选择的是表驱动循环体固定不变文法知识全部沉淀在预测分析表里。另一个经典选项是递归下降——每个非终结符写一个函数函数体直接按产生式展开。表驱动的优势是文法与代码分离想加一种运算改表、加产生式对象循环不用动。递归下降的优势是报错精度高、可以在展开的同时直接插入语义动作但文法一改就要改函数结构。教学实验选表驱动本质上是想让你看到“编译器前端的骨架”是一台通用的下推自动机而不是一堆互相调用的函数。6.2 手工填表 vs 自动生成冲突报告才是真正难点这个实验真正耗时的地方不在写循环而在手算 FIRST/FOLLOW 和逐格填表。文档里所有表项都是手工算好再赋值给C数组的文法稍微复杂一点这个环节就很容易出错。真实世界的编译器前端会用工具自动生成分析表但工具输出的冲突报告比如某个格子同时出现两条产生式仍然需要人用 FIRST/FOLLOW 的思维去解读。理解这张表怎么来才能读懂工具在报什么。6.3 LL(1) 的边界与 LR 的存在意义LL(1) 能处理的文法有限不能有左递归、不能有公共左因子、预测表任何格子不能出现两条产生式。算术表达式用 LR(1) 处理其实更自然——E → ET这种左递归文法在 LR 体系下不需要改写就能直接用。那为什么实验还坚持 LL(1)因为 LL(1) 的每一步推导都对应语法树的一层生长分析过程肉眼可见教学价值远高于 LR 那套状态机。这份文档让你亲手把一张表、一个栈、一套集合运算跑通之后再接触 LR 的状态转移图会更容易理解它们是在用空间换能力。从那以后我每次拿到一个文法都会先手工算一遍 FIRST 和 FOLLOW、把预测分析表完整画出来再去读分析器代码——表画对了程序基本就成功了一半表画错了后面所有调试都是在给错误的表圆场。这份实验文档里的完整 C 源码和运行输出可以作为你对照调试的样本每一步分析过程都能在代码里找到对应的分支希望帮到你。本文还有配套的精品资源点击获取