2021-06-05

编译原理实验：中间代码生成

点此下载源代码

实验所给文法如下：

其中 包括 int, float, char, bool 四种类型。

1 改写文法

1.1 修改错误

由于在 中定义了数组类型，但是赋值表达式中未体现，因此这里不实现数组类型，将 改为

由于 中只涉及四则运算、负数、取反，没有布尔表达式的求值和逻辑运算，因此也将 、 、 、 、 、 放入 的运算中。

由于最后的 只可以推出 ，即整数，然而 中也支持浮点、字符、布尔型，因此需要新定义一个终结符 表示所有常量。

1.2 改为二义文法

由于二义文法更为精简，且和教材上给的大部分中间代码生成的语法制导定义符合，因此可将原先的文法改为等价的二义文法。首先将 改为如下：

之后将 改为如下：

通过指定运算符的优先级和结合性解决二义文法的移入-规约和规约-规约冲突，在grammar.y规定优先级和结合性如下：

1
2
3
4
5
6
7
%left OR
%left AND
%left EQ NE
%left LT LE GT GE
%left '+' '-'
%left '*' '/'
%right INV NOT

其中 INV 为取负数，NOT 为取逻辑非。

1.3 错误恢复

为了在识别到语法错误时，yacc 不立刻退出，而是继续进行翻译并发现剩下可能的错误，这里在 中加入了错误产生式：

Yacc 会在遇到错误时，一直向前看，直到遇到分号（即这条错误语句结束）后，将前面的错误规约为 ，之后接着翻译后面的内容，从而实现错误恢复。

1.4 综合属性

由于 yacc 采用自底向上的 LR 翻译方案，因此设置每个非终结符和终结符具有如下的综合属性，在types.h中定义为yystack结构体：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
typedef struct yystack
{
    char name[MAXLEN];
    constant_val val;
    type type;
    int addr;
    goto_list *t_list;
    goto_list *f_list;
    goto_list *n_list;
} yystack;

#define YYSTYPE yystack

其中

属性名含义
name终结符 的名称
val终结符 的常量值
type终结符和非终结符的类型，有 int, float, char, bool
addr非终结符对应的临时变量所在的地址
t_list条件为真时，待回填目标地址的跳转指令列表，对应教材的
f_list条件为假时，待回填目标地址的跳转指令列表，对应教材的
n_list该语句结束时，待回填目标地址的跳转指令列表，对应教材的

2 词法分析

在lexer.l中，对于 终结符，设置相应的类型属性并返回：

1
2
3
4
int     { yylval.type = INT; return BASIC; }
float   { yylval.type = FLOAT; return BASIC; }
char    { yylval.type = CHAR; return BASIC; }
bool    { yylval.type = BOOL; return BASIC; }

对于常量 ，也设置相应的类型，并根据不同类型用不同的方法解析常量值。整数和浮点数通过atoi和atof实现，字符型取字符串的第二个字符（第一个是单引号），而布尔型则直接设置：

1
2
3
4
5
true    { yylval.type = BOOL; yylval.val.boolean = true; return CONST; }
false   { yylval.type = BOOL; yylval.val.boolean = false; return CONST; }
{num}   { yylval.type = INT; yylval.val.num = atoi(yytext); return CONST; }
{real}  { yylval.type = FLOAT; yylval.val.real = atof(yytext); return CONST; }
{char}  { yylval.type = CHAR; yylval.val.ch = yytext[1]; return CONST; }

对于 ，直接将匹配结果复制到 name 属性，其类型需要句法分析时才能确定。

1
{id}    { strcpy(yylval.name, yytext); return ID; }

匹配标识符、整数、浮点数、字符的正则表达式定义如下，支持浮点数的 E 表示法。

1
2
3
4
id      [A-Za-z][0-9A-Za-z]*
num     [0-9]+
real    [0-9]+(\.[0-9]+)?(E[+-]?[0-9]+)?
char    '.'

