/*   
   This is a grammar for parsing ANSI C.  Its not in a finished
   state, but its pretty close.   This is all covered under the 
   GNU Public lic. -- that means its free software, period.

   mtr (mtr@ai.mit.edu)
*/


/*  Tokens for C.  */

%token IDENTIFIER CONSTANT STRING_LITERAL SIZEOF
%token PTR_OP INC_OP DEC_OP LEFT_OP RIGHT_OP LE_OP GE_OP EQ_OP NE_OP
%token AND_OP OR_OP MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN ADD_ASSIGN
%token SUB_ASSIGN LEFT_ASSIGN RIGHT_ASSIGN AND_ASSIGN
%token XOR_ASSIGN OR_ASSIGN TYPE_NAME

%token TYPEDEF EXTERN STATIC AUTO REGISTER
%token CHAR SHORT INT LONG SIGNED UNSIGNED FLOAT DOUBLE CONST VOLATILE VOID
%token STRUCT UNION ENUM ELIPSIS

/*  Reserved words.  */
%token CASE DEFAULT IF ELSE SWITCH WHILE DO FOR GOTO CONTINUE BREAK RETURN

%start translation_unit
%%

primary_expr
	: identifier
	| CONSTANT
	| STRING_LITERAL
	| '(' expr ')'
	;

postfix_expr
	: primary_expr
	| postfix_expr '[' expr ']'
	| postfix_expr '(' ')'
	| postfix_expr '(' argument_expr_list ')'
	| postfix_expr '.' identifier
	| postfix_expr PTR_OP identifier
	| postfix_expr INC_OP
	| postfix_expr DEC_OP
	;

argument_expr_list
	: assignment_expr
	| argument_expr_list ',' assignment_expr
	;

unary_expr
	: postfix_expr
	| INC_OP unary_expr
	| DEC_OP unary_expr
	| unary_operator cast_expr
	| SIZEOF unary_expr
	| SIZEOF '(' type_name ')'
	;

unary_operator
	: '&' | '*' | '+' | '-' | '~' | '!'
	;

cast_expr
	: unary_expr
	| '(' type_name ')' cast_expr
	;

multiplicative_expr
	: cast_expr
	| multiplicative_expr '*' cast_expr
	| multiplicative_expr '/' cast_expr
	| multiplicative_expr '%' cast_expr
	;

additive_expr
	: multiplicative_expr
	| additive_expr '+' multiplicative_expr
	| additive_expr '-' multiplicative_expr
	;

shift_expr
	: additive_expr
	| shift_expr LEFT_OP additive_expr
	| shift_expr RIGHT_OP additive_expr
	;

relational_expr
	: shift_expr
	| relational_expr '<' shift_expr
	| relational_expr '>' shift_expr
	| relational_expr LE_OP shift_expr
	| relational_expr GE_OP shift_expr
	;

equality_expr
	: relational_expr
	| equality_expr EQ_OP relational_expr
	| equality_expr NE_OP relational_expr
	;

and_expr
	: equality_expr
	| and_expr '&' equality_expr
	;

exclusive_or_expr
	: and_expr
	| exclusive_or_expr '^' and_expr
	;

inclusive_or_expr
	: exclusive_or_expr
	| inclusive_or_expr '|' exclusive_or_expr
	;

logical_and_expr
	: inclusive_or_expr
	| logical_and_expr AND_OP inclusive_or_expr
	;

logical_or_expr
	: logical_and_expr
	| logical_or_expr OR_OP logical_and_expr
	;

conditional_expr
	: logical_or_expr
	| logical_or_expr '?' expr ':' conditional_expr
	;

assignment_expr
	: conditional_expr
	| unary_expr assignment_operator assignment_expr
	;

assignment_operator
	: '=' | MUL_ASSIGN | DIV_ASSIGN | MOD_ASSIGN | ADD_ASSIGN | SUB_ASSIGN
	| LEFT_ASSIGN | RIGHT_ASSIGN | AND_ASSIGN | XOR_ASSIGN | OR_ASSIGN
	;

expr
	: assignment_expr
	| expr ',' assignment_expr
	;

