简介面向编译原理课程实验的学习者这份文档围绕语法分析程序的设计与实现展开可配合实验一所得单词序列完成语法检查与结构分析。内容以算术表达式简化子集为对象给出 BNF 定义及 LL(1) 文法改写讲解预测分析表的构造与使用并附 C 实现的源程序框架涉及分析栈、剩余串、产生式结构体以及 RIGHT/ERROR 输出等关键环节。文档还梳理实验目的、基本要求、流程图与数据结构考虑、词法与语法分析合并调试、正例与错例测试等便于读者理解自上而下语法分析的完整链路也可作为课程实验报告与程序调试的参考。资源包共 1 个 doc 文件约 127KB轻量便携适合直接查阅与打印。已有 143 人学习适合需要补足 LL(1) 分析表、递归下降或算符优先等分析方法实践的高校学生与自学者。1. 从词法输出到语法判定这套语法分析程序到底要交出什么语法分析程序设计与实现这道题很多人写完词法分析器就松懈了——扫描器能把ii*i切成一串UCON, PL, UCON, MU, ID就觉得大功告成真正卡住的是下一步给这串单词一个结构上的说法。这个实验要的东西很具体给定文法 G2[E]读入上游扫描器吐出的单词序列判断它是不是该文法的句子是就输出 RIGHT 并逐行打印分析栈、剩余串和所用产生式不是就输出 ERROR同时把出错位置、当时的栈内容和缺失符号讲清楚。互联网上能搜到的同类代码大多把分析表写死在 main 里、错一个字符就整段退出交上去能跑答辩一问就露馅。这套方案适合正在做编译原理课设、需要一份能演示、能讲清推导过程、还能顺手接上实验一扫描器的完整实现。2. 文法改造从带左递归的 G2[E] 到可以查表的 LL(1)2.1 为什么先做左递归消除而不是直接写递归下降题目给的原始文法是左递归的E → T | ET | E-T T → F | T*F | T/F F → i | (E)E → ET这种形式如果直接照抄成递归下降函数E() { E(); match(); T(); }第一次调用就自己调自己栈帧一路压到爆程序直接崩。这是编译原理实验里最经典的一课文法好看不等于能直接实现。消除直接左递归的标准做法是把A → Aα | β拆成两个非终结符A → βA A → αA | ε套到 E 和 T 上再引入两个新非终结符 G管加减和 S管乘除得到改写后的 LL(1) 文法编号产生式来源说明0E → TGE 的左递归被拆成「先一个 T再循环加减」1G → TGG 承担原来 E 里T的部分2G → -TG同上减号分支3G → ε加减链结束4T → FST 的左递归拆成「先一个 F再循环乘除」5S → *FSS 承担*F6S → /FS除号分支7S → ε乘除链结束8F → (E)括号因子递归回到 E9F → i运算对象无符号常数和变量统一记作 i这里有个容易忽略的设计取舍为什么选 LL(1)而不是算符优先、SLR(1) 或 LR(1)。算符优先表要单独算优先关系遇到一元负号和括号嵌套时优先关系容易冲突出错SLR(1) 和 LR(1) 要做项目集规范族、构造 DFA工作量比这个实验的定位大得多一个课设周期内很难做扎实递归下降写起来最直观但左递归要手工消、错误定位全靠异常抛出答辩时讲不清「第几步用了哪条产生式」。LL(1) 的产出是三张能手工推导、能当场合对的表——FIRST 集、FOLLOW 集、预测分析表每一步分析都能打印出来这对需要现场演示的实验来说是最优解。改写之后还要确认一件事新文法确实是 LL(1) 的。判定标准是对同一个非终结符的任意两条候选产生式 α、β满足FIRST(α) ∩ FIRST(β) ∅并且如果 β 能推出 ε还要满足FIRST(α) ∩ FOLLOW(A) ∅。拿 G 来看TG的 FIRST 是{}-TG的 FIRST 是{-}ε的 FIRST 是空集三者互不相交再看 S*FS是{*}、/FS是{/}也互不相交。这一步核过后面填表才不会出现一格两个产生式的冲突。2.2 提取左公因子与空产生式的书写约定标准流程里消除左递归之后通常还要提取左公因子但这份文法不需要。判断依据看 FF → i和F → (E)两个候选右部的首符号分别是i和(交集为空公共前缀长度为零没有可提的东西。如果文法写成F → i | i(E)那就必须提成F → i F、F → (E) | ε否则查表时F遇到i不知道该选哪条。实验报告里把这段判断写出来比只贴一张表更能说明你真的想过。空产生式的书写是个小设计点。教材上写 ε但代码里用单字符栈存符号直接写希腊字母会带来编码和比较的麻烦。通常的做法是用^代替 ε占一个 char 位压栈时有特殊判断——遇到^就不压。原文代码里用的就是这个约定g2.array[0]^、g2.length1把空产生式也当成一条长度为 1 的正常产生式来存结构统一只在压栈那一刻特判。注意^只能出现在产生式右部、且只能单独出现。如果哪条产生式写成S → ^FS那不是 ε是把^当成了一个普通终结符查表时永远匹配不上分析会卡死在这一格。2.3 FIRST 与 FOLLOW 集先手算再写进代码很多人图省事直接从网上抄一张分析表塞进程序跑通了就交。这种做法的风险是只要文法改一个符号整张表就全错而且你没法解释表里的每一项为什么在那儿。可靠的做法是先把 FIRST 和 FOLLOW 手推一遍写在实验报告里代码里的表只是这份手算结果的转录。非终结符FIRST 集FOLLOW 集E{ i, ( }{ #, ) }G{ , -, ε }{ #, ) }T{ i, ( }{ , -, ), # }S{ *, /, ε }{ , -, ), # }F{ i, ( }{ *, /, , -, ), # }推导顺序建议按依赖关系走先 FIRST从最底层的 F 往上算F 的 FIRST 是{i, (}T → FS 的 FIRST 等于 FIRST(F)E → TG 的 FIRST 等于 FIRST(T)所以 E、T、F 三个的首符集完全一样。G 和 S 因为有 ε 产生式FIRST 里要带上 ε。FOLLOW 的推法反过来从开始符号 E 往下传。E 是开始符号先塞一个#E → TG 说明 FOLLOW(G) 包含 FOLLOW(E)所以 G 拿到#G → TG 说明 T 后面紧跟 GFOLLOW(T) 包含 FIRST(G) 去掉 ε 的部分即{, -}同时因为 G 能推出 εFOLLOW(T) 还要并入 FOLLOW(G)于是 T 的 FOLLOW 变成{, -, #}。用同样的传递关系往下推S 从 T → FS 拿到 FOLLOW(T)F 从 T → FS 和 S → *FS 拿到{*, /}再并上 FOLLOW(S)。推完之后有一项自检特别好用每一个非终结符的 FOLLOW 集大小应该只增不减而且#必须出现在 E、G、T、S、F 全部五个里因为整条文法的所有非终结符最终都可能走到串尾。如果算完发现 F 的 FOLLOW 里没有#那一定是某一步传递漏了。3. 数据结构与分析表把文法固化进一个 5×8 的二维表3.1 终结符表、非终结符表与产生式结构体LL(1) 分析程序的核心数据结构只有四个终结符集合、非终结符集合、产生式数组、预测分析表。终结符集合决定了分析表的列非终结符集合决定了行两边顺序一旦定死就不能再动——这是后面所有查表逻辑的基准。终结符按i - * / ( ) #排下标 0 到 7非终结符按E G T S F排下标 0 到 4。这里要注意一个反直觉的地方非终结符的顺序不是按 E、T、F 的语法层级排而是按改写后的产生式出现顺序 E、G、T、S、F。如果按E T F排后面填表和查表用的行号就对不上症状是程序能跑但判定结果和手推不一致排查起来非常费时间。产生式用结构体存左部一个字符、右部一个字符数组、长度一个整数// 产生式右部最多 3 个符号^ 表示 ε struct Prod { char lhs; // 左部非终结符取值 E/G/T/S/F char rhs[4]; // 右部符号串以 \0 结尾 int len; // 右部符号个数ε 产生式记 1 }; // 10 条产生式下标即编号与分析表里的值一一对应 Prod P[10] { {E, TG, 2}, // 0: E - TG {G, TG, 3}, // 1: G - TG {G, -TG, 3}, // 2: G - -TG {G, ^, 1}, // 3: G - ε {T, FS, 2}, // 4: T - FS {S, *FS, 3}, // 5: S - *FS {S, /FS, 3}, // 6: S - /FS {S, ^, 1}, // 7: S - ε {F, (E), 3}, // 8: F - (E) {F, i, 1} // 9: F - i };这样设计的直接好处是分析表里只需要存产生式的编号一个 int打印时用P[id].lhs和P[id].rhs拼字符串不用在每个表项里重复存一份右部。原文代码把type对象直接塞进C[10][10]每个格子都是一个完整的结构体副本内存浪费是小事关键是填表代码变成了C[0][0]e; C[1][1]g;这种一个字母一个字母的赋值改一条产生式要改好几处非常容易错位。3.2 预测分析表的填充规则与空项语义分析表是 5 行 8 列的二维数组行对应非终结符列对应当前输入符号。填充规则来自 FIRST 和 FOLLOW对产生式A → α凡a ∈ FIRST(α)就把M[A][a]填成这条产生式的编号如果 α 能推出 ε则凡b ∈ FOLLOW(A)也把M[A][b]填成这条产生式。剩下没被覆盖的格子是空项表示「此处无产生式可用」也就是语法错误的位置。// 行序 E G T S F列序 i - * / ( ) #值 -1 表示空项 int M[5][8]; void initTable() { for (int i 0; i 5; i) for (int j 0; j 8; j) M[i][j] -1; // 先全部置空 // E: FIRST(TG) { i, ( } M[0][0] 0; M[0][5] 0; // G: 遇 走 1遇 - 走 2遇 ) 和 # 走 εFOLLOW(G) { ), # } M[1][1] 1; M[1][2] 2; M[1][6] 3; M[1][7] 3; // T: FIRST(FS) { i, ( } M[2][0] 4; M[2][5] 4; // S: 遇 * 走 5遇 / 走 6遇 - ) # 走 ε M[3][1] 7; M[3][2] 7; M[3][3] 5; M[3][4] 6; M[3][6] 7; M[3][7] 7; // F: 遇 i 走 9遇 ( 走 8 M[4][0] 9; M[4][5] 8; }对着这张表可以核对几个关键格子验证理解是否正确。M[1][6]G 遇到右括号填 3意思是「括号里加减链到此结束用 ε 收尾」这正是(ii)能分析成功的原因。M[3][3]S 遇到乘号填 5 而不是 7说明乘除链要继续延伸不能提前收尾——如果这里错填成 εii*i会在第二个之前就把 S 弹空然后报出「期望 # 实际 *」这种完全对不上现象的错误。提示空项不要用 0 表示。产生式编号 0 是E → TG用 0 当空项会导致「本该报错的地方反而展开了一条产生式」程序不崩但结果全错这类 bug 比崩溃更难查。3.3 分析栈与剩余串两个指针怎么配合运行时的状态只有两个数组和两个指针。分析栈A从下标 0 往上长top指向当前栈顶剩余输入串B是一个已经归一化成终结符的字符数组末尾补#b指向当前待匹配字符。初始化时A[0]#、A[1]E、top1b0。栈里同时存终结符和非终结符靠一张终结符表区分拿弹出符号去i-*/()#里找找到就是终结符走匹配分支找不到就一定是非终结符走查表分支。这个判断每轮循环都要做一次所以必须写成函数或者每次循环开头重置标志位不能依赖一个跨轮次的全局变量。栈容量要留余量。最坏情况下(((i)))这种深层嵌套加上多次展开栈深会超过符号串长度的两倍。数组开 64 个字符够应付课设级别的测试用例但如果要演示ii*i/i-i*ii这种长串建议开到 128 并加一句越界断言出错时能立刻定位而不是段错误。4. 主控程序一趟循环走完匹配与展开4.1 初始化与主循环骨架主循环的逻辑可以概括成一句话弹出栈顶是终结符就比对输入是非终结符就查表展开直到栈顶和输入同时到达#。整个过程是一趟线性扫描没有回溯这也是 LL(1) 相比回溯法的核心优势——每个位置该用哪条产生式查表一次就定了。char A[128]; // 分析栈 char B[128]; // 剩余串已归一化为终结符并以 # 结尾 int top 0, b 0, len strlen(B); A[top] #; A[top] E; // 初始栈内容# E int step 0; while (true) { // 每步打印步骤号、分析栈、剩余串、所用产生式 printf(%-4d %-14s %-14s , step, A, B b); char X A[top--]; // 弹出栈顶符号 if (strchr(i-*/()#, X) ! NULL) { // 分支一终结符 if (X # B[b] #) { // 双 # 相遇接受 printf(acc\n); break; } if (X B[b]) { // 匹配成功输入指针后移 printf(匹配 %c\n, X); b; continue; } printf(ERROR: 期望 %c实际 %c\n, X, B[b]); break; } int m row(X), n col(B[b]); // 分支二非终结符查表 if (m 0 || n 0 || M[m][n] 0) { printf(ERROR: 非终结符 %c 遇 %c 无产生式可用\n, X, B[b]); break; } const Prod p P[M[m][n]]; printf(%c - %s\n, p.lhs, p.rhs); for (int k p.len - 1; k 0; --k) // 逆序压栈 if (p.rhs[k] ! ^) A[top] p.rhs[k]; // ε 不入栈 }这段代码里有三个地方值得单独说清楚因为它们是整份实现里最容易写错、也最容易被追问的地方。第一个是A[top--]这个写法。它先取栈顶值赋给 X再把 top 减一等价于「弹出」。写成X A[top]; top--;效果一样但合在一起更紧凑。要注意的是弹出之后 top 指向的是新的栈顶后面压栈时用A[top]先加再赋值两个操作正好对称。第二个是逆序压栈。产生式右部TG压栈后栈里从下到上必须是G、T、也就是在最顶上下一轮才能先匹配。所以循环变量k必须从p.len - 1递减到 0。如果写成正序TG压完是在最底下、G在最顶上下一轮直接去展开 G分析顺序整个乱掉——症状是单符号输入i#能过ii#就报错非常迷惑。第三个是if (p.rhs[k] ! ^)。空产生式G → ^压栈时^会被跳过栈里什么也不加等价于「G 消失了」。如果漏掉这个判断^会进入分析栈下一轮弹出时既不匹配输入、又不在非终结符表里程序直接报出「期望 ^ 实际 #」这种看不懂的错误。4.2 终结符匹配与非终结符展开的分支边界两个分支的判定依据是「弹出符号是否在终结符表里」而不是「是否大写」。用大小写判断在本题能跑因为非终结符恰好都是大写字母但这是个坏习惯一旦文法里出现id、num这类多字符终结符或者把运算对象记成小写i以外的符号判据立刻失效。正确做法是维护一张i-*/()#的字符串用strchr查。匹配分支还有一个边界要处理双#相遇必须放在「相等即匹配」之前判断。如果先判相等#和#会被当成普通终结符匹配成功、指针后移然后下一轮弹出栈里已经空了的A[top]读到垃圾值。原文代码里的做法是先判x#再exit(1)效果上也是终止但输出写的是acc!加强制退出不够干净——正常接受应该让主循环自然结束把收尾工作比如释放输入、打印统计留给循环外的代码。非终结符展开分支要处理两种失败符号不在非终结符表里说明栈被污染了通常是空产生式没跳过导致^入栈以及查表得到空项说明当前位置文法推不下去是真正的语法错误。这两种失败的信息要区分开否则调试时分不清是自己的实现 bug 还是输入的用例就该报错。4.3 接上词法分析UCON、PL、ID 怎么变成 i、、i实验二的输入是实验一扫描器的输出格式形如UCON, PL, UCON, MU, ID。语法分析器只认i - * / ( ) #这八个终结符所以中间要加一层归一化无符号常数 UCON 和标识符 ID 都映射成i加号 PL 映射成乘号 MU 映射成*除号 DI 映射成/左括号 LP、右括号 RP 各自对应末尾补#。# 把实验一输出的单词串归一化成文法终结符串 TOKEN_MAP { UCON: i, ID: i, # 常数和变量都归为运算对象 i PL: , MI: -, # 加、减 MU: *, DI: /, # 乘、除 LP: (, RP: ), # 左右括号 EOF: # # 输入结束标记 } def normalize(token_line): out [] for t in token_line.replace(, ,).split(,): t t.strip() if not t: continue if t not in TOKEN_MAP: raise ValueError(f词法单元 {t} 无法映射到终结符) # 词法层错误 out.append(TOKEN_MAP[t]) out.append(#) return .join(out)这一层的作用不只是「翻译」。词法阶段的错误比如出现、非法数字12a在这里就被拦下来抛出明确异常不会污染语法分析栈归一化之后语法分析器拿到的永远是干净的终结符串匹配分支里不需要再考虑多字符 token 的比较问题。两个实验合起来构成完整前端这也是题目要求「将词法、语法分析合在一起」的落点。注意归一化阶段不要偷偷「纠正」输入。比如遇到MI就自作主张补一个i看似提高了通过率实际上把错误输入变成了合法输入测试用例里的错例全部失效。错例必须原样传下去让语法分析器自己报错。4.4 出错信息的三类划分题目要求「不论对错都应有明确的信息输出」这句话在实现上意味着错误不能只打印一个 ERROR 了事。按出错位置分三类每类的信息内容不同第一类是词法层错误发生在归一化阶段输出「第几个 token 无法映射」此时语法分析还没开始。第二类是终结符不匹配发生在匹配分支输出「期望符号、实际符号、当前剩余串、当前栈内容」——这四项凑齐基本能定位到是多了符号还是少了符号。第三类是查表得空项发生在展开分支输出「哪个非终结符遇到哪个输入符号推不下去」这类错误通常对应「缺少运算对象」或「运算符连用」。三类错误都应该在退出前把当前的分析栈和剩余串完整打印一遍。中途结果比错误信息本身更有价值因为它是手推过程的标准答案能和自己的推导逐行对照。5. 避坑与排查语法分析程序最容易翻车的五处5.1 产生式抄错或挂错非终结符现象ii*i#被判 ERROR但手工按分析表推一遍明明是 RIGHT或者分析步骤打印出来第 3 步用的产生式和预期完全对不上。原因从教材或网络资料上抄产生式时把消除左递归引入的中间非终结符搞混了。常见错法是把S → *FS写成F → -FS或者把S → /FS挂到 F 上还有的把 ε 产生式写成S → ^FS。原文的说明文档里就出现过F--FS | /FS和S-^FS这样的笔误直接照抄进代码就是灾难。解决把 10 条产生式单独列一张表逐条和 FIRST 集对照——每条产生式右部的首符号必须落在左部非终结符的 FIRST 集里。F → -FS这条F 的 FIRST 是{i, (}根本没有-一眼就能看出错。5.2 ε 产生式被压进分析栈现象分析到ii#的最后一步栈顶弹出一个^程序报「期望 ^ 实际 #」或者 top 越界后读到乱码。原因空产生式G → ^的长度记为 1压栈循环没有跳过^把它当成普通符号压进去了。解决压栈时加一句if (p.rhs[k] ! ^)空产生式等价于「该非终结符凭空消失」。同时把「弹出符号既不是终结符也不在非终结符表里」这种情况显式判为内部错误未来再出现类似污染能第一时间暴露。5.3 逆序压栈写成了正序现象单符号输入i#能正确接受带运算符的ii#就报错报错信息往往是「期望 G 实际 」这类看着莫名其妙的内容。原因产生式右部从左到右压栈导致最左符号沉到栈底栈顶变成了最右符号。LL(1) 要求每轮处理最左符号顺序一反展开顺序全乱。解决循环写成for (int k p.len - 1; k 0; --k)。验证办法很直接对E → TG压栈后打印栈内容从顶到底应该是T、G、#如果看到G在顶上就是写反了。5.4 分析表行列索引与符号表顺序不一致现象程序不崩、每步都能打印产生式但某些合法串被判 ERROR某些非法串反而过了。把打印的产生式和手推结果对比发现第 2 步开始就分叉。原因填表时按E G T S F的顺序查表时row()函数却按E T F G S的顺序返回行号或者干脆在代码里写死M[1][3]这种魔数。两套顺序只要有一处对不上整张表就错位。解决非终结符数组和填表行序共用同一个常量表row()函数遍历这张表返回下标绝不在业务代码里写数字。终结符同理。写完之后拿M[1][6]这种已知答案的格子做一次断言等于给表加了个单元测试。5.5 输入串未校验、指针越界现象输入里混进一个非法字符程序不报错而是继续往下跑最后输出一堆乱码或者匹配完最后一个#后b继续自增读到数组外的内存段错误退出。原因读入阶段只判断了「是不是#结尾」没有校验字符是否在终结符集合内匹配成功后的b没有做上界保护。解决读入时逐字符比对终结符表非法字符立即报错退出这一点原文代码是做到了的if (ch!i ch! ...) exit(1)匹配分支里b之前加一句if (b len) break;之类的保护让越界变成可控的错误提示而不是崩溃。提示这五条里有三条5.2、5.3、5.5只在特定输入下才触发i#这种最小用例测不出来。测试集里必须包含ii*i#、(ii)*i#、ii)#这三种覆盖展开、嵌套和错误路径。6. 验收与答辩用测试用例把「能跑」变成「能证明」验收环节最忌讳的是现场敲一个ii*i#看着输出 RIGHT 就完事。评审关心的不是你跑通了一个用例而是你能不能证明这套实现对「所有」输入都成立。我的做法是准备一张固定的测试表正例、边界、错例各占一部分每条都标注它考察的是哪条设计决策。输入串期望输出考察点ii*i#RIGHT乘除优先级高于加减S 在处用 ε 收尾(ii)*i#RIGHT括号嵌套F → (E) 递归回 Ei-i/i#RIGHT同级左结合G 和 S 分别处理ii-i*i/i#RIGHT长串检验栈深度和指针边界ii)#ERROR右括号多余栈顶#与输入)不匹配(ii#ERROR括号未闭合遇#时 F 无产生式可用i*#ERROR乘号后缺运算对象F 遇#查表空项i i#ERROR缺运算符S 遇i查表空项每条错例都要能说清「错在哪一步、当时栈里是什么、为什么这一格是空的」。比如i*#走到 F 遇#那一格M[4][7] -1因为 F 的两条产生式首符集是{i, (}#不在其中也不在 FOLLOW(F) 里——这个解释比「程序报错了」有说服力得多。答辩现场我一般只讲三件事控制在五分钟内。第一件为什么选 LL(1)左递归必须消、表驱动可演示、错误可定位一句话带过对比算符优先和 SLR 的取舍。第二件三张表怎么来的FIRST 从下往上推、FOLLOW 从上往下传、分析表由前两者交叉填出顺手在白板上写FOLLOW(T) {, -, ), #}证明不是抄的。第三件错误分几类、每类输出什么。剩下的时间留给现场跑测试表让评委随便指一条错例当场定位到分析表的具体格子。有一套流程我后来每次做这类实验都强制走一遍先手推三条用例写在纸上再对着纸上的每一步去比对程序的打印输出逐行对齐。哪一行对不上问题一定在那一行对应的展开或匹配逻辑里不用满代码找。这套笨办法救过我两次——一次是逆序压栈写反一次是分析表行序错位两次都是靠「纸上有、屏幕上没有」在十分钟内定位的。希望帮到你。本文还有配套的精品资源点击获取