语法分析：预测分析表与栈式驱动器实现)
简介面向编译原理课程实验与语法分析入门学习者的 DOC 文档聚焦算术表达式简化子集的语法分析程序设计与实现可用于对实验一扫描器输出的单词序列进行语法检查、结构分析及课程报告参考。内容以 BNF 定义 G2 为对象比较算符优先、递归下降、LL(1) 等思路重点展开 LL(1) 改写文法、预测分析表构造、分析栈与剩余串输出、RIGHT/ERROR 判别以及 C 源程序框架并给出流程图、数据结构、正误例测试和调试要点方便对照实现与排错。压缩包仅含 1 个 doc 文件约 127KB轻量易查阅已有 145 人学习。适合需要理解预测分析流程、补齐实验代码和梳理实验报告的学生参考。1. 语法分析为什么一个栈加一张表就能断定表达式合法多数人第一次写语法分析器都以为难点在“理解”表达式——判断优先级、还原括号层级。真正的 LL(1) 实现里没有理解这回事它只做三件事查表、出栈、压栈。把ii*i丢进去它既不计算也不建树只是机械地把栈顶的非终结符替换成某条产生式的右部直到栈和输入同时出现终结符#。互联网上流传的编译原理课程大多从 LL(1) 讲起原因也在这里——它把“语法结构”这个抽象概念压缩成一张二维表和一个字符数组所有玄学都被摊开在纸上。搞懂这套机制的价值不在应付实验空产生式为什么不能入栈、产生式逆序入栈的理由、空白表项如何充当错误前哨这些细节决定了你后面写递归下降、写 LR、甚至写一个配置 DSL 解析器时能不能一眼判断问题出在文法还是驱动器上。2. 文法改造为什么 LL(1) 必须先杀掉左递归和左公因子原始的算术表达式文法 G2 长这样看起来非常符合人类直觉E → T | ET | E-T T → F | T*F | T/F F → i | (E)E 在前T 在中F 在后优先级关系一目了然。但这份直觉文法直接交给自上而下的分析器一步都走不动。这里要拆开讲两件事左递归在机制层面到底卡在哪以及消除左递归之后为什么还要额外检查左公因子。2.1 左递归为什么会让自上而下的分析器直接瘫痪先把问题放在递归下降的视角下看。如果一条产生式对应一个函数E → ET展开就是void E() { E(); /* 一进来就调自己栈帧原地爆炸 */ match(); T(); }调用第一行就再次进入E()没有任何一个符号被消费掉输入指针原地不动调用栈无限增长。这就是左递归最直观的形态递归没有任何“前进”的承诺永远不会触底。换成表驱动的视角问题的表现形式变了但根源一样。填分析表的第一行需要先算出SELECT(E → TG)而SELECT依赖FIRST(E)偏偏E → ET的右部首符号又是 E 本身FIRST(E)的计算会回到FIRST(E)形成循环定义。换句话说你连分析表的第一行都填不满。左递归对 LL(1) 的伤害不是“运行慢”而是“编译期就无解”。标准解法是消除左递归把左递归改写成右递归E → T G G → T G | -T G | ε一般公式是对于A → Aα | β改写成A → βAA → αA | ε。代进本例α 是T或-Tβ 是T新引入的非终结符 G 承担“剩余的加减运算”这一角色。改写前后的语言是否等价可以靠推导链验证E ⇒ T G ⇒ T T G ⇒ T T ⇒ F T ⇒ i i这跟原始文法E ⇒ ET ⇒ TT ⇒ ii生成的串完全一致。差别在于推导的方向原始文法是“从左往右长”新文法是“先把左边的 T 算完再把尾巴挂在 G 上”。这个方向上的翻转正是 LL(1) 能工作的前提——分析器从左到右扫描输入天然只能先确定最左符号。顺带提醒一句改写后的 G 是右递归的它会在分析栈上“挂着”直到整个 T 分析完才轮到它。栈里能同时存在多个 G这也是后面写栈式驱动器时要处理的正常状态不是 bug。2.2 提取左公因子把“看一眼就能决定”变成可能消除左递归解决了“转不起来”但 LL(1) 还有第二个硬性要求对同一个非终结符的所有候选产生式分析器只能看一个输入符号就必须选出唯一一条。如果两条候选式的右部开头相同看一个符号根本分不出来。文档里给出的最终文法是E → TG G → TG | -TG | ε T → FS S → *FS | /FS | ε F → (E) | i逐个非终结符检查候选式的首符号G 的三条候选式首符分别是、-和空S 的两条是*和/F 的两条是(和i。全部互不相同所以这份文法不需要再做提取左公因子。这是改写之后刚好“撞上”的运气不是必然。如果 S 写成S → *FS | *F两条候选式都以*开头就必须提取出S → *S、S → FS | F否则分析表里C[S][*]这一格要填两条产生式产生冲突——这就是 LL(1) 中那个“1”的含义一格只能有一条。注意消除左递归和提取左公因子是两个独立的动作前者修的是“推不动”后者修的是“选不出”。只做前者文法照样可能填不出表。2.3 FIRST、FOLLOW、SELECT分析表里每一格的来源把文法理顺之后接下来是纯机械的集合计算。先算 FIRST非终结符FIRST 集推导过程F{ i, ( }两条候选式直接给出S{ *, /, ε }前两条给出*/第三条是空产生式T{ i, ( }T → FSFIRST(F) 不含 ε直接继承G{ , -, ε }前两条给出运算符第三条为空E{ i, ( }E → TGFIRST(T) 不含 ε直接继承再算 FOLLOW从开始符号 E 出发遇到#视为输入结束非终结符FOLLOW 集依据E{ ), # }开始符号含#F → (E)中 E 后面跟)G{ ), # }G 出现在 E 的末尾继承 FOLLOW(E)T{ , -, ), # }T 后面跟 GFIRST(G){ε} 加 FOLLOW(E)S{ , -, ), # }S 在 T 的末尾继承 FOLLOW(T)F{ *, /, , -, ), # }F 后面跟 SFIRST(S){ε} 加 FOLLOW(T)有了这两个集合SELECT规则就一句话SELECT(A → α)等于FIRST(α)如果 α 能推出 ε就把FOLLOW(A)并进来。空产生式的格子正是靠 FOLLOW 填的这一步凭直觉必错后面避坑章节会专门讲。3. 预测分析表那张二维矩阵里的每一格代表什么决策表算出来之后代码要做的事其实非常朴素把文法固化成一个二维数组行是非终结符列是终结符格子里放产生式。真正值得看的是这个“格子”用什么数据结构表示以及行列下标怎么和符号对应——这两处决定了整套程序是能改还是只能跑。3.1 产生式对象为什么存结构体而不是存编号class type { /* 一条产生式的完整描述 */ public: char origin; /* 左部大写非终结符如 E */ char array[5]; /* 右部字符序列如 {T,G} */ int length; /* 右部实际有效字符个数关键字段 */ }; type e, t, g, g1, g2, s, s1, s2, f, f1; /* 10 条产生式各一个对象 */ type C[10][10]; /* 预测分析表值语义 */这个设计有三个容易被忽略的取舍。第一array[5]是定长字符数组不保证以\0结尾。所以后面所有输出右部的代码都必须写成for (j 0; j cha.length; j)而不是cout cha.array。一旦偷懒用后者屏幕上会跟出一串内存里的脏字符。length字段不是冗余它是这套结构里唯一可信的长度来源。第二表里存的是产生式对象的副本不是编号。代价是每个格子占1 5 4字节含对齐10×10 的表大约 1KB对这个规模完全无所谓收益是查表拿到格子就能直接取右部做逆序入栈省掉一张“编号 → 产生式”的间接表。常见的实现思路是存整数编号更省内存但那要多一次数组跳转在教学规模的程序里不划算。第三origin字段同时承担两个职责既是左部符号名又是“这一格有没有产生式”的标志。空表项统一初始化为Nfor (m 0; m 4; m) for (n 0; n 7; n) C[m][n].origin N; /* N 表示该格为空即语法错误 */用一个合法符号集之外的字符当哨兵比用空指针或单独的布尔数组更省事代价是可读性——N这个约定必须写注释否则三个月后没人记得它代表什么。3.2 行列下标的硬编码表能填对但很难改终结符和非终结符各有一个字符数组下标就是列号和行号char v1[20] {i,,-,*,/,(,),#}; /* 终结符 → 列号 0..7 */ char v2[20] {E,G,T,S,F}; /* 非终结符 → 行号 0..4 */填表代码直接按下标赋值C[0][0] e; C[0][5] e; /* E→TG : 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→FS : 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 和 F→(E) */对照 2.3 节算出的集合每一格都能解释清楚。C[0][0]和C[0][5]是SELECT(E→TG) {i, (}对应列 0 和列 5C[1][6]和C[1][7]是G→ε落在FOLLOW(G) {), #}上C[3][1]、C[3][2]、C[3][6]、C[3][7]同理是S→ε落在FOLLOW(S)上C[3][3]和C[3][4]则是S的两条非空产生式落在FIRST上。把这些格子还原成表格更直观行\列i-*/()#EE→TGE→TGGG→TGG→-TGG→εG→εTT→FST→FSSS→εS→εS→*FSS→/FSS→εS→εFF→iF→(E)这里有个血泪经验v1和v2的顺序就是所有C[m][n]下标的语义。一旦你为了“看起来顺眼”把v1改成{i,(,),,-,*,/,#}上面十几行赋值全部失效程序照样能编译、照样能跑只是分析结果错得毫无规律。我一般会这么理解这种“下标即语义”的写法是教学代码的典型妥协真实实现会用mapchar,int或枚举把位置编码和符号解耦改文法时只动一个函数。3.3 空白格不是摆设它是错误检测的前哨LL(1) 分析表有一个很强的性质每个空格都对应一个必定出错的输入状态。当栈顶是非终结符 A、当前输入符号是 a而C[A][a]为空时说明不存在任何一条以 a 开头的 A 产生式输入串一定不属于该文法。驱动器里的判断就一行cha C[m][n]; if (cha.origin ! N) { /* 有产生式正常推导 */ /* 输出并逆序入栈 */ } else { /* 空格立即判定错误 */ print(); print1(); cout 出错 endl; exit(1); }这个错误检测发生在推导之前而不是等输入读完才发现不匹配。对i*i#这种串读到*时栈顶是 TC[T][*]为空程序立刻报错并打印当前栈和剩余串——错误位置精确到符号这就是表驱动相对“扫完整串再判断”的优势。代价是这套实现只做检测不做恢复一遇错就exit(1)。真实编译器要在这里接错误恢复跳过输入符号直到遇到FOLLOW(A)中的符号弹出栈顶继续分析。LL(1) 的恢复之所以相对好写正是因为FOLLOW集天然告诉了你“这个非终结符结束后可以期待什么”。4. 栈式驱动器分析栈与剩余串指针如何协同推进表是静态的驱动器是动态的。这一章看的是运行时状态怎么变化栈里放什么、指针怎么走、产生式右部按什么顺序压进去。4.1 两个数组、三个游标char A[30]; /* 分析栈栈底在 A[0] */ char B[30]; /* 剩余输入串 */ int j 0, b 0, top 0, l; /* j:输入长度计数 b:当前读位置 top:栈顶 l:串长 */初始化状态是A[0] #、A[1] E、top 1即栈里从底到顶是#E输入指针指向第一个符号。整个分析过程就是反复看A[top]它是终结符就走匹配是非终结符就查表推导直到栈顶的#和输入末尾的#对上。有一点需要说明print()从A[0]顺序打到A[top1]所以屏幕上看到的栈是左边栈底、右边栈顶。#E表示栈底是#、栈顶是E。这个方向和很多教科书图示相反读输出时容易看反。4.2 逆序入栈为什么循环要倒着写推导发生时要把产生式右部压进栈。核心代码只有三行但顺序极其关键for (j cha.length - 1; j 0; j--) /* 从右往左压 */ A[top] cha.array[j]; if (A[top] ^) /* 空产生式标记不入栈 */ top--;以E → TG为例cha.array {T,G}length 2。正序压栈会得到栈顶G而下一个该处理的符号明明是T——分析器会拿G去和输入比第一步就跑偏。逆序压栈后栈顶是T符合“最左推导”的语义栈顶永远是当前最左未展开的符号。这就是自顶向下分析的本质——栈顶对应当前句型的第一个符号。很多人在这一步翻车不是因为不懂文法而是因为没意识到栈是“后进先出”的而推导要“从左到右”。4.3 空产生式为什么必须做特殊判断文档里的文法用^表示 ε对应产生式是g2.array[0] ^、length 1。如果按统一逻辑逆序压栈^会被压进A里成为一个真实的栈符号下一轮循环拿它去查v1找不到它不是终结符查v2也找不到它不是非终结符驱动器直接卡死或误判。所以压栈之后必须立刻检查栈顶是不是^是就弹掉。这一句if (A[top] ^) top--;等价于“这条产生式右部为空不产生任何待匹配符号”。代码里这个判断写在压栈循环之后而不是之前是因为^在array里也占了一个位置length 1统一处理更省分支。另一种常见做法是给空产生式单独设length 0让压栈循环自然空转就不需要这个判断了。两种写法都对前者改动小后者更干净。4.4 走一遍ii*i#每一步的栈和输入把驱动器跑起来用ii*i#做输入完整轨迹如下栈从左到右是栈底到栈顶步骤分析栈剩余输入动作0#Eii*i#初始1#GTii*i#E→TG2#GSFii*i#T→FS3#GSiii*i#F→i4#GSi*i#i 匹配输入前进5#Gi*i#S→ε6#GTi*i#G→TG7#GTi*i# 匹配输入前进8#GSFi*i#T→FS9#GSii*i#F→i10#GS*i#i 匹配输入前进11#GSF**i#S→*FS12#GSFi#* 匹配输入前进13#GSii#F→i14#GS#i 匹配输入前进15#G#S→ε16##G→ε17(空)#栈顶 # 匹配acc有两点值得注意。第一第 5 步S→ε是因为当前输入是而在FOLLOW(S)里不在FIRST(S)里——这一格能填对全靠 2.3 节把 FOLLOW 算准了。第二第 15、16 两步连续弹空是因为i*i项已经完整S 和 G 都该收缩了。任何一步的栈内容对不上回查的一定是分析表那一格填错了。5. 常见问题排查LL(1) 实现里最容易翻车的五处写完能跑不等于写对语法分析器最坑的地方在于错误往往不报错只是判错。下面五条是这类程序里反复出现的故障按“现象 → 原因 → 解决”整理。5.1 合法串被判 ERROR出错点总在运算符上现象输入ii#或(i)#跑到或)就打印“出错”但i#单独测又正常。原因空产生式的列填少了。G→ε只填了#列漏了)列而FOLLOW(G) {), #}是两个符号。S→ε同理FOLLOW(S) {,-,),#}四个列都要填。凭直觉填表时很容易只想到“串结束了才该收缩”忘了右括号和运算符同样意味着当前非终结符已经结束。解决填表前把每个非终结符的 FOLLOW 集写在纸上空产生式逐个符号对照着填填完反向检查表里每个ε产生式的格子数必须等于对应 FOLLOW 集的大小。5.2 第一步就错栈顶符号和预期对不上现象输入第一个符号就匹配失败或者输出里第一步的产生式右部是反的。原因产生式右部按正序压栈了。for (j 0; j length; j)会让右部最后一个符号跑到栈顶而栈顶应该是右部第一个符号。解决循环改成for (j length - 1; j 0; j--)。判断方法很简单压完栈后栈顶必须等于产生式右部的第一个字符这一点可以在代码里加一句断言。5.3 栈里出现^或者程序陷入死循环现象输出里分析栈莫名其妙多出^符号或者某一步之后栈和输入都不再变化程序卡死。原因空产生式压栈后没弹出。^既不在终结符表里也不在非终结符表里查表时行号和列号都停在上一轮的脏值上可能反复取到同一条产生式形成“推导—压^—再推导”的死循环。解决压栈后立刻判断if (A[top] ^) top--;或者把空产生式的length设为 0从源头避免压入。5.4 最后一个字符总是出错或者打印多一位现象i#分析到最后一格报错或者输出剩余串时#后面跟着一个乱码字符。原因输入长度算错了。读入循环是“先存再自增然后判断是否为#”所以#也被存进了Bj指向#的下一格l j比实际串长多 1。之后for (j b; j l; j) cout B[j];用就会多打一个越界字符而栈顶比较逻辑如果用l当边界也会错位。解决统一口径——l表示“最后一个有效下标”取l j - 1所有遍历写j l。或者l表示长度取l j所有遍历写j l。两种都行混用必错。5.5 出错只给一个 ERROR完全不知道错在哪现象程序判定输入非法只输出一行“出错”没有栈内容、没有剩余串、没有位置。原因错误分支里直接exit(1)print()和print1()可能被漏掉或者调用了但缓冲区没刷新。分析类程序一旦丢了现场就只能靠猜。解决错误分支至少输出三样东西——当前分析栈、剩余输入串、出错时输入指针的下标。栈告诉你“期望什么”剩余串告诉你“实际是什么”两者一对照问题基本就定位了。这也是表驱动相对手写递归下降的一个隐性优势栈里那一串符号天然就是“当前期待的符号集合”比递归下降的调用栈好读得多。注意还有一种不报错的坑——文法抄写和代码不一致。比如把S → *FS | /FS误抄成F → -FS程序能编译、能跑分析表也填得满只是遇到减号时行为完全不对。改完文法一定要拿“加、减、乘、除、括号、单变量”六类输入各测一遍。6. 设计取舍LL(1) 能走多远以及为什么工业编译器最后都换道把这份程序跑通之后最值得琢磨的不是代码本身而是它失效的边界在哪里。LL(1) 的表达力有一个硬上限同一非终结符的各候选式首符号集合必须互不相交且集合内不含 ε 冲突。算术表达式经过改写恰好满足但真实语言的很多结构不满足。悬空 else 是经典案例if (E) S和if (E) S else S两条候选式的前缀完全一样看一个符号根本分不出该选哪条。C 语言里“声明”和“表达式”共享同一批标识符开头也是同样的问题。遇到这类文法要么提取公因子提到文法面目全非要么就得换分析方法。换道之后的选择本质上是在三种方案之间权衡维度LL(1) 表驱动手写递归下降LR(1)/LALR文法限制无左递归、无左公因子、SELECT 不冲突同 LL(1)但可手工回溯几乎无限制能处理左递归改文法的成本改表数据不必动驱动器改函数逻辑分散改表但表生成器复杂错误诊断强栈内容即“期望符号集”强可携带语义信息弱项集不直观实现复杂度低低高分析方向自顶向下最左推导自顶向下自底向上最右推导的逆诊断能力这一栏经常被低估。LL(1) 出错时栈里剩下的符号就是一份现成的“期望列表”可以输出“此处期望 - ) #实际读到*”。LR 分析器出错时手上只有一堆状态编号要生成同样友好的提示得多做一层映射。所以不少真实编译器在前端用 LL 系或手写递归下降而不是 LR图的就是错误信息好写。另一个取舍是栈的容量。这份实现用char A[30]固定长度对算术表达式够用但嵌套括号一深就溢出比如((((((i))))))每层括号要压进(和 F 相关的符号深度增长很快。教学代码用定长数组是为了省事真实实现必须用动态栈或者显式检查top越界——栈溢出和语法错误必须区分开否则用户会看到一个语法完全正确的表达式被判 ERROR排查起来极度痛苦。至于性能LL(1) 是严格的线性时间每个输入符号最多被匹配一次每条产生式最多被展开一次总步数是 O(n)常数很小。真正拖慢前端的一般不是分析算法而是词法部分的字符串处理和符号表查找。最后说个我自己的教训。早年写这类程序我习惯先把代码敲完再补测试结果第一次跑ii*i#就 ERROR回头查了两个小时文法、三个小时分析表最后发现是逆序入栈的循环写反了——一个字符的差别。从那以后我每次写分析器都强制先把分析表打印成表格拿三五个串手工推一遍栈确认每一步和表对得上再去写驱动器。表对了驱动器只剩机械翻译表错了代码写得再漂亮也是白搭。这份资源里除了完整的文法改写和源代码还有测试用例和每一步的分析输出对着它把上面那张轨迹表自己走一遍比读十遍算法描述都管用。希望帮到你。本文还有配套的精品资源点击获取
