编译原理

Lab2 Report

2020-04-10 00:00 CST
2020-04-11 16:17 CST
CC BY-NC 4.0

0. 额外约定

因为本次实验讲义存在太多未详细定义的错误,因此我把我进行额外处理的错误在这里列出:

  • ifwhile看作一种特殊的运算符处理,只能接受int类型的表达式(符合假设2),如果条件是其他类型的表达式,则抛出错误7。例如,if (0.0)是一种错误的使用if“运算符”的做法。
  • 所有的变量享受局部作用域限制(符合选做要求2),变量可以和函数(全局作用域)重名;但变量不可以和结构体(全局作用域)重名,结构体也不可以和所有作用域中仍然存在的变量重名,否则抛出错误16。例如,我先在函数中定义了变量a,函数体结束后a随着符号表被销毁,则此时可以定义结构体a,但定义结构体后都不能再定义a,否则认为发生重定义。
  • 函数如果前后声明不一致,那么一律以第一次出现的为准,即使后面出现了定义但类型或签名不一致也认为该函数没有定义。例如,int foo();后定义了float foo() {...},则会报出错误18(未定义)和错误19(冲突)。
  • 和gcc一样,表达式解析中出现未定义的ID或类型一律以int处理,所有四则运算一律以左边的作为返回类型,数组只要维度和基类相同即为相同类型(不考虑每一维的大小)。

1. 文件结构

本次新增的内容如下:

  • semantics.c:语义分析主入口
  • rbtree.c:某种邪恶的数据结构
  • table.c:符号表数据结构(实现与底层数据结构隔离的抽象层)
  • type.c:数据类型和各种符号解析函数(一个语法树节点类型一个解析函数)

2. 数据结构

我是functional style选手(因为一个作用域一张符号表太符合直观了,爱了),采用了邪恶的红黑树作为底层数据结构。红黑树是我Google随便找了一个C++版本移植到C的(干啥啥不行,外包第一名)。红黑树采用void *作为红黑树的节点类型,并通过函数指针来控制红黑树对数据的行为。

为了简化上层实现,我在符号表和红黑树之间加入了一个中间的抽象层处理。在进行相关红黑树操作时,这些函数会首先将void *转换为如下所示的STEntry *,然后对数据进行具体的操作。这样在进行语义分析的时候只要调用符号表相关函数,符号表再去调用抽象层中的函数即可完成。

typedef struct STEntry {
  const char *id;
  SEType *type;
} STEntry;

然而如果在语义分析时直接对红黑树进行操作太麻烦了,因此我通过符号表实现了对红黑树具体操作的抽象。

typedef struct STStack {
  enum STStackType type;
  struct RBNode *root;
  struct STStack *prev; // no next
} STStack;
  • functional style的符号表可以看作是一个单向(只忘链表头部指的)链表,在链表头部的即为全局符号表(结构体、函数、全局变量);
  • 为了访问符号表,共有3个符号表指针:
    • struStack指向结构体符号表,
    • funcStack指向函数符号表,
    • currStack指向当前最小作用域对应的符号表(初始状态下为全局变量符号表)。
  • 每进入一个局部作用域,对符号表压栈,创建新的红黑树并更新currStack
  • 每离开一个局部作用域,对符号表出栈,销毁对应红黑树并更新currStack
  • 分析结束后,一路出栈直到链表为空,销毁所有的红黑树。

3. 语义分析

语义分析就是每种语法树节点一个处理函数,然后面向过程的处理所有可能出现的情况,没什么好讲的。

主要讲一讲单个语法树节点的分析函数的不同返回类型,共有三种:

  • void:无返回值,如解析FunDec时直接在函数符号表上产生副作用,不需要返回类型。
  • SEType *:返回一个指向类型的指针,如解析Exp时直接返回解析得到的类型。
  • SEChain:返回一个类型的链表,如解析DefList时返回一连串的类型指针,组成结构体定义。

而因为存在类型指针,所以用了三个静态变量来防止大量重复的创建相同对象操作:

  • STATIC_TYPE_VOID:空类型(如函数不需要参数,签名类型为VOID);
  • STATIC_TYPE_INT:所有的整数都长一个样;
  • STATIC_TYPE_FLOAT:所有的实数都长一个样。

对于函数定义,是通过如下方式处理的:

  1. 解析返回类型;
  2. 解析函数名称,符号表压栈(函数签名是局部作用域);
  3. 解析函数签名(与struct相同处理方式),并在函数符号表中注册函数;
  4. 解析函数体CompSt
  5. 符号表出栈,销毁局部作用域中的所有变量。

最后,如果遇到了错误,会调用throwErrorS函数抛出错误,此处使用了枚举类型防止每次查讲义确定错误编号。

4. 内存管理

本次实验实现了语义分析部分和语法树的内存回收。(除了flex和bison分配的一些内存以外,基本都收回来了,但想想这个工作如果实现不稳定的话就会吃苦不讨好。)

回收时遇到了一些问题:对于数组和结构体的类型指针,经常会出现双重free的情况。解决方案:

  • 回收数组类型时,一路销毁类型对象,直到遇到基类(必为intfloat或结构体);
  • 回收其他所有类型时,一旦遇到结构体或基础类型马上跳过。
  • 每个结构体必须被单独地、显式地销毁,即使销毁结构体时也不能销毁成员的结构体类型。

5. 实验的感想和致谢

感觉实验花太多时间了(特别是内存回收感觉做了个对于得分来说没必要的玩意……)

感谢各位助教的耐心解答、董杨静同学开发的测试脚本、各种测试数据(我也contribute了几个LOL)

6. Time Limit Exceeded

非常感谢董杨静同学提供的鬼畜测试数据……把我卡死了:假设一个结构体有$n$个变量,每个变量都是结构体……总共有$m$层嵌套,那么朴素地比较这两个结构体的类型就需要$O(n^m)$的时间,直接炸了。

解决方案:使用并查集+路径压缩,时间复杂度压到了$O(\alpha(n+m))$。(编译原理变成了问题求解)