spl.y.c

浙江大学编译原理课程设计源代码,高等院校计算机专业

%{

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "common.h"
#include "symtab.h"
#include "error.h"
#include "tree.h"

#ifdef _MSDOS_
#include "debug.h"
#include "type.h"
#endif

#include "x86.h"

extern char *yytext;
symtab *ptab;
symbol *p, *q;
tree   *t;
type *pt, *qt;
int temp;
symbol* pop_term_stack();
symbol* top_term_stack();
void push_term_stack(symbol * p);

Env global_env;
Env main_env;

Symtab	rtn = NULL;
Symbol	arg = NULL;

#ifdef GENERATE_AST

Tree pop_ast_stack();
Tree top_ast_stack();
void push_ast_stack(Tree t);

int pop_lbl_stack();
int top_lbl_stack();
void push_lbl_stack(int id);

int pop_case_stack();
int top_case_stack();
void push_case_stack(int id);

List pop_case_ast_stack();
List top_case_ast_stack();
void push_case_ast_stack(List newlist);

struct list ast_forest;
struct list para_list;				/* for parameter list. */
List  case_list = NULL;
struct list dag_forest;				/* for dags. */
Tree   	args;
Tree   	now_function;
Tree	t;
Symbol	new_label = NULL;
/* Symbol	case_label = NULL;	*/
Symbol	test_label = NULL;
Symbol  exit_label = NULL;
char 	mini_buf[NAME_LEN];			/* buffer for generated name. */
int		if_label_count;				/* count for label of if test. */
int		repeat_label_count;			/* count for label of repeat. */
int		case_label_count;			/* count for label of case. */
int		switch_label_count;			/* count for label of switch. */
int		do_label_count;				/* count for label of do. */
int		while_label_count;			/* count for label of while. */
int		for_label_count;			/* count for label of for. */

#endif

int parser_init();

Symbol install_temporary_symbol(char *name, int deftype, int typeid);
Type install_temporary_type(char *name, int deftype, int typeid);

void trap_in_debug();

#ifdef DEBUG
#define DEBUG_POINT	trap_in_debug();
#endif

#if 0

#ifndef GENERATE_AST

%type  <num>proc_stmt assign_stmt
%type  <num>expression expression_list
%type  <p_symbol>factor term expr

#else

%type  <p_tree>proc_stmt assign_stmt
%type  <p_tree>factor term expr
%type  <p_tree>expression expression_list

#endif

#endif

%}

%union {
	char 		p_char[NAME_LEN];
	int 		num;
	int 		ascii;
	Symbol 		p_symbol;
	Type		p_type;
	KEYENTRY	*p_lex;
	Tree 		p_tree;
}

%error-verbose

%term kAND
%term kARRAY
%term kBEGIN
%term kCASE
%term kCONST
%term kDIV
%term kDO
%term kDOWNTO
%term kELSE
%term kEND
%term kFILE
%term kFOR
%term kFUNCTION
%term kGOTO
%term kIF
%term kIN
%term kLABEL
%term kMOD
%term kNIL
%term kNOT
%term kOF
%term kOR
%term kPACKED
%term kPROCEDURE
%term kPROGRAM
%term kRECORD
%term kREPEAT
%term kSET
%term kTHEN
%term kTO
%term kTYPE
%term kUNTIL
%term kVAR
%term kWHILE
%term kWITH
%term <num>SYS_CON
%term cFALSE
%term cTRUE
%term cMAXINT
%term <p_char>cSTRING
%term <num>cINTEGER
%term <p_char>cREAL
%term <p_char>cCHAR
%term <p_char>cBOOLEAN
%term <p_char>SYS_TYPE
%term tINTEGER
%term tCHAR
%term tREAL
%term tBOOLEAN
%term tTEXT
%term <p_lex>SYS_FUNCT
%term fABS
%term fCHR
%term fODD
%term fORD
%term fPRED
%term fSQR
%term fSQRT
%term fSUCC
%term <p_lex>SYS_PROC
%term pREAD
%term pREADLN

