parser.y

《编译方法》课程设计内容２．《编译方法》课程设计内容

   地址到函数调用语句的四元式代码中. 

   为了简化编译器, 我们没有在整个分析结束后对函数调用语句是否还有没有
   回填, 可以考虑在语法分析结束时检查符号表是否存在这样的符号, 即符号的类型
   是未定义, 而LABEL2非空

   "FUNC fname(args) stmt" 翻译为 "LABELn; BEGINFUNC; args; stmt; 
   ENDFUNC"  */

{
	TAC *tlist ;			 /* The backpatch list */

	TAC *tlab ;			 /* Label at start of function */
	TAC *tbegin ;			 /* BEGINFUNC marker */
	TAC *tend ;			 /* ENDFUNC marker */

	/* 查看函数名的类型,如果不是未定义, 则报错返回, 否则产生函数体的
	   首尾标号语句,对标号语句,形参列表语句和函数体语句的代码进行链接.
	   最后对调用该函数语句的四元式代码进行回填 */

	if( func->type != T_UNDEF )
	{
		error( "function already declared" ) ;
		return NULL ;
	}

	tlab   = mktac( TAC_LABEL,     mklabel( next_label++ ), NULL, NULL ) ;
	tbegin = mktac( TAC_BEGINFUNC, NULL, NULL, NULL ) ;
	tend   = mktac( TAC_ENDFUNC,   NULL, NULL, NULL ) ;

	tbegin->prev = tlab ;
	code         = join_tac( args, code ) ;
	tend->prev   = join_tac( tbegin, code ) ;

	tlist = func->LABEL2 ;			 /* 回填链表的链首 */

	while( tlist != NULL )
	{
		TAC *tnext = tlist->LB ;  	 /* 下一项 */

		tlist->LB  = tlab ;
		tlist      = tnext ;
	}

	func->type   = T_FUNC ;		 /* 定义符号表的各项 */
	func->LABEL2 = tlab ;		 /* LABEL2指向函数的入口地址 */

	return tend ;

}	/* TAC *do_func( SYMB *func,
		     	 TAC  *args,
			 TAC  *code ) */


TAC *declare_var( SYMB *var )

/*  由于变量共享唯一的符号表, 因此任何地方出现的变量不能重名,
    变量声明语句将翻译为: 完成对符号表单元各项的填写,其中offset设为-1,
    表示没有分配实际的内存空间,这部分工作将在代码生成时完成; 产生变量
    声明四元式代码, 该代码的作用是在代码生成时, 对变量分配存储空间,
    注意, 在此我们忽略了变量作用域的定义, 这对一个实用编译器是必不可少的 */


{
	if( var->type != T_UNDEF )
	{
		error( "variable already declared" ) ;
		return NULL ;
	}

	var->type  = T_VAR ;
	var->ADDR2 = -1 ;		 /* 设为无效*/

	/* 生成变量定义四元式代码 */

	return  mktac( TAC_VAR, var, NULL, NULL ) ;

}	/* TAC *declare_var( SYMB *var ) */


TAC *do_assign( SYMB  *var,	 /* 被赋值的变量 */
		ENODE *expr )	 /* 表达式 */

/* 赋值语句的翻译, 首先检查表达式左边的变量是否定义, 如果没有, 系统报错;
   否则, 生成赋值四元式中间代码, 释放表达式结点的内存单元.

   "var := expr"将翻译为: "expr语句; COPY, var, expr" */
 

{
	TAC  *code ;

	/* Warn if variable not declared, then build code */

	if( var->type != T_VAR )
		error( "assignment to non-variable" ) ;

	code       = mktac( TAC_COPY, var, expr->res, NULL ) ;
	code->prev = expr->tac ;
	free_enode( expr ) ;		 /* 表达式结点信息不再被使用 */

	return code ;

}	/* TAC *do_assign( SYMB  *var,
			   ENODE *expr ) */


ENODE *do_bin(  int    binop,		 /* 二元运算符 */
		ENODE *expr1,		 /* 运算量 */
		ENODE *expr2 )