3 标识符和常量

3.1 符号表

在types.h中定义标识符、符号表和相关函数如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct symbol
{
    char name[MAXLEN];
    type type;
    int addr;
    int width;
    struct symbol *next;
} symbol;

typedef struct symbol_list
{
    symbol *head;
    struct symbol_list *prev;
    int begin;
    int end;
} symbol_list;

symbol *new_symbol(symbol_list *list, char *name, type type);
symbol *find_symbol(symbol_list *list, char *name);
symbol *find_local_symbol(symbol_list *list, char *name);
symbol_list *new_symbol_list(symbol_list *prev, int addr);
void print_symbol_list(symbol_list *list);
void delete_symbol_list(symbol_list *list);

其中，标识符结构体记录了标识符的名称、类型、所在地址、占据的内存宽度信息，并记录下一个符号的指针，形成链表。由于标识符的定义可以出现在不同的 中，且最里层的 可以引用当前层以及上层 的所有已定义的标识符，因此需要保存符号表的上一级符号表指针prev。

通过修改 的产生式，实现不同层级符号表的动态创建和删除：

其中slist为全局变量，表示当前最外层的 的符号表。

grammar.y中具体实现如下：当第一次建立符号表时，需要指定符号表的起始地址。这里用SYMBOL_BEGIN表示，为 1000。之后的符号表从上一级符号表的末尾地址开始。当符号表被释放前，调用print_symbol_list打印当前的符号表。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
block   : '{' begin decls stmts end '}'
begin   :
        {
            if (slist == NULL)
                slist = new_symbol_list(NULL, SYMBOL_BEGIN);
            else
                slist = new_symbol_list(slist, slist->end);
        }
end     :
        {
            symbol_list *slist2 = slist;
            if (error == 0)
                print_symbol_list(slist2);
            slist = slist2->prev;
            delete_symbol_list(slist2);
        }

3.2 常量表

常量表与符号表类似，但是只需要一个全局常量表clist即可，从地址编号 3000（CONSTANT_BEGIN）开始，不需要保存层级关系，相关函数定义如下：

1
2
3
4
5
constant *new_constant(constant_list *list, constant_val val, type type);
constant *find_constant(constant_list *list, constant_val val, type type);
constant_list *new_constant_list(int addr);
void print_constant_list(constant_list *list);
void delete_constant_list(constant_list *list);

3.2 标识符声明和引用

标识符是在句法分析到声明（declaration）时加入到符号表的。因为这时候才可以知道标识符的类型。

其中new_symbol函数创立一个新标识符，并通过当前的符号表信息指定新标识符的地址，通过类型确定新的标识符占据的宽度。在插入到符号表时，还应考虑是否有重复定义的标识符。因为内层同名的标识符会被外层覆盖，因此只需查找当前层的符号表即可，通过find_local_symbol函数实现当前层的符号表查找。语义规则的具体实现在grammar.y中如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
decl    : BASIC ID ';'
        {
            if (find_local_symbol(slist, $2.name) == NULL)
                new_symbol(slist, $2.name, $1.type);
            else
            {
                char msg[MAXLEN];
                sprintf(msg, "duplicate declearation of symbol \"%s\"", $2.name);
                yyerror(msg);
            }
        }

引用标识符时，将标识符的属性赋值给当前的非终结符即可：

当然也要检查符号是否已经被定义，否则报错，但是可以立刻插入一个新的符号进行错误恢复处理，具体实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
expr    : ID
        {
            symbol *id = find_symbol(slist, $1.name);
            if (id == NULL)
            {
                char msg[MAXLEN];
                sprintf(msg, "undeclared symbol \"%s\"", $1.name);
                yyerror(msg);
                id = new_symbol(slist, $1.name, INT);
            }
            $$.type = id->type;
            $$.addr = id->addr;
        }

3.3 常量的引用

对于常量，出现时需要同时加入到全局常量表clist并将其属性赋值给非终结符：