%term  pWRITE
%term  pWRITELN
%term  oPLUS
%term  oMINUS
%term  oMUL
%term  oDIV
%term  oEQUAL
%term  oASSIGN
%term  oUNEQU
%term  oLT
%term  oLE
%term  oGT
%term  oGE
%term  oCOMMA
%term  oSEMI
%term  oCOLON
%term  oQUOTE
%term  oDOT
%term  oDOTDOT
%term  oARROW
%term  oLP
%term  oRP
%term  oLB
%term  oRB
%term  oLC
%term  oRC
%term  <p_char>yNAME

%type  <p_symbol>const_value
%type  <p_symbol>name_list
%type  <p_symbol>val_para_list var_para_list
%type  <num>direction
%type  <p_type>type_decl_list type_definition
%type  <p_type>type_decl simple_type_decl
%type  <p_type>array_type_decl record_type_decl
%type  <p_symbol>field_decl field_decl_list

%type  <p_tree>proc_stmt assign_stmt
%type  <p_tree>factor term expr
%type  <p_tree>expression expression_list

%start  program

%%

program
:first_act_at_prog program_head sub_program oDOT
{
	//dump_symtab(Global_symtab);
	pop_symtab_stack();
#ifdef GENERATE_AST
	if (!err_occur())
	{
		list_clear(&dag_forest);
		t = new_tree(TAIL, NULL, NULL, NULL);
		t->u.generic.symtab = top_symtab_stack();
		list_append(&ast_forest, t);

		/* generate dag forest. */
		gen_dag(&ast_forest, &dag_forest);

		/* emit asm code. */
		emit_code(&dag_forest);

		(*(IR->main_end))(&main_env);

		/* call end interface. */
		(*(IR->program_end))(&global_env);
	}
#else
	emit_main_epilogue(Global_symtab);
	emit_program_epilogue(Global_symtab);
#endif
	return 0;
}
;

first_act_at_prog
:   
{
	parser_init();
	make_global_symtab();
	make_system_symtab();
	push_symtab_stack(Global_symtab);
};

program_head
:kPROGRAM yNAME oSEMI 
{
	strcpy(Global_symtab->name, $2);
	snprintf(Global_symtab->rname, sizeof(Global_symtab->rname), "main");
	Global_symtab->defn = DEF_PROG;
#ifdef GENERATE_AST
	global_env.u.program.tab = Global_symtab;
	/* call initialization interface. */
	(*(IR->program_begin))(&global_env);
#else
	emit_program_prologue(Global_symtab);
#endif

}
|error oSEMI
;

sub_program
:routine_head
{
#ifdef GENERATE_AST
	main_env.u.main.tab = Global_symtab;
	(*(IR->main_begin))(&main_env);
	list_clear(&ast_forest);
	list_clear(&para_list);
	
	push_symtab_stack(Global_symtab);
	/*
	ptab = top_symtab_stack();
	strncpy(ptab->name, $3, NAME_LEN);
	sprintf(ptab->rname, "rtn%03d",ptab->id);
	ptab->defn = DEF_PROC;
	p = new_symbol($3, DEF_PROC, TYPE_VOID);
	add_symbol_to_table(ptab,p);
	reverse_parameters(ptab);
	{
		Tree header;
		
		header = new_tree(HEADER, find_type_by_id(TYPE_VOID), NULL, NULL); 
		header->u.header.para = &para_list;
		list_append(&ast_forest, header);
		now_function = new_tree(ROUTINE, find_type_by_id(TYPE_VOID), header, NULL);
	}

	ptab = new_symtab(top_symtab_stack());
	push_symtab_stack(ptab);
	*/

#else
	emit_main_prologue(Global_symtab);
#endif

}
routine_body
{
}
;

