sysy 编译器设计

Posted on:2023.01.17

TOC

Open TOC

Info

https://github.com/courses-at-nju-by-hfwei/compilers-lab-docs/

https://github.com/VGalaxies/SysY-compiler

Ref

https://gitlab.eduxiji.net/nscscc/compiler2022

https://pku-minic.github.io/online-doc/#/

Lab 1

功能实现

通过 antlr 的 lexer 模块进行词法分析，并输出 tokens

若在词法分析中出现错误，则不输出成功匹配的 tokens，这通过自定义 lexer 的 listener 来实现

由于对十六进制和八进制数字常量输出 token 文本时需输出其十进制的值，所以考虑在词法分析的过程中替换其 text 文本，并重置其 type 为 INTEGR_CONST

DECIMAL_INT_CONST : NON_ZERO_DIGIT DIGIT* { setType(INTEGR_CONST); } ;
OCTAL_INT_CONST : '0' OCTAL_DIGIT* { setText(NumberUtils.octToDec(getText())); setType(INTEGR_CONST); } ;
HEXADECIMAL_INT_CONST : HEXADECIMAL_PREFIX HEXADECIMAL_DIGIT+ { setText(NumberUtils.hexToDec(getText())); setType(INTEGR_CONST); } ;


INTEGR_CONST : DECIMAL_INT_CONST | OCTAL_INT_CONST | HEXADECIMAL_INT_CONST ;

此处 INTEGR_CONST 规则仅用于提供 type，实际词法分析的过程中不会有 token 的 type 会直接设置为 INTEGR_CONST

观察

import org.antlr.v4.runtime.*;
import org.antlr.v4.runtime.tree.*;


public class Test {
    public static void main(String[] args) throws Exception {
        // create a CharStream that reads from standard input
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        // create a lexer that feeds off of input CharStream
        ArrayInitLexer lexer = new ArrayInitLexer(input);
        // create a buffer of tokens pulled from the lexer
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        // create a parser that feeds off the tokens buffer
        ArrayInitParser parser = new ArrayInitParser(tokens);
        ParseTree tree = parser.init(); // begin parsing at init rule
        System.out.println(tree.toStringTree(parser)); // print LISP-style tree
    }
}

在执行 parser.init() 前，不会有任何的 tokens 会被消耗

所以在本次实验中，需要通过 getAllTokens 获得所有的 tokens

参考

https://github.com/antlr/grammars-v4

https://github.com/antlr/antlr4/blob/master/doc/lexer-rules.md

https://stackoverflow.com/questions/6487593/what-does-fragment-mean-in-antlr

Lab 2

功能实现

依据 Lab 1 中词法分析模块生成的 tokens 流，通过 antlr 的 parser 模块进行语法分析

若语法分析的过程中未产生错误，则生成 parser tree，并自定义 visitor 或 listener 在 parser tree 上遍历

否则，通过自定义 parser 的 listener 来输出错误信息，这一部分与 Lab 1 中类似，不再赘述

这里考虑自定义 visitor 实现遍历 parser tree 的目的，其继承关系如下

public class SysYParserDerivedVisitor extends SysYParserBaseVisitor<Void>

需要 override 基类两个方法

输出对应的非终结符信息，注意需要手动将 rule names 的首字母大写，同时控制缩进格式

输出对应的终结符信息，利用表驱动的方式为 tokens 打印对应的颜色，这会与 SysYLexer 内部的 ruleNames 高度耦合

碎碎念

由于似乎绝大部分测试用例都是没有语法错误的，因此本次实验的正确性高度依赖 SysYParser.g4 中定义的文法结构，在某种程度下限制了自由发挥

另外，考虑到 antlr 相较于传统的语法分析工具 bison 进行了一些抽象与封装，本次实验似乎难以在语法错误上进行过多的考察

对比隔壁传统编译原理的第一次实验中，测试用例中语法错误的占比应该超过了 90 %

参考

https://github.com/antlr/antlr4/blob/master/doc/parser-rules.md

Lab 3

功能实现

使用 ANTLR 提供的 Listener 或 Visitor 机制遍历语法树，在遍历过程中填充符号表，并进行语义分析，若语义分析无误，则对指定位置的变量进行重命名

这里使用了 Visitor 机制遍历语法树，为了传递继承属性和综合属性，考虑引入 context 类记录一些必要的信息，如变量声明的 base type

