本文章主要记录了2025秋季学期北航编译原理课程实验上机期中期末的回忆题目~

题目均由本人回忆记录，可能与原题稍有偏差，但大体思路一致

期中题目

1. 新增 elif 文法：

具体新增文法如下：

1
2
3
Stmt -> 'if' '(' Cond ')'Stmt 
		{ 'elif' '(' Cond ')' Stmt } 1.有elif 2.无elif 3.有多个elif
		[ 'else' Stmt ] // 1.有else 2.无else

解题思路：

  1. 词法分析阶段识别 elif 为一个保留关键字，建立 ELIFTK。
  2. 语法分析阶段，对于 IfStmt 语法结构，新增一个 list 用来装 elif，里面每一个单元涵盖 Cond 和 Stmt。在 toString 的时候，先对 if 语句进行 toString，然后看有没有 elif，如果有的话就仿照 if 的 toString 操作去写就可以。最后对 else 进行处理。

2. 新增 functionDef 文法：

具体新增文法如下：

1
2
FuncDef → FuncType Ident '(' [FuncFParams] ')' Block 
		| FuncType Ident '(' [FuncFParams] ')' ; // 新增

解题思路：

  1. 词法分析不用改

  2. 语法分析阶段，首先新增一个新的语法节点，然后将 FuncDef 设置为接口，原来的 FuncDef 和新增的都实现这个接口。两个 FuncDef 的不同之处就是一个是 Block 一个是 ；

    在识别有没有 FuncFParams 的时候，在看后面 Token 是不是 { 的时候，还要看是不是 ;，如果是的话说明没有 FuncFParams 并且缺少右小括号。然后在检查完右小括号后，根据下一个 Token 是 { 还是 ; 决定返回的语法节点类型。

期末题目

1. 新增 cin 文法：

具体新增文法规则如下：

1
语句 Stmt → 'cin' '>>' LVal; // 新增 cin 文法，错误类型为i，h

其功能等价于：LVal = getint() ，即读入一个 int 类型的数，然后存储在 LVal 中。

错误类型为 i：缺少分号，h：LVal 为 const 不可赋值。

解题思路：

  1. 在词法分析阶段解析 cin 为 CINTK，解析 >> 为 SHR。
  2. 在语法分析阶段，为 cin 文法新增 AST 节点类型 CinStmt，其内部只需存储一个 LVal 即可。在 parseStmt 的时候，如果当前 token 是 CINTK，则调用 parseCinStmt 方法。parseCinStmt 方法：先跳过 cin 和 >> ，然后调用 parseLVal 返回 LVal 用于构建 CinStmt。最后检查有没有分号，没有报 i 错误。
  3. 在语义分析阶段，在 checkStmt 中，如果是 CinStmt 则调用 checkCinStmt。该方法内部先 getLVal 拿到左值，然后去符号表里拿到 varSymbol，如果 varSymbol.isConst 是真，则报 h 错误。然后再调用 checkLVal 方法去检查 LVal（若 LVal 未定义则在 checkLVal 中报错，不在 checkCinStmt 里报错）。
  4. 在中间代码生成阶段，如果是 CinStmt，则调用 buildCinStmt 方法。该方法首先 new CallInst 去调用 getint 库函数，然后得到其 Value，然后 getLVal 得到 LVal，用 getLValPtr 得到 LVal 的指针，最后 new StoreInst 将 getint Value 存储到 LVal 指针处即可。
  5. 后端代码生成不用改。

2. 新增 -> 文法：

具体新增文法规则如下：

1
2
3
4
乘除模表达式 MulExp → UnaryExp | MulExp ('*' | '/' | '%' | '->') UnaryExp // 新增 '->' 运算
'->' 运算解释：
a -> b = a + (a + 1) + (a + 2) + ....... + b
保证 a <= b

解题思路：

  1. 在词法分析阶段解析 -> 为 LEFTTORIGHTTK。
  2. 在语法分析阶段，在解析 MulExp 的时候，如果遇到 (‘*’ | ‘/‘ | ‘%’ | ‘->’) 运算符，就添加语法成分，最后正常返回 MulExp 语法节点。这里只要添加一个 else if 特判是不是 LEFTTOTIGHTTK 就可以。
  3. 在语义分析阶段，不用改。
  4. 在中间代码生成阶段，如果是 LEFTTORIGHTTK，则调用 buildLRTK 方法。该方法有两种实现方式：
    • 第一种比较简单，利用等差数列求和公式，只需要计算出 ((a + b) * (b - a + 1)) / 2 即可。计算方法就根据计算顺序生成对应的计算语句，然后返回最后的计算结果 Token 即可。
    • 第二种方法是利用循环来计算。可以写一个 for 循环，循环开始为 a，终止为 b，循环体内的语句就是累加当前值，最后返回累加值即可。方法为创建三个 BasicBlock，第一个为条件块，第二个为语句块，第三个为结束块。首先创建临时变量 i，并赋初值为 a，然后跳转到条件块，生成条件为 i <= b，若满足条件则跳转到语句块，不满足则跳转到结束块。然后跳转到语句块，累加 i 的值，然后无条件跳转到条件块。最后将当前块移至结束块即可。
  5. 后端代码生成不用改。

3. 代码优化

直接提交课下代码优化的版本进行评测，有两个测试点。按照测试点的 cycle 数进行排名给分。

一般来说课下的代码优化能过，那么课上这两个点就能过。

然后还需要提交代码优化前后中间代码和目标代码的 txt 版本，别忘了交

4. 问答题

针对给出的示例代码提出很多问题，要结合代码进行文字解释。重点都是 mips 代码生成的问题。

有印象的问题是：

  • 在 mips 函数传参的时候，前四个参数要通过 $a0 - $a3 传递，第五个参数是如何传递的？
  • 还考了一个跟函数有关的，具体忘了

总结

同学们好好复习，期中比较简单，期末要上点小强度。

一般来说，期末只需要改 llvm 中端就行了，如果 llvm 不新增指令，那么 mips 完全不用改。为了预防 llvm 有新增指令，需要提前准备一些方案，我能想到的 llvm 新增指令就是新增一些运算指令类型，比如新增异或、与运算、或运算之类的。这些就仿照加减法正常做就可以。

可以打印纸质资料带进去，建议先把预测到的问题问一下 AI ，让 AI 生成详细的更改指导，最后打印出来带进考场看。

有问题可加微信：zhaojiyuan0721