parser.y

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

/******************************************************************************
*******************************************************************************

				   parser.y
		
				语法分析yacc源文件 
	     
   本文件定义了VSL语言的语法，及对应的语义处理和中间代码生成函数。
   因此由yacc生成的函数yyparse()能完成VSL语言的中间代码生成。

   文件修改时间
   ============

   2005年5月7日:  Yacc源文件   (C) hfwang
 
*******************************************************************************
******************************************************************************/

%{

/* 定义部分 */

/* 本模块所需的头文件，注意：没有parser.h，因为它是由yacc分析本文件的一个输出文
   件。*/

#include <stdio.h>
#include <ctype.h>
#include "vc.h"

/* 以下是在本文件用户代码部分所定义的函数的原形。这些程序将用于词法分析中。*/

TAC   *do_program( TAC *c ) ;

TAC   *do_func( SYMB *func,
	      TAC  *args,
	      TAC  *code ) ;

TAC   *declare_var( SYMB *var ) ;

TAC   *do_assign( SYMB  *var,
		ENODE *expr ) ;

ENODE *do_bin(  int    binop,
		ENODE *expr1,
		ENODE *expr2 ) ;

ENODE *do_un(  int    unop,
	       ENODE *expr ) ;

ENODE *do_fnap( SYMB  *func,
		ENODE *arglist ) ;

TAC   *do_lib( int   rtn,
	     SYMB *arg ) ;

TAC   *do_if( ENODE *expr,
	    TAC   *stmt ) ;

TAC   *do_test( ENODE *expr,
	      TAC   *stmt1,
	      TAC   *stmt2 ) ;

TAC   *do_while( ENODE *expr,
	       TAC   *stmt ) ;

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

void  yyerror( char *str ) ;

%}

/* %union定义了语义值的属性，有符号指针，三地址码指针和表达式指针三种属性，符
   号指针对应于词法分析产生的终结符：标识符、整数常量和字符串常量；三地址指针
   对应于一般的非终结符；而表达式指针用于处理对表达式的分析与翻译，表达式结构
   记录了表达式翻译对应的三地址码和保存中间结果的临时变量。 */

%union
{
	SYMB   *symb ;		 /* 变量,常数和字符串的语义值 */
	TAC    *tac ;		 /* 语句的语义值 */
	ENODE  *enode ;		 /* 表达式的语义值 */
}

%{

/* yacc将%union翻译为一个类型名为YYSTYPE的共用体的类型定义。在此定义全局变量
   finaltac记录最后产生的三地址码指针，利用该指针，我们在目标代码生成时可以
   找到三地址码链的头节点。*/

YYSTYPE finaltac;

%}


/* 定义词汇（终结符）及对应的语义属性。只有标识符VARIABLE、整数常量INTEGER和字
   符串常量TEXT有符号指针属性。*/

%token         FUNC			 /* 关键字'FUNC' */
%token <symb>  VARIABLE			 /* 标识符 */
%token         ASSIGN_SYMBOL		 /* ':=' */
%token <symb>  INTEGER			 /* 整数常量 */
%token         PRINT			 /* 关键字'PRINT' */
%token <symb>  TEXT			 /* 由双引号所引的字符串常量 */
%token         RETURN			 /* 关键字'RETURN' */
%token         CONTINUE			 /* 关键字'CONTINUE */
%token         IF			 /* 关键字'IF' */
%token         THEN			 /* 关键字'THEN' */
%token         ELSE			 /* 关键字'ELSE' */
%token         FI			 /* 关键字'FI' */
%token         WHILE			 /* 关键字'WHILE' */
%token         DO			 /* 关键字'DO' */
%token         DONE			 /* 关键字'DONE' */
%token         VAR			 /* 关键字'VAR' */
%token         UMINUS			 /* 一元减,虚拟词汇 */

/* 定义非终结符及对应的属性，除表达式expression、表达式列表expression_list和
   参数列表argument_list的语义属性为表达式指针外，其余的非终结符的语义属性为
   三地址指针。*/