实际上可以考虑使用 ParseTreeProperty

该 context 类即为 SysYParserBaseVisitor 的泛型类型，子规则由此可以向父规则传递综合属性

为了能够让父规则向子规则传递继承属性，同样利用该 context 类，在全局定义一个该类的实例，在子规则访问属性后，父规则需要将相应的属性及时 reset

正因如此，context 类的属性不可重入

另外，考虑到每个规则可能存在多条产生式，为了避免对可能的终结符或非终结符进行 null 判定，可以考虑在文法中添加 # 注解，例如

cond
   : exp # CondExp
   | lhs = cond (op = LT | op = GT | op = LE | op = GE) rhs = cond # CondBinary
   | lhs = cond (op = EQ | op = NEQ) rhs = cond # CondBinary
   | lhs = cond op = AND rhs = cond # CondBinary
   | lhs = cond op = OR rhs = cond # CondBinary
   ;

此时 visitCond 接口会被拆分为 visitCondExp 和 visitCondBinary 接口，而实际的文法结构不会发生变化

对于符号表的设计，其数据结构如下

name -> {name, type, position, value, is-constant}

由于数组类型的等价性无视每个维度的大小，所以在本次实验中不必记录类型值相关的信息，即不必进行编译期计算

由于函数的参数视作在函数内部的那个作用域内，所以不必特殊处理函数产生的块作用域

position 字段记录了该符号起始字符的所在行数 (从 1 开始计数) 和列数 (从 0 开始计数)

该字段会被 SymbolTracker 类记录，该类维护了变量生命周期一致的同名变量的 position 集合

当 define 和 resolve 一个符号时，会修改上述集合，例如，对于下述程序

int a() {
    return 42;
}


int res = a();


int main(int a) {
    int b = a;
    res = a + 4;
}

其对应的 position 集合为

{lineNo:7,column:4}
{lineNo:5,column:4},{lineNo:9,column:4}
{lineNo:8,column:8}
{lineNo:1,column:4},{lineNo:5,column:10}
{lineNo:9,column:10},{lineNo:8,column:12},{lineNo:7,column:13}

碎碎念

在实验要求中有这样的描述

『请注意，请输出最本质的错误，对其进行合理的恢复后继续分析后续错误』

我们考虑变量赋值这一情形

int a[2][3];
int b[2][3];

通过观察 gcc 和 clang 的报错信息，得出了如下一些简单的规律

例如对于上述声明，若执行 a[2][3][4] = b;，则仅会输出

a.c:4:10: error: subscripted value is not an array, pointer, or vector
                a[2][3][4] = b;
                ~~~~~~~^~
1 error generated.

例如对于上述声明，若执行 a[a[1]][a[1]][4] = b;，则仅会输出

a.c:4:6: error: array subscript is not an integer
        a[1][a[1]][a[1]] = b;
            ^~~~~
1 error generated.

若执行 a[1][1] = b + a[1] + a[1];，则仅会输出

a.c:4:14: error: invalid operands to binary expression ('int[2][3]' and 'int[3]')
        a[1][1] = b + a[1] + a[1];
                  ~ ^ ~~~~
1 error generated.

若执行 a[1][1] = b + (a[1] + a[1]);，则仅会输出

a.c:4:22: error: invalid operands to binary expression ('int[3]' and 'int[3]')
        a[1][1] = b + (a[1] + a[1]);
                       ~~~~ ^ ~~~~
1 error generated.

为了能够在子规则中快速回退调用栈，来到预先设置的同步恢复点，考虑利用 Java 的异常机制

同步恢复点 (catch exception) 的设计如下

某些同步恢复点会引入 hasError 标记，便于判断在捕获异常后提前结束正常执行流，或者重新抛出异常 (cond)

而对于异常的抛出 (throw) 的时机，通常考虑在子规则 report error 之后

某些中间规则不考虑捕获这些异常，实际上相当于该中间规则也会抛出异常，直至被同步恢复点捕获

还有一些比较反直觉的语义定义

int test(int i, int i) {
    return test(i + 1);
}

实际上，个人感觉本质的语义错误并没有一个『清晰』的定义，考虑变量重复定义的场景

对于下述程序

int foo() {
  return 42;
}


int main() {
    int a[1] = {1};
    int a[foo(1)] = {1};
}

gcc 和 clang 会报告变量重复定义

