c--.y

简单实现C--语言的编译器

%{
#include 	<ctype.h>
#include 	<string.h>
#include 	<stdio.h>
#include 	<stdlib.h>
//#include      <assert.h>

#define HASHSIZE 128

typedef struct paramp{   //函数参数
	int type;
	char *code;  // 参数的代码 push ...
	struct paramp *next; 
}paramtp;

typedef struct {
	char *name; /* symbol name */
	int scope; /* scope level */
	int type;
	int offset; /* for functions: size of local variables */
	int isargv;  /* 判定所给ID 是否是函数参数 */
	int is_fun_ret;  //函数是否有返回值
	int ret_const;  //函数是否返回常数
	int retvalue;    //函数的常数返回值
	int ret;     /*return value */
 	paramtp *paramer;  /* 参数表 */
} symbol ;


struct sym_entry {
	symbol sym; /* this symbol */
	struct sym_entry *next; /* next entry on hash chain */
};

struct table {
	int level; /* scope level for this table */
	struct table *previous; /* table at lower scope */
	struct sym_entry *buckets[HASHSIZE]; /* hash buckets */
};

typedef struct  //四元组
{
    char op;
    symbol *x, *y, *z;
} Quadruple;


typedef struct  // ?? 
{
    char *translation;
    int variable;
} myattribute;

typedef struct  // ??
{  char * name;
} fun_type;

struct string_data {
  	int index; //在数据段只能感的位置
	int is_n;  //是否有带回车
  	char * value;  //具体的串值
};

int n_const_strings = 0;  //常量串的个数
struct string_data const_strings[100];  // 具体内容

struct table * table_stack[100];   /*符号表栈  */ 
struct table * global_table;    /*全局符号表 */
int table_len = 0;
int offset_stack[100];
int offset_len = 0;
int level = 0;
int verbose = 0;    //是否DEBUG

int is_error = 0;       //可用于判断是否出错，若有错，verbose++；最后判断verbose是否为0 ，做相应的动作
int is_first = 0;       //决定.code 的位置
int is_one_var = 0;     // 判断表达式右边是否只有一个操作数
int is_funret = 0;      // 是否有函数返回
int data_place = 0;     //数据段的位移
symbol *temp_ret;       //函数返回的临时存放单元


void trace(char *s) { if (verbose) fprintf(stderr, s); }

symbol *lookup_all(char *name, struct table *tp) {
	struct sym_entry *p;
	unsigned h = ((unsigned)name)&(HASHSIZE-1); /*not素数 */
	do
		for (p = tp->buckets[h]; p; p = p->next)
			if (name == p->sym.name) return &p->sym;
	while (tp = tp->previous);
	return 0;
}


symbol *lookup(char *name, struct table *tp) {  /* 查找是否已在该层符号表中存在 */
	struct sym_entry *p;
	unsigned h = ((unsigned)name)&(HASHSIZE-1); /*not素数 */
	for (p = tp->buckets[h]; p; p = p->next)	
		if (name == p->sym.name) 
			return &p->sym;
	return 0;
}


struct table * mktable(struct table *previous, int level) {
	int i;
	struct table *new = (struct table *)malloc(sizeof *new);
	new->previous = previous; new->level = level;
	for (i = 0; i < HASHSIZE; i++)
		new->buckets[i] = 0;
	return new;
}

symbol *insert(char *name, struct table *tpp) {
	unsigned h = ((unsigned)name)&(HASHSIZE-1);
	struct table *tp = tpp;
	struct sym_entry *p = (struct sym_entry *)malloc(sizeof *p);
	if (tp->level < level) { // 当前scope level
		tp = mktable(tp, level);
		table_stack[table_len] = tp; 
		table_len ++;
		offset_stack[offset_len] = 0;
		offset_len ++;
	}
	p->sym.name = name; 
	p->sym.scope = level; 
	p->sym.type = 0; /*假设是常数, 常数的类型为0*/
	p->next = tp->buckets[h];
	tp->buckets[h] = p; /* 新名字在表头 */
	return &p->sym;
}


typedef struct {  // 表达式类型
  	int is_const; 
	int type;    /* 类型  */
  	int value;   /* 表达式的值 */
	int aa;
  	symbol * place;
  	symbol * offset; /* for array */
  	char * code; //对应的代码
} expr;

char * insert_id(char *name);    // define in c--.lex.l HASH

symbol * newtemp()
{   //生成一个临时变量
    static int index = 1;
    char tmpname[20];
    symbol * s;

    sprintf(tmpname, "__t%d", index);
    index++;
    s = insert(insert_id(tmpname), table_stack[table_len-1]);
    s->offset = offset_stack[offset_len-1];
    offset_stack[offset_len-1] += 4;
    return s;
}

char * newlabel()
{  //生成一个标号
	static int index = 1;
	char tmpname[20];
	char *temp;
	int len;

	sprintf(tmpname, "__@%d", index);
   	index++;
	len = strlen(tmpname);   //不能直接返回tmpname
	temp = (char *)malloc(len+1);
	strcpy(temp,tmpname);
	return temp;
}


int is_C(char *fun_name)  
{   // 因为是C 函数，没有bool型
	char *C_FUN[7] = {"main","puts","gets","write","read","printf","scanf"};  //应该不止这些
	int i = 0;
	
	while(i<7){
		if(strcmp(C_FUN[i],fun_name)==0) break;
		i++;
	}
	if(i==7) return 0;
	else return 1;
}


%}



