LC-3编译器的代码生成

ECE 220 Fall 2022 ZJUI Machine Problem 11

Translated by DeepL, formatted and checked by Qiushi Liu.

I do not guarantee the correctness of any part of this translated document.

这项作业要求你使用递归将一个C语言子集的程序描述翻译成LC-3汇编代码。开发这样的代码为你提供了在C语言中使用递归和基于指针的数据结构的经验，这两者都是重要的工具。你还会对从一种形式的程序自动翻译成另一种形式的程序所涉及的方法和挑战有更好的理解。编译器的大部分将提供给你，包括将C代码翻译成抽象语法树（AST）的代码，以及支持LC-3上基本算术和I/O的C库例程。你的重点是将AST转化为LC-3指令的序列。

在你开始编程之前，请完整地阅读这份文件。

关于阅读代码

你不需要阅读提供给你的超过3300行的C、词法分析器、解析器和LC-3代码。提供给你。当然，我们欢迎你这样做，但你不需要阅读它们来完成这个任务。这个任务。所有来自标题等的相关材料都包含在本文件中。此外，你应该知道，大量的代码（大约4500行！）是在你构建编译器时自动生成的。而这些自动生成的代码（如 ece220_lex.yy.c）都不是为了让人阅读的，不要尝试。如果你想删除自动生成的文件，这样你就可以看到原始发行中的内容，输入make clear。

C语言的子集

为了简化你的任务，该编译器只支持完整的C语言编程的一个狭窄子集。包括对if语句、for循环、return语句和使用大多数C语言操作符的表达式的支持。复合语句是必须的，~~而不是只作为良好练习~~（Compound statements are required as opposed to simply being good practice）。例如：


int i;
for (i = 0; 10 > i; i++) /* This code will generate a syntax error. */
    printf ("%d\n", i);
for (i = 0; 10 > i; i++) { /* To avoid, include braces around loop body. */
    printf ("%d\n", i);
}

为该编译器编写的程序可以声明全局变量以及一个子程序（当然是int main()）。在main中可以声明局部变量，但在其他情况下不允许声明变量（例如，在复合语句中）。只支持两种类型：int和整数的一维数组。不支持指针类型，而且你只能用括号内的表达式来使用数组的索引。例如：


xxxxxxxxxx
int a[1];
scanf ("%d", a); /* NOT legal--will generate a syntax error */
scanf ("%d", &a[0]); /* legal */

常量字符串可以使用，但只能作为函数调用的参数，如上面printf和scanf例子中的格式字符串所示。

支持大多数C语言操作符，包括赋值（=）、基本算术（+、-、*、/、%和取反）、前后增减（++、--）、逻辑操作符（!、&&、||）以及比较（<、<=、==、>=、>、!=）。获取变量或数组元素的地址也是可能的（如scanf所需要的），但几乎没有为你做类型检查。

因此，编译器接受下面的代码（和gcc一样，但伴随有警告）。


xxxxxxxxxx
int i;
int j;
i = &j;
printf ("%d\n", "Hello!\n");
printf ("i at %d, j at %d\n", &i, &j);
scanf ("%d", i);

上面代码中的printf调用产生的输出是不可预测的，没有什么价值，但是scanf调用传递的是变量i的值而不是它的地址，因此可能会不可预测地改变内存。在上面的代码中，i先前被设置为j的地址，但这样的小把戏令人困惑且容易出错。

其他缺失的功能的例子包括：指针解读、多维数组、结构、枚举、定义新的类型、声明中的变量初始化、除for循环以外的循环、switch语句和按位操作。凡是在本文件AST部分没有明确提到的AST节点类型，都没有包括在语言中，你不必担心实现它。当然，你也不可能在你想使用编译器的C程序中使用这种功能。

代码生成

你的代码必须为main子程序生成LC-3汇编，并将其打印到stdout。如你所知，像main这样的C函数由变量声明和语句组成。变量声明将被翻译成一个符号表，你的代码在为每条语句生成汇编代码时必须使用这个符号表。堆栈框架将已经为你设置好，并在你的代码完成后被撕掉。请确保执行堆栈框架的拆解——不要在你生成的代码中直接插入RET指令。

这个MP并不打算要求你进行大量的LC-3编程。你编写的每个递归组件应该不会比实现系统分解的一个步骤更复杂，事实上，你可能想回顾一下我们在课程早期所讲的条件分解和迭代分解的LC-3实现。