> gcc a.c
a.c: In function ‘main’:
a.c:7:5: error: variable-sized object may not be initialized
    7 |     int a[foo(1)] = {1};
      |     ^~~
a.c:7:9: error: redeclaration of ‘a’ with no linkage
    7 |     int a[foo(1)] = {1};
      |         ^
a.c:6:9: note: previous definition of ‘a’ with type ‘int[1]’
    6 |     int a[1] = {1};
      |         ^


> clang a.c
a.c:7:16: warning: too many arguments in call to 'foo'
    int a[foo(1)] = {1};
          ~~~  ^
a.c:7:9: error: redefinition of 'a'
    int a[foo(1)] = {1};
        ^
a.c:6:9: note: previous definition is here
    int a[1] = {1};

实际上 gcc 都没有检测函数调用参数是否匹配

而当数组下标的表达式为未定义的变量时

int main() {
    int a[1] = {1};
    int a[b] = {1};
}

gcc 和 clang 就不会报告变量重复定义了

> gcc a.c
a.c: In function ‘main’:
a.c:3:11: error: ‘b’ undeclared (first use in this function)
    3 |     int a[b] = {1};
      |           ^
a.c:3:11: note: each undeclared identifier is reported only once for each function it appears in


> clang a.c
a.c:3:11: error: use of undeclared identifier 'b'
    int a[b] = {1};

由此可见，编译器汇报的语义错误很大程度上取决于其具体实现，个人认为语义错误检测的基本要求是不能漏报，在此基础上尽可能减少误报

参考

> gcc --version
gcc (GCC) 12.2.0
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.


> clang --version
clang version 14.0.6
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin

Lab 4

功能实现

利用 LLVM API，实现对 return 语句和常量表达式的翻译

考虑自定义 visitor 在遍历 parser tree 的过程中翻译，其继承关系如下

public class SysYIRGenerator extends SysYParserBaseVisitor<LLVMValueRef>

初始化过程略去，只需要 override 下述三个方法即可

注意到最终生成的 LLVM IR 会直接计算出常量表达式的值

碎碎念

由于使用了 maven 添加 llvm 和 javacpp 的依赖，所以需要修改 Makefile 的 compile 和 run 规则

在个人的环境下，通过如下方式获取 classpath

LIBPATH = $(shell (find /usr/local/lib -name "antlr-*-complete.jar" ; find /home/vgalaxy/.m2/repository -name "llvm*.jar" ; find /home/vgalaxy/.m2/repository -name "javacpp*.jar") | xargs | sed 's/ /:/g')

然后对应修改即可

compile: antlr
  mkdir -p classes
  $(JAVAC) -classpath $(LIBPATH) $(JAVAFILE) -d classes
  $(call git_commit, "make")


# make run ARGS="xxx"
run: compile
  java -classpath ./classes:$(LIBPATH) Main $(ARGS)

或者考虑修改 maven 的构建配置

Lab 5

功能实现

利用 LLVM API，实现函数的定义、调用和局部变量的声明、定义、使用的翻译

考虑重新设计符号表，在每一个作用域内建立如下的映射关系

symbol name -> LLVMValueRef

对于符号表中每个的 LLVMValueRef，本质上都是通过 LLVMBuildAlloca 构建的，统一使用 lvalue 命名

对于 GEP 指令，实际上相当于根据一个 lvalue 生成另一个 lvalue

当 lvalue 作为右值使用，即出现下述文法结构时

exp : lVal

需要使用一次 load 指令

store 指令的范式如下

LLVMBuildStore(builder, rvalue, lvalue);

其中 rvalue 可能为

函数形参的构建，应该在切换基本块之后，访问 block 之前

碎碎念

大部分构建 LLVMValueRef 的函数，最后一个参数都是 String s

当传入空字符串时，会根据该 LLVMValueRef 是否被使用选择是否显示助记符，例如调用一个 void 函数

C 标准规定，数组变量在初始化时，若长度给出，则必须为 integer constant expression

An integer constant expression shall have integer type and shall only have operands that are integer constants…

LLVM 中提供了下述 API，可以在运行时将满足上述条件的 LLVMValueRef 转换为 interger

@Cast({"unsigned long long"})
public static native long LLVMConstIntGetZExtValue(LLVMValueRef var0);

若不满足上述条件，得到的结果为随机值

在语义分析阶段，并未检查一个函数是否显式包含了对应的 return 语句