constant_expr
	: conditional_expr
	;

declaration
	: declaration_specifiers ';'
            {
	      $$ = $1;
	    }
	| declaration_specifiers  /* { reset_is_a_type = is_a_type; } */ init_declarator_list ';'
            {
	      reset_is_a_type = 0;
	      $$ = make_root ("nop", NOP);
	      ((TRnode *) $$)->left = $1;
	      ((TRnode *) $$)->right = $2;

	      /*  This is such a hack.  In the case for a list of 
		  typedefs (eg "typedef int i, j, k; ") or a list of
		  structure tags (eg "struct { int i; } node, *ptr; ").  */

	      if (0 == strcmp (((TRnode *) $$)->left->pc, "struct") ||
		  (0 == strcmp (((TRnode *) $$)->left->pc, "typedef")))
		make_types ($2);

	    }
	;

declaration_specifiers
	: storage_class_specifier
            {
	      $$ = $1;
	    }
	| storage_class_specifier declaration_specifiers 
            {
	      $$ = $1;
	      if ($1 != 0)
		((TRnode *) $1)->right = $2;
	    }
	| type_specifier
            {
	      $$ = $1;
	    }
	| type_specifier declaration_specifiers
            { 
	      $$ = $1;

	      if ($1 != 0)
		((TRnode *) $1)->right = $2;
	    }
	| type_qualifier
            {
	      $$ = $1;
	    }
	| type_qualifier declaration_specifiers
            { 
	      $$ = $1;
	      if ($1 != 0)
		((TRnode *) $1)->right = $2;
	    }
	;

init_declarator_list
 	: init_declarator
	    {
	      $$ = $1;
	    }
	| init_declarator_list ',' init_declarator
	    {
	      $$ = make_root ("nop", NOP);
	      ((TRnode *) $$)->left = $1;
	      ((TRnode *) $$)->right = $3;
	    }
	;

init_declarator
	: declarator
	    {
	      $$ = $1;
	    }
	| declarator '=' initializer
	    {
	      $$ = make_root ("=", OP);

	      ((TRnode *) $$)->left = $1;
	      ((TRnode *) $$)->right = $3;
	    }
	;

storage_class_specifier
	: TYPEDEF 
            {
	      set_type ();
	      $$ = make_root ("typedef", STORAGE_CLASS);
	    }
        | EXTERN 
            {
	      $$ = make_root ("extern", STORAGE_CLASS);
	    }
        | STATIC 
            {
	      $$ = make_root ("static", STORAGE_CLASS);
	    }
        | AUTO 
            {
	      $$ = make_root ("auto", STORAGE_CLASS);
	    }

        | REGISTER
            {
	      $$ = make_root ("register", STORAGE_CLASS);
	    }
	;

type_specifier
	: VOID 
            {
	      $$ = make_root ("void", TYPE);
	    }
        | CHAR 
            {
	      $$ = make_root ("char", TYPE);
	    }
        | SHORT 
            {
	      $$ = make_root ("short", TYPE);
	    }
        | INT 
            {
	      $$ = make_root ("int", TYPE);
	    }
        | LONG
            {
	      $$ = make_root ("long", TYPE);
	    }
	| FLOAT 
            {
	      $$ = make_root ("float", TYPE);
	    }
        | DOUBLE 
            {
	      $$ = make_root ("double", TYPE);
	    }
        | SIGNED 
            {
	      $$ = make_root ("signed", TYPE);
	    }
        | UNSIGNED
            {
	      $$ = make_root ("unsigned", TYPE);
	    }
	| struct_or_union_specifier 
            {
	      $$ = $1;
	    }
	| enum_specifier
            { 
	      $$ = $1;
              set_type (); 
            }
	| TYPE_NAME 
            {
	      $$ = make_root (yytext, TYPE);
	    }
	;

