实验综述

什么是 Decaf？

Decaf 是一种非常简单的面向对象编程语言。

它是一种强类型的、面向对象的、支持单继承和对象封装的语言。 实验用的 Decaf 更加类似 Java，与 C++ 有比较大的差别。 学会用 Decaf 写程序是非常简单的一件事情，但是请记住 Decaf 跟现实中使用的编程语言并不完全相同，它是经过简化且面向编译器教学的需要构造的。 下面是一段 Decaf 程序：

class Main {
    static void main() {
        class Fibonacci f;
        f = new Fibonacci();
        Print(f.get(ReadInteger()));
    }
}

class Fibonacci {
    int get(int i) {
        if (i < 2) {
            return 1;
        }
        return get(i - 1) + get(i - 2);
    }
}

这段代码的大意是从键盘读取一个整数，然后把下标为这个整数的 Fibonacci 数打印到屏幕上。从中可以看出：

  1. Decaf 程序有一个叫做 Main 的类，并且含有一个静态的，返回值为 void ，参数列表为空的 main 函数，这是整个程序的入口。 main 函数必须是静态函数，返回类型为 void ，参数列表为空。

  2. Decaf 程序中引用类名、函数名等等不需要有事先声明，但是所引用到的符号在整个程序中必须有适当的定义（这一点跟 Java 是一样的）。

各阶段的 PA

Decaf 编译器的实现划分为5个阶段，每个阶段都有对应的 PA。 最后两个阶段的 PA 是选做，评分参见第一节课课件。

阶段一（PA1-A，PA1-B）：词法分析、语法分析及抽象语法树生成

本阶段可分为两个子任务，一是词法分析，二是语法分析。抽象语法树（以下简称语法树）的生成采取语法制导的方法，因此将其划归到语法分析子任务中。

词法分析的功能是从左到右扫描Decaf源程序，从而识别出标识符、保留字、整数常量、算符、分界符等单词符号（即终结符），把识别结果返回到语法分析器，以供语法分析器使用。 在识别的过程中，我们还需要检测词法相关的错误，例如字符@并非Decaf程序中的合法符号，若这个字符在注释以外出现，则需要向用户提示一个词法错误。

语法分析是在词法分析的基础上对词法分析得到的终结符串建立语法树，并对不符合语法规则的Decaf程序报错。 比如常见的少写分号的问题，就属于语法错误，会在这个阶段被发现。

PA1的最终结果是一棵跟所输入的Decaf源程序相对应的语法树。在我们的实验中，PA1的实现分两种方案，分别对应两项实验内容PA1-A和PA1-B：

  • PA1-A的重点是掌握如 lex/yacc/antlr 等语法分析器自动生成工具的用法，体会使用自动构造工具的好处，并且结合实践体会正规表达式、自动机、LALR(1)分析等理论是如何在实践中得到运用的。

  • PA1-B是通过半手工方式实现词法分析、语法分析及语法树的生成，不再使用自动生成工具。这一阶段将基于 LL1-Parser-Gen 工具生成的分析表，使用自顶向下的方法来构造语法分析器，并实现简单的错误恢复。

阶段二（PA2）：语义分析

能够成功建立语法树只说明了所输入的Decaf源程序在格式上是合法的，但是要进行有效的翻译，编译器还需要了解这个程序每个语句的含义。 了解程序含义的过程称为语义分析。考虑下面程序片断：

int str = "abc";

这个程序是符合Decaf语法的，可以通过PA1的检查并建立语法树，但这段程序显然是不正确的：字符串常量不能赋值给整数类型的变量。

在PA2中，我们把语义分析过程分为两个内容：分析符号含义和检查语义正确性。 分析符号含义是指对于表达式中所出现的符号，要找出这个符号所代表的内容，这个工作主要通过检索符号表实现。 检查语义正确性指的是要检查每个表达式的操作数是否符合要求，也就是说这个表达式是否是语言规范中所规定的合法的表达式。 由于不合法的语句具体含义在语言规范中没有规定，从而使得编译器没法明确这些语句的确切含义，所以检查语义的正确性是很有必要的。 如果一个程序成功通过语义分析，则说明这个程序的含义对于编译器来说是明确的，从而翻译工作才能得以进行。

阶段三（PA3）：中间代码生成

由于源语言和目标语言一般有比较大的差别，因此直接把语法树翻译为目标语言中的合法程序通常是比较困难的。 大多数编译器实现中所采取的做法是首先把源语言的程序翻译成一种相对接近目标语言的中间表示形式，然后再从这种中间表示翻译成目标代码。

在Decaf编译器中，我们采用一种叫做三地址码（Three Address Code，即TAC）的中间表示形式。 这种中间表示比一般的编程语言要低级，但比汇编语言要高级。 主要体现在TAC有定制的函数调用指令，以及无限可用的伪寄存器。 PA3完成后，三地址码程序可在实验框架中给定的TAC模拟器上执行。

在Scala版本的实验框架中，除了能生成 TAC 之外，还可以生成 JVM 字节码，从而在 JVM 上运行。

