编译原理实验指南：手写词法分析、语法分析与符号表全流程-北京尧图网络

简介这是一套面向中国海洋大学编译原理课程的实验源码与指导合集覆盖2020年春季学期全部8个实验从词法分析、语法分析、语义分析到中间代码生成、代码优化、目标代码生成、错误处理与编译器综合并附《实验内容和要求》文档适合正在学习编译器构造的学生按阶段对照实践。压缩包内共有74个文件以C源码和Lex/Yacc源文件为核心配合头文件、makefile构建脚本、可执行程序与测试用例整体仅774KB目录按实验一至八分模块展示便于定位。已有4411人学习下载。借助其中完整的编译前端实现、语法树打印与错误诊断代码以及测试程序和输出样例读者可运行调试、观察二义性文法与无二义文法的处理差异并将各阶段组件串成完整编译器真正理解编译原理从源码到目标代码的完整脉络。1. OUC编译原理全部实验一门课里最值得自己动手重写的代码OUC编译原理全部实验是这类课程里最值得自己一行行重写的代码词法分析、语法分析、语义分析、符号表管理串起来就是一条完整的编译器前端链路。很多人上课时听懂了正则、LL(1)、LR(1)一打开实验模板却对着几百行骨架发懵最后从网上找一份代码改个文件名交差答辩时连变量都解释不清。这篇文章按课程实验的常见顺序把每个实验的输入、输出、边界和踩坑讲清楚写给两类人正在被实验报告追着跑的在校生以及工作后想回炉把编译原理前端补扎实的工程师。你能照着这个思路重写一套自己的实现而不是复制一份连注释都是别人的代码。2. 词法分析实验从正则到 token 流手写一个扫描器2.1 词法分析到底在考什么把正则文法变成状态机词法分析实验是整个编译原理实验的入口它的任务是把源程序字符串拆成 token 序列。很多人觉得这是在考正则表达式实际上实验模板给你的往往不是正则库而是要求你手工构造一个有限自动机。比如识别一个标识符正则写起来是[a-zA-Z_][a-zA-Z0-9_]*但手写扫描器时你要维护的状态是当前字符是不是字母或下划线、后续字符是否允许出现在标识符中间、什么时候该把累积的字符切出来。这里的核心概念是“最长匹配”。比如输入intx如果关键字表里只有int扫描器不能读进i、n、t就立刻判定为关键字而要继续读x发现intx整体是一个标识符。最容易出错的地方也在这里把关键字判定放在最长匹配之前导致intx被拆成int和x两个 token。实验报告的得分点通常就藏在这种边界用例里。我见过不少同学直接用 JDK 的String.split加一堆正则硬拆面对运算优先级不敏感的简单语法也能跑通但一旦加上字符串常量、浮点数、多行注释规模就失控了。常见做法仍然是手写逐字符扫描因为词法分析器的逻辑是线性的读一个字符、判断状态、决定是否切分。这个线性逻辑在后续语法分析报错时需要精确到行号和列号正则批量替换很难做到。2.2 最小可跑的 Java 词法分析器识别标识符、数字、运算符下面这个实现是我常用的一种最小结构适合 OUC 编译原理第一个实验的常见要求识别标识符、整型/浮点数字、加减乘除运算符、括号、赋值号并记录行号。语言用 Java因为很多学校模板就是 Java但它换成 C 或 Python 只是语法差异状态迁移逻辑完全一样。import java.util.ArrayList; import java.util.List; import java.util.Set; public class Lexer { private final String src; private int pos 0; private int line 1; private static final SetString KEYWORDS Set.of(int, float, if, else, while, return); public Lexer(String src) { this.src src; } public ListToken tokenize() { ListToken tokens new ArrayList(); while (pos src.length()) { char c src.charAt(pos); if (Character.isWhitespace(c)) { if (c \n) line; pos; } else if (Character.isLetter(c) || c _) { tokens.add(readIdentifierOrKeyword()); } else if (Character.isDigit(c)) { tokens.add(readNumber()); } else if (c || c - || c * || c /) { tokens.add(new Token(OP, String.valueOf(c), line)); pos; } else if (c ( || c ) || c { || c }) { tokens.add(new Token(DELIM, String.valueOf(c), line)); pos; } else if (c ) { if (pos 1 src.length() src.charAt(pos 1) ) { tokens.add(new Token(OP, , line)); pos 2; } else { tokens.add(new Token(ASSIGN, , line)); pos; } } else { throw new LexException(无法识别的字符 c 在第 line 行); } } tokens.add(new Token(EOF, , line)); return tokens; } private Token readIdentifierOrKeyword() { int start pos; while (pos src.length() (Character.isLetterOrDigit(src.charAt(pos)) || src.charAt(pos) _)) { pos; } String word src.substring(start, pos); String type KEYWORDS.contains(word) ? KEYWORD : IDENT; return new Token(type, word, line); } private Token readNumber() { int start pos; while (pos src.length() Character.isDigit(src.charAt(pos))) { pos; } if (pos src.length() src.charAt(pos) .) { pos; while (pos src.length() Character.isDigit(src.charAt(pos))) { pos; } } return new Token(NUM, src.substring(start, pos), line); } }逻辑说明tokenize()是主循环每次只前进一步遇到空白字符时单独处理换行保证行号跟踪准确。readIdentifierOrKeyword()先按“字母/数字/下划线连续”读满整个词再查关键字表把intx这类输入正确处理为标识符。readNumber()使用两个连续的while循环第一个保证整型部分读完第二个在遇到小数点时读取小数部分这样能识别3.14而不是拆成3、.、14。参数说明KEYWORDS集合决定了哪些词会被当作关键字实际实验里要根据自定义文法增减。这种情况是二字符运算符的典型代表如果你的文法还有、、需要在分支里继续扩展字符匹配。行号记录实现是line但注释和字符串里的换行不能触发行号自增这块在扩展实验里必须改。注意这种实现默认源程序是纯 ASCII。如果实验要求支持中文字符串常量Character.isLetter会把中文也判定为标识符起始字符需要在readIdentifierOrKeyword()里增加“仅 ASCII 字母”的判断。2.3 必调细节关键字表、行号记录、错误恢复词法分析器看起来代码量不大但几个细节决定了实验能不能拿到高分。第一是关键字表放在哪里。有的人把关键字写在switch里每读一个词做字符串比较效率低且难维护用Set的contains判断复杂度是 O(1)而且扩展关键字只改一处。第二是行号记录。很多同学只在 token 里存了词法和值没存行号等到语法分析实验做报错定位时才发现要回头改结构。我建议从第一个实验就把Token类设计成包含type、value、line三个字段后面所有实验都能直接复用。第三是错误恢复。词法分析遇到非法字符时最简单的做法是抛异常结束。但课程实验有时候要求“跳过非法字符继续分析”这时候需要把异常换成recordError()并在累加错误数后pos跳过。如果目标不是课程分数而是做一个真正能用的前端我建议保留“报错即停”的模式因为早期编译阶段频繁出错时一次性给你 50 个错误里可能只有 5 个是真的其余全是连锁误报。3. 语法分析实验用递归下降吃掉表达式与语句3.1 为什么实验选递归下降而不是 LALR语法分析实验是 OUC 编译原理里卡住人最多的一关因为它有两种典型路线自顶向下的递归下降和自底向上的 LALR 分析表。学校实验室里要求手写代码的绝大多数用递归下降原因很实际代码可读性强、报错位置准确、和后续语义动作能直接挂钩。LALR 分析器生成工具比如 yacc虽然功能强大但生成的表是个黑匣子实验答辩时老师问“这个状态转移为什么是 3 个动作”你很难答上来。更关键的是LALR 的文法冲突报错极其抽象对初学者极不友好。递归下降则是一手文法一手代码每个非终结符对应一个方法文法长什么样代码就是什么样。缺点是必须手动消除左递归比如E - E T这种文法直接写会无限递归常见做法是把左递归改成右递归或者用循环代替递归。我一般会建议把实验文法限制在 LL(1) 子集内。如果实验给的文法里有公共左因子比如两个产生式都以同一个终结符开头需要先提取公共左因子不然递归下降里无法决定走哪个分支。这一步做好了后面表达式、语句、作用域的代码都能按部就班地写下去。3.2 表达式优先级从文法消除二义性到代码实现表达式是语法分析里最有代表性的部分因为加减乘除和括号的优先级是人人都懂、但代码实现最容易乱的地方。文法上要先消除二义性经典做法是把优先级分层expr - term | expr term | expr - term term - factor | term * factor | term / factor factor - NUMBER | IDENT | ( expr )这个文法仍然有左递归直接写成递归下降会死循环。常见做法是改成基于优先级爬升Pratt Parsing的循环实现代码比纯递归下降更简洁。下面是一个最小实现处理加减乘除和括号public class ExprParser { private final Lexer lexer; private Token cur; public ExprParser(Lexer lexer) throws LexException { this.lexer lexer; this.cur lexer.tokenize().get(0); } public ASTNode parseExpr() { return parseExprWithMinPrec(1); } private ASTNode parseExprWithMinPrec(int minPrec) { ASTNode left parseFactor(); while (cur.type.equals(OP) prec(cur.value) minPrec) { String op cur.value; advance(); ASTNode right parseExprWithMinPrec(prec(op) 1); left new BinaryOpNode(op, left, right); } return left; } private ASTNode parseFactor() { if (cur.type.equals(NUM) || cur.type.equals(IDENT)) { ASTNode node new AtomNode(cur); advance(); return node; } if (cur.value.equals(()) { advance(); ASTNode inner parseExpr(); if (!cur.value.equals())) { throw new ParseException(缺少右括号, cur.line); } advance(); return inner; } throw new ParseException(无法识别的表达式起始符号 cur.value, cur.line); } private int prec(String op) { if (op.equals() || op.equals(-)) return 10; if (op.equals(*) || op.equals(/)) return 20; return 0; } private void advance() { ListToken tokens lexer.tokenize(); int nextIndex tokenIndex 1; // 实际工程里应通过索引游标取下一个 token这里省略游标细节 cur tokens.get(nextIndex); } }逻辑说明parseExprWithMinPrec(1)是最小优先级入口minPrec参数决定当前层接受哪些运算符。parseFactor()只负责数字、标识符和括号它永远是最底层的原子节点。循环内部读取运算符后递归调用parseExprWithMinPrec(prec(op) 1)1是关键它保证左结合性1 - 2 3会先算(1 - 2)再算 3而不是把2 3先结合。参数说明prec(op)返回 10 和 20 两个等级乘法优先级高于加法。如果实验文法里有取负号这种单目运算符需要单独设一个更高的优先级并放到parseFactor的前缀分支里。代码里advance()简化了 token 游标的细节实际实现时应该让词法分析器返回一个ListToken语法分析器内部维护一个index字段每次调用advance()只做index。3.3 语句与作用域从语法树到语义动作表达式层做完后语法分析实验的下一层是语句。常见装备是给文法加上赋值、if、while、return树节点从表达式节点扩展成语句节点。这一层真正的难点不是识别语法而是理解“语法分析不关心变量有没有声明过”。比如x y 1递归下降只负责确认这是一个合法的赋值语句至于x和y有没有定义、类型对不对那是语义分析的活。这里容易踩一个坑在语法分析阶段就试图查符号表。比如写parseStatement()时遇到IDENT就去符号表里查一下如果没找到就直接报错。这在简单实验里仿佛可行但遇到“先使用后声明”的语言特性就翻车。正确做法是语法分析只建树或直接输出语法动作符号表绑定放到专门的语义分析遍历。如果你的课程实验没有明确划分阶段我建议至少保留一个“语法分析完后再遍历一次 AST 做检查”的步骤这比边解析边查表要容易调试得多。语句的递归下降实现核心是每种语句对应一个方法方法开头根据当前 token 决定走哪个分支。比如if开头就走parseIfStatement()while开头走parseWhileStatement()IDENT开头尝试读读到了就是赋值语句读不到就回溯。回溯在递归下降里很费劲因此文法设计时要避免歧义。4. 符号表与语义分析实验作用域、绑定与类型检查4.1 符号表设计栈式作用域还是哈希表词法分析和语法分析做完编译原理实验进入一个分水岭——符号表与语义分析。这也是热词里“编译原理符号表”对应的核心考点。符号表的第一问题不是用什么数据结构存而是作用域怎么表达。最简单的是单张哈希表适合没有块级作用域的实验语言但大多数 OUC 实验要求支持函数作用域和块作用域单张哈希表会在退出作用域时无法恢复上一层的同名变量。常见做法是栈式作用域每个作用域一张哈希表作用域压栈进入出栈销毁。查符号时从栈顶向下找每个表查不到就查下一层。这种设计代码量小、语义直观且对嵌套作用域天然支持。另一种做法是给每个符号一个 ID哈希表里存(名字, 作用域ID, 类型)副作用是查询时必须携带当前作用域 ID 做过滤稍微复杂但便于实现“同一作用域内不允许重复声明”的检查。我一般会选择栈式作用域做课程实验因为它和递归下降天然匹配进一个{}块就pushScope()出块就popScope()。而且后续实验做中间代码生成时需要为每个变量生成偏移量栈式结构方便在符号条目里保存偏移信息。4.2 变量声明、引用与类型检查的最小实现语义分析实验的常见要求是变量使用前必须声明、类型必须匹配、函数调用参数个数和类型必须一致。下面是一个简化但结构完整的符号表实现支持作用域嵌套和基本类型检查import java.util.*; public class SymbolTable { private final DequeMapString, Symbol scopes new ArrayDeque(); public void pushScope() { scopes.push(new HashMap()); } public void popScope() { scopes.pop(); } public void declare(String name, String type, int line) { MapString, Symbol top scopes.peek(); if (top.containsKey(name)) { throw new SemanticException(重复声明 name, line); } top.put(name, new Symbol(name, type, line)); } public Symbol lookup(String name, int line) { for (MapString, Symbol scope : scopes) { Symbol sym scope.get(name); if (sym ! null) return sym; } throw new SemanticException(未声明变量 name, line); } public String checkType(String name, int line) { Symbol sym lookup(name, line); return sym.type; } static class Symbol { String name; String type; int definedLine; Symbol(String name, String type, int definedLine) { this.name name; this.type type; this.definedLine definedLine; } } }逻辑说明pushScope和popScope维护当前作用域链declare只往栈顶写如果栈顶已经有同名符号就报重复声明错误。lookup从栈顶向下遍历每一层查不到继续往下一层查直到栈底。这样内层作用域可以遮蔽外层同名变量退出内层后外层变量恢复可见。参数说明Symbol里的type字段按实验要求可以是int、float、bool或自定义类型。definedLine字段用于错误报告语义分析报错时能定位声明位置这在课程报告里是加分项。类型检查的实现通常是在遍历 AST 时对每个表达式节点调用checkType然后比较左右操作数的类型遇到int float是否允许取决于实验文法如果不允许就在这个位置报类型不匹配。注意函数声明需要单独处理参数列表和返回类型。常见做法是符号条目里增加ListParam字段函数调用时逐个比对数类型而不是直接比较一个整体类型字符串。4.3 语义错误的处理策略如何做到一次报告多个错误语义分析实验的另一个大坑是错误恢复。常见的报错方式是throw new SemanticException遇到第一个错误就终止。这在测试简单程序时没问题但课程实验的测试用例往往故意包含多个错误比如同时又重复声明和类型不匹配你的编译器只报第一个错误成绩单上就被扣分。我建议增加一个errorCount和一个reportError方法遇到错误先记录、不抛出、继续分析当前节点只有错误数超过阈值时才强制终止。比如private int errorCount 0; private void reportError(String msg, int line) { System.err.println(第 line 行: msg); errorCount; if (errorCount 50) { throw new TooManyErrorsException(错误超过 50 个终止编译); } }这个策略的思想是单个错误往往不影响分析器继续向下走比如int x abc;虽然类型不匹配但赋值语句的 AST 结构是完整的可以继续分析后续代码。只有错误导致 AST 结构无法构建时比如缺少右括号才必须立即终止。这也是真实编译器如 GCC 的做法能恢复就恢复不能恢复才放弃。5. 实验避坑编译原理实验的五个常见翻车点5.1 翻车点一一上来就想写一个完整的 C 语言编译器现象拿到实验说明书后第一反应是参照 GCC 的功能清单给自己的编译器加上数组、结构体、指针、函数重载结果写了两个星期连词法分析器都还在处理字符串转义。原因实验的评分标准是按阶段划分的词法分析实验只考 token 拆分语法分析实验只考 AST 结构过度设计反倒是给自己挖坑。解决严格按实验公告的阶段目标控制范围先把当前阶段跑通、提交、拿分再回头扩展。扩展功能时先加测试用例后加实现代码不要凭感觉加特性。5.2 翻车点二报错信息定位不准调试全靠 print现象程序输入一个错误表达式报错只写“语法错误”不写行号、不写当前 token你对着自己的代码找半天也没找到是在哪个函数抛的异常。原因我在 Java 课程设计里见过很多同学用System.out.println(error)代替真正的错误报告这类调试输出到了提交阶段又删不干净而且没有上下文信息。解决从词法分析实验开始就统一错误信息格式至少包含行号、期望值、实际值三个字段比如第 3 行: 期望 )实际 }。这样错误报告不是给人看的摆设而是能直接指导调试的线索。5.3 翻车点三没有标准测试集改一处挂一片现象词法分析跑通了int a 3;加到语法分析后改成支持数组下标发现原来能通过的测试样例全挂了还不知道什么时候改坏的。原因没有回归测试每次改代码只测刚加的功能不跑历史样例。解决花半天时间建一个testcases/目录按实验阶段放 10 到 20 个输入文件每个文件对应一个输出期望文件再写一个简单的 Shell 脚本批量跑。做实验时每次改动代码后跑一遍全量测试用时不到一分钟能省下大量调试时间。这个习惯在实验结束写报告时也很有说服力测试数据可以直接作为附件。5.4 翻车点四中间代码生成和符号表不同步现象语义分析阶段生成了符号表到中间代码实验时又自己建了一套变量名和临时变量的表格两边信息对不上生成的三地址码里频繁出现未定义寄存器。原因把符号表设计成了面向语义分析的结构没有预留中间代码生成需要的字段。解决在设计符号表条目时就把后续要用的字段都预留出来变量名、类型、作用域深度、如果需要生成三地址码再加一个临时位置或偏移量字段。即便当前实验用不到也先在Symbol类里写着避免之后重构。这个设计上的远视比其他补救措施都省时间。5.5 翻车点五不懂得利用已有工具链对拍现象自己的编译器输出结果不知道对不对老师给的测试用例太少心里没底。原因没有使用成熟的参考实现来验证自己的输出。解决用一个简单的 Python 脚本或javac来跑相同的源码对比自己的编译器和参考实现的行为差异。注意不能直接把参考实现当模板抄代码而是用它来检查行为比如自己把1 2的布尔值生成反了跑一遍javac就知道正确输出是什么。这个对拍手段尤其适用于代码生成实验能独立验证每个运算符的语义而不是靠肉眼猜。6. 把全部实验串成一条龙最小编译管线的验证方法与边界6.1 建立最小测试集从一行程序到嵌套函数所有实验都完成后我建议搭建一条“源码文件 → 词法 token → 语法 AST → 符号表绑定 → 输出”的最小管线用脚本一键跑完。测试集按难度递增分三档第一档是只有一个表达式的最小程序用于快速验证前端链路通不通第二档加入变量声明、赋值和 if、while 语句覆盖语法分析和符号表最常用的路径第三档加入函数调用和嵌套作用域专门验证符号表的生命周期和类型检查边界。每档测试都要有一个对应的期望输出文件格式可以是 token 序列、AST 缩进打印或中间代码文本。期望文件的生成办法是先用参考编译器跑一遍人工确认正确的样例把输出存下来以后每次都和它做 diff。这个测试集就是你的“后悔药”在后续做扩展实验时能立刻发现哪个改动破坏了几百行之前的功能。6.2 验证实验成果的实用技巧一个 Shell 脚本加三个检查点我习惯在每个实现阶段留一个检查脚本核心只有三行命令编译、运行、对比 diff。检查点按顺序来第一词法分析输出中所有 token 都带正确行号第二语法分析对错误输入能报出包含行号和预期的错误而不是抛异常崩溃第三语义分析不能出现“查不到符号”的内部空指针所有错误必须通过统一错误入口报告。一个常被忽略的边界是 EOF 处理源文件末尾没有换行时词法分析器要能正常结束而不是越界。这看起来是小问题但在测试脚本里用printf int a3; | 你的编译器这种输入时就会暴露。另一个边界是空文件很多实现遇到空文件时 token 列表是空的语法分析入口若无判断会直接抛IndexOutOfBoundsException。我对编译原理实验最大的教训是不要迷信一次写对的谬误再简单的实验也要留回归测试再快的修复也要跑一遍全量用例。课程实验的评分不是看你写了多少行代码而是看你处理了多少边界、报错是否友好、结构是否清晰。照这个流程走下来你会发现编译原理实验的每一阶段都在给下一个阶段铺路而不是交完作业就断掉。希望这份从词法到语义分析的拆解能帮你少走几段弯路把 OUC 编译原理全部实验做成一份自己讲得清楚、老师挑不出毛病的工程实践。本文还有配套的精品资源点击获取

编译原理实验指南：手写词法分析、语法分析与符号表全流程

相关推荐

MediaPipe多模态姿态检测实战：三模态对齐与世界坐标解析

ENVI Layer Stack批量处理与IDL自动化实战指南

从报文头到传输服务：用IB Vol 1规范体系化排查网络故障

更多资讯

mysql-8.0.15-winx64 zip包安装：初始化、配置与避坑全攻略

基于协同过滤的校园图书馆管理与推荐系统实现

吉大SNL编译器课设实战：从词法分析到x86汇编生成

异或操作可行性判定：从竞赛题看线性空间与不变量

Flask多租户SaaS权限管理实战：从数据模型到越权防护

Context7 使用文档：提升AI编程助手准确性的MCP服务器

今日更新

Susi AI API实战指南：susi_alexa_skill如何用Node.js调用chat.json获取智能回答

换新电脑了？KeyStats 恢复码数据找回完全指南，端到端加密统计一键重建

重建二叉树：由前序与中序遍历序列还原二叉树的原理与 Java 实现（YCBlogs 剑指 Offer 精讲）

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？