若源代码中省略了 return 语句，会导致生成的中间代码缺少 terminator 指令

考虑到每个基本块的最后必须要有一个 terminator 指令，需要在生成中间代码前进行检查和修复

为此引入 SysYReturnFixer 类

public class SysYReturnFixer extends SysYParserBaseVisitor<Void>

该类仅 override 一个方法 visitFuncDef，若发现一个函数的最后一条语句不是对应的 return 语句，则通过下述方式进行修复，例如添加 return;

private void addReturnVoid(SysYParser.BlockContext blockContext) {
    SysYParser.BlockItemContext blockItemContext = new SysYParser.BlockItemContext(blockContext, -1);
    SysYParser.StmtContext stmtContext = new SysYParser.StmtContext(blockItemContext, -1);


    Token returnToken = new CommonToken(SysYLexer.RETURN);
    TerminalNode returnNode = new TerminalNodeImpl(returnToken);


    Token semicolonToken = new CommonToken(SysYLexer.SEMICOLON);
    TerminalNode semicolonNode = new TerminalNodeImpl(semicolonToken);


    stmtContext.addChild(returnNode);
    stmtContext.addChild(semicolonNode);


    blockItemContext.addChild(stmtContext);
    blockContext.addChild(blockItemContext);
}

此处利用了 ANTLR 中 lexer 和 parser 提供的方法，原地修改语法树结构

另一种更简单的方法，使用 LLVMGetBasicBlockTerminator 测试当前基本块是否存在 terminator 指令

参考

Lab 6

功能实现

利用 LLVM API，实现全局变量和条件语句的翻译

对于全局变量，只需修改 visitVarDef 和 visitConstDef 的实现，利用下述 API 构造全局变量即可

对于条件语句，需要对 if 语句和 cond 表达式进行翻译

  1. 对于 if 语句

考虑统一 if 语句与 ifelse 语句，也就是每一次进入 if 语句的上下文时，都需要生成三个基本块

这里比较关键的是，这些基本块并不会立即被 append 到 cfg 中，而是需要在合适的时机 append 并切换，其范式如下

visit cond
append and switch to trueBlock
visit stmt(0)
append and switch to falseBlock
visit stmt(1)
append and switch to nextBlock

为此，需要使用 LLVMCreateBasicBlockInContext 和 LLVMAppendExistingBasicBlock 这两个 API 完成上述操作

由于每个基本块的最后必须有且仅有一个 terminator 指令，所以可以使用 LLVMGetBasicBlockTerminator 这个 API 判断 trueBlock 或 falseBlock 中是否已经存在 terminator 指令，若不存在，再显式添加 br 无条件跳转指令

使用 ParseTreeProperty<LLVMBasicBlockRef> 存储这些基本块作为继承属性

  1. 对于 cond 表达式

考虑将其分类为

其中只有第二类 cond 表达式会生成 br 条件跳转指令

若考虑隐式类型转换，则

更具体的，当 cond 表达式的 parent context 为 stmt 或第三类 cond 表达式时，需要生成 br 条件跳转指令，否则作为值使用

碎碎念

如果不实现短路求值，也就是让下面的程序爆栈

int foo(int x) { return foo(x); }


int main() {
  int a = 2;
  if (a == 2 || foo(a) == 2) {
    a = 1;
  }
  return a;
}

可以完全不使用 ParseTreeProperty<LLVMBasicBlockRef> 存储基本块作为继承属性

此时所有的 cond 表达式都会统一返回 i32 类型的值

只有在 if 语句中才会生成 br 条件跳转指令，即将 cond 表达式返回的值与 zero 比较

这种方案可以无心智负担的实现隐式类型转换

Lab 7

功能实现

利用 LLVM API，实现循环语句 (包括 break 和 continue 语句) 的翻译

类似 if 语句，其翻译范式如下

goto beginBlock
append and switch to beginBlock
visit cond
append and switch to trueBlock
visit stmt
append and switch to nextBlock

在实际操作中，发现 nextBlock 不必使用 ParseTreeProperty<LLVMBasicBlockRef> 存储，因为 nextBlock 仅会在 if 和 while 语句的开头创建

考虑使用栈存储 while 语句中创建的 beginBlock 和 nextBlock，然后使用 br 无条件跳转指令即可

碎碎念