%type <tac>     program
%type <tac>     function_list
%type <tac>     function
%type <tac>     parameter_list
%type <tac>     variable_list
%type <enode>   argument_list
%type <enode>   expression_list
%type <tac>     statement
%type <tac>     assignment_statement
%type <enode>   expression
%type <tac>     print_statement
%type <tac>     print_list
%type <tac>     print_item
%type <tac>     return_statement
%type <tac>     null_statement
%type <tac>     if_statement
%type <tac>     while_statement
%type <tac>     block
%type <tac>     declaration_list
%type <tac>     declaration
%type <tac>     statement_list
%type <tac>     error

/* 定义算术运算的优先级别和结合次序：伪终结符UMINUS是为了定义一元减的
   优先级。*/

%left  '+' '-'
%left  '*' '/'
%right UMINUS

%%


/* 语法规则部分 */

/* 以下定义了VSL语言的语法规则及对应的语义操作，在语法分析之后，产生程序的三地
   址码。注意缺省的语义操作是：$$ = $1 。*/


/* program是文法开始符号，这是自底向上分析的最后一部，此时function_list的语义
   值是指向整个程序的三地址码链的链尾的指针，我们用全局变量finaldoc记录该指针，
   在代码生成时用该指针找到三地址链表的表头。*/

   program                 :       function_list
                                {finaltac.tac = $1;}
			;

/* function_list有两个产生式，对第二个产生式，我们用join_tac()将产生式右边的两
   个三地址链表链结在一起，将返回的表尾指针作为产生式左边符号的语义值，join_tac()
   函数在链结两表时必须将后一个三地址链的表尾指针移动到表头，这样在程序过大时会
   降低编译器的执行效率，在实际的编译器中可以采用不链结函数的三地址码链，而是将
   函数的三地址码的尾指针保存在一个数据结构中，以提高编译器的效率。*/

function_list		:	function
			|	function_list function
				{
					$$ = join_tac( $1, $2 ) ;
				}
			;

/* 函数定义语句的形式文法和翻译，首先将临时变量计数其清零，因为临时变量仅在函数
   调用时才动态分配存储空间，所以，不同函数的临时变量可以同名；又因为临时变量仅
   是为了记录表达式运算的中间结果，没有初值，因此不同函数的临时变量可以共享同一
   个符号单元，对函数定义语句的翻译由函数do_func()完成。

   在语法分析出错时，通过yacc的特殊终结符error对语法分析进行恢复，同时调用error()
   函数报错，这是最简单的出错处理，在实际的编译器中，一般用定义同步符号集等方法
   对错误进行恢复。*/

function		:	FUNC VARIABLE '(' parameter_list ')'
			        statement
				{
					next_tmp = 0 ;
					$$ = do_func( $2, $4, $6 ) ;
				}
			|	error
				{
					error( "Bad function syntax" ) ;
					$$ = NULL ;
				}
			;

/* 参数列表：或者是变量名(形参)列表，或者是空，表示无参函数。*/

parameter_list		:	variable_list
			|
				{
					$$ = NULL ;
				}
			;

/* 变量名列表，在此我们将形参当变量等同处理，由于，变量的内存地址在代码生成阶段确
   定通过，因此处理变量时，通过引入三地址码指令TAC_VAR记录变量定义语句，在代码生成
   时通过该三地址码指令分配变量的内存在，declare_var()产生变量定义语句，*/

variable_list		:	VARIABLE
				{
					$$ = declare_var( $1 ) ;
				
					/* $1是词法分析函数yylex()识别变量后
					   定义的yylval */
				}		
			|	variable_list ',' VARIABLE
				{
					TAC *t = declare_var( $3 ) ;

					t->prev = $1 ;
					/* 链结三地址码 */
					$$ = t ;
				}		
			;


statement		:	assignment_statement
			|	return_statement
			|	print_statement
			|	null_statement
			|	if_statement
			|	while_statement
			|	block
			|   	error
				{
					error( "Bad statement syntax" ) ;
					$$ = NULL ;
				}
			;

assignment_statement	:	VARIABLE ASSIGN_SYMBOL expression
				{
					$$ = do_assign( $1, $3 ) ;
				}
			;

/* 表达式语义翻译, 注意通过引入虚拟词汇%prec UMINUS处理一元减 */

