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; }

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

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用于根据类型确定是哪条移动(赋值)指令,有movimovfmovcmovb

6 控制流翻译

6.1 回填技术

types.h中定义goto_list类型,用于回填表结构,即t_listf_listn_list(对应教材上的 )。其中存放待回填目标地址的跳转指令的地址列表。并定义相关函数,前两个new_goto_listmerge_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 布尔表达式

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