parse.y

1.小型编译器 2。支持整数

%{
#define YYPARSER /* distinguishes Yacc output from other code files */

#include "Globals.h"
#include "Util.h"
#include "Scan.h"
#include "Parse.h"

static char * savedFunName; /* for use in assignments */
static char * savedIdName;
static char * savedId2Name;
static char * saveStructName;
static int savedLineNo;  /* ditto */
static TreeNode * savedTree; /* stores syntax tree for later return */

%}

	
%union { TreeNode * ptree;
         VExpType type; 
}

%token ENDFILE ERROR 
%token INT CHAR DOUBLE STRUCT IF ELSE WHILE VOID RETURN BREAK CONTINUE
%token ID NUM DNUM SCHAR STRUCT DOT TYPEDEF STRING
%token PLUS SUB MUT DIV LT LE GT GE EQ NEQ AND OR NOT ASSIGN SEMI COMMA LP RP LSP RSP LFP RFP REF

       
%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 struct_dec field_list field_dec
%type <type> type_spec

%left	COMMA
%right	ASSIGN
%left 	OR    
%left 	AND
%left 	EQ NEQ
%left 	LT LE GT GE
%left 	PLUS SUB
%left 	MUT DIV
%left	LP RP LSP RSP LFP RFP

%right 	ELSE


%% /* Grammar for C_minus */

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; }
            | struct_dec { $$ = $1; }
            ;
id          : ID { savedIdName = copyString(tokenString); }
            ;
id2         : ID { savedId2Name = copyString(tokenString); }
            ;          
fid         : ID { savedFunName = copyString(tokenString); }
            ;
strid		: ID { saveStructName = copyString(tokenString); }
			;
var_dec     : type_spec id_list SEMI	
				{ 
					if($1.type == Void){
						yyerror("no type spec");
					}
					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;
                }	
            | 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;
              }
            | id2 ASSIGN simple_exp
              { 
				 $$ = newStmtNode(AssignK);
				 $$ -> child[0] = newExpNode(IdK);
				 $$ -> child[0] -> attr.name = savedId2Name;
				 $$ -> child[1] = $3;
              }
            ; 
type_spec   : INT { VExpType t; t.type = Integer; $$ = t; }         
            | DOUBLE { $$.type = Double; }         
            | CHAR { $$.type = Char; }         
            | VOID { $$.type = Void; }
            | STRUCT id { $$.type = Struct; $$.name = savedIdName; };
            ;
fun_def     : type_spec fid LP params RP comp_stmt 
				{  
					$$ = newDecNode(FunDefK);
				  	$$ -> attr.name = savedFunName;
				  	$$ -> type = $1;
				  	$$ -> child[0] = $4;
				  	$$ -> child[1] = $6; 
				}
            | fid LP params RP comp_stmt
				{ 
					$$ = newDecNode(FunDefK);
				  	$$ -> attr.name = savedFunName;
				  	$$ -> type.type = Void;
				  	$$ -> child[0] = $3;
				  	$$ -> child[1] = $5; 
				}
            ;
fun_dec     : type_spec fid LP params RP SEMI
				{  
					$$ = newDecNode(FunDecK);
				  	$$ -> attr.name = savedFunName;
				  	$$ -> type = $1;
				  	$$ -> child[0] = $4;
				  	$$ -> child[1] = NULL;
				}
			| fid LP params RP SEMI
				{ 
					$$ = newDecNode(FunDecK);
				  	$$ -> attr.name = savedFunName;
				  	$$ -> type.type = Void;
				  	$$ -> child[0] = $3;
				  	$$ -> child[1] = NULL;
				}
            ; 

struct_dec	:STRUCT strid LFP field_list RFP SEMI
			{
				$$ = newDecNode(StructDecK);
			  	$$ -> attr.name = saveStructName;
			  	$$ -> type.type = Struct;
			  	$$ -> child[0] = $4;
			  	$$ -> child[1] = newDecNode(StructEndK);
			};

