Pwn进你的心
0%

编译原理-Lab3

Posted on Edited on In 28k 25 mins.

第一个任务

通过前面对 AST 遍历，完成了语义分析后，如果没有语法语义错误，就可以再次对 AST 进行遍历，计算相关的属性值，建立符号表，并生成以三地址代码 TAC 作为中间语言的中间语言代码序列

在这里对本实验的实现做了一些限制，假设数据类型只包含整数类型，不包含如浮点数、数组、结构和指针等其它数据类型

实验目标：完成语义分析的下半部分，以根据 AST 生成中间语言 TAC

三地址代码 TAC

中间语言（中间代码）是一种面向语法，易于翻译成目标程序的等效内部表示代码（二进制码）

其可理解性及易于生成目标代码的程度介于源语言和目标语言之间

三地址中间代码 TAC 是一个4元组，逻辑上包含 (op、opn1、opn2、result)：

  • op：表示操作类型说明
  • opn1 和 opn2：表示2个操作数
  • result：表示运算结果

后续还需要根据 TAC 序列生成目标代码，所以设计其存储结构时，每一部分要考虑目标代码生成时所需要的信息

表 4-1 中间代码定义：

语法 描述 Op Opn1 Opn2 Result
LABEL x 定义标号 x LABEL X
FUNCTION f: 定义函数 f FUNCTION F
x := y 赋值操作 ASSIGN X X
x := y + z 加法操作 PLUS Y Z X
x := y - z 减法操作 MINUS Y Z X
x := y * z 乘法操作 STAR Y Z X
x := y / z 除法操作 DIV Y Z X
GOTO x 无条件转移 GOTO X
IF x [relop] y GOTO z 条件转移 [relop] X Y Z
RETURN x 返回语句 RETURN X
ARG x 传实参 x ARG X
x:=CALL f 调用函数 CALL F X
PARAM x 函数形参 PARAM X
READ x 读入 READ X
WRITE x 打印 WRITE X
  • 运算符：
    • 表示这条指令需要完成的运算，可以用枚举常量表示，如 PLUS 表示双目加，JLE 表示小于等于，PARAM 表示形参，ARG 表示实参等
  • 操作数与运算结果：
    • 这些部分包含的数据类型有多种，整常量，实常量，还有使用标识符的情况，如变量的别名、变量在其数据区的偏移量和层号、转移语句中的标号等
    • 类型不同，所以考虑使用联合，为了明确联合中的有效成员，将操作数与运算结果设计成结构类型，包含 kind，联合等几个成员，kind 说明联合中的有效，联合成员是整常量，实常量或标识符表示的别名或标号或函数名等
  • 为了配合后续的 TAC 代码序列的生成，将 TAC 代码作为数据元素，用双向循环链表表示 TAC 代码序列

翻译模式

翻译模式：把语义规则（也称为语义动作），用花括号 {} 括起来，插入到产生式右部的合适位置上，进一步细化了语义计算的时机

翻译模式用于指明各个符号的具体含义，当 “词法分析” 和 “语法分析” 都执行完毕以后，程序便会开始 “语义分析”，其大概包含以下两个步骤：

  • 生成符号表，并进行：重复检查，未声明/定义检查，类型匹配检查
  • 为 AST 的各个节点类型编写“含义”（根据翻译模式对各个节点的意义进行解释）

翻译模式共有两种：

  • S-翻译模式：
    • 只涉及到综合属性，语义动作集置于产生式右端的末尾
    • 常采用 LR 的自底向上的分析法，和S-属性文法类似
  • L-翻译模式：
    • 包含综合属性，也可以包含继承属性
    • 必须满足以下条件：
      • 产生式右部符号的继承属性，其语义计算必须位于该符号前，且语义动作不访问右边符号的属性
      • 产生式左部符号的综合属性只有在它所引用的所有属性都计算出来之后才可以计算，计算这种属性的动作通常放在产生式的末尾
      • 继承属性只能依赖于兄长的属性、父亲的继承属性、自身的属性
      • 属性间的依赖图不能形成环路

本实验将会采用S-翻译模式和 LR(1) 文法：

  • 基础文法 LL(1)：自顶向下计算
  • 基础文法 LR(1)：自底向上计算

属性计算

在遍历过程中，需要根据翻译模式给出的计算方法完成属性的计算，本实验中设置的属性如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct node
{                     
    ......
    int level;                  // 层号
    int place;                  // 表示结点对应的变量或运算结果符号表的位置序号
    char Etrue[15], Efalse[15]; // 对布尔表达式的翻译时，真假转移目标的标号
    char Snext[15];             // 该结点对饮语句执行后的下一条语句位置标号
    struct codenode *code;      // 该结点中间代码链表头指针
    char op[10];
    int type;   // 结点对应值的类型
    int pos;    // 语法单位所在位置行号
    int offset; // 偏移量
    int width;  // 占数据字节数
    int num;	// 记录个数
};
  • .place：记录该结点操作数在符号表中的位置序号，每次完成了计算后，中间结果需要用一个临时变量保存，临时变量也需要登记到符号表中（返回局部变量会生成一个临时变量，即没有名字的变量）
  • .type：记录数据的类型，用于表达式的计算中，该属性也可用于语句，表示语句语义分析的正确性（OK或ERROR）
  • .offset：记录外部变量在静态数据区中的偏移量，以及局部变量和临时变量在活动记录中的偏移量（另外对函数，这项保存活动记录的大小）
  • .width：记录一个结点表示的语法单位中，定义的变量和临时单元所需要占用的字节数，方便计算变量、临时变量在活动记录中偏移量，以及最后计算函数活动记录的大小
  • .code：记录中间代码序列的起始位置，如采用链表表示中间代码序列，该属性就是一个链表的头指针
  • .Etrue 和 .Efalse：在完成布尔表达式翻译时，表达式值为真假时要转移的程序位置（标号的字符串形式）
  • .Snext：该结点的语句序列执行完后，要转移的程序位置（标号的字符串形式）