除了语句之外，代码生成中的大部分工作都涉及计算表达式的结果。为了简化你的任务，你被要求使用堆栈来计算所有的表达式。你可能还记得，任何表达式都可以使用堆栈和一些基本规则进行计算。要 "执行 "一个字面操作数，如看到一个数字，就把操作数推到栈上。要 "执行 "一个操作数，从堆栈中取出操作数，将操作数应用于这些操作数，然后将操作结果推回堆栈。

虽然这种方法产生的LC-3代码将是冗长而低效的，但使用堆栈与递归很好地结合起来，可以直接实现大部分的MP。例如，一个加法运算符的代码（AST220_OP_ADD，如后文所述）执行以下操作序列：

操作序列
生成代码以产生加法的第一个操作数	(递归调用)
生成代码以产生加法的第二个操作数	(递归调用)
从堆栈中弹出第二个操作数	(打印LC-3指令)
从堆栈中弹出第一个操作数	(打印LC-3指令)
两者相加	(打印一个`ADD`指令)
将结果推入堆栈	(打印LC-3指令)

你产生的LC-3指令必须意识到LC-3寄存器的约定，以及你在代码中做出的可以递归调用它的任何假设。例如，考虑一下如果我们不对表达式使用基于堆栈的方法可能发生的情况：一个给定的二进制运算符可能产生它的第一个操作数并将其放入R0，然后生成代码以产生它的第二个操作数。然而，第二个操作数所需的代码必须避免覆盖R0中的第一个操作数。如果第二个操作数使用的是同一个运算符（例如，1+(2+3)）怎么办？使用堆栈可以避免这种复杂性。

LC-3的寄存器惯例如下：

寄存器惯例
`R0-R3`	可供你的代码使用
`R4`	全局数据指针
`R5`	`main`的堆栈框架指针
`R6`	堆栈指针
`R7`	由`JSR/JSRR`使用

还请注意，为你提供的汇编例程在被调用时确实改变了某些寄存器的值。(详情见下一节)。

C语言库

为了避免你在LC-3中实现功能，我们编写并提供了一个小型函数库，以支持你在生成汇编代码时使用。该库包括四个可以直接从C语言中使用的接口和另外三个接口，供你在实现基本运算时使用。在C语言中可见的调用如下。


xxxxxxxxxx
int printf (const char* format, ...); /* assembly label PRINTF */
int rand ();                          /* assembly label RAND */
int scanf (const char* format, ...);  /* assembly label SCANF */
void srand (int new_seed);            /* assembly label SRAND */

这些调用具有C风格的接口：参数必须以正确的顺序放入堆栈，而返回值将在堆栈中。除了R6（递减以存储返回值）和R7（由JSR改变），这些子程序没有改变任何寄存器的值。正如课堂上所描述的，调用这些函数中的任何一个返回后，调用者要负责从堆栈中删除参数。

printf和scanf例程以标准方式工作，但只支持少量的转义：


`%d`	打印/扫描作为十进制整数的参数
`%%`	打印/扫描单个%字符
`\n`	打印/扫描换行
`\\`	打印/扫描一个单一的\字符

printf例程返回打印的字符数。scanfrand $0$ $2^{15}-1$ 之间的伪随机数，srand例程为rand使用的伪随机数发生器设置种子。

为你定义的算术函数有基于寄存器的接口。这三个函数都是对R0和R1的二进制运算，并且都在R0中返回运算的结果。除了R0（返回值）和R7（由JSR改变），这些子程序没有改变任何寄存器的值。这些例程的内容如下：


DIVIDE	用`R0`除以`R1`，四舍五入，并将结果存入`R0`
MODULUS	计算`R0%R1`（C语言定义），并将结果存入`R0`
MULTIPLY	`R0`乘以`R1`，将结果存入`R0`

所有这七个库的例程都使用堆栈来存储调用保存的寄存器。

抽象语法树

抽象语法树（AST）是中间表示法的一种形式，被用作编译器前端和后端之间的接口。回顾一下，编译器的前端将高级语言（如C）翻译成中间表示，而后端将中间表示翻译成汇编代码。你在这个任务中的工作是为一个基于AST的中间表示法编写一个LC-3后端。

AST是一个基于指针的数据结构，由代表原始代码中的语句和表达式的节点组成。在你的编译器中使用的结构如下：


