decafcparser.y

decafc的源代码

%{
/****************************************************************************
 * File name:	decafcParser.y						    *
 * Description:	parsing program for Decaf language			    *
 * Input:	none							    *
 * Output:	none							    *
 * Author:	Luojian Chen						    *
 * Date:	February 16, 1997					    *
 ****************************************************************************/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "decafc.h"
#include "ASTree.h"
#include "decafcError.h"
#include "symbolTable.h"

extern String	nodeNames[];
extern int	errorNumber;

/* external function prototypes */

extern void		yyunput(int);
extern NodePtr		CreateNode(NodeType, ...);
extern NodePtr		ReplaceNode(NodeType, NodePtr); 
extern NodePtr		MergeSubTrees(NodeType, ...);
extern void		yyerror(String);
extern void		ReportError(ErrorIndex, String, int, int);
extern SymbolTablePtr	NewSymbolTable(int);
extern SymbolTablePtr	DupSymbolTable(SymbolTablePtr);
extern ElementPtr	Insert(SymbolTablePtr, String, int, ElementPtr);
extern ElementPtr	Lookup(SymbolTablePtr, String);
extern void		FreeSymbolTable(SymbolTablePtr);
extern void		DisplaySymbolTable(SymbolTablePtr);
extern void		NewSymbolTableStack(SymbolTableStackPtr);
// extern SymbolTablePtr	Pop(SymbolTableStackPtr);
extern void		Pop(SymbolTableStackPtr, SymbolTablePtr *, int *);
extern void		SemanticCheck(NodePtr);
extern void		DisplayASTree(NodePtr);
extern void		CreateNewArrayType(NodePtr);
extern void		OptimizeUnaryPlusExp(NodePtr *);
extern void		OptimizeUnaryMiusExp(NodePtr *);
extern void		OptimizeNotExp(NodePtr *);
extern void		OptimizeEqualExp(NodePtr *);
extern void		OptimizeNotEqualExp(NodePtr *);
extern void		OptimizeLessEqualExp(NodePtr *);
extern void		OptimizeGreaterEqualExp(NodePtr *);
extern void		OptimizeLessExp(NodePtr *);
extern void		OptimizeGreaterExp(NodePtr *);
extern void		OptimizePlusExp(NodePtr *);
extern void		OptimizeMinusExp(NodePtr *);
extern void		OptimizeOrExp(NodePtr *);
extern void		OptimizeMultiplyExp(NodePtr *);
extern void		OptimizeDivideExp(NodePtr *);
extern void		OptimizeModularExp(NodePtr *);
extern void		OptimizeAndExp(NodePtr *);
extern void		GenerateCode(NodePtr);

/* external global variables */

extern int		yydebug;
extern ElementPtr	intTypePtr;
extern ElementPtr	voidTypePtr;
extern ElementPtr	refTypePtr;
extern ElementPtr	unknownTypePtr;
extern int		currentLineNumber;
extern int		currentColumnNumber;
// extern int		beginLocalVarID;


/* global variables */

NodePtr			rootNodePtr = NULL; /* pointer to the root of the parse tree */
NodePtr			nodePtr = NULL;	/* pointer to an error node */
SymbolTablePtr		typeSymbolTable = NULL;
SymbolTablePtr		currentBlockSymbolTable = NULL;
SymbolTableStack	symbolTableStack;
SymbolTableStackPtr	symbolTableStackPtr = &symbolTableStack;
Boolean			inMethod = FALSE;
String			currentClassName = NULL;
Boolean			hasMainMethod = FALSE;
NodePtr			mainMethodDecNodePtr = NULL;
int			localVarID = 0;
int			parameterVarID = 0;
Boolean			firstBlock = TRUE;
FILE			*CFileFp = NULL;
FILE			*HFileFp = NULL;
String			HFileName = NULL;

static SymbolTablePtr		currentClassSymbolTable = NULL;
static SymbolTablePtr		currentParameterSymbolTable = NULL;
static ElementPtr		elementPtr = NULL;
static String			methodName = NULL;
static int			classVarID = 0;

void	yyerror(String);
%}