struct_or_union_specifier
	: struct_or_union 
            { 
	      /* unset_type ();  */
	      reset_is_a_type = is_a_type;
	      unset_type ();
	    } 
          '{' { ++in_struct; } struct_declaration_list { --in_struct; } '}' 
            { 
	      if (reset_is_a_type)
		set_type (); 
	    }
	| struct_or_union  identifier 
            { 
	      /* add_type (((TRnode *) $2)->pc); */
	      reset_is_a_type = is_a_type;
	      unset_type (); 
	    } 
          '{' { ++in_struct; } struct_declaration_list { --in_struct; } '}' 
            {
	      if (reset_is_a_type)
		set_type (); 
	    }
	| struct_or_union identifier 
            {
	      /* POSSIBLY... */
	      /* set_type ();  */
	      $$ = $2;
	      if (0 != $$)
		((TRnode *) $$)->left = $1;
	    }
	;

struct_or_union
	: STRUCT
            {
	      $$ = make_root ("struct", LABEL);
	    }
        | UNION
            {
	      $$ = make_root ("union", LABEL);
	    }
	;

struct_declaration_list
	: struct_declaration
	| struct_declaration_list struct_declaration
	;

struct_declaration
	: specifier_qualifier_list struct_declarator_list ';'
	;

specifier_qualifier_list
	: type_specifier
	| type_specifier specifier_qualifier_list
	| type_qualifier
	| type_qualifier specifier_qualifier_list
	;

struct_declarator_list
	: struct_declarator
	| struct_declarator_list ',' struct_declarator
	;

struct_declarator
	: declarator
	| ':' constant_expr
	| declarator ':' constant_expr
	;

enum_specifier
	: ENUM '{' enumerator_list '}'
        | ENUM '{' enumerator_list ',' '}'
	| ENUM identifier '{' enumerator_list '}'
        | ENUM identifier '{' enumerator_list ',' '}'
	| ENUM identifier
	;

enumerator_list
	: enumerator
/*        | enumerator ',' */
	| enumerator_list ',' enumerator
	;

enumerator
	: identifier
	| identifier '=' constant_expr
	;

type_qualifier
	: CONST
            {
	      $$ = make_root ("const", LABEL);
	    }
        | VOLATILE
            {
	      $$ = make_root ("volatile", LABEL);
	    }
	;

declarator
        : direct_declarator
            { 
	      $$ = $1; 
	    }
        | pointer direct_declarator
            {
	      $$ = make_root ("nop", NOP);
	      ((TRnode *) $$)->left = $1;
	      ((TRnode *) $$)->right = $2; 
	    }
	;

direct_declarator
	: identifier
              {  
		$$ = make_root (yytext, IDENT);
		add_type_maybe (yytext); 
	      }
	| '(' declarator ')'
	| direct_declarator '[' ']'
	| direct_declarator '[' constant_expr ']'
	| direct_declarator '(' parameter_type_list ')'
            {
	      $$ = $1;
	      if ($$ != 0)
		((TRnode *) $$)->right = $3;
	    }
	| direct_declarator '(' ')'
            {
	      $$ = $1;
	    }
	| direct_declarator '(' identifier_list ')'
            {
	      $$ = $1;
	      if ($$ != 0)
		((TRnode *) $$)->right = $3;
	    }
	;

pointer
	: '*'
            {
	      $$ = make_root ("*", PTR);
	    }
/*  FIX */
	| '*' specifier_qualifier_list
	| '*' pointer
            {
	      $$ = make_root ("*", PTR);
	      ((TRnode *) $$)->left = $2;
	    }
/*  FIX  */
	| '*' specifier_qualifier_list pointer
	;

parameter_type_list
	: parameter_list
            {
	      $$ = $1;
	    }
	| parameter_list ',' ELIPSIS
	;

parameter_list
	: parameter_declaration
            {
	      $$ = $1;
	    }
	| parameter_list ',' parameter_declaration
            {
	      $$ = make_root ("nop", NOP);
	      ((TRnode *) $$)->left = $1;
	      ((TRnode *) $$)->right = $3;
	    }
	;

parameter_declaration
	: declaration_specifiers declarator
            {
	      $$ = make_root ("nop", NOP);
	      ((TRnode *) $$)->left = $1;
	      ((TRnode *) $$)->right = $2;
	    }
	| declaration_specifiers
            {
	      $$ = $1;
	    }
	| declaration_specifiers abstract_declarator
            {
	      $$ = make_root ("nop", NOP);
	      ((TRnode *) $$)->left = $1;
	      ((TRnode *) $$)->right = $2;
	    }
	      
	;

