简介面向编译原理课程实验的一份完整参考材料适合华东理工大学相关专业学生也适合高校开设PL/0编译器实验的初学者对照学习。资源围绕词法分析与语法分析两条主线提供两份实验报告及词法分析源程序能够帮助读者理解单词识别流程、标识符与关键字区分、数值转换、语法分析任务设计等核心环节。压缩包共5个文件包含2份doc实验报告、2个cpp源文件及1个pl测试用例整体仅274KB轻量便于快速下载。报告按实验步骤展开从编写PL/0测试用例到PL0Compiler读入并输出带序号、字符串、类型和值的单词流再到借鉴C语言标识符规则将PL/0扩展为PL/1测试程序均配有数据变化与输出结果分析源文件支持直接运行和断点调试方便复现实验现象。当前已有721人学习下载适合作为课程实验的借鉴模板与排错参考。1. 实验整体设计与思路拆解1.1 编译原理实验在学什么很多同学第一次听到“词法分析”和“语法分析”这两个词容易觉得它们是很抽象、很高深的东西。其实把它放到编译器的全局里看就是做“翻译”的前两步先读懂源代码的单词再读懂源代码的句子结构。说得更直白一点词法分析负责把一串字符切成一个个有意义的“词”Token语法分析负责把这些“词”按语法规则组成一棵“树”语法树后续的语义分析和代码生成都是在这棵树上做文章。这次华东理工大学的实验报告核心任务就是把这两个模块做成一个完整的可运行程序。我在做这个实验的时候最大的体会是它能跑通和它能正确跑完所有测试用例是两码事。前者只要功能写出来就行后者需要你把各种边界情况都考虑到。所以这个实验并不只是练手它真正逼着你去理解状态转换图、上下文无关文法、FIRST/FOLLOW集这些概念而不是背概念应付考试。1.2 整体架构选型手写还是工具生成现在业界做词法和语法分析几乎都是直接用工具比如Flex、Bison、ANTLR、JavaCC。但课程实验不同学校要考察的是你对底层原理的掌握程度大部分情况下要求手写实现。我在做这个实验时选择的是用C手写词法分析器再用递归下降法手写语法分析器。理由很简单手写词法分析能让你真正理解状态转换图手写递归下降能让你直观感受文法规则是如何映射成代码的。另一种常见路线是用Yacc/Bison生成语法分析器但那样的话你只是在写文法规则内部的栈操作、移进归约逻辑都是工具帮你封装好的对初学编译原理的人来说反而是个黑盒。所以如果你不是被老师明确允许用工具我还是建议老老实实手写一遍。代码量并不大但写完后你会觉得编译器再也不是魔法。这里我补一句实验报告里不需要写“我为什么选C”但你需要把模块划分清楚。我自己的设计是三个文件Lexer.h/cpp负责词法分析Parser.h/cpp负责语法分析main.cpp负责文件读取和结果输出。词法分析和语法分析之间通过一个Token结构体衔接语法分析器内部持有一个Token流逐个消费。2. 词法分析从字符流到Token流2.1 词法规则定义先定Category再写Regex写词法分析器之前第一件事不是写代码而是把你要识别的Token类别列全。我以这次实验为例把类别表整理如下Token类别示例说明关键字int, return, if, else, while需要单独建表匹配标识符foo, _bar, a1字母或下划线开头后跟字母数字下划线整数常量0, 42, 007支持十进制是否需要八进制十六进制看实验要求运算符, -, *, /, , , , 单字符和多字符要区分分隔符( ) { } , ;常用的界符错误字符, #不在规则中必须报错而不是静默跳过列完表之后再为每个类别画出对应的正则表达式。比如标识符的正则是[A-Za-z_][A-Za-z0-9_]*整数的正则是[0-9]。有了正则表达式你再把它转成NFA、DFA才有着力点。这里有个很重要的细节关键字和标识符的区分。如果你把“int”也当作普通标识符去匹配那么你就需要在识别出标识符之后查一下关键字表。常见的做法是用一个unordered_setstring存关键字识别完标识符后查表如果命中就改为关键字Token。还有一点容易忽略的是大小写敏感性C/C大小写敏感但如果你写的是一门不敏感的语言正则表达式要加上大小写分支这些都是规则定义阶段就该定下来的。2.2 状态转换图的代码化有了正则表达式接下来是把它变成程序。最直观的方式就是画状态转换图然后把状态转换图写成switch语句或if-else链。拿标识符识别来说状态转换图大概是状态0读入字母或下划线进入状态1状态1读入字母、数字或下划线留在状态1其余情况结束识别。转换成代码就是这么一段std::string curLexeme; int state 0; while (!isEOF()) { char ch peekChar(); if (state 0) { if (isAlpha(ch) || ch _) { curLexeme getChar(); state 1; } else { // 不是标识符的起始字符交给其他状态处理 break; } } else if (state 1) { if (isAlpha(ch) || isDigit(ch) || ch _) { curLexeme getChar(); } else { break; // token结束 } } } // 回退多余字符返回token写这段代码时有几个坑要提醒最后一个字符是分隔符时它不属于当前token必须把它“放回”输入流。我习惯用一个pushbackChar()函数配合一个unreadBuffer实现避免一个字符读进来就丢掉的尴尬。不要用std::string做“逐字符拼接”然后频繁返回效率低但不影响实验更关键的是不要忘了在token结束处清空curLexeme否则下次拼接会把上一次的残留带进来。这个bug很隐蔽我调了将近一小时才发现。对于两个字符的运算符比如、、需要做一个“最长匹配”的判断。读完之后看一眼下一个字符是不是如果是就拼成不是就把多读的一个字符退回去。2.3 符号表存什么、什么时候存热搜词里提到了“编译原理符号表”确实符号表是词法分析阶段绕不开的话题。但课程实验里符号表应该做到多深取决于要求。我做的版本是在词法分析阶段只负责登记标识符不解析作用域。每个标识符Token出现时查字典如果不在就插入在就返回已有ID。我用的数据结构是std::unordered_mapstd::string, SymbolInfo其中SymbolInfo至少包含struct SymbolInfo { std::string name; // 标识符名 int id; // 符号表编号从1开始 TokenType type; // 这里先用UNKNOWN等语法/语义阶段再填 };用ID替代名字来和Token关联好处是后续语法分析时比较标识符是否相等只需比较整数比字符串比较快很多而且实验报告中也能体现出“编译器的中间表示是可以一层层简化的”。很多同学会问符号表不是在语法分析和语义分析阶段才用吗是的但词法分析阶段把标识符登记造册正好能给后续阶段提供基础。注意事项如果你在做递归下降语法分析而你的语言允许变量在声明之后使用那么符号表的作用域问题会非常大。但词法阶段不要管作用域只管“登记”。作用域是语法/语义分析阶段的事情。如果一个实验能跑通但表格字段不完整那多半是你对符号表的定位理解偏了。3. 语法分析从Token流到语法树3.1 文法设计与左递归消除语法分析的第一步是设计文法也就是BNF。以常见的类C语言子集为例表达式部分可以写成expr - term (( | -) term)* term - factor ((* | /) factor)* factor - ( expr ) | NUMBER | IDENT这段文法有个特点它是左递归的。如果直接用递归下降来写expr会无限调用自己。我一开始没有意识到这个问题写出来的代码一运行就栈溢出。后来老老实实做了文法改写把左递归转成右递归expr - term expr_tail expr_tail - term expr_tail | - term expr_tail | ε term - factor term_tail term_tail - * factor term_tail | / factor term_tail | ε factor - ( expr ) | NUMBER | IDENT改写之后每个非终结符对应一个解析函数逻辑清晰parseExpr()调parseTerm()再调parseExprTail()如此一层层套下去。左递归消除这个点实验报告里一定要写清楚你原来写了什么文法发现什么问题怎么改的改完效果如何——这一整套思路比给一大段代码更有价值。如果课程要求LL(1)分析还需要算FIRST和FOLLOW集。我这次也手算了一份然后和程序里自动生成的结果对了一遍。手算时容易漏掉FOLLOW集里逗号或分号的情况因为这类符号虽然只出现在语句层面不直接出现在表达式文法里但它会影响外层语法规则。3.2 FIRST集与FOLLOW集计算实战算FIRST集没什么技巧就是按规则一条条推。拿上面那个文法我手算的结果是这样FIRST(expr) FIRST(term) FIRST(factor) { (, NUMBER, IDENT }FIRST(expr_tail) { , -, ε }FIRST(term_tail) { *, /, ε }FOLLOW集稍微麻烦一点需要注意ε产生式带来的影响。我算出来FOLLOW(expr) { ), $ }$表示输入结束符FOLLOW(expr_tail) FOLLOW(expr) { ), $ }FOLLOW(term) FIRST(expr_tail) - {ε} ∪ FOLLOW(expr_tail) { , -, ), $ }FOLLOW(term_tail) FOLLOW(term) { , -, ), $ }FOLLOW(factor) FIRST(term_tail) - {ε} ∪ FOLLOW(term_tail) { *, /, , -, ), $ }我建议用一个递归函数来自动算但手算一遍能帮你发现很多“我以为我懂了其实没懂”的地方。比如第一次算的时候我漏了FOLLOW(term)会从expr_tail的FOLLOW传递过来因为term可能在expr_tail的末尾。这个传递关系是新手最容易算错的地方。顺便给大家一个自查方法把算好的FIRST和FOLLOW填入预测分析表检查每个表项是否唯一。如果一个格子出现两个产生式说明文法不是LL(1)需要进一步提取左因子。我们实验的语言比较小一般不会出现这个问题但考试和面试很喜欢考这一点。3.3 递归下降解析器的实现细节我没有用LR分析器生成器而是手写递归下降因为代码直观出错好排查。核心思路是给每个非终结符写一个函数函数之间互相调用。下面是我parseExprTail的一段代码骨架void Parser::parseExprTail() { if (matchAndAdvance(TokenType::PLUS)) { parseTerm(); parseExprTail(); } else if (matchAndAdvance(TokenType::MINUS)) { parseTerm(); parseExprTail(); } // else 什么都不做相当于 ε 产生式 }注意这里用递归而不是循环是为了和书上的文法对应得更好。你完全可以用while循环代替尾递归实际编译器里也是循环更高效。如果是实验代码我建议先按递归写跑通了再改成循环这样出了问题容易对照文法调试。匹配函数matchAndAdvance很简单看一下当前Token是不是预期类型如果是就消费掉不是就返回false。但有一个地方要小心matchAndAdvance在判断失败时不能消费Token否则后面做错误恢复时会丢失关键Token。3.4 错误恢复与友好报错实验报告里如果不要求容错处理很多同学就只做“解析到错误就停”。但我强烈建议花一点时间做最基础的错误恢复报错时打印出期望的Token和实际拿到的Token然后跳过若干个Token尝试继续解析后续内容。这样做有两个好处调试自己的语法规则时你能一次看到多个错误而不是暴露一个就停下。实验报告里可以多写一节“错误恢复策略”这是加分项。具体的跳过策略我采用的是“同步符号法”当出错时跳过所有Token直到遇到分号或右花括号这种明确的语句边界。这个想法很朴素但对表达式和简单语句来说足够了。伪代码如下void Parser::synchronize() { while (!currentTokenIs(TokenType::SEMICOLON) !currentTokenIs(TokenType::RBRACE) !isEOF()) { advance(); } if (currentTokenIs(TokenType::SEMICOLON)) { advance(); // 把分号消费掉 } }3.5 抽象语法树的构建与输出语法分析除了“判断输入是否符合文法”还要产出结果。实验里常见的要求是输出语法树很多同学在这里把语法树和概念上的“推导树”Parse Tree搞混。推导树是把每个产生式都展开成节点非常庞大冗余而抽象语法树AST只保留运算符和操作数括号、逗号这类辅助符号都会被去掉。我实现的AST节点类型大致有ExprNode表达式节点内部存std::vectorExprNode* children方便二叉树转多叉树。StmtNode语句节点比如IntDeclStmt、AssignStmt、IfStmt。ProgramNode整体根节点管理所有语句。输出的时候我先用缩进的方式打印ASTProgram IntDecl name: a init: 1 AssignStmt name: b expr: BinaryExpr op: left: a right: 2这样的输出既方便你肉眼验证语法树对不对也方便在实验报告中贴图。如果你还想更直观可以用Graphviz的dot格式输出配合可视化工具看到一棵真正的树。但是注意别把顺序写反先验证AST内容再谈可视化否则一旦文法写偏可视化出来也是一堆错乱。4. 常见问题与排查技巧实录4.1 Token类型与AST结构的类型安全这是我踩过最大的坑。我在做语法分析时Token的lexeme和AST节点的nodeType用的是裸enum结果在不同模块间传递时经常出现“拿错类型”的问题。比如我在factor里判断Token是否NUMBER却在else分支里默认它是ID一旦遇到括号表达式就直接崩了。后来我把Token提高了一层用std::variant或者C的多态体系去设计虽然代码写得慢了一点但编译期就能排查出很多问题。建议你在动手写语法分析之前先把Token和AST节点这两个类型的结构设计好不要在写的过程中反复改数据结构否则改一处卡十处。4.2 多字符运算符的识别顺序运算符识别有一个经典问题和谁先匹配。如果你在词法分析时用的是逐个字符判断遇到就读进去紧接着读那应该没问题。但如果你用“按字符类别切分”的写法比如把所有运算符按单词长度从长到短排序再匹配那就要小心被先切成和两个Token。我的建议很简单在状态转换图里处理读取之后必须peek下一个字符如果是就组成否则把字符退回。这样既符合最大匹配原则也不会产生歧义。另外注释符号//和/*也要在词法分析阶段剔除不要在语法分析阶段才处理否则你很难写词法规则。4.3 常见错误速查表现象可能原因解决思路程序栈溢出文法左递归未消除递归下降无限嵌套重写文法将左递归改为右递归或循环标识符永远识别不了起始字符判断漏掉下划线检查isAlpha关键字和标识符混在一起识别完标识符后没有查关键字表在词法分析末尾增加关键字表匹配操作遇到却被切成两个token运算符识别没有做最长匹配用peek查后继字符或按长度排序匹配语法分析首个Token就报错词法分析多读或漏读一个字符检查pushback机制确保多余的字符被退回流中FIRST/FOLLOW集手算和程序不一致漏掉了ε的传递或FOLLOW的传递规则再检查包含空产生式的规则常见于表达式尾部符号4.4 测试用例的构造思路最后说说测试。编程实验里很多同学喜欢拿一个大文件压测一报错就不知道错在哪。建议反过来先写“最小通过用例”和“最小失败用例”。我的测试列表大概是这样的单个标识符a;单个数字1;简单运算a 1;括号优先级(a 1) * 2;嵌套表达式((a));多个语句int a 1; a a 2;错误用例a ;、1 2缺分号、(a 1;括号不匹配每加一个用例跑一遍把通过的用例和失败的用例都记录在实验报告里。这样老师一眼就能看出你考虑了很多边界情况而不是只拿一个例程糊弄过去。5. 调试心得与实验环境提示5.1 我用的开发环境和工具链这次实验我是在Visual Studio Code里写的编译器用的是MinGW-w64。C标准选的是C17因为std::optional和std::variant在这种模块间传递数据时特别好用。如果你用的是Linux可以直接用g没有任何区别。编译命令可以写在Makefile里也可以直接命令行执行。我习惯把词法分析和语法分析分别编译成独立的可执行文件这样调试词法阶段时不用管语法逻辑。等到两个模块都单测通过了再合成一个完整的程序这种“自底向上拼装”的方式在编译原理这种偏底层的实验里特别省时间。5.2 分阶段调试不要等写完了再跑我特别想强调一个习惯词法分析和语法分析是两件事分开来调试。词法分析完成后可以先做一个“用词法分析器批量打印Token流”的中间步骤肉眼验证一遍Token的类型、行号、列号、词素都是对的再进入语法分析。很多同学把两个阶段写在一个函数里Token一生成就交给语法分析器一旦出错很难说是词法部分写错了还是语法部分写错了。分开调试可以帮你把错误范围迅速缩小也能在你写实验报告时分别展示“词法输出示例”和“语法输出示例”从呈现效果上也更规整。5.3 实验报告里值得写的“反思点”从我自己的经验来看实验报告如果只贴代码和截图评价一般不会太高。但如果能写清楚你遇到了什么问题、怎么定位的、最后怎么解决的含金量会明显不同。我这次在报告里写了三个反思点左递归消除前后的代码对比。词法分析中pushback机制的设计以及它如何影响后续运算符匹配。AST输出格式的选择为什么用缩进文本而不是嵌套括号。写这些点的时候不需要长篇大论每个点三五行总结就好。关键是让读者感受到你真的理解了自己的代码而不只是“照抄调试通过”。按照我个人经验这个实验里80%的时间都花在排查各种奇奇怪怪的边界问题上反而是剩余20%的时间在写正式的代码逻辑。如果你遇到“怎么跑都有一两个用例过不去”的情况别硬扛着看代码用纸笔画一下状态转换图或递归调用栈往往比盯着屏幕更有效。本文还有配套的精品资源点击获取