parser.y

一个面向对像语言的编译器

/* File: parser.y
 * --------------
 * Yacc input file to generate the parser for the compiler.
 *
 * pp4:  your task is to add code generation to the parser actions.
 */

%{

#include "scanner.h" // for yylex
#include <stdio.h>
#include <stdlib.h>
#include "utility.h"
#include "errors.h"
#include "declaration.h"
#include "type.h"
#include "scope.h"
#include "semantic.h"
#include "codegen.h"

 
/* Global variables (for shame!)
 * -----------------------------
 * Having one or two globally accessible variables turns out to be handy
 * since we don't have a way to pass parameters into yyparse(), so we
 * allow ourselves the liberty of global access to our scope stack and
 * code generator, which are needed everywhere.
 */
ScopeStack *scopes;
CodeGenerator *cg;

//存放被调用函数的链表
DeclList *FunUsedList;
int numerr=0;
%}

 
/*
 * yylval 
 * ------
 * Here we define the type of the yylval global variable that is used by
 * the scanner to store attibute information about the token just scanned
 * and thus communicate that information to the parser. You will need to
 * add new fields to this union as you add different attributes to your
 * non-terminal symbols.
 */
%union {
  int integerConstant;
  bool boolConstant;
  const char *stringConstant;
  double doubleConstant;
  char identifier[128];
  Type *type;
  Declaration *decl;
  DeclList *declList;
  char *label;
}


/* Tokens
 * ------
 * Here we tell yacc about all the token types that we are using.
 * Yacc will assign unique numbers to these and export the #define
 * in the generated y.tab.h header file.
 */
%token T_Void T_Bool T_Int T_Double T_String T_Class 
%token T_LessEqual T_GreaterEqual T_Equal T_NotEqual
%token T_And T_Or T_Null T_Extends T_This
%token T_While T_For T_If T_Else T_Return T_Break
%token <identifier>T_Identifier
%token <stringConstant>T_StringConstant <integerConstant>T_IntConstant
%token <doubleConstant>T_DoubleConstant <boolConstant>T_BoolConstant
%token T_New T_NewArray T_Print T_ReadInteger T_ReadLine

  
/* Non-terminal types
 * ------------------
 * In order for yacc to assign/access the correct field of $$, $1, we
 * must to declare which field is appropriate for the non-terminal.
 * As an example, this first type declaration establishes that the Type
 * non-terminal uses the field named "type" in the yylval union.
 * (what a tongue-twister!)
 */
%type<type> Type OptExtends
%type<decl> Variable Decl Call OptReceiver 
%type<decl> Constant BoolExpr
%type<decl> Expr LValue
%type<decl> VariableDecl Field
%type<decl> FunctionDecl FunctionDefn
%type<decl> ClassDefn
%type<declList> Formals VariableList FieldList DeclList ExprList Actuals 
/* Precedence and associativity
 * ----------------------------
 * Here we establish the precedence and associativity of the
 * tokens as needed to resolve conflicts and remove ambiguity.
 */

%left T_Or
%left T_And 
%nonassoc T_Equal T_NotEqual
%nonassoc T_LessEqual T_GreaterEqual '<' '>'
%left  '+' '-'
%left  '*' '/' '%'  
%nonassoc T_UnaryMinus '!' 
%nonassoc '[' '.' 
%nonassoc T_Lower_Than_Else ')'
%nonassoc T_Else

%%
	 
                   
Program         :       DeclList
                        {
						//在退出全局作用域之前检查链接错误，在此只检查那些函数调用但没有定义的情况
						int numElements;
						Declaration *decl;
						
						//所有调用过的函数的个数
						numElements=FunUsedList->NumElements();

						for(int i=0; i<numElements; i++)
						{
							decl=FunUsedList->Nth(i);
							//如果函数没有定义
							if(!decl->FunIsDefined())
							{
								//类中定义的函数的调用
								if(decl->GetScope()->IsClassScope())
								{
									numerr++;
									ReportError(NULL,err_meth_undefined,decl->GetName(), decl->GetScope()->GetClassType()->GetClassName());
								}
								//全局函数的调用
								if(decl->GetScope()->IsGlobalScope())
								{
									//没有定义而调用则报错
									numerr++;
									ReportError(NULL,err_fn_undefined,decl->GetName());
								}
							}
						}
						
						//下面单独处理main函数的情况
						Scope *tScope=scopes->GetCurrentScope();
						Declaration *dec1;
						bool flag=false;

						dec1=tScope->FirstDecla();
						while(dec1!=NULL)
						{
							//是否有main函数
							if(strcmp(dec1->GetName(),"main")==0&&dec1->FunIsDefined())
								flag=true;
							//下一个
							dec1=tScope->NextDecla();
						}
							
						//没有main函数定义则报错
						if(!flag)
								ReportError(NULL,err_fn_undefined,"main");

						 scopes->PopScope(); 
							
						  numErrors=numErrors+numerr;
                          if (numErrors == 0) cg->Emit(); }
                ;
  