name_list
:name_list oCOMMA yNAME 
{
	p = new_symbol($3, DEF_UNKNOWN, TYPE_UNKNOWN);
	for(q = $1; q->next; q = q->next);
	q->next = p; p ->next = NULL;
	$$ = $1;
}
|yNAME
{
	p = new_symbol($1, DEF_UNKNOWN, TYPE_UNKNOWN);
	$$ = p;
}
|yNAME error oSEMI
|yNAME error oCOMMA
;

sub_routine
:routine_head routine_body
;

routine_head
:label_part const_part type_part var_part routine_part
{
#ifdef GENERATE_AST
#else
	emit_routine_prologue(top_symtab_stack());
#endif
}
;

label_part
:
;

const_part
:kCONST const_expr_list
|
;

const_expr_list
:const_expr_list yNAME oEQUAL const_value oSEMI
{
	/* change name of symbol const_value to yNAME */
	strncpy($4->name, $2, NAME_LEN);
	add_symbol_to_table(
		top_symtab_stack(), $4);
}
|yNAME oEQUAL const_value oSEMI
{
	/* change name of symbol const_value to yNAME */
	strncpy($3->name, $1, NAME_LEN);
	add_symbol_to_table(
		top_symtab_stack(),$3);
}
;

const_value
:cINTEGER
{
	/* integer const, temperary named $$$, will change later. */
	p = new_symbol("$$$", DEF_CONST,
		TYPE_INTEGER);
	p->v.i = $1;
	$$ = p;
}
|cREAL
{
	p = new_symbol("$$$",DEF_CONST,
		TYPE_REAL);

	p->v.f = atof($1);
	$$ = p;
}
|cCHAR
{
	p = new_symbol("$$$", DEF_CONST,
		TYPE_CHAR);

	p->v.c= $1[1];
	$$ = p;
}
|cSTRING
{
	p = new_symbol("$$$",DEF_CONST,
		TYPE_STRING);

	p->v.s = strdup($1);
	$$ = p;
}
|SYS_CON
{
	p = new_symbol("$$$", DEF_CONST,
		TYPE_UNKNOWN);

	switch($1)
	{
	case cMAXINT:
		strcpy(p->rname, "maxint");
		p->v.i = (1 << (IR->intmetric.size * 8)) - 1;
		p->type = find_type_by_id(TYPE_INTEGER);
		break;

	case cFALSE  :
		strcpy(p->rname, "0");
		p->v.b = 0;
		p->type = find_type_by_id(TYPE_BOOLEAN);
		break;
		  
	case cTRUE:
		strcpy(p->rname, "1");
		p->v.b = 1;
		p->type = find_type_by_id(TYPE_BOOLEAN);
		break; 

	default:
		p->type = find_type_by_id(TYPE_VOID);
		break;
	}

	$$ = p;
}
;

type_part
:kTYPE type_decl_list
|
;

type_decl_list
:type_decl_list type_definition
|type_definition
;

type_definition
:yNAME oEQUAL type_decl oSEMI
{
	if($3->name[0] == '$')
	{
		/* a new type. */
		$$ = $3;
		strncpy($$->name, $1, NAME_LEN);
	}
	else{
		/* an existed type. */
		$$ = clone_type($3);
		strncpy($$->name, $1, NAME_LEN);
		add_type_to_table(
			top_symtab_stack(), $$);
	}
}
;

type_decl
:simple_type_decl
|array_type_decl
|record_type_decl
;

array_type_decl
:kARRAY oLB simple_type_decl oRB kOF type_decl
{
	$$ = new_array_type("$$$", $3, $6);
	add_type_to_table(
		top_symtab_stack(),$$);
} 
;

record_type_decl
:kRECORD field_decl_list kEND
{ 
	pt = new_record_type("$$$", $2);
 	add_type_to_table(top_symtab_stack(), pt);
	$$ = pt;
}
;