xxxxxxxxxx
typedef struct ast220_t ast220_t;
struct ast220_t {
    ast220_type_t type; /* type of AST node */
    int32_t value; /* a number (PUSH_INT, DEBUG_MARKER) */
    char* name; /* a string (PUSH_STR, VARIABLE) */
    ast220_builtin_func_t fnum; /* function number (FUNC_CALL) */
    ast220_t* test; /* test condition (IF_STMT, FOR_STMT) */
    ast220_t* left; /* left child/first operand */
    ast220_t* middle; /* middle child (FOR_STMT) */
    ast220_t* right; /* right child/second operand */
    ast220_t* next; /* next AST node */
};

AST节点的type字段（ast220_t结构）指定了代表哪种节点。例如，一个AST节点可能代表一个if语句，而第二个节点代表一个变量引用，第三个节点代表一个加法操作。一般来说，AST节点的类型决定了结构中其他字段的含义（或没有含义）。这个规则的例外是next字段，它被用来连接AST节点，代表代码块中的连续语句，以及函数调用中的连续参数。

为你的编译器定义了AST节点的两个一般类别：语句和表达式。编译器支持的C语言的子集是最小的，因此只有五种语句类型是可能的：

上表中没有定义的字段没有任何意义，不应假定其持有任何特定的值（例如，NULL）。唯一的语句类型，从你使用C语言的经验来看可能不是很清楚的是AST220_DEBUG_MARKER，它只是一个调试辅助工具，旨在帮助你进行编程。如果你在你的C程序中加入一个DEBUG(20);形式的语句，一个AST220_DEBUG_MARKER类型的AST节点将出现在它的位置上（value为20），这反过来又能在汇编输出中生成一个标记该点的汇编注释（使用一个已经为你写好的例程）。

表达式节点包括我们的C语言子集所支持的所有运算符，以及整数和字符串常量、变量引用等的节点。最简单的表达式包括常量、变量引用和函数调用，它们的AST类型如下表所示。一般来说，为表达式AST节点生成的代码（递归）应该把表达式的结果留在堆栈的顶部。

AST220_VARIABLE节点很特别，它既可用于表达式，也可用于变量的值和地址。在一般的表达式中，你应该假定变量的值必须被找到并推到堆栈中。当AST220_VARIABLE节点是下一页顶部表格中的一个类型的子节点时，变量的地址就会发挥作用。在这些情况下，你应该直接处理该变量，而不是把它当作一般的表达式（也就是说，不要递归到你生成任意表达式的代码的例程）。

剩下的AST节点对应的是用于算术、逻辑运算和比较的一元和二元运算符。请记住，我们为你提供了乘法、除法和模的汇编代码子程序。

$0$ $0$ $A=0x4000$ $B=0x8000$ $A<B$ $B$ $A - B = 0x4000 - 0x8000 = 0xC000 < 0$ ，这是对的。

符号表

一个符号表将被构建并提供给你。如前所述，AST220_VARIABLE类型的AST节点使用name字段来指定引用的变量名称。在数组变量的情况下，节点的left字段将持有一个计算数组索引的表达式。解析器会检查索引表达式是否总是存在于数组变量中，而从不存在于标量（非数组）变量中。有两个符号表例程是你感兴趣的：


xxxxxxxxxx
void symtab_dump ();
symtab_entry_t* symtab_lookup (const char* vname);

symtab_dump例程的调用是为了将人类可读的符号表副本放入汇编代码输出中，但如果你觉得方便制作额外的副本，你可以再次调用它。然而，这些额外的拷贝应该在你提交代码之前被删除。

symtab_dump例程可以找到与给定变量名称相关的符号表条目。我们不允许变量隐藏（对局部和全局变量使用相同的名字）。符号表项的定义如下：


xxxxxxxxxx
typedef struct symtab_entry_t symtab_entry_t;
struct symtab_entry_t {
    char* name; /* variable name (case sensitive) */
    int array_len; /* size of array (0 = not an array) */
    int is_global; /* global variable (1) or local to main (0) */
    int offset; /* offset with respect to appropriate register */
};

当你生成LC-3指令来操作一个变量时，你必须使用变量符号表项的is_global和offset字段来定位它。正如你可能记得的那样，全局变量是相对于全局数据指针R4的，而局部变量是相对于main框架指针R5的。

$[-16, 15]$ 的范围内。大的数组可能会超出这个区间，但当我们测试你的MP时，任何数组的第一个元素都会落在这个区间内。