DeclList        :       DeclList Decl 
						{ if($2) $1->Append($2); $$ = $1; }
                |       /* empty */
						{$$=new DeclList(); FunUsedList=new DeclList();}
                ;

Decl            :       ClassDefn		{$$=$1;}
                |       FunctionDefn	{$$=$1;}
                |       FunctionDecl	{$$=$1;}
                |       VariableDecl	{$$=$1;}
                ;

VariableDecl    :       Variable ';'
                        {
							Declaration *debug=$1;
							scopes->Declare($1); 
							
						//	if($1->GetType()->IsArrayType())
						//		$1->ValidateAddr();
							
							Scope *tScope=scopes->GetCurrentScope();
							//local中的变量声明，设置local offset
							if(tScope->IsLocalScope())
							{
								cg->SetLocalOffset($1);
							}
							
							
							if(tScope->IsGlobalScope())
							{
								//生成全局变量
								cg->GenGVar($1);
							}

							if(tScope->IsClassScope())
							{
								//如果是类域里面变量，设置变量在类域的offset
								cg->SetIVarOffset($1);
							}

							$$=$1;	
						}
                ;
 
Variable        :       Type T_Identifier 
                        { if ($1->IsEquivalentTo(Type::doubleType)) {
                            ReportError(&@1, err_no_code_gen_for_doubles);
                            $1 = Type::errorType;
                          }
                          $$ = BuildVarDecl($2, $1, @2.first_line);
                        }
                ;

Type            :       T_Int
                        { $$ = Type::intType; }
                |       T_Void
                        { $$ = Type::voidType;}
                |       T_Bool
                        { $$ = Type::boolType;}
                |       T_String
                        { $$ = Type::stringType;}
                |       T_Double
                        { $$ = Type::doubleType;} 
                |       T_Class T_Identifier
                        { $$ = TypeForClassName($2);}
                |       Type '[' ']'
                        { $$ = Type::NewArrayType($1); }
                ;

ClassDefn       :       T_Class T_Identifier OptExtends 
 
                        {
							Declaration *d = BuildClassDecl($2,$3,@2.first_line);
							int maxParentIVarOffset=0, maxParentMethodOffset=-4;
							Declaration *decl;
							bool flag1=false,flag2=false;

							$$=d;
							scopes->Declare(d);
							$<type>$ = d->GetType();
							scopes->PushScope($<type>$->GetClassScope());
							
							//初始化类中变量和成员方法的offset
							cg->InitIVarOffset();
							cg->InitMethodOffset();

					
							if($3!=NULL)
							{//继承有父类

								//拷贝父类成员
								scopes->GetCurrentScope()->CopyFieldsFromParent($3->GetClassScope());
								Scope *temp;
								int offset;

								temp=scopes->GetCurrentScope();
								decl=temp->FirstDecla();

								//下面查找父类中成员变量和方法的offset, 以便设置本类中新定义的成员的offset
								while(decl!=NULL)
								{
									if(decl->IsVarDecl())
									{
										offset=decl->GetOffset();
										if(offset>maxParentIVarOffset)
											maxParentIVarOffset=offset;
									}

									if(decl->IsFunctionDecl())
									{
										offset=decl->GetOffset();
										if(offset>maxParentMethodOffset)
											maxParentMethodOffset=offset;
									}

									decl=temp->NextDecla();
								}
								if(maxParentIVarOffset!=0)
									cg->SetTopIVarOffset(maxParentIVarOffset+VarSize);
								
								if(maxParentMethodOffset!=-4)
								cg->SetTopMethodOffset(maxParentMethodOffset+VarSize);
							}
						 }
                        '{' FieldList '}'
                        {
							Scope *tScope;
							DeclList *tMethodList, *methodList;
							Declaration *decl;
							int num;

							tScope=scopes->GetCurrentScope();
							tMethodList=new DeclList();
							methodList=new DeclList();
							cg->InitMethodOffset();

							decl=tScope->FirstDecla();
							//将类中（包括父类）所有的成员方法加入tMethodList中
							while(decl!=NULL)
							{
								if(decl->IsFunctionDecl())
								{
									tMethodList->Append(decl);
								}
								
								decl=tScope->NextDecla();	
							}
							
							num=tMethodList->NumElements();
							
							//将所得到的所有的成员方法按声明的先后顺序加入vTable中
							for(int i=0; i<num; i++)
							{
								for(int j=0; j<num; j++)
								{
									decl=tMethodList->Nth(j);
									if(decl->GetOffset()==4*i)
										methodList->Append(decl);
								}
							}		
					
							cg->GenVTable($2,methodList);
							
							Declaration *classDecl=scopes->Lookup($2);
							int size=cg->GetStackFrameSize(ClassStackSize);
							//设置要为该类分配对象空间的时候的大小
							classDecl->SetStackFrameSize(size);

							scopes->PopScope(); 
						}
                ; 