这一步非常复杂，如果有必要的话，我们需要对每个类型的节点都设置一个函数，用于解析它本身的语义：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
void semantic_Analysis(struct node *T){
    if (T)
    {
        switch (T->kind)
        {
        case EXT_DEF_LIST: // 外部定义列表
            ext_def_list(T);
            break;
        case EXT_VAR_DEF: // 外部变量声明
            ext_var_def(T);
            break;
        case FUNC_DEF: // 函数定义
            func_def(T);
            break;
        case FUNC_DEC: // 函数声明
            func_dec(T);
            break;
        case PARAM_LIST: // 参数定义列表
            param_list(T);
            break;
        case PARAM_DEC: // 参数定义
            param_dec(T);
            break;
        case COMP_STM: // 复合语句
            comp_stm(T);
            break;
        case DEF_LIST: // 定义列表
            def_list(T);
            break;
        case VAR_DEF: // 定义
            var_def(T);
            break;
        case STM_LIST: // 语句列表
            stmt_list(T);
            break;
        case IF_THEN: // IF ELSE-IF语句
            if_then(T);
            break; 
        case IF_THEN_ELSE: // IF ELSE语句
            if_then_else(T);
            break;
        case WHILE: // WHILE语句
            while_dec(T);
            break;
        case FOR: // FOR语句(改动)
            for_dec(T);
            break;    
        case FOR_DEC: // FOR语句列表(新添)
            for_list(T);
            break;  
        case EXP_STMT: // 表达式语句
            exp_stmt(T);
            break;
        case RETURN: // 返回
            return_dec(T);
            break;
        case ID:
        case STRUCT_TAG: // 结构体(新添)
        case INT:
        case FLOAT:
        case CHAR:
        case STRING:
        case ASSIGNOP:
        case AND:
        case OR:
        case RELOP:
        case PLUS:
        case PPLUS: // 加加(改名)
        case PLUSASSIGNOP: // 加等于(改名)
        case MINUS:
        case MMINUS: // 减减(改名)
        case MINUSASSIGNOP: // 减等于(改名)
        case STAR:
        case STARASSIGNOP: // 乘等于(改名)
        case DIV:
        case DIVASSIGNOP: // 除等于(改名)
        case NOT:
        case UMINUS:
        case FUNC_CALL:
        case EXP_ARRAY:
            Exp(T); //处理基本表达式
            break;
        }
    }
}
  • 上述展示的节点类型并不完整，有些类型的处理函数会出现在其子函数中

这里要补充一下：和上个实验相比，新填了3个节点：

  • STRUCT_TAG：结构体名称
1
2
3
4
5
OptTag	: {$$=NULL;}
		| ID {$$=mknode(STRUCT_TAG,NULL,NULL,NULL,yylineno);strcpy($$->struct_name,$1);}
		;
Tag	: ID {$$=mknode(STRUCT_TAG,NULL,NULL,NULL,yylineno);strcpy($$->struct_name,$1);}
	;
  • STRUCT_DEF：结构体定义
  • STRUCT_DEC：结构体声明
1
2
3
StructSpecifier : STRUCT OptTag LC DefList RC {$$=mknode(STRUCT_DEF,$2,$4,NULL,yylineno);}
			   | STRUCT Tag  {$$=mknode(STRUCT_DEC,$2,NULL,NULL,yylineno);}
			   ;

修改了1个节点：（另外几个只是改了名字，代码没有变）

  • FOR：FOR 语句
1
2
3
4
5
6
7
8
Stmt:   Exp SEMI    {$$=mknode(EXP_STMT,$1,NULL,NULL,yylineno);}
      | CompSt      {$$=$1;}     
      | RETURN Exp SEMI   {$$=mknode(RETURN,$2,NULL,NULL,yylineno);}
      | IF LP Exp RP Stmt %prec LOWER_THEN_ELSE   {$$=mknode(IF_THEN,$3,$5,NULL,yylineno);}
      | IF LP Exp RP Stmt ELSE Stmt   {$$=mknode(IF_THEN_ELSE,$3,$5,$7,yylineno);}
      | WHILE LP Exp RP Stmt {$$=mknode(WHILE,$3,$5,NULL,yylineno);}
      | FOR LP ForDec RP Stmt {$$=mknode(FOR,$3,$5,NULL,yylineno);}
      ;
  • ForDec：FOR 语句列表
1
2
3
ForDec: Exp SEMI Exp SEMI Exp {$$=mknode(FOR_DEC,$1,$3,$5,yylineno);}
       | SEMI Exp SEMI {$$=mknode(FOR_DEC,NULL,$2,NULL,yylineno);}
       ;

中间代码的生成

核心结构体如下：

1
2
3
4
5
6
struct codenode
{   /* 三地址TAC代码结点 */
    int op;                        // TAC代码的运算符种类
    struct opn opn1, opn2, result; // 2个操作数和运算结果
    struct codenode *next, *prior; // 采用双向循环链表存放中间语言代码
};
  • 用于描述操作数的结构体如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct opn
{
    int kind; // 标识操作的类型
    int type; // 标识操作数的类型
    union {
        int const_int;     // 整常数值,立即数
        float const_float; // 浮点常数值,立即数
        char const_char;   // 字符常数值,立即数
        char *const_string;
        char id[33]; // 变量或临时变量的别名或标号字符串
        struct Array *type_array;
        struct Struct *type_struct;
    };
    int level;  // 变量的层号,0表示是全局变量,数据保存在静态数据区
    int offset; // 变量单元偏移量,或函数在符号表的定义位置序号,目标代码生成时用
};

中间代码生成的过程其实就是完成 codenode 双向链表，其中的 opn1, opn2, result 需要根据 “表 4-1 中间代码定义” 来进行填写