独特标签

我们为您提供了在您生成的汇编代码中创建和使用独特标签的功能：


xxxxxxxxxx
ece220_label_t* label_create ();
char* label_value (ece220_label_t* label);

当你需要一个标签时，声明一个类型为ece220_label_t*的变量，通过调用label_create获得一个新标签。要打印标签，可以调用label_value，从标签指针中获得一个字符串表示。

开始工作

在完全阅读完本文件后，进入你的mp11目录，输入make，将所有内容编译成一个名为c220的可执行文件。在这一点上，c220编译器将从一个有效的C程序中产生有效的汇编输出，但主子程序的汇编代码实现除了堆栈帧的设置和拆分外，实际上不会做任何事情。

你的代码会进入mp11.c文件。具体来说，你必须完成函数：


xxxxxxxxxx
void MP11_generate_code (ast220_t* prog);

请注意，除了mp11.c之外，你不能修改任何文件。我们在测试你的代码时不会使用你的任何其他文件。

现有的代码生成

一些生成代码所需的工作已经为你完成，提供给你的mp11.c文件已经包含了大量的必要结构。那里有大约700行，其中大部分是原型和注释。

代码优化不是这个任务的目标，因此任何合理大小的C代码都有可能突破LC-3分支和JSR偏移量的限制。为了避免汇编失败，只有当你知道分支偏移量在范围内时才可以使用分支指令，而且你必须始终使用JSRR而不是JSR。对于分支，为你提供了一个例程，为任意偏移量的 "branch"（即JMP指令）打印一个适当的指令序列：


xxxxxxxxxx
void gen_long_branch (br_type_t type, ece220_label_t* label);

分支类型是在mp11.c文件的开头附近定义的。

在mp11.c中还包含了几个大的开关语句，用于指导通用语句（gen_statement）和表达式（gen_expression）的递归调用。这些开关语句将每种类型的AST节点指向一个小函数，以生成该类型节点的代码。你必须为这些小函数中的大多数编写代码，但有些（六种比较操作）已经为你提供了一个例子。调试标记函数也包括在内。

前半部分

你必须在截止日期前完成两半的所有任务。分开的目的只是为了指导你如何处理这个问题。我们建议你按照这里列出的顺序来做，这将使你能够检查你的进度。

MP11_generate_code：从编写你的代码的主入口点开始。在你写完这个函数之前，mp11.c中的其他函数都不会被调用。ast参数是一个AST节点的链接列表（由next字段链接），代表C程序主函数中的语句。现在你所要做的就是为每一条生成代码。
整数常量：接下来，写代码把一个整数常数推到堆栈上。在这里，你需要玩和提供给你的长分支代码中一样的把戏。就是说，把带有常数的.FILL放到代码中，然后围绕它进行分支。丑陋，但这种方法保证了你的LD指令有一个有效的偏移。
return语句：实现return语句。堆栈框架已经为你设置好了，所以你只需在书中或你的笔记中查找相对偏移量。请记住，在你设置了返回值后，你需要分支到堆栈拆分。在MP11_generate_code中添加代码，将标签放在正确的位置，并在文件范围变量中跟踪标签。一旦你达到这一点，你就可以编译、组装和模拟一个由返回语句组成的程序。调用main的代码也会打印出返回值；试一试，确保你的代码到目前为止是有效的。
取反：取反是最简单的操作之一。从堆栈顶部取出数值，取反它，然后再放回去。为了测试，return -(42)——括号是必要的；不加括号试试就知道为什么。
加法和减法：接下来是另外两个相当简单的堆栈操作。加法和减法取两个值，进行适当的操作，并将结果推回栈上。要确保减法的顺序正确。你可以通过使用返回语句来测试，例如return 10+(40-8);。
字符串常量：处理字符串常量的方式与处理整数常量的方式相同。记住，应该推送字符串的第一个字符的地址。
函数调用：函数调用要花点功夫。首先，注意参数是按照它们在C代码中从右到左的顺序给你的。一旦你把它们都推到了，就用一个JSRR（同样，见所提供的长分支代码）来调用库，然后清理参数，把返回值复制到栈上，成为你唯一留下的东西。现在你可以尝试一下经典的第一个C程序：printf ("Hello, world!\n");
标量变量引用：编写代码来读取一个标量变量并将其推入堆栈。你需要在符号表中查找该变量，以便知道在哪里找到它。现在，你可以假设该变量不是一个数组（或者通过处理两种类型的变量，在第二个检查点上获得先机）。
标量变量赋值：现在编写代码来处理对标量变量的赋值。同样，现在你可以假设你不需要处理对数组元素的赋值。
pop stack 语句：一个分号前面的C语言表达式是一个语句（这并不像听起来那么无用，因为 a=10 是一个表达式）。这个表达式在堆栈上留下了一个值，必须丢弃这个值才能完成语句。你所需要做的就是弹出堆栈。

