简介一份针对东北大学秦皇岛分校编译原理课程的实验报告围绕PL/0语言词法分析程序的设计与实现展开适合计算机专业本科生或正在学习编译原理的开发者用于理解词法分析的核心流程。资源包内共1个doc文档压缩包大小122KB内容完整、结构清晰。文档以C语言在Windows环境下实现包含实验目的、实验环境、实验代码及运行思路详细给出了isLetter、isDigit、isP、isJ等字符分类函数以及单词识别、关键词表ktt匹配、非法字符检测等功能模块的实现方法。读者可借助完整源代码与注释示例掌握从读取源程序、逐字符扫描到输出单词二元组的完整流程也可作为编译原理课程实验报告的参考样式同时为理解语法分析、语义分析等后续环节打下基础。资源当前已有97人学习。1. 编译原理实验报告不是课后心得它记录的是三次关键设计决策“编译原理实验报告”这几个字在多数人眼里就是期末一份交差文档代码跑通、截图贴上、写几句“通过本次实验我掌握了”就算完。但真拿高分、真能把编译原理变成自己能力的报告记的不是过程而是决策。词法分析用正则还是手写状态机、语法分析选递归下降还是 LR、符号表怎么管作用域——这三个选择背后各自有代价报告真正要写清楚的是“你为什么这么选、代价在哪、翻车了怎么修”。这决定了给分的人能不能看出你理解了编译器不是黑匣子。适合谁适合正在写编译原理实验、并且不想让报告停留在“代码附录心得”层面的人。这篇直接按词法、语法、符号表三段展开附 Java 代码骨架、测试方法和避坑记录。2. 词法分析实验从正则到 DFA代码骨架与报告里的两张表2.1 为什么词法实验绕不开 DFA 最小化词法分析最简单粗暴的思路是拿正则表达式逐个匹配 token 类型比如遇到字母开头就一直读直到读到一个既不是字母也不是数字的字符再回头查关键字表。这个做法在实验一够用但它有一个理论短板一旦语言的关键字和运算符多起来逐类匹配的时间会线性膨胀而且匹配顺序写错就会误判。王生原那本教材的第三章整个就是在讲怎么从正则表达式构造 NFA、再确定化为 DFA、最后做最小化——目的就是让词法分析器在“读一个字符、换一个状态”的固定开销下工作。实验里我一般建议做到 DFA 这一层不是因为它比手写匹配快多少而是因为它逼你把 token 种类、状态转移、接受状态这三样东西显式建模。只要这三样是显式的报告里就能画状态转换表、能算状态数、能讨论最小化前后差多少。如果只写一个while循环加if判断状态是隐式的报告根本没有可分析的对象。2.2 用 Java 写一个最小可用的词法分析器骨架用 Java 写词法实验的人最多我给出一个能跑通基础运算表达式的最小骨架。它识别标识符、整数、运算符和关键字核心是把“读字符切 token”和“查关键字表”分离成两步。import java.util.*; public class Lexer { // 关键字表识别为标识符后二次归类 private static final SetString KEYWORDS Set.of(if, else, while, return); private final String input; private int pos; public Lexer(String input) { this.input input; this.pos 0; } public ListToken tokenize() { ListToken tokens new ArrayList(); while (pos input.length()) { char c input.charAt(pos); if (Character.isWhitespace(c)) { pos; continue; } if (Character.isLetter(c)) tokens.add(readIdentOrKeyword()); else if (Character.isDigit(c)) tokens.add(readNumber()); else tokens.add(readOperator()); } tokens.add(new Token(EOF, )); return tokens; } private Token readIdentOrKeyword() { int start pos; while (pos input.length() Character.isLetterOrDigit(input.charAt(pos))) pos; String word input.substring(start, pos); String type KEYWORDS.contains(word) ? word.toUpperCase() : IDENT; return new Token(type, word); } private Token readNumber() { int start pos; while (pos input.length() Character.isDigit(input.charAt(pos))) pos; return new Token(NUMBER, input.substring(start, pos)); } private Token readOperator() { char c input.charAt(pos); // 处理两个字符的运算符比如 、! if (pos input.length() (c || c !) input.charAt(pos) ) return new Token(OP, c input.charAt(pos)); return new Token(OP, String.valueOf(c)); } } record Token(String type, String value) {}逻辑上这个代码做了三件事跳过空白、按首字符分流、统一输出 token 流。readIdentOrKeyword里先按“字母开头、字母数字后续”切词再查关键字集合而不是在读取过程中判断——这样关键字表的增删不影响状态转移逻辑。readNumber只收数字不收小数点实验里如果要支持浮点数就补一个input.charAt(pos) .的判断但要注意.单独出现时的二义性。readOperator做了最长匹配的简化版先取一个字符再看能不能和后面一个字符构成双字符运算符。参数说明里最值得调的是两个关键字表KEYWORDS和运算符分支。前者直接决定标识符/关键字划分后者决定和这种最长匹配能否正确切分。如果你的语言里还有三个字符的运算符比如**或-,需要在readOperator里多加一层前瞻判断否则切出来的 token 流会和语法分析器的期望对不上。2.3 报告必须写清楚的两张表token 种类表和 DFA 状态转换表词法实验报告最值钱的部分不是代码是两张表。第一张叫 token 种类表列出你支持的所有 token 类型、每种的正则表达式、以及对应示例。第二张叫 DFA 状态转换表行是状态、列是输入字符类别、格子里是下一状态并标出哪些状态是接受状态。这两张表一出来评阅的人能直接看出你的词法分析器覆盖了哪些输入、在哪个字符上会拒绝输入。token 类型正则描述示例对应状态IDENT字母开头的字母数字串count, iS1接受NUMBER数字串1024S2接受KEYWORDIDENT 落入关键字表if, elseS1 后查表OP_EQabS3-S4接受OP_ASSIGNa1S3接受写这张表时有个常见误区把关键字也当成单独状态去画。实际上关键字可以先全部走 IDENT 状态在接受后查表归类这样状态数少一半也符合教材里“关键字是保留字”的处理方式。状态转换表则要画出非接受状态到接受状态的路径还要画一条出错状态——任何一个输入字符在当前状态没有对应转移就进出错状态报告里要说明你的分析器对非法字符是直接抛异常还是跳过。3. 语法分析实验递归下降和 LR 的选型以及报告怎么论证你的选择3.1 递归下降对左递归敏感一个最小例子的调用结构语法分析实验是编译原理报告里最容易拉开档次的环节。多数人遇到的第一个分叉路口是手写递归下降还是用工具或手写表驱动做 LR 分析。我的看法是如果实验只要求覆盖一个迷你语言的表达式和语句递归下降是最稳的——它的分析逻辑就是文法产生式的直接映射报错位置天然精确调试时能顺着调用栈定位到具体非终结符。但递归下降有一个硬条件文法必须去左递归。比如expr - expr term | term这条产生式如果直接写成parseExpr()内部先调用parseExpr()就会无限递归直到栈溢出。解决方法是先消除左递归改成expr - term { term }这种形式代码里对应的是parseTerm()加while循环。public class RecursiveDescentParser { private final Lexer lexer; private Token lookahead; public void parse() throws ParseException { lookahead lexer.tokenize().get(0); expr(); expect(EOF); } private void expr() throws ParseException { // 文法expr - term { (|-) term } term(); while (lookahead.type().equals(OP) (lookahead.value().equals() || lookahead.value().equals(-))) { match(OP); term(); } } private void term() throws ParseException { // 文法term - factor { (*|/) factor } factor(); while (lookahead.type().equals(OP) (lookahead.value().equals(*) || lookahead.value().equals(/))) { match(OP); factor(); } } private void factor() throws ParseException { if (lookahead.type().equals(NUMBER)) { match(NUMBER); } else if (lookahead.value().equals(()) { match(OP); expr(); match(OP); // 对应右括号 } else { throw new ParseException(Unexpected token: lookahead); } } }这段代码的调用链是expr - term - factor - expr括号产生右递归while循环消化左递归带来的同级运算符。参数上最值得调的是lookahead的管理方式——我在factor里连match内部前移lookahead的那个动作都写出来了为的是说清楚一个原则每调用一次match才消费一个 token绝不跳 token。语法分析器最常见的 bug 就是某个分支多读了一个 token后面所有判断全部错位。3.2 LR 分析表驱动移进-归约冲突的判定参数如果你的实验要求覆盖更大文法或者明确要求用 LR 分析那就不能靠手写递归得做分析表。SLR(1) 是动手做表驱动的常见折中它比 LR(0) 多一步 follow 集的判断能处理一部分移进-归约冲突又不像 LR(1) 那样需要构建大量状态。表驱动的核心代码反而是最简单的难的是表怎么生成——实验里通常是手算再用代码查表。public class LRDriver { private final int[][] actionTable; // 状态 x 终结符 - 动作编码 private final int[][] gotoTable; // 状态 x 非终结符 - 下一状态 private final DequeInteger stateStack new ArrayDeque(); private final DequeToken symStack new ArrayDeque(); public void drive(ListToken tokens) { stateStack.push(0); int ip 0; while (true) { int state stateStack.peek(); Token a tokens.get(ip); int action actionTable[state][a.type().hashCode() % ACTION_COLUMNS]; if (action SHIFT) { stateStack.push(gotoTable[state][a.type().hashCode() % ACTION_COLUMNS]); symStack.push(a); ip; } else if (action REDUCE) { int ruleLen getRuleLength(action); for (int i 0; i ruleLen; i) { stateStack.pop(); symStack.pop(); } int prevState stateStack.peek(); stateStack.push(gotoTable[prevState][getLhsNonterminal(action)]); } else if (action ACCEPT) { break; } else { throw new ParseException(Syntax error at token: a); } } } }这里我用了a.type().hashCode() % ACTION_COLUMNS做列索引是一个简化写法实验报告里不能这么交——它会有哈希碰撞风险正确做法是给每个终结符编一个整数编号action 表直接用二维数组按编号索引。这个代码骨架真正想让读者看到的是LR 驱动器本身不包含任何文法知识文法全在 action 表和 goto 表里所以报告的写作重点应当是表怎么算出来的而不是驱动器怎么写的。SLR(1) 构造的详细步骤在教材里有报告里至少要有项目集规范族的部分截图或手算表格并把 follow 集冲突的处理单独写一段。3.3 报告里要把“为什么不用另一套方案”写明白语法分析实验报告里最容易被忽视的是选型论证。常见的写法是“本实验采用递归下降分析法”然后开始贴代码——跳过了“为什么”。评阅人想看到的是对比你的文法有几条产生式、是否左递归、优先级怎么体现、错误恢复要做到什么程度。如果这些是选择递归下降的理由就一条条写如果选了 LR则要解释为什么自顶向下方法处理不了这个文法。我一般会在报告里画一个两列表格左列是“选用方案的优势与牺牲”右列是“被放弃方案在哪个环节不合适”。比如递归下降的牺牲是文法必须改写、不支持左递归LR 表驱动的牺牲是状态数大、手工构造容易出错、报错信息不如递归下降精确。这样写三句话就能让评阅人看出你理解了两个方案的边界而不是只背了概念。4. 符号表实验作用域、重定义与错误恢复报告里这些细节不能省4.1 符号表结构选型哈希桶加作用域链符号表是编译原理实验里最容易被做成“一个 HashMap”的模块。如果你只需要存变量名和类型那确实一个 HashMap 够了但只要语言里有嵌套作用域、有函数、有结构体就必须考虑两层结构一层是当前作用域的符号表一层是作用域间的链式指向。遇到重名变量时内层屏蔽外层查表从当前作用域往父作用域逐层找。class SymbolTable { private final MapString, Symbol symbols new HashMap(); private final SymbolTable parent; // null 表示全局作用域 SymbolTable(SymbolTable parent) { this.parent parent; } Symbol lookup(String name) { SymbolTable scope this; while (scope ! null) { Symbol s scope.symbols.get(name); if (s ! null) return s; scope scope.parent; } return null; } void define(String name, Symbol sym) { if (symbols.containsKey(name)) { throw new SemanticException(duplicate declaration: name); } symbols.put(name, sym); } Symbol lookupCurrent(String name) { return symbols.get(name); } }lookup和define的分工是这段代码的关键。lookup走完整条作用域链解决“能不能用这个变量”的问题define只查当前层解决“当前作用域里是否重复声明”的问题。两者分开后实验报告里描述语义规则会非常干净声明查当前层、引用查全链。常见的坑是有人把define也写成链式查找导致内层变量名和外层重名时内层声明直接报“重复定义”这在 C 系语言里是错判。4.2 作用域出入栈的时机声明、语句块和函数体符号表的另一个核心问题是“什么时候创建新作用域、什么时候销毁”。这听起来简单实做起来容易玄学for 循环体算不算一个作用域函数参数列表和函数体是不是同一个作用域if 的 then 分支和 else 分支是共用还是各建一个这些决定权在语言设计说明书里不在符号表代码里但实验报告必须明确写出来。我的建议是做一个作用域栈进入一对花括号就push一个新表离开就pop。函数声明呢参数先进函数作用域函数体内部再建一个子作用域挂在参数表下面这样参数在函数体内可见、但函数体内声明的变量不会污染参数表。class ScopeManager { private final DequeSymbolTable scopes new ArrayDeque(); void enterScope() { scopes.push(new SymbolTable(scopes.peek())); // 父作用域是栈顶 } void exitScope() { scopes.pop(); } Symbol lookUp(String name) { // 从栈顶一直向下找栈顶是当前作用域 for (SymbolTable s : scopes) { Symbol sym s.lookupCurrent(name); if (sym ! null) return sym; } // 栈底是全局作用域 return scopes.peekLast().lookupCurrent(name); } }这个栈式管理配合链式表是教科书上“最近嵌套作用域规则”的直接实现。for (SymbolTable s : scopes)的遍历顺序是从栈顶到栈底正好符合从内层向外层查找的顺序。写报告时建议拿一段样例程序手动画出每一步的栈内容变化进入函数压一层、进入语句块压一层、变量查找到第几层命中、离开语句块弹一层。这张图比任何文字描述都有说服力。4.3 报告里要附错误恢复的行为样例符号表实验报告里还有一个高频失分点只展示正常工作路径不展示错误路径。语义分析的价值恰恰体现在错误处理上——重复定义要报错、未声明标识符要报错、类型不匹配要报错。但报错还分两种风格遇到第一个错就停还是恢复后继续检查后面的代码。实验报告里我建议写明你采用的策略。我的习惯是实现“错误恢复”遇到未声明标识符时往当前作用域打一个占位符号让后续分析继续跑最后统一汇报错误列表。这样一次实验能暴露更多问题报告里也能贴上“一条输入产生多条错误”的输出截图。这比严格终止的实现更能展示语义分析器是完整构造出来的而不是只处理了课本上的正确用例。5. 编译原理实验报告避坑指南五条具体到代码的踩坑记录5.1 现象报告贴了整段代码但没有任何 token 流的中间输出很多词法实验报告交了整整 300 行代码唯一证明程序“活过”的证据是最后一句“经测试程序运行正确”。评阅人看不到分析过程只能按代码量给基础分。原因作者把程序正确性和可读性划了等号以为代码跑通就完成了报告。解决词法和语法分析实验都必须在报告中贴中间产物。词法贴 token 流语法贴分析树或推导过程。我给词法实验加过一行调试输出System.out.println(tokens);跑一个表达式就直接得到[NUMBER(3), OP(*), IDENT(x)]这样的输出。报告里放一次真实输入对应的一次真实输出比十张截图都有力。5.2 现象递归下降分析器在左递归文法上死循环或栈溢出做语法分析实验选了递归下降却直接把教材里的左递归产生式抄进代码运行时要么StackOverflowError要么程序卡死没输出。原因不理解递归下降是自顶向下方法左递归会让parseExpr()无限调用自己。解决动手之前先把文法改写掉。expr - expr term | term改成expr - term { term }循环代替递归。报告里要把改前和改后的产生式都贴出来简述“左递归改右递归或循环”的理由。这个处理本身就是语法分析实验的重要考点写了是加分项不写会被当成“碰巧跑通”。5.3 现象符号表只插入不弹出内层变量污染外层作用域符号表实验常见的翻车是函数里定义了一个局部变量int i函数结束后全局再查i居然能查到。原因作用域栈只压不弹或者只在exitScope里把栈顶置空没有真正移除。解决给ScopeManager.exitScope()写一个计数日志每exitScope一次就打印当前栈深。实验报告里贴这段日志展示进入函数栈深从 1 变 2、离开函数从 2 变 1评阅人能直接看到作用域是被正确释放的。我遇到过一种隐蔽情况enterScope 和 exitScope 的数量在 if 分支里不对等因为某个分支提前 return 了导致栈深错乱。修复方式是统一在finally块里调用退出或者在主循环里保证成对调用。5.4 现象测试集全是合法程序错误恢复路径从未被触发这是实验报告里最普遍的问题。词法分析器测了“能认出的”没测“认不出的”语义分析器测了所有正确程序没测重复声明和未声明变量。原因写测试用例时下意识只写正确输入因为“错的跑了也不知道对不对”。解决每类错误造一个最小用例。词法造一个含符号的输入、语法造一个缺右括号的表达式、语义造一个重复声明。把这些用例的输出也贴进报告并注明“第 3 行报告了错误但分析继续执行到了第 7 行”以此证明错误恢复机制生效。这个测试设计习惯能让报告从“作业”升到“工程验证”的层次。5.5 现象报告把算法描述写成名词解释没有和你的实现对应有些报告花一整页解释什么是 DFA、什么是 LR(0) 项目集然后实现代码只有两段二者没有任何对应关系。评阅人看完的感觉是“这人抄了概念却没理解概念在他的代码里长什么样”。原因把实验报告当成课程论文写以为概念解释越多越显学术。解决每个概念引入后必须紧接一行“在本实验中对应什么”。比如解释完 DFA写“本实验状态 0 是开始状态状态 1 接受标识符图 1 是自动生成的状态转换图”。概念是为实现服务的不能悬空。写报告时如果发现自己说不清某个概念在代码里的位置大概率是代码本身也没有真正实现这个概念趁早回头改代码。6. 实验跑通之后的验证技巧trace 开关与三组最小测试程序“跑通”不等于“做对”编译原理实验尤其如此。我给自己的实验代码统一加过一个TRACE环境变量开关打开后每个分析步骤打印一行状态信息关上后什么也不打。这个开关让调试和验收变成同一个动作也让报告里的截图有了统一的输出格式。public class Trace { public static final boolean ON System.getenv(TRACE) ! null; public static void log(String fmt, Object... args) { if (ON) System.out.printf([TRACE] fmt %n, args); } }用法很简单在Lexer.nextToken()里打 “consume char’x’, state2”在递归下降的expr()入口打 “enter expr, lookaheadNUMBER”在ScopeManager.enterScope()打 “push scope, depth3”。跑一个带嵌套函数和重复声明的输入trace 输出就完整呈现了词法到语法到语义的整条链路。评阅者如果看到这样一份报告第一反应是“这个人真的把整个流程跑通了”这个印象比任何自夸都值钱。三组最小测试是我在交付前固定跑的三遍。第一组是合法程序覆盖所有 token、所有产生式分支、两层以上嵌套作用域第二组是单点错误集每个用例只制造一个错误验证错误定位是否精确第三组是连环错误集在同一条输入里放多个错误验证错误恢复能否定位到真正的第二个错误而不是被第一个错误带偏。第三组最考验实现质量如果错误恢复是“遇到错误直接跳到文件结尾”那第二个错误永远报不出来。我在一次语义分析实验里就栽在第三组。测试输入第一行有未声明变量第二行有重复声明我的恢复策略是打占位符、继续分析但占位符插错了作用域导致第二行的重复声明被误判成“上一行的变量又声明了一次”。后来把占位符改为只在当前作用域插入并在 trace 里打印插入位置才定位到问题。现在每写完一个实验模块我都会先用第三组测试冲一遍再写报告因为报告里的错误恢复截图必须来自真实修复后的运行结果不能拿一张带着 bug 的输出去交差。这套做法不一定能让你一夜之间成为编译器大佬但它保证了一件事你写进实验报告里的每句话都有对应的代码和输出可追溯。编译原理实验报告到最后拼的不是文笔是“说得清、可复现”。希望这次的经验能帮你在下个实验里少走几步弯路。本文还有配套的精品资源点击获取
简介一份针对东北大学秦皇岛分校编译原理课程的实验报告围绕PL/0语言词法分析程序的设计与实现展开适合计算机专业本科生或正在学习编译原理的开发者用于理解词法分析的核心流程。资源包内共1个doc文档压缩包大小122KB内容完整、结构清晰。文档以C语言在Windows环境下实现包含实验目的、实验环境、实验代码及运行思路详细给出了isLetter、isDigit、isP、isJ等字符分类函数以及单词识别、关键词表ktt匹配、非法字符检测等功能模块的实现方法。读者可借助完整源代码与注释示例掌握从读取源程序、逐字符扫描到输出单词二元组的完整流程也可作为编译原理课程实验报告的参考样式同时为理解语法分析、语义分析等后续环节打下基础。资源当前已有97人学习。1. 编译原理实验报告不是课后心得它记录的是三次关键设计决策“编译原理实验报告”这几个字在多数人眼里就是期末一份交差文档代码跑通、截图贴上、写几句“通过本次实验我掌握了”就算完。但真拿高分、真能把编译原理变成自己能力的报告记的不是过程而是决策。词法分析用正则还是手写状态机、语法分析选递归下降还是 LR、符号表怎么管作用域——这三个选择背后各自有代价报告真正要写清楚的是“你为什么这么选、代价在哪、翻车了怎么修”。这决定了给分的人能不能看出你理解了编译器不是黑匣子。适合谁适合正在写编译原理实验、并且不想让报告停留在“代码附录心得”层面的人。这篇直接按词法、语法、符号表三段展开附 Java 代码骨架、测试方法和避坑记录。2. 词法分析实验从正则到 DFA代码骨架与报告里的两张表2.1 为什么词法实验绕不开 DFA 最小化词法分析最简单粗暴的思路是拿正则表达式逐个匹配 token 类型比如遇到字母开头就一直读直到读到一个既不是字母也不是数字的字符再回头查关键字表。这个做法在实验一够用但它有一个理论短板一旦语言的关键字和运算符多起来逐类匹配的时间会线性膨胀而且匹配顺序写错就会误判。王生原那本教材的第三章整个就是在讲怎么从正则表达式构造 NFA、再确定化为 DFA、最后做最小化——目的就是让词法分析器在“读一个字符、换一个状态”的固定开销下工作。实验里我一般建议做到 DFA 这一层不是因为它比手写匹配快多少而是因为它逼你把 token 种类、状态转移、接受状态这三样东西显式建模。只要这三样是显式的报告里就能画状态转换表、能算状态数、能讨论最小化前后差多少。如果只写一个while循环加if判断状态是隐式的报告根本没有可分析的对象。2.2 用 Java 写一个最小可用的词法分析器骨架用 Java 写词法实验的人最多我给出一个能跑通基础运算表达式的最小骨架。它识别标识符、整数、运算符和关键字核心是把“读字符切 token”和“查关键字表”分离成两步。import java.util.*; public class Lexer { // 关键字表识别为标识符后二次归类 private static final SetString KEYWORDS Set.of(if, else, while, return); private final String input; private int pos; public Lexer(String input) { this.input input; this.pos 0; } public ListToken tokenize() { ListToken tokens new ArrayList(); while (pos input.length()) { char c input.charAt(pos); if (Character.isWhitespace(c)) { pos; continue; } if (Character.isLetter(c)) tokens.add(readIdentOrKeyword()); else if (Character.isDigit(c)) tokens.add(readNumber()); else tokens.add(readOperator()); } tokens.add(new Token(EOF, )); return tokens; } private Token readIdentOrKeyword() { int start pos; while (pos input.length() Character.isLetterOrDigit(input.charAt(pos))) pos; String word input.substring(start, pos); String type KEYWORDS.contains(word) ? word.toUpperCase() : IDENT; return new Token(type, word); } private Token readNumber() { int start pos; while (pos input.length() Character.isDigit(input.charAt(pos))) pos; return new Token(NUMBER, input.substring(start, pos)); } private Token readOperator() { char c input.charAt(pos); // 处理两个字符的运算符比如 、! if (pos input.length() (c || c !) input.charAt(pos) ) return new Token(OP, c input.charAt(pos)); return new Token(OP, String.valueOf(c)); } } record Token(String type, String value) {}逻辑上这个代码做了三件事跳过空白、按首字符分流、统一输出 token 流。readIdentOrKeyword里先按“字母开头、字母数字后续”切词再查关键字集合而不是在读取过程中判断——这样关键字表的增删不影响状态转移逻辑。readNumber只收数字不收小数点实验里如果要支持浮点数就补一个input.charAt(pos) .的判断但要注意.单独出现时的二义性。readOperator做了最长匹配的简化版先取一个字符再看能不能和后面一个字符构成双字符运算符。参数说明里最值得调的是两个关键字表KEYWORDS和运算符分支。前者直接决定标识符/关键字划分后者决定和这种最长匹配能否正确切分。如果你的语言里还有三个字符的运算符比如**或-,需要在readOperator里多加一层前瞻判断否则切出来的 token 流会和语法分析器的期望对不上。2.3 报告必须写清楚的两张表token 种类表和 DFA 状态转换表词法实验报告最值钱的部分不是代码是两张表。第一张叫 token 种类表列出你支持的所有 token 类型、每种的正则表达式、以及对应示例。第二张叫 DFA 状态转换表行是状态、列是输入字符类别、格子里是下一状态并标出哪些状态是接受状态。这两张表一出来评阅的人能直接看出你的词法分析器覆盖了哪些输入、在哪个字符上会拒绝输入。token 类型正则描述示例对应状态IDENT字母开头的字母数字串count, iS1接受NUMBER数字串1024S2接受KEYWORDIDENT 落入关键字表if, elseS1 后查表OP_EQabS3-S4接受OP_ASSIGNa1S3接受写这张表时有个常见误区把关键字也当成单独状态去画。实际上关键字可以先全部走 IDENT 状态在接受后查表归类这样状态数少一半也符合教材里“关键字是保留字”的处理方式。状态转换表则要画出非接受状态到接受状态的路径还要画一条出错状态——任何一个输入字符在当前状态没有对应转移就进出错状态报告里要说明你的分析器对非法字符是直接抛异常还是跳过。3. 语法分析实验递归下降和 LR 的选型以及报告怎么论证你的选择3.1 递归下降对左递归敏感一个最小例子的调用结构语法分析实验是编译原理报告里最容易拉开档次的环节。多数人遇到的第一个分叉路口是手写递归下降还是用工具或手写表驱动做 LR 分析。我的看法是如果实验只要求覆盖一个迷你语言的表达式和语句递归下降是最稳的——它的分析逻辑就是文法产生式的直接映射报错位置天然精确调试时能顺着调用栈定位到具体非终结符。但递归下降有一个硬条件文法必须去左递归。比如expr - expr term | term这条产生式如果直接写成parseExpr()内部先调用parseExpr()就会无限递归直到栈溢出。解决方法是先消除左递归改成expr - term { term }这种形式代码里对应的是parseTerm()加while循环。public class RecursiveDescentParser { private final Lexer lexer; private Token lookahead; public void parse() throws ParseException { lookahead lexer.tokenize().get(0); expr(); expect(EOF); } private void expr() throws ParseException { // 文法expr - term { (|-) term } term(); while (lookahead.type().equals(OP) (lookahead.value().equals() || lookahead.value().equals(-))) { match(OP); term(); } } private void term() throws ParseException { // 文法term - factor { (*|/) factor } factor(); while (lookahead.type().equals(OP) (lookahead.value().equals(*) || lookahead.value().equals(/))) { match(OP); factor(); } } private void factor() throws ParseException { if (lookahead.type().equals(NUMBER)) { match(NUMBER); } else if (lookahead.value().equals(()) { match(OP); expr(); match(OP); // 对应右括号 } else { throw new ParseException(Unexpected token: lookahead); } } }这段代码的调用链是expr - term - factor - expr括号产生右递归while循环消化左递归带来的同级运算符。参数上最值得调的是lookahead的管理方式——我在factor里连match内部前移lookahead的那个动作都写出来了为的是说清楚一个原则每调用一次match才消费一个 token绝不跳 token。语法分析器最常见的 bug 就是某个分支多读了一个 token后面所有判断全部错位。3.2 LR 分析表驱动移进-归约冲突的判定参数如果你的实验要求覆盖更大文法或者明确要求用 LR 分析那就不能靠手写递归得做分析表。SLR(1) 是动手做表驱动的常见折中它比 LR(0) 多一步 follow 集的判断能处理一部分移进-归约冲突又不像 LR(1) 那样需要构建大量状态。表驱动的核心代码反而是最简单的难的是表怎么生成——实验里通常是手算再用代码查表。public class LRDriver { private final int[][] actionTable; // 状态 x 终结符 - 动作编码 private final int[][] gotoTable; // 状态 x 非终结符 - 下一状态 private final DequeInteger stateStack new ArrayDeque(); private final DequeToken symStack new ArrayDeque(); public void drive(ListToken tokens) { stateStack.push(0); int ip 0; while (true) { int state stateStack.peek(); Token a tokens.get(ip); int action actionTable[state][a.type().hashCode() % ACTION_COLUMNS]; if (action SHIFT) { stateStack.push(gotoTable[state][a.type().hashCode() % ACTION_COLUMNS]); symStack.push(a); ip; } else if (action REDUCE) { int ruleLen getRuleLength(action); for (int i 0; i ruleLen; i) { stateStack.pop(); symStack.pop(); } int prevState stateStack.peek(); stateStack.push(gotoTable[prevState][getLhsNonterminal(action)]); } else if (action ACCEPT) { break; } else { throw new ParseException(Syntax error at token: a); } } } }这里我用了a.type().hashCode() % ACTION_COLUMNS做列索引是一个简化写法实验报告里不能这么交——它会有哈希碰撞风险正确做法是给每个终结符编一个整数编号action 表直接用二维数组按编号索引。这个代码骨架真正想让读者看到的是LR 驱动器本身不包含任何文法知识文法全在 action 表和 goto 表里所以报告的写作重点应当是表怎么算出来的而不是驱动器怎么写的。SLR(1) 构造的详细步骤在教材里有报告里至少要有项目集规范族的部分截图或手算表格并把 follow 集冲突的处理单独写一段。3.3 报告里要把“为什么不用另一套方案”写明白语法分析实验报告里最容易被忽视的是选型论证。常见的写法是“本实验采用递归下降分析法”然后开始贴代码——跳过了“为什么”。评阅人想看到的是对比你的文法有几条产生式、是否左递归、优先级怎么体现、错误恢复要做到什么程度。如果这些是选择递归下降的理由就一条条写如果选了 LR则要解释为什么自顶向下方法处理不了这个文法。我一般会在报告里画一个两列表格左列是“选用方案的优势与牺牲”右列是“被放弃方案在哪个环节不合适”。比如递归下降的牺牲是文法必须改写、不支持左递归LR 表驱动的牺牲是状态数大、手工构造容易出错、报错信息不如递归下降精确。这样写三句话就能让评阅人看出你理解了两个方案的边界而不是只背了概念。4. 符号表实验作用域、重定义与错误恢复报告里这些细节不能省4.1 符号表结构选型哈希桶加作用域链符号表是编译原理实验里最容易被做成“一个 HashMap”的模块。如果你只需要存变量名和类型那确实一个 HashMap 够了但只要语言里有嵌套作用域、有函数、有结构体就必须考虑两层结构一层是当前作用域的符号表一层是作用域间的链式指向。遇到重名变量时内层屏蔽外层查表从当前作用域往父作用域逐层找。class SymbolTable { private final MapString, Symbol symbols new HashMap(); private final SymbolTable parent; // null 表示全局作用域 SymbolTable(SymbolTable parent) { this.parent parent; } Symbol lookup(String name) { SymbolTable scope this; while (scope ! null) { Symbol s scope.symbols.get(name); if (s ! null) return s; scope scope.parent; } return null; } void define(String name, Symbol sym) { if (symbols.containsKey(name)) { throw new SemanticException(duplicate declaration: name); } symbols.put(name, sym); } Symbol lookupCurrent(String name) { return symbols.get(name); } }lookup和define的分工是这段代码的关键。lookup走完整条作用域链解决“能不能用这个变量”的问题define只查当前层解决“当前作用域里是否重复声明”的问题。两者分开后实验报告里描述语义规则会非常干净声明查当前层、引用查全链。常见的坑是有人把define也写成链式查找导致内层变量名和外层重名时内层声明直接报“重复定义”这在 C 系语言里是错判。4.2 作用域出入栈的时机声明、语句块和函数体符号表的另一个核心问题是“什么时候创建新作用域、什么时候销毁”。这听起来简单实做起来容易玄学for 循环体算不算一个作用域函数参数列表和函数体是不是同一个作用域if 的 then 分支和 else 分支是共用还是各建一个这些决定权在语言设计说明书里不在符号表代码里但实验报告必须明确写出来。我的建议是做一个作用域栈进入一对花括号就push一个新表离开就pop。函数声明呢参数先进函数作用域函数体内部再建一个子作用域挂在参数表下面这样参数在函数体内可见、但函数体内声明的变量不会污染参数表。class ScopeManager { private final DequeSymbolTable scopes new ArrayDeque(); void enterScope() { scopes.push(new SymbolTable(scopes.peek())); // 父作用域是栈顶 } void exitScope() { scopes.pop(); } Symbol lookUp(String name) { // 从栈顶一直向下找栈顶是当前作用域 for (SymbolTable s : scopes) { Symbol sym s.lookupCurrent(name); if (sym ! null) return sym; } // 栈底是全局作用域 return scopes.peekLast().lookupCurrent(name); } }这个栈式管理配合链式表是教科书上“最近嵌套作用域规则”的直接实现。for (SymbolTable s : scopes)的遍历顺序是从栈顶到栈底正好符合从内层向外层查找的顺序。写报告时建议拿一段样例程序手动画出每一步的栈内容变化进入函数压一层、进入语句块压一层、变量查找到第几层命中、离开语句块弹一层。这张图比任何文字描述都有说服力。4.3 报告里要附错误恢复的行为样例符号表实验报告里还有一个高频失分点只展示正常工作路径不展示错误路径。语义分析的价值恰恰体现在错误处理上——重复定义要报错、未声明标识符要报错、类型不匹配要报错。但报错还分两种风格遇到第一个错就停还是恢复后继续检查后面的代码。实验报告里我建议写明你采用的策略。我的习惯是实现“错误恢复”遇到未声明标识符时往当前作用域打一个占位符号让后续分析继续跑最后统一汇报错误列表。这样一次实验能暴露更多问题报告里也能贴上“一条输入产生多条错误”的输出截图。这比严格终止的实现更能展示语义分析器是完整构造出来的而不是只处理了课本上的正确用例。5. 编译原理实验报告避坑指南五条具体到代码的踩坑记录5.1 现象报告贴了整段代码但没有任何 token 流的中间输出很多词法实验报告交了整整 300 行代码唯一证明程序“活过”的证据是最后一句“经测试程序运行正确”。评阅人看不到分析过程只能按代码量给基础分。原因作者把程序正确性和可读性划了等号以为代码跑通就完成了报告。解决词法和语法分析实验都必须在报告中贴中间产物。词法贴 token 流语法贴分析树或推导过程。我给词法实验加过一行调试输出System.out.println(tokens);跑一个表达式就直接得到[NUMBER(3), OP(*), IDENT(x)]这样的输出。报告里放一次真实输入对应的一次真实输出比十张截图都有力。5.2 现象递归下降分析器在左递归文法上死循环或栈溢出做语法分析实验选了递归下降却直接把教材里的左递归产生式抄进代码运行时要么StackOverflowError要么程序卡死没输出。原因不理解递归下降是自顶向下方法左递归会让parseExpr()无限调用自己。解决动手之前先把文法改写掉。expr - expr term | term改成expr - term { term }循环代替递归。报告里要把改前和改后的产生式都贴出来简述“左递归改右递归或循环”的理由。这个处理本身就是语法分析实验的重要考点写了是加分项不写会被当成“碰巧跑通”。5.3 现象符号表只插入不弹出内层变量污染外层作用域符号表实验常见的翻车是函数里定义了一个局部变量int i函数结束后全局再查i居然能查到。原因作用域栈只压不弹或者只在exitScope里把栈顶置空没有真正移除。解决给ScopeManager.exitScope()写一个计数日志每exitScope一次就打印当前栈深。实验报告里贴这段日志展示进入函数栈深从 1 变 2、离开函数从 2 变 1评阅人能直接看到作用域是被正确释放的。我遇到过一种隐蔽情况enterScope 和 exitScope 的数量在 if 分支里不对等因为某个分支提前 return 了导致栈深错乱。修复方式是统一在finally块里调用退出或者在主循环里保证成对调用。5.4 现象测试集全是合法程序错误恢复路径从未被触发这是实验报告里最普遍的问题。词法分析器测了“能认出的”没测“认不出的”语义分析器测了所有正确程序没测重复声明和未声明变量。原因写测试用例时下意识只写正确输入因为“错的跑了也不知道对不对”。解决每类错误造一个最小用例。词法造一个含符号的输入、语法造一个缺右括号的表达式、语义造一个重复声明。把这些用例的输出也贴进报告并注明“第 3 行报告了错误但分析继续执行到了第 7 行”以此证明错误恢复机制生效。这个测试设计习惯能让报告从“作业”升到“工程验证”的层次。5.5 现象报告把算法描述写成名词解释没有和你的实现对应有些报告花一整页解释什么是 DFA、什么是 LR(0) 项目集然后实现代码只有两段二者没有任何对应关系。评阅人看完的感觉是“这人抄了概念却没理解概念在他的代码里长什么样”。原因把实验报告当成课程论文写以为概念解释越多越显学术。解决每个概念引入后必须紧接一行“在本实验中对应什么”。比如解释完 DFA写“本实验状态 0 是开始状态状态 1 接受标识符图 1 是自动生成的状态转换图”。概念是为实现服务的不能悬空。写报告时如果发现自己说不清某个概念在代码里的位置大概率是代码本身也没有真正实现这个概念趁早回头改代码。6. 实验跑通之后的验证技巧trace 开关与三组最小测试程序“跑通”不等于“做对”编译原理实验尤其如此。我给自己的实验代码统一加过一个TRACE环境变量开关打开后每个分析步骤打印一行状态信息关上后什么也不打。这个开关让调试和验收变成同一个动作也让报告里的截图有了统一的输出格式。public class Trace { public static final boolean ON System.getenv(TRACE) ! null; public static void log(String fmt, Object... args) { if (ON) System.out.printf([TRACE] fmt %n, args); } }用法很简单在Lexer.nextToken()里打 “consume char’x’, state2”在递归下降的expr()入口打 “enter expr, lookaheadNUMBER”在ScopeManager.enterScope()打 “push scope, depth3”。跑一个带嵌套函数和重复声明的输入trace 输出就完整呈现了词法到语法到语义的整条链路。评阅者如果看到这样一份报告第一反应是“这个人真的把整个流程跑通了”这个印象比任何自夸都值钱。三组最小测试是我在交付前固定跑的三遍。第一组是合法程序覆盖所有 token、所有产生式分支、两层以上嵌套作用域第二组是单点错误集每个用例只制造一个错误验证错误定位是否精确第三组是连环错误集在同一条输入里放多个错误验证错误恢复能否定位到真正的第二个错误而不是被第一个错误带偏。第三组最考验实现质量如果错误恢复是“遇到错误直接跳到文件结尾”那第二个错误永远报不出来。我在一次语义分析实验里就栽在第三组。测试输入第一行有未声明变量第二行有重复声明我的恢复策略是打占位符、继续分析但占位符插错了作用域导致第二行的重复声明被误判成“上一行的变量又声明了一次”。后来把占位符改为只在当前作用域插入并在 trace 里打印插入位置才定位到问题。现在每写完一个实验模块我都会先用第三组测试冲一遍再写报告因为报告里的错误恢复截图必须来自真实修复后的运行结果不能拿一张带着 bug 的输出去交差。这套做法不一定能让你一夜之间成为编译器大佬但它保证了一件事你写进实验报告里的每句话都有对应的代码和输出可追溯。编译原理实验报告到最后拼的不是文笔是“说得清、可复现”。希望这次的经验能帮你在下个实验里少走几步弯路。本文还有配套的精品资源点击获取