接下来就按照逻辑顺序，依次展示各个节点的中间代码的生成过程

全局变量定义（本实验的外部变量就是全局变量）

EXT_DEF_LIST：外部定义列表（EXT_VAR_DEF | ARRAY_DEF | FUNC_DEF，EXT_DEF_LIST）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void ext_def_list(struct node *T)
{
    if (!T->ptr[0])
        return;

    T->ptr[0]->offset = T->offset; // 语义分析之前先设置偏移地址
    semantic_Analysis(T->ptr[0]); // 访问外部定义列表中的第一个
    T->code = T->ptr[0]->code; // 之后会合并code

    if (T->ptr[1]) /* 第2棵子树指向下一个EXT_DEF_LIST节点,可为NULL */
    {
        T->ptr[1]->offset = T->ptr[0]->offset + T->ptr[0]->width;
        semantic_Analysis(T->ptr[1]); // 访问该外部定义列表中的其它外部定义
        T->code = merge(2, T->code, T->ptr[1]->code); // 合并code
    }
}
  • 函数 merge：合并多个中间代码的双向循环链表，首尾相连

EXT_VAR_DEF：外部变量声明（TYPE，EXT_DEC_LIST）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void ext_var_def(struct node *T)
{
    if (!strcmp(T->ptr[0]->type_id, "int")) /* 变量类型判断 */
    {
        T->type = T->ptr[1]->type = INT;
        T->ptr[1]->width = 4; /* 解释该类型的实际大小 */
    }
    if (!strcmp(T->ptr[0]->type_id, "float"))
    {
        T->type = T->ptr[1]->type = FLOAT;
        T->ptr[1]->width = 8;
    }
    if (!strcmp(T->ptr[0]->type_id, "char"))
    {
        T->type = T->ptr[1]->type = CHAR;
        T->ptr[1]->width = 1;
    }
    T->ptr[1]->offset = T->offset; 				// 这个外部变量的偏移量向下传递
    ext_var_list(T->ptr[1]);                        // 处理外部变量中的标识符序列
    T->width = (T->ptr[1]->width) * T->ptr[1]->num; // 计算这个外部变量声明的宽度
    T->code = NULL;                                 // 这里假定外部变量不支持初始化
}
  • EXT_DEC_LIST 节点中可能记录了类型相同的多个变量声明，需要递归处理
  • 假定全局变量不支持初始化，因此不需要设置中间代码 code

EXT_DEC_LIST：变量名称列表（ID，EXT_DEC_LIST）

ID：变量名称（ID）

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
void ext_var_list(struct node *T)
{
    int rtn, num = 1;
    switch (T->kind)
    {
    case EXT_DEC_LIST: /* EXT_DEC_LIST节点必然存在两棵子树 */
        T->ptr[0]->type = T->type;                //将类型属性向下传递变量结点
        T->ptr[0]->offset = T->offset;            //外部变量的偏移量向下传递
        T->ptr[1]->type = T->type;                //将类型属性向下传递变量结点
        T->ptr[1]->offset = T->offset + T->width; //外部变量的偏移量向下传递
        T->ptr[1]->width = T->width;
        ext_var_list(T->ptr[0]); /* 进入ID */
        ext_var_list(T->ptr[1]); /* 进入EXT_DEC_LIST */
        T->num = T->ptr[1]->num + 1;
        break;
    case ID:
        rtn = fillSymbolTable(T->type_id, newAlias(), LEV, T->type, 'V', T->offset); // 最后一个变量名
        if (rtn == -1)
            semantic_error(T->pos, T->type_id, "变量重复定义，语义错误");
        else
            T->place = rtn;
        T->num = 1;
        break;
    default:
        break;
    }
}
  • 函数 fillSymbolTable：根据 name 查符号表，不能重复定义：
    • 重复定义，则返回 -1
    • 不重复定义，则填表并返回符号在符号表中的位置序号

分析以上这3个函数的流程，就可以大概清楚属性计算的流程，在遍历 AST 的过程中就可以自下而上来分析节点属性

函数定义

FUNC_DEF：函数定义（TYPE，FUNC_DEC，COMP_STM）

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
void func_def(struct node *T)
{
    if (!strcmp(T->ptr[0]->type_id, "int"))
    {
        T->ptr[1]->type = INT;
    }
    if (!strcmp(T->ptr[0]->type_id, "float"))
    {
        T->ptr[1]->type = FLOAT;
    }
    if (!strcmp(T->ptr[0]->type_id, "char"))
    {
        T->ptr[1]->type = CHAR;
    }
    T->width = 0;            //函数的宽度设置为0,不会对外部变量的地址分配产生影响
    T->offset = DX;			//设置局部变量在活动记录中的偏移量初值
    semantic_Analysis(T->ptr[1]);  //处理函数名和参数结点部分(不考虑寄存器传参)
    T->offset += T->ptr[1]->width; //用形参单元宽度修改函数局部变量的起始偏移量
    T->ptr[2]->offset = T->offset;
    strcpy(T->ptr[2]->Snext, newLabel()); //函数体语句执行结束后的位置属性
    semantic_Analysis(T->ptr[2]);         //处理函数体结点
    //计算活动记录大小,这里offset属性存放的是活动记录大小,不是偏移
    symbolTable.symbols[T->ptr[1]->place].offset = T->offset + T->ptr[2]->width;
    T->code = merge(3, T->ptr[1]->code, T->ptr[2]->code, genLabel(T->ptr[2]->Snext)); //函数体的代码作为函数的代码
}
  • 函数 newLabel：生成一个标号，标号命名形式为 “LABEL+序号”
  • 函数 genLabel：生成标号语句

