企业官网建设流程全解析

简介：面向编译原理课程的LL(1)语法分析实验资源，源自山东科技大学2022年编译原理实验，内容包含完整的CodeBlocks工程代码和实验报告，适合正在学习编译原理、需要完成类似实验或想深入理解LL(1)分析方法的学生与自学者。压缩包大小约1.08MB，主要文件类型为可直接编译运行的源码文件和文字版实验报告，报告对LL(1)分析中的关键步骤有详细推导；目前已有913人学习或下载，可用于课程实验、期末复习或毕业设计参考。通过资源中的代码，读者可以快速验证对给定文法的分析过程，该文法覆盖加减乘除及括号表达式，涉及E→TG、G→+TG|-TG、T→FM、M→*FM|/FM、F→(E)等产生式，借助完整的预测分析表驱动，能够判断任意输入符号串是否符合文法。报告还详细说明了FIRST集合、FOLLOW集合的求解方法以及预测分析表的构建步骤，便于对照代码加深理解。

1. LL1分析法在编译原理实验里的位置：它到底解决了什么

LL1分析法是编译原理实验里最典型的自顶向下语法分析实现，22年山科大编译原理实验把语法分析单独拎出来要求实现LL1，背后其实是在考察两件事：First集与Follow集算得对不对，以及驱动程序能不能按预测分析表机械地完成匹配。LL1这三个字母分别代表从左到右扫描输入、最左推导、向前看1个token，它把文法规则全部映射成一张二维预测分析表，分析器本身就是一个查表加进出栈的循环。

这个实验适合两类人：一类是被递归下降分析法里各种手写分支绕晕的学生，另一类是已经跑过词法分析、想用Java快速体验一遍完整语法分析流程的开发者。把LL1实现一遍，你就会明白为什么教材要花一整章讲First集和Follow集——表面是集合运算，实际是文法可预测性的判断依据。下面从集合计算开始，一步步把整个分析器搭起来。

2. 从文法到预测分析表：First集与Follow集的计算实现

很多同学写LL1直接跳去写驱动循环，结果预测分析表构造不对，一跑就崩。First集和Follow集是整个实验的地基，这两套集合算错一个符号，后面驱动循环里查表就会得到错误产生式或者查不到表项。这一章先解决集合计算，并且用不动点迭代实现，避免文法里出现互相引用时递归调用栈溢出。

2.1 First集计算：为什么要用不动点迭代

First集的定义是一个文法符号能推导出的所有终结符首符的集合。对于产生式A -> X1 X2 ... Xn，求First(A)时要依次看右部每个符号：如果X1是终结符，直接把它加入First(A)并结束；如果X1是非终结符，把First(X1)里除ε以外的符号全部并入First(A)，只有当X1能推导出ε时才继续看X2。右部所有符号都能推导出ε时，ε才加入First(A)。

由于文法里可能存在A -> B、B -> A这种互引用，按教材上那种“逐个产生式推导”的方式手算容易漏项。更稳的做法是循环扫描所有产生式，直到所有集合都不再变化，也就是不动点迭代。下面是Java实现：

