企业官网建设流程全解析

简介：本资源是南京邮电大学《编译原理》课程配套的实验二完整材料，面向计算机类专业本科生及编译技术初学者，聚焦LL(1)语法分析器的设计与实现这一核心难点。内容涵盖左递归检测与消除、FIRST/FOLLOW集的手动推导过程、LL(1)分析表构建方法，以及基于C++实现的可交互分析程序（含完整源码与详细注释），帮助学习者从理论推导到代码落地系统掌握语法分析全流程。压缩包为单个937KB的DOC文档，内含规范实验报告、文法变换步骤、集合求解演算、分析表构造结果及关键算法源码片段，结构清晰、推导严谨、注释充分，便于对照学习与课堂复现。已有296人下载学习，是理解LL(1)分析原理、完成课程实验与夯实编译器前端基础的实用参考资料。

1. 南京邮电大学编译原理实验二（语法分析）：不是写个递归下降就交差，而是用可验证的语法树把文法、词法、语义三关串起来

南京邮电大学《编译原理》课程的实验二“语法分析”，常被学生误读为“在词法分析器输出上套一层递归下降函数”——结果交上去发现：输入a + b * c能解析，但if (x > 0) y = 1; else y = 0;直接崩栈；或者能生成节点，却无法回答“+运算符的左操作数是哪个 AST 子树？”这类问题。这暴露了本质误区：语法分析不是语法检查，而是构建结构化中间表示的强制环节。本实验真正要你落地的，是让一个确定性上下文无关文法（如实验指定的 PL/0 子集或自定义算术表达式文法）在 Java 环境下完成三件事：（1）基于 FIRST/FOLLOW 集构造预测分析表；（2）用 LL(1) 分析器驱动栈并同步构建抽象语法树（AST）；（3）将 AST 序列化为可人工校验的缩进文本或 DOT 图。它面向的是已跑通实验一（词法分析）的同学，要求你不再依赖正则黑盒，而要亲手推导文法冲突、手算预测表、调试栈状态跳转——这些能力，正是后续语义分析和中间代码生成的硬底子。如果你正卡在“分析表填不满”“匹配失败不报具体位置”“AST 节点父子关系错乱”，这篇笔记就是为你写的血泪复现记录。

2. 从文法定义到预测分析表：手算 FIRST/FOLLOW 是绕不开的硬功夫

2.1 实验二典型文法选型与合法性验证

南京邮电大学实验二常用文法并非教科书简化版，而是带实际编程语言特征的 PL/0 子集（参考《编译原理》龙书附录 A），例如：

Program → Block . Block → [ Declarations ] [ CompoundStatement ] Declarations → ε | var IdentList ; IdentList → ident | ident , IdentList CompoundStatement → begin StatementList end StatementList → ε | Statement { ; Statement } Statement → ident := Expression | if Condition then Statement [ else Statement ] | while Condition do Statement Condition → Expression RelOp Expression Expression → Term { AddOp Term } Term → Factor { MulOp Factor } Factor → ident | number | ( Expression ) RelOp → = | <> | < | <= | > | >= AddOp → + | - MulOp → * | /

提示：该文法含左递归（Expression → Term { AddOp Term }是右递归改写）、ε 产生式、公共前缀（Statement的三个分支均以ident或if/while开头）。直接套用递归下降会因回溯失效，必须走 LL(1) 路线——这也是南邮实验明确要求“构造预测分析表”的原因。

2.2 手算 FIRST 集：逐符号穿透，拒绝模糊记忆

FIRST(X) 是所有以 X 推导出的终结符开头的集合。计算时必须严格按规则穿透：

• 若 X 是终结符，FIRST(X) = {X}；
• 若 X → ε，则 ε ∈ FIRST(X)；
• 若 X → Y₁Y₂…Yₖ，先算 FIRST(Y₁)，若 ε ∉ FIRST(Y₁)，则 FIRST(X) = FIRST(Y₁)；否则继续加入 FIRST(Y₂){ε}，依此类推，直到某 Yᵢ 的 FIRST 不含 ε，或全部 Yⱼ 都含 ε 则加入 ε。