OptExtends      :       T_Extends T_Identifier
                        { $$ = TypeForClassName($2); }
                |       /* empty */
                        { $$ = NULL; }
                ;

FieldList       :       FieldList Field
						{ if($2) $1->Append($2); $$ = $1; }
                |       /* empty */
						{$$=new DeclList();}
                ;

Field           :       VariableDecl 
						{$$=$1;}
                |       FunctionDefn
						{$$=$1;}
                |       FunctionDecl
						{$$=$1;}
                ;

FunctionDecl    :       Type T_Identifier '(' Formals ')' ';' 
                        { 
							Declaration * decl=BuildFnDecl($2, $1, $4, DeclOnly, &@2);
							Scope *tScope;
							Declaration *dec1;

							tScope=scopes->GetCurrentScope();

							//如果是在类域中的函数声明设置它的offset
							if(tScope->IsClassScope())
							{
								dec1=tScope->Lookup($2);
								if(dec1!=NULL)
								{
									//如果前面还有声明，offset设置为前面声明的offset
									if(dec1->IsFunctionDecl())
										decl->SetOffset(dec1->GetOffset());
									else
										cg->SetMethodOffset(decl);
								}
								else	
									cg->SetMethodOffset(decl);
							}
							$$=decl;
							scopes->Declare(decl);
							
						}
                ;
 
Formals         :       VariableList
						{$$=$1;}
                |       /* empty */
                        { $$ = new DeclList; }
                ;

VariableList    :       VariableList ',' Variable
                        { $1->Append($3); $$ = $1; }
                |       Variable
                        {	
							$$ = new DeclList();
							$$->Append($1); 
						}
                ;

FunctionDefn    :       Type T_Identifier '(' Formals ')' 
                        {
							Declaration *d = BuildFnDecl($2, $1, $4, FullDefn, &@2);
							Declaration *mythis;
							Scope *tScope;
							bool flag=false;

							if(scopes->GetCurrentScope()->IsClassScope())
							{
								flag=true;
							}

							if(scopes->GetCurrentScope()->IsGlobalScope())
							{
								tScope=scopes->GetCurrentScope();
								Declaration *temp=tScope->Lookup($2);
								//使该函数的的定义标识为有效，以便处理link错误
								if(temp!=NULL)
									temp->MakeFunDefined();
							}

							//设置类成员函数的offset
							if(flag)
							{
								tScope=scopes->GetCurrentScope();

								//先查找该函数是否已经声明过
								Declaration *temp=tScope->Lookup($2);
								if(temp!=NULL)
								{
									//如果已经声明过，将现在定义的函数的offset设置为前面声明的offset
									if(temp->IsFunctionDecl())
									{
										int offset=temp->GetOffset();
										d->SetOffset(offset);
										//使该函数的的定义标识为有效，以便处理link错误
										temp->MakeFunDefined();
									}
								}
								else
									cg->SetMethodOffset(d);
							}
							
							//将标示函数是否已经定义过的标识置为有效
							d->MakeFunDefined();

							$$=d;
							$<decl>$=d;
							scopes->Declare(d);

							scopes->PushScope(new Scope(d)); 
							cg->InitParaOffset();
						
							if(flag)
							{
								//如果是类中的函数定义，就将this作为第一个形参
								mythis=new Declaration(Declaration::Variable, "this", d->GetScope()->GetClassType());
								cg->SetParaOffset(mythis);
								scopes->Declare(mythis);
							}		
									
							DeclList *paraList=$4;
							int paraNum=paraList->NumElements();
							
							//设置个形参的offset
							for(int i=0; i<paraNum; i++)
							{