expression		:	expression '+' expression
				{
					$$ = do_bin( TAC_ADD, $1, $3 ) ;
				}
			|	expression '-' expression
				{
					$$ = do_bin( TAC_SUB, $1, $3 ) ;
				}
			|	expression '*' expression
				{
					$$ = do_bin( TAC_MUL, $1, $3 ) ;
				}
			|	expression '/' expression
				{
					$$ = do_bin( TAC_DIV, $1, $3 ) ;
				}
			|	'-' expression  %prec UMINUS
				{
					$$ = do_un( TAC_NEG, $2 ) ;
				}
			|	'(' expression ')'
				{
					$$ = $2 ;
				}		
			|	INTEGER
				{
					$$ = mkenode( NULL, $1, NULL ) ;
				}
			|	VARIABLE
				{
					$$ = mkenode( NULL, $1, NULL ) ;
				}
			|	VARIABLE '(' argument_list ')'
				{
					$$ = do_fnap( $1, $3 ) ;
				}		
			|   	error
				{
					error( "Bad expression syntax" ) ;
					$$ = mkenode( NULL, NULL, NULL ) ;
				}
			;

argument_list		:
				{
					$$ = NULL ;
				}
			|	expression_list
			;

expression_list		:	expression
			|	expression_list ',' expression
				{

					/* 产生表达式链表 */

					$1->next = $3 ;
					$$       = $1 ;
				}
			;

print_statement		:	PRINT print_list
				{
					$$ = $2 ;
				}		
			;

print_list		:	print_item
			|	print_list ',' print_item
				{
					$$ = join_tac( $1, $3 ) ;
				}		
			;

/* 打印项目将翻译为调用库函数,通过函数do_lib()产生调用打印库函数的三地址码,
   通过join_tac()将该三地址码链接到三地址码链上 */

print_item		:	expression
				{

					/* 调用打印库函数,其中$1->res是
					   表达式临时变量在符号表的指针 */

					$$ = join_tac( $1->tac,
						       do_lib( LIB_PRINTN,
						       $1->res )) ;
				}
			|	TEXT
				{

					/* 同上,$1是字符串常量在符号表的指针 */

					$$ = do_lib( LIB_PRINTS, $1 ) ;
				}
			;

return_statement	:	RETURN expression
				{
					TAC *t = mktac( TAC_RETURN, $2->res,
							NULL, NULL ) ;
					t->prev = $2->tac ;
					free_enode( $2 ) ;
					$$      = t ;
				}		
			;

null_statement		:	CONTINUE
				{
					$$ = NULL ;
				}		
			;

/* 在此对匹配的if和不匹配的if采用不同的翻译方法. */

if_statement		:	IF expression THEN statement FI
				{
					$$ = do_if( $2, $4 ) ;
				}
			|	IF expression THEN statement
			        ELSE statement FI
				{
					$$ = do_test( $2, $4, $6 ) ;
				}
			;

while_statement		:	WHILE expression DO statement DONE
				{
					$$ = do_while( $2, $4 ) ;
				}		
			;

block			:	'{' declaration_list statement_list '}'
				{
					$$ = join_tac( $2, $3 ) ;
				}		
			;

declaration_list	:
				{
					$$ = NULL ;
				}
			|	declaration_list declaration
				{
					$$ = join_tac( $1, $2 ) ;
				}
			;

declaration		:	VAR variable_list
				{
					$$ = $2 ;
				}
			;

statement_list		:	statement

			|	statement_list statement
				{
					$$ = join_tac( $1, $2 ) ;
				}		
			;

%%

/* 一些是处理各类语句翻译的函数,这样处理将简化语法规则中的语义动作,并使得
   有些翻译动作可以在动作部分重复使用 */


TAC *do_func( SYMB *func,	 		 /* 函数名在 */
	      TAC  *args,	 		 /* 参数列表 */
	      TAC  *code )	 		 /* 函数体的四元式链 */

/* 函数定义语句的翻译: 首先对函数体四元式代码的首尾加上TAC_BEGINFUNC和
   TAC_ENDFUNC标签, 然后查看函数名的类型, 该函数名在符号表中的类型必须
   是未定义T_UNDEF类型, 否则表示该函数名已经被定义过, 

   由于VSL语言的函数可以是先使用后定义,在这种情况下,函数调用时还不
   知道函数的入口地址, 我们将调用语句的四元式地址链接到函数名的符号表
   单元的LABEL2上, 因此函数定义语句如果检测到LABEL2非空, 将回填函数的入口