parse.y

一个C语言的编译器

%{
/****************************************************************************
parse.y
ParserWizard generated YACC file.
BY:计算机科学与技术系 0610386 蒲凌君
Date: 2008年12月22日 星期一
****************************************************************************/
#define YYPARSER 

#include "globals.h"
#include "util.h"
#include "scan.h"
#include "parse.h"


static char * savedFunName;            //保存函数名
static char * savedIdName;             //保存变量名
static int savedLineNo;                //保存行号
static TreeNode * savedTree;           //保存语法树的根结点
%}

/////////////////////////////////////////////////////////////////////////////
// declarations section
%token ENDFILE ERROR        
%token INT CHAR DOUBLE VOID                           //类型(PS:汇编程序可以完成INT CHAR的翻译，DOUBLE可以识别，翻译还不太会)
%token IF ELSE WHILE ASSIGN RETURN FOR INPUT OUTPUT   //语句(IF ELSE;WHILE;FOR;赋值;输入;输出;函数返回;)
%token ID NUM FNUM SCHAR                              //定义变量
%token SEMI COMMA LP RP LSP RSP LFP RFP               //定义一些辅助符号(; , ( ) [ ] { })
%token PLUS SUB MUT DIV MOD INC DEC B_AND B_OR B_NOT B_XOR B_LEFT B_RIGHT        //算术运算(+,-,*,/,%,++,--,&,|,^,~,<<,>>)  
%token EQ GT LT GE LE NEQ                                                        //关系运算(==,>,<,>=,<=,!=)
%token AND OR NOT                                                                //逻辑运算(&&,||,!)
	
%union { TreeNode * ptree;                            //定义树结点
         Type type;                                   //定义类型
       }
       
%type <ptree> program dec_list dec var_dec fun_dec fun_def params param_list param comp_stmt local_dec stmt_list stmt 
              exp_stmt sele_stmt iter_stmt return_stmt exp var simple_exp factor call args arg_list
              id_list input_stmt output_stmt
%type <type> type_spec
%left	COMMA                                         //按照优先级的关系进行先后定义(优先级从上到下依次增加)
%right	ASSIGN
%left   OR    
%left   AND
%left   B_AND B_XOR B_OR 
%left   EQ NEQ
%left   LT LE GT GE
%left   B_LEFT B_RIGHT
%left   PLUS SUB
%left   MOD
%left   MUT DIV
%left   NOT B_NOT 
%left   INC DEC
%left   LP RP LSP RSP LFP RFP
%right ELSE

%include {
    void yyerror(const char * message);               
	TreeNode * parse(void);
}

%%

/////////////////////////////////////////////////////////////////////////////
// rules section

program     : dec_list                              //程序由声明表组成
                 { savedTree = $1;} 
            ;
dec_list    : dec_list dec	                        //用兄弟结点表示不同的声明语句
				{ TreeNode * t = $1;
				  if (t != NULL)
				  { while (t->sibling != NULL)
					t = t->sibling;
					t->sibling = $2;
					$$ = $1; }
				  else $$ = $2;
				}	                 
            | dec  
                { $$ = $1; }
            ;
dec         : var_dec	{ $$ = $1; }                //声明由三种的情况（变量定义;函数声明;函数定义）组成
            | fun_dec	{ $$ = $1; }
            | fun_def   { $$ = $1; }
            ;
id          : ID { savedIdName = copyString(tokenString); }
            ;
fid         : { savedFunName = savedIdName; }       //保存函数名
            ;
var_dec     : type_spec id_list SEMI                //变量定义	
				{ if($1 == Void)
					  ;
					  // err
				  else
				    {	
					  $$ = newDecNode(VarK); 
					  $$ -> type = $1;
					  $$ -> child[0] = $2;
					}
				} 
            ;
id_list     : id_list COMMA var                     //用兄弟结点表示不同的变量名
                { 
                  TreeNode * t = $1;
				  if (t != NULL)
				  { while (t->sibling != NULL)
					t = t->sibling;
					t->sibling = $3;
					$$ = $1; }
				  else $$ = $3;
                }	//	i,str[5],j
            | var { $$ = $1; }
            | id_list COMMA id ASSIGN simple_exp    //在声明时还可以对其进行赋值
              { 
				  TreeNode * new_node = newStmtNode(AssignK);
				  TreeNode * t = $1;
				  if (t != NULL)
				  { while (t->sibling != NULL)
					t = t->sibling;
					t->sibling = new_node;
					$$ = $1; }
				  else $$ = new_node;
              }
            | id ASSIGN simple_exp
              { 
				 $$ = newStmtNode(AssignK);
				 $$ -> child[0] = newExpNode(IdK);
				 $$ -> child[0] -> attr.name = savedIdName;
				 $$ -> child[1] = $3;
              }
            ; 