FUNC_DEC：函数声明（PARAM_LIST）

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
void func_dec(struct node *T)
{
    int rtn;
    struct opn opn1, opn2, result;
    rtn = fillSymbolTable(T->type_id, newAlias(), LEV, T->type, 'F', 0); //函数不在数据区中分配单元,偏移量为0
    if (rtn == -1)
    {
        semantic_error(T->pos, T->type_id, "函数名重复使用，可能是函数重复定义，语义错误");
        return;
    }
    else
        T->place = rtn;
    result.kind = ID;
    strcpy(result.id, T->type_id);
    result.offset = rtn;
    T->code = genIR(FUNCTION, opn1, opn2, result); //生成中间代码:FUNCTION 函数名
    T->offset = DX;                                //设置形式参数在活动记录中的偏移量初值
    if (T->ptr[0]) /* 判断是否有参数 */
    { 
        T->ptr[0]->offset = T->offset;
        semantic_Analysis(T->ptr[0]); //处理函数参数列表
        T->width = T->ptr[0]->width;
        symbolTable.symbols[rtn].paramnum = T->ptr[0]->num;
        T->code = merge(2, T->code, T->ptr[0]->code); //连接函数名和参数代码序列
    }
    else
        symbolTable.symbols[rtn].paramnum = 0, T->width = 0;
}
  • 函数 genIR：生成一条 TAC 的中间代码语句
    • 一般情况下，TAC 中涉及到2个运算对象和运算结果
    • 如果是局部变量或临时变量，表示在运行时，其对应的存储单元在活动记录中，这时需要将其偏移量 offset 和数据类型同时带上，方便最后的目标代码生成
    • 全局变量也需要带上偏移量
  • 查中间代码表可知 “FUNCTION 函数名” 不需要 opn1 opn2，只需要 result

PARAM_LIST：参数定义列表（PARAM_DEC）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void param_list(struct node *T)
{
    T->ptr[0]->offset = T->offset;
    semantic_Analysis(T->ptr[0]);
    if (T->ptr[1])
    {
        T->ptr[1]->offset = T->offset + T->ptr[0]->width;
        semantic_Analysis(T->ptr[1]);
        T->num = T->ptr[0]->num + T->ptr[1]->num;             //统计参数个数
        T->width = T->ptr[0]->width + T->ptr[1]->width;       //累加参数单元宽度
        T->code = merge(2, T->ptr[0]->code, T->ptr[1]->code); //连接参数代码
    }
    else
    {
        T->num = T->ptr[0]->num;
        T->width = T->ptr[0]->width;
        T->code = T->ptr[0]->code;
    }
}

PARAM_DEC：参数定义（TYPE，ID）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void param_dec(struct node *T)
{
    int rtn;
    struct opn opn1, opn2, result;
    rtn = fillSymbolTable(T->ptr[1]->type_id, newAlias(), 1, T->ptr[0]->type, 'P', T->offset);
    if (rtn == -1)
        semantic_error(T->ptr[1]->pos, T->ptr[1]->type_id, "参数名重复定义,语义错误");
    else
        T->ptr[1]->place = rtn;
    T->num = 1;                                //参数个数计算的初始值
    T->width = T->ptr[0]->type == INT ? 4 : 8; //参数宽度
    result.kind = ID;
    strcpy(result.id, symbolTable.symbols[rtn].alias);
    result.offset = T->offset;
    T->code = genIR(PARAM, opn1, opn2, result); //生成:PARAM 形参名
}
  • 生成形式参数的中间代码

COMP_STM：复合语句（DEF_LIST，STM_LIST）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void comp_stm(struct node *T)
{
    LEV++; //设置层号加1,并且保存该层局部变量在符号表中的起始位置在symbol_scope_TX
    symbol_scope_TX.TX[symbol_scope_TX.top++] = symbolTable.index;
    T->width = 0;
    T->code = NULL;
    if (T->ptr[0])
    {
        T->ptr[0]->offset = T->offset;
        semantic_Analysis(T->ptr[0]); //处理该层的局部变量DEF_LIST
        T->width += T->ptr[0]->width;
        T->code = T->ptr[0]->code;
    }
    if (T->ptr[1])
    {
        T->ptr[1]->offset = T->offset + T->width;
        strcpy(T->ptr[1]->Snext, T->Snext); //S.next属性向下传递
        semantic_Analysis(T->ptr[1]); //处理复合语句的语句列表STM_LIST
        T->width += T->ptr[1]->width;
        T->code = merge(2, T->code, T->ptr[1]->code);
    }
    LEV--; //出复合语句,层号减1
    symbolTable.index = symbol_scope_TX.TX[--symbol_scope_TX.top]; //删除该作用域中的符号
}
  • symbol_scope_TX 是一个存放 symbolTable.index 的栈结构

表达式

下面给一个通用表达式 Exp 的案例：

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
43
44
45
46
47
48
49
void Exp(struct node *T)
{
    if (T)
    {
        switch (T->kind)
        {
            case ID: // 名称(符号)
                id_exp(T);
                break;
            case CHAR: // char类型
                char_exp(T);
                break;
            case INT: // int类型
                int_exp(T);
                break;
            case FLOAT: // float类型
                float_exp(T);
                break;
            case ASSIGNOP: // 赋值
                assignop_exp(T);
                break;
            case PPLUS: // 加减
            case MMINUS: // 减减
                oop_exp(T);
                break;
            case AND: // 且
            case OR: // 或
            case RELOP: // 二元运算符
                relop_exp(T);
                break;
            case PLUSASSIGNOP: // 加等于
            case MINUSASSIGNOP: // 减等于
            case STARASSIGNOP: // 乘等于
            case DIVASSIGNOP: // 除等于
            case PLUS: // 加
            case MINUS: // 减
            case STAR: // 乘
            case DIV: // 除
                op_exp(T);
                break;
            case FUNC_CALL: //根据T->type_id查出函数的定义,如果语言中增加了实验教材的read,write需要单独处理一下
                func_call_exp(T);
                break;
            case ARGS: //此处仅处理各实参表达式的求值的代码序列,不生成ARG的实参系列
                args_exp(T);
                break;
        }
    }
}