field_decl_list
:field_decl_list field_decl
{
    for(p = $1; p->next; p = p->next);
	p->next = $2;
	$$ = $1;  
}
|field_decl
{
	$$ = $1;
}
;

field_decl
:name_list oCOLON type_decl oSEMI
{    
	for(p = $1; p; p = p->next) {
		if($3->type_id == TYPE_SUBRANGE)
			p->type = $3->first->type;
		else if($3->type_id == TYPE_ENUM)
			p->type = find_type_by_id(TYPE_INTEGER);
		else
			p->type = find_type_by_id($3->type_id);

		p->type_link = $3;
		p->defn = DEF_FIELD;
	}
	$$ = $1;
}
;

simple_type_decl
:SYS_TYPE
{
	pt = find_type_by_name($1);
	if(!pt)
		parse_error("Undeclared type name",$1);
	$$ = pt;
}
|yNAME
{
	pt = find_type_by_name($1);
	if (!pt)
	{
		parse_error("Undeclared type name", $1);
		return 0;
	}
	$$ = pt;
}
|oLP name_list oRP
{
	$$ = new_enum_type("$$$");
	add_enum_elements($$, $2);
	add_type_to_table(
		top_symtab_stack(),$$);
}
|const_value oDOTDOT const_value
{
	if($1->type->type_id != $3->type->type_id){
		parse_error("type mismatch","");
		return 0;
	}
	$$ = new_subrange_type("$$$", $1->type->type_id);
	add_type_to_table(
		top_symtab_stack(), $$);

	if($1->type->type_id == TYPE_INTEGER)
		set_subrange_bound($$,
			(int)$1->v.i,(int)$3->v.i);
	else if ($1->type->type_id == TYPE_BOOLEAN)
		set_subrange_bound($$,
			(int)$1->v.b,(int)$3->v.b);
	else if ($1->type->type_id == TYPE_CHAR)
		set_subrange_bound($$,
			(int)$1->v.c,(int)$3->v.c);
	else
		parse_error("invalid element type of subrange","");
}
|oMINUS const_value oDOTDOT const_value
{
	if($2->type->type_id != $4->type->type_id){
		parse_error("type mismatch","");
		/* return 0; */
	}

	$$ = new_subrange_type("$$$",
		$2->type->type_id);
		
	add_type_to_table(
		top_symtab_stack(),$$);

	if($2->type->type_id == TYPE_INTEGER){
		$2->v.i= -$2->v.i;
		set_subrange_bound($$,
			(int)$2->v.i,(int)$4->v.i);
	}
	else if ($2->type->type_id == TYPE_BOOLEAN){
		$2->v.b ^= 1;
		set_subrange_bound($$,
			(int)$2->v.b,(int)$4->v.b);
	}
	else if ($2->type->type_id == TYPE_CHAR)
		parse_error("invalid operator","");
	else
   		parse_error("invalid element type of subrange","");
}
|oMINUS const_value oDOTDOT oMINUS const_value
{
	if($2->type->type_id != $5->type->type_id) {
		parse_error("type mismatch.","");
		return  0;
	}
	
	$$ = new_subrange_type("$$$", $2->type->type_id);

	add_type_to_table(
		top_symtab_stack(),$$);

	if($2->type->type_id == TYPE_INTEGER){
		$2->v.i = -$2->v.i;
		$5->v.i = -$5->v.i;
	
		set_subrange_bound($$,(int)$2->v.i,
			(int)$5->v.i);
	}
	else if ($2->type->type_id == TYPE_BOOLEAN){
		$2->v.b ^= 1;
		$5->v.b ^= 1;
		set_subrange_bound($$,(int)$2->v.b,
		(int)$5->v.b);
	}
	else if ($2->type->type_id == TYPE_CHAR)
		parse_error("invalid operator","");
	else
		parse_error("invalid element type of subrange","");
}
|yNAME oDOTDOT yNAME
{
	p = find_element(top_symtab_stack(), $1);

	if(!p){
		parse_error("Undeclared identifier", $1);
		install_temporary_symbol($1, DEF_ELEMENT, TYPE_INTEGER);
		/* return 0; */
	}
	
	if(p->defn != DEF_ELEMENT){
		parse_error("not an element identifier", $1);
		/* return 0; */
	}
	
	q = find_element(top_symtab_stack(), $3);
	if(!q){
		parse_error("Undeclared identifier", $3);
		install_temporary_symbol($3, DEF_ELEMENT, TYPE_INTEGER);
		/* return 0; */
	}
	if(q->defn != DEF_ELEMENT){
		parse_error("Not an element identifier", $3);
		/* return 0; */
	}
	
	if(p && q){
		$$ = new_subrange_type("$$$", TYPE_INTEGER);
		add_type_to_table(
			top_symtab_stack(),$$);
		set_subrange_bound($$, p->v.i, q->v.i);
	}
	else
		$$ = NULL;
}
;

