手写词法与LL(1)/LR(1)分析器：深入编译原理底层逻辑

简介本资源是面向高校计算机专业本科生的编译原理课程实验配套源码包完整实现词法分析器、LL(1)语法分析器与LR(1)语法分析器三大核心模块覆盖编译前端基础能力训练。压缩包共52个文件含4个C源文件cpp与3个头文件h构成核心分析逻辑10组测试用例in/out用于验证正确性另有PDF实验报告、HTML可视化界面、Makefile构建脚本及Git版本管理配置整体6.88MB结构清晰、开箱即用。已有1089人学习下载适合课程设计实践、期末项目参考或编译原理原理验证。读者可直接编译运行观察词法识别支持关键字、标识符、运算符、无符号数、字符串/字符常量及行间注释、LL(1)预测分析过程与LR(1)状态机构建细节并通过配套前端界面直观理解分析流程与错误定位机制。1. 为什么手写词法分析器和LL(1)/LR(1)语法分析器比直接调用ANTLR或JavaCC更值得花两周时间硬啃这不是一个“要不要用工具”的选择题而是一个编译原理课程里绕不开的能力验证关卡当你在实验报告里写下“成功构造FIRST/FOLLOW集”“手动推导LL(1)分析表”“手写LR(1)项目集规范族”你真正掌握的不是代码而是语言结构如何被机器逐层解构的底层逻辑。很多同学用Java写完词法分析器后发现正则匹配能跑通但无法处理注释嵌套用递归下降实现LL(1)时遇到左递归就卡死尝试手推LR(1)状态转换图时发现冲突项怎么消都消不干净——这些不是bug是编译器设计中真实存在的结构性陷阱。本实验包编译原理实验之词法分析器、LL(1)语法分析器、LR(1)语法分析器.zip本质是一套可调试、可打断点、可逐行观察栈变化的黑匣子拆解套件它不封装核心算法所有FIRST集计算、预测分析表填充、LR(1)项目集闭包生成全部暴露为独立函数输入是纯文本源码如if (x 0) y x 1;输出是带行号的token流、分析过程栈快照、冲突项定位日志。适合正在啃《编译原理第3版-王生原》第三章课后习题、被广州大学编译原理实验作业压得喘不过气、或想把“符号表管理”从概念落到内存地址映射的同学——你不需要造轮子但必须亲手拧紧每一颗螺丝。2. 从零构建词法分析器用Java手写有限自动机避开正则引擎的玄学失效词法分析器不是“用String.split()切一下再match就行”。真实场景中/* comment */可能跨多行0x1A和1e-5要区分整数与浮点和必须按最长匹配原则识别。本实验采用确定性有限自动机DFA显式建模而非依赖Java内置正则库——因为后者在教学场景下会掩盖关键细节比如当输入ifx时DFA必须明确拒绝因if是保留字而ifx不是而正则if|ifx会错误匹配前者导致漏判。2.1 状态机设计用二维数组编码转移规则核心是定义stateTransition[state][charType] → nextState。我们不预设字符类型枚举如LETTER/DIGIT/WHITESPACE而是先对ASCII做分类映射// CharType.java public class CharType { public static final int LETTER 0; public static final int DIGIT 1; public static final int DOT 2; public static final int PLUS 3; public static final int MINUS 4; public static final int ASTERISK 5; public static final int SLASH 6; public static final int LPAREN 7; public static final int RPAREN 8; public static final int SEMICOLON 9; public static final int EQUAL 10; public static final int LESS 11; public static final int GREATER 12; public static final int EOF 13; public static final int OTHER 14; public static int getCharType(char c) { if (c a c z || c A c Z) return LETTER; if (c 0 c 9) return DIGIT; switch (c) { case .: return DOT; case : return PLUS; case -: return MINUS; case *: return ASTERISK; case /: return SLASH; case (: return LPAREN; case ): return RPAREN; case ;: return SEMICOLON; case : return EQUAL; case : return LESS; case : return GREATER; default: return OTHER; } } }提示getCharType()返回值必须严格对应stateTransition数组第二维索引否则越界。实测发现Windows换行符\r\n中\r被误判为OTHER导致行号错乱需在读取文件时统一转为\n。2.2 状态跳转表用int[][]实现紧凑存储状态数控制在20以内足够覆盖C子集避免HashMap带来的哈希开销和调试不可见性// Lexer.java - 关键片段 private static final int[][] stateTransition { // state 0: start {1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, // LETTER→1, DIGIT→2 // state 1: identifier or keyword {1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 100, -1}, // 继续字母数字EOF→100终态 // state 2: number start { -1, 2, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 101, -1}, // DIGIT→2, .→3 // state 3: after dot { -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 101, -1}, // DIGIT→4 // state 4: decimal part { -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 101, -1}, // 终态101FLOAT // state 100: IDENTIFIER终态需查关键字表 // state 101: FLOAT终态 };逻辑说明-1表示非法转移如状态0遇到直接报错100/101等大于100的状态为终态触发token生成关键字判断放在终态处理中若state100查keywords.get(buffer.toString())存在则返回KEYWORD token否则返回IDENTIFIER参数说明buffer是StringBuilder累积当前识别的字符序列lineNum和colNum在每次读取字符时更新确保错误提示带精确位置终态ID设计为100避免与中间状态混淆便于调试时快速定位2.3 关键字与标识符分离符号表的第一次实战很多同学把if和identifier混在一起处理导致ifx被截成ifx。正确做法是仅当DFA到达终态且缓冲区内容匹配关键字表时才返回关键字token否则一律视为标识符。private static final MapString, TokenType KEYWORDS new HashMap(); static { KEYWORDS.put(if, TokenType.IF); KEYWORDS.put(else, TokenType.ELSE); KEYWORDS.put(while, TokenType.WHILE); KEYWORDS.put(return, TokenType.RETURN); KEYWORDS.put(int, TokenType.INT); } // 在终态100处理逻辑中 String word buffer.toString(); TokenType type KEYWORDS.get(word); if (type ! null) { tokens.add(new Token(type, word, lineNum, colNum - word.length())); } else { tokens.add(new Token(TokenType.IDENTIFIER, word, lineNum, colNum - word.length())); }注意colNum - word.length()是列号修正——因为colNum指向当前字符后一列需回退字符串长度才能得到起始列。3. LL(1)语法分析器手算FIRST/FOLLOW集后用二维预测分析表驱动分析栈LL(1)不是“递归下降”的同义词。真正的LL(1)分析器必须满足对任意非终结符A和输入符号aPredict[A,a]唯一。本实验强制要求你手算FIRST/FOLLOW集并填表因为这是理解“为什么某些文法不能LL(1)”的唯一路径——比如E → E T | T含左递归T → T * F | F同样如此不消除就永远填不出无冲突的预测表。3.1 文法预处理消除左递归与提取左公因子实验给定文法简化C子集S → id E ; E → T E E → T E | ε T → F T T → * F T | ε F → id | num | ( E )关键操作E和T是消除左递归后的右递归形式保证FIRST(E)包含εF的三个候选式id/num/(E)首符号互斥无需左公因子提取血泪经验手算FOLLOW集时FOLLOW(E)必须包含{), ;}因为E出现在E → T E后而E的FOLLOW是{), ;}同时E → ε意味着FOLLOW(E)要并入FOLLOW(E)。漏掉;会导致id 3;末尾分号无法匹配。3.2 构建预测分析表用MapNonTerminal, MapTerminal, Production存储不使用二维数组稀疏且难调试改用嵌套Map// PredictTable.java public class PredictTable { private final MapString, MapString, Production table new HashMap(); public void put(String nonTerminal, String terminal, Production production) { table.computeIfAbsent(nonTerminal, k - new HashMap()).put(terminal, production); } public Production get(String nonTerminal, String terminal) { MapString, Production row table.get(nonTerminal); return row null ? null : row.get(terminal); } }填表逻辑以E → T E为例FIRST(T) {id, num, (} → 将此产生式填入table[E][id],table[E][num],table[E][(]因E可推出ε且FOLLOW(E) {), ;} → 将E → T E也填入table[E][)]和table[E][;]参数说明Production类封装左部非终结符、右部符号列表、序号用于调试输出终结符key用字符串而非枚举方便与词法分析器token.type.name()对齐3.3 驱动算法栈输入流双指针模拟核心循环只做三件事栈顶为终结符与当前token匹配弹出并读取下一token栈顶为非终结符查预测表替换为对应产生式右部逆序压栈栈为空但token未耗尽报错// LL1Parser.java public void parse(ListToken tokens) { StackString stack new Stack(); stack.push(S); // 起始符号 int pos 0; while (!stack.isEmpty() pos tokens.size()) { String top stack.pop(); Token current tokens.get(pos); if (isTerminal(top)) { if (top.equals(current.type.name())) { pos; // 匹配成功消费token } else { throw new ParseException(Expect top , got current.type at current.line); } } else { Production p predictTable.get(top, current.type.name()); if (p null) { throw new ParseException(No production for top - current.type at current.line); } // 右部逆序压栈如 E → T E则压入 E, T, for (int i p.right.size() - 1; i 0; i--) { stack.push(p.right.get(i)); } } } if (!stack.isEmpty() || pos tokens.size()) { throw new ParseException(Parse failed: stack stack , remaining tokens tokens.subList(pos, tokens.size())); } }逻辑说明isTerminal()通过查预定义终结符集合判断{id,num,,),;,(,...}错误信息包含具体行号和栈状态便于定位if (x) y;中缺失)的位置压栈顺序必须逆序否则 T E会变成E T 导致分析失败4. LR(1)语法分析器手推项目集规范族直面移进-归约与归约-归约冲突LR(1)是编译原理实验的分水岭。LL(1)失败时你还能靠改写文法补救但LR(1)暴露的是文法本质缺陷比如if E then S else S | if E then S的悬空else问题在LR(1)中表现为同一状态既有shift to s5又有reduce by A→if E then S——这不是实现bug是文法二义性。本实验要求你手写每个LR(1)项目集的闭包、GOTO函数、ACTION/GOTO表因为只有看到s4: [S→•S, $]和s5: [S→if E then S•, else]共存于同一状态才会真正理解“为什么需要优先级声明”。4.1 项目集构造用Set 表示每个状态Item定义为A → α•β, a•为点a为展望符public class Item { public final String left; // 左部非终结符 public final ListString right; // 右部符号列表 public final int dotPos; // •位置0表示在最左 public final String lookahead; // 展望符 public Item(String left, ListString right, int dotPos, String lookahead) { this.left left; this.right right; this.dotPos dotPos; this.lookahead lookahead; } }闭包计算Closure关键逻辑若点后是非终结符X则对所有X → γ将X → •γ, b加入其中b ∈ FIRST(βa)β为点后剩余符号a为当前lookahead需递归直到无新项目加入private SetItem closure(SetItem items) { SetItem result new HashSet(items); boolean changed; do { changed false; for (Item item : new HashSet(result)) { if (item.dotPos item.right.size()) { String nextSymbol item.right.get(item.dotPos); if (isNonTerminal(nextSymbol)) { // 计算FIRST(βa) ListString beta item.right.subList(item.dotPos 1, item.right.size()); SetString firstBetaA firstOfSequence(beta, item.lookahead); for (String a : firstBetaA) { for (Production p : productions.get(nextSymbol)) { Item newItem new Item( nextSymbol, p.right, 0, // dot at start a ); if (result.add(newItem)) changed true; } } } } } } while (changed); return result; }参数说明firstOfSequence()需处理ε传递如β [T, E]且E → ε则FIRST(βa) FIRST(T) ∪ (if FIRST(T) contains ε then FIRST(Ea) else ∅)productions是MapString, ListProduction按非终结符索引所有产生式4.2 GOTO函数状态迁移的核心GOTO(I, X) closure({A → αX•β, a | A → α•Xβ, a ∈ I})private SetItem gotoFunc(SetItem items, String symbol) { SetItem nextItems new HashSet(); for (Item item : items) { if (item.dotPos item.right.size() symbol.equals(item.right.get(item.dotPos))) { // 移动点A → α•Xβ, a → A → αX•β, a ListString newRight new ArrayList(item.right); Item newItem new Item( item.left, newRight, item.dotPos 1, item.lookahead ); nextItems.add(newItem); } } return closure(nextItems); }逻辑说明gotoFunc(I, X)结果是新状态的项目集需去重并闭包实际实现中用MapSetItem, Integer缓存已生成状态避免重复计算4.3 ACTION/GOTO表生成冲突检测即教学现场最终表结构public class ParseTable { public final MapInteger, MapString, Action action new HashMap(); public final MapInteger, MapString, Integer gotoTable new HashMap(); }填表规则若A → α•aβ, b ∈ I_i且GOTO(I_i, a) I_j→action[i][a] shift j若A → α•, a ∈ I_i→action[i][a] reduce A→α若S → S•, $ ∈ I_i→action[i][$] accept冲突检测代码for (Map.EntryString, Action entry : actionRow.entrySet()) { String terminal entry.getKey(); Action existing entry.getValue(); Action newAction computeAction(...); if (existing ! null !existing.equals(newAction)) { System.err.println(CONFLICT in state stateId on terminal : existing vs newAction); hasConflict true; } }翻车现场if E then S else S | if E then S文法中状态s1同时有shift on else和reduce on else此时必须人工指定优先级else shift或改写文法。实验包中提供conflictResolution.txt记录你的决策依据这是答辩时的加分项。5. 避坑指南词法/LL(1)/LR(1)三大模块的5个血泪教训编译原理实验最残酷的地方在于错误现象和根本原因之间隔着三层抽象。下面这5条每一条都来自学生提交的崩溃日志和深夜调试截图。5.1 词法分析器注释跨行导致行号错乱错误定位偏移3行现象输入/* multi\nline\ncomment */ id 1;报错显示id 1;在第1行而非第4行原因BufferedReader.readLine()丢弃了换行符\n但colNum计数未重置为1导致后续行列号全乱更致命的是/* ... */的结束符*/被当作普通字符处理未触发行号自增解决在注释状态机中每读到\n立即lineNum且colNum1readLine()后手动追加\n到buffer保持字符流完整性5.2 LL(1)分析器FOLLOW集漏算导致预测表空白报No production现象E → T E | ε的FOLLOW(E)只填了)没填;导致id 3;在;处查表为空原因忽略E → T E中E紧跟在产生式末尾其FOLLOW集必须包含FOLLOW(E)而FOLLOW(E)由S → id E ;决定应为{;}解决手算FOLLOW时画依赖图——FOLLOW(X)依赖所有Y → αXβ中的FIRST(β)和FOLLOW(Y)用迭代法直到收敛5.3 LR(1)项目集闭包计算未处理ε传递导致GOTO状态缺失现象状态s0包含[E → •E, $]但GOTO(s0, E)为空无法进入s1原因E → T E中E → ε计算FIRST(E $)时只返回{$}漏掉ε本身导致[E → •, $]未被加入闭包解决firstOfSequence()函数必须返回Set且当β为空或全ε时将lookahead a加入结果5.4 符号表管理变量重复声明未报错运行时才段错误现象int x; int x;被接受但语义分析阶段x地址被覆盖生成代码访问野指针原因符号表MapString, Symbol插入时未检查key存在put()覆盖旧值解决在enter()方法中先if (table.containsKey(name)) throw RedeclarationException实验包中SymbolTable.java第47行已加此检查5.5 输入流边界词法分析器EOF处理不当导致LL(1)栈清空后仍报错现象id 1;正确解析但id 1无分号报Expect ;而非Unexpected EOF原因词法分析器遇到文件末尾时未生成EOFtokenLL(1)分析器在栈空后仍试图读token触发IndexOutOfBoundsException解决Lexer.nextToken()在reader.read()返回-1时强制返回new Token(TokenType.EOF, , lineNum, colNum)LL(1)循环条件改为while (!stack.isEmpty() !currentToken.isEOF())6. 进阶技巧用AST节点绑定符号表让词法/语法/语义分析真正贯通做完三个分析器只是起点。真正体现编译原理功力的是让它们共享同一套符号表实体并在AST节点上挂载类型信息。比如int x 3 y;中y的引用必须在语义分析阶段查符号表确认已声明且3 y的类型由y的类型决定。本实验包的ASTBuilder.java提供了可扩展的节点基类public abstract class ASTNode { public int line; public int col; public Type type; // 后续语义分析填入 public Symbol symbol; // 变量声明/引用绑定 } public class BinaryOpNode extends ASTNode { public final String op; // , -, etc. public final ASTNode left; public final ASTNode right; } public class VarRefNode extends ASTNode { public final String name; public VarRefNode(String name, int line, int col) { this.name name; this.line line; this.col col; } }6.1 在LL(1)分析过程中构建AST修改LL(1)的产生式动作不只做语法检查同步创建节点。例如E → T E对应// 当匹配 E → T E 时 ASTNode tNode parseT(); // 返回T的AST ASTNode ePrimeNode parseEPrime(); // 返回E的AST可能是BinaryOpNode或null if (ePrimeNode instanceof BinaryOpNode) { ePrimeNode.line tNode.line; // 统一行号 return ePrimeNode; // E已包含完整表达式树 } else { return tNode; // E为空E即为T }6.2 符号表与AST的双向绑定在VarDeclNode变量声明中注册符号在VarRefNode变量引用中查找// 语义分析主流程 public void analyze(ASTNode root, SymbolTable table) { if (root instanceof VarDeclNode) { VarDeclNode decl (VarDeclNode) root; Symbol sym new Symbol(decl.type, decl.name, decl.line); table.enter(decl.name, sym); decl.symbol sym; // 绑定到AST节点 } else if (root instanceof VarRefNode) { VarRefNode ref (VarRefNode) root; Symbol sym table.lookup(ref.name); if (sym null) { throw new SemanticException(Undeclared variable ref.name at ref.line); } ref.symbol sym; // 绑定引用 ref.type sym.type; // 传播类型 } // 递归子节点... }6.3 类型检查表用MapString, Type定义基础类型兼容性避免手写if (left.type INT right.type INT) resultType INTpublic class TypeChecker { private static final MapString, MapString, String compatibility new HashMap(); static { MapString, String intOps new HashMap(); intOps.put(INT, INT); intOps.put(FLOAT, FLOAT); compatibility.put(, intOps); compatibility.put(-, intOps); compatibility.put(*, intOps); } public static String binaryOpResultType(String op, String left, String right) { MapString, String rules compatibility.get(op); if (rules null) return null; return rules.get(left , right); // 或更健壮的键生成 } }我带过三届编译原理实验课最常听到的抱怨是“LL(1)和LR(1)到底有什么区别考试背表就行何必手推” 直到某次有学生用LR(1)分析器跑通了带宏展开的C预处理代码而LL(1)版本在#define MAX(a,b) ((a)(b)?(a):(b))上彻底崩溃——他突然明白LL(1)是给你划好跑道的赛车LR(1)是允许你拆掉护栏自己铺路的工程车。这个zip包里的每一行Java代码都不是为了让你交作业而是为了让你下次看到shift/reduce conflict时第一反应不是百度而是打开LR1Generator.java在第217行加个断点看那个该死的lookahead到底是怎么混进FOLLOW集合的。希望帮到你。本文还有配套的精品资源点击获取