/** * 迭代计算所有非终结符的FIRST集 * productions: List<Production>，Production包含left(String)和right(List<String>) * nonTerminals / terminals: 预先收集好的符号集合 */ public Map<String, Set<String>> buildFirstSet() { Map<String, Set<String>> first = new HashMap<>(); for (String nt : nonTerminals) { first.put(nt, new HashSet<>()); } boolean changed = true; while (changed) { changed = false; for (Production p : productions) { Set<String> firstOfLeft = first.get(p.left); // 右部是否所有符号都可空（能推导出ε） boolean allNullable = true; for (String symbol : p.right) { if (terminals.contains(symbol)) { // 终结符直接加入，ε不在这里处理 if (!symbol.equals("ε") && firstOfLeft.add(symbol)) { changed = true; } allNullable = false; break; } // 非终结符：把它的FIRST去掉ε后并入左部 for (String s : first.get(symbol)) { if (!s.equals("ε") && firstOfLeft.add(s)) { changed = true; } } // 该符号不能推导出ε，停止继续向后扫描 if (!first.get(symbol).contains("ε")) { allNullable = false; break; } } // 右部全部可空，说明左部能推导出ε if (allNullable && firstOfLeft.add("ε")) { changed = true; } } } return first; }

这段代码里最值得注意的就是allNullable标志。例如产生式E' -> + T E' | ε，第二条产生式右部为空列表，循环体不执行，allNullable保持true，于是ε被加入First(E')。如果右部是T E'，先处理T，T的First不含ε，于是allNullable置为false并break，不会继续看E'。

外层while (changed)循环是这套实现的精髓。手写递归求First时，遇到A -> B且B -> A这种文法直接栈溢出；不动点迭代不会，因为每个集合只增不减，终结符数量有限，迭代必然收敛。我一般会把最大迭代次数设为非终结符数量的两倍加一，防止程序死循环，实验里不必写这么严，但心里要有这个数。

2.2 Follow集计算：看右侧和后继，而不是看左侧

Follow集的定义比First集绕一层：对非终结符A，Follow(A)是在所有句型中紧跟在A之后可能出现的终结符集合。它不是看A产生什么，而是看A出现在哪些产生式的右部、A后面跟了什么。

教材给的两条规则要记牢。规则一：对产生式A -> α B β，把First(β)中除ε以外的符号并入Follow(B)。规则二：如果A -> α B，或者A -> α B β且β能推导出ε，那么把Follow(A)并入Follow(B)。另外，开始符号的Follow集里要放上输入结束符#。

规则二很容易被忽略，尤其是“β能推导出ε”这条。因为Follow集也存在传播关系，同样用不动点迭代实现：

/** * 计算FOLLOW集，依赖buildFirstSet的结果 * startSymbol: 文法开始符号，输入串结尾符记为# */ public Map<String, Set<String>> buildFollowSet( Map<String, Set<String>> first) { Map<String, Set<String>> follow = new HashMap<>(); for (String nt : nonTerminals) { follow.put(nt, new HashSet<>()); } follow.get(startSymbol).add("#"); boolean changed = true; while (changed) { changed = false; for (Production p : productions) { List<String> right = p.right; for (int i = 0; i < right.size(); i++) { String B = right.get(i); if (!nonTerminals.contains(B)) continue; Set<String> followB = follow.get(B); if (i == right.size() - 1) { // 规则二的第一种情况：A -> α B，B在末尾 for (String s : follow.get(p.left)) { if (followB.add(s)) changed = true; } } else { // 规则一：A -> α B β，取FIRST(β)去掉ε List<String> beta = right.subList(i + 1, right.size()); Set<String> firstBeta = computeFirstOfSequence(beta, first); for (String s : firstBeta) { if (!s.equals("ε") && followB.add(s)) { changed = true; } } // 规则二的第二种情况：β可推导出ε if (firstBeta.contains("ε")) { for (String s : follow.get(p.left)) { if (followB.add(s)) changed = true; } } } } } } return follow; }

这里新增了一个辅助函数computeFirstOfSequence(beta, first)，它计算一个符号序列的First集：从beta第一个符号开始，并入其First，如果可空则继续处理下一个，直到遇到不可空符号或序列结束，若整个序列可空则返回结果里包含ε。这个函数是对2.1节右部处理逻辑的复用，写成一个独立方法能让Follow计算代码清晰很多。

我见过有人把Follow计算写成只遍历一遍产生式，结果E -> T E'这种产生式里E'的Follow迟迟算不出完整的#和)。原因就是Follow信息跨多个产生式传播，一轮扫描不够。所以这里必须也用while (changed)包起来。

2.3 验证计算结果：拿经典算术文法对答案

实现完两套集合后，先别急着写驱动，用一个标准文法做自检。下面这套消除左递归后的算术表达式文法，是编译原理教材第三版的常见例题，也适合用来验证代码：

E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id

用上面的代码跑完后，关键集合应该得到这些值：

注意F的Follow里有*，因为来自T' -> * F T'中F后面直接跟了T'，而T'可空，所以Follow(T')的+、#、)也传播给了F。如果你的输出里F的Follow缺了#或)，基本可以断定规则二没实现完整，回头检查计算顺序。

3. 用 Java 跑通 LL1 驱动：预测分析表与查表循环怎么落地

集合算对了，预测分析表就只是个“填格子”的过程。LL1分析器核心就三步：查表、压栈、匹配。但细节坑很多，比如产生式右部压栈为什么要逆序、ε产生式怎么处理、表项冲突怎么发现。这一章直接给出可运行的Java代码。

3.1 构造预测分析表：填表规则与冲突检测

预测分析表是一个二维矩阵，行是非终结符，列是终结符加#。对每个产生式A -> α，按两条规则填：

• 对First(α)中每个终结符a，把该产生式填入M[A, a]。
• 如果ε在First(α)中，则对Follow(A)中每个符号b，把该产生式填入M[A, b]。

第二条规则是LL1分析的特殊之处。E' -> ε这个产生式不匹配任何终结符，它只在遇到Follow(E')里的符号时才“空降”弹栈，让E'从栈中消失，继续处理后续输入。代码实现：

/** * 构造预测分析表 * 返回类型: Map<非终结符, Map<终结符, 产生式>> * 如果同一个格子被两个不同产生式占用，说明文法不是LL(1) */ public Map<String, Map<String, Production>> buildTable( Map<String, Set<String>> first, Map<String, Set<String>> follow) { Map<String, Map<String, Production>> table = new HashMap<>(); for (Production p : productions) { Set<String> firstOfRight = computeFirstOfSequence(p.right, first); // 规则一：FIRST(α)中每个终结符都填该产生式 for (String a : firstOfRight) { if (a.equals("ε")) continue; Production old = putIntoTable(table, p, p.left, a); if (old != null && !old.equals(p)) { throw new IllegalStateException( "文法不是LL(1)：M[" + p.left + ", " + a + "] 冲突"); } } // 规则二：ε在FIRST(α)中时，FOLLOW(A)的每个符号都填该产生式 if (firstOfRight.contains("ε")) { for (String b : follow.get(p.left)) { Production old = putIntoTable(table, p, p.left, b); if (old != null && !old.equals(p)) { throw new IllegalStateException( "文法不是LL(1)：M[" + p.left + ", " + b + "] 冲突"); } } } } return table; } private Production putIntoTable( Map<String, Map<String, Production>> table, Production p, String nonTerminal, String terminal) { Map<String, Production> row = table.computeIfAbsent(nonTerminal, k -> new HashMap<>()); return row.put(terminal, p); }

这里的冲突检测是血泪经验。很多同学遇到文法含左递归或公共前缀时，驱动跑出来行为诡异，就是因为表里同一个格子被后一个产生式覆盖了，前一个静默丢失。用put返回旧值来判断冲突，能让你在构造表时立刻知道文法不是LL1，而不是在分析阶段排查半天。

3.2 LL1驱动循环：栈、输入缓冲区、查表的机械步骤

预测分析表建好后，驱动算法可以描述成一个循环：

1. 初始化：栈压入#，再压入开始符号；输入串末尾加#。
2. 取栈顶符号X和当前输入符号a。
3. 若X是终结符且等于a，弹栈，读下一个输入符号。
4. 若X是非终结符，查M[X, a]，找到产生式则弹栈，把右部逆序压栈（ε不压）；查不到则报错。
5. 反复执行直到栈空，栈空且输入读完则接受。

逆序压栈是新手最容易想不通的地方。因为栈是后进先出，产生式右部第一个符号应最早被展开处理，所以它必须最后入栈。比如面对E' -> + T E'，压栈顺序是E'、T、+，这样+在栈顶，下一步就能和输入匹配。核心代码：

public boolean parse(String inputWithSpaces, Map<String, Map<String, Production>> table) { Deque<String> stack = new ArrayDeque<>(); stack.push("#"); stack.push(startSymbol); // 输入串建议用空格分词，如 "id + id * id" String[] tokens = inputWithSpaces.split(" "); List<String> inputList = new ArrayList<>(Arrays.asList(tokens)); inputList.add("#"); int pos = 0; System.out.println("====== 分析步骤 ======"); while (!stack.isEmpty()) { String top = stack.pop(); String lookahead = inputList.get(pos); if (terminals.contains(top) || top.equals("#")) { // 栈顶是终结符，必须和当前输入匹配 if (top.equals(lookahead)) { pos++; System.out.println(top + " 匹配成功"); } else { System.err.println("语法错误：期望 " + top + "，但读到 " + lookahead + "，位置 " + pos); return false; } } else { // 栈顶是非终结符，查表 Production p = table.get(top).get(lookahead); if (p == null) { System.err.println("语法错误：非终结符 " + top + " 无法接受 " + lookahead + "，位置 " + pos); return false; } // 右部逆序压栈，ε不压入 List<String> right = new ArrayList<>(p.right); Collections.reverse(right); for (String symbol : right) { if (!symbol.equals("ε")) stack.push(symbol); } System.out.println(top + " -> " + p.right + " 应用"); } } // 正常情况下循环结束时 pos 指向 "#'，输入也被消费完 return pos == inputList.size() - 1; }

这个驱动函数有几个地方要注意。第一，tokens按空格切分，实验里最好在测试代码里把输入写成"id + id * id"这种空格分隔形式，避免自己写词法切分引入额外bug。第二，出错信息里带上当前token和第几个位置，排错时一眼看出问题出现在哪个输入符号附近。第三，while循环退出条件只有stack.isEmpty()，如果输入串提前消费完而栈里还有非终结符，查表会因lookahead越界报错，所以输入末尾加#是必须的。

3.3 手动走一遍id + id * id，验证驱动逻辑

用3.1节的算术表达式文法跑id + id * id，前几步应该是这样：

第五步是关键：栈顶T'面对输入+，M[T', +]里存的产生式是T' -> ε，所以右部为空，什么都不压栈，T'直接消失，成功把处理权交还给E'。这就是LL1处理空产生式的典型过程。如果你在驱动里把ε当作普通符号压栈，这一步就会永远匹配不上，程序直接报错。

4. LL1 实验最容易翻车的四个坑：从死循环到文件编码

LL1实现本身不算复杂，但翻车点都很隐蔽，往往不是算法大错，而是某些边界条件没处理。这一章写我在这个实验里最常见的四个坑，每条按现象、原因、解决来写，可以直接对照排查。

4.1 左递归文法让驱动进程永远停不下来

现象：程序跑某个文法或某条输入时卡住，栈无限增长，内存耗尽或CPU占满。比如直接用E -> E + T | T这个产生式构造文法。

原因：左递归产生式E -> E + T的First(E)里包含E自身能推导出的终结符，填表时 M[E, +] 会指向E -> E + T。驱动循环每次遇到E都把它展开成E + T，E重新进栈，加上原有的E，栈里E越堆越多，永远消不下去。

解决：先把文法改写成等价的无左递归形式。标准做法是把左递归转成右递归：E -> E α | β改写成E -> β E'和E' -> α E' | ε。改写后重新计算First和Follow再建表，问题随即消失。注意不只是直接左递归，E -> A T且A -> E这种间接左递归也要处理，实验一般不要求，但要心里有数。

4.2 公共前缀导致表项冲突

现象：构造预测分析表时，明明没报错，驱动跑一些输入时采用了错误的产生式，导致中间某一步栈顶和输入无法匹配。

原因：文法存在公共前缀，比如S -> if E then S else S | if E then S，两个产生式右部的First集都包含if，表项M[S, if]被后一个产生式覆盖，前一个分支永远走不到，或者做了冲突检测直接抛异常。

解决：提取左因子，将公共部分提出来：S -> if E then S S'，S' -> else S | ε。提取后要重新算集合和表。这里有一个排查技巧：冲突检测抛出的异常消息里会打印非终结符和终结符，比如M[S, if] 冲突，看到这个组合直接去文法里找以if开头的多个产生式即可。

4.3 ε的空串传播顺序导致Follow集算错

现象：某个非终结符的Follow集里多了或者少了终结符，表现是输入串该接受时被拒绝，或者反过来接受了非法串。例如3.3节的文法，F的Follow少了#。

原因：Follow计算依赖First的可空性判断，而可空性本身需要多次迭代才能传播到位。如果只遍历一遍产生式，T' -> * F T' | ε这种规则中，F的Follow要等T'的Follow先算好才能完整传播，顺序稍有不符就漏项。

解决：全部改用不动点迭代，这一点在2.2节已经强调。复查方式很简单：把每个非终结符的Follow集打印出来，对照教材给的答案核对。不要试图通过调整产生式遍历顺序来“碰巧”算对，因为文法一换就坏。

4.4 从文件读文法时被BOM和编码坑

现象：在main方法里硬编码文法字符串时一切正常，改成从文件读文法后，第一条产生式的左部怎么都匹配不上，报“未知非终结符”。用文本编辑器看文件内容完全正常。

原因：Windows记事本保存UTF-8文件时会在文件头写入三个字节的BOM（EF BB BF），Java读取后第一个字符变成不可见的\uFEFF。如果你用这个字符去查非终结符集合，自然查不到。同理，文件里如果有中文注释，用FileReader按GBK读取时也可能读到乱码交换进去。

解决：读取文法文件时跳过BOM头，或者统一用UTF-8无BOM编码保存。代码里可以这样处理：

BufferedReader reader = new BufferedReader( new InputStreamReader( new FileInputStream(file), StandardCharsets.UTF_8)); // 处理BOM：读第一行前检查首字符 String line = reader.readLine(); if (line != null && line.startsWith("\uFEFF")) { line = line.substring(1); }

这一条属于玄学翻车，但每年都有人耗一下午在这里。多花30秒规范化输入编码，能省掉大量无意义的排查时间。

5. 把 LL1 从跑通做到能排错：跟踪打印与错误定位技巧

实验做到能跑通几条合法输入只是及格，真正拉开差距的是非法输入出现时你能不能快速定位问题。这一章讲两个我常用的排错技巧，都改动量极小，但对调试效率提升明显。

第一个技巧是在驱动循环里加一个计数器，每步打印当前序号、栈内容、剩余输入和被选用的产生式。前面3.3节的跟踪表就是手工模拟的，实际程序里把栈打印成字符串即可。调试时盯着栈的变化，能立刻看出某一步是不是错误地压入了不该出现的符号，或者该弹栈时没弹。

第二个技巧是让错误信息携带“期望-实际”对。当查表失败时，报错信息写成：第 pos 个token附近，非终结符 E' 期望接受 +、#、)，但读到 id。这里的期望集合就是Follow(E')，实际读到的是当前输入token。这样做的好处是定位不靠肉眼扫整个分析栈，而是直接告诉你文法在哪个非终结符上、什么上下文环境下出的错。我在实验里把这条信息输出到控制台后，非法输入的排错时间缩短了至少一半。

再进一步，可以把预测分析表导出成文本文件检查。对每个非终结符，打印一行“在哪些终结符下选择哪条产生式”，人工扫一遍就能发现漏填的表项。这套方法不仅适用于课程实验，后面你接触递归下降分析器或者手写JSON解析器时，同样能用——把“当前状态”和“期望输入”打印出来永远是排查解析问题最快的方式。

我自己的习惯是：写完LL1后先用合法输入跑通，再用三条非法输入故意触发报错，确认错误信息里能看到期望集合和实际token，才算这个实验真正结束。这个习惯后来帮我解决了不少实际项目里的配置解析问题——解析器好不好用，不只看它能接受什么，更看它拒绝时能不能告诉你为什么。希望帮到你。

本文还有配套的精品资源，点击获取