阶段四（可选 PA4）：数据流分析与代码优化

一般来说，在三地址码的基础上是可以直接翻译为目标代码的，但是这样的直接翻译会导致所产生的代码的效率比较差，所以多数编译器都会进行一定的优化工作。 大多数编译优化的基础是数据流分析。所谓数据流分析，是指分析各种数据对象在程序的执行路径中的状态关系，例如一个变量在离开某个语句以后是否还有用等。

在PA4中，我们之前的课程实验只要求基于 TAC 实现简单的数据流分析。本学期将新增更多代码优化的选项供大家实现。

阶段五（可选 PA5）：目标代码生成

编译器最后一个阶段的核心内容是生成汇编代码，实验框架中主要包括汇编指令选择、寄存器分配和栈帧管理等模块。 这一阶段完成后，就能生成 MIPS 32 汇编代码，可以使用 SPIM 模拟器来运行生成的代码。

这一阶段的实验框架仅实现了一种暴力寄存器分配算法，要求同学们能够实现更加高效的寄存器分配算法，并生成正确的汇编代码。除了 MIPS 外，根据框架开发和测试进度还可能 提供 RISC-V 作为备选。对 RISC-V 或者其他未列出的平台感兴趣的同学可与助教联系。

实验任务概述

概括的说，各阶段的任务均是：

在已有 Decaf 框架的基础上，增加新语言特性的支持（lambda, 类型推断），或实现新功能（代码优化，寄存器分配）。 Decaf 实验不要求你从零开始实现一个编译器。 各个阶段会有更细化的 PA 要求，和 PA 作业一起发布。

我们提供

  1. 已有的 Decaf 的框架

  2. 用于建立编程环境的工具、文档等

  3. 各阶段针对新特性的详细说明文档

  4. 各阶段针对新特性的公开测例

要求大家独立完成各阶段实验内容。

实验环境

实验环境由两部分构成：Decaf 框架和测试样例。

关于 Decaf 框架，现有三个版本：Java, Scala 和 Rust。 每位同学可任选三个版本之一，但本学期只允许选定一个版本。 我们会以第一次实验你所提交版本来确定你的选择。

各版本实验框架的预览版本可前往 Github 查看： Java Scala Rust。 注意，最终的实验框架将会在第一次实验前确定，此期间仍会更新。请注意在第一次实验发布时再次同步你的实验框架。 本学期必做实验的具体要求将在各阶段实验开始时发布。

另外，除了框架整体代码，每次 PA 我们也会发布单独的代码包。 这主要是为了避免诸如 “PA1 改了一个地方，结果实际属于 PA2 阶段的文件报编译错误” 这种情况发生。 同学们有两种选择，不过你的选择不会影响评分：

  • 使用每次 PA 单独的代码包。这样的坏处是每次需要把之前的工作在新的代码包上重做。

  • 直接在框架整体上开发。这样的坏处如上所述。

关于测试样例，各个 PA 的测试样例会在作业布置时确定和发布。 所给出的测例原则上会覆盖所有新特性及要检查的点。 此外，我们会保留一部分测例不公开，因此请你仍需自己通过其他手段来验证你的实现是否符合文档的要求。

下面简要叙述三个版本的基本实验环境。在你做 PA 过程中，若发现实验框架有任何问题，请及时告知助教，以便快速解决问题或更正。

Java

Java 版本使用 gradle 构建，前端使用 JFlex 和 Jacc。

  • 安装好 JDK 12 开发环境，正确设置好 JAVA_HOME 等环境变量。

    • 框架使用了 Java 12 的 switch 表达式，所以运行 java 的时候需要加上选项 --enable-preview 才行。

    • 运行命令 java -version 检查输出是否是 java version "12..."

    • 可以将 decaf 命令别名成 java -jar --enable-preview /project_top/build/libs/decaf.jar 方便调试

  • 安装 gradle，要求版本至少 5.2

    • 运行命令 gradle -v 检查版本，注意保证 gradle 使用的 JVM 版本和 java 12 的版本一致

  • [可选] 集成开发环境

    • IntelliJ IDEA：Import Gradle project。

    • 使用 Eclipse：安装 Gradle 插件，有可能需要修改 gradle.build 文件以开启插件。

    • 使用 Visual Studio Code：先配置 Java 插件，再安装 Gradle 插件。

  • [可选] 不使用集成开发环境，直接命令行构建

    • 在项目根目录下运行 gradle build 完成构建

    • 偶尔会出现构建时找不到符号的 bug，这时再运行一次 gradle build 即可

测试方法

  1. 将测试样例下载（或 git clone），放到项目根目录下名为 TestCase 的目录下；

  2. 构建你的项目，保证被测试的是你最新的代码

  3. 执行 TestCase/testAll.py

Scala