针对重复引用相同常量的问题，在new_constant的函数内部加入了对重复常量的判断。当常量值和类型均相同时，直接返回原先的常量。具体实现与标识符的引用类似。

4 四元组和三地址码

4.1 四元组表

四元组由运算符 op，参数 arg1，arg2，结果 result(arg3)构成。在types.h中定义四元组和四元组列表结构体如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
typedef struct quadruple
{
    int op;
    int arg1;
    int arg2;
    int arg3;
    char code[4 * MAXLEN];
} quadruple;

typedef struct quadtable
{
    quadruple *buf;
    int size;
    int bufsize;
} quadtable;

quadtable *new_quadtable();
void print_quadtable(quadtable *table);
void delete_quadtable(quadtable *table);

其中四元组的code字段用于存放三地址码。四元组表的buf用于存放四元组。用于向四元组表中插入四元组的代码，并且生成对应四元组的中间代码。

4.2 增量翻译

使用增量翻译的方式，实现教材上的 函数。定义如下，其中 arg1、arg2 和 arg3 均为参数的内存地址。

1
void gen(quadtable *table, symbol_list *slist, constant_list *clist, int op, int arg1, int arg2, int arg3)

该函数具体实现步骤如下。首先，四元组表的大小采用动态内存分配的方式，如果大小不够，则在插入时进行realloc：

1
2
3
4
5
if (table->size == table->bufsize)
{
    table->bufsize += MAXLEN;
    table->buf = realloc(table->buf, table->bufsize);
}

之后，依次进行赋值，插入当前的四元组。如果 arg1、arg2、arg3 的值为 -1，则说明未使用到该参数，或者该参数待回填。

1
2
3
4
5
6
quadruple *t = table->buf + table->size;
t->op = op;
t->arg1 = arg1;
t->arg2 = arg2;
t->arg2 = arg2;
t->arg3 = arg3;

插入后，需要生成该条四元组对应的中间代码。中间代码的地址为当前四元组表的大小加上代码的起始地址CODE_BEGIN，这里设为 100。首先通过arg_name函数查找符号表和常量表，将 arg1、arg2 和 arg3 从内存地址转成对应的符号名称或者常量的字符串表示。如果 arg 的值为 -1，对应空字符串，用于后续的回填。

1
2
3
4
5
6
7
int addr = table->size + CODE_BEGIN;
char code1[MAXLEN];
char code2[MAXLEN];
char code3[MAXLEN];
arg_name(code1, slist, clist, t->arg1);
arg_name(code2, slist, clist, t->arg2);
arg_name(code3, slist, clist, t->arg3);

之后，根据运算符的不同，生成不同形式的三地址中间代码。因为使用了回填法，中间代码采用每行一个标号，而非 L0、L1 的形式。

 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
33
34
35
36
37
38
39
40
41
42
switch (t->op)
{
case movi:
case movf:
case movc:
case movb:
    sprintf(t->code, "%d:\t%s = %s\n", addr, code3, code1);
    break;
case addi:
case addf:
    sprintf(t->code, "%d:\t%s = %s + %s\n", addr, code3, code1, code2);
    break;
    ...
case and:
    sprintf(t->code, "%d:\t%s = %s && %s\n", addr, code3, code1, code2);
    break;
    ...
case eq:
    sprintf(t->code, "%d:\t%s = %s == %s\n", addr, code3, code1, code2);
    break;
        ...
case invi:
case invf:
    sprintf(t->code, "%d:\t%s = -%s\n", addr, code3, code1);
    break;
case not:
    sprintf(t->code, "%d:\t%s = !%s\n", addr, code3, code1);
    break;
case ftoi:
case ctoi:
case btoi:
    sprintf(t->code, "%d:\t%s = (int)%s\n", addr, code3, code1);
    break;
    ...
case jmp:
    sprintf(t->code, "%d:\tgoto %s\n", addr, code3);
    break;
    ...
case jle:
    sprintf(t->code, "%d:\tif %s <= %s goto %s\n", addr, code1, code2, code3);
    break;
}