/* YYSTYPE */

%union {
	NodePtr	nodePtr;
}

/* terminals */

%token TOKEN_INVALID_TOKEN
%token TOKEN_IDENTIFIER
%token TOKEN_NUMBER
%token TOKEN_KW_CLASS
%token TOKEN_KW_ELSE
%token TOKEN_KW_IF
%token TOKEN_KW_INT
%token TOKEN_KW_NEW
%token TOKEN_KW_NULL
%token TOKEN_KW_PRINT
%token TOKEN_KW_READ
%token TOKEN_KW_RETURN
%token TOKEN_KW_THIS
%token TOKEN_KW_VOID
%token TOKEN_KW_WHILE
%token TOKEN_OP_LEFT_SQUARE_BRACKET
%token TOKEN_OP_RIGHT_SQUARE_BRACKET
%token TOKEN_OP_LEFT_CURLY_BRACKET
%token TOKEN_OP_RIGHT_CURLY_BRACKET
%token TOKEN_OP_NOT_EQUAL
%token TOKEN_OP_EQUAL
%token TOKEN_OP_LESS
%token TOKEN_OP_GREATER
%token TOKEN_OP_LESS_OR_EQUAL
%token TOKEN_OP_GREATER_OR_EQUAL
%token TOKEN_OP_AND
%token TOKEN_OP_OR
%token TOKEN_OP_NOT
%token TOKEN_OP_PLUS
%token TOKEN_OP_MINUS
%token TOKEN_OP_MULTIPLY
%token TOKEN_OP_DIVIDE
%token TOKEN_OP_MODULAR
%token TOKEN_OP_SEMICOLON
%token TOKEN_OP_COMMA
%token TOKEN_OP_LEFT_PARENTHESIS
%token TOKEN_OP_RIGHT_PARENTHESIS
%token TOKEN_OP_ASSIGN
%token TOKEN_OP_COMMENTS
%token TOKEN_OP_DOT

/* associativity and precedence */

%left TOKEN_OP_EQUAL TOKEN_OP_NOT_EQUAL TOKEN_OP_LESS_OR_EQUAL TOKEN_OP_GREATER_OR_EQUAL TOKEN_OP_LESS TOKEN_OP_GREATER
%left TOKEN_OP_PLUS TOKEN_OP_MINUS TOKEN_OP_OR
%left TOKEN_OP_MULTIPLY TOKEN_OP_DIVIDE TOKEN_OP_MODULAR TOKEN_OP_AND
%right TOKEN_OP_NOT

%nonassoc LOWER_THAN_ELSE
%nonassoc TOKEN_KW_ELSE

%nonassoc error

%%

Program	:
	ClassDeclarationList
		{
		  /* create a node and link it with its children
		     this is the start rule, so the tree is completely
		     built when this production is reduced */

		  rootNodePtr = CreateNode(NODE_TYPE_PROGRAM,
					   1,
    					   $1.nodePtr);

		  if (hasMainMethod == FALSE) {
		    ReportError(ERROR_NO_MAIN_METHOD,
				STRING_MAIN,
				rootNodePtr->lineNumber,
				rootNodePtr->columnNumber);
		  }
		}
  ;

ClassDeclarationList :
	ClassDeclaration
		{
		  /* create a node and link it with its children
		     the same in other productions */

		  $$.nodePtr = CreateNode(NODE_TYPE_CLASS_DEC_LIST,
					  1,
					  $1.nodePtr);
		}
  |	ClassDeclarationList ClassDeclaration
		{
		  $$.nodePtr = MergeSubTrees(NODE_TYPE_CLASS_DEC_LIST,
					     2,
					     $1.nodePtr,
					     $2.nodePtr);
		}
  ;