field_list	:	field_list field_dec	
			{
				TreeNode * t = $1;
			  	if (t != NULL)
			  	{	 
			  		while (t->sibling != NULL)
						t = t->sibling;
					t->sibling = $2;
					$$ = $1; }
			  	else $$ = $2;
			}
			| 
                { $$ = NULL; }
            ;

field_dec     : type_spec id_list SEMI	
				{ 
					if($1.type == Void){
						yyerror("no type spec");
					}
					else
				    {	
					  $$ = newDecNode(FieldDecK); 
					  $$ -> type = $1;
					  $$ -> child[0] = $2;
					}
				}            

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;
                  	$$ -> refFlag = 0;
                }            
			| type_spec id
                {
                	$$ = newDecNode(ParamK);
                  	$$ -> type = $1;
                  	$$ -> refFlag = 0;
                  	$$ -> attr.name = savedIdName;
                }   
            | type_spec REF id
                {
                	$$ = newDecNode(ParamK);
                  	$$ -> type = $1;
                  	$$ -> refFlag = 1;
                  	$$ -> attr.name = savedIdName;
                }        
            | type_spec id LSP simple_exp RSP
                { 
                	$$ = newDecNode(ParamK);
                  	$$ -> type = $1;
                  	$$ -> refFlag = 0;
                  	$$ -> attr.name = savedIdName;
                  	$$ -> child[0] = $4;
                }            
            ;
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; }
            | CONTINUE SEMI { $$ = newStmtNode(ContinueK); }
            | BREAK SEMI    { $$ = newStmtNode(BreakK); }
            ;
exp_stmt    : exp SEMI
                { $$ = $1; }
            | SEMI
                { $$ = NULL; }            
            ;