//********************************************************************************************



%token 	ID  NUM  INT  VOID  CHAR  IF  ELSE WHILE  RETURN  CDECL  STDCALL  
		EQ  NE  LT  GT  LE  GE   AND  OR  STRING_LITERAL CHAR_LITERAL 
		FUN_DECLAR  FUN_DEFINE  INT_ARRAY  CHAR_ARRAY  INT_POINT  CHAR_POINT  
		VOID_POINT   INT_POINT_ARRAY  CHAR_POINT_ARRAY



%start 	program

%right 	'='
%left  	'+'     '-'	
%left  	'*'     '/'	  '%'
%nonassoc	LOW_ELSE    /*for if ..else conplict*/
%nonassoc	ELSE 

 

%union{       
	char * _ident;
       char _op; 
       int _value;
	paramtp * _param;  //函数参数类型
       symbol *_sym; 
       expr _expr;
};


%token <_ident> NUM
%token <_ident> ID
%type <_op> addop
%type <_op> mulop
%type <_op> unaryop
%type <_value> type_spec
%type <_value> callconvent
%type <_sym> var_declar
%type <_sym> fun_declar
%type <_sym> fun_tag       /* 注意其类型 */
%token <_sym> STRING_LITERAL
%token <_sym> CHAR_LITERAL
%type <_param> args      
%type <_param> arg_list
%type <_param> params
%type <_param> param_list
%type <_param> param
%type <_sym> var    
%type <_expr> expr
%type <_expr> factor
%type <_expr> unary_expr 
%type <_expr> term
%type <_expr> add_expr
%type <_expr> simple_expr
%type <_expr> relop  
%type <_expr> local_declars
%type <_expr> comp_stmt
%type <_expr> if_stmt
%type <_expr> while_stmt
%type <_expr> stmt_list
%type <_expr> stmt
%type <_expr> expr_stmt 
%type <_expr> return_stmt
%type <_expr> call

%%




program  :    M   declar_list
	{  fprintf(yyout, "	.data\n");
       { 
	int i;
       struct sym_entry *p;

        /* 生成常量数组  参阅汇编 label 的用法? */
	 if(n_const_strings != 0) fprintf(yyout, "s@	label	byte\n");
        for (i = 0; i< n_const_strings; i++) {
		//printf("i = %d   %s\n",i,const_strings[i].value);
		if(const_strings[i].is_n) fprintf(yyout, "	db	\"%s\",10,0\n",const_strings[i].value); 
 	   	else fprintf(yyout, "	db	\"%s\",0\n",const_strings[i].value); /* \n可能需要变成 10 */
        }
       /* 生成全局变量 */
        for (i = 0; i< HASHSIZE; i++) {
			p = global_table->buckets[i]; /* hash buckets */
			while (p) {
				if (p->sym.type == INT) fprintf(yyout, "_%s	DD	?\n", p->sym.name); else
				if (p->sym.type == CHAR) fprintf(yyout, "_%s	DB	?\n", p->sym.name);
				p = p->next;
			}
	    }

	   is_first = 0;  //恢复
	   fprintf(yyout, "\n	public	_main\n");	
	   fprintf(yyout, "	end\n");
     }}
      ;