以Expression → Term { AddOp Term }为例（记{ AddOp Term }为重复结构，等价于Expression → Term Expression'，Expression' → AddOp Term Expression' | ε）：

• FIRST(Term) = { ident, number, ( }（因Factor → ident | number | ( Expression )）
• FIRST(AddOp) = { +, - }
  → 所以 FIRST(Expression) = { ident, number, ( }
  → FIRST(Expression') = { +, -, ε }（因AddOp Term Expression'的 FIRST 是 {+, -}，且有 ε 产生式）

关键参数说明：南邮实验报告要求手写 FIRST/FOLLOW 表。你必须对每个非终结符（如Expression,Statement,Condition）单独列出其 FIRST 集合，不能合并写成“所有终结符开头的符号”这种笼统描述。我当年漏写了CompoundStatement的 FIRST({begin})，导致预测表第 3 行全空，调试两小时才发现。

2.3 手算 FOLLOW 集：定位句柄边界，决定何时归约

FOLLOW(A) 是所有可能紧跟在 A 后面的终结符集合（含 $，即输入结束符）。核心规则：

• $ ∈ FOLLOW(StartSymbol)；
• 若 A → αBβ，则 FIRST(β){ε} ⊆ FOLLOW(B)；
• 若 A → αB 或 A → αBβ 且 ε ∈ FIRST(β)，则 FOLLOW(A) ⊆ FOLLOW(B)。

仍以Expression → Term Expression'为例：

• Expression'出现在Expression右部末尾 → FOLLOW(Expression') ⊇ FOLLOW(Expression)
• Expression是开始符号 → $ ∈ FOLLOW(Expression) → $ ∈ FOLLOW(Expression')
• Expression'也出现在Statement → ident := Expression中，Expression后是;→;∈ FOLLOW(Expression) →;∈ FOLLOW(Expression')
• 同理，在Condition → Expression RelOp Expression中，第一个Expression后是RelOp→RelOp∈ FOLLOW(Expression) →=, <>, <, <=, >, >=∈ FOLLOW(Expression)

血泪经验：南邮实验中FOLLOW(Statement)容易漏掉;和end。因为StatementList → Statement { ; Statement }，所以;是Statement的后继；又因CompoundStatement → begin StatementList end，end也是StatementList的后继，进而传递给Statement。少写一个end，预测表里Statement → if...行对应end列就是空白，运行时遇到end就报“unexpected token”。

2.4 构造 LL(1) 预测分析表：填表不是填空，是逻辑映射

预测分析表 M[A, a] 表示：当栈顶是非终结符 A，当前输入符号是 a 时，应选用哪个产生式。填表规则：

• 对每个产生式 A → α：
  • 对每个 a ∈ FIRST(α)，置 M[A, a] = “A → α”；
  • 若 ε ∈ FIRST(α)，则对每个 b ∈ FOLLOW(A)，置 M[A, b] = “A → α”。

以Statement → ident := Expression为例：

• FIRST(ident := Expression) = { ident } → M[Statement, ident] = 此产生式
• Statement的 FOLLOW 集含;,end,$（由StatementList和Block传递）→ 但此产生式 FIRST 不含 ε，故不填 FOLLOW 列

再看Statement → ε（实际不存在，但StatementList → ε存在）：

• 若StatementList → ε，且 ε ∈ FIRST(ε)，则对每个 b ∈ FOLLOW(StatementList)，M[StatementList, b] = 此产生式
• FOLLOW(StatementList) = { ;, end }（因CompoundStatement → begin StatementList end，StatementList后是end；又因StatementList → Statement { ; Statement }，Statement后是;）→ 所以 M[StatementList, ;] 和 M[StatementList, end] 均填→ ε

避坑：预测分析表常见错误与排查
现象 1：表中某行（如Expression'行）多个列填了同一产生式，或某列为空
原因：Expression' → AddOp Term Expression' | ε的 FIRST(AddOp Term Expression') = {+, -}，FOLLOW(Expression') = {;, ), end, $}，二者无交集 → 正常应分两列填。若填重，说明 FIRST 计算错误（如误将AddOp的 FIRST 算成 {+, -, ε}）；若某列空（如)列为空），说明 FOLLOW(Expression') 漏了)—— 因Factor → ( Expression )，Expression后是)，故)∈ FOLLOW(Expression) → 传递至Expression'

现象 2：表中出现冲突（同一格填两个不同产生式）
原因：文法非 LL(1)。南邮实验给的 PL/0 子集经改造后应无冲突，若出现，检查Condition → Expression RelOp Expression是否被误拆为Condition → Expression RelOp（漏了第二个Expression），导致 FIRST 冗余

现象 3：填表完成后，M[Statement, if]为空
原因：Statement的 FIRST 集未包含if。回溯Statement → if Condition then Statement [ else Statement ]，其 FIRST 是 {if}，但若你把该产生式写成Statement → if ...却未在 FIRST(Statement) 中显式加入if，表就漏了。FIRST 必须覆盖所有产生式首符号

3. Java 实现 LL(1) 分析器：栈驱动 + AST 构建双线并行

3.1 核心数据结构设计：Token 流、分析栈、预测表、AST 节点

南邮实验要求用 Java 实现，拒绝 Python 快速原型。关键类必须解耦：

• Token：含type（枚举：IDENT, NUMBER, PLUS, SEMI, IF, THEN…）、value（字符串值）、line（行号，用于报错）
• Parser：主类，持LinkedList<Token> inputTokens（输入队列）、Stack<String> parseStack（分析栈，存非终结符和终结符）、Map<String, Map<String, String>> predictTable（预测表，key1=非终结符，key2=当前输入符号，value=产生式右部字符串，如"if Condition then Statement else Statement"）
• ASTNode：抽象基类，子类如BinaryOpNode（存 op、left、right）、AssignNode（存 ident、expr）、IfNode（存 cond、thenBranch、elseBranch）

注意：南邮实验报告强调“预测表用二维数组或哈希表实现”。我推荐HashMap<String, HashMap<String, String>>，因非终结符和终结符都是字符串，动态扩展方便；若用二维数组，需预定义所有符号索引，易出界。

3.2 分析循环：三步原子操作，每步必更新 AST

LL(1) 分析主循环逻辑（伪代码）：

while (!parseStack.isEmpty()) { String top = parseStack.pop(); Token lookahead = inputTokens.peek(); // 不移除 if (isTerminal(top)) { if (top.equals(lookahead.type.name())) { inputTokens.poll(); // 匹配成功，消耗 token // 终结符不生成 AST 节点，仅推进 } else { throw new ParseException("Expected " + top + ", got " + lookahead.type, lookahead.line); } } else { // top 是非终结符 String production = predictTable.get(top).get(lookahead.type.name()); if (production == null) { throw new ParseException("No production for " + top + " on " + lookahead.type, lookahead.line); } // 将产生式右部逆序压栈（因栈是 LIFO） String[] rhs = production.split("\\s+"); for (int i = rhs.length - 1; i >= 0; i--) { if (!rhs[i].isEmpty()) parseStack.push(rhs[i]); } // 关键：在此处调用 AST 构建函数，传入 top 和 rhs buildASTNode(top, rhs, lookahead); } }

逻辑说明：buildASTNode是核心钩子。例如top = "Statement"，rhs = ["if", "Condition", "then", "Statement", "else", "Statement"]，则创建IfNode，并将后续Condition、Statement（then）、Statement（else）的 AST 子树挂载为其字段。必须在压栈后立即构建，否则子节点顺序错乱。

3.3 AST 构建策略：右部符号到节点的映射规则

AST 不是语法树的简单复制，需剥离冗余符号（如;,begin,end,:=），只保留运算结构。规则：

• Expression → Term AddOp Term→ 构建BinaryOpNode(op=AddOp, left=TermAST, right=TermAST)
• Statement → ident := Expression→ 构建AssignNode(ident=ident.value, expr=ExpressionAST)
• Condition → Expression RelOp Expression→ 构建BinaryOpNode(op=RelOp, left=ExpressionAST, right=ExpressionAST)
• CompoundStatement → begin StatementList end→StatementListAST即为CompoundStatement的 AST，begin/end不生成节点

参数说明：buildASTNode函数需接收top（非终结符名）、rhs（右部符号数组）、lookahead（当前 token，用于取 ident 值）。例如处理ident := Expression时，rhs[0]是"ident"，需从lookahead取value；rhs[2]是"Expression"，其 AST 已在之前buildASTNode("Expression", ...)中构建完毕，此处直接引用。

3.4 预测表加载：从文件读取 vs 硬编码，南邮推荐后者

南邮实验二不要求动态文法，预测表固定。为防格式错误，建议硬编码初始化：

// 初始化 predictTable Map<String, Map<String, String>> predictTable = new HashMap<>(); predictTable.put("Statement", new HashMap<>()); predictTable.get("Statement").put("if", "if Condition then Statement else Statement"); predictTable.get("Statement").put("ident", "ident := Expression"); // ... 其他行

为什么不用 CSV 文件？因实验验收时需提交.java源码，外部文件易遗漏；且手算表已知大小，硬编码更可控。我见过同学 CSV 解析时因空格没 trim 导致predictTable.get("Statement").get("if ")为 null，报错信息却是“no production”，排查半小时。

4. AST 可视化与验证：用缩进文本和 DOT 图揪出结构错误

4.1 缩进文本序列化：人眼可读的 AST 结构快照

南邮实验报告要求“输出语法分析结果”，最稳妥方式是打印缩进文本。ASTNode.toString(int indent)方法：

public String toString(int indent) { StringBuilder sb = new StringBuilder(); String prefix = " ".repeat(indent); if (this instanceof AssignNode) { AssignNode n = (AssignNode) this; sb.append(prefix).append("Assign: ").append(n.ident).append("\n"); sb.append(n.expr.toString(indent + 1)); } else if (this instanceof BinaryOpNode) { BinaryOpNode n = (BinaryOpNode) this; sb.append(prefix).append("BinaryOp: ").append(n.op).append("\n"); sb.append(n.left.toString(indent + 1)); sb.append(n.right.toString(indent + 1)); } else if (this instanceof IfNode) { IfNode n = (IfNode) this; sb.append(prefix).append("If\n"); sb.append(prefix).append(" Condition:\n"); sb.append(n.cond.toString(indent + 2)); sb.append(prefix).append(" Then:\n"); sb.append(n.thenBranch.toString(indent + 2)); if (n.elseBranch != null) { sb.append(prefix).append(" Else:\n"); sb.append(n.elseBranch.toString(indent + 2)); } } return sb.toString(); }

验证技巧：对输入if a > 0 then b := 1 else b := 0，正确输出应为：

If Condition: BinaryOp: > Ident: a Number: 0 Then: Assign: b Number: 1 Else: Assign: b Number: 0

若Condition下没出现BinaryOp，说明Condition → Expression RelOp Expression未触发；若Then和Else缩进不对齐，说明IfNode构建时子节点挂载错位。

4.2 DOT 图生成：用 Graphviz 直观查父子关系

为防缩进文本视觉疲劳，生成 DOT 文件供 Graphviz 渲染：

public void toDot(PrintWriter writer, String parentId) { String nodeId = "node" + idCounter++; if (this instanceof AssignNode) { writer.printf(" %s [label=\"Assign(%s)\"];\n", nodeId, ((AssignNode)this).ident); writer.printf(" %s -> %s;\n", parentId, nodeId); ((AssignNode)this).expr.toDot(writer, nodeId); } else if (this instanceof BinaryOpNode) { writer.printf(" %s [label=\"BinaryOp(%s)\"];\n", nodeId, ((BinaryOpNode)this).op); writer.printf(" %s -> %s;\n", parentId, nodeId); ((BinaryOpNode)this).left.toDot(writer, nodeId); ((BinaryOpNode)this).right.toDot(writer, nodeId); } }

落地命令：生成ast.dot后，终端执行dot -Tpng ast.dot -o ast.png，即可得清晰树图。南邮助教验收时，常放大 PNG 查if节点是否同时有cond、then、else三条边——这是比读文本更快的结构审计。

4.3 错误恢复机制：让分析器不死于单个 token 错误

南邮实验输入常含人为错误（如if x > 0 the b := 1漏n）。LL(1) 默认遇错即停，需加恢复：

• 当predictTable.get(top).get(lookahead.type)为 null 时，不抛异常，而执行：
  • 若top在 FOLLOW 集中，弹出栈顶，跳过当前 token（同步恢复）；
  • 否则，从输入流中跳过 token，直到遇到 FOLLOW(top) 中的符号（短语级恢复）。

String top = parseStack.pop(); Token lookahead = inputTokens.peek(); if (isTerminal(top)) { if (top.equals(lookahead.type.name())) { inputTokens.poll(); } else { // 终结符不匹配：跳过当前 token，尝试下一个 System.err.println("Skip token " + lookahead.type + " at line " + lookahead.line); inputTokens.poll(); } } else { String production = predictTable.get(top).get(lookahead.type.name()); if (production == null) { // 非终结符无产生式：检查 FOLLOW，若在则弹出 top；否则跳过 token Set<String> follow = followSet.get(top); if (follow != null && follow.contains(lookahead.type.name())) { System.err.println("Sync: pop " + top + " on " + lookahead.type); } else { System.err.println("Skip token " + lookahead.type + " at line " + lookahead.line); inputTokens.poll(); } } else { // 正常压栈... } }

避坑：错误恢复常见问题
现象 1：加了恢复后，错误传播，后续大量误报
原因：恢复后未重置栈状态。例如top=Statement无产生式，你跳过the，但栈顶仍是Statement，下次循环又遇到the，无限循环。解决：恢复后continue跳过本次循环，不执行后续压栈

现象 2：FOLLOW(Statement)包含;，但输入是if x > 0 the b := 1;，the不在 FOLLOW 中，应跳过，但程序却弹出Statement导致栈空
原因：FOLLOW集计算错误，或the被词法分析器识别为IDENT而非THEN，导致lookahead.type.name()是"IDENT"而非"THEN"。解决：先确认词法分析器输出是否正确，再查 FOLLOW 集是否含IDENT（通常不含，Statement的 FOLLOW 是;,end,$）

现象 3：恢复后 AST 缺失节点，如if语句只生成Condition，无Then
原因：恢复发生在buildASTNode之前，导致该次产生式未触发构建。解决：恢复逻辑必须在buildASTNode调用之后，或确保恢复不破坏已构建的子树

5. 南邮实验二验收要点与性能优化：让代码经得起助教三连问

5.1 助教高频提问清单：从原理到代码细节

南邮实验验收不是跑通就行，助教会现场提问，以下问题出现频率超 80%：

• Q1：“你文法里的StatementList → Statement { ; Statement }，{ ; Statement }是什么？它对应的产生式怎么写？FIRST 集是什么？”
  →答：{ ; Statement }是 EBNF 重复结构，等价于StatementList' → ; Statement StatementList' | ε，其 FIRST = {;, ε}
• Q2：“Expression → Term Expression'和Expression' → AddOp Term Expression' | ε，为什么Expression'的 FOLLOW 包含)？”
  →答：因Factor → ( Expression )，Expression后是)，故)∈ FOLLOW(Expression)；又因Expression → Term Expression'，所以)∈ FOLLOW(Expression')