Scala 版本使用 sbt 构建，前端使用 ANTLR 4.

  • 安装好 JDK 8 或更高版本的开发环境，正确设置好 JAVA_HOME 等环境变量。

  • 安装 sbt

    • Scala 编译器会通过 sbt 自动下载，你无需手动安装 Scala 编译器。

  • 安装 ANTLR 4，正确设置 CLASSPATH 等环境变量

  • [可选] 集成开发环境

  • [可选] 不使用集成开发环境，直接命令行构建

    • 在项目根目录下运行 sbt build 完成构建

    • 在项目根目录下运行 sbt assembly 完成打包

测试方法

  1. 将测试样例下载（或 git clone），放到项目根目录下名为 TestCase 的目录下；

  2. 构建你的项目，保证被测试的是你最新的代码

  3. 执行 TestCase/testAll.py

Rust

Rust 版本使用 cargo 构建，前端为 mashplant 自主研发。

  • 利用 rustup 安装 nightly 版本的 Rust 编译器：rustup default nightly。

    • 项目已经在 rustc 1.38.0-nightly 上测试过，比它更新的版本应该也可以。

  • 集成开发环境

    • 使用 Clion：安装 Rust 插件 即可开发。

    • 使用 Visual Studio Code：安装 Rust language server 插件。但是它似乎对复杂 toml 字符串支持的不太好，导致一些文件显示异常。

  • 相关命令

    • 运行：cargo run --bin decaf

    • 测试：cargo run --bin test

实验提交

关于提交方式，本学期拟采用校内 Git 平台 提交（至少是必做阶段的）实验代码。该平台直接用 info 账号登录。 课程组近期将通过网络学堂的作业窗口收集大家的用户名，请前往 https://git.tsinghua.edu.cn 登录后查看并提交自己的用户名。 实验开始前，助教将统一为大家创建私有仓库，请将实验代码在各阶段截止时间之前提交至此仓库。评分会以截止时间前的最后一次 master 分支提交为准。

完成实验的代码部分以后，你还需写一份实验报告。一般的，报告中包含如下内容，在此前提下尽量简明扼要：

  1. 完成 PA 的大致思路（例如加入了哪些新的数据结构、函数、大致工作逻辑等）；

  2. 如果有，遇到的挑战和解决方法；

  3. 各个 PA 要求回答的问题；

  4. [特别注意] 如果你借用别人成果或思路，必须明确说明：借用内容，请教了谁，参考了什么文献或网址

为避免文档编码等问题，实验报告一律使用PDF格式，命名为 report-PA_NAME.pdf。 实验报告放在源码根目录下，其中 PA_NAME 可能是：

PA1-A
PA1-B
PA2
PA3
PA3-JVM

请在规定的截止时间前提交，晚交将会酌情扣分，不交将没有成绩。

以上仅适用于Decaf前四个阶段的必做阶段实验。此外，可能会有同学选作特定的选做阶段实验以及拓展实验，具体安排将在课程后期通知。

评分标准

Decaf 每阶段实验所占最终成绩的比例见课程第一讲课件。

细化到每个阶段（PA），

  • 80% 成绩是程序部分。要求程序输出结果与标准输出完全一致。

  • 20% 成绩是实验报告。评分标准如：清楚说明工作内容，正确回答该 PA 要求回答的问题

  • 和软件工程课程不同，编译原理不考察 git log 等与课程无关的内容。

补交政策如下：假设 a 日 23:59 是某 PA 在网络学堂上的截止时间，那么

  • 补交（包括不扣分的补交）必须给负责该 PA 的助教发邮件告知，补交时间是助教收到邮件的时间；

  • 邮件内容请包含：学号，姓名，用于该 commit 测试的 commit sha1（至少包含前 12 位防止冲突）；

  • a+2 日 23:59 前补交，此 PA 不扣分；

  • a+k 日 23:59 前补交，此 PA 得分乘以 1 - (k-2)/15；

  • a+16 日 23:59 后不接受补交，此 PA 得 0 分。

若完成了选做实验或拓展实验，则在四个阶段的评分完成后统一评分。 拓展实验的评价是综合考虑创新性、实用性、合理性、难度、工作量等因素进行的。

在每阶段截止提交以后，我们一般会在两周内在网络学堂上公布成绩。 如果你认为成绩有问题，请及时与助教联系（关于实验成绩的疑问最晚请在期末考试以前提出，考试以后不能再更改实验成绩）。

学术规范声明

由于实验有一定难度，同学之间相互学习和指导是提倡的。

对于其他同学的代码（包括实验报告中问题的回答），可以参考，但禁止直接拷贝。 如有代码交给其他同学参考的，必须向老师或助教申明，告知给哪些同学拷贝过代码（包括可能通过间接渠道传播给其他同学）。 请所有同学不要将自己的代码托管至任何公开的仓库上（如 Github、Gitlab 等），托管至私有仓库的请不要给其他同学任何访问权限。 如发现有代码拷贝的情形，拷贝者和被拷贝者将会得到同样的处罚，除非被拷贝的同学提交时已做过声明。

代码雷同情节严重的，课程组有权上报至院系和学校，并按照相关规定严肃处理。

相关资料

PreviousIntroductionNextPA1-A 实验说明

Last updated