简介面向编译原理课程的 LL(1) 语法分析器实验完整资源包适合计算机专业本科生完成实验二时参考。内容围绕给定文法构造预测分析表并从键盘读入输入串判断其是否为该文法的句子若判定正确则通过若存在语法错误则给出报错能够帮助学习者理解 FIRST/FOLLOW 集计算、预测分析表生成及语法错误处理流程。压缩包共 13 个文件涵盖 cpp 源代码、可直接运行的 exe、docx/doc 实验报告、mp4 讲解视频以及 Makefile 等工程配置文件整体仅 24.81MB便于下载后对照学习与运行验证。已有 3101 人学习查看。资源附带配套讲解视频和程序设计思想文档从原理剖析到操作演示均有覆盖同时包含两版源程序实现主程序与法二.cpp可对照不同写法实验要求文档与工程布局也一并给出适合需要快速上手、补全实验报告或参考完整实现细节的学生。1. 编译原理实验二LL(1)语法分析器一份能直接跑的资源包编译原理实验二的 LL(1) 语法分析器应该是我见过最能直接救急的资源包之一。你不用再对着课本手敲一遍预测分析表的构造过程——这份 zip 里把源代码、可执行程序、实验报告、程序设计思想和讲解视频都打包好了解压之后在 Dev-C 里打开 .dev 工程重新编译一次就能跑。适合谁一是实验截止前还没调通的本科在读学生二是想在一两天内把 FIRST 集、FOLLOW 集、预测分析表这套流程完整看懂的工作人员。它解决的问题很具体给定一个 LL(1) 文法程序能自动构造预测分析表再从键盘读入输入串判断该串是否为该文法的句子正确就通过错误就报错。如果你的目标就是弄明白这套机制并且拿到一个能交差的实验结果这个包值得你拆开看完。2. LL(1) 原理与程序结构为什么自顶向下分析选 LL(1)先把课本上最核心的东西过一遍不然你拿到源码也看不懂它为什么要这么写。LL(1) 三个字符的含义是第一个 L 表示从左到右扫描输入串第二个 L 表示每次推导都选择最左非终结符进行展开括号里的 1 表示每一步只需要向前看一个输入符号就能决定用哪条产生式。这意味着整个分析过程是确定性的不需要回溯因此也叫预测分析。2.1 为什么这个选型能跑通LL(1) 的分析逻辑自顶向下分析有一个天然问题如果文法有左递归分析器会陷入无限循环。LL(1) 通过两个手段绕开这个问题——一是要求文法必须是 LL(1) 文法也就是说构造出来的预测分析表里每个格子最多只有一个产生式二是程序内部对终结符和非终结符分别做 FIRST 集和 FOLLOW 集的迭代计算把“当前非终结符遇到哪个输入符号该选哪条产生式”这件事预先算好存进一张二维表里。分析时只查表不试错。所以你在实验要求里看到的“构造相应 LL(1) 预测分析表”本质上是把文法翻译成一张查找表。之后的判定过程反而简单维护一个栈栈顶是非终结符就从表里查动作栈顶是终结符就和输入串的当前符号比对。全部匹配完且栈空句子就通过任何一步匹配不上就报错。理解了这个逻辑你再看资源包里的源码会发现代码结构基本就是按照“读文法 → 算 FIRST/FOLLOW → 建表 → 分析输入串”四段式组织的。2.2 资源包里的文件分别怎么用拿到 zip 第一件事不是解压就运行而是先理清包里各文件的角色。以下是我根据文件名和实验场景整理出来的对应关系文件类型实际作用LL(1)语法分析器.cpp源代码主程序源码核心逻辑所在法二.cpp源代码第二种实现版本一般用于对比或验证不同写法LL(1)语法分析程序.devDev-C 工程双击它就能在 Dev-C 里打开整个工程Makefile.win构建脚本Windows 下 Dev-C 用的编译规则文件LL(1)语法分析器.o中间产物编译过程中生成的二进制目标文件不用管LL(1)语法分析程序.exe可执行程序已经编译好的成品可直接运行LL(1)语法分析器.exe可执行程序另一个可执行文件可能是法二编译出的版本LL(1)语法分析程序.layout布局文件Dev-C 的窗口布局记录删了也不影响编译讲解视频.mp4视频对着流程讲解程序思路和操作方法程序设计思想.docx文档说明整体设计思路写实验报告时可以直接参考编译原理实验二.docx实验文档实验要求、过程记录模板《编译原理》实验二-2020.doc任务书当年的实验任务说明包含验收标准建议你的操作顺序是先看《编译原理》实验二-2020.doc 确认验收要求再看程序设计思想.docx 了解思路最后才打开源码。视频留着跑通之后再看因为你已经动手之后再看讲解视频效率最高。2.3 FIRST 集和 FOLLOW 集预测分析表的两块地基预测分析表的每个格子 M[A][a] 表示“栈顶是非终结符 A、当前输入符号是 a 时用哪条产生式去展开”。要算出这张表必须先算 FIRST 集和 FOLLOW 集。FIRST(α) 是从符号串 α 能推导出的所有终结符开头字符的集合FOLLOW(A) 是在所有句型中可能紧跟在非终结符 A 之后的终结符集合再加上输入结束符 #。计算过程是一个不动点迭代我一般会在代码里这样组织// 计算 FIRST 集反复扫描产生式直到集合不再变化 for (int round 0; round MAX_ROUND; round) { int changed 0; for (int i 0; i prodCount; i) { // 对产生式 A - X1 X2 ... Xn // 如果 X 是终结符加入 FIRST(X)结束本轮 // 如果 X 是非终结符加入 FIRST(X) 去掉 ε // 如果 X 能推出 ε就继续看下一个符号 } if (!changed) break; // 集合稳定迭代结束 }注意这里的核心逻辑如果右部的一个符号能推导出空串 ε就必须继续往后看这是新手最容易漏掉的地方。比如 E - T E | ε 这条产生式的 FIRST 集必须先加 然后发现 ε 候选式也要纳入因为 E 本身能推导出空。FOLLOW 集的计算类似只是规则变成了两条A - αBβ 时把 FIRST(β) 去掉 ε 加入 FOLLOW(B)A - αB 或 β 能推出 ε 时把 FOLLOW(A) 加入 FOLLOW(B)。不动点迭代的好处是不用递归不用担心栈溢出代码还好调试。3. 源码拆解预测分析表是怎么从文法算出来的整个程序的骨架其实很传统你把源码打开后前几十行一定是数据结构定义。我见过的大部分课程设计版本都是这个思路你可以照着这个框架去对照阅读。3.1 文法读入与符号分类终结符、非终结符怎么区分大多数实验版本会用字符数组存文法然后用一个函数判断字符是终结符还是非终结符。约定不一常见的有“大写字母是非终结符”“ 包围的是非终结符”。这个包里的实现我推测是后者因为 C 语言课程设计里用尖括号区分符号在字符串处理上最省事。核心数据结构一般长这样typedef struct { char left; // 产生式左部单个非终结符 char right[MAX_RULES][MAX_LEN]; // 右部候选式列表 int ruleCount; // 该非终结符的候选式数量 } Grammar; Grammar gram[MAX_NONTERMINAL]; // 文法产生式数组 int gramCount; // 产生式总数 char terminals[MAX_TERMINAL]; // 终结符表 char nonTerminals[MAX_NONTERMINAL]; // 非终结符表逻辑说明这里用 left 加 right 二维数组存文法好处是查找“某个非终结符的所有候选式”时直接遍历对应下标就行不用每次扫描全部产生式。terminals 和 nonTerminals 两个数组是为了后续判断字符类型——判断时逐个字符串比较命中就返回类型。注意验证文法合法性时最要紧的一条产生式左部必须已经在非终结符表里右部每个符号也必须在终结符或非终结符表里否则后面算 FIRST 集时会越界或者漏算。参数说明MAX_RULES 和 MAX_LEN 是数组维度常见取 10 和 50够课程设计用了。如果文法量特别大比如超过 20 条产生式需要调大这两个值否则写入越界会直接数组溢出表现就是运行到一半乱码或者崩溃。我在帮别人排查时遇到过一次那个版本写死了 [10][50]输入一个 24 条产生式的文法直接翻车。3.2 预测分析表的构造逐格填充与冲突判定有了 FIRST 集和 FOLLOW 集填表就是机械操作。表结构一般用一个二维整数数组int table[MAX_NONTERMINAL][MAX_TERMINAL]; // 存储产生式编号-1 表示出错构造规则按课本定义就两条但代码里要处理一个关键细节如果某条产生式右部能推出 ε第一轮循环并不能给它填表必须等 FOLLOW 集算完才能补上那一批格子。所以代码里会有两个循环第一个循环先处理所有非 ε 候选式第二个循环专门处理 ε 候选式。for (int i 0; i gramCount; i) { // 规则 1对 FIRST(alpha) 中的每个终结符 a填 M[A][a] 此产生式 for (int j 0; j firstSetCount[i]; j) { int t getTerminalIndex(firstSet[i][j]); if (t 0) { if (table[nonTermIndex][t] ! -1) { printf(存在冲突M[%c][%c]\n, nonTerminal, terminals[t]); } table[nonTermIndex][t] i; } } // 规则 2如果 alpha 能推出 ε对 FOLLOW(A) 中每个终结符 b 填表 if (canDeriveEpsilon(gram[i].right)) { for (int j 0; j followSetCount[i]; j) { int t getTerminalIndex(followSet[i][j]); if (t 0) { if (table[nonTermIndex][t] ! -1) { printf(冲突M[%c][%c]\n, nonTerminal, terminals[t]); } table[nonTermIndex][t] i; } } } }逻辑说明填表前把 table 全部初始化为 -1。每填一个格子前先检查是否已有产生式如果有说明文法不是 LL(1) 文法——两个产生式都能处理同一个栈顶符号和输入符号的组合。冲突判定是实验验收时的高频提问点很多同学的程序没输出冲突提示不是因为文法没问题而是漏写了这个检查分支。加上它就能在输入文法后立刻发现文法是否合格。参数说明canDeriveEpsilon 的判断要小心它检查的是“整个右部能否推出 ε”不是某个符号能不能推出 ε。实现方式通常是递归判断右部每个符号都含 ε。这里的递归深度受文法长度限制一般不会超过 10 层不用额外担心栈溢出。3.3 分析驱动栈操作与出错处理预测分析表建好之后分析输入串的代码要简单得多。运行时维护一个字符栈栈底放 #初始把开始符号压入。然后循环void analyze(char *input) { char stack[MAX_STACK]; int top 0; stack[top] #; stack[top] startSymbol; // 开始符号入栈 int pos 0; // 输入串指针 while (top 0) { char X stack[top]; // 栈顶符号 char a input[pos]; // 当前输入符号 if (X a) { // 匹配弹出栈顶 top--; pos; } else if (isTerminal(X)) { printf(错误栈顶终结符 %c 与输入 %c 不匹配\n, X, a); return; } else { int prod table[getNonTermIndex(X)][getTerminalIndex(a)]; if (prod -1) { printf(错误预测分析表 M[%c][%c] 无产生式\n, X, a); return; } // 弹出栈顶把产生式右部逆序入栈 top--; int len strlen(gram[prod].right); for (int i len - 1; i 0; i--) { stack[top] gram[prod].right[i]; } } } if (input[pos] # top 0) { printf(输入串是该文法的句子\n); } }逻辑说明这里有个容易写反的点——产生式右部入栈时必须逆序因为栈是后进先出。比如 E - T E展开后栈顶应该是 所以要把右部从后往前压。我见过好几个版本把顺序写反结果分析永远失败。另外注意文法里包含 ε 产生式时的处理M[E][#] 如果指向 ε 产生式入栈时右部是空串代码会直接跳过入栈效果就是栈顶被弹出而不压入任何符号相当于把 E 消掉。参数说明pos 是输入串指针每次匹配成功才前移和栈顶匹配是同一个节奏。# 是输入串的结束标记判断句子是否分析完毕就看 pos 是否指向末尾的 # 且栈内只剩 #。出错时直接返回不继续做无意义的匹配这是教科书推荐的做法。4. 运行验证输入串的判定流程与测试用例设计代码看明白之后就该跑起来了。这一章讲操作流程照着做就能完成实验验收的整个环节。4.1 用 Dev-C 打开工程.dev 文件与 Makefile.win 的关系资源包里带的是 Dev-C 工程打开方式很简单启动 Dev-C菜单里选“文件” → “打开工程或项目”定位到解压目录选择扩展名为 .dev 的文件。打开后左侧的工程管理面板里能看到源文件列表点编译运行按钮或按 F11就会重新编译。如果编译通过Dev-C 会直接启动生成的 exe。这里有个常见的实际操作问题.layout 文件是窗口布局记录删掉不影响编译.o 是旧编译产物重新编译时会被覆盖Makefile.win 是 Dev-C 自动维护的构建脚本不建议手工修改。如果你的环境里没有 Dev-C装了 Code::Blocks 或者 Visual Studio可以直接把 .cpp 拖进去新建空项目编译因为代码本身没有依赖 Dev-C 的私有库。注意别双击旧 exe 当成品用——不同电脑上的运行环境不一致旧 exe 可能缺运行库。我的习惯是打开 .dev 重新编译一次确保程序由你本机的编译器生成这样排查问题时每一步都是可控的。4.2 输入文法与输入串程序交互顺序程序是控制台交互式的运行后会依次提示输入文法信息。可预期的交互顺序是先输入终结符集合再输入非终结符集合然后输入产生式数量和各产生式指定开始符号程序计算并展示 FIRST/FOLLOW 集和预测分析表最后提示输入待分析的句子。你可以准备一组标准 LL(1) 文法做测试终结符i * ( ) # 非终结符E T E T F 开始符号E 产生式 E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | i操作时注意两点一是输入产生式时 ε 用什么符号表示程序提示里通常会写明二是输入句子末尾需要手动加 #。这个文法对应常规四则运算表达式足够验证绝大多数功能点。4.3 测试用例设计合法串、非法串与边界写完一段测试用例既是为了验收入场合规也是排查程序逻辑的手段。按我的习惯至少准备三类输入测试串预期结果覆盖点ii*i#通过最基本的含乘法表达式(ii)*i#通过括号嵌套与优先级ii#通过同优先级连续运算i*i#报错运算符相邻中间缺少操作数i(ii)#报错缺运算符ε / 空串#报错或提示语法错误边界场景第一组用例全部通过只说明基本功能正常真正检验程序健壮性的是后几组。如果 ii# 被判定通过基本可以断定预测分析表里 和 对应的格子有冲突或者输入串读取时把某个字符漏掉了。建议每改动一次代码就把这六组用例从头跑一遍确认没引入新问题。5. 避坑与常见问题LL(1) 实验最容易翻车的五个细节这个实验我前前后后帮人排查过不下十次绝大多数问题集中在五个固定位置。下面按“现象 → 原因 → 解决”记录你可以直接对照排除。1. 现象程序运行后卡住不动CPU 占用很高或者直接无响应。原因最常见的两种一是文法带左递归导致分析栈永远消不干净二是 FIRST/FOLLOW 集计算时没有做不动点终止判定集合无限增长。这两种都属于程序死循环问题。解决先输一个极短的测试串如 i# 试运行如果还是卡死断点或者加打印看是卡在建表还是分析阶段。卡在建表就是集合计算没收敛检查迭代循环里 changed 标记是否每次循环都重置卡在分析就是文法的锅把 E - E T 这类左递归改写成右递归形式再试。2. 现象输入文法后程序提示“存在冲突”但仍然继续运行。原因文法本身不是 LL(1) 文法。冲突分两类——FIRST 集冲突同一非终结符的多个候选式有共同首符号和 FIRST/FOLLOW 冲突某候选式能推出 ε 时有终结符同时出现在 FIRST 和 FOLLOW 里。解决不要试图在当前文法上修补先做文法改写。提取左因子解决 FIRST 冲突对能推出 ε 的非终结符检查它推导链上参与该 ε 的所有符号必要时重新设计文法层次。3. 现象合法句子被报错而且报错位置总是偏早或偏晚一个字符。原因输入串读取时把换行符 \n 也读进去了。控制台输入时用户敲回车这个换行符会残留在缓冲区如果程序用 getchar 会把它当成第一个输入符号。解决在 main 函数里读完整行后检测末尾 \n 并替换为 \0或者在控制台输入句子后手动加 # 并把 \n 前的字符全部忽略。4. 现象在本机编译运行都正常换了台电脑双击 exe 闪退。原因Dev-C 默认动态链接 MinGW 的运行库 DLL目标机器上没有就会闪退且没有任何错误提示。解决在 Dev-C 里重新编译并运行这就是为什么我一再强调打开 .dev 而不是直接用旧 exe。如果你的实验验收是在实验室电脑上做提前把源码和 Dev-C 便携版都带上或者发布时改成静态编译。5. 现象预测分析表里 ε 对应的格子为空导致某些合法句子报错。原因实现时把 ε 当成普通终结符处理算 FIRST 和 FOLLOW 时没有把“能推出空”的语义单独处理。ε 不是一个实际字符它表示右部可以为空填表时要用 FOLLOW 集去补格子。解决检查 canDeriveEpsilon 函数确认它返回的是一个布尔值而不是把 ε 字符存入 FIRST 集。代码里处理 ε 产生式的分支一定要放在所有普通候选式之后。6. 加一个栈过程追踪30 行代码看清分析器每一步如果你想让这次实验不流于“能跑就行”我强烈建议给分析驱动函数加一个状态打印把每一步的栈内容和剩余输入串打出来。这既是排查问题的武器也是实验报告里的亮点指导老师问起来你能当场把流程讲清楚。void printStatus(char *stack, int top, char *input, int pos, char *prodName) { printf(栈); for (int i 0; i top; i) { printf(%c , stack[i]); } printf(\t输入%s\t\t动作%s\n, input[pos], prodName); }在 analyze 函数的循环体内每个分支处理完之后调用一次// 栈顶是终结符且匹配成功 top--; pos; printStatus(stack, top, input, pos, 匹配终结符); // 栈顶是非终结符查表换产生式 top--; for (int i len - 1; i 0; i--) { stack[top] gram[prod].right[i]; } printStatus(stack, top, input, pos, gram[prod].right);逻辑说明printStatus 接收当前栈和输入指针位置打印出剩余输入串——注意传的是 input[pos]C 语言里这样写就直接输出从当前位置到字符串结尾的内容比循环逐字符打印简洁得多。动作列写了当前这一步做了什么要么是“匹配终结符”要么是具体产生式串。参数说明栈顶 top 是指向栈顶元素下标的变量。调用时机很关键必须先修改栈再打印这样才能看到这一步动作的完整结果。比如 E - T E 展开后打印的栈应该是 T E #栈底到栈顶输入串指针停在刚读过的 之后的位置。然后你运行测试串 ii*i#会看到类似下面的输出栈# E 输入ii*i# 动作E - T E 栈# E T 输入ii*i# 动作T - F T 栈# E T F 输入ii*i# 动作F - i 栈# E T 输入i*i# 动作匹配终结符 i每一行都能直接对应到教材上的最左推导过程。你会在十步之内直观地理解预测分析表就是用来消除“该选哪条产生式”的不确定性而栈里保留的就是当前推导的待处理部分。从那以后我每次拿到语法分析相关代码第一件事就是先加上这种追踪输出再小的程序也值得看过程不然查错全靠猜。希望这份资源也能帮你把 LL(1) 分析器一次跑通。本文还有配套的精品资源点击获取