ClassDeclaration :
	TOKEN_KW_CLASS TOKEN_IDENTIFIER ClassBody
		{
		  $$.nodePtr = CreateNode(NODE_TYPE_CLASS_DEC,
					  2,
					  $2.nodePtr,
					  $3.nodePtr);

		  currentClassName = $2.nodePtr->info.lexeme;

		  if (Lookup(typeSymbolTable, currentClassName) == NULL) {
		    $$.nodePtr->typePtr =
		      Insert(typeSymbolTable, currentClassName, 0, NULL);
		  } else {
		    ReportError(ERROR_CLASS_REDECLARATION,
				currentClassName,
				$2.nodePtr->lineNumber,
				$2.nodePtr->columnNumber);
		  }

		  $$.nodePtr->info.symbolTablePtr = currentClassSymbolTable;
		  currentClassSymbolTable = NewSymbolTable(SYMBOL_TABLE_SIZE);
		  currentBlockSymbolTable = NewSymbolTable(SYMBOL_TABLE_SIZE);

		  #ifdef DEBUG
		  printf("\nSymbol table for class %s:\n",
			 currentClassName);
		  DisplaySymbolTable($$.nodePtr->info.symbolTablePtr);
		  #endif
		}
  |	TOKEN_KW_CLASS error ClassBody
		{
		  /* class name is missing */

		  /* discard lookahead, print an error message
		     create an error node
		     create a interior node for ClassDeclaration
		     and link it with its children
		     the same in other error productions */

		  yyclearin;
		  yyerrok;
		  ReportError(ERROR_NO_CLASS_NAME,
			      NULL,
			      currentLineNumber,
			      currentColumnNumber);

		  nodePtr = CreateNode(NODE_TYPE_ERROR, 0);
		  $$.nodePtr = CreateNode(NODE_TYPE_CLASS_DEC,
					  3,
					  $1.nodePtr,
					  nodePtr,
					  $3.nodePtr);

		  strcpy(currentClassName, "");

		  $$.nodePtr->info.symbolTablePtr = currentClassSymbolTable;
		  currentClassSymbolTable = NewSymbolTable(SYMBOL_TABLE_SIZE);
		  currentBlockSymbolTable = NewSymbolTable(SYMBOL_TABLE_SIZE);

		  #ifdef DEBUG
		  printf("\nSymbol table for class %s:\n",
			 currentClassName);
		  DisplaySymbolTable($$.nodePtr->info.symbolTablePtr);
		  #endif
		}
  |	error TOKEN_KW_CLASS
		{
		  yyclearin;
		  yyerrok;
		  yyless(0);	/* unread "class" */
		  ReportError(ERROR_MISPLACED_STATEMENTS,
			      NULL,
			      currentLineNumber,
			      currentColumnNumber);

		  nodePtr = CreateNode(NODE_TYPE_ERROR, 0);
		  $$.nodePtr = CreateNode(NODE_TYPE_CLASS_DEC,
					  1,
					  nodePtr);
		}
  ;