表达式 Exp 的类型很多，这里只选择几个简单分析：

ID：名称（NULL）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void id_exp(struct node *T)
{
    int rtn;

    rtn = searchSymbolTable(T->type_id);
    if (rtn == -1)
        semantic_error(T->pos, T->type_id, "变量未声明定义就引用，语义错误");
    if (symbolTable.symbols[rtn].flag == 'F')
        semantic_error(T->pos, T->type_id, "是函数名，不是普通变量，语义错误");
    else
    {
        T->place = rtn; //结点保存变量在符号表中的位置
        T->code = NULL; //标识符不需要生成TAC
        T->type = symbolTable.symbols[rtn].type;
        T->offset = symbolTable.symbols[rtn].offset;
        T->width = 0; //未再使用新单元
    }
}

INT：int 类型（其他基础类型同理）

1
2
3
4
5
6
7
8
9
10
11
12
void int_exp(struct node *T){
    struct opn opn1, opn2, result;
    T->place = temp_add(newTemp(), LEV, T->type, 'T', T->offset); //为整常量生成一个临时变量
    T->type = INT;
    opn1.kind = INT;
    opn1.const_int = T->type_int;
    result.kind = ID;
    strcpy(result.id, symbolTable.symbols[T->place].alias);
    result.offset = symbolTable.symbols[T->place].offset;
    T->code = genIR(ASSIGNOP, opn1, opn2, result);
    T->width = 4;
}
  • 返回局部变量会生成一个临时变量，由于 int 和 float 会参与计算，因此需要一个临时变量来存储计算的结果
  • 函数 temp_add：填写临时变量到符号表，返回临时变量在符号表中的位置

ASSIGNOP：赋值（ID，Exp）

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
void assignop_exp(struct node *T)
{
    struct opn opn1, opn2, result;
    if (T->ptr[0]->kind != ID)
    {
        semantic_error(T->pos, "", "赋值语句没有左值，语义错误");
    }
    else
    {
        Exp(T->ptr[0]); //处理左值,例中仅为变量
        T->ptr[1]->offset = T->offset;
        Exp(T->ptr[1]); //处理右值
        T->type = T->ptr[0]->type;
        T->width = T->ptr[1]->width;
        T->code = merge(2, T->ptr[0]->code, T->ptr[1]->code);

        opn1.kind = ID;
        strcpy(opn1.id, symbolTable.symbols[T->ptr[1]->place].alias); //右值一定是个变量或临时变量
        opn1.offset = symbolTable.symbols[T->ptr[1]->place].offset;
        result.kind = ID;
        strcpy(result.id, symbolTable.symbols[T->ptr[0]->place].alias);
        result.offset = symbolTable.symbols[T->ptr[0]->place].offset;
        T->code = merge(2, T->code, genIR(ASSIGNOP, opn1, opn2, result)); //生成:x := y
    }
}
  • 生成赋值语句的中间代码

FUNC_CALL：函数调用（ARGS）

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
43
44
45
46
47
48
49
void func_call_exp(struct node *T)
{
    int rtn,width;
    struct node *T0;
    struct opn opn1, opn2, result;
    rtn = searchSymbolTable(T->type_id);
    if (rtn == -1)
    {
        semantic_error(T->pos, T->type_id, "函数未定义，语义错误");
        return;
    }
    if (symbolTable.symbols[rtn].flag != 'F')
    {
        semantic_error(T->pos, T->type_id, "不是函数名，不能进行函数调用，语义错误");
        return;
    }
    T->type = symbolTable.symbols[rtn].type;
    width = T->type == INT ? 4 : 8; //存放函数返回值的单数字节数
    if (T->ptr[0]) //有调用参数
    {
        T->ptr[0]->offset = T->offset;
        Exp(T->ptr[0]);                      //处理所有实参表达式,求值及类型
        T->width = T->ptr[0]->width + width; //累加上计算实参使用临时变量的单元数
        T->code = T->ptr[0]->code;
    }
    else //无调用参数
    {
        T->width = width;
        T->code = NULL;
    }
    match_param(rtn, T->ptr[0]); //处理所有参数的匹配
    T0 = T->ptr[0];
    while (T0) //处理参数列表的中间代码
    {
        result.kind = ID;
        strcpy(result.id, symbolTable.symbols[T0->ptr[0]->place].alias);
        result.offset = symbolTable.symbols[T0->ptr[0]->place].offset;
        T->code = merge(2, T->code, genIR(ARG, opn1, opn2, result));
        T0 = T0->ptr[1];
    }
    T->place = temp_add(newTemp(), LEV, T->type, 'T', T->offset + T->width - width); /* 临时变量用于存储函数的返回值 */
    opn1.kind = ID;
    strcpy(opn1.id, T->type_id); //保存函数名
    opn1.offset = rtn;           //这里offset用以保存函数定义入口,在目标代码生成时，能获取相应信息
    result.kind = ID;
    strcpy(result.id, symbolTable.symbols[T->place].alias);
    result.offset = symbolTable.symbols[T->place].offset;
    T->code = merge(2, T->code, genIR(CALL, opn1, opn2, result)); //生成:x := CALL 函数名
}
  • 生成函数调用中间代码
  • 函数 match_param：匹配函数参数

ARGS：函数参数（Exp | Exp，Args）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void args_exp(struct node *T)
{
    T->ptr[0]->offset = T->offset;
    Exp(T->ptr[0]);
    T->width = T->ptr[0]->width;
    T->code = T->ptr[0]->code;
    if (T->ptr[1]) //存在多个参数
    {
        T->ptr[1]->offset = T->offset + T->ptr[0]->width;
        Exp(T->ptr[1]); //再次调用args_exp
        T->width += T->ptr[1]->width;
        T->code = merge(2, T->code, T->ptr[1]->code);
    }
}

语句列表

在开始分析选择/循环语句之前需要先分析：STM_LIST

