Featured image of post BUAA Compiler 上机
Compiler

BUAA Compiler 上机

祝期末顺利

2306 上机真题

期中考试

分为两道题。

T1

第一题为填空题，选择你的编译器语言类型：C、C++、Java。

坑点解析：C选项才是Java，而A选项才是C。

T2

第二题为新增文法，只考查词法分析、语法分析，以及这两个阶段的错误处理。

新增文法：函数声明。

原文法：

1
2

CompUnit → {Decl} {FuncDef} MainFuncDef
FuncDef → FuncType Ident '(' [FuncFParams] ')' Block

需要实现：

CompUnit → {Decl}{FuncDecl|FuncDef} MainFuncDef // 大致长这样，总之要区分FuncDecl和FuncDef

FuncDecl → FuncType Ident ‘(’ [FuncFParams] ‘)’ ；// i 错误

  1. 新建AST节点类型
  2. 修改CompUnit的parse方法
  3. 实现FuncDecl的parse方法，其中包含错误处理。

难点显然在第二步：修改CompUnit的parse方法。

因为FuncDecl和FuncDef的区分不是简简单单peek几个token就能实现的，一般考虑使用回溯。

期末考试

分为四道题。

T1

第一题为新增文法。

新增文法分为MIPS与非MIPS，请阅读对应栏目的题面。

MIPS生成赛道的题面：

需要实现：

乘除模表达式新增运算符：->

MulExp → UnaryExp | MulExp (’*’ | ‘/’ | ‘%’ | ‘->’) UnaryExp

其中a->b表示 a + (a+1) + (a+2) + …… +b，保证b>=a且均为整数。

如 3->3 = 3, 4->6= 15。

Stmt新增类型：

Stmt → ‘cin’ ‘»’ LVal; // i 错误

其语义完全等价于LVal = getint();

词法分析，新增三个token，并完成lexer。

语法分析则比较简单，cin语句的判别也只靠currentToken就能解决。

需要注意书写CinStmt的parse方法时要追加错误处理。

语义分析，重点是->的常量预计算，显然直接使用**(a+b)(b-a+1)/2**计算。

代码生成：

  • ->依旧使用(a+b)(b-a+1)/2即可。就这么一直new AluInstr。注意不要忘记减1和除2。
  • cin语句和assign语句更是基本一模一样，只是store的不是ExpIr，而是**new GetIntInstr()**而已。

整体做下来算是比较简单的一份题目了。

据说原题目是 函数重载和形参缺省值。因为太难 助教本人做不出而被否决。 // 经 or 未经

T2

第二题为竞速排序题。

提供一个样例点。共有三个测试点。

对优化给予超级强测！许多人在这一步被迫关掉大量优化。

但是不开优化时应该一般没有问题。 // 未经

T3

第三题为文件上传题。

针对第二题上传的编译器与题面给出的样例，生成针对该样例的四个txt文件，并打包为zip上传。

1

testfile_学号_姓名_优化前/后中间/目标代码

一定注意是四个文件。

如果未实现优化，可仅包含优化前中间/目标代码共2个txt文件。

T4

第四题为简答题。

给了一个巨长无比的测试程序。

复习算法时看到分治的快排，猛地回忆起来。

本题的程序应该是qsort的完整实现，当然外加了一些彰显优化的小巧思。

里面大致是my_rand函数，swap函数、partition函数、以及递归调用的q_sort函数。

首先在本地运行，然后观察你的MIPS，结合你的具体代码实现（可精确到文件名、方法、行数），回答下列四个问题。 下面是题目大致信息：

  • XXX函数共有五个参数，前四个通过$ax寄存器传递，那么第五个参数你是如何实现传递的？参数的值又是如何被获取的？

基础知识。callInstr的toMips()的基本问题，利用栈进行存储，讲一讲你fillParam与loadParam的逻辑就行。

  • XXX函数的MIPS代码中，$tx 临时寄存器在调用YYY函数的时候你是否保存？如果不保存，YYY函数可能会覆盖该临时寄存器，你是如何处理的？

我没有区分s和t，所以用到就保存了。

  • XXX函数中，存在多次对a[j]的访问。其中a是数组基地址保持不变，j则不断变化。讲一讲你如何利用a和j实现对a[j]所在地址的获取？

这道题a[j]的访问是在一个循环体里。所以如果实现循环展开，再结合公共子表达式，很可能只需对地址加加减减。不过我这个版本没有实现，所以循环体里的语句就是朴素的a + j«2。

  • 观察XXX函数和YYY函数对应生成的MIPS代码，你实现了哪些优化？还有哪些优化你可以实现？

这就得看题目本身了。里面有常数合并、常数传播、死代码删除等等。其实我没看出来太多。

这道题一般比较吃时间。不过下限低，真没时间了也没关系。 // 未经