identifier_list
        : identifier
            {
	      $$ = $1;
	    }

	| identifier_list ',' identifier
            {
	      $$ = make_root ("nop", NOP);
	      ((TRnode *) $$)->left = $1;
	      ((TRnode *) $$)->right = $3;
	    }
	;

type_name
	: specifier_qualifier_list
	| specifier_qualifier_list abstract_declarator
	;

abstract_declarator
	: pointer
            {
	      $$ = $1;
	    }
	| direct_abstract_declarator
            {
	      $$ = $1;
	    }
	| pointer direct_abstract_declarator
            {
	      $$ = make_root ("nop", NOP);
	      ((TRnode *) $$)->left = $1;
	      ((TRnode *) $$)->right = $2;
	    }
	;

/* STOPED HERE */
direct_abstract_declarator
	: '(' abstract_declarator ')'
	| '[' ']'
	| '[' constant_expr ']'
	| direct_abstract_declarator '[' ']'
	| direct_abstract_declarator '[' constant_expr ']'
	| '(' ')'
	| '(' parameter_type_list ')'
	| direct_abstract_declarator '(' ')'
	| direct_abstract_declarator '(' parameter_type_list ')'
	;

initializer
	: assignment_expr
	| '{' initializer_list '}'
	| '{' initializer_list ',' '}'
	;

initializer_list
	: initializer
	| initializer_list ',' initializer
	;

statement
	: labeled_statement
	| compound_statement
	| expression_statement
	| selection_statement
	| iteration_statement
	| jump_statement
/*        | ';' */
	;

labeled_statement
	: identifier ':' statement
	| CASE constant_expr ':' statement
	| DEFAULT ':' statement
	;

compound_statement
	: '{' '}'
	| '{' statement_list '}'
	| '{' declaration_list '}'
	| '{' declaration_list statement_list '}'
	;

declaration_list
	: declaration
            { 
	      $$ = $1; 
	    }
	| declaration_list declaration
            { 

	      $$ = make_root ("nop", NOP);
	      ((TRnode *) $$)->left = $1;
	      ((TRnode *) $$)->right = $2;
	    }
	;

statement_list
	: statement
	| statement_list statement
	;

expression_statement
	: ';'
	| expr ';'
	;

selection_statement
	: IF '(' expr ')' statement
	| IF '(' expr ')' statement ELSE statement
	| SWITCH '(' expr ')' statement
	;

iteration_statement
	: WHILE '(' expr ')' statement
	| DO statement WHILE '(' expr ')' ';'
	| FOR '(' ';' ';' ')' statement
	| FOR '(' ';' ';' expr ')' statement
	| FOR '(' ';' expr ';' ')' statement
	| FOR '(' ';' expr ';' expr ')' statement
	| FOR '(' expr ';' ';' ')' statement
	| FOR '(' expr ';' ';' expr ')' statement
	| FOR '(' expr ';' expr ';' ')' statement
	| FOR '(' expr ';' expr ';' expr ')' statement
	;

jump_statement
	: GOTO identifier ';'
	| CONTINUE ';'
	| BREAK ';'
	| RETURN ';'
	| RETURN expr ';'
	;

translation_unit
	: external_declaration
{ is_a_type = in_struct = 0; }
	| translation_unit external_declaration
{ is_a_type = in_struct = 0; }
	;

external_declaration
	: function_definition
            {
	      comment_counter = 0;
	    }
	| declaration 
            { 
	      comment_counter = 0;
	    }
	;

function_definition
	: declarator 
            { 
	      LIadd (0, $1, 0);;
	    }
          compound_statement
	| declarator declaration_list 
            { 
	      LIadd (0, $1, $2);
	    }
          compound_statement
	| declaration_specifiers declarator 
            { 
	      LIadd ($1, $2, 0);
	    }
          compound_statement
	| declaration_specifiers declarator declaration_list 
            {
	      LIadd ($1, $2, $3);
	    }
          compound_statement
	;