• Q3：“你的AssignNode类，expr字段类型是ASTNode还是ExpressionNode？如果传入IfNode会怎样？”
  →答：必须是ASTNode（基类），多态保证；若传错类型，toString()会调用IfNode.toString()，结构正确，无运行时错误

翻车预警：若答不出 Q1/Q2，助教会认为你没手算 FIRST/FOLLOW，直接扣分；若 Q3 答“用ExpressionNode”，说明你没理解 AST 的泛型设计，可能被要求重构。

5.2 内存与速度优化：小改动提升大体验

南邮实验输入规模不大（<100 行），但优化体现工程素养：

• 栈操作优化：Stack已过时，改用ArrayDeque（parseStack = new ArrayDeque<>()），push/pop性能提升 30%
• 字符串分割优化：production.split("\\s+")在循环中频繁调用，改为预编译Pattern.compile("\\s+")，或直接用StringTokenizer
• AST 节点 ID 生成：避免UUID.randomUUID()，用静态计数器private static int idCounter = 0;，省去字符串哈希开销

// 优化后的 ASTNode 构造 public ASTNode() { this.id = idCounter++; // O(1) } // 而非 this.id = UUID.randomUUID().toString(); // O(n) 字符串生成

5.3 一键验证脚本：用 Bash 自动化测试全流程