STM_LIST：语句列表（Stmt-语句节点，STM_LIST）

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
void stmt_list(struct node *T)
{
    if (!T->ptr[0])
    {
        T->code = NULL;
        T->width = 0;
        return;
    }              //空语句序列
    if (T->ptr[1]) //2条以上语句连接,生成新标号作为第一条语句结束后到达的位置
        strcpy(T->ptr[0]->Snext, newLabel());
    else //语句序列仅有一条语句,S.next属性向下传递
        strcpy(T->ptr[0]->Snext, T->Snext);
    T->ptr[0]->offset = T->offset;
    semantic_Analysis(T->ptr[0]); /* 分析语句Stmt */
    T->code = T->ptr[0]->code; /* 将分析完毕的语句Stmt-code装回 */
    T->width = T->ptr[0]->width;
    if (T->ptr[1])
    { 
        strcpy(T->ptr[1]->Snext, T->Snext); //2条以上语句连接,S.next属性向下传递
        T->ptr[1]->offset = T->offset; //顺序结构共享单元方式
        semantic_Analysis(T->ptr[1]);
        //序列中第1条为表达式语句,返回语句,复合语句时,第2条前不需要标号
        if (T->ptr[0]->kind == RETURN || T->ptr[0]->kind == EXP_STMT || T->ptr[0]->kind == COMP_STM)
            T->code = merge(2, T->code, T->ptr[1]->code);
        else
            T->code = merge(3, T->code, genLabel(T->ptr[0]->Snext), T->ptr[1]->code);
        if (T->ptr[1]->width > T->width)
            T->width = T->ptr[1]->width; //顺序结构共享单元方式
    }
}
  • 函数 newLabel 会生成一个标号，用于记录 if 语句为真时跳转的位置
  • 只要 STM_LIST 节点的 STM_LIST 子树存在，程序就会给 Stmt 子树分配一个标号
  • 根据代码逻辑，在选择/循环语句后必定有一个 LABEL labeln，用于标记跳转

SEMI：语句（Stmt-语句节点）

语句的类型很多，这里重点分析选择语句和循环语句

选择/循环语句

IF_THEN_ELSE：IF ELSE 语句（Exp，Stmt-语句节点，Stmt-语句节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void if_then_else(struct node *T)
{
    strcpy(T->ptr[0]->Etrue, newLabel()); //设置条件语句真假转移位置
    strcpy(T->ptr[0]->Efalse, newLabel());
    T->ptr[0]->offset = T->ptr[1]->offset = T->ptr[2]->offset = T->offset;
    boolExp(T->ptr[0]); //条件,要单独按短路代码处理
    T->width = T->ptr[0]->width;
    strcpy(T->ptr[1]->Snext, T->Snext);
    semantic_Analysis(T->ptr[1]); //if子句
    if (T->width < T->ptr[1]->width)
        T->width = T->ptr[1]->width;
    strcpy(T->ptr[2]->Snext, T->Snext);
    semantic_Analysis(T->ptr[2]); //else子句
    if (T->width < T->ptr[2]->width)
        T->width = T->ptr[2]->width;
    T->code = merge(6, T->ptr[0]->code, /* Exp子句-code */
                    genLabel(T->ptr[0]->Etrue),
                    T->ptr[1]->code, /* if子句-code */
                    genGoto(T->Snext),
                    genLabel(T->ptr[0]->Efalse), 
                    T->ptr[2]->code); /* else子句-code */
}
  • 函数 genGoto：生成 GOTO 语句，返回头指针
  • 函数 genLabel：生成标号语句
  • 函数 boolExp 用于判断 Exp 是否为真
  • 在 “Exp子句” 中会调用一次 genGoto，根据条件跳转到 “if子句”，否则跳转到 “else子句”
  • 在 “if子句” 中也会调用一次 genGoto，跳转到 “if-else语句” 结束
  • 当 “else子句” 执行完毕时，“if-else语句” 结束
  • 注意：程序将直接执行 boolExp，而不是去分析 T->ptr[0]，这样会导致函数调用无法生效（函数调用的核心代码在 Exp 中）
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
void boolExp(struct node *T)
{
    struct opn opn1, opn2, result;
    int op;
    int rtn;
    if (T)
    {
        switch (T->kind)
        {
            case INT: /* 非'0'则真 */
                if (T->type_int != 0)
                    T->code = genGoto(T->Etrue);
                else
                    T->code = genGoto(T->Efalse);
                T->width = 0;
                break;
            case FLOAT: /* 非'0'则真 */
                if (T->type_float != 0.0)
                    T->code = genGoto(T->Etrue);
                else
                    T->code = genGoto(T->Efalse);
                T->width = 0;
                break;
            case ID: /* 查符号表,获得符号表中的位置(不支持函数调用) */
                rtn = searchSymbolTable(T->type_id);
                if (rtn == -1)
                    semantic_error(T->pos, T->type_id, "变量未定义，语义错误");
                if (symbolTable.symbols[rtn].flag == 'F'){
                    semantic_error(T->pos, T->type_id, "是函数名，不是普通变量，语义错误");
                }
                else
                {
                    opn1.kind = ID;
                    strcpy(opn1.id, symbolTable.symbols[rtn].alias);
                    opn1.offset = symbolTable.symbols[rtn].offset;
                    opn2.kind = INT;
                    opn2.const_int = 0;
                    result.kind = ID;
                    strcpy(result.id, T->Etrue);
                    T->code = genIR(NEQ, opn1, opn2, result);
                    T->code = merge(2, T->code, genGoto(T->Efalse));
                }
                T->width = 0;
                break;
            case RELOP: /* 处理关系运算表达式,2个操作数都按基本表达式处理 */
                T->ptr[0]->offset = T->ptr[1]->offset = T->offset;
                Exp(T->ptr[0]);
                T->width = T->ptr[0]->width;
                Exp(T->ptr[1]);
                if (T->width < T->ptr[1]->width)
                    T->width = T->ptr[1]->width;
                opn1.kind = ID;
                strcpy(opn1.id, symbolTable.symbols[T->ptr[0]->place].alias);
                opn1.offset = symbolTable.symbols[T->ptr[0]->place].offset;
                opn2.kind = ID;
                strcpy(opn2.id, symbolTable.symbols[T->ptr[1]->place].alias);
                opn2.offset = symbolTable.symbols[T->ptr[1]->place].offset;
                result.kind = ID;
                strcpy(result.id, T->Etrue);
                if (strcmp(T->type_id, "<") == 0)
                    op = JLT;
                else if (strcmp(T->type_id, "<=") == 0)
                    op = JLE;
                else if (strcmp(T->type_id, ">") == 0)
                    op = JGT;
                else if (strcmp(T->type_id, ">=") == 0)
                    op = JGE;
                else if (strcmp(T->type_id, "==") == 0)
                    op = EQ;
                else if (strcmp(T->type_id, "!=") == 0)
                    op = NEQ;
                T->code = genIR(op, opn1, opn2, result);
                T->code = merge(4, T->ptr[0]->code, T->ptr[1]->code, T->code, genGoto(T->Efalse));
                break;
            case AND:
            case OR:
                if (T->kind == AND)
                {
                    strcpy(T->ptr[0]->Etrue, newLabel());
                    strcpy(T->ptr[0]->Efalse, T->Efalse);
                }
                else
                {
                    strcpy(T->ptr[0]->Etrue, T->Etrue);
                    strcpy(T->ptr[0]->Efalse, newLabel());
                }
                strcpy(T->ptr[1]->Etrue, T->Etrue);
                strcpy(T->ptr[1]->Efalse, T->Efalse);
                T->ptr[0]->offset = T->ptr[1]->offset = T->offset;
                boolExp(T->ptr[0]);
                T->width = T->ptr[0]->width;
                boolExp(T->ptr[1]);
                if (T->width < T->ptr[1]->width)
                    T->width = T->ptr[1]->width;
                if (T->kind == AND)
                    T->code = merge(3, T->ptr[0]->code, genLabel(T->ptr[0]->Etrue), T->ptr[1]->code);
                else
                    T->code = merge(3, T->ptr[0]->code, genLabel(T->ptr[0]->Efalse), T->ptr[1]->code);
                break;
            case NOT: /* 交换Efalse与Etrue */
                strcpy(T->ptr[0]->Etrue, T->Efalse);
                strcpy(T->ptr[0]->Efalse, T->Etrue);
                boolExp(T->ptr[0]);
                T->code = T->ptr[0]->code;
                break;
            case FUNC_CALL: /* 函数调用(不支持) */
                semantic_error(T->pos, T->type_id, "暂时不支持函数调用");
                break;
            default:
                break;
        }
    }
}