ClassBody :
	TOKEN_OP_LEFT_CURLY_BRACKET
	TOKEN_OP_RIGHT_CURLY_BRACKET
		{
		  $$.nodePtr = CreateNode(NODE_TYPE_CLASS_BODY,
					  3,
					  NULL,
					  NULL,
					  NULL);
		  classVarID = 0;
		}
  |	TOKEN_OP_LEFT_CURLY_BRACKET
		VarDeclarationList
	TOKEN_OP_RIGHT_CURLY_BRACKET
		{
		  $$.nodePtr = CreateNode(NODE_TYPE_CLASS_BODY,
					  3,
					  $2.nodePtr,
					  NULL,
					  NULL);
		  classVarID = 0;
		}
  |	TOKEN_OP_LEFT_CURLY_BRACKET
		ConstructorDeclaration
	TOKEN_OP_RIGHT_CURLY_BRACKET
		{
		  $$.nodePtr = CreateNode(NODE_TYPE_CLASS_BODY,
					  3,
					  NULL,
					  $2.nodePtr,
					  NULL);
		  classVarID = 0;
		}
  |	TOKEN_OP_LEFT_CURLY_BRACKET
		MethodDeclarationList
	TOKEN_OP_RIGHT_CURLY_BRACKET
		{
		  $$.nodePtr = CreateNode(NODE_TYPE_CLASS_BODY,
					  3,
					  NULL,
					  NULL,
					  $2.nodePtr);
		  classVarID = 0;
		}
  |	TOKEN_OP_LEFT_CURLY_BRACKET
		VarDeclarationList
		ConstructorDeclaration
	TOKEN_OP_RIGHT_CURLY_BRACKET
		{
		  $$.nodePtr = CreateNode(NODE_TYPE_CLASS_BODY,
					  3,
					  $2.nodePtr,
					  $3.nodePtr,
					  NULL);
		  classVarID = 0;
		}
  |	TOKEN_OP_LEFT_CURLY_BRACKET
		VarDeclarationList
		MethodDeclarationList
	TOKEN_OP_RIGHT_CURLY_BRACKET
		{
		  $$.nodePtr = CreateNode(NODE_TYPE_CLASS_BODY,
					  3,
					  $2.nodePtr,
					  NULL,
					  $3.nodePtr);
		  classVarID = 0;
		}
  |	TOKEN_OP_LEFT_CURLY_BRACKET
		ConstructorDeclaration
		MethodDeclarationList
	TOKEN_OP_RIGHT_CURLY_BRACKET
		{
		  $$.nodePtr = CreateNode(NODE_TYPE_CLASS_BODY,
					  3,
					  NULL,
					  $2.nodePtr,
					  $3.nodePtr);
		  classVarID = 0;
		}
  |	TOKEN_OP_LEFT_CURLY_BRACKET
		VarDeclarationList
		ConstructorDeclaration
		MethodDeclarationList
	TOKEN_OP_RIGHT_CURLY_BRACKET
		{
		  $$.nodePtr = CreateNode(NODE_TYPE_CLASS_BODY,
					  3,
					  $2.nodePtr,
					  $3.nodePtr,
					  $4.nodePtr);
		  classVarID = 0;
		}
  |	TOKEN_OP_LEFT_CURLY_BRACKET
		error
	TOKEN_OP_RIGHT_CURLY_BRACKET
		{
		  yyclearin;
		  yyerrok;
		  ReportError(ERROR_INVALID_CLASS_BODY,
			      NULL,
			      currentLineNumber,
			      currentColumnNumber);

		  $$.nodePtr = CreateNode(NODE_TYPE_CLASS_BODY,
					  3,
					  NULL,
					  NULL,
					  NULL);
		}
  ;

VarDeclarationList :
	VarDeclaration
		{
		  $$.nodePtr = CreateNode(NODE_TYPE_VAR_DEC_LIST,
					  1,
					  $1.nodePtr);
		}
  |	VarDeclarationList VarDeclaration
		{
		  $$.nodePtr = MergeSubTrees(NODE_TYPE_VAR_DEC_LIST,
					     2,
					     $1.nodePtr,
					     $2.nodePtr);
		}
  ;

