Cminusf编译原理课设全解析：从词法分析到中间代码生成

简介重庆大学计算机学院编译原理课程实验项目合集聚焦Cminusf语言的完整编译流程面向正在学习编译原理、需要完成词法/语法/语义分析与中间代码生成实验的本科生或自学者。资源包含实验一至实验三的代码实现与调试记录可帮助读者对照真实项目理解编译器各阶段的设计思路与排错方法。压缩包共361个文件以out、sy、tk、json输出文件及h/cpp源码为主并含txt说明、py脚本等整体大小1.52MB目录结构便于按实验逐项检索。包内代码覆盖词法分析、语法分析、语义分析和中间代码生成关键环节调试记录详述了实验中的常见问题与分析过程另有说明文件与主目录Compilation_principle_ex-main方便快速搭建环境并运行测试。目前已有78人学习下载适合作为编译原理课程实验的参考资料与实现模板。1. 编译原理课设为什么总在Cminusf上翻车这门实验到底在训练什么很多人第一次拿到Cminusf实验时直观感受是“这语言也太小了”——没有类、没有结构体、连布尔类型都要自己模拟跟平时写的C或Java比起来像玩具。但真正动手做词法分析、语法分析、语义分析到中间代码生成才发现这个“玩具”精准地切中了编译原理最核心的难点正规式与状态机、上下文无关文法与递归下降、符号表与类型检查、三地址码与临时变量管理。重庆大学计算机学院这个编译原理课程实验集合把实验一词法分析、实验二语法分析、实验三语义分析与中间代码生成串成一条线最终产出的是能跑通Cminusf源码并输出四元式的完整前端。适合正在做课设的学生、想补编译原理短板的开发者以及那些只背过概念、没真正写过一遍语法树遍历的人——这门实验不做完一遍你对编译器前端的理解永远是黑匣子。2. 词法分析从Cminusf到Token流的完整实现2.1 先看懂Cminusf的词法规则保留字、标识符和数字的三个判断点Cminusf是C语言子集关键词大概有if、else、while、return、int、float、void这几个外加运算符和分隔符。词法分析器要做的第一件事不是写代码而是把语言的词法规则画成一张状态图。我最常犯的错是一上来就写大循环等发现被拆成和再回头改状态转换早就乱成一团。正确的顺序是先列出所有终结符的类别再定义每种类别的匹配规则最后设计一个getNextToken()函数。三个容易判断错的地方第一标识符必须以字母或下划线开头后面可以跟数字、字母、下划线但如果保留字表没先查if会被当成标识符第二数字分整数和浮点Cminusf要求浮点数必须带小数点3.合法3.0合法但3后面直接跟.5是非法输入这需要在状态机里加一个“小数点后必须跟数字”的转移条件第三注释以/*开始以*/结束但这里的坑在于注释里不能嵌套遇到/*必须一直读到*/中间出现/*也不能进入嵌套状态。把这三条理清词法规则表就完成了80%。2.2 手写词法分析器的代码结构一个循环加一张状态表我用Java实现词法分析器核心是一个Scanner类内部维护input字符串、position指针、currentLine行号。每次调用nextToken()先跳过空白和注释再根据当前字符决定进入哪个分支。下面这个简化版本完整展示了状态机和最大匹配的逻辑public Token nextToken() throws SyntaxException { // 跳过空白与注释 while (position input.length()) { char c input.charAt(position); if (Character.isWhitespace(c)) { position; } else if (c / position 1 input.length() input.charAt(position 1) *) { int startLine currentLine; position 2; while (position 1 input.length() !(input.charAt(position) * input.charAt(position 1) /)) { if (input.charAt(position) \n) { currentLine; } position; } if (position 1 input.length()) { throw new SyntaxException(Unterminated comment at line startLine); } position 2; // 跳过结束的 */ } else { break; } } if (position input.length()) { return new Token(TokenType.EOF, , currentLine); } int start position; char first input.charAt(position); // 标识符或保留字 if (Character.isLetter(first) || first _) { while (position input.length()) { char ch input.charAt(position); if (Character.isLetterOrDigit(ch) || ch _) { position; } else { break; } } String word input.substring(start, position); TokenType type reservedMap.getOrDefault(word, TokenType.IDENTIFIER); return new Token(type, word, currentLine); } // 数字整数或浮点数 if (Character.isDigit(first) || (first . position 1 input.length() Character.isDigit(input.charAt(position 1)))) { boolean isFloat false; while (position input.length()) { char ch input.charAt(position); if (Character.isDigit(ch)) { position; } else if (ch . !isFloat) { isFloat true; position; // 小数点后必须跟数字 if (position input.length() || !Character.isDigit(input.charAt(position))) { throw new SyntaxException(Malformed float at line currentLine); } } else { break; } } String num input.substring(start, position); return new Token(isFloat ? TokenType.FLOAT : TokenType.INTEGER, num, currentLine); } // 运算符和分隔符 String twoChar position 1 input.length() ? input.substring(position, position 2) : ; if (.equals(twoChar) || .equals(twoChar) || .equals(twoChar) || !.equals(twoChar) || .equals(twoChar) || ||.equals(twoChar)) { position 2; return new Token(tokenTypeMap.get(twoChar), twoChar, currentLine); } String oneChar input.substring(position, position 1); if (tokenTypeMap.containsKey(oneChar)) { position; return new Token(tokenTypeMap.get(oneChar), oneChar, currentLine); } throw new SyntaxException(Unexpected character oneChar at line currentLine); }这个实现的关键在于“最大匹配”——处理必须先看两位字符再看一位字符否则会把拆成和。注释扫描单独用一个while循环因为注释内容不需要产生Token但跳过的行号要累加否则后续语法分析的报错行号会全错。数字状态机的判断条件里我特意让小数点开头的.5也能被识别这是很多同学忽略的边界情况Cminusf虽然少见但语法规则没有禁止。保留字和标识符统一处理在结束处查reservedMap这样省去了单独建一张DFA的麻烦。2.3 词法分析调试记录最大匹配和错误恢复怎么处理调试记录里最容易出问题的不是常规代码而是特殊输入。我遇到过一段测试用例只有一行/* comment */结果我的词法分析器抛出了“unexpected character”而不是正常返回EOF原因是注释结束后position已经越过字符串末尾但外层循环没有正确判断。后来我规定nextToken()开头先处理空白和注释处理完后必须if (position input.length()) return EOF。另一个血的教训是错误恢复——很多同学遇到非法字符直接抛出异常导致整个分析停止。课程实验通常要求词法分析报告错误后继续分析因此我在抛出SyntaxException之前会将position然后返回一个ERROR类型的Token让调用方能收集所有词法错误。但这里有一个边界如果连续出现非法字符不能死循环所以nextToken()内部要保证每次调用至少消费一个字符。把这个逻辑写清楚词法分析这关就稳了。3. 语法分析递归下降还是LR(1)Cminusf实验怎么选3.1 语法分析的两种路线为什么课程实验推荐递归下降Cminusf的语法规模适合手写递归下降但很多教材强调LR(1)更“正规”导致初学者陷入抉择。我的建议是除非实验允许使用Yacc/Bison否则一律手写递归下降。理由有三条。第一LR(1)需要构造Action表和Goto表表驱动代码虽然机械但一旦文法有冲突排错成本极高而递归下降的每个函数对应一个非终结符报错位置能直接定位到函数调用栈。第二Cminusf的表达式优先级关系在递归下降里可以用分层函数清晰表达expression - additive_expr - term - factor每层只做一件事别人看你的代码也容易给分。第三课程实验的测试用例通常包含语法错误递归下降可以精确知道当前期望的终结符报错信息能具体到“期望遇到;实际遇到)”。3.2 用递归下降实现Cminusf表达式的优先级与左递归消除递归下降最大的坑是左递归。Cminusf的产生式如expr - expr term如果照抄成parseExpr()先调用parseExpr()直接无限递归。我的做法是转成循环用parseExpr()先解析一个term然后while循环里看下一个Token是不是或-是就继续解析下一个term并构造二元运算节点。下面是一个简化版表达式解析代码覆盖加减乘除和括号public ASTNode parseExpression() throws SyntaxException { // 先解析乘除优先级更高的项然后处理加减 ASTNode node parseTerm(); while (currentToken.is(TokenType.PLUS) || currentToken.is(TokenType.MINUS)) { Token op currentToken; nextToken(); ASTNode right parseTerm(); node new BinaryOpNode(op, node, right); } return node; } public ASTNode parseTerm() throws SyntaxException { ASTNode node parseFactor(); while (currentToken.is(TokenType.MUL) || currentToken.is(TokenType.DIV)) { Token op currentToken; nextToken(); ASTNode right parseFactor(); node new BinaryOpNode(op, node, right); } return node; } public ASTNode parseFactor() throws SyntaxException { if (currentToken.is(TokenType.LPAREN)) { nextToken(); ASTNode node parseExpression(); expect(TokenType.RPAREN); return node; } if (currentToken.is(TokenType.IDENTIFIER) || currentToken.is(TokenType.INTEGER) || currentToken.is(TokenType.FLOAT)) { Token token currentToken; nextToken(); return new LeafNode(token); } if (currentToken.is(TokenType.MINUS)) { // 一元负号单独处理 Token op currentToken; nextToken(); ASTNode operand parseFactor(); return new UnaryNode(op, operand); } throw new SyntaxException(Unexpected token currentToken in factor); }这段代码的层级关系就是文法的优先级映射parseExpression处理加减parseTerm处理乘除parseFactor处理括号、常量标识符和一元负号。注意一元负号的位置我放在parseFactor里这样-a*b会先被解析成(-a)*b而不是-(a*b)这符合C语言的语义。如果你的实验要求一元负号优先级最高放在factor层完全正确。另外expect()函数负责检查当前Token是否是指定类型不是就抛异常这是递归下降里最常见的错误处理方式。实际项目中你还需要处理数组下标[expr]、函数调用ident(args)等但它们不影响这层结构。3.3 语法分析的错误定位如何让报错信息真正可用很多同学的语法分析器能跑通合法程序一遇到非法程序就崩溃在未知异常报错信息只有一行“NullPointerException”。这背后是缺少全局的错误捕获与恢复机制。我的方案是在递归下降的每个入口函数顶层捕获SyntaxException记录当前Token的行号和期望类型然后执行errorRecovery()——跳过Token直到遇到分号或}等同步标记。这样一来一个错误不会导致一连串假错误。另一个细节是嵌套恢复的顺序当parseFactor失败时不能直接吞掉Token因为上层parseTerm的循环可能还在等待运算符。我一般让parseAbstractError()先返回一个特殊的ErrorNode上层看到ErrorNode就不会再继续试图解析右操作数直接把它当作一个整体返回。调试记录里我把所有语法错误测试用例分成三类缺少分号、括号不匹配、表达式运算符缺失分别验证错误信息中的行号和期望Token是否正确。这三类能覆盖大部分课设测试点。4. 语义分析与中间代码生成把语法树变成四元式4.1 符号表与作用域语义分析的第一道关卡语义分析的前提是符号表。Cminusf只有全局变量、函数参数和局部变量作用域规则是函数内部可以引用函数参数和本函数内声明的局部变量但不能引用其他函数的局部变量。我实现的是链式符号表一个全局MapString, Symbol加上一个ListMapString, Symbol作为作用域栈。进入函数体时压入新层退出时弹出。查找符号时从栈顶向下查这样局部变量可以遮蔽全局变量。这里有个容易忽略的点函数名本身也是一种符号且和变量名放在同一命名空间时如果实验要求区分你需要用SymbolKindFUNCTION / VARIABLE / PARAMETER来标记否则遇到int foo; int foo(){}会报冲突但实际C语言允许它们分别存在。更多课程实验不要求这么细致但符号表的结构决定了后面类型检查的难易。4.2 类型检查与中间代码生成四元式的设计要点Cminusf要求int和float混用时要进行隐式类型转换比如int float会生成一个int转float的四元式。许多同学在语法分析阶段直接生成中间代码跳过了语义检查这会导致int x; x abc;这种错误在运行期才暴露。正确流程是先遍历语法树做类型检查同时把常量折叠掉然后再生成四元式。四元式我用一个类表达public class Quad { public String op; // 操作码如 ADD, SUB, MUL, DIV, ASSIGN, GOTO, LABEL public String arg1; // 第一操作数 public String arg2; // 第二操作数 public String result; // 结果临时变量或目标标签 // 构造函数省略 }中间代码生成的常见做法是为每个表达式引入临时变量。例如a b * c会生成MUL b c t1 ADD a t1 t2类型检查通过后生成器需要知道每个AST节点的类型才能决定是否插入INT_TO_FLOAT四元式。我的实现里BinaryOpNode的inferType()会做子节点类型提升如果左操作数是int右操作数是float就会在生成MUL或ADD之前先在子表达式的结果上生成转换。语义分析和中间代码生成可以合并成一趟遍历但不建议合并成一步——因为中间代码生成需要知道每个符号的地址或临时变量编号这部分可以单独放在符号表里。4.3 调试记录从“通过”到“得分”的差距在哪我见过很多实验报告词法分析测试全过语法分析测试全过但到中间代码生成一环输出的四元式顺序错误、临时变量编号混乱、条件跳转的label名重复。根本原因是缺少对中间代码的“可读性”要求。课程实验的评分标准往往包含手工检查——老师会打开你生成的四元式文本看是不是规范。所以我在调试记录里特意总结了三个规范临时变量必须从t1开始递增不能跳过label必须按照L0、L1顺序编号且每个函数内部的label不能重复无条件跳转GOTO最好明确写出目标label不要使用相对跳转。另外if语句的中间代码生成容易产生多余label。Cminusf的if (cond) stmt else stmt正确的跳转结构应该是计算cond后以假跳转跳过then分支如果存在else在then分支末尾加一个无条件跳转跳过else分支。很多同学把条件取反放在生成的cond代码里导致变成时出错。我建议将所有比较运算符在中间代码层原样保留由跳转指令来决定条件真假。这样语义更清晰调试时也容易追踪边界。5. 避坑实录Cminusf实验里最常踩的五个坑5.1 现象词法分析把注释尾部的换行符吞了测试用例里有一段注释后紧跟下一行代码词法分析器返回的Token行号和预期不符导致语法分析报错指向错误行号。原因是我的注释跳过逻辑在遇到*/后立即返回但之前已经消费了换行符而行号累加逻辑放在注释循环内部。更隐蔽的问题是如果注释紧贴换行比如/*...*/\nint a;换行符被当成了注释的一部分。解决方法是在跳过注释的循环中只有当字符是\n时才增加行号且注释结束后的position停在*/的下一个字符这样换行符会在外层空白跳过逻辑中被处理行号不会重复累加。为了验证我把“注释中只有换行”“注释后紧跟着程序”这两类测试用例单独做成一个文件跑完对比每个Token行号的期望值。5.2 现象语法分析对一元负号产生移进/归约冲突用Yacc的同学在Bison里遇到expr: - expr | expr - expr时会出现移进归约冲突报错说“0 shift/reduce conflicts”。这不是Bison的错而是文法本身有歧义。解决方法是把一元负号的优先级声明为%left -之后再加一行%left UNARY_MINUS并在文法中用%prec UNARY_MINUS指定。但手写递归下降的同学会碰上另一个翻车点在parseFactor里遇到-时直接递归调用parseFactor结果-a-b被解析成-(a-b)因为内层parseFactor把后面的减号也消费了。正确做法是内层只解析一个基本因子常量、变量、括号表达式不能再次调用parseFactor。我最后用小括号隔离测试用例-a*b和-(a*b)分别验证这个坑才算填平。5.3 现象语义分析时数组下标类型检查漏掉隐式转换Cminusf允许数组下标是整数表达式但不允许浮点数。我的符号表里数组名有type: int[]或float[]下标表达式的inferType()返回int时才能通过。但实际测试用例中写了arr[i j]i和j是int没问题可arr[1.0]居然也过了——因为我在生成下标取址时忘了检查类型。原因是ArrayAccessNode的类型检查逻辑只验证了数组本身的类型没有递归检查下标表达式的结果类型。修复方式是在typeCheck()里先调用下标表达式的typeCheck()如果结果是FLOAT直接抛语义错误。这个坑提醒我语义分析不能只盯着符号表每个语法树的节点都必须有完整的类型传播。5.4 现象中间代码生成时临时变量重复使用导致值被覆盖a (b c) * (d e)生成的中间代码应该是先算t1 b c再算t2 d e最后t3 t1 * t2。但如果我在生成器里用一个全局计数器tempCounter每次生成一个临时变量就并返回t counter那么两个加法会得到t1和t2没问题。问题出在我对常量表达式做了折叠如果b1, c2我直接生成t1 3然后后续生成器还在用原来的t1计数导致同一个t1既被常量结果占用又被后来的乘法结果占用。解决方法是把常量折叠和临时变量分配分开折叠的结果直接写入四元式的arg1不再分配临时变量临时变量分配器严格递增。调试时我在所有四元式后面打印生成的临时变量列表一眼就发现了t1被重复定义。5.5 现象实验报告调试记录写成流水账得分上不去这个坑和代码无关但直接影响最终得分。老师的评分标准里明确写了“调试记录需要体现问题的定位过程”很多同学写的是“第3行出错修复后通过”这等于没说。我的做法是记录三个要素触发问题的测试用例输入、报错的完整输出含行号、根因分析哪段逻辑、哪个边界条件没考虑。每条调试记录控制在50字内的现象描述加100字左右的解决思路例如“对空文件调用nextToken()时返回了空指针——原因是最初的循环没有处理输入为空的边界——解决办法是在nextToken()开头加长度判断并直接返回EOF”。这种记录才能真正体现你的工作量也是答辩时帮你解释代码的最好材料。6. 让实验得分再往上走的三个验证技巧6.1 用最小用例集做回归测试很多同学的测试方法是把几个样例文件跑通就算完。我建议把测试用例拆分成“每个语法特性一个文件”void_function.cminus测试无返回值函数int_return.cminus测试整型返回float_expr.cminus测试浮点运算nested_if.cminus测试嵌套条件array_access.cminus测试数组读写。每个文件不超过10行好处是定位错误时能快速缩小到某几个特性。我自己维护了一个tests/目录配合一个run_all.py脚本每个用例的输出和期望输出做diff。这个习惯帮我至少避免了三次“修改A特性导致B特性回归”的翻车。6.2 把调试记录整理成“现象-原因-解决”表格实验报告中的调试记录部分如果只是代码时间线老师很难判断你有多深入。我一般把所有踩坑项整理成三列表格现象含输入输出截断、原因定位到具体函数和状态、解决代码改动和结果。表格的好处是老师扫一眼就能看到问题数量和覆盖面也方便答辩时自己回顾。另外在表格前面加一行说明“所有调试用例均已保存在tests/regression目录可复现”这比写十页废话更有说服力。6.3 中间代码的静态检查手工模拟执行一遍生成四元式后不要急着交差。我会选一个包含条件跳转和赋值语句的简单函数比如int f(int a) { if (a 0) return a; else return -a; }然后手工模拟四元式的执行顺序检查跳转目标是否正确、临时变量是否在正确位置被赋值。这个动作能发现很多只在动态运行时才暴露的问题比如条件跳转的label名拼写错误、return后面的临时变量没有生成赋值指令。我自己的经验是这种手工模拟虽然繁琐但比写一个解释器快得多而且能加深对中间代码控制流的理解。做完这一步把结论写进调试记录再配上“通过模拟执行验证了中间代码的正确性”这句话得分自然就上去了。最后说一个我的习惯每次跑完实验我会把四个阶段的中间产物——Token流、语法树、符号表、四元式——全部打印到文件里保留一份原始输出。这个习惯救了我很多次因为老师偶尔会抽查某个阶段输出而重新生成可能因为环境差异对不上。编译原理这门课最后的差距往往就体现在这些看似笨拙但可靠的细节上。希望帮到你。本文还有配套的精品资源点击获取