WHILE：WHILE 语句（Exp，Stmt-语句节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void while_dec(struct node *T)
{
    strcpy(T->ptr[0]->Etrue, newLabel()); //子结点继承属性的计算
    strcpy(T->ptr[0]->Efalse, T->Snext);
    T->ptr[0]->offset = T->ptr[1]->offset = T->offset;
    boolExp(T->ptr[0]); //循环条件,要单独按短路代码处理
    T->width = T->ptr[0]->width;
    strcpy(T->ptr[1]->Snext, newLabel());
    semantic_Analysis(T->ptr[1]); //while子句-循环体
    if (T->width < T->ptr[1]->width)
        T->width = T->ptr[1]->width;
    T->code = merge(5, genLabel(T->ptr[1]->Snext), T->ptr[0]->code,
                    genLabel(T->ptr[0]->Etrue), T->ptr[1]->code, genGoto(T->ptr[1]->Snext));
}
  • 程序会在 “Exp子句” 之前写入一个 LABEL labeln
  • 在 “Exp子句” 中会调用一次 genGoto，根据条件跳转到 “while子句”，否则结束 “while语句”
  • 当 “while子句” 结束时会自动跳转到 “Exp子句” 开始新一轮循环

FOR：FOR 语句（FOR_DEC，Stmt-语句节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void for_dec(struct node* T)
{
    strcpy(T->ptr[0]->Etrue, newLabel()); 
    strcpy(T->ptr[0]->Efalse, T->Snext);
    T->ptr[0]->offset = T->ptr[1]->offset = T->offset;
    semantic_Analysis(T->ptr[0]); 
    strcpy(T->ptr[1]->Snext, newLabel());
    semantic_Analysis(T->ptr[1]); 
    if (T->width < T->ptr[1]->width)
        T->width = T->ptr[1]->width;
    T->code = merge(7, T->ptr[0]->ptr[0]->code, 
                    genLabel(T->ptr[1]->Snext), T->ptr[0]->ptr[1]->code,
                    genLabel(T->ptr[0]->ptr[1]->Etrue), T->ptr[1]->code, 
                    T->ptr[0]->ptr[2]->code, genGoto(T->ptr[1]->Snext));
}
  • 函数 for_dec 调用后，函数 for_list 必被调用

ForDec：FOR 语句列表（Exp，Exp，Exp）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void for_list(struct node* T){
    if(T->ptr[0]!=NULL){
        T->ptr[0]->offset = T->ptr[2]->offset = T->offset;
        if(T->ptr[0]->kind == ASSIGNOP){
            semantic_Analysis(T->ptr[0]);
        }
        else{
            semantic_error(T->pos, "", "for wrong\n");
        }
        if(T->ptr[2]->kind != ASSIGNOP){
            semantic_Analysis(T->ptr[2]);
        }
        else{
            semantic_error(T->pos, "", "for wrong\n");
        }
    }

    T->ptr[1]->offset = T->offset; 
    strcpy(T->ptr[1]->Etrue, T->Etrue); 
    strcpy(T->ptr[1]->Efalse, T->Efalse);
    boolExp(T->ptr[1]);
    T->width = T->ptr[0]->width+T->ptr[1]->width+T->ptr[2]->width;
}
  • 不更新 T->code，方便交给 for_dec 函数来控制顺序