type_spec   : INT { $$ = Integer; }                  //类型定义（int;char;double;void）  
            | DOUBLE { $$ = Double; }         
            | CHAR { $$ = Char; }         
            | VOID { $$ = Void; }         
            ;
fun_def     : type_spec id fid LP params RP comp_stmt  //函数定义 
				{ $$ = newDecNode(FunDefK);
				  $$ -> attr.name = savedFunName;
				  $$ -> type = $1;
				  $$ -> child[0] = $5;
				  $$ -> child[1] = $7; 
				}
            | id fid LP params RP comp_stmt
				{ $$ = newDecNode(FunDefK);
				  $$ -> attr.name = savedFunName;
				  $$ -> type = Void;
				  $$ -> child[0] = $4;
				  $$ -> child[1] = $6; 
				}
            ;
fun_dec     : type_spec id fid LP params RP SEMI
				{ $$ = newDecNode(FunDecK);
				  $$ -> attr.name = savedFunName;
				  $$ -> type = $1;
				  $$ -> child[0] = $5;
				  $$ -> child[1] = NULL;
				}
			| id fid LP params RP SEMI
				{ $$ = newDecNode(FunDecK);
				  $$ -> attr.name = savedFunName;
				  $$ -> type = Void;
				  $$ -> child[0] = $4;
				  $$ -> child[1] = NULL;
				}
            ;             
params      : param_list                              //函数的参数列表
                { $$ = $1; }
            | 
				{ $$ = NULL; }
            ;         
param_list  : param_list COMMA param
            	{ TreeNode * t = $1;
				  if (t != NULL)
				  { while (t->sibling != NULL)
					t = t->sibling;
					t->sibling = $3;
					$$ = $1; }
				  else $$ = $3;
				}	                 
            | param
                { $$ = $1; }
            ;
param       : type_spec                                
                { $$ = newDecNode(ParamK);
                  $$ -> type = $1;
                }            
			| type_spec id
                { $$ = newDecNode(ParamK);
                  $$ -> type = $1;
                  $$ -> attr.name = savedIdName;
                }            
            ;
comp_stmt   : LFP local_dec stmt_list RFP             //复合语句定义
                { $$ = newDecNode(CompK);
                  $$ -> child[0] = $2;
                  $$ -> child[1] = $3;
                }            
            ;
local_dec   : local_dec var_dec                       //临时变量的定义       
            	{ TreeNode * t = $1;
				  if (t != NULL)
				  { while (t->sibling != NULL)
					t = t->sibling;
					t->sibling = $2;
					$$ = $1; }
				  else $$ = $2;
				}	                 
            | 
                { $$ = NULL; }
            ;
stmt_list   : stmt_list stmt                          //语句表          
            	{ TreeNode * t = $1;
				  if (t != NULL)
				  { while (t->sibling != NULL)
					t = t->sibling;
					t->sibling = $2;
					$$ = $1; }
				  else $$ = $2;
				}	                 
            | 
                { $$ = NULL; }
            ;
stmt        : exp_stmt	{ $$ = $1; }                  //语句的类型（条件语句，循环语句，输入输出语句等）          
            | sele_stmt	{ $$ = $1; }
            | iter_stmt	{ $$ = $1; }
            | return_stmt	{ $$ = $1; }
            | comp_stmt  { $$ = $1; }
            | input_stmt { $$ = $1; }
            | output_stmt{ $$ = $1; }
            ;
exp_stmt    : exp SEMI
                { $$ = $1; }
            | SEMI
                { $$ = NULL; }            
            ;
sele_stmt   : IF LP exp RP stmt %prec ELSE            //IF语句的两种形式
                { $$ = newStmtNode(IfK);
                  $$ -> child[0] = $3;
                  $$ -> child[1] = $5;
                }            
            | IF LP exp RP stmt ELSE stmt
                { $$ = newStmtNode(IfK);
                  $$ -> child[0] = $3;
                  $$ -> child[1] = $5;
				  $$ -> child[2] = $7;
                }
            ;
iter_stmt   : WHILE LP exp RP stmt                    //循环语句（WHILE,FOR）
				{ $$ = newStmtNode(WhileK);
                  $$ -> child[0] = $3;
                  $$ -> child[1] = $5;
                }
            | FOR LP exp_stmt exp_stmt exp RP stmt
                {
                  $$ = newStmtNode(ForK);
                  $$ -> child[0] = $3;
                  $$ -> child[1]  = $4;
                  $$ -> child[2]  = $7;
                  $$ -> child[3]  = $5;
                }            
            ;  
input_stmt  : INPUT LP id RP SEMI                     //输入语句