/*
編譯原理實驗三實驗代碼
B3.Y
newplan
08-09-16
*/
%{
/*-----------head file---------*/
#include <ctype.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
/*-----------macros------------*/
#define HASHSIZE 128
#define _INT 34
#define _CHAR 35
#define _VOID 36
#define _STRING 37
#define _FUNC_TYPE 38
#define _ERROR 39
extern int yylex();
extern FILE* yyin;
extern FILE* yyout;
int yylineno;
typedef struct {
int a[5];
int n;
int h;
int ret_type;
}param;
/*¶¨Òå±êʶ·û*/
typedef struct {
char name[10];
int scope;/*ËùÔڵIJã´Î*/
int type;/*±êʶ·ûÀàÐÍ*/
param *p;
}symbol;
/*¶¨ÒåhashÍ°*/
struct sym_entry{
symbol sym;
struct sym_entry *next ;
};
/*¶¨ÒåhashÁ´±í*/
struct table {
int level ;
struct table *previous;
struct sym_entry *buckets[HASHSIZE] ;
};
int table_len = 0;/*ÓжàÉÙ¸ö±í*/
struct table *table_stack[100];/*±íÕ»*/
struct table *global_table ;/*È«¾Ö±íÖ¸Õë*/
param *global_func_p;
int level = 0 ;/*È«¾Ö²ã´ÎÉèÖÃΪ 0 */
int error = 0;
int trace = 0;
/*hash º¯Êý*/
int hash(char *s)
{
char *p ;
unsigned h = 0,g=0;
for(p=s ;*p != '\0' ;p++)
{
h=(h<<4)+(*p) ;
if(g=h & 0xf0000000)
{
h=h^(g>>24);
h=h^g;
}
}
return h%128;
}
/*----------------²éÕÒ·ûºÅ±í------------------*/
symbol *lookupall(char *name,struct table *tp)
{
int h =hash(name);
struct sym_entry *p = NULL;
int tag=0;
do
{
if(tp->level ==level && tag >0 )continue;
for(p = tp->buckets[h];p;p=p->next)
if(!strcmp(name,p->sym.name)) return &p->sym ;
tag = 1 ;
}
while(tp=tp->previous);
return NULL;
}
/*---------------------------------------------*/
symbol *lookup(char *name,struct table *tp)
{
int h= hash(name);
struct sym_entry *p =NULL;
for(p = tp->buckets[h];p;p = p->next)
if(!strcmp(name,p->sym.name)){return &p->sym ;}
return NULL;
}
/*---------------´´½¨Ò»¸ö·ûºÅ±í----------------*/
struct table * mktable(struct table *previous ,int level)
{
struct table *new =(struct table *)malloc(sizeof *new);
new->previous = previous ;
new->level = level ;
int i;
for(i= 0; i<HASHSIZE ;i++)new->buckets[i]=0;
return new;
}
/*---------------²åÈëÒ»¸ö±êʶ·û----------------*/
symbol *insert(char *name,struct table *tpp)
{
int h = hash(name);
struct table *tp = tpp;
struct sym_entry *p =(struct sym_entry *)malloc(sizeof *p);
if(tp->level<level)
{
tp =(struct table *)mktable(tp,level);
table_stack[table_len] = tp ;
table_len ++;
}
strcpy(p->sym.name,name);
p->sym.scope= level;
p->sym.type = 0;
p->next = tp->buckets[h];
tp->buckets[h]=p;
return &p->sym ;
}
%}
%start program
%right '='
%left ADDOP
%left '*' '/'
%left LE LT GT GE EQ NE
%union {char _ident[9]; int value;char _op;};
%token <_ident> ID
%token NUM
%token <_ident> STRING
%token IF
%token ELSE
%token WHILE
%token INT
%token CHAR
%token <_ident> CONST_CHAR
%token VOID
%token RETURN
%token FOR
%token DO
%token <_op> ADDOP
%type <value> type_specifer
%type <value> var
%type <value> factor
%type <value> term
%type <value> additive_expression
%type <value> simple_expression
%type <value> expression
%type <value> arg_list
%token <_op> MULOP
%nonassoc IFX
%nonassoc ELSE
%%
program : M declaration_list {if(1 == trace)printf("program ==> M declaration_list.\n");if(error == 0 ) fprintf(yyout,"no error\n");}
;
M : {
global_table = mktable(NULL,0);
table_stack[table_len] = global_table ;
table_len++;
}
;
declaration_list: declaration_list declaration
{
if(trace == 1) fprintf(yyout,"declaration_list ==> declaration_list declaration.\n");
}
| declaration
{
if(trace == 1) fprintf(yyout,"declaration_list ==> declaration.\n");
}
;
declaration :var_declaration
{
if (trace ==1) fprintf(yyout,"declaration ==> var_declaration.\n");
}
|fun_declaration
{
if (trace ==1) fprintf(yyout,"declaration ==> fun_declaration.\n");
}
;
var_declaration :type_specifer ID ';'
{
if(trace == 1) printf("var_declaration ==>type_specifer ID.\n");
struct table *tp = table_stack[table_len-1];
if(lookup($2,tp) == NULL)
{
symbol *p = insert($2,tp);
p->type = $1 ;
}
else {error = 1 ; fprintf(yyout, "line %d:error:%s:redefinition\n ",yylineno,$2);}
}
|type_specifer ID '[' NUM ']' ';'
;
type_specifer :INT {$$ =_INT ;}
|CHAR {$$ = _CHAR;}
|VOID {$$ =_VOID ;}
;
fun_declaration :type_specifer fun_tag '(' LL params ')' compound_stmt {level--;}
|type_specifer fun_tag '(' LL params ')' ';'{level--;}
;
fun_tag : ID
{
struct table *tp = table_stack[table_len-1];
symbol *tmp ;
tmp = lookupall($1,tp);
if(tmp == NULL)
{tmp =insert($1,tp);
global_func_p = tmp->p = (param *)malloc(sizeof(*tmp->p));
global_func_p->n =0 ;
global_func_p->ret_type = _INT ;
tmp->type =_FUNC_TYPE;
}
else
{error = 1 ; fprintf(yyout,"line %d:error %s redefine of function.\n",yylineno,$1);}
}
;
LL: {level++;
struct table *tp = mktable(table_stack[table_len-1],level);
table_stack[table_len]=tp;
table_len++;
if(1==trace)printf("level = %d \n",level);
}
;
params :param_list
|VOID{global_func_p->n = 0; if(1 == trace)printf("params==>void\n");}
;
param_list :param_list ',' param {if(1 ==trace )printf("param_list ==> param_list , param.\n");}
|param
;
param :type_specifer ID
{
struct table *tp =table_stack[table_len-1];
symbol *p =insert($2,tp);
p->type =$1;
global_func_p->a[global_func_p->n++]= $1 ;
// printf("type[%d]=%d\n",global_func_p->n-1,global_func_p->a[global_func_p->n-1]);
}
;
compound_stmt :'{' local_declarations statement_list '}'
;
local_declarations: local_declarations var_declaration{if(1 ==trace )printf("local_declarations ==>loacal_declarations var_declaration\n");}
|{if(1 == trace )printf("local_declarations ==> .\n");}
;
statement_list :statement_list statement
|{}
;
statement :expression_stmt{if(1 == trace )printf("statement ==> expression_stmt.\n");}
|if_stmt
|compound_stmt
|while_stmt
|return_stmt
;
expression_stmt :expression ';'
|';'
;
if_stmt :IF '(' expression ')' statement %prec IFX {if(1== trace)printf("if_stmt ==> if expression statement .\n");}
|IF '(' expression ')' statement ELSE statement
{if(1==trace )printf("if_Stmt ==> if expression statement else statement.\n");} ;
while_stmt :WHILE '(' expression ')' statement
;
return_stmt :RETURN ';'
|RETURN expression ';'
;
expression :var '=' expression{if($1 != $3){error =1 ;printf("line %d: '=' must be same type.\n",yylineno);}if(1 == trace )printf("expression ==>var = expression.\n");}
|simple_expression {$$ == $1 ;}
;
var :ID {
symbol *p = lookupall($1,table_stack[table_len-1]);
if(NULL==p){$$ = _ERROR ;error =1 ;fprintf(yyout,"line %d undeclared identifier %s\n",yylineno,$1);}
else
$$ =p->type ;
}
;
simple_expression:additive_expression relop additive_expression{if($1==_INT && $3 ==_INT || $1 ==_CHAR && $3 == _CHAR){;}else{ error =1 ;printf("line %d :relop must int int or char char.\n",yylineno);}}
|additive_expression{$$ =$1 ;}
;
relop :LE
|LT
|GT
|GE
|EQ
|NE
;
additive_expression:additive_expression ADDOP term {if($1 == _INT && $3 ==_INT){;}else{error =1 ;printf("line%d :addop must int int .\n",yylineno);}if(1==trace)printf("additive_expression ==>additive_expression ADDOP term.\n");}
|term{$$ = $1 ;}
;
term :term MULOP factor {if($1==_INT && $3 ==_INT ){;}else{error = 1 ;printf("\nline%d :mulop must int int.\n",yylineno);}}
|factor {$$ =$1;}
;
factor :'(' expression ')'
|var {$$ = $1;}
|call{if(global_func_p){$$=global_func_p->ret_type;}}
|NUM {$$ = _INT;}
|STRING {$$ =_STRING;}
|CONST_CHAR {$$ = _CHAR ;}
;
call :ID { symbol *tmp =lookupall($1,table_stack[table_len-1]);if(NULL ==tmp||tmp->type!=_FUNC_TYPE){error =1;printf("line%d :undeclared identifier %s.\n",yylineno,$1);}else {global_func_p = tmp->p;global_func_p->h = 0;}
} '(' args ')' {if(1 == trace )printf("call ==> ID args .\n");}
;
args :arg_list{if(global_func_p->n > global_func_p->h){error=1;printf("line%d :param num error.\n",yylineno);}}
|{if(global_func_p->n != 0){error =1 ;printf("line%d :param error.\n",yylineno);}}
;
arg_list :arg_list ',' expression{if(global_func_p->n<=global_func_p->h){error=1 ;printf("line%d :param num error.\n",yylineno);}else if(global_func_p->a[global_func_p->h]!=$3){error =1 ;printf("line%d :param error %d.\n",yylineno,$3);}else{global_func_p->h++;}}
|expression {$$ =$1 ; if(global_func_p->a[global_func_p->h]!=$1){error =1 ;printf("line%d :param error $1=%d.\n",yylineno,$1);}else{global_func_p->h++;}}
;
%%
int main(int argc,char *argv[])
{
printf("start checking...\n");
yylineno=1;
if(argc==3)
{
yyin=fopen(argv[1],"r");
yyout=fopen(argv[2],"w");
}
else if(argc==2)
{ yyin=fopen(argv[1],"r");
yyout = stdout ;
}
yyparse();
return 0;
}
int yyerror(char *string)
{
printf("error:%s in line %d\n",string,yylineno);
return 0;
}