基础运算

加减乘除：PLUS，MINUS，STAR，DIV（Exp，Exp）

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
void op_exp(struct node *T)
{
    struct opn opn1, opn2, result;
    T->ptr[0]->offset = T->offset;
    Exp(T->ptr[0]); /* 处理第一个表达式 */
    T->ptr[1]->offset = T->offset + T->ptr[0]->width;
    Exp(T->ptr[1]); /* 处理第二个表达式 */
    /* 判断T->ptr[0],T->ptr[1]类型是否正确
    可能根据运算符生成不同形式的代码,给T的type赋值 */
    T->type = INT, T->width = T->ptr[0]->width + T->ptr[1]->width + 2;

    T->place = temp_add(newTemp(), LEV, T->type, 'T', T->offset + T->ptr[0]->width + T->ptr[1]->width);
    opn1.kind = ID;
    strcpy(opn1.id, symbolTable.symbols[T->ptr[0]->place].alias);
    opn1.type = T->ptr[0]->type;
    opn1.offset = symbolTable.symbols[T->ptr[0]->place].offset;
    opn2.kind = ID;
    strcpy(opn2.id, symbolTable.symbols[T->ptr[1]->place].alias);
    opn2.type = T->ptr[1]->type;
    opn2.offset = symbolTable.symbols[T->ptr[1]->place].offset;
    result.kind = ID;
    strcpy(result.id, symbolTable.symbols[T->place].alias);
    result.type = T->type;
    result.offset = symbolTable.symbols[T->place].offset;
    T->code = merge(3, T->ptr[0]->code, T->ptr[1]->code, genIR(T->kind, opn1, opn2, result)); 
    T->width = T->ptr[0]->width + T->ptr[1]->width + 4;//INT
}
  • 函数 temp_add 生成的临时变量在赋值语句 ASSIGNOP 中才有作用
  • 虽然 T->code 的次序为 opnstr1 opnstr2 op，但在 print_IR 函数打印时可以调整它的次序

加加减减：PPLUS，MMINUS（Exp）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void oop_exp(struct node *T){
    struct opn opn1, opn2, result;
    T->ptr[0]->offset = T->offset;
    Exp(T->ptr[0]);

    T->type = INT, T->width = T->ptr[0]->width;

    opn1.kind = ID;
    strcpy(opn1.id, symbolTable.symbols[T->ptr[0]->place].alias);
    opn1.type = T->ptr[0]->type;
    opn1.offset = symbolTable.symbols[T->ptr[0]->place].offset;

    T->code = merge(2, T->ptr[0]->code, genIR(T->kind, opn1, opn2, result));
    T->width = T->ptr[0]->width;
}

最终的完整代码有 1200 多行，就不放出了

编译与结果

编译命令：

1
2
3
flex lexer.l
bison -d -v parser.y
gcc display.c semantic_analysis.c parser.tab.c lex.yy.c -lfl -o test3

测试文件1：

1
2
3
4
5
6
7
8
9
10
11
int fact(int n){
	int temp;
	temp = n;
	if(n==1)
		n=2;
	else{
		n=3;
	}
	fact(n);
	return n;
}

结果1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
FUNCTION fact :
  PARAM var2
  var3 := var2
  temp1 := #1
  IF var2 == temp1 GOTO label4
  GOTO label5
LABEL label4 :
  temp2 := #2
  var2 := temp2
  GOTO label3
LABEL label5 :
  temp3 := #3
  var2 := temp3
LABEL label3 :
  ARG var2
  temp4 := CALL fact
  RETURN var2
LABEL label1 :

测试文件2：

1
2
3
4
5
6
7
8
9
10
11
int main(char c)
{
	int c1 = 5;
	int c2 = 6;
	int c3 = 7;
	int c4 = 8;
	int c5 = 9;
	
	c3 = (c1+c2*c3)*(c5-c4);
	c1++;
}

结果2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
FUNCTION main :
  PARAM var2
  temp1 := #5
  var3 := temp1
  temp2 := #6
  var4 := temp2
  temp3 := #7
  var5 := temp3
  temp4 := #8
  var6 := temp4
  temp5 := #9
  var7 := temp5
  temp6 := var4 * var5
  temp7 := var3 + temp6
  temp8 := var7 - var6
  temp9 := temp7 * temp8
  var5 := temp9
  var3 := var3 + 1
LABEL label1 :

测试文件3：

1
2
3
4
5
6
7
8
9
10
11
int n;
int main(char c)
{
	int c1 = 5;
	n = 0;

	while(c1>1){
		n = n+1;
	}
	return n;
}

结果3：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
FUNCTION main :
  PARAM var3
  temp1 := #5
  var4 := temp1
  temp2 := #0
  var1 := temp2
LABEL label5 :
  temp3 := #1
  IF var4 > temp3 GOTO label4
  GOTO label3
LABEL label4 :
  temp4 := #1
  temp5 := var1 + temp4
  var1 := temp5
  GOTO label5
LABEL label3 :
  RETURN var1
LABEL label1 :

测试文件4：

1
2
3
4
5
6
7
8
9
10
int main(char c)
{
	int n = 8;
	int i;

	for(i=10;i<n;i++){
		n -= 2;
	}
	return i;
}

结果4：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
FUNCTION main :
  PARAM var2
  temp1 := #8
  var3 := temp1
  temp2 := #10
  var4 := temp2
LABEL label4 :
  IF var4 < var3 GOTO label3
  GOTO label2
LABEL label3 :
  temp3 := #2
  var3 := var3 - temp3
  var4 := var4 + 1
  GOTO label4
LABEL label2 :
  RETURN var4
LABEL label1 :