sele_stmt   : IF LP exp RP stmt %prec ELSE
                { 
                	$$ = 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
				{
					$$ = newStmtNode(WhileK);
                  	$$ -> child[0] = $3;
                  	$$ -> child[1] = $5;
                }            
            ;    
return_stmt : RETURN SEMI
                {  
                	$$ = newStmtNode(ReturnK);
                  	$$ -> child[0] = NULL;
                }
            | RETURN exp SEMI
                { 
                	$$ = newStmtNode(ReturnK);
                 	$$ -> child[0] = $2;
                }
            ;                   
exp         : var ASSIGN exp
                { 
                	$$ = newStmtNode(AssignK);
                  	$$ -> child[0] = $1;
                  	$$ -> child[1] = $3;
                }
            | simple_exp
                { $$ = $1; }
            ;
var         : id
                { 
                	$$ = newExpNode(IdK);
                  	$$ -> attr.name = savedIdName;
                }            
            | id LSP simple_exp RSP
				{ 
					$$ = newExpNode(IdK);
				  	$$ -> attr.name = savedIdName;
                  	$$ -> child[0] = $3;
                }  
            | strid DOT var
            	{
            		$$ = newExpNode(StructIdK);
				  	$$ -> attr.name = saveStructName;
				  	$$ -> child[0] = $3;
            	}
            ;
simple_exp : simple_exp OR simple_exp 
				{ 
					$$ = newExpNode(OpK);
				  	$$ -> child[0] = $1;
				  	$$ -> child[1] = $3;
				  	$$ -> attr.op = OR;
				}
			|simple_exp AND simple_exp 
				{ 
					$$ = newExpNode(OpK);
				  	$$ -> child[0] = $1;
				  	$$ -> child[1] = $3;
				  	$$ -> attr.op = AND;
				}
			|simple_exp LT simple_exp 
				{ 
					$$ = newExpNode(OpK);
				  	$$ -> child[0] = $1;
				  	$$ -> child[1] = $3;
				  	$$ -> attr.op = LT;
				  	$$ -> type.type = Boolean;
				}
			|simple_exp LE simple_exp 
				{ 
					$$ = newExpNode(OpK);
				  	$$ -> child[0] = $1;
				  	$$ -> child[1] = $3;
				  	$$ -> attr.op = LE;
				  	$$ -> type.type = Boolean;
				}
			|simple_exp GT simple_exp 
				{ 
					$$ = newExpNode(OpK);
				  	$$ -> child[0] = $1;
				  	$$ -> child[1] = $3;
				  	$$ -> attr.op = GT;
				  	$$ -> type.type = Boolean;
				}
			|simple_exp GE simple_exp 
				{ 
					$$ = newExpNode(OpK);
				 	$$ -> child[0] = $1;
				  	$$ -> child[1] = $3;
				  	$$ -> attr.op = GE;
				  	$$ -> type.type = Boolean;
				}
			|simple_exp EQ simple_exp 
				{ 
					$$ = newExpNode(OpK);
				  	$$ -> child[0] = $1;
				  	$$ -> child[1] = $3;
				  	$$ -> attr.op = EQ;
				  	$$ -> type.type = Boolean;
				}
			|simple_exp NEQ simple_exp 
				{ 
					$$ = newExpNode(OpK);
				  	$$ -> child[0] = $1;
				  	$$ -> child[1] = $3;
				  	$$ -> attr.op = NEQ;
				  	$$ -> type.type = Boolean;
				}
			|simple_exp PLUS simple_exp 
				{ 
					$$ = newExpNode(OpK);
				  	$$ -> child[0] = $1;
				  	$$ -> child[1] = $3;
				  	$$ -> attr.op = PLUS;
				}
			|simple_exp SUB simple_exp 
				{ 
					$$ = newExpNode(OpK);
				  	$$ -> child[0] = $1;
				  	$$ -> child[1] = $3;
				  	$$ -> attr.op = SUB;
				}
			|simple_exp MUT simple_exp 
				{
					$$ = newExpNode(OpK);
				  	$$ -> child[0] = $1;
				  	$$ -> child[1] = $3;
				  	$$ -> attr.op = MUT;
				}
			|simple_exp DIV simple_exp 
				{ 
					$$ = newExpNode(OpK);
				  	$$ -> child[0] = $1;
				  	$$ -> child[1] = $3;
				  	$$ -> attr.op = DIV;
				}
			| factor
			    { 	$$ = $1; }
			;

factor      : LP exp RP
                { 	$$ = $2; }			
            | var
                { 	$$ = $1; }			
			| call
			    { 	$$ = $1; }			
			| NUM
			    { 	$$ = newExpNode(NumK);
			      	$$ -> type.type = Integer;
			      	$$ -> attr.val.i = atoi(tokenString);
			    }
			| DNUM
			    {	$$ = newExpNode(DNumK);
			      	$$ -> type.type = Double;
			      	$$ -> attr.val.f = atof(tokenString);
			    }
			| SCHAR
			    { 	$$ = newExpNode(CharK);
			      	$$ -> type.type = Char;
			      	$$ -> attr.val.i = *(tokenString + 1);
			    }
			| STRING
				{
				  	$$ = newExpNode(StringK);
			      	$$ -> type.type = String;
			      	$$ -> attr.val.str = copyString(tokenString);
				}
			| NOT factor
			    { 	$$ = $2;
			      	$$ -> attr.op = NOT;
			    }
			;
call        : var LP args RP
                { 	$$ = newStmtNode(CallK);
				  	$$ -> attr.name = $1 -> attr.name;
                  	$$ -> child[0] = $3;
                }
            ;
arg_list    : arg_list COMMA exp            
				{ TreeNode * t = $1;
				  if (t != NULL)
				  { while (t->sibling != NULL)
						t = t->sibling;
					t->sibling = $3;
					$$ = $1; }
				  else $$ = $3;
				}	                 
            | exp
                { 	$$ = $1; }
			;
args        : arg_list
                { 	$$ = $1; }           
            | 
                { 	$$ = NULL; }
            ;
%%

void yyerror(const char * message)
{ 
	fprintf(listing,"Syntax error at line %d: %s\n",lineno,message);
  	fprintf(listing,"Current token: \n");
  	printToken(yychar,tokenString);
  	Error = TRUE;
}

TreeNode * parse(void)
{ 
	printf("parse begin\n");
	yyparse();
	printf("parse end\n");
  	return savedTree;
}