为防验收前夜手忙脚乱，写test.sh一键跑通：

#!/bin/bash # 编译 javac -d bin src/*.java # 生成词法分析结果（假设实验一已提供 LexicalAnalyzer） java -cp bin LexicalAnalyzer < test1.pl0 > tokens.txt # 运行语法分析器 java -cp bin Parser < tokens.txt > ast.txt # 生成 DOT 并转 PNG java -cp bin ASTPrinter < tokens.txt > ast.dot dot -Tpng ast.dot -o ast.png echo "Test1 done. Check ast.txt and ast.png"

后悔药：南邮实验二截止前 2 小时，我因tokens.txt格式多了一空格，Parser读取时split(" ")出错。后来改成input.nextLine().trim().split("\\s+")，并加test.sh自动校验tokens.txt行数是否匹配预期——这招救了我。

6. 我的三个硬核习惯：让编译原理实验从“应付”变成“真懂”

6.1 习惯一：手写 FIRST/FOLLOW 表时，用 Excel 行列锁定功能

南邮实验要求手写表格，但手写易错。我的做法：

• 在 Excel 新建 sheet，A1:A20 填非终结符（Program,Block,Statement…），B1:Z1 填终结符（ident,number,if,then,;,),$…）
• 选中 A1:Z1 → “视图” → “冻结窗格” → “冻结首行首列”
• 这样滚动时，行列标题永远可见，填M[Statement, if]时不会看串行。填完后截图贴报告，清晰度远超手写。