identifier
	: IDENTIFIER
            {
	      $$ = make_root (yytext, IDENT);
	    }
	;
%%
#include <stdio.h> 
#include "tr.h"

int xxxx;
int is_a_type = 0;
int reset_is_a_type = 0;
int number_user_defined_types;
int type_list_size;
char **user_defined_types;
int in_struct = 0;
extern char yytext[];
extern int comment_counter;
int print_level;
int stop_level;

dump_types ()
{
  int i;

printf ("TYPES\n");

  for (i = 0; i < number_user_defined_types; i++)
    printf ("%s\n", user_defined_types[i]);
  printf ("\n\n");
}

char *
make_string (pc)
     char *pc;
{
  char *new_pc;

  new_pc = (char *) malloc (strlen (pc) + 1);
  if (0 == new_pc)
    {
      fprintf (stderr, "Memory error in make_string\n");
      exit (2);
    }
  strcpy (new_pc, pc);
  return new_pc;
}


set_type ()
{
  is_a_type = 1;
  reset_is_a_type = 0;
}

unset_type ()
{
  is_a_type = 0;
}

add_type (type)
  char *type;
{
  is_a_type = 1;
  add_type_maybe (type);
}

add_type_maybe (type)
  char *type;
{
  static int init = 0;
  char *pc;

  if (!is_a_type || in_struct)
    return;

  if (!init)
    {
      init = 1;
      type_list_size = 1024;
      number_user_defined_types = 0;
      user_defined_types = (char **) malloc (sizeof (char *) * type_list_size);
      if (0 == user_defined_types)
	{
 	  fprintf (stderr, "Memory error\n"); 
	  exit (2);
	}
    }
  if (type_list_size == number_user_defined_types)
    {
      type_list_size *= 2;
      user_defined_types = (char **) realloc (user_defined_types, type_list_size);
      if (0 == user_defined_types)
	{
	  fprintf (stderr, "Memory error\n");
	  exit (2);
	}
    }
/* printf ("\nADD TYPE <%s>\n", type);*/
  user_defined_types[number_user_defined_types++] = make_string (type);
  reset_is_a_type = is_a_type = 0;

}

int
output_tree (node, mode)
     TRnode *node;
     int mode;
{
  if (0 == node )
    return;

  /*  Inorder: Left-Root-Right. */
  if (0 != node->left)
    output_tree (node->left, mode);

/*  if (NOP != node->type)  */
    {
  char *lc;
  switch (node->type) {
  case NOP:  lc = "NOP"; break;
  case LABEL:lc = "LABEL"; break;
  case IDENT:lc = "IDENT"; break;
  case PTR:  lc = "PTR"; break;
  case STORAGE_CLASS: lc = "STORAGE_CLASS"; break;
  case TYPE: lc = "TYPE"; break;
  default: lc = "UNKNOWN"; break;
  }
      printf (" %s (%s)", node->pc, lc);
     /* tladd (node);*/
    }

  if (0 != node->right)
    output_tree (node->right, mode);
}

int
output_param_tree (node)
     TRnode *node;
{
  if (0 != node->left)
    output_param_tree (node->left);

  if (NOP != node->type)
    {
      printf (" %s", node->pc);
      if (node->type == IDENT)
	printf (";\n\t");
      else
	printf ("  ");
    }

  if (0 != node->right)
    output_param_tree (node->right);
}


TRnode *
make_root (pc, type)
     char *pc;
     int type;
{
  TRnode *node;
    
  node = malloc (sizeof (TRnode));
  if (0 == node)
    {
      fprintf (stderr, "Memory problems with syntax tree\n");
      exit (2);
    }
  node->left = 0;
  node->right = 0;
  node->pc = make_string (pc);
  node->type = type;
  return node;
}

make_types (node)
     TRnode *node;
{

  if (0 == node)
    return;

  if (0 != node->left)
    make_types (node->left);
  
  
  if (IDENT == node->type && TYPE_NAME != check_type (node->pc))
    { 
      add_type (node->pc);
    }

  if (0 != node->right)
    make_types (node->right);

}