特别情况：今年考试的markdown编辑页面自带保存备份，过几秒就会自动保存打断你一次，所以建议在本地写好再粘贴到希冀的编辑器。

备考策略

一般来说，增添新文法并不会耗费太多的时间，而且测试点中包含纯课下的点，所以不必过于紧张。

真出问题了大抵也是课下的，现场估计也修不出来。

提前30min到考场。调试设备，配置IDEA的JDK。

可以携带纸质资料。因此作业截止后才发现自己的bug的同学可以把diff打印出来带到考场，提前奋笔疾书。

可以把你新增文法的基本思路写一写，因为这和你自己的实现息息相关，是你独享的秘籍。预先想得全面一点也不至于考试的时候缺东少西，发生本地跑一下RE了再赶紧改诸如此类的事。

下面内容仅供参考。

文法新增一般思路

有关错误处理：

新增ErrorType，然后ErrorList.addError(new Error(type, line));

Operator型

这类题目几乎必考，处理起来也相对粗暴。

词法分析

TokenType新增token。

lexer：readchar是消耗当前的字符，所以预读时先看currentchar，再决定直接return还是继续readchar

语法分析

如果是一元运算符UnaryOp，一定要注意修改以下部分的parser的FIRST集判定：

  • UnaryExp判定函数调用，鉴定FuncRParams时 （其实这个可以无条件，因为没有分支）
  • UnaryExp区分UnaryOp UnaryExp与PrimaryExp时
  • Stmt在回溯前初步判别ExpStmt与AssignStmt时

如果是其他运算符，需要修改所在层级Exp是否继续while循环的判定。

语义分析

主要内容是常量预计算。

如果是一元运算符，

在UnaryExp最下面的compute方法中新增else if。

其他运算符在RecursionExp的compute方法中新增case。

代码生成

主要修改VisitorExp。

如果是一元运算符，找到generateUnaryExpUnaryIr，新增case即可。

其他运算符找对应的generate，把while循环中的

1

AluInstr aluInstr = new AluInstr(op.getToken().getValue(), irValue1, irValue2);

改成

1
2
3
4
5

if (op.getToken().getValue().equals("XXX")){
	XXXXX
} else {
	AluInstr aluInstr = new AluInstr(op.getToken().getValue(), irValue1, irValue2);
}

运算型IR构建技巧

加文法很方便的一点是，很多东西你都做好了、封装好了。除了全新的功能，基本上都可以尝试复用。

常量：new IrConstantInt(X)

拿到irValue（要注意VarSymbol的irValue是指针，其余的基本是值）：

最底层的irValue很少，要不然是IrConstant，要不然是函数def与变量decl时分配的irValue。

其余的，大多数都是Instr这种形式存在的irValue，不用依赖symbol。

如果真的没有上下文提供irValue，必须自己拿：

1
2
3
4
5
6

// 函数
FuncSymbol funcSymbol = (FuncSymbol) SymbolRecorder.getSymbol(identName);
IrFunction irFunction = (IrFunction) funcSymbol.getIrValue(); 
// 变量 LVal
IrValue irValue = generateLValIr(LVal lval, boolean beAssigned)；
// true为取址（要被赋值） false为取值

某个irValue一定是const，我要用值：((IrConstantInt) irValue).getValue()

我要某个VarSymbol的irValue（是个地址）对应的值：new LoadInstr(XXX.getSymbol().getIrValue());

A=A OP B：irValue1 = new AluInstr("OP", irValue1, irValue2);

目前支持的OP：+、-、*、/、%、&同&&、|同||

变量赋值操作： 左值、右值、store

1
2
3
4
5
6
7
8
9

private static void generateAssignStmtIr(Stmt stmt) {
    LVal lval = stmt.getLVal();
    Exp exp = stmt.getAssignStmtExp();

    IrValue irLVal = VisitorLVal.generateLValIr(lval, true);
    IrValue irExp = VisitorExp.generateExpIr(exp);
    irExp = IrType.convertType(irExp, ((IrPointerType) irLVal.getIrType()).getTargetType());
    new StoreInstr(irExp, irLVal);
}

一个例子：**代表(a+b)^b。保证b为const。

1
2
3
4
5
6
7
8

if (op.getToken().getValue().equals("**")) {
    int b = ((IrConstantInt) irValue2).getValue();
    irValue2 = new AluInstr("+", irValue1, irValue2);
    irValue1 = new AluInstr("*", new IrConstantInt(1), irValue2);
    for (int i = 1; i < b; i++) {
        irValue1 = new AluInstr("*", irValue1, irValue2);
    }
}

一定注意AluInstr的Op要自己写。

如下面一元表达式的例子，不要把++的op直接写为op。

1
2
3
4
5
6
7