var_part
:kVAR var_decl_list
|
;

var_decl_list
:var_decl_list var_decl
|var_decl
;

var_decl
:name_list oCOLON type_decl oSEMI
{    
	ptab = top_symtab_stack();
	
	for(p = $1; p ;){
		if($3->type_id == TYPE_SUBRANGE)
			p->type = find_type_by_id($3->first->type->type_id);
		else if($3->type_id == TYPE_ENUM)
			p->type = find_type_by_id(TYPE_INTEGER);
		else
			p->type = find_type_by_id($3->type_id);

		p->type_link = $3;
		p->defn = DEF_VAR;

		q = p; p = p->next;
		q->next = NULL;
		add_symbol_to_table(ptab, q);
	}
	$1 = NULL;
}
;

routine_part
:routine_part function_decl
|routine_part procedure_decl
|function_decl
|procedure_decl
|
;

function_decl
:function_head oSEMI sub_routine oSEMI 
{
#ifdef GENERATE_AST
	if (!err_occur())
	{
		
		list_clear(&dag_forest);
		t = new_tree(TAIL, NULL, NULL, NULL);
		t->u.generic.symtab = top_symtab_stack();
		list_append(&ast_forest, t);

		/* generate dag forest. */
		gen_dag(&ast_forest, &dag_forest);

		/* emit asm code. */
		emit_code(&dag_forest);
	}
#else
	emit_routine_epilogue(top_symtab_stack());
#endif

	pop_symtab_stack();
}
;

function_head
:kFUNCTION
{
#ifdef GENERATE_AST
	list_clear(&ast_forest);
	list_clear(&para_list);
#endif

	ptab = new_symtab(top_symtab_stack());
	push_symtab_stack(ptab);
}
yNAME parameters oCOLON
simple_type_decl
{
	ptab = top_symtab_stack();
	strncpy(ptab->name, $3, NAME_LEN);
	sprintf(ptab->rname, "rtn%03d",ptab->id);
	ptab->defn = DEF_FUNCT;
	
	if($6->type_id == TYPE_SUBRANGE)
		ptab->type = $6->first->type;
	else if($6->type_id == TYPE_ENUM)
		ptab->type = find_type_by_id(TYPE_INTEGER);
	else
		ptab->type = find_type_by_id($6->type_id);

	p = new_symbol($3, DEF_FUNCT, ptab->type->type_id);
	p->type_link = $6;
	add_symbol_to_table(ptab, p);
	reverse_parameters(ptab);
#ifdef GENERATE_AST
	{
		Tree header;
		
		header = new_tree(HEADER, ptab->type, NULL, NULL);
		header->u.header.para = &para_list;
		header->u.header.symtab = ptab;
		list_append(&ast_forest, header);
		now_function = new_tree(FUNCTION, ptab->type, header, NULL);
	}
#endif	
}
;

procedure_decl
:procedure_head oSEMI sub_routine oSEMI
{