编译原理第五次实验
2024年6月21日...大约 6 分钟
编译原理第五次实验
一、实验目的
通过在词法分析，语法分析和语义分析程序的基础上，将源代码翻译成中间代码，认识中间代码的表示形式和生成中间代码的原理和技巧，掌握中间代码生成器的构造原理和语法制导翻译的实现方法。
二、实验内容
用Bison进行语法分析的基础上，编写一个中间代码生成程序。**（文法定义**见教材附录 A.1，p394）
三、实现方案
需要考虑以下方面：
- 中间代码形式
中间代码采用三地址码形式，实现时用四元式存储四个字段：
(op, arg1, arg2, result)
- 变量声明的处理
在符号表中存储相关变量的变量名、类型、分配内存地址（偏移量值）；
先考虑基本类型的变量，若有时间再实现数组类型。
可参考教材2.7符号表的内容，为每个作用域设置一个符号表。
- 语句
语句分为赋值语句（包括算术表达式）和控制流语句（包括布尔表达式）。
本实验难度教大，分两阶段进行。
第一阶段：声明和赋值语句的翻译。赋值语句的实现只涉及综合属性，顺序声称三地址码，参考P232图6-20，用函数gen()构造一条三地址指令实现。在表达式中进行类型检查，实现自动类型转换功能。数组元素访问可以选做。
第二阶段：控制流语句的翻译。控制流需要回填跳转指令的转向地址，可选择实现部分语句（if、if-else、while）。
1. 第一阶段 声明和赋值语句的翻译
对于Exlab5_1内的compile_assign.y，需要修改以下部分：
- 三地址码的生成： /* 把四元式所对应的三地址代码写入到文件中 */
switch( op ) {
case OIntAdd :
case OFloatAdd :
if( op==OIntAdd ) ch = '+';
else if (op==OFloatAdd) ch = '+';
sprintf(str,"[%d] = [%d] %c [%d]", ptr->arg3, ptr->arg1, ch, ptr->arg2);
printf("%s = %s %c %s\n", ptr->arg3name, ptr->arg1name, ch, ptr->arg2name);
break;
case OIntSub :
case OFloatSub :
if( op==OIntSub ) ch = '-';
else if (op==OFloatSub) ch = '-';
sprintf(str,"[%d] = [%d] %c [%d]", ptr->arg3, ptr->arg1, ch, ptr->arg2);
printf("%s = %s %c %s\n", ptr->arg3name, ptr->arg1name, ch, ptr->arg2name);
break;
case OIntMultiply :
case OFloatMultiply :
if( op==OIntMultiply ) ch = '*';
else if (op==OFloatMultiply) ch = '*';
sprintf(str,"[%d] = [%d] %c [%d]", ptr->arg3, ptr->arg1, ch, ptr->arg2);
printf("%s = %s %c %s\n", ptr->arg3name, ptr->arg1name, ch, ptr->arg2name);
break;
case OIntDivide :
case OFloatDivide :
if( op==OIntDivide ) ch = '/';
else if (op==OFloatDivide) ch = '/';
sprintf(str,"[%d] = [%d] %c [%d]", ptr->arg3, ptr->arg1, ch, ptr->arg2);
printf("%s = %s %c %s\n", ptr->arg3name, ptr->arg1name, ch, ptr->arg2name);
break;
case OIntEvaluation :
case OFloatEvaluation :
sprintf(str,"[%d] = [%d]", ptr->arg3, ptr->arg1);
printf("%s = %s\n", ptr->arg3name, ptr->arg1name);
break;
case OCharEvaluation :
case OBoolEvaluation :
sprintf(str,"[%d] = [%d]", ptr->arg3, ptr->arg1);
printf("%s = %s\n", ptr->arg3name, ptr->arg1name);
break;
case OGoto :
sprintf(str,"goto [%d]", ptr->arg3);
printf("goto %s\n", ptr->arg3name);
break;
case OGTGoto :
case OGEGoto :
case OLTGoto :
case OLEGoto :
case OEQGoto :
case ONEQGoto :
sprintf(str,"if [%d] goto [%d]", ptr->arg1, ptr->arg3);
printf("if %s goto %s\n", ptr->arg1name, ptr->arg3name);
break;
case HALT :
sprintf(str, "HALT");
printf("HALT\n");
break;
default: yyerror("程序错误：出现不认识的运算符！"); strcpy(str, "error: Unknown operator");break;
}增加了对浮点数、减法、乘法、除法等的处理
- 表达式识别处理
expr : expr '+' expr
{ printf("产生式：expr->expr + expr\n");
char *name;
int p;
if( $1.expr.type == $3.expr.type)
{
$$.expr.type = $1.expr.type ;
$$.expr.width = $1.expr.type == INT ? INT_WIDTH : FLOAT_WIDTH;
$$.expr.addr = NewTemp(TopSymbolList, $$.expr.str, $$.expr.width);
Gen($1.expr.type == INT ? OIntAdd : OFloatAdd, $1.expr.addr, $3.expr.addr, $$.expr.addr,$1.expr.str,$3.expr.str,$$.expr.str);
}
else
{
yyerror("类型不匹配");
}
}
| expr '-' expr
{ printf("产生式：expr->expr - expr\n");
char *name;
int p;
if( $1.expr.type == $3.expr.type)
{
$$.expr.type = $1.expr.type ;
$$.expr.width = $1.expr.type == INT ? INT_WIDTH : FLOAT_WIDTH;
$$.expr.addr = NewTemp(TopSymbolList, $$.expr.str, $$.expr.width);
Gen($1.expr.type == INT ? OIntSub : OFloatSub, $1.expr.addr, $3.expr.addr, $$.expr.addr,$1.expr.str,$3.expr.str,$$.expr.str);
}
else
{
yyerror("类型不匹配");
}
}
| expr '*' expr
{ printf("产生式：expr->expr * expr\n");
char *name;
int p;
if( $1.expr.type == $3.expr.type)
{
$$.expr.type = $1.expr.type ;
$$.expr.width = $1.expr.type == INT ? INT_WIDTH : FLOAT_WIDTH;
$$.expr.addr = NewTemp(TopSymbolList, $$.expr.str, $$.expr.width);
Gen($1.expr.type == INT ? OIntMultiply : OFloatMultiply, $1.expr.addr, $3.expr.addr, $$.expr.addr,$1.expr.str,$3.expr.str,$$.expr.str);
}
else
{
yyerror("类型不匹配");
}
}
| expr '/' expr
{ printf("产生式：expr->expr / expr\n");
char *name;
int p;
if( $1.expr.type == $3.expr.type)
{
$$.expr.type = $1.expr.type ;
$$.expr.width = $1.expr.type == INT ? INT_WIDTH : FLOAT_WIDTH;
$$.expr.addr = NewTemp(TopSymbolList, $$.expr.str, $$.expr.width);
Gen($1.expr.type == INT ? OIntDivide : OFloatDivide, $1.expr.addr, $3.expr.addr, $$.expr.addr,$1.expr.str,$3.expr.str,$$.expr.str);
}
else
{
yyerror("类型不匹配");
}
}
| ID
{
struct SymbolElem * p;
printf("产生式：expr ->id\n");
p = LookUpAllSymbolList( TopSymbolList, $1.id.name );
if( p != NULL ) {
strcpy( $$.factor.str, p->name );
$$.expr.type = p->type;
$$.expr.addr = p->addr;
$$.expr.width = p->width;
}
else {
yyerror( "变量名没有定义" );
strcpy( $$.factor.str, "no_id_defined" ); /*容错处理*/
$$.expr.type = INT;
$$.expr.addr = -1;
$$.expr.width = INT_WIDTH;
}
}
| CONST
{
struct ConstElem * p;
printf("产生式：factor->CONST\n");
strcpy( $$.factor.str, $1.constval.str );
$$.expr.type = INT; // 默认为整型常量
$$.expr.addr = 3000; // 默认常量地址3000
$$.expr.width = INT_WIDTH;
}
| ID '[' expr ']'
{
struct SymbolElem * p;
printf("产生式：expr -> id [ expr ]\n");
p = LookUpAllSymbolList( TopSymbolList, $1.id.name );
if( p != NULL ) {
if( $3.expr.type == INT ) {
strcpy( $$.factor.str, p->name );
$$.expr.type = p->type;
$$.expr.addr = p->addr + $3.expr.addr * p->width;
$$.expr.width = p->width;
} else {
yyerror("数组下标必须是整型");
}
} else {
yyerror( "数组名没有定义" );
strcpy( $$.factor.str, "no_array_defined" ); /*容错处理*/
$$.expr.type = INT;
$$.expr.addr = -1;
$$.expr.width = INT_WIDTH;
}
}
;运行测试
测试代码：
{
int i;
int j;
i = 2.7;
j = 10.9;
i = i - j / i * 2;
j = j+1;
}运行结果：
生成的四元式：
2. 第二阶段 控制流语句的翻译
在Exlab2中compile_sim.y的基础上，加入第一阶段的成果，实现浮点数、减法、乘法等
接着
- 首先是对rel部分进行修改，实现翻译多种关系运算
rel
: expr RELOP_LT expr
{
printf("产生式：rel -> expr < expr\n");
$$.rel.truelist = makelist(QuadTable.startaddr + QuadTable.len);
$$.rel.falselist = makelist(QuadTable.startaddr + QuadTable.len + 1);
Gen(OLTGoto, $1.expr.addr, $3.expr.addr, 0, $1.expr.str, $3.expr.str, "_");
Gen(OGoto, 0, 0, 0, "", "", "_");
}
| expr RELOP_LE expr
{
printf("产生式：rel -> expr <= expr\n");
$$.rel.truelist = makelist(QuadTable.startaddr + QuadTable.len);
$$.rel.falselist = makelist(QuadTable.startaddr + QuadTable.len + 1);
Gen(OLEGoto, $1.expr.addr, $3.expr.addr, 0, $1.expr.str, $3.expr.str, "_");
Gen(OGoto, 0, 0, 0, "", "", "_");
}
| expr RELOP_GT expr
{
printf("产生式：rel -> expr > expr\n");
$$.rel.truelist = makelist(QuadTable.startaddr + QuadTable.len);
$$.rel.falselist = makelist(QuadTable.startaddr + QuadTable.len + 1);
Gen(OGTGoto, $1.expr.addr, $3.expr.addr, 0, $1.expr.str, $3.expr.str, "_");
Gen(OGoto, 0, 0, 0, "", "", "_");
}
| expr RELOP_GE expr
{
printf("产生式：rel -> expr >= expr\n");
$$.rel.truelist = makelist(QuadTable.startaddr + QuadTable.len);
$$.rel.falselist = makelist(QuadTable.startaddr + QuadTable.len + 1);
Gen(OGEGoto, $1.expr.addr, $3.expr.addr, 0, $1.expr.str, $3.expr.str, "_");
Gen(OGoto, 0, 0, 0, "", "", "_");
}
| expr RELOP_EQ expr
{
printf("产生式：rel -> expr == expr\n");
$$.rel.truelist = makelist(QuadTable.startaddr + QuadTable.len);
$$.rel.falselist = makelist(QuadTable.startaddr + QuadTable.len + 1);
Gen(OEQGoto, $1.expr.addr, $3.expr.addr, 0, $1.expr.str, $3.expr.str, "_");
Gen(OGoto, 0, 0, 0, "", "", "_");
}
| expr RELOP_NEQ expr
{
printf("产生式：rel -> expr != expr\n");
$$.rel.truelist = makelist(QuadTable.startaddr + QuadTable.len);
$$.rel.falselist = makelist(QuadTable.startaddr + QuadTable.len + 1);
Gen(ONEQGoto, $1.expr.addr, $3.expr.addr, 0, $1.expr.str, $3.expr.str, "_");
Gen(OGoto, 0, 0, 0, "", "", "_");
}
| expr
{
printf("产生式：rel -> expr\n");
$$.rel.addr = $1.expr.addr;
strcpy($$.rel.str, $1.expr.str);
}
;- 然后修改stmt实现IF-ELSE和WHILE
stmt : ID '=' expr ';'
{ printf("产生式：stmt->id = expr;\n");
struct SymbolElem * p;
p = LookUpAllSymbolList( TopSymbolList, $1.id.name );
if( p != NULL ) {
strcpy( $$.factor.str, p->name );
$$.factor.type = p->type;
$$.factor.addr = p->addr;
$$.factor.width = p->width;
Gen(OIntEvaluation , $3.expr.addr, 0, p->addr, $3.expr.str, "", p->name);
}
else {
yyerror( "变量名没有定义" );
strcpy( $$.factor.str, "no_id_defined" ); /*容错处理*/
$$.factor.type = INT;
$$.factor.addr = -1;
$$.factor.width = INT_WIDTH;
Gen(OIntEvaluation , $3.expr.addr, 0, p->addr, $3.expr.str, "", p->name);
$$.stmt.nextlist = NULL;
}
}
| IF '(' bool ')' M stmt
{
printf("产生式：stmt->if (bool) stmt\n");
backpatch($3.bool.truelist,$5.M.instr);
$$.stmt.nextlist = merge($3.bool.falselist,$6.stmt.nextlist);
}
| IF '(' bool ')' M stmt ELSE N stmt
{
printf("产生式：stmt->if (bool) M stmt else N stmt\n");
backpatch($3.bool.truelist, $5.M.instr);
backpatch($3.bool.falselist, $8.M.instr);
$$.stmt.nextlist = merge($6.stmt.nextlist, $9.stmt.nextlist);
}
| WHILE M '(' bool ')' N stmt
{
printf("产生式：stmt->while M (bool) N stmt\n");
backpatch($7.stmt.nextlist, $2.M.instr);
backpatch($4.bool.truelist, $6.M.instr);
$$.stmt.nextlist = $4.bool.falselist;
Gen(OGoto, -1, -1, $2.M.instr, "", "", "_");
}
| block { printf("产生式：stmt->block\n");
$$.stmt.nextlist = $1.block.nextlist;
}
;运行测试
测试代码：
{
int i;
int j;
i = 2;
j = 10;
if (i <100)
{
i = i + 2;
if (j<20)
j = j+1;
}
else
{
i = i*2;
}
while (i>0) {
i = i-1;
}
}运行结果
Powered by Waline v3.4.1