/* 二元表达式的翻译, 由于表达式必须翻译为两层含义: 表达式的四元式代码和
   表达式中间结果, 因此我们用树结构记录表达式的翻译信息. 运算量expr1和
   expr2一旦参与新的运算后(如: expr -> expr1 binop expr2), 其作为树结点
   的辅助信息不再被使用(其四元式代码链将链接到运算结果expr结点上; 而表达
   式的值将被expr的四元式代码引用), 因此在翻译后, expr1和expr2的结点信息
   不再被使用, 我们可以释放其内存单元, 由于expr需要一个心得结点, 所以我们
   可以保留expr1的结点给expr使用. 在翻译常数表达式时, 我们可以做一点优化,
   即, 在编译阶段就计算出其运算结果, */

{
	TAC  *temp ;			 /* 临时四元式 */
	TAC  *res ;			 /* 结果四元式 */

	/* 处理expr1和expr2都是常数的情况, */

	if(( expr1->ETYPE == T_INT ) && ( expr2->ETYPE == T_INT ))
	{
		switch( binop )		 /* 选择运算符号 */
		{
		case TAC_ADD:

			expr1->EVAL1 = expr1->EVAL1 + expr2->EVAL1 ;
			break ;

		case TAC_SUB:

			expr1->EVAL1 = expr1->EVAL1 - expr2->EVAL1 ;
			break ;

		case TAC_MUL:

			expr1->EVAL1 = expr1->EVAL1 * expr2->EVAL1 ;
			break ;

		case TAC_DIV:

			expr1->EVAL1 = expr1->EVAL1 / expr2->EVAL1 ;
			break ;

		}

		free_symb( expr2->res ) ;  /* 释放expr2的内存 */
		free_enode( expr2 ) ;

		return expr1 ;		   /* 返回新的结点 */
	}

	/* 处理不是常数的情况 */

	temp       = mktac( TAC_VAR, mktmp(), NULL, NULL ) ;
	temp->prev = join_tac( expr1->tac, expr2->tac ) ;
	res        = mktac( binop, temp->VA, expr1->res, expr2->res ) ;
	res->prev  = temp ;

	expr1->res = temp->VA ;
	expr1->tac = res ;
	free_enode( expr2 ) ;

	return expr1 ;	

}	/* ENODE *do_bin(  int    binop,
	 		   ENODE *expr1,
			   ENODE *expr2 ) */


ENODE *do_un(  int    unop,		 /* 一元运算 */
	       ENODE *expr )		 /* 运算量 */

/* 完全和二元运算的翻译一样 */


{
	TAC  *temp ;			 /* 临时四元式 */
	TAC  *res ;			 /* 结果四元式 */

	/* 处理常数情况 */

	if( expr->ETYPE == T_INT )
	{
		switch( unop )		 /* 选择运算符, VSL只有一元减 */
		{
		case TAC_NEG:

			expr->EVAL1 = - expr->EVAL1 ;
			break ;
		}

		return expr ;		   /* 返回结果表达式 */
	}

	/* 处理非常数情况 */

	temp       = mktac( TAC_VAR, mktmp(), NULL, NULL ) ;
	temp->prev = expr->tac ;
	res        = mktac( unop, temp->VA, NULL, expr->res ) ;
	res->prev  = temp ;

	expr->res = temp->VA ;
	expr->tac = res ;

	return expr ;	

}	/* ENODE *do_un(  int    unop,
	 		  ENODE *expr ) */


ENODE *do_fnap( SYMB  *func,		 /* 函数调用 */
		ENODE *arglist )	 /* 实参列表 */

/* 函数调用的翻译: 首先类型检查判断函数名是否有定义, 如果函数名的类型不是
   T_FUNC或T_UNDEF, 表示该标识符不是函数, 分析出错返回; 否则, 链结arglist
   中的每个实参代码, 形成arglist代码链, 紧接着对每个实参产生TAC_ARG三地址
   码(注意TAC_ARG必须是连续的代码, 最后产生TAC_CALL代码. 如果函数的类型是
   T_UNDEF, 表示该函数调用是先调用后引用, 此时, 需要将TAC_CALL语句加入到函
   数名的回填链中.

   例如 "fname(expr1, expr2)" 将翻译为 "expr1语句; expr2语句; ARG, var1;
   ARG, var2; CALL, result, fname", 其中, varn是临时变量, 保存exprn的计
   算结果; res保存函数的返回值 */

