语法分析程序设计与实现：从BNF改造到预测分析表驱动)
简介这份文档面向计算机专业学习编译原理的学生聚焦语法分析程序的设计与实现帮助读者在完成词法扫描器后进一步掌握对单词序列进行语法检查与结构分析的方法。资源包共1个doc文件大小约127KB内容围绕实验目的、实验内容与要求、实验步骤、问题分析及源程序、结论等模块展开结构完整便于按实验流程对照学习。文档以算术表达式简化子集为分析对象给出BNF定义G2[E]并选用LL(1)文法改写为E→TG、T→FS等产生式配合预测分析表与C源程序展示分析栈、剩余串、终结符与非终结符等数据结构设计还包含RIGHT与ERROR判定及中间结果输出思路。目前已有143人学习适合需要完成语法分析实验、理解LL(1)预测分析流程或参考C实现细节的读者。1. 从一份“实验二”文档说起语法分析程序到底怎么落地很多人拿到“实验二–语法分析程序设计与实现.doc”这类资源第一反应是“这不就是编译原理课设吗”然后扔进收藏夹吃灰。但如果你正在做扫描器之后的语法检查模块或者想给一个表达式求值引擎加上结构校验这份文档其实是一份能直接抄作业的 LL(1) 实现模板。它把 BNF 定义、LL(1) 分析表构造、C 源码和运行结果串成了一条线核心解决的是给定词法分析输出的单词串比如 UCON, PL, UCON, MU, ID怎么判断它是不是合法算术表达式并在出错时告诉你栈里剩了什么。适合刚学完编译原理、需要动手写一个能跑的分析程序的新手也适合想快速回顾预测分析表驱动流程的熟手。下面我按“文法怎么改 → 分析表怎么填 → 代码怎么跑 → 坑在哪”拆一遍。2. LL(1) 文法改造从左递归到预测分析表2.1 为什么原始 BNF 不能直接喂给 LL(1)文档里给出的原始文法 G2[E] 是左递归形式E → ET | E-T | TT → T*F | T/F | F。LL(1) 要求每个非终结符的产生式右部首符号集不相交而左递归会让 FIRST(E) 和 FIRST(T) 纠缠在一起递归下降会直接死循环。所以文档做了标准改造消除左递归、提取左公因子引入 G、S 两个新非终结符。改造后的产生式是E → TGG → TG | -TG | εT → FSS → *FS | /FS | εF → (E) | i这里 ε 在源码里用字符^表示因为 C 风格字符串不好直接存空串。注意文档里有一处笔误它把 F 的产生式写成了F → -TG | /FS这明显是排版错位正确应为F → (E) | i。如果你照着错的那行去填分析表F 行会全乱。我一般会先手写一遍 FIRST 和 FOLLOW 集来验证FIRST(E){(, i}FIRST(G){, -, ε}FIRST(T){(, i}FIRST(S){, /, ε}FIRST(F){(, i}FOLLOW(E){#, )}FOLLOW(G){#, )}FOLLOW(T){, -, #, )}FOLLOW(S){, -, #, )}FOLLOW(F){, /, , -, #, )}。这些集合直接决定分析表哪些格子填产生式、哪些格子填空。2.2 预测分析表的填充逻辑与源码映射文档用了一个type类来存产生式origin存左部非终结符array存右部字符串length存右部长度。分析表C[10][10]是一个二维对象数组行对应非终结符 E、G、T、S、Fv2 数组列对应终结符 i、、-、*、/、(、)、#v1 数组。初始化时全部originN表示空然后按产生式逐格填充。我把它整理成一张对照表方便你核对行\列i-*/()#EE→TGE→TGGG→TGG→-TGG→εG→εTT→FST→FSSS→εS→εS→*FSS→/FSS→εS→εFF→iF→(E)源码里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 行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 行。填表时最容易翻车的是 S 行的 ε 产生式当 lookahead 是 、-、)、# 时都要填 S→ε少填一个就会在分析ii#时卡在 S 上。2.3 分析栈与剩余串的驱动流程主循环的逻辑是取栈顶 x如果 x 是终结符就和当前输入字符 ch 比较相等则匹配并读下一个不等则报错如果 x 是非终结符就用 x 和 ch 查表得到产生式把产生式右部逆序压栈ε 不压然后打印这一步。文档里A[top--]先弹出栈顶print()打印的是弹出前的栈内容所以你会看到分析栈里始终包含当前正在处理的符号。剩余串用B数组存b指向当前待匹配位置print1()先输出对齐空格再输出B[b..l]。这个设计有个小坑print()里循环条件是atop1而top在弹出后已经减一所以实际打印的是从栈底到原栈顶的字符刚好把刚弹出的符号也显示出来方便对照产生式。如果你自己重写建议把打印时机统一放在“查表后、压栈前”这样每一步的栈和剩余串对应关系更直观。3. 把源码跑起来从输入串到 RIGHT/ERROR 的完整复现3.1 环境准备与源码修正文档源码是早期 C 风格用了#include iostream.h和#include stdio.h在现在的 g 上直接编译会报错。我一般会做三处最小修改把iostream.h改成iostream并加using namespace std;把strcpy和exit的头文件补成cstring和cstdlib把void main()改成int main()并在末尾return 0;。另外源码里print1()的循环for(j0;jb;j) cout ;在 b 较大时对齐会偏可以改成cout string(b, );。这些改动不影响算法逻辑只是让它在现代编译器上能过。// 修正后的关键片段头文件与主函数签名 #include iostream #include cstring #include cstdlib using namespace std; 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; // l 为输入串长度 class type { public: char origin; // 产生式左部 char array[5]; // 产生式右部 int length; // 右部长度 }; type e, t, g, g1, g2, s, s1, s2, f, f1; type C[10][10]; // 预测分析表 int main() { // ... 原有初始化与分析表填充 ... return 0; }3.2 输入串的构造与词法对接文档要求输入是由实验一扫描器输出的单词串但源码里直接让用户输入字符并且只接受i、、-、*、/、(、)、#。这意味着你需要把词法分析输出的UCON、ID、PL、MU等记号映射成这里的终结符UCON和ID都映射成iPL映射成MU映射成-MUL映射成*DIV映射成/左右括号保留末尾补#。比如词法输出UCON, PL, UCON, MU, ID对应输入串就是ii-i#。如果你直接拿UCON当输入程序会报“输入串中有非法字符”并退出。常见做法是在词法分析器里加一个toParserToken()函数做这层映射而不是让语法分析器去认单词类别。// 词法记号到语法终结符的映射示例 char mapToken(const string token) { if (token UCON || token ID) return i; if (token PL) return ; if (token MU) return -; if (token MUL) return *; if (token DIV) return /; if (token LP) return (; if (token RP) return ); return #; // 结束符 }3.3 运行结果解读与出错信息定位输入ii*i#程序会输出每一步的分析栈、剩余字符和所用产生式最后打印acc!。如果输入ii#在匹配完第一个后栈顶是 T当前字符是查表 T 行 列为空程序会打印当前栈和剩余串然后输出“出错”并退出。文档里出错处理只打印了栈和剩余串没有指出是哪个非终结符卡住了。我一般会在else分支里加一行cout 出错非终结符 x 遇到 ch endl;这样调试时能直接定位。另外注意exit(1)会直接终止进程如果你是在集成环境里跑建议改成返回错误码或抛异常方便上层捕获。输入串预期输出关键检查点ii*i#RIGHTacc!S 行 * 列填 S→*FS(ii)#RIGHTacc!F 行 ( 列填 F→(E)ii#ERRORT 行 列为空报错位置在第二个 ii)#ERROR匹配到 ) 时栈顶不是 )报错i*i#RIGHTacc!G 行 # 列填 G→ε提示测试错例时至少覆盖“多余运算符”“括号不匹配”“非法字符”三类每类跑一遍看报错信息是否指向正确位置。4. 避坑与排查LL(1) 分析程序常见的五个翻车点4.1 现象输入ii#程序卡死或无限循环原因G 行或 S 行的 ε 产生式没有填全导致查表返回originN时走了出错分支但出错分支里没有exit或break循环继续。文档源码里出错分支有exit(1)但如果你自己改写成不退出就会死循环。解决确保 G 行在)和#列都填G→εS 行在、-、)、#列都填S→ε出错分支必须终止当前分析。4.2 现象分析(ii)*i#时在)处报错原因F 行(列填了F→(E)但 E 行)列没有填产生式而 G 行)列填了G→ε。当栈顶是 G、当前字符是)时应该用 G→ε 弹出 G然后栈顶变成)与输入匹配。如果 G 行)列漏填就会在 G 处报错。解决对照 2.2 节的表逐格检查特别是 G 行和 S 行的 ε 列。4.3 现象输入串末尾没有#程序读入越界原因源码用do { cin ch; B[j] ch; } while(ch ! #);读入如果用户输入没有#会一直读到缓冲区空j超出B[30]。解决在循环里加if (j 29) { cout 输入过长或缺少结束符# endl; exit(1); }并提示用户必须以#结尾。4.4 现象词法输出的UCON直接输入被拒原因语法分析器只认单字符终结符不认单词类别。解决在词法分析输出和语法分析输入之间加映射层把UCON、ID统一转成i把PL、MU等转成对应运算符末尾补#。这一步不做实验一和实验二就接不上。4.5 现象分析表打印出来全是N查表永远出错原因C[m][n].originN初始化后填充时行列索引写反了。文档里C[0][0]e表示 E 行 i 列但如果你把m当列、n当行就会填到错误位置。解决在填充前打印v2[m]和v1[n]确认行列对应关系或者直接用二维数组加字符串键来存产生式避免索引混淆。5. 进阶技巧把分析表从硬编码改成可配置文档里的分析表是硬编码在main里的改一条产生式就要重新编译。如果你要分析不同的表达式文法或者想让学生自己填表验证可以把分析表抽成外部文件。我一般用 CSV 存第一行是终结符列表第一列是非终结符单元格填产生式右部空表示出错^表示 ε。读取时用ifstream逐行解析动态构建type对象数组。这样换文法只需要改 CSV不用动源码。// 从 CSV 加载分析表的简化示例 #include fstream #include sstream #include vector #include string void loadTable(const string filename, type table[10][10], vectorchar terms, vectorchar nonterms) { ifstream fin(filename); string line; getline(fin, line); // 首行,i,,-,*,/,(,),# stringstream ss(line); string cell; getline(ss, cell, ,); // 跳过左上角 while (getline(ss, cell, ,)) terms.push_back(cell[0]); int row 0; while (getline(fin, line)) { stringstream rs(line); getline(rs, cell, ,); // 行首非终结符 nonterms.push_back(cell[0]); int col 0; while (getline(rs, cell, ,)) { if (!cell.empty() cell ! ^) { table[row][col].origin nonterms.back(); strcpy(table[row][col].array, cell.c_str()); table[row][col].length cell.size(); } else if (cell ^) { table[row][col].origin nonterms.back(); table[row][col].array[0] ^; table[row][col].length 1; } else { table[row][col].origin N; } col; } row; } }加载后主循环里查表逻辑不变只是C[m][n]换成了动态加载的table。这样你可以把实验二扩展成一个小型语法分析框架词法输出 → 映射 → 加载表 → 驱动分析 → 输出步骤。验证方法也很直接用文档里的五个测试串跑一遍对比输出是否与硬编码版本一致再改一条产生式比如把F→(E)改成F→[E]看 CSV 改完后程序是否能识别新括号。从那以后我每次接语法分析任务都会先把分析表抽成配置文件再写驱动代码这样调文法不用反复编译省下的时间够多跑好几组错例。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/14 17:09:42 · 阅读 1.2k LL(1)语法分析程序设计与实现：从BNF改造到预测分析表驱动
简介这份文档面向计算机专业学习编译原理的学生聚焦语法分析程序的设计与实现帮助读者在完成词法扫描器后进一步掌握对单词序列进行语法检查与结构分析的方法。资源包共1个doc文件大小约127KB内容围绕实验目的、实验内容与要求、实验步骤、问题分析及源程序、结论等模块展开结构完整便于按实验流程对照学习。文档以算术表达式简化子集为分析对象给出BNF定义G2[E]并选用LL(1)文法改写为E→TG、T→FS等产生式配合预测分析表与C源程序展示分析栈、剩余串、终结符与非终结符等数据结构设计还包含RIGHT与ERROR判定及中间结果输出思路。目前已有143人学习适合需要完成语法分析实验、理解LL(1)预测分析流程或参考C实现细节的读者。1. 从一份“实验二”文档说起语法分析程序到底怎么落地很多人拿到“实验二–语法分析程序设计与实现.doc”这类资源第一反应是“这不就是编译原理课设吗”然后扔进收藏夹吃灰。但如果你正在做扫描器之后的语法检查模块或者想给一个表达式求值引擎加上结构校验这份文档其实是一份能直接抄作业的 LL(1) 实现模板。它把 BNF 定义、LL(1) 分析表构造、C 源码和运行结果串成了一条线核心解决的是给定词法分析输出的单词串比如 UCON, PL, UCON, MU, ID怎么判断它是不是合法算术表达式并在出错时告诉你栈里剩了什么。适合刚学完编译原理、需要动手写一个能跑的分析程序的新手也适合想快速回顾预测分析表驱动流程的熟手。下面我按“文法怎么改 → 分析表怎么填 → 代码怎么跑 → 坑在哪”拆一遍。2. LL(1) 文法改造从左递归到预测分析表2.1 为什么原始 BNF 不能直接喂给 LL(1)文档里给出的原始文法 G2[E] 是左递归形式E → ET | E-T | TT → T*F | T/F | F。LL(1) 要求每个非终结符的产生式右部首符号集不相交而左递归会让 FIRST(E) 和 FIRST(T) 纠缠在一起递归下降会直接死循环。所以文档做了标准改造消除左递归、提取左公因子引入 G、S 两个新非终结符。改造后的产生式是E → TGG → TG | -TG | εT → FSS → *FS | /FS | εF → (E) | i这里 ε 在源码里用字符^表示因为 C 风格字符串不好直接存空串。注意文档里有一处笔误它把 F 的产生式写成了F → -TG | /FS这明显是排版错位正确应为F → (E) | i。如果你照着错的那行去填分析表F 行会全乱。我一般会先手写一遍 FIRST 和 FOLLOW 集来验证FIRST(E){(, i}FIRST(G){, -, ε}FIRST(T){(, i}FIRST(S){, /, ε}FIRST(F){(, i}FOLLOW(E){#, )}FOLLOW(G){#, )}FOLLOW(T){, -, #, )}FOLLOW(S){, -, #, )}FOLLOW(F){, /, , -, #, )}。这些集合直接决定分析表哪些格子填产生式、哪些格子填空。2.2 预测分析表的填充逻辑与源码映射文档用了一个type类来存产生式origin存左部非终结符array存右部字符串length存右部长度。分析表C[10][10]是一个二维对象数组行对应非终结符 E、G、T、S、Fv2 数组列对应终结符 i、、-、*、/、(、)、#v1 数组。初始化时全部originN表示空然后按产生式逐格填充。我把它整理成一张对照表方便你核对行\列i-*/()#EE→TGE→TGGG→TGG→-TGG→εG→εTT→FST→FSSS→εS→εS→*FSS→/FSS→εS→εFF→iF→(E)源码里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 行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 行。填表时最容易翻车的是 S 行的 ε 产生式当 lookahead 是 、-、)、# 时都要填 S→ε少填一个就会在分析ii#时卡在 S 上。2.3 分析栈与剩余串的驱动流程主循环的逻辑是取栈顶 x如果 x 是终结符就和当前输入字符 ch 比较相等则匹配并读下一个不等则报错如果 x 是非终结符就用 x 和 ch 查表得到产生式把产生式右部逆序压栈ε 不压然后打印这一步。文档里A[top--]先弹出栈顶print()打印的是弹出前的栈内容所以你会看到分析栈里始终包含当前正在处理的符号。剩余串用B数组存b指向当前待匹配位置print1()先输出对齐空格再输出B[b..l]。这个设计有个小坑print()里循环条件是atop1而top在弹出后已经减一所以实际打印的是从栈底到原栈顶的字符刚好把刚弹出的符号也显示出来方便对照产生式。如果你自己重写建议把打印时机统一放在“查表后、压栈前”这样每一步的栈和剩余串对应关系更直观。3. 把源码跑起来从输入串到 RIGHT/ERROR 的完整复现3.1 环境准备与源码修正文档源码是早期 C 风格用了#include iostream.h和#include stdio.h在现在的 g 上直接编译会报错。我一般会做三处最小修改把iostream.h改成iostream并加using namespace std;把strcpy和exit的头文件补成cstring和cstdlib把void main()改成int main()并在末尾return 0;。另外源码里print1()的循环for(j0;jb;j) cout ;在 b 较大时对齐会偏可以改成cout string(b, );。这些改动不影响算法逻辑只是让它在现代编译器上能过。// 修正后的关键片段头文件与主函数签名 #include iostream #include cstring #include cstdlib using namespace std; 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; // l 为输入串长度 class type { public: char origin; // 产生式左部 char array[5]; // 产生式右部 int length; // 右部长度 }; type e, t, g, g1, g2, s, s1, s2, f, f1; type C[10][10]; // 预测分析表 int main() { // ... 原有初始化与分析表填充 ... return 0; }3.2 输入串的构造与词法对接文档要求输入是由实验一扫描器输出的单词串但源码里直接让用户输入字符并且只接受i、、-、*、/、(、)、#。这意味着你需要把词法分析输出的UCON、ID、PL、MU等记号映射成这里的终结符UCON和ID都映射成iPL映射成MU映射成-MUL映射成*DIV映射成/左右括号保留末尾补#。比如词法输出UCON, PL, UCON, MU, ID对应输入串就是ii-i#。如果你直接拿UCON当输入程序会报“输入串中有非法字符”并退出。常见做法是在词法分析器里加一个toParserToken()函数做这层映射而不是让语法分析器去认单词类别。// 词法记号到语法终结符的映射示例 char mapToken(const string token) { if (token UCON || token ID) return i; if (token PL) return ; if (token MU) return -; if (token MUL) return *; if (token DIV) return /; if (token LP) return (; if (token RP) return ); return #; // 结束符 }3.3 运行结果解读与出错信息定位输入ii*i#程序会输出每一步的分析栈、剩余字符和所用产生式最后打印acc!。如果输入ii#在匹配完第一个后栈顶是 T当前字符是查表 T 行 列为空程序会打印当前栈和剩余串然后输出“出错”并退出。文档里出错处理只打印了栈和剩余串没有指出是哪个非终结符卡住了。我一般会在else分支里加一行cout 出错非终结符 x 遇到 ch endl;这样调试时能直接定位。另外注意exit(1)会直接终止进程如果你是在集成环境里跑建议改成返回错误码或抛异常方便上层捕获。输入串预期输出关键检查点ii*i#RIGHTacc!S 行 * 列填 S→*FS(ii)#RIGHTacc!F 行 ( 列填 F→(E)ii#ERRORT 行 列为空报错位置在第二个 ii)#ERROR匹配到 ) 时栈顶不是 )报错i*i#RIGHTacc!G 行 # 列填 G→ε提示测试错例时至少覆盖“多余运算符”“括号不匹配”“非法字符”三类每类跑一遍看报错信息是否指向正确位置。4. 避坑与排查LL(1) 分析程序常见的五个翻车点4.1 现象输入ii#程序卡死或无限循环原因G 行或 S 行的 ε 产生式没有填全导致查表返回originN时走了出错分支但出错分支里没有exit或break循环继续。文档源码里出错分支有exit(1)但如果你自己改写成不退出就会死循环。解决确保 G 行在)和#列都填G→εS 行在、-、)、#列都填S→ε出错分支必须终止当前分析。4.2 现象分析(ii)*i#时在)处报错原因F 行(列填了F→(E)但 E 行)列没有填产生式而 G 行)列填了G→ε。当栈顶是 G、当前字符是)时应该用 G→ε 弹出 G然后栈顶变成)与输入匹配。如果 G 行)列漏填就会在 G 处报错。解决对照 2.2 节的表逐格检查特别是 G 行和 S 行的 ε 列。4.3 现象输入串末尾没有#程序读入越界原因源码用do { cin ch; B[j] ch; } while(ch ! #);读入如果用户输入没有#会一直读到缓冲区空j超出B[30]。解决在循环里加if (j 29) { cout 输入过长或缺少结束符# endl; exit(1); }并提示用户必须以#结尾。4.4 现象词法输出的UCON直接输入被拒原因语法分析器只认单字符终结符不认单词类别。解决在词法分析输出和语法分析输入之间加映射层把UCON、ID统一转成i把PL、MU等转成对应运算符末尾补#。这一步不做实验一和实验二就接不上。4.5 现象分析表打印出来全是N查表永远出错原因C[m][n].originN初始化后填充时行列索引写反了。文档里C[0][0]e表示 E 行 i 列但如果你把m当列、n当行就会填到错误位置。解决在填充前打印v2[m]和v1[n]确认行列对应关系或者直接用二维数组加字符串键来存产生式避免索引混淆。5. 进阶技巧把分析表从硬编码改成可配置文档里的分析表是硬编码在main里的改一条产生式就要重新编译。如果你要分析不同的表达式文法或者想让学生自己填表验证可以把分析表抽成外部文件。我一般用 CSV 存第一行是终结符列表第一列是非终结符单元格填产生式右部空表示出错^表示 ε。读取时用ifstream逐行解析动态构建type对象数组。这样换文法只需要改 CSV不用动源码。// 从 CSV 加载分析表的简化示例 #include fstream #include sstream #include vector #include string void loadTable(const string filename, type table[10][10], vectorchar terms, vectorchar nonterms) { ifstream fin(filename); string line; getline(fin, line); // 首行,i,,-,*,/,(,),# stringstream ss(line); string cell; getline(ss, cell, ,); // 跳过左上角 while (getline(ss, cell, ,)) terms.push_back(cell[0]); int row 0; while (getline(fin, line)) { stringstream rs(line); getline(rs, cell, ,); // 行首非终结符 nonterms.push_back(cell[0]); int col 0; while (getline(rs, cell, ,)) { if (!cell.empty() cell ! ^) { table[row][col].origin nonterms.back(); strcpy(table[row][col].array, cell.c_str()); table[row][col].length cell.size(); } else if (cell ^) { table[row][col].origin nonterms.back(); table[row][col].array[0] ^; table[row][col].length 1; } else { table[row][col].origin N; } col; } row; } }加载后主循环里查表逻辑不变只是C[m][n]换成了动态加载的table。这样你可以把实验二扩展成一个小型语法分析框架词法输出 → 映射 → 加载表 → 驱动分析 → 输出步骤。验证方法也很直接用文档里的五个测试串跑一遍对比输出是否与硬编码版本一致再改一条产生式比如把F→(E)改成F→[E]看 CSV 改完后程序是否能识别新括号。从那以后我每次接语法分析任务都会先把分析表抽成配置文件再写驱动代码这样调文法不用反复编译省下的时间够多跑好几组错例。希望帮到你。本文还有配套的精品资源点击获取