一旦你完成了这些任务，你的编译器将能够使用涉及加法、减法、取反和标量变量的表达式处理赋值和返回语句。你还可以使用对printf的调用来打印出结果。试着用几个不同的程序来检查程序是否正常。

后半部分

你还必须完成以下任务，尽管我们建议你在进行这些任务之前，先让前半部分工作起来。

乘法、除法和取模：从一些更多的二进制运算符开始。对于这些，与其自己实现这些运算，不如简单地调用（使用JSRR）提供给你的C库。
数组变量引用：现在回到你的变量引用代码中，处理对数组变量的访问。记住，符号表中的偏移量是到数组的开始，所以你需要加入C代码中提供的任何索引（这是一个必须被计算的表达式）。
数组变量赋值：再次回到你的赋值代码中，处理对数组变量的赋值。如果你还没有这样做，试着编译一些使用新运算符以及数组的代码，以检查你是否正确地生成了代码。请确保同时尝试局部和全局变量。
递增和递减：这些运算符有四种，要求你读取一个变量（可能是一个数组条目），修改它，写回它，并在栈上返回一个结果。在继续前进之前，要小心并测试它们。
for 语句：如果你不记得for循环是如何工作的，你可能想在书中或笔记中找找看。注意，在我们的编译器中，初始化和更新AST节点是语句，这样你就不必在gen_for_statement中从栈中弹出结果。测试条件是一个正则表达式，因为你必须在产生它之后对它进行测试。主体是一个语句的链接列表。把它们放在正确的顺序上，记住在C语言中任何非零的东西都是真的，并且在循环体很长的情况下使用长分支。
获取变量地址：对于scanf的调用，你需要能够传递变量地址。写一个函数，找到一个变量的地址，无论是标量还是数组元素，并把它推到堆栈上。
if 语句。和for语句一样，在实现这个语句之前，你可能要先查一下LC-3对条件分解的实现。测试是一个表达式，then和else块是链接的语句列表，其中任何一个都可能是空的（但在这种情况下你不需要优化你的代码）。
逻辑操作。逻辑NOT、OR和AND操作比你已经实现的运算符要复杂一些。首先，它们的结果总是0或1，你必须确保你生成的代码能将正确的值放在堆栈上。其次，OR和AND都需要捷径，这意味着只有当第一个表达式允许它改变逻辑运算的结果时，第二个表达式才被计算。例如，如果OR的第一个操作数为真，第二个操作数就不会被计算。

评分

细节待定，但大致上85%在功能上，15%在注释和文字上。编译你的代码时产生的任何警告将导致同样的扣分（10%）。

请注意，这些规则与以前的MP基本相同。你的所有代码必须包含在你的库的mp/mp11子目录中的mp11.c文件中。我们不会给任何其他名称的文件打分。

一如既往，你的函数必须能够被多次调用并产生正确的结果，所以我们建议你避免使用任何静态存储（否则你可能会失去大部分/全部的功能点）。

执行编译器

如果你在虚拟机内工作，你必须确保解析器编译器——一种叫做Bison的工具——已经被安装。要做到这一点，请输入


xxxxxxxxxx
sudo apt install bison

编译器，c220，然后接受来自键盘的代码输入，并将汇编语言输出到显示屏上。要覆盖这一行为，例如，要读取一个程序，对其进行编译，并产生一个带有汇编代码的文件，请输入（例如）以下内容：


xxxxxxxxxx
cat tests/testprog.c | ./c220 > testprog.asm

然后你可以检查testprog.asm文件--确保只看 "STUDENT CODE "标签之间的内容，因为其余部分是自动生成的库代码。或者你可以用lc3as来组装它，然后用lc3sim来执行它。

你也可以自己编写简单的C语言程序，并通过编译器运行它们。只支持C语言的一个子集，但请尽情享受吧！