M : {   
	fprintf(yyout, "	.386p\n");
	fprintf(yyout, "	model flat\n\n");
	   
	global_table = mktable(NULL,0); 
	table_stack[table_len] = global_table; 
	table_len++;
	offset_stack[offset_len] = 0;
	offset_len++;
	}
     ;



declar_list  :    declar_list declar 
	{  trace("declar_list => declar_list declar\n");  }
      |   declar
      ;
declar  :    var_declar 
      |   fun_declar
      ;
var_declar  :    type_spec   ID   ';' 
	{
	struct table *tp = table_stack[table_len-1];
	symbol *p;
	int width;

	if((lookup($2,tp))!=0){      //had exist in this block
		fprintf(errfile,"line %d : %s define repeatedly\n",nline,$2); 
	       is_error++; 
		return 0;
	}
	else{   
		p = insert($2,tp);
          	width = 0;    //类型长度
	   	p->type = $1;
	   	p->isargv = 0;
	   	p->offset = offset_stack[offset_len-1];
          	if ($1 == INT) width = 4; 
	   	else if ($1 == CHAR) width = 1;
          	offset_stack[offset_len-1] += width;
       }
	}
      |   type_spec   ID  '['  NUM  ']'     ';'
	{  
	struct table *tp = table_stack[table_len-1];
	symbol *p;
	int width;

	trace("var_declar => type_spec ID [ NUM ] ;\n");  
	if((lookup($2,tp))!=0){      //had exist in this block
		fprintf(errfile,"line %d : %s define repeatedly\n",nline,$2); 
		is_error++; 
		return 0;
       } 
	else{
		p = insert($2,tp);
          	width = 0;    //类型长度
	   	p->isargv = 0;
	   	p->offset = offset_stack[offset_len-1];
	   	if($1 == INT){
		   	p->type = INT_ARRAY;
		   	width = 4*atoi($4);
	   	}
          	else if($1 == CHAR){
		   	p->type = CHAR_ARRAY;
		   	width = atoi($4);
	   	}
	   	offset_stack[offset_len-1] += width;
	}
	}
      |   type_spec   '*'  ID   ';' 
	{  
	struct table * tp = table_stack[table_len-1];
	symbol *p;
	int width;

	trace(" var_declar =>  type_spec * ID ;\n");  
	if((p = lookup($3,tp))!=0){      //had exist in this block
		fprintf(errfile,"line %d : %s define repeatedly\n",nline,$3); 
		is_error++; 
		return 0;
	}
	else{
		p = insert($3,tp);
          	width = 0;    //类型长度
	   	p->isargv = 0;
	   	p->offset = offset_stack[offset_len-1];
	   	if($1 == INT){
		   	p->type = INT_POINT;
		   	width = 4;
	   	}
          	else if($1 == CHAR){
		   	p->type = CHAR_POINT;
		   	width = 4;
	   	}
	   	else if($1 == VOID){
		   	p->type = VOID_POINT;
		   	width = 4;
          	}
         	offset_stack[offset_len-1] += width;
	}
	}
      |   type_spec   '*'  ID  '['  NUM  ']'     ';'
	{  
	struct table *tp = table_stack[table_len-1];
	symbol *p;
	int width;

	trace("var_declar =>  type_spec * ID [ NUM ] ;\n");  
	if((lookup($3,tp))!=0){      //had exist in this block
		fprintf(errfile,"line %d : %s define repeatedly\n",nline,$3); 
		is_error++; 
		return 0 ;
       }
	else{
	    	p = insert($3,tp);
          	width = 0;    //类型长度
	   	p->isargv = 0;
	   	p->offset = offset_stack[offset_len-1];
	   	if($1 == INT){
			p->type = INT_POINT_ARRAY;
		   	width = 4*atoi($5);
	   	}
          	else if($1 == CHAR){
		   	p->type = CHAR_POINT_ARRAY;
		   	width = 4*atoi($5);
	   	}
          	offset_stack[offset_len-1] += width;
	}
	}
      ;
type_spec  :    INT
	{  $$ = INT;   }
      |   VOID 
	{  $$ = VOID;  }
      |   CHAR
	{  $$ = CHAR;  }
      | error 
	{
	fprintf(errfile,"type name expected\n"); 
	is_error++; 
	exit(0);
	} 
      ;