VarDeclaration :
	Type TOKEN_IDENTIFIER TOKEN_OP_SEMICOLON
		{
		  $$.nodePtr = CreateNode(NODE_TYPE_VAR_DEC,
					  2,
					  $1.nodePtr,
					  $2.nodePtr);

		  // if ($1.nodePtr->numberOfChildren > 0) {
		    // CreateNewArrayType($1.nodePtr);
		  // }

		  if (Lookup(currentBlockSymbolTable,
			     $2.nodePtr->info.lexeme) == NULL) {
		    elementPtr = Insert(currentBlockSymbolTable,
			   		$2.nodePtr->info.lexeme,
					classVarID + FIRST_CLASS_VAR_OFFSET,
			   		$1.nodePtr->typePtr);
		    elementPtr = Insert(currentClassSymbolTable,
			   		$2.nodePtr->info.lexeme,
		    			classVarID + FIRST_CLASS_VAR_OFFSET,
			   		$1.nodePtr->typePtr);
		    classVarID ++;
		  } else {
		    ReportError(ERROR_VAR_REDECLARATION,
				NULL,
				currentLineNumber,
				currentColumnNumber);
		  }
		}
  |	Type TOKEN_IDENTIFIER error
		{
		  yyclearin;
		  yyerrok;
		  ReportError(ERROR_MISSING_SEMICOLON,
			      NULL,
			      currentLineNumber,
			      currentColumnNumber);

		  $$.nodePtr = CreateNode(NODE_TYPE_VAR_DEC,
					  2,
					  $1.nodePtr,
					  $2.nodePtr);

		  // if ($1.nodePtr->numberOfChildren > 0) {
		    // CreateNewArrayType($1.nodePtr);
		  // }

		  if (Lookup(currentBlockSymbolTable,
			     $2.nodePtr->info.lexeme) == NULL) {
		    Insert(currentBlockSymbolTable,
			   $2.nodePtr->info.lexeme,
		    	   classVarID + FIRST_CLASS_VAR_OFFSET,
			   $1.nodePtr->typePtr);
		    classVarID ++;
		  } else {
		    ReportError(ERROR_VAR_REDECLARATION,
				NULL,
				currentLineNumber,
				currentColumnNumber);
		  }
		}
  |	Type error TOKEN_OP_SEMICOLON
		{
		  yyclearin;
		  yyerrok;
		  ReportError(ERROR_INVALID_VAR_DECLARATION,
			      NULL,
			      currentLineNumber,
			      currentColumnNumber);
		  nodePtr = CreateNode(NODE_TYPE_ERROR, 0);

		  $$.nodePtr = CreateNode(NODE_TYPE_VAR_DEC,
					  2,
					  $1.nodePtr,
					  nodePtr);
		}
  ;

Type :
	SimpleType
		{
		  ReplaceNode(NODE_TYPE_TYPE, $1.nodePtr);
		  $$.nodePtr = $1.nodePtr;
		}
  |	IntArrayDeclaration
		{
		  ReplaceNode(NODE_TYPE_TYPE, $1.nodePtr);
		  $$.nodePtr = $1.nodePtr;
		}
  |	OtherArrayDeclaration
		{
		  ReplaceNode(NODE_TYPE_TYPE, $1.nodePtr);
		  $$.nodePtr = $1.nodePtr;
		}
  ;

SimpleType :
	TOKEN_KW_INT
		{
		  $$.nodePtr = $1.nodePtr;
		}
  |	TOKEN_IDENTIFIER
		{
		  $$.nodePtr = $1.nodePtr;
		}
  ;

IntArrayDeclaration :
	TOKEN_KW_INT
	TOKEN_OP_LEFT_SQUARE_BRACKET TOKEN_OP_RIGHT_SQUARE_BRACKET
		{
		  nodePtr = CreateNode(NODE_TYPE_DIM, 0);
		  $$.nodePtr = CreateNode(NODE_TYPE_INT_ARRAY_DEC,
					  2,
					  $1.nodePtr,
					  nodePtr);
		  CreateNewArrayType($$.nodePtr);
		}
  |	IntArrayDeclaration
	TOKEN_OP_LEFT_SQUARE_BRACKET TOKEN_OP_RIGHT_SQUARE_BRACKET
		{
		  nodePtr = CreateNode(NODE_TYPE_DIM, 0);
		  $$.nodePtr = CreateNode(NODE_TYPE_INT_ARRAY_DEC,
					  2,
					  $1.nodePtr,
					  nodePtr);
		  CreateNewArrayType($$.nodePtr);
		}
  |	TOKEN_KW_INT TOKEN_OP_LEFT_SQUARE_BRACKET error TOKEN_IDENTIFIER
		{
		  yyclearin;
		  yyerrok;
		  yyless(0);	/* unread "identifier" */
		  ReportError(ERROR_UNBALANCED_BRACKETS,
			      NULL,
			      currentLineNumber,
			      currentColumnNumber);

		  nodePtr = CreateNode(NODE_TYPE_ERROR, 0);
		  $$.nodePtr = CreateNode(NODE_TYPE_INT_ARRAY_DEC,
					  2,
					  $1.nodePtr,
					  nodePtr);
		  CreateNewArrayType($$.nodePtr);
		}
  |	IntArrayDeclaration TOKEN_OP_LEFT_SQUARE_BRACKET error TOKEN_IDENTIFIER