switch (op) {
    case "+":
        return irValue;
    case "++":
        return new AluInstr("+", new IrConstantInt(1), irValue);
    case "-":
        return new AluInstr(op, constantZero, irValue);

Stmt型之新增def成分

词法分析

无新token产生。

语法分析

要新建或修改对应的parse方法。建议新建，大不了许多内容复制粘贴，也要尽量把类型区分开。

因为涉及到新的def成分，往往是BType Ident = InitVal，所以我们直接用一个更包容的BType + VarDef来取代。

毕竟如果不涉及语义错误，就不会出现没有 = InitVal被误判为正确的现象出现。

为什么不直接用VarDecl？你看一眼就会发现它的定义里包含一个分号。

语义分析

看起来关键在VarDef上，实际上它的visit已经封装好了。

这也就是我们没有单个处理Ident = InitVal而是直接视为VarDef的原因。

实际上的关键在于Scope。在某Stmt内定义var，还想只在该Stmt内生效，就需要再套一层Scope。

直接对于该Stmt，在整个visit函数套上：

1
2
3

SymbolRecorder.enterScope();
// XXXXXX
SymbolRecorder.exitScope();

代码生成

首先要为刚才的def成分提供一个get方法。

然后去VisitStmt找到对应函数，先套上：

1
2
3

SymbolRecorder.goToSonSymbolTable();
// XXXXXX
SymbolRecorder.exitScope();

注意不是enterscope了！因为enter不仅包含goto，还包含create

接下来就是XXXXX的具体内容。

首先把varDef用get方法拿到，然后

VisitorDecl.generateVarDefIr(varDef);

注意这个方法本来是private的，这里要把它public一下

Stmt型之新的Stmt

这里以一个简单的while(Cond) Stmt为例。

词法分析

新增token是单词while，因此要在TokenType的getTokenType(String string)方法新增一个case即可。

语法分析

Stmt中新增一个StmtType，并单独设立Parse方法。

利用type.equals(TokenType.WHILETK)直接实现判别。

之后就直接

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

type = StmtType.WHILE;
addNode(new TokenNode()); // while
addNode(new TokenNode()); // (
addNode(new Cond()); // Cond
if (getCurrentToken().getType().equals(TokenType.RPARENT)) { // 如果真的要求处理
	addNode(new TokenNode()); // )
} else {
    addMissRightParenthesisError(); // 自带错误记录与BUG_FIX
}
SymbolRecorder.enterFor(); // 重要！不能忽略这也是个循环！
addNode(new Stmt());
SymbolRecorder.exitFor(); // 这是为continue与break的异常判断提供信息

顺便提前为代码生成部分准备好getWhileStmtCond、getWhileStmtStmt。

语义分析

这个反倒没什么特别的。不定义变量，也不涉及语义错误。

直接super.visit()

代码生成

我们可以完全照搬for的结构。

关于循环体需要注意的IrLoop的维护与跳转的逻辑基本上都是一样的。

continue是跳转到该层循环的step块

break是跳转到该层循环的follow块

while的特点是没有step块，并且continue会跳到cond块。

所以直接认为step块就是cond块。

for循环是cond->body->step->cond或cond->follow

但是出于continue的含义才没有把body和step合并。

在while里就简单的多了，就是cond->body->cond或者cond->follow

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

private static void generateStmtWhileStmtIr(Stmt stmt) {
    // 创建基本块
    final IrBasicBlock condBlock = IrBuilder.getNewBasicBlockIr();
    final IrBasicBlock bodyBlock = IrBuilder.getNewBasicBlockIr();
    final IrBasicBlock followBlock = IrBuilder.getNewBasicBlockIr();
    
    // 将loop入栈：stepBlock项为condBlock
    IrBuilder.LoopStackPush(new IrLoop(condBlock, bodyBlock, condBlock, followBlock));
	// 跳转统一用这个封装方法
    jumpIfNeeded(condBlock);
    
    // 解析条件cond
    IrBuilder.setCurrentBasicBlock(condBlock); // 先进入cond块
    Cond cond = stmt.getWhileStmtCond();
    // Cond的跳转由于短路求值已特别封装
    // 注意前面是true，后面是false
    VisitorExp.generateCondIr(cond, bodyBlock, followBlock);
    
    // 处理循环体body
    IrBuilder.setCurrentBasicBlock(bodyBlock);
    // 解析循环函数体stmt
    Stmt bodyStmt = stmt.getWhileStmtStmt();
    generateStmtIr(bodyStmt);
    // 跳转统一用这个封装方法
    jumpIfNeeded(condBlock);

    // loop出栈
    IrBuilder.LoopStackPop();
        
    // 处理后续块
    IrBuilder.setCurrentBasicBlock(followBlock);
}

对于非Cond型的条件跳转，大胆使用new BranchInstr(irValue, trueBlock, falseBlock);

comments powered by Disqus
© 2024 - 2026 Demiurge
Easy Life and Easy Learning
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
本站总访问量次 本站访客数人次