{
	ENODE  *alt ;			 /* 用于在实参链上移动 */
	SYMB   *res ;			 /* 保存函数调用的返回结果 */
	TAC    *code ;			 /* 保存最后的代码链 */
	TAC    *temp ;			 /* 临时变量 */

	/* 类型检查 */

	if(( func->type != T_UNDEF ) && ( func->type != T_FUNC ))
	{
		error( "function declared other than function" );
		return NULL ;
	}

	res   = mktmp() ;		   /* 函数调用表达式的结果 */
	code  = mktac( TAC_VAR, res, NULL, NULL ) ;

	for( alt = arglist ; alt != NULL ; alt = alt->next )  
			/* 链结实参代码 */
		code = join_tac( code, alt->tac ) ;

	while( arglist != NULL )	 /* 产生连续的TAC_ARG语句 */
	{
		temp       = mktac( TAC_ARG, arglist->res, NULL, NULL ) ;
		temp->prev = code ;
		code       = temp ;

		alt = arglist->next ;
		free_enode( arglist ) ;	 /* 释放内存 */
		arglist = alt ;
	} ;

		/* 产生函数调用语句 */
	temp       = mktac( TAC_CALL, res, (SYMB *)func->LABEL2, NULL ) ;
		/* 注意LABEL2有两种可能, 一种是函数代码的入口标号, 
		   另一种是回填链表的表头, 而回填链表的每个元素的类型
		   是TAC, 并且是通过LABEL2进行链结, 两种情况都可以这样
                   处理, 对第二种, 只要将函数的表头设置为temp即可; 另一个
     		   要注意的是由于TAC数据结构的运算量类型是SYMB *, 而LABEL2
            	   的类型是TAC *, 因此要用强制类型转换, 将之转换为SYMB指针,
		   在代码生成时, 再将TAC_CALL的第二运算量转换回来即可, 下面
		   的翻译还有类似的情况, 不再作特别的注释. 指针的类型转换
		   是C语言处理的一个常用手段, 使用转换后的指针一定要再转换
 		   回来 */
 
	temp->prev = code ;
	code       = temp ;

	/* 如果函数的类型是T_UNDEF, 则设置回填链的新表头为temp */

	if( func->type == T_UNDEF )
		func->LABEL2 = code ;

	return mkenode( NULL, res, code ) ;

}	/* ENODE *do_fnap( SYMB  *func,
		           ENODE *arglist ) */


TAC *do_lib( int   rtn,			 /* 库函数码 */
	     SYMB *arg )		 /* 实参 */

/* VSL语言采用简单的方法处理库函数的调用, 即将两个库函数的标号语句
   三地址码预先装入数组library中, 并且预留相应的标号(2和4), 库函数
   PRINTN和PRINTS的形参只有1个, 而VSL的打印语句的参数个数是可变的,
   在处理这样的变参情况, VSL采用的策略是在形式文法这一级上进行处理,
   即, 通过PRINT关键字, 引入变参调用. 这样, 当词法分析器识别"PRINT  
   item1, item2", 我们可以将之翻译为两个连续的打印函数的调用语句:
   "PRINT item1 PRINT item2", 这样就避免了在中间代码一级上处理变参的
   情况. 这样的解决方案仅是一个权宜之计, 它不能处理用户自定义的边
   参函数. 对于每个"PRINT item", 将之翻译为: TAC_ARG, item和TAC_CALL,
   library[rtn]即可, 而rtn可以在语法这一级上确定item是TEXT或是expression,
   即是字符串常量或是整数 */

{
	TAC *a = mktac( TAC_ARG, arg, NULL, NULL ) ;
	TAC *c = mktac( TAC_CALL, NULL, (SYMB *)library[rtn], NULL ) ;

	c->prev = a ;

	return c ;

}	/* TAC *do_lib( int   rtn,
	   		SYMB *arg ) */


TAC *do_if( ENODE *expr,		 /* 条件 */
	    TAC   *stmt )		 /* 执行的语句 */

/* 条件语句的翻译: 为了方便将if结构分为两个情况处理, 一个是do_if(), 
   它没有else挂靠; 另一个是do_test(), 它有else挂靠, 在翻译if结构时
   我们没有采用通常的回填技术,  而是使用家标号的方法, 这样: "IF expr
   THEN stmt FI"翻译为: "expr语句; IFZ, LABELn expr; stmt; LABELn"; 
   
   由此可能产生标号的重叠使用, 如: "IF expr1 THEN IF expr2 THEN stmt
    FI FI"的三地址码是: "expr语句; IFZ, LABELn expr; IFZ, LABELm, expr2;
   LABELm; LABELn", 其中LABELm和LABELn连续出现, 

   由于在最后的目标代码中标号作为伪指令还保留, 因此该问题只有到最后
   VAM二进制文件生成时进行处理, 处理的方法是对编译器生成的汇编代码
   进行二次扫描, 第一次扫时对非标号语句进行计数,而每个标号语句将转化
   为该标号语句之后的第一条非标号语句对应的计数,因此, 这样连续的标号
   语句的问题最终可以解决, 由于在目标语言的汇编码中加入了伪指令标号, 
   这使得中间语言的翻译简化, 但对此留下的问题, 我们必须用两遍(two pass)
   的方式解决, 为此处的简化付出代价, 而对一般的编译器都是使用回填技术
   进行处理, 以避免two pass处理 */