6.2 习惯二：AST 节点类全部实现equals()和hashCode()

这不是实验要求，但极大提升调试效率。例如：

@Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; AssignNode that = (AssignNode) o; return Objects.equals(ident, that.ident) && Objects.equals(expr, that.expr); }

这样就能写单元测试：

@Test public void testIfNode() { IfNode node = new IfNode(cond, thenBranch, elseBranch); assertEquals("If", node.toString(0).substring(0, 2)); // 验证类型 }

南邮虽不考单元测试，但当你怀疑IfNode构建错时，assertEquals一行就定位到cond字段为空——比打断点快十倍。

6.3 习惯三：为每个产生式写独立的buildXXX()方法，而非大switch

早期我写：

switch (top) { case "Statement": if (rhs[0].equals("if")) buildIf(...); else if (rhs[0].equals("ident")) buildAssign(...); break; }

问题：rhs数组索引易错（rhs[0]是"if"，但rhs[1]是"Condition"，不是"if"），且难以单测。
现在改为：

private ASTNode buildStatement_if(String[] rhs) { return new IfNode( buildCondition(rhs, 1), // rhs[1] 是 Condition buildStatement(rhs, 3), // rhs[3] 是 then Statement buildStatement(rhs, 5) // rhs[5] 是 else Statement（若存在） ); }

每个方法职责单一，参数明确，buildCondition只管Condition，buildStatement只管Statement，互不干扰。南邮实验二代码量不大，这种设计让助教一眼看懂你的构建逻辑，而不是在 switch 里找分支。

最后说一句：编译原理实验二不是终点，而是你第一次亲手把“语法”变成“结构”的临界点。那些手算 FIRST 时的草稿纸、预测表里涂改的墨迹、AST PNG 图上反复确认的箭头——它们不会消失，会沉淀成你读 clang 源码、调 LLVM Pass、写 DSL 解析器时的直觉。希望帮到你。

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