这里定义了运算符的枚举类型，mov 系列为赋值运算，add 系列为加法运算，inv 系列为取负数运算，to 系列为类型转换运算，j 系列为跳转和分支指令。后面的 i、f、c、b 后缀对应 int、float、char、bool 类型。如果分支指令需要回填，由于 -1 地址对应的字符串为空字符串，可以直接在原先的字符串后覆盖换行符并追加内容。

5 表达式翻译

5.1 临时变量

用于实现教材的 。首先，维护全局变量temp_count表示当前临时变量的下标。之后生成临时变量名，并和new_symbol一样的方式将其加入到当前的符号表中，最后返回生成的临时变量的地址：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int new_temp(symbol_list *list, type type)
{
    symbol *id = malloc(sizeof(symbol));
    sprintf(id->name, "_t%d", temp_count++);
    id->type = type;
    id->width = type_width[type];
    id->addr = list->end;
    list->end += id->width;
    id->next = list->head;
    list->head = id;
    return id->addr;
}

5.2 类型转换

用于实现教材的 函数和 函数。

在types.h中定义了如下的枚举类型和转换矩阵conv，对应类型转换的 op，例如conv[INT][FLOAT] = conv[0][1] = itof，即表示整数转浮点数的指令。-1 表示无需转换。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
typedef enum type
{
    INT,
    FLOAT,
    CHAR,
    BOOL
} type;

int conv[4][4] = {
    {-1, itof, itoc, itob},
    {ftoi, -1, ftoc, ftob},
    {ctoi, ctof, -1, ctob},
    {btoi, btof, btoc, -1}};

之后，编写widen函数。该函数首先根据转换前后的类型判断是否需要转换，如果不需要转换，直接返回原来的参数地址，否则通过new_temp添加一个新的中间变量，并通过gen生成一条类型转换的中间代码，返回中间变量的地址。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int widen(quadtable *table, symbol_list *slist, constant_list *clist, int addr, type type1, type type2)
{
    int op = conv[type1][type2];
    if (op != -1)
    {
        int arg3 = new_temp(slist, type2);
        gen(table, slist, clist, op, addr, -1, arg3);
        return arg3;
    }
    return addr;
}

接下来，定义了max数组，表示两个类型的数值进行四则运算时，结果的类型应为如何，用于为上述类型转换提供依据。

1
2
3
4
5
6
int max[4][4] = {
    {INT, FLOAT, INT, INT},
    {FLOAT, FLOAT, FLOAT, FLOAT},
    {INT, FLOAT, CHAR, INT},
    {INT, FLOAT, INT, BOOL}
};

例如max[CHAR][FLOAT] = MAX[2][1] = FLOAT，即字符类型和浮点类型运算后的结果应是浮点类型。

5.3 四则运算

以加法为例：

首先，需要通过max数组确定结果的类型。之后，通过widen函数对源操作数进行类型转换（如果需要）。并新建一个中间变量保存表达式的结果，并将该中间变量的地址赋值给非终结符 的地址属性。最后，通过gen函数增量翻译该语句，生成中间代码。具体实现如下：

1
2
3
4
5
6
7
8
9
expr    : expr '+' expr
        {
            $$.type = max[$1.type][$3.type];
            int arg1 = widen(table, slist, clist, $1.addr, $1.type, $$.type);
            int arg2 = widen(table, slist, clist, $3.addr, $3.type, $$.type);
            int arg3 = new_temp(slist, $$.type);
            gen(table, slist, clist, _add[$$.type], arg1, arg2, arg3);
            $$.addr = arg3;
        }

其中_add数组用于根据类型确定采用哪条加法指令，即addi还是addf。减法、乘法、除法均类似，只是gen中的运算符不同。

