delim      [  \t]
ws           {delim}+
letter       [A-Za-z]
digit        [0-9]
id           {letter}({letter}|{digit})*
number       {digit}+
addop        [+-]
mulop        [*/]
%%
\r\n         {yylineno++;}
{ws}         {/*d*/}
while        {return WHILE;}
do           {return DO;}
if           {return IF;}
else         {return ELSE;}
for          {return FOR;}
int          {return INT;}
char         {return CHAR;}
void         {return VOID;}
return       {return RETURN;}
\'[a-zA-Z0-9]\'    {strcpy(yylval._ident,yytext);return CONST_CHAR;}
\"[a-zA-Z]+\" {strcpy(yylval._ident,yytext);return STRING;}
{id}         {strcpy(yylval._ident,yytext);return ID;}
{number}     {strcpy(yylval._ident,yytext);return NUM;}
"["          {return '[';}
"]"          {return ']';}
"<"          {return LT;}
"="          {return '=';}
">"          {return GT;}
"<="         {return LE;}
">="         {return GE;}
"!="         {return NE;}
"=="         {return EQ;}
{addop}      {yylval._op=yytext[0]; return ADDOP;}
{mulop}      {yylval._op=yytext[0]; return MULOP;}
";"          {return ';';}
"{"          {return '{';}
"}"          {return '}';}
"("          {return '(';}
")"          {return ')';}
","          {return ',';}
%%
int yywrap(){
   return 1;
}

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;
}