{
	TAC *label = mktac( TAC_LABEL, mklabel( next_label++ ), NULL, NULL ) ;
	TAC *code  = mktac( TAC_IFZ, (SYMB *)label, expr->res, NULL ) ;

	code->prev  = expr->tac ;
	code        = join_tac( code, stmt ) ;
	label->prev = code ;

	free_enode( expr ) ;		 /* 表达式不再使用 */

	return label ;
}	/* TAC *do_if( ENODE *expr,
	    	       TAC   *stmt ) */


TAC *do_test( ENODE *expr,		 /* 条件 */
	      TAC   *stmt1,		 /* THEN部分 */
	      TAC   *stmt2 )		 /* ELSE部分 */

/* 有else挂靠: "IF expr THEN stmt1 ELSE stmt2 FI"将翻译为: 
   "expr语句; IFZ, label1, expr;  stmt1; goto, LABEL2; LABEL1; 
    stmt2; LABEL2" */

{
	TAC *label1 = mktac( TAC_LABEL, mklabel( next_label++ ), NULL, NULL ) ;
	TAC *label2 = mktac( TAC_LABEL, mklabel( next_label++ ), NULL, NULL ) ;
	TAC *code1  = mktac( TAC_IFZ, (SYMB *)label1, expr->res, NULL ) ;
	TAC *code2  = mktac( TAC_GOTO, (SYMB *)label2, NULL, NULL ) ;

	code1->prev  = expr->tac ;		   /* 按上次序连接代码 */
	code1        = join_tac( code1, stmt1 ) ;
	code2->prev  = code1 ;
	label1->prev = code2 ;
	label1       = join_tac( label1, stmt2 ) ;
	label2->prev = label1 ;

	free_enode( expr ) ;		 /* 释放expr内存 */

	return label2 ;

}	/* TAC *do_test( ENODE *expr,
	      		 TAC   *stmt1,
	      		 TAC   *stmt2 ) */


TAC *do_while( ENODE *expr,		 /* 循环条件 */
	       TAC   *stmt )		 /* 循环体 */

/* 循环语句的翻译: 处理的方法和条件语句一样通过标号语句来引导分支的
   转移. "WHILE expr DO stmt DONE" 翻译为: "LABELm; expr语句;  
   IFZ, LABELn expr; stmt; goto LABELm; LABELn", 如果将其中的 "stmt; 
   goto LABELm" 看成是stmt1; 则: "expr语句;  IFZ, LABELn expr; stmt1;
   LABELn" 是一个无挂靠的IF结构, 因此可以使用函数do_if() */   

{
	TAC *label = mktac( TAC_LABEL, mklabel( next_label++ ), NULL, NULL ) ;
	TAC *code  = mktac( TAC_GOTO, (SYMB *)label, NULL, NULL ) ;

	code->prev = stmt ;		 /* 产生stmt1 */

	return join_tac( label, do_if( expr, code )) ;

}	/* TAC *do_while( ENODE *expr,
	       		  TAC   *stmt ) */


ENODE *mkenode( ENODE *next,
		SYMB  *res,
		TAC   *code )

/* 产生表达式结点, 本函数本应该作为编译的辅助函数在main.c模块中
   定义, 但是仅有本处使用该函数, 故移至此处 */

{
	ENODE *expr = get_enode() ;

	expr->next = next ;
	expr->res  = res ;
	expr->tac  = code ;

	return expr ;

}	/* ENODE *mkenode( ENODE *next,
			   SYMB  *res,
			   TAC   *code ) */


void  yyerror( char *str )

/* YACC的标准出错处理函数, 分析器在分析出错时调用该函数 */

{
	error( str ) ;

}	/* void  yyerror( char *str ) */