5.4 布尔运算

由于这里的布尔运算出现在 的产生式，而非 的产生式中，因此只需考虑布尔运算的值。与四则运算类似，但是 预先指定为BOOL，而非使用max数组确定。

5.5 单目运算符和括号

对于取逻辑非操作，也是将类型预先设为BOOL，而对于取负数操作，则将类型设为操作数和INT的最大值，这是因为对于浮点数，取反之后还是浮点数，对于整数、字符、布尔类型，取反之后会变成正数。同时，由于只有一个操作数，因此在使用gen增量翻译的时候，需要将arg2设为 -1。

对于括号，则更简单，直接将属性原封不动的赋值给产生式左部的非终结符即可：

具体实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
expr    : '!' expr %prec NOT
        {
            $$.type = BOOL;
            int arg1 = widen(table, slist, clist, $2.addr, $2.type, $$.type);
            int arg3 = new_temp(slist, $$.type);
            gen(table, slist, clist, not, arg1, -1, arg3);
            $$.addr = arg3;
        }
        | '-' expr %prec INV
        {
            $$.type = max[$2.type][INT];
            int arg1 = widen(table, slist, clist, $2.addr, $2.type, $$.type);
            int arg3 = new_temp(slist, $$.type);
            gen(table, slist, clist, _inv[$$.type], arg1, -1, arg3);
            $$.addr = arg3;
        }
        | '(' expr ')'
        {
            $$.type = $2.type;
            $$.addr = $2.addr;
        }

5.6 赋值语句

表达式计算完成后，可能需要将其赋值给已定义的标识符。但是 这里仍然涉及类型转换，需要通过widen将表达式的类型转换成标识符本身的类型（如果需要），并生成赋值的中间代码：

此外，还需要考虑标识符是否已定义。如果在所有的符号表中均为查询到，则报错，但是可以立即新建一个标识符进行错误恢复。具体实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
stmt    : ID '=' expr ';'
        {
            $$.n_list = NULL;
            symbol *id = find_symbol(slist, $1.name);
            if (id == NULL)
            {
                char msg[MAXLEN];
                sprintf(msg, "undeclared symbol \"%s\"", $1.name);
                yyerror(msg);
                id = new_symbol(slist, $1.name, INT);
            }
            int arg1 = widen(table, slist, clist, $3.addr, $3.type, id->type);
            int arg3 = id->addr;
            gen(table, slist, clist, _mov[id->type], arg1, -1, arg3);
        }

其中_mov用于根据类型确定是哪条移动（赋值）指令，有movi、movf、movc、movb。

6 控制流翻译

6.1 回填技术

在types.h中定义goto_list类型，用于回填表结构，即t_list、f_list、n_list（对应教材上的 、 、 ）。其中存放待回填目标地址的跳转指令的地址列表。并定义相关函数，前两个new_goto_list和merge_goto_list分别对应教材上的 、 函数。

1
2
3
4
5
6
7
8
9
typedef struct goto_list
{
    int addr;
    struct goto_list *next;
} goto_list;

goto_list *new_goto_list(int addr);
goto_list *merge_goto_list(goto_list *list1, goto_list *list2);
void delete_goto_list(goto_list *list);

同时，实现教材的回填函数 如下：对于给定的回填表和回填地址，访问位于四元表中的四元组，修改其跳转指令的目的地址（第三个参数arg3），并且修改已经生成的中间代码，在后面追加回填地址的字符串形式：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void backpatch(quadtable *table, goto_list *list, int addr)
{
    while (list != NULL)
    {
        quadruple *t = table->buf + list->addr;
        t->arg3 = addr;
        sprintf(t->code + strlen(t->code) - 1, "%d\n", addr);
        list = list->next;
    }
}

6.2 布尔表达式

对于布尔表达式，需要为 非终结符维护 和 。采用布尔运算符“短路”的方法翻译布尔表达式，为此需将产生式进一步做适当的改写：