fun_declar  :    type_spec  fun_tag   '(' LL params   ')'  comp_stmt
	{  
	paramtp *i,*j;    //用于检查参数是否一致 
	int t;

	t=is_C($2->name);
	if(t==1)	fprintf(yyout, "_%s	proc	near\n", $2->name);  
	else	fprintf(yyout, "%s	proc	near\n", $2->name);  
	fprintf(yyout, "	push      ebp\n");
	fprintf(yyout, "	mov       ebp,esp\n");
       $2->offset = offset_stack[offset_len-1]; 
	fprintf(yyout, "	sub	  esp, %d\n", $2->offset);
	fprintf(yyout, "%s\n", $7.code);    // 所有语句的代码
	//fprintf(yyout, "	.....\n");
	fprintf(yyout,"	mov	esp,ebp\n");
	fprintf(yyout,"	pop	ebp\n");
	fprintf(yyout, "	ret\n");
	if(t==1)	fprintf(yyout, "_%s	endp\n\n", $2->name);  
	else	fprintf(yyout, "%s	endp\n\n", $2->name);  

	/* 函数返回类型检查 */
	if(is_funret && $1 == VOID){ 
		fprintf(errfile,"line %d: function ret type is unreasonable\n",nline);
		is_error++;
		return 0;	
	}
	else if (!is_funret && $1 != VOID){
		fprintf(errfile,"line %d: function ret type is unreasonable\n",nline);
		is_error++;	
		return 0;
	}
	else{
		if($7.is_const){
			$2->is_fun_ret=1;
			$2->ret_const=1;
			$2->retvalue = $7.value;
		}
		else{
			$2->is_fun_ret=1;
			$2->ret_const=0;
		}
	}	

	/* 函数参数检查 */
	if($2 != NULL){
		if($2->type == FUN_DECLAR){  //函数声明
		   //检验类型，参数及其类型是否一致
                      for(i = $2->paramer,j = $5;i!=NULL &&j!=NULL;i=i->next,j=j->next){
				if(i->type!=j->type){
					//fprintf(yyout,"in line %d : the type of function argvments is unexpected!\n",nline);
					break;
				}
			 }
			 if(i!=NULL || j!=NULL){
				fprintf(errfile,"line %d : the type of function argvments is unexpected!\n",nline);
				is_error++; 
				$2->paramer = $5;  
			 }
		        if($2->ret != $1){  //检验返回值类型
				fprintf(errfile,"line %d : the return type of function argvments is unexpected!",nline);
				is_error++; 
				$2->ret = $1;
			}
	       }
		else{   // 新定义的函数
			$2->type = FUN_DEFINE;  //函数定义类型
		  	$2->paramer = $5;
		 	$2->ret = $1;

		}
	}

	offset_len--;
       table_len--;
       level--;

      }
      |   type_spec  fun_tag   '(' LL   params   ')'      ';'		
	{  
	int t;
	t = is_C($2->name);
	if(t == 1)	fprintf(yyout, "extrn	_%s:near\n\n", $2->name);  
	else	fprintf(yyout, "extrn	%s:near\n\n", $2->name); 

	if($2 != NULL){
		if($2->type == FUN_DECLAR){ 
                 	fprintf(errfile,"line %d :warning function %s had been defined!",nline,$2);
              }
		else{
			$2->type = FUN_DECLAR;
			$2->paramer = $5;
			$2->ret = $1;
		}

	}
	offset_len--;
       table_len--;
       level--;

	}
      ;

LL: ;
	{	
	level++;      /* 在后面调用insert时，可能需要建立符号表(见insert)*/
	insert(NULL, table_stack[table_len-1]);    //防止出现表未建时，进行lookup变量  INPORTANCE ERROR
	}  
	;    
fun_tag  :    callconvent  ID
	{  
	struct table *tp = table_stack[table_len-1];
       symbol *ttp;

	trace("fun_tag => callconvent  ID\n");  
	if((ttp = lookup_all($2,tp))!=0){   //已经在符号表出现(声明)
		if(ttp->type == FUN_DECLAR){  //函数声明
			$$ = ttp;
		}
		else if(ttp->type == FUN_DEFINE){  //先定义
			fprintf(errfile,"line %d : function %s define repeatedly\n",nline,$2);
			is_error++;
			$$ = NULL;
		}
		else{  // 函数名可能和一变量名相同
			fprintf(errfile,"line %d : warning the function argvment(s) is expected\n");
			$$ = NULL;
		}
	}
	else{