https://gitlab.eduxiji.net/nscscc/compiler2022/-/blob/master/%E5%85%AC%E5%BC%80%E6%A0%B7%E4%BE%8B%E4%B8%8E%E8%BF%90%E8%A1%8C%E6%97%B6%E5%BA%93/hidden_functional/34_multi_loop.sy

之前提过，可以使用 LLVMGetBasicBlockTerminator 这个 API 测试某个基本块是否已经存在 terminator 指令，从而可以避免下述情形对 return 语句的多次翻译

int main() {
  int a = 42;
  return a;
  return a;
}

然而，在测试过程中发现，若某个基本块中 terminator 指令不是连续出现的，LLVM 会插入一些隐式 basic block，例如

int main() {
  int a = 42;
  return a;
  int b = 12;
  return a;
}

生成的中间代码可能如下

define i32 @main() {
mainEntry:
  %a = alloca i32, align 4
  store i32 42, i32* %a, align 4
  %0 = load i32, i32* %a, align 4
  ret i32 %0
  %b = alloca i32, align 4
  store i32 12, i32* %b, align 4
  %1 = load i32, i32* %a, align 4
  ret i32 %1
}

对于上述中间代码，LLVM 会将其解读为

define i32 @main() {
mainEntry:
  %a = alloca i32, align 4
  store i32 42, i32* %a, align 4
  %0 = load i32, i32* %a, align 4
  ret i32 %0
%1:
  %b = alloca i32, align 4
  store i32 12, i32* %b, align 4
  %1 = load i32, i32* %a, align 4
  ret i32 %1
}

注意这里多出的 %1 标号，所以在执行过程中会出现

lli: lli: dump.ll:12:3: error: instruction expected to be numbered '%2'
  %1 = load i32, i32* %a, align 4

除了 return 语句，break 和 continue 语句也会有类似的结果，本质上，这三类语句生成的 terminator 指令都是与语法结构一一对应的，即语法树中有多少条 return 语句，就会生成多少条 terminator 指令

为了避免出现上述问题，考虑在这三类语句生成 terminator 指令后，添加一个 dummy basic block，这样会导致生成的中间代码中出现没有 predecessors 的 basic block，但是不会影响正常的执行流

int nums[8] = {4, 3, 5, 0, 6, 2, 1, 7};


void swap(int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}


int partition(int left, int right) {
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) {
            j = j - 1;
        }
        while (i < j && nums[i] <= nums[left]) {
            i = i + 1;
        }
        swap(i, j);
    }
    swap(i, left);
    return i;
}


void quickSort(int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = partition(left, right);
    quickSort(left, pivot - 1);
    quickSort(pivot + 1, right);
}


int main() {
    quickSort(0, 7);
    int idx = 0;
    while (idx < 8) {
        if (nums[idx] != idx) {
            return 1;
        }
        idx = idx + 1;
    }
    return 0;
}

参考

Lab 8

功能实现

利用 LLVM API，允许一维数组作为函数的参数

需要修改下面三处地方

  1. 翻译函数形参

此时的形参类型为 LLVMPointerType(i32Type, 0)

其中 LLVMPointerType 的含义如下

This constructs a pointer to an object of the specified type in a numbered address space.

此处传递 0 即可

  1. 翻译函数实参

需要考虑两种情形

例如对于下述代码

int foo(int arr[]) {
    ...
}


int main() {
    int a[2] = {};
    return combine(a);
}

则应该利用 GEP 指令进行一次解引用

%0 = getelementptr [2 x i32], [2 x i32]* %a, i32 0, i32 0
%1 = call i32 @foo(i32* %0)

例如对于下述代码

int bar(int arr[]) {
    ...
}


int foo(int arr[]) {
    bar(arr);
}

则应该利用 LOAD 指令进行一次解引用

%0 = load i32*, i32** %arr, align 8
%1 = call i32 @bar(i32* %0)
  1. 下标访问 PointerType 类型的变量

例如对于下述代码

int foo(int arr[]) {
    return arr[0];
}

则应该利用 GEP 指令进行一次解引用

define i32 @foo(i32* %0) {
fooEntry:
  %arr = alloca i32*, align 8
  store i32* %0, i32** %arr, align 8
  %1 = load i32*, i32** %arr, align 8
  %2 = getelementptr i32, i32* %1, i32 0
  %3 = load i32, i32* %2, align 4
  ret i32 %3
}

注意此处的 GEP 指令的 indices 长度为 1 而非 2

参考