nsz Git - cparser/blob - parser.c

   1 #include <config.h>
   2
   3 #include <assert.h>
   4 #include <stdarg.h>
   5 #include <stdbool.h>
   6
   7 #include "parser.h"
   8 #include "lexer.h"
   9 #include "token_t.h"
  10 #include "type_t.h"
  11 #include "type_hash.h"
  12 #include "ast_t.h"
  13 #include "adt/bitfiddle.h"
  14 #include "adt/error.h"
  15 #include "adt/array.h"
  16
  17 //#define PRINT_TOKENS
  18 //#define ABORT_ON_ERROR
  19 #define MAX_LOOKAHEAD 2
  20 //#define STRICT_C99
  21
  22 struct environment_entry_t {
  23         symbol_t      *symbol;
  24         declaration_t *old_declaration;
  25         const void    *old_context;
  26 };
  27
  28 static token_t               token;
  29 static token_t               lookahead_buffer[MAX_LOOKAHEAD];
  30 static int                   lookahead_bufpos;
  31 static struct obstack        environment_obstack;
  32 static environment_entry_t **environment_stack = NULL;
  33 static context_t            *global_context    = NULL;
  34 static context_t            *context           = NULL;
  35 static declaration_t        *last_declaration  = NULL;
  36 static struct obstack        temp_obst;
  37
  38 static type_t               *type_int        = NULL;
  39 static type_t               *type_double     = NULL;
  40 static type_t               *type_const_char = NULL;
  41 static type_t               *type_string     = NULL;
  42 static type_t               *type_void       = NULL;
  43 static type_t               *type_size_t     = NULL;
  44
  45 static statement_t *parse_compound_statement(void);
  46 static statement_t *parse_statement(void);
  47
  48 static expression_t *parse_sub_expression(unsigned precedence);
  49 static expression_t *parse_expression(void);
  50 static type_t       *parse_typename(void);
  51
  52 #define STORAGE_CLASSES     \
  53         case T_typedef:         \
  54         case T_extern:          \
  55         case T_static:          \
  56         case T_auto:            \
  57         case T_register:
  58
  59 #define TYPE_QUALIFIERS     \
  60         case T_const:           \
  61         case T_restrict:        \
  62         case T_volatile:        \
  63         case T_inline:
  64
  65 #ifdef PROVIDE_COMPLEX
  66 #define COMPLEX_SPECIFIERS  \
  67         case T__Complex:
  68 #else
  69 #define COMPLEX_SPECIFIERS
  70 #endif
  71
  72 #ifdef PROVIDE_IMAGINARY
  73 #define IMAGINARY_SPECIFIERS \
  74         case T__Imaginary:
  75 #else
  76 #define IMAGINARY_SPECIFIERS
  77 #endif
  78
  79 #define TYPE_SPECIFIERS     \
  80         case T_void:            \
  81         case T_char:            \
  82         case T_short:           \
  83         case T_int:             \
  84         case T_long:            \
  85         case T_float:           \
  86         case T_double:          \
  87         case T_signed:          \
  88         case T_unsigned:        \
  89         case T__Bool:           \
  90         case T_struct:          \
  91         case T_union:           \
  92         case T_enum:            \
  93         case T___typeof__:      \
  94         COMPLEX_SPECIFIERS      \
  95         IMAGINARY_SPECIFIERS
  96
  97 #define DECLARATION_START   \
  98         STORAGE_CLASSES         \
  99         TYPE_QUALIFIERS         \
 100         TYPE_SPECIFIERS
 101
 102 #define TYPENAME_START      \
 103         TYPE_QUALIFIERS         \
 104         TYPE_SPECIFIERS
 105
 106 static inline void *allocate_ast_zero(size_t size)
 107 {
 108         void *res = allocate_ast(size);
 109         memset(res, 0, size);
 110         return res;
 111 }
 112
 113 static inline void *allocate_type_zero(size_t size)
 114 {
 115         void *res = obstack_alloc(type_obst, size);
 116         memset(res, 0, size);
 117         return res;
 118 }
 119
 120 static inline void free_type(void *type)
 121 {
 122         obstack_free(type_obst, type);
 123 }
 124
 125 /**
 126  * returns the top element of the environment stack
 127  */
 128 static inline size_t environment_top(void)
 129 {
 130         return ARR_LEN(environment_stack);
 131 }
 132
 133
 134
 135 static inline void next_token(void)
 136 {
 137         token                              = lookahead_buffer[lookahead_bufpos];
 138         lookahead_buffer[lookahead_bufpos] = lexer_token;
 139         lexer_next_token();
 140
 141         lookahead_bufpos = (lookahead_bufpos+1) % MAX_LOOKAHEAD;
 142
 143 #ifdef PRINT_TOKENS
 144         print_token(stderr, &token);
 145         fprintf(stderr, "\n");
 146 #endif
 147 }
 148
 149 static inline const token_t *look_ahead(int num)
 150 {
 151         assert(num > 0 && num <= MAX_LOOKAHEAD);
 152         int pos = (lookahead_bufpos+num-1) % MAX_LOOKAHEAD;
 153         return & lookahead_buffer[pos];
 154 }
 155
 156 #define eat(token_type)  do { assert(token.type == token_type); next_token(); } while(0)
 157
 158 void error(void)
 159 {
 160 #ifdef ABORT_ON_ERROR
 161         abort();
 162 #endif
 163 }
 164
 165 void parser_print_prefix_pos(const source_position_t source_position)
 166 {
 167     fputs(source_position.input_name, stderr);
 168     fputc(':', stderr);
 169     fprintf(stderr, "%d", source_position.linenr);
 170     fputs(": ", stderr);
 171 }
 172
 173 void parser_print_error_prefix_pos(const source_position_t source_position)
 174 {
 175         parser_print_prefix_pos(source_position);
 176         fputs("error: ", stderr);
 177         error();
 178 }
 179
 180 void parser_print_error_prefix(void)
 181 {
 182         parser_print_prefix_pos(token.source_position);
 183         error();
 184 }
 185
 186 static void parse_error(const char *message)
 187 {
 188         parser_print_error_prefix();
 189         fprintf(stderr, "parse error: %s\n", message);
 190 }
 191
 192 __attribute__((unused))
 193 static void parse_warning(const char *message)
 194 {
 195         parser_print_prefix_pos(token.source_position);
 196         fprintf(stderr, "warning: %s\n", message);
 197 }
 198
 199 static void parse_error_expected(const char *message, ...)
 200 {
 201         va_list args;
 202         int first = 1;
 203
 204         if(message != NULL) {
 205                 parser_print_error_prefix();
 206                 fprintf(stderr, "%s\n", message);
 207         }
 208         parser_print_error_prefix();
 209         fputs("Parse error: got ", stderr);
 210         print_token(stderr, &token);
 211         fputs(", expected ", stderr);
 212
 213         va_start(args, message);
 214         token_type_t token_type = va_arg(args, token_type_t);
 215         while(token_type != 0) {
 216                 if(first == 1) {
 217                         first = 0;
 218                 } else {
 219                         fprintf(stderr, ", ");
 220                 }
 221                 print_token_type(stderr, token_type);
 222                 token_type = va_arg(args, token_type_t);
 223         }
 224         va_end(args);
 225         fprintf(stderr, "\n");
 226 }
 227
 228 static void eat_block(void)
 229 {
 230         if(token.type == '{')
 231                 next_token();
 232
 233         while(token.type != '}') {
 234                 if(token.type == T_EOF)
 235                         return;
 236                 if(token.type == '{') {
 237                         eat_block();
 238                         continue;
 239                 }
 240                 next_token();
 241         }
 242         eat('}');
 243 }
 244
 245 static void eat_statement(void)
 246 {
 247         while(token.type != ';') {
 248                 if(token.type == T_EOF)
 249                         return;
 250                 if(token.type == '}')
 251                         return;
 252                 if(token.type == '{') {
 253                         eat_block();
 254                         continue;
 255                 }
 256                 next_token();
 257         }
 258         eat(';');
 259 }
 260
 261 static void eat_brace(void)
 262 {
 263         if(token.type == '(')
 264                 next_token();
 265
 266         while(token.type != ')') {
 267                 if(token.type == T_EOF)
 268                         return;
 269                 if(token.type == ')' || token.type == ';' || token.type == '}') {
 270                         return;
 271                 }
 272                 if(token.type == '(') {
 273                         eat_brace();
 274                         continue;
 275                 }
 276                 if(token.type == '{') {
 277                         eat_block();
 278                         continue;
 279                 }
 280                 next_token();
 281         }
 282         eat(')');
 283 }
 284
 285 #define expect(expected)                           \
 286     if(UNLIKELY(token.type != (expected))) {       \
 287         parse_error_expected(NULL, (expected), 0); \
 288         eat_statement();                           \
 289         return NULL;                               \
 290     }                                              \
 291     next_token();
 292
 293 #define expect_void(expected)                      \
 294     if(UNLIKELY(token.type != (expected))) {       \
 295         parse_error_expected(NULL, (expected), 0); \
 296         eat_statement();                           \
 297         return;                                    \
 298     }                                              \
 299     next_token();
 300
 301 static void set_context(context_t *new_context)
 302 {
 303         context = new_context;
 304
 305         declaration_t *declaration = new_context->declarations;
 306         if(declaration != NULL) {
 307                 while(true) {
 308                         if(declaration->next == NULL)
 309                                 break;
 310                         declaration = declaration->next;
 311                 }
 312         }
 313
 314         last_declaration = declaration;
 315 }
 316
 317 /**
 318  * called when we find a 2nd declarator for an identifier we already have a
 319  * declarator for
 320  */
 321 static bool is_compatible_declaration (declaration_t *declaration,
 322                                       declaration_t *previous)
 323 {
 324         /* TODO: not correct yet */
 325         return declaration->type == previous->type;
 326 }
 327
 328 /**
 329  * pushs an environment_entry on the environment stack and links the
 330  * corresponding symbol to the new entry
 331  */
 332 static inline declaration_t *environment_push(declaration_t *declaration,
 333                                               const void *context)
 334 {
 335         symbol_t *symbol = declaration->symbol;
 336         assert(declaration != symbol->declaration);
 337         assert(declaration->source_position.input_name != NULL);
 338
 339         if(symbol->context == context) {
 340                 declaration_t *previous_declaration = symbol->declaration;
 341                 if(symbol->declaration != NULL) {
 342                         if(!is_compatible_declaration(declaration, previous_declaration)) {
 343                                 parser_print_error_prefix_pos(declaration->source_position);
 344                                 fprintf(stderr, "definition of symbol '%s' with type ",
 345                                         declaration->symbol->string);
 346                                 error();
 347                                 print_type(declaration->type);
 348                                 fputc('\n', stderr);
 349                                 parser_print_error_prefix_pos(
 350                                                 previous_declaration->source_position);
 351                                 fprintf(stderr, "is incompatible with previous declaration "
 352                                         "of type ");
 353                                 print_type(previous_declaration->type);
 354                                 fputc('\n', stderr);
 355                         }
 356                         return previous_declaration;
 357                 }
 358         }
 359
 360         environment_entry_t *entry
 361                 = obstack_alloc(&environment_obstack, sizeof(entry[0]));
 362         memset(entry, 0, sizeof(entry[0]));
 363
 364         int top = ARR_LEN(environment_stack);
 365         ARR_RESIZE(environment_stack, top + 1);
 366         environment_stack[top] = entry;
 367
 368         entry->old_declaration = symbol->declaration;
 369         entry->old_context     = symbol->context;
 370         entry->symbol          = symbol;
 371         symbol->declaration    = declaration;
 372         symbol->context        = context;
 373
 374         return declaration;
 375 }
 376
 377 /**
 378  * pops symbols from the environment stack until @p new_top is the top element
 379  */
 380 static inline void environment_pop_to(size_t new_top)
 381 {
 382         environment_entry_t *entry = NULL;
 383         size_t top = ARR_LEN(environment_stack);
 384         size_t i;
 385
 386         if(new_top == top)
 387                 return;
 388
 389         assert(new_top < top);
 390         i = top;
 391         do {
 392                 entry = environment_stack[i - 1];
 393
 394                 symbol_t *symbol = entry->symbol;
 395
 396                 symbol->declaration = entry->old_declaration;
 397                 symbol->context     = entry->old_context;
 398
 399                 --i;
 400         } while(i != new_top);
 401         obstack_free(&environment_obstack, entry);
 402
 403         ARR_SHRINKLEN(environment_stack, (int) new_top);
 404 }
 405
 406
 407
 408 static expression_t *parse_constant_expression(void)
 409 {
 410         /* start parsing at precedence 7 (conditional expression) */
 411         return parse_sub_expression(7);
 412 }
 413
 414 static expression_t *parse_assignment_expression(void)
 415 {
 416         /* start parsing at precedence 2 (assignment expression) */
 417         return parse_sub_expression(2);
 418 }
 419
 420 static void parse_compound_type_entries(void);
 421 static void parse_declarator(declaration_t *declaration,
 422                              storage_class_t storage_class, type_t *type,
 423                              int may_be_abstract);
 424 static declaration_t *record_declaration(declaration_t *declaration);
 425
 426 typedef struct declaration_specifiers_t  declaration_specifiers_t;
 427 struct declaration_specifiers_t {
 428         storage_class_t  storage_class;
 429         type_t          *type;
 430 };
 431
 432 static const char *parse_string_literals(void)
 433 {
 434         assert(token.type == T_STRING_LITERAL);
 435         const char *result = token.v.string;
 436
 437         next_token();
 438
 439         while(token.type == T_STRING_LITERAL) {
 440                 result = concat_strings(result, token.v.string);
 441                 next_token();
 442         }
 443
 444         return result;
 445 }
 446
 447 static void parse_attributes(void)
 448 {
 449         while(true) {
 450                 switch(token.type) {
 451                 case T___attribute__:
 452                         next_token();
 453
 454                         expect_void('(');
 455                         int depth = 1;
 456                         while(depth > 0) {
 457                                 switch(token.type) {
 458                                 case T_EOF:
 459                                         parse_error("EOF while parsing attribute");
 460                                         break;
 461                                 case '(':
 462                                         next_token();
 463                                         depth++;
 464                                         break;
 465                                 case ')':
 466                                         next_token();
 467                                         depth--;
 468                                         break;
 469                                 default:
 470                                         next_token();
 471                                 }
 472                         }
 473                         break;
 474                 case T_asm:
 475                         next_token();
 476                         expect_void('(');
 477                         if(token.type != T_STRING_LITERAL) {
 478                                 parse_error_expected("while parsing assembler attribute",
 479                                                      T_STRING_LITERAL);
 480                                 eat_brace();
 481                                 break;
 482                         } else {
 483                                 parse_string_literals();
 484                         }
 485                         expect_void(')');
 486                         break;
 487                 default:
 488                         goto attributes_finished;
 489                 }
 490         }
 491
 492 attributes_finished:
 493         ;
 494 }
 495
 496 static designator_t *parse_designation(void)
 497 {
 498         if(token.type != '[' && token.type != '.')
 499                 return NULL;
 500
 501         designator_t *result = NULL;
 502         designator_t *last   = NULL;
 503
 504         while(1) {
 505                 designator_t *designator;
 506                 switch(token.type) {
 507                 case '[':
 508                         designator = allocate_ast_zero(sizeof(designator[0]));
 509                         next_token();
 510                         designator->array_access = parse_constant_expression();
 511                         expect(']');
 512                         break;
 513                 case '.':
 514                         designator = allocate_ast_zero(sizeof(designator[0]));
 515                         next_token();
 516                         if(token.type != T_IDENTIFIER) {
 517                                 parse_error_expected("problem while parsing designator",
 518                                                      T_IDENTIFIER, 0);
 519                                 return NULL;
 520                         }
 521                         designator->symbol = token.v.symbol;
 522                         next_token();
 523                         break;
 524                 default:
 525                         expect('=');
 526                         return result;
 527                 }
 528
 529                 assert(designator != NULL);
 530                 if(last != NULL) {
 531                         last->next = designator;
 532                 } else {
 533                         result = designator;
 534                 }
 535                 last = designator;
 536         }
 537 }
 538
 539 static initializer_t *parse_initializer_list(void);
 540
 541 static initializer_t *parse_initializer(void)
 542 {
 543         designator_t *designator = parse_designation();
 544
 545         initializer_t *result;
 546         if(token.type == '{') {
 547                 result = parse_initializer_list();
 548         } else {
 549                 result          = allocate_ast_zero(sizeof(result[0]));
 550                 result->type    = INITIALIZER_VALUE;
 551                 result->v.value = parse_assignment_expression();
 552         }
 553         result->designator = designator;
 554
 555         return result;
 556 }
 557
 558 static initializer_t *parse_initializer_list(void)
 559 {
 560         eat('{');
 561
 562         initializer_t *result = allocate_ast_zero(sizeof(result[0]));
 563         result->type = INITIALIZER_LIST;
 564
 565         initializer_t *last = NULL;
 566         while(1) {
 567                 initializer_t *initializer = parse_initializer();
 568                 if(last != NULL) {
 569                         last->next = initializer;
 570                 } else {
 571                         result->v.list = initializer;
 572                 }
 573                 last = initializer;
 574
 575                 if(token.type == '}')
 576                         break;
 577
 578                 if(token.type != ',') {
 579                         parse_error_expected("problem while parsing initializer list",
 580                                              ',', '}', 0);
 581                         eat_block();
 582                         return result;
 583                 }
 584                 eat(',');
 585
 586                 if(token.type == '}')
 587                         break;
 588         }
 589
 590         expect('}');
 591
 592         return result;
 593 }
 594
 595 static compound_type_t *find_compound_type(compound_type_t *types,
 596                                            const symbol_t *symbol)
 597 {
 598         compound_type_t *type = types;
 599         for( ; type != NULL; type = type->next) {
 600                 if(type->symbol == symbol)
 601                         return type;
 602         }
 603
 604         return NULL;
 605 }
 606
 607 static type_t *parse_compound_type_specifier(bool is_struct)
 608 {
 609         if(is_struct) {
 610                 eat(T_struct);
 611         } else {
 612                 eat(T_union);
 613         }
 614
 615         symbol_t        *symbol        = NULL;
 616         compound_type_t *compound_type = NULL;
 617
 618         if(token.type == T_IDENTIFIER) {
 619                 symbol = token.v.symbol;
 620                 next_token();
 621
 622                 if(context != NULL) {
 623                         if(is_struct) {
 624                                 compound_type = find_compound_type(context->structs, symbol);
 625                         } else {
 626                                 compound_type = find_compound_type(context->unions, symbol);
 627                         }
 628                 }
 629         } else if(token.type != '{') {
 630                 if(is_struct) {
 631                         parse_error_expected("problem while parsing struct type specifier",
 632                                              T_IDENTIFIER, '{', 0);
 633                 } else {
 634                         parse_error_expected("problem while parsing union type specifier",
 635                                              T_IDENTIFIER, '{', 0);
 636                 }
 637
 638                 return NULL;
 639         }
 640
 641         if(compound_type == NULL) {
 642                 compound_type = allocate_type_zero(sizeof(compound_type[0]));
 643
 644                 if(is_struct) {
 645                         compound_type->type.type = TYPE_COMPOUND_STRUCT;
 646                 } else {
 647                         compound_type->type.type = TYPE_COMPOUND_UNION;
 648                 }
 649                 compound_type->source_position = token.source_position;
 650                 compound_type->symbol          = symbol;
 651         }
 652
 653         if(token.type == '{') {
 654                 if(compound_type->defined) {
 655                         parser_print_error_prefix();
 656                         fprintf(stderr, "multiple definition of %s %s\n",
 657                                         is_struct ? "struct" : "union", symbol->string);
 658                         compound_type->context.declarations = NULL;
 659                 }
 660                 compound_type->defined = 1;
 661
 662                 int         top          = environment_top();
 663                 context_t  *last_context = context;
 664                 set_context(&compound_type->context);
 665
 666                 parse_compound_type_entries();
 667                 parse_attributes();
 668
 669                 assert(context == &compound_type->context);
 670                 set_context(last_context);
 671                 environment_pop_to(top);
 672         }
 673
 674         return (type_t*) compound_type;
 675 }
 676
 677 static void parse_enum_entries(void)
 678 {
 679         eat('{');
 680
 681         if(token.type == '}') {
 682                 next_token();
 683                 parse_error("empty enum not allowed");
 684                 return;
 685         }
 686
 687         do {
 688                 declaration_t *entry = allocate_ast_zero(sizeof(entry[0]));
 689
 690                 if(token.type != T_IDENTIFIER) {
 691                         parse_error_expected("problem while parsing enum entry",
 692                                              T_IDENTIFIER, 0);
 693                         eat_block();
 694                         return;
 695                 }
 696                 entry->storage_class   = STORAGE_CLASS_ENUM_ENTRY;
 697                 entry->symbol          = token.v.symbol;
 698                 entry->source_position = token.source_position;
 699                 next_token();
 700
 701                 if(token.type == '=') {
 702                         next_token();
 703                         entry->initializer = parse_initializer();
 704                 }
 705
 706                 record_declaration(entry);
 707
 708                 if(token.type != ',')
 709                         break;
 710                 next_token();
 711         } while(token.type != '}');
 712
 713         expect_void('}');
 714 }
 715
 716 static enum_type_t *find_enum_type(enum_type_t *types, const symbol_t *symbol)
 717 {
 718         enum_type_t *type = types;
 719         for( ; type != NULL; type = type->next) {
 720                 if(type->symbol == symbol)
 721                         return type;
 722         }
 723
 724         return NULL;
 725 }
 726
 727 static type_t *parse_enum_specifier(void)
 728 {
 729         eat(T_enum);
 730
 731         symbol_t    *symbol    = NULL;
 732         enum_type_t *enum_type = NULL;
 733
 734         if(token.type == T_IDENTIFIER) {
 735                 symbol = token.v.symbol;
 736                 next_token();
 737
 738                 if(context != NULL) {
 739                         enum_type = find_enum_type(context->enums, symbol);
 740                 }
 741         } else if(token.type != '{') {
 742                 parse_error_expected("problem while parsing enum type specifier",
 743                                      T_IDENTIFIER, '{', 0);
 744                 return NULL;
 745         }
 746
 747         if(enum_type == NULL) {
 748                 enum_type                  = allocate_type_zero(sizeof(enum_type[0]));
 749                 enum_type->type.type       = TYPE_ENUM;
 750                 enum_type->source_position = token.source_position;
 751                 enum_type->symbol          = symbol;
 752         }
 753
 754         if(token.type == '{') {
 755                 if(enum_type->defined) {
 756                         parser_print_error_prefix();
 757                         fprintf(stderr, "multiple definitions of enum %s\n",
 758                                 symbol->string);
 759                         enum_type->entries_begin = NULL;
 760                         enum_type->entries_end   = NULL;
 761                 }
 762                 enum_type->defined = 1;
 763
 764                 declaration_t *before = last_declaration;
 765
 766                 parse_enum_entries();
 767                 parse_attributes();
 768
 769                 if(before == NULL) {
 770                         enum_type->entries_begin = context->declarations;
 771                 } else {
 772                         enum_type->entries_begin = before->next;
 773                 }
 774                 enum_type->entries_end = last_declaration;
 775         }
 776
 777         return (type_t*) enum_type;
 778 }
 779
 780 static type_t *parse_typeof(void)
 781 {
 782         eat(T___typeof__);
 783
 784         type_t *result;
 785
 786         expect('(');
 787
 788         declaration_t *declaration;
 789         expression_t  *expression;
 790
 791 restart:
 792         switch(token.type) {
 793         case T___extension__:
 794                 /* this can be a prefix to a typename or an expression */
 795                 /* we simply eat it now. */
 796                 do {
 797                         next_token();
 798                 } while(token.type == T___extension__);
 799                 goto restart;
 800
 801         case T_IDENTIFIER:
 802                 declaration = token.v.symbol->declaration;
 803                 if(declaration != NULL
 804                                 && declaration->storage_class == STORAGE_CLASS_TYPEDEF) {
 805                         result = parse_typename();
 806                         break;
 807                 }
 808                 expression = parse_expression();
 809                 result     = expression->datatype;
 810                 break;
 811
 812         TYPENAME_START
 813                 result = parse_typename();
 814                 break;
 815
 816         default:
 817                 expression = parse_expression();
 818                 result     = expression->datatype;
 819                 break;
 820         }
 821
 822         expect(')');
 823
 824         return result;
 825 }
 826
 827 typedef enum {
 828         SPECIFIER_SIGNED    = 1 << 0,
 829         SPECIFIER_UNSIGNED  = 1 << 1,
 830         SPECIFIER_LONG      = 1 << 2,
 831         SPECIFIER_INT       = 1 << 3,
 832         SPECIFIER_DOUBLE    = 1 << 4,
 833         SPECIFIER_CHAR      = 1 << 5,
 834         SPECIFIER_SHORT     = 1 << 6,
 835         SPECIFIER_LONG_LONG = 1 << 7,
 836         SPECIFIER_FLOAT     = 1 << 8,
 837         SPECIFIER_BOOL      = 1 << 9,
 838         SPECIFIER_VOID      = 1 << 10,
 839 #ifdef PROVIDE_COMPLEX
 840         SPECIFIER_COMPLEX   = 1 << 11,
 841 #endif
 842 #ifdef PROVIDE_IMAGINARY
 843         SPECIFIER_IMAGINARY = 1 << 12,
 844 #endif
 845 } specifiers_t;
 846
 847 static type_t *create_builtin_type(symbol_t *symbol)
 848 {
 849         builtin_type_t *type = allocate_type_zero(sizeof(type[0]));
 850         type->type.type      = TYPE_BUILTIN;
 851         type->symbol         = symbol;
 852
 853         type_t *result = typehash_insert((type_t*) type);
 854         if(result != (type_t*) type) {
 855                 free_type(type);
 856         }
 857
 858         return result;
 859 }
 860
 861 static void parse_declaration_specifiers(declaration_specifiers_t *specifiers)
 862 {
 863         declaration_t *declaration;
 864         type_t        *type            = NULL;
 865         unsigned       type_qualifiers = 0;
 866         unsigned       type_specifiers = 0;
 867         int            newtype         = 0;
 868
 869         while(true) {
 870                 switch(token.type) {
 871
 872                 /* storage class */
 873 #define MATCH_STORAGE_CLASS(token, class)                                \
 874                 case token:                                                      \
 875                         if(specifiers->storage_class != STORAGE_CLASS_NONE) {        \
 876                                 parse_error("multiple storage classes in declaration "   \
 877                                             "specifiers");                               \
 878                         }                                                            \
 879                         specifiers->storage_class = class;                           \
 880                         next_token();                                                \
 881                         break;
 882
 883                 MATCH_STORAGE_CLASS(T_typedef,  STORAGE_CLASS_TYPEDEF)
 884                 MATCH_STORAGE_CLASS(T_extern,   STORAGE_CLASS_EXTERN)
 885                 MATCH_STORAGE_CLASS(T_static,   STORAGE_CLASS_STATIC)
 886                 MATCH_STORAGE_CLASS(T_auto,     STORAGE_CLASS_AUTO)
 887                 MATCH_STORAGE_CLASS(T_register, STORAGE_CLASS_REGISTER)
 888
 889                 /* type qualifiers */
 890 #define MATCH_TYPE_QUALIFIER(token, qualifier)                          \
 891                 case token:                                                     \
 892                         type_qualifiers |= qualifier;                               \
 893                         next_token();                                               \
 894                         break;
 895
 896                 MATCH_TYPE_QUALIFIER(T_const,    TYPE_QUALIFIER_CONST);
 897                 MATCH_TYPE_QUALIFIER(T_restrict, TYPE_QUALIFIER_RESTRICT);
 898                 MATCH_TYPE_QUALIFIER(T_volatile, TYPE_QUALIFIER_VOLATILE);
 899                 MATCH_TYPE_QUALIFIER(T_inline,   TYPE_QUALIFIER_INLINE);
 900
 901                 case T___extension__:
 902                         /* TODO */
 903                         next_token();
 904                         break;
 905
 906                 /* type specifiers */
 907 #define MATCH_SPECIFIER(token, specifier, name)                         \
 908                 case token:                                                     \
 909                         next_token();                                               \
 910                         if(type_specifiers & specifier) {                           \
 911                                 parse_error("multiple " name " type specifiers given"); \
 912                         } else {                                                    \
 913                                 type_specifiers |= specifier;                           \
 914                         }                                                           \
 915                         break;
 916
 917                 MATCH_SPECIFIER(T_void,       SPECIFIER_VOID,      "void")
 918                 MATCH_SPECIFIER(T_char,       SPECIFIER_CHAR,      "char")
 919                 MATCH_SPECIFIER(T_short,      SPECIFIER_SHORT,     "short")
 920                 MATCH_SPECIFIER(T_int,        SPECIFIER_INT,       "int")
 921                 MATCH_SPECIFIER(T_float,      SPECIFIER_FLOAT,     "float")
 922                 MATCH_SPECIFIER(T_double,     SPECIFIER_DOUBLE,    "double")
 923                 MATCH_SPECIFIER(T_signed,     SPECIFIER_SIGNED,    "signed")
 924                 MATCH_SPECIFIER(T_unsigned,   SPECIFIER_UNSIGNED,  "unsigned")
 925                 MATCH_SPECIFIER(T__Bool,      SPECIFIER_BOOL,      "_Bool")
 926 #ifdef PROVIDE_COMPLEX
 927                 MATCH_SPECIFIER(T__Complex,   SPECIFIER_COMPLEX,   "_Complex")
 928 #endif
 929 #ifdef PROVIDE_IMAGINARY
 930                 MATCH_SPECIFIER(T__Imaginary, SPECIFIER_IMAGINARY, "_Imaginary")
 931 #endif
 932                 case T_long:
 933                         next_token();
 934                         if(type_specifiers & SPECIFIER_LONG_LONG) {
 935                                 parse_error("multiple type specifiers given");
 936                         } else if(type_specifiers & SPECIFIER_LONG) {
 937                                 type_specifiers |= SPECIFIER_LONG_LONG;
 938                         } else {
 939                                 type_specifiers |= SPECIFIER_LONG;
 940                         }
 941                         break;
 942
 943                 /* TODO: if type != NULL for the following rules issue an error */
 944                 case T_struct:
 945                         type = parse_compound_type_specifier(true);
 946                         break;
 947                 case T_union:
 948                         type = parse_compound_type_specifier(false);
 949                         break;
 950                 case T_enum:
 951                         type = parse_enum_specifier();
 952                         break;
 953                 case T___typeof__:
 954                         type = parse_typeof();
 955                         break;
 956                 case T___builtin_va_list:
 957                         type = create_builtin_type(token.v.symbol);
 958                         next_token();
 959                         break;
 960
 961                 case T___attribute__:
 962                         /* TODO */
 963                         parse_attributes();
 964                         break;
 965
 966                 case T_IDENTIFIER:
 967                         declaration = token.v.symbol->declaration;
 968                         if(declaration == NULL ||
 969                                         declaration->storage_class != STORAGE_CLASS_TYPEDEF) {
 970                                 goto finish_specifiers;
 971                         }
 972
 973                         type = declaration->type;
 974                         assert(type != NULL);
 975                         next_token();
 976                         break;
 977
 978                 /* function specifier */
 979                 default:
 980                         goto finish_specifiers;
 981                 }
 982         }
 983
 984 finish_specifiers:
 985
 986         if(type == NULL) {
 987                 atomic_type_type_t atomic_type;
 988
 989                 /* match valid basic types */
 990                 switch(type_specifiers) {
 991                 case SPECIFIER_VOID:
 992                         atomic_type = ATOMIC_TYPE_VOID;
 993                         break;
 994                 case SPECIFIER_CHAR:
 995                         atomic_type = ATOMIC_TYPE_CHAR;
 996                         break;
 997                 case SPECIFIER_SIGNED | SPECIFIER_CHAR:
 998                         atomic_type = ATOMIC_TYPE_SCHAR;
 999                         break;
1000                 case SPECIFIER_UNSIGNED | SPECIFIER_CHAR:
1001                         atomic_type = ATOMIC_TYPE_UCHAR;
1002                         break;
1003                 case SPECIFIER_SHORT:
1004                 case SPECIFIER_SIGNED | SPECIFIER_SHORT:
1005                 case SPECIFIER_SHORT | SPECIFIER_INT:
1006                 case SPECIFIER_SIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
1007                         atomic_type = ATOMIC_TYPE_SHORT;
1008                         break;
1009                 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT:
1010                 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
1011                         atomic_type = ATOMIC_TYPE_USHORT;
1012                         break;
1013                 case SPECIFIER_INT:
1014                 case SPECIFIER_SIGNED:
1015                 case SPECIFIER_SIGNED | SPECIFIER_INT:
1016                         atomic_type = ATOMIC_TYPE_INT;
1017                         break;
1018                 case SPECIFIER_UNSIGNED:
1019                 case SPECIFIER_UNSIGNED | SPECIFIER_INT:
1020                         atomic_type = ATOMIC_TYPE_UINT;
1021                         break;
1022                 case SPECIFIER_LONG:
1023                 case SPECIFIER_SIGNED | SPECIFIER_LONG:
1024                 case SPECIFIER_LONG | SPECIFIER_INT:
1025                 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_INT:
1026                         atomic_type = ATOMIC_TYPE_LONG;
1027                         break;
1028                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG:
1029                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_INT:
1030                         atomic_type = ATOMIC_TYPE_ULONG;
1031                         break;
1032                 case SPECIFIER_LONG | SPECIFIER_LONG_LONG:
1033                 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG:
1034                 case SPECIFIER_LONG | SPECIFIER_LONG_LONG | SPECIFIER_INT:
1035                 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG
1036                         | SPECIFIER_INT:
1037                         atomic_type = ATOMIC_TYPE_LONGLONG;
1038                         break;
1039                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG:
1040                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG
1041                         | SPECIFIER_INT:
1042                         atomic_type = ATOMIC_TYPE_ULONGLONG;
1043                         break;
1044                 case SPECIFIER_FLOAT:
1045                         atomic_type = ATOMIC_TYPE_FLOAT;
1046                         break;
1047                 case SPECIFIER_DOUBLE:
1048                         atomic_type = ATOMIC_TYPE_DOUBLE;
1049                         break;
1050                 case SPECIFIER_LONG | SPECIFIER_DOUBLE:
1051                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE;
1052                         break;
1053                 case SPECIFIER_BOOL:
1054                         atomic_type = ATOMIC_TYPE_BOOL;
1055                         break;
1056 #ifdef PROVIDE_COMPLEX
1057                 case SPECIFIER_FLOAT | SPECIFIER_COMPLEX:
1058                         atomic_type = ATOMIC_TYPE_FLOAT_COMPLEX;
1059                         break;
1060                 case SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
1061                         atomic_type = ATOMIC_TYPE_DOUBLE_COMPLEX;
1062                         break;
1063                 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
1064                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE_COMPLEX;
1065                         break;
1066 #endif
1067 #ifdef PROVIDE_IMAGINARY
1068                 case SPECIFIER_FLOAT | SPECIFIER_IMAGINARY:
1069                         atomic_type = ATOMIC_TYPE_FLOAT_IMAGINARY;
1070                         break;
1071                 case SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
1072                         atomic_type = ATOMIC_TYPE_DOUBLE_IMAGINARY;
1073                         break;
1074                 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
1075                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY;
1076                         break;
1077 #endif
1078                 default:
1079                         /* invalid specifier combination, give an error message */
1080                         if(type_specifiers == 0) {
1081 #ifndef STRICT_C99
1082                                 parse_warning("no type specifiers in declaration (using int)");
1083                                 atomic_type = ATOMIC_TYPE_INT;
1084                                 break;
1085 #else
1086                                 parse_error("no type specifiers given in declaration");
1087 #endif
1088                         } else if((type_specifiers & SPECIFIER_SIGNED) &&
1089                                   (type_specifiers & SPECIFIER_UNSIGNED)) {
1090                                 parse_error("signed and unsigned specifiers gives");
1091                         } else if(type_specifiers & (SPECIFIER_SIGNED | SPECIFIER_UNSIGNED)) {
1092                                 parse_error("only integer types can be signed or unsigned");
1093                         } else {
1094                                 parse_error("multiple datatypes in declaration");
1095                         }
1096                         atomic_type = ATOMIC_TYPE_INVALID;
1097                 }
1098
1099                 atomic_type_t *atype = allocate_type_zero(sizeof(atype[0]));
1100                 atype->type.type     = TYPE_ATOMIC;
1101                 atype->atype         = atomic_type;
1102                 newtype              = 1;
1103
1104                 type = (type_t*) atype;
1105         } else {
1106                 if(type_specifiers != 0) {
1107                         parse_error("multiple datatypes in declaration");
1108                 }
1109         }
1110
1111         type->qualifiers = type_qualifiers;
1112
1113         type_t *result = typehash_insert(type);
1114         if(newtype && result != (type_t*) type) {
1115                 free_type(type);
1116         }
1117
1118         specifiers->type = result;
1119 }
1120
1121 static type_qualifier_t parse_type_qualifiers(void)
1122 {
1123         type_qualifier_t type_qualifiers = 0;
1124
1125         while(true) {
1126                 switch(token.type) {
1127                 /* type qualifiers */
1128                 MATCH_TYPE_QUALIFIER(T_const,    TYPE_QUALIFIER_CONST);
1129                 MATCH_TYPE_QUALIFIER(T_restrict, TYPE_QUALIFIER_RESTRICT);
1130                 MATCH_TYPE_QUALIFIER(T_volatile, TYPE_QUALIFIER_VOLATILE);
1131                 MATCH_TYPE_QUALIFIER(T_inline,   TYPE_QUALIFIER_INLINE);
1132
1133                 default:
1134                         return type_qualifiers;
1135                 }
1136         }
1137 }
1138
1139 static void parse_identifier_list(void)
1140 {
1141         while(true) {
1142                 if(token.type != T_IDENTIFIER) {
1143                         parse_error_expected("problem while parsing parameter identifier "
1144                                              "list", T_IDENTIFIER, 0);
1145                         return;
1146                 }
1147                 next_token();
1148                 if(token.type != ',')
1149                         break;
1150                 next_token();
1151         }
1152 }
1153
1154 static declaration_t *parse_parameter(void)
1155 {
1156         declaration_specifiers_t specifiers;
1157         memset(&specifiers, 0, sizeof(specifiers));
1158
1159         parse_declaration_specifiers(&specifiers);
1160
1161         declaration_t *declaration = allocate_ast_zero(sizeof(declaration[0]));
1162         parse_declarator(declaration, specifiers.storage_class,
1163                          specifiers.type, 1);
1164
1165         return declaration;
1166 }
1167
1168 static declaration_t *parse_parameters(method_type_t *type)
1169 {
1170         if(token.type == T_IDENTIFIER) {
1171                 symbol_t      *symbol      = token.v.symbol;
1172                 declaration_t *declaration = symbol->declaration;
1173                 if(declaration == NULL
1174                                 || declaration->storage_class != STORAGE_CLASS_TYPEDEF) {
1175                         /* TODO */
1176                         parse_identifier_list();
1177                         return NULL;
1178                 }
1179         }
1180
1181         if(token.type == ')') {
1182                 type->unspecified_parameters = 1;
1183                 return NULL;
1184         }
1185         if(token.type == T_void && look_ahead(1)->type == ')') {
1186                 next_token();
1187                 return NULL;
1188         }
1189
1190         declaration_t      *declarations = NULL;
1191         declaration_t      *declaration;
1192         declaration_t      *last_declaration = NULL;
1193         method_parameter_t *parameter;
1194         method_parameter_t *last_parameter = NULL;
1195
1196         while(true) {
1197                 switch(token.type) {
1198                 case T_DOTDOTDOT:
1199                         next_token();
1200                         type->variadic = 1;
1201                         return declarations;
1202
1203                 case T_IDENTIFIER:
1204                 case T___extension__:
1205                 DECLARATION_START
1206                         declaration = parse_parameter();
1207
1208                         parameter       = allocate_type_zero(sizeof(parameter[0]));
1209                         parameter->type = declaration->type;
1210
1211                         if(last_parameter != NULL) {
1212                                 last_declaration->next = declaration;
1213                                 last_parameter->next   = parameter;
1214                         } else {
1215                                 type->parameters = parameter;
1216                                 declarations     = declaration;
1217                         }
1218                         last_parameter   = parameter;
1219                         last_declaration = declaration;
1220                         break;
1221
1222                 default:
1223                         return declarations;
1224                 }
1225                 if(token.type != ',')
1226                         return declarations;
1227                 next_token();
1228         }
1229 }
1230
1231 typedef enum {
1232         CONSTRUCT_POINTER,
1233         CONSTRUCT_METHOD,
1234         CONSTRUCT_ARRAY
1235 } construct_type_type_t;
1236
1237 typedef struct construct_type_t construct_type_t;
1238 struct construct_type_t {
1239         construct_type_type_t  type;
1240         construct_type_t      *next;
1241 };
1242
1243 typedef struct parsed_pointer_t parsed_pointer_t;
1244 struct parsed_pointer_t {
1245         construct_type_t  construct_type;
1246         type_qualifier_t  type_qualifiers;
1247 };
1248
1249 typedef struct construct_method_type_t construct_method_type_t;
1250 struct construct_method_type_t {
1251         construct_type_t  construct_type;
1252         method_type_t    *method_type;
1253 };
1254
1255 typedef struct parsed_array_t parsed_array_t;
1256 struct parsed_array_t {
1257         construct_type_t  construct_type;
1258         type_qualifier_t  type_qualifiers;
1259         bool              is_static;
1260         bool              is_variable;
1261         expression_t     *size;
1262 };
1263
1264 typedef struct construct_base_type_t construct_base_type_t;
1265 struct construct_base_type_t {
1266         construct_type_t  construct_type;
1267         type_t           *type;
1268 };
1269
1270 static construct_type_t *parse_pointer_declarator(void)
1271 {
1272         eat('*');
1273
1274         parsed_pointer_t *pointer = obstack_alloc(&temp_obst, sizeof(pointer[0]));
1275         memset(pointer, 0, sizeof(pointer[0]));
1276         pointer->type_qualifiers = parse_type_qualifiers();
1277
1278         return (construct_type_t*) pointer;
1279 }
1280
1281 static construct_type_t *parse_array_declarator(void)
1282 {
1283         eat('[');
1284
1285         parsed_array_t *array = obstack_alloc(&temp_obst, sizeof(array[0]));
1286         memset(array, 0, sizeof(array[0]));
1287
1288         if(token.type == T_static) {
1289                 array->is_static = true;
1290                 next_token();
1291         }
1292
1293         type_qualifier_t type_qualifiers = parse_type_qualifiers();
1294         if(type_qualifiers != 0) {
1295                 if(token.type == T_static) {
1296                         array->is_static = true;
1297                         next_token();
1298                 }
1299         }
1300         array->type_qualifiers = type_qualifiers;
1301
1302         if(token.type == '*' && look_ahead(1)->type == ']') {
1303                 array->is_variable = true;
1304                 next_token();
1305         } else if(token.type != ']') {
1306                 array->size = parse_assignment_expression();
1307         }
1308
1309         expect(']');
1310
1311         return (construct_type_t*) array;
1312 }
1313
1314 static construct_type_t *parse_method_declarator(declaration_t *declaration)
1315 {
1316         eat('(');
1317
1318         method_type_t *method_type
1319                 = allocate_type_zero(sizeof(method_type[0]));
1320         method_type->type.type   = TYPE_METHOD;
1321
1322         declaration_t *parameters = parse_parameters(method_type);
1323         if(declaration != NULL) {
1324                 declaration->context.declarations = parameters;
1325         }
1326
1327         construct_method_type_t *construct_method_type =
1328                 obstack_alloc(&temp_obst, sizeof(construct_method_type[0]));
1329         memset(construct_method_type, 0, sizeof(construct_method_type[0]));
1330         construct_method_type->construct_type.type = CONSTRUCT_METHOD;
1331         construct_method_type->method_type         = method_type;
1332
1333         expect(')');
1334
1335         return (construct_type_t*) construct_method_type;
1336 }
1337
1338 static construct_type_t *parse_inner_declarator(declaration_t *declaration,
1339                 int may_be_abstract)
1340 {
1341         construct_type_t *result = NULL;
1342         construct_type_t *last   = NULL;
1343
1344         while(token.type == '*') {
1345                 construct_type_t *type = parse_pointer_declarator();
1346                 if(last != NULL) {
1347                         last->next = type;
1348                 } else {
1349                         result = type;
1350                 }
1351                 last = type;
1352         }
1353
1354         /* TODO: find out if this is correct */
1355         parse_attributes();
1356
1357         construct_type_t *inner_types = NULL;
1358
1359         switch(token.type) {
1360         case T_IDENTIFIER:
1361                 if(declaration == NULL) {
1362                         parse_error("no identifier expected in typename");
1363                 } else {
1364                         declaration->symbol          = token.v.symbol;
1365                         declaration->source_position = token.source_position;
1366                 }
1367                 next_token();
1368                 break;
1369         case '(':
1370                 next_token();
1371                 inner_types = parse_inner_declarator(declaration, may_be_abstract);
1372                 expect(')');
1373                 break;
1374         default:
1375                 if(may_be_abstract)
1376                         break;
1377                 parse_error_expected("problem while parsing declarator", T_IDENTIFIER,
1378                                      '(', 0);
1379         }
1380
1381         while(true) {
1382                 construct_type_t *type;
1383                 switch(token.type) {
1384                 case '(':
1385                         type = parse_method_declarator(declaration);
1386                         break;
1387                 case '[':
1388                         type = parse_array_declarator();
1389                         break;
1390                 default:
1391                         goto declarator_finished;
1392                 }
1393
1394                 if(last != NULL) {
1395                         last->next = type;
1396                 } else {
1397                         result = type;
1398                 }
1399                 last = type;
1400         }
1401
1402 declarator_finished:
1403         parse_attributes();
1404
1405         if(inner_types != NULL) {
1406                 if(last != NULL) {
1407                         last->next = inner_types;
1408                 } else {
1409                         result = inner_types;
1410                 }
1411                 last = inner_types;
1412         }
1413
1414         return result;
1415 }
1416
1417 static type_t *construct_declarator_type(construct_type_t *construct_list,
1418                                          type_t *type)
1419 {
1420         construct_type_t *iter = construct_list;
1421         for( ; iter != NULL; iter = iter->next) {
1422                 parsed_pointer_t        *parsed_pointer;
1423                 parsed_array_t          *parsed_array;
1424                 construct_method_type_t *construct_method_type;
1425                 method_type_t           *method_type;
1426                 pointer_type_t          *pointer_type;
1427                 array_type_t            *array_type;
1428
1429                 switch(iter->type) {
1430                 case CONSTRUCT_METHOD:
1431                         construct_method_type = (construct_method_type_t*) iter;
1432                         method_type           = construct_method_type->method_type;
1433
1434                         method_type->result_type = type;
1435                         type                     = (type_t*) method_type;
1436                         break;
1437
1438                 case CONSTRUCT_POINTER:
1439                         parsed_pointer = (parsed_pointer_t*) iter;
1440                         pointer_type   = allocate_type_zero(sizeof(pointer_type[0]));
1441
1442                         pointer_type->type.type       = TYPE_POINTER;
1443                         pointer_type->points_to       = type;
1444                         pointer_type->type.qualifiers = parsed_pointer->type_qualifiers;
1445                         type                          = (type_t*) pointer_type;
1446                         break;
1447
1448                 case CONSTRUCT_ARRAY:
1449                         parsed_array  = (parsed_array_t*) iter;
1450                         array_type    = allocate_type_zero(sizeof(array_type[0]));
1451
1452                         array_type->type.type       = TYPE_ARRAY;
1453                         array_type->element_type    = type;
1454                         array_type->type.qualifiers = parsed_array->type_qualifiers;
1455                         array_type->is_static       = parsed_array->is_static;
1456                         array_type->is_variable     = parsed_array->is_variable;
1457                         array_type->size            = parsed_array->size;
1458                         type                        = (type_t*) array_type;
1459                         break;
1460                 }
1461
1462                 type_t *hashed_type = typehash_insert((type_t*) type);
1463                 if(hashed_type != type) {
1464                         free_type(type);
1465                         type = hashed_type;
1466                 }
1467         }
1468
1469         return type;
1470 }
1471
1472 static void parse_declarator(declaration_t *declaration,
1473                              storage_class_t storage_class, type_t *type,
1474                              int may_be_abstract)
1475 {
1476         construct_type_t *construct_type
1477                 = parse_inner_declarator(declaration, may_be_abstract);
1478
1479         declaration->type         = construct_declarator_type(construct_type, type);
1480         declaration->storage_class = storage_class;
1481         if(construct_type != NULL) {
1482                 obstack_free(&temp_obst, construct_type);
1483         }
1484 }
1485
1486 static type_t *parse_abstract_declarator(type_t *base_type)
1487 {
1488         construct_type_t *construct_type
1489                 = parse_inner_declarator(NULL, 1);
1490
1491         if(construct_type == NULL)
1492                 return NULL;
1493
1494         type_t *result = construct_declarator_type(construct_type, base_type);
1495         obstack_free(&temp_obst, construct_type);
1496
1497         return result;
1498 }
1499
1500 static declaration_t *record_declaration(declaration_t *declaration)
1501 {
1502         if(context == NULL)
1503                 return declaration;
1504
1505         symbol_t *symbol = declaration->symbol;
1506         if(symbol != NULL) {
1507                 declaration_t *alias = environment_push(declaration, context);
1508                 if(alias != declaration)
1509                         return alias;
1510         }
1511
1512         if(last_declaration != NULL) {
1513                 last_declaration->next = declaration;
1514         } else {
1515                 context->declarations  = declaration;
1516         }
1517         last_declaration = declaration;
1518
1519         return declaration;
1520 }
1521
1522 static void parser_error_multiple_definition(declaration_t *previous,
1523                                              declaration_t *declaration)
1524 {
1525         parser_print_error_prefix_pos(declaration->source_position);
1526         fprintf(stderr, "multiple definition of symbol '%s'\n",
1527                 declaration->symbol->string);
1528         parser_print_error_prefix_pos(previous->source_position);
1529         fprintf(stderr, "this is the location of the previous "
1530                 "definition.\n");
1531         error();
1532 }
1533
1534 static void parse_init_declarators(const declaration_specifiers_t *specifiers)
1535 {
1536         while(true) {
1537                 declaration_t *ndeclaration
1538                         = allocate_ast_zero(sizeof(ndeclaration[0]));
1539
1540                 parse_declarator(ndeclaration, specifiers->storage_class,
1541                                  specifiers->type, 0);
1542                 declaration_t *declaration = record_declaration(ndeclaration);
1543                 if(token.type == '=') {
1544                         next_token();
1545
1546                         /* TODO: check that this is an allowed type (esp. no method type) */
1547
1548                         if(declaration->initializer != NULL) {
1549                                 parser_error_multiple_definition(declaration, ndeclaration);
1550                         }
1551
1552                         ndeclaration->initializer = parse_initializer();
1553                 } else if(token.type == '{') {
1554                         if(declaration->type->type != TYPE_METHOD) {
1555                                 parser_print_error_prefix();
1556                                 fprintf(stderr, "Declarator ");
1557                                 print_type_ext(declaration->type, declaration->symbol, NULL);
1558                                 fprintf(stderr, " is not a method type.\n");
1559                         }
1560
1561                         if(declaration->initializer != NULL) {
1562                                 parser_error_multiple_definition(declaration, ndeclaration);
1563                         }
1564                         if(ndeclaration != declaration) {
1565                                 memcpy(&declaration->context, &ndeclaration->context,
1566                                        sizeof(declaration->context));
1567                         }
1568
1569                         int         top          = environment_top();
1570                         context_t  *last_context = context;
1571                         set_context(&declaration->context);
1572
1573                         /* push function parameters */
1574                         declaration_t *parameter = declaration->context.declarations;
1575                         for( ; parameter != NULL; parameter = parameter->next) {
1576                                 environment_push(parameter, context);
1577                         }
1578
1579                         statement_t *statement = parse_compound_statement();
1580
1581                         assert(context == &declaration->context);
1582                         set_context(last_context);
1583                         environment_pop_to(top);
1584
1585                         declaration->statement = statement;
1586                         return;
1587                 }
1588
1589                 if(token.type != ',')
1590                         break;
1591                 next_token();
1592         }
1593         expect_void(';');
1594 }
1595
1596 static void parse_struct_declarators(const declaration_specifiers_t *specifiers)
1597 {
1598         while(1) {
1599                 if(token.type == ':') {
1600                         next_token();
1601                         parse_constant_expression();
1602                         /* TODO (bitfields) */
1603                 } else {
1604                         declaration_t *declaration
1605                                 = allocate_ast_zero(sizeof(declaration[0]));
1606                         parse_declarator(declaration, specifiers->storage_class,
1607                                          specifiers->type, 1);
1608
1609                         /* TODO: check for doubled fields */
1610                         record_declaration(declaration);
1611
1612                         if(token.type == ':') {
1613                                 next_token();
1614                                 parse_constant_expression();
1615                                 /* TODO (bitfields) */
1616                         }
1617                 }
1618
1619                 if(token.type != ',')
1620                         break;
1621                 next_token();
1622         }
1623         expect_void(';');
1624 }
1625
1626 static void parse_compound_type_entries(void)
1627 {
1628         eat('{');
1629
1630         while(token.type != '}' && token.type != T_EOF) {
1631                 declaration_specifiers_t specifiers;
1632                 memset(&specifiers, 0, sizeof(specifiers));
1633                 /* TODO not correct as this allows storage class stuff... but only
1634                  * specifiers and qualifiers sould be allowed here */
1635                 parse_declaration_specifiers(&specifiers);
1636
1637                 parse_struct_declarators(&specifiers);
1638         }
1639         if(token.type == T_EOF) {
1640                 parse_error("unexpected error while parsing struct");
1641         }
1642         next_token();
1643 }
1644
1645 static void parse_declaration(void)
1646 {
1647         declaration_specifiers_t specifiers;
1648         memset(&specifiers, 0, sizeof(specifiers));
1649         parse_declaration_specifiers(&specifiers);
1650
1651         if(token.type == ';') {
1652                 next_token();
1653                 return;
1654         }
1655         parse_init_declarators(&specifiers);
1656 }
1657
1658 static type_t *parse_typename(void)
1659 {
1660         declaration_specifiers_t specifiers;
1661         memset(&specifiers, 0, sizeof(specifiers));
1662         parse_declaration_specifiers(&specifiers);
1663         if(specifiers.storage_class != STORAGE_CLASS_NONE) {
1664                 /* TODO: improve error message, user does probably not know what a
1665                  * storage class is...
1666                  */
1667                 parse_error("typename may not have a storage class");
1668         }
1669
1670         type_t *result = parse_abstract_declarator(specifiers.type);
1671
1672         return result;
1673 }
1674
1675
1676
1677
1678 typedef expression_t* (*parse_expression_function) (unsigned precedence);
1679 typedef expression_t* (*parse_expression_infix_function) (unsigned precedence,
1680                                                           expression_t *left);
1681
1682 typedef struct expression_parser_function_t expression_parser_function_t;
1683 struct expression_parser_function_t {
1684         unsigned                         precedence;
1685         parse_expression_function        parser;
1686         unsigned                         infix_precedence;
1687         parse_expression_infix_function  infix_parser;
1688 };
1689
1690 expression_parser_function_t expression_parsers[T_LAST_TOKEN];
1691
1692 static expression_t *expected_expression_error(void)
1693 {
1694         parser_print_error_prefix();
1695         fprintf(stderr, "expected expression, got token ");
1696         print_token(stderr, & token);
1697         fprintf(stderr, "\n");
1698
1699         expression_t *expression = allocate_ast_zero(sizeof(expression[0]));
1700         expression->type = EXPR_INVALID;
1701         next_token();
1702
1703         return expression;
1704 }
1705
1706 static expression_t *parse_string_const(void)
1707 {
1708         string_literal_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
1709
1710         cnst->expression.type     = EXPR_STRING_LITERAL;
1711         cnst->expression.datatype = type_string;
1712         cnst->value               = parse_string_literals();
1713
1714         return (expression_t*) cnst;
1715 }
1716
1717 static expression_t *parse_int_const(void)
1718 {
1719         const_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
1720
1721         cnst->expression.type     = EXPR_CONST;
1722         cnst->expression.datatype = type_int;
1723         cnst->v.int_value         = token.v.intvalue;
1724
1725         next_token();
1726
1727         return (expression_t*) cnst;
1728 }
1729
1730 static expression_t *parse_float_const(void)
1731 {
1732         const_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
1733
1734         cnst->expression.type     = EXPR_CONST;
1735         cnst->expression.datatype = type_double;
1736         cnst->v.float_value       = token.v.floatvalue;
1737
1738         next_token();
1739
1740         return (expression_t*) cnst;
1741 }
1742
1743 static declaration_t *create_implicit_function(symbol_t *symbol,
1744                 const source_position_t source_position)
1745 {
1746         method_type_t *method_type = allocate_type_zero(sizeof(method_type));
1747
1748         method_type->type.type              = TYPE_METHOD;
1749         method_type->result_type            = type_int;
1750         method_type->unspecified_parameters = true;
1751
1752         type_t *type = typehash_insert((type_t*) method_type);
1753         if(type != (type_t*) method_type) {
1754                 free_type(method_type);
1755         }
1756
1757         declaration_t *declaration = allocate_ast_zero(sizeof(declaration[0]));
1758
1759         declaration->storage_class   = STORAGE_CLASS_EXTERN;
1760         declaration->type            = type;
1761         declaration->symbol          = symbol;
1762         declaration->source_position = source_position;
1763
1764         /* we have to violate the environment push/pop rules here and assign
1765          * the declaration directly to its symbol and append it to the
1766          * global context */
1767         assert(symbol->declaration == NULL);
1768         symbol->declaration          = declaration;
1769         declaration->next            = global_context->declarations;
1770         global_context->declarations = declaration;
1771
1772         return declaration;
1773 }
1774
1775 static expression_t *parse_reference(void)
1776 {
1777         reference_expression_t *ref = allocate_ast_zero(sizeof(ref[0]));
1778
1779         ref->expression.type = EXPR_REFERENCE;
1780         ref->symbol          = token.v.symbol;
1781
1782         declaration_t     *declaration     = ref->symbol->declaration;
1783         source_position_t  source_position = token.source_position;
1784         next_token();
1785
1786         if(declaration == NULL) {
1787 #ifndef STRICT_C99
1788                 /* an implicitely defined function */
1789                 if(token.type == '(') {
1790                         parser_print_prefix_pos(token.source_position);
1791                         fprintf(stderr, "warning: implicit declaration of function '%s'\n",
1792                                 ref->symbol->string);
1793
1794                         declaration = create_implicit_function(ref->symbol,
1795                                                                source_position);
1796                 } else
1797 #endif
1798                 {
1799                         parser_print_error_prefix();
1800                         fprintf(stderr, "unknown symbol '%s' found.\n", ref->symbol->string);
1801                         return (expression_t*) ref;
1802                 }
1803         }
1804
1805         ref->declaration         = declaration;
1806         ref->expression.datatype = declaration->type;
1807
1808         return (expression_t*) ref;
1809 }
1810
1811 static void check_cast_allowed(expression_t *expression, type_t *dest_type)
1812 {
1813         (void) expression;
1814         (void) dest_type;
1815         /* TODO check if cast is allowed and issue warnings/errors */
1816 }
1817
1818 static expression_t *parse_cast(void)
1819 {
1820         unary_expression_t *cast = allocate_ast_zero(sizeof(cast[0]));
1821
1822         cast->expression.type            = EXPR_UNARY;
1823         cast->type                       = UNEXPR_CAST;
1824         cast->expression.source_position = token.source_position;
1825
1826         type_t *type  = parse_typename();
1827
1828         expect(')');
1829         expression_t *value = parse_sub_expression(20);
1830
1831         check_cast_allowed(value, type);
1832
1833         cast->expression.datatype = type;
1834         cast->value               = value;
1835
1836         return (expression_t*) cast;
1837 }
1838
1839 static expression_t *parse_statement_expression(void)
1840 {
1841         statement_expression_t *expression
1842                 = allocate_ast_zero(sizeof(expression[0]));
1843         expression->expression.type = EXPR_STATEMENT;
1844         expression->statement       = parse_compound_statement();
1845
1846         /* find last statement and use it's type */
1847         const statement_t *last_statement = NULL;
1848         const statement_t *statement      = expression->statement;
1849         for( ; statement != NULL; statement = statement->next) {
1850                 last_statement = statement;
1851         }
1852
1853         if(last_statement->type == STATEMENT_EXPRESSION) {
1854                 const expression_statement_t *expression_statement =
1855                         (const expression_statement_t*) last_statement;
1856                 expression->expression.datatype
1857                         = expression_statement->expression->datatype;
1858         } else {
1859                 expression->expression.datatype = type_void;
1860         }
1861
1862         expect(')');
1863
1864         return (expression_t*) expression;
1865 }
1866
1867 static expression_t *parse_brace_expression(void)
1868 {
1869         eat('(');
1870
1871         declaration_t *declaration;
1872         switch(token.type) {
1873         case '{':
1874                 /* gcc extension: a stement expression */
1875                 return parse_statement_expression();
1876
1877         TYPE_QUALIFIERS
1878         TYPE_SPECIFIERS
1879                 return parse_cast();
1880         case T_IDENTIFIER:
1881                 declaration = token.v.symbol->declaration;
1882                 if(declaration != NULL &&
1883                                 (declaration->storage_class == STORAGE_CLASS_TYPEDEF)) {
1884                         return parse_cast();
1885                 }
1886         }
1887
1888         expression_t *result = parse_expression();
1889         expect(')');
1890
1891         return result;
1892 }
1893
1894 static expression_t *parse_function_keyword(void)
1895 {
1896         eat(T___FUNCTION__);
1897         /* TODO */
1898
1899         string_literal_t *expression = allocate_ast_zero(sizeof(expression[0]));
1900         expression->expression.type     = EXPR_FUNCTION;
1901         expression->expression.datatype = type_string;
1902         expression->value               = "TODO: FUNCTION";
1903
1904         return (expression_t*) expression;
1905 }
1906
1907 static expression_t *parse_pretty_function_keyword(void)
1908 {
1909         eat(T___PRETTY_FUNCTION__);
1910         /* TODO */
1911
1912         string_literal_t *expression = allocate_ast_zero(sizeof(expression[0]));
1913         expression->expression.type     = EXPR_PRETTY_FUNCTION;
1914         expression->expression.datatype = type_string;
1915         expression->value               = "TODO: PRETTY FUNCTION";
1916
1917         return (expression_t*) expression;
1918 }
1919
1920 static designator_t *parse_designator(void)
1921 {
1922         designator_t *result = allocate_ast_zero(sizeof(result[0]));
1923
1924         if(token.type != T_IDENTIFIER) {
1925                 parse_error_expected("problem while parsing member designator",
1926                                      T_IDENTIFIER, 0);
1927                 eat_brace();
1928                 return NULL;
1929         }
1930         result->symbol = token.v.symbol;
1931         next_token();
1932
1933         designator_t *last_designator = result;
1934         while(true) {
1935                 if(token.type == '.') {
1936                         next_token();
1937                         if(token.type != T_IDENTIFIER) {
1938                                 parse_error_expected("problem while parsing member designator",
1939                                         T_IDENTIFIER, 0);
1940                                 eat_brace();
1941                                 return NULL;
1942                         }
1943                         designator_t *designator = allocate_ast_zero(sizeof(result[0]));
1944                         designator->symbol       = token.v.symbol;
1945                         next_token();
1946
1947                         last_designator->next = designator;
1948                         last_designator       = designator;
1949                         continue;
1950                 }
1951                 if(token.type == '[') {
1952                         next_token();
1953                         designator_t *designator = allocate_ast_zero(sizeof(result[0]));
1954                         designator->array_access = parse_expression();
1955                         if(designator->array_access == NULL) {
1956                                 eat_brace();
1957                                 return NULL;
1958                         }
1959                         expect(']');
1960
1961                         last_designator->next = designator;
1962                         last_designator       = designator;
1963                         continue;
1964                 }
1965                 break;
1966         }
1967
1968         return result;
1969 }
1970
1971 static expression_t *parse_offsetof(void)
1972 {
1973         eat(T___builtin_offsetof);
1974
1975         offsetof_expression_t *expression
1976                 = allocate_ast_zero(sizeof(expression[0]));
1977         expression->expression.type     = EXPR_OFFSETOF;
1978         expression->expression.datatype = type_size_t;
1979
1980         expect('(');
1981         expression->type = parse_typename();
1982         expect(',');
1983         expression->designator = parse_designator();
1984         expect(')');
1985
1986         return (expression_t*) expression;
1987 }
1988
1989 static expression_t *parse_va_arg(void)
1990 {
1991         eat(T___builtin_va_arg);
1992
1993         va_arg_expression_t *expression = allocate_ast_zero(sizeof(expression[0]));
1994         expression->expression.type     = EXPR_VA_ARG;
1995
1996         expect('(');
1997         expression->arg = parse_assignment_expression();
1998         expect(',');
1999         expression->expression.datatype = parse_typename();
2000         expect(')');
2001
2002         return (expression_t*) expression;
2003 }
2004
2005 static expression_t *parse_builtin_symbol(void)
2006 {
2007         builtin_symbol_expression_t *expression
2008                 = allocate_ast_zero(sizeof(expression[0]));
2009         expression->expression.type = EXPR_BUILTIN_SYMBOL;
2010
2011         /* TODO: set datatype */
2012
2013         expression->symbol = token.v.symbol;
2014
2015         next_token();
2016
2017         return (expression_t*) expression;
2018 }
2019
2020 static expression_t *parse_primary_expression(void)
2021 {
2022         switch(token.type) {
2023         case T_INTEGER:
2024                 return parse_int_const();
2025         case T_FLOATINGPOINT:
2026                 return parse_float_const();
2027         case T_STRING_LITERAL:
2028                 return parse_string_const();
2029         case T_IDENTIFIER:
2030                 return parse_reference();
2031         case T___FUNCTION__:
2032                 return parse_function_keyword();
2033         case T___PRETTY_FUNCTION__:
2034                 return parse_pretty_function_keyword();
2035         case T___builtin_offsetof:
2036                 return parse_offsetof();
2037         case T___builtin_va_arg:
2038                 return parse_va_arg();
2039         case T___builtin_expect:
2040         case T___builtin_va_start:
2041         case T___builtin_va_end:
2042                 return parse_builtin_symbol();
2043
2044         case '(':
2045                 return parse_brace_expression();
2046         }
2047
2048         parser_print_error_prefix();
2049         fprintf(stderr, "unexpected token ");
2050         print_token(stderr, &token);
2051         fprintf(stderr, "\n");
2052         eat_statement();
2053
2054         expression_t *expression = allocate_ast_zero(sizeof(expression[0]));
2055         expression->type     = EXPR_INVALID;
2056         expression->datatype = type_void;
2057
2058         return expression;
2059 }
2060
2061 static expression_t *parse_array_expression(unsigned precedence,
2062                                             expression_t *array_ref)
2063 {
2064         (void) precedence;
2065
2066         eat('[');
2067
2068         array_access_expression_t *array_access
2069                 = allocate_ast_zero(sizeof(array_access[0]));
2070
2071         array_access->expression.type     = EXPR_ARRAY_ACCESS;
2072         array_access->array_ref           = array_ref;
2073         array_access->index               = parse_expression();
2074
2075         type_t *array_type = array_ref->datatype;
2076         if(array_type != NULL) {
2077                 if(array_type->type == TYPE_POINTER) {
2078                         pointer_type_t *pointer           = (pointer_type_t*) array_type;
2079                         array_access->expression.datatype = pointer->points_to;
2080                 } else {
2081                         parser_print_error_prefix();
2082                         fprintf(stderr, "array access on object with non-pointer type ");
2083                         print_type(array_type);
2084                         fprintf(stderr, "\n");
2085                 }
2086         }
2087
2088         if(token.type != ']') {
2089                 parse_error_expected("Problem while parsing array access", ']', 0);
2090                 return (expression_t*) array_access;
2091         }
2092         next_token();
2093
2094         return (expression_t*) array_access;
2095 }
2096
2097 static bool is_declaration_specifier(const token_t *token,
2098                                      bool only_type_specifiers)
2099 {
2100         declaration_t *declaration;
2101
2102         switch(token->type) {
2103                 TYPE_SPECIFIERS
2104                         return 1;
2105                 case T_IDENTIFIER:
2106                         declaration = token->v.symbol->declaration;
2107                         if(declaration == NULL)
2108                                 return 0;
2109                         if(declaration->storage_class != STORAGE_CLASS_TYPEDEF)
2110                                 return 0;
2111                         return 1;
2112                 STORAGE_CLASSES
2113                 TYPE_QUALIFIERS
2114                         if(only_type_specifiers)
2115                                 return 0;
2116                         return 1;
2117
2118                 default:
2119                         return 0;
2120         }
2121 }
2122
2123 static expression_t *parse_sizeof(unsigned precedence)
2124 {
2125         eat(T_sizeof);
2126
2127         sizeof_expression_t *sizeof_expression
2128                 = allocate_ast_zero(sizeof(sizeof_expression[0]));
2129         sizeof_expression->expression.type     = EXPR_SIZEOF;
2130         sizeof_expression->expression.datatype = type_size_t;
2131
2132         if(token.type == '(' && is_declaration_specifier(look_ahead(1), true)) {
2133                 next_token();
2134                 sizeof_expression->type = parse_typename();
2135                 expect(')');
2136         } else {
2137                 expression_t *expression           = parse_sub_expression(precedence);
2138                 sizeof_expression->type            = expression->datatype;
2139                 sizeof_expression->size_expression = expression;
2140         }
2141
2142         return (expression_t*) sizeof_expression;
2143 }
2144
2145 static expression_t *parse_select_expression(unsigned precedence,
2146                                              expression_t *compound)
2147 {
2148         (void) precedence;
2149
2150         assert(token.type == '.' || token.type == T_MINUSGREATER);
2151         next_token();
2152
2153         select_expression_t *select = allocate_ast_zero(sizeof(select[0]));
2154
2155         select->expression.type = EXPR_SELECT;
2156         select->compound        = compound;
2157
2158         /* TODO: datatype */
2159
2160         if(token.type != T_IDENTIFIER) {
2161                 parse_error_expected("Problem while parsing select", T_IDENTIFIER, 0);
2162                 return (expression_t*) select;
2163         }
2164         select->symbol = token.v.symbol;
2165         next_token();
2166
2167         return (expression_t*) select;
2168 }
2169
2170 static expression_t *parse_call_expression(unsigned precedence,
2171                                            expression_t *expression)
2172 {
2173         (void) precedence;
2174         call_expression_t *call = allocate_ast_zero(sizeof(call[0]));
2175
2176         call->expression.type     = EXPR_CALL;
2177         call->method              = expression;
2178
2179         /* parse arguments */
2180         eat('(');
2181
2182         if(token.type != ')') {
2183                 call_argument_t *last_argument = NULL;
2184
2185                 while(true) {
2186                         call_argument_t *argument = allocate_ast_zero(sizeof(argument[0]));
2187
2188                         argument->expression = parse_assignment_expression();
2189                         if(last_argument == NULL) {
2190                                 call->arguments = argument;
2191                         } else {
2192                                 last_argument->next = argument;
2193                         }
2194                         last_argument = argument;
2195
2196                         if(token.type != ',')
2197                                 break;
2198                         next_token();
2199                 }
2200         }
2201         expect(')');
2202
2203         type_t *type = expression->datatype;
2204         if(type != NULL) {
2205                 /* we can call pointer to function */
2206                 if(type->type == TYPE_POINTER) {
2207                         pointer_type_t *pointer = (pointer_type_t*) type;
2208                         type = pointer->points_to;
2209                 }
2210
2211                 if(type == NULL || type->type != TYPE_METHOD) {
2212                         parser_print_error_prefix();
2213                         fprintf(stderr, "expected a method type for call but found type ");
2214                         print_type(expression->datatype);
2215                         fprintf(stderr, "\n");
2216                 } else {
2217                         method_type_t *method_type = (method_type_t*) type;
2218                         call->expression.datatype  = method_type->result_type;
2219                 }
2220         }
2221
2222         return (expression_t*) call;
2223 }
2224
2225 static void type_error(const char *msg, const source_position_t source_position,
2226                        const type_t *type)
2227 {
2228         parser_print_error_prefix_pos(source_position);
2229         fprintf(stderr, "%s, but found type ", msg);
2230         print_type(type);
2231         fputc('\n', stderr);
2232         error();
2233 }
2234
2235 static void type_error_incompatible(const char *msg,
2236                 const source_position_t source_position, const type_t *type1,
2237                 const type_t *type2)
2238 {
2239         parser_print_error_prefix_pos(source_position);
2240         fprintf(stderr, "%s, incompatible types: ", msg);
2241         print_type(type1);
2242         fprintf(stderr, " - ");
2243         print_type(type2);
2244         fprintf(stderr, ")\n");
2245         error();
2246 }
2247
2248 static type_t *get_type_after_conversion(const type_t *type1,
2249                                          const type_t *type2)
2250 {
2251         /* TODO... */
2252         (void) type2;
2253         return (type_t*) type1;
2254 }
2255
2256 static expression_t *parse_conditional_expression(unsigned precedence,
2257                                                   expression_t *expression)
2258 {
2259         eat('?');
2260
2261         conditional_expression_t *conditional
2262                 = allocate_ast_zero(sizeof(conditional[0]));
2263         conditional->expression.type = EXPR_CONDITIONAL;
2264         conditional->condition = expression;
2265
2266         /* 6.5.15.2 */
2267         type_t *condition_type = conditional->condition->datatype;
2268         if(condition_type != NULL) {
2269                 if(!is_type_scalar(condition_type)) {
2270                         type_error("expected a scalar type", expression->source_position,
2271                                    condition_type);
2272                 }
2273         }
2274
2275         conditional->true_expression = parse_expression();
2276         expect(':');
2277         conditional->false_expression = parse_sub_expression(precedence);
2278
2279         type_t *true_type  = conditional->true_expression->datatype;
2280         if(true_type == NULL)
2281                 return (expression_t*) conditional;
2282         type_t *false_type = conditional->false_expression->datatype;
2283         if(false_type == NULL)
2284                 return (expression_t*) conditional;
2285
2286         /* 6.4.15.3 */
2287         if(true_type == false_type) {
2288                 conditional->expression.datatype = true_type;
2289         } else if(is_type_arithmetic(true_type) && is_type_arithmetic(false_type)) {
2290                 type_t *result = get_type_after_conversion(true_type, false_type);
2291                 /* TODO: create implicit convs if necessary */
2292                 conditional->expression.datatype = result;
2293         } else if(true_type->type == TYPE_POINTER &&
2294                   false_type->type == TYPE_POINTER &&
2295                           true /* TODO compatible points_to types */) {
2296                 /* TODO */
2297         } else if(/* (is_null_ptr_const(true_type) && false_type->type == TYPE_POINTER)
2298                || (is_null_ptr_const(false_type) &&
2299                    true_type->type == TYPE_POINTER) TODO*/ false) {
2300                 /* TODO */
2301         } else if(/* 1 is pointer to object type, other is void* */ false) {
2302                 /* TODO */
2303         } else {
2304                 type_error_incompatible("problem while parsing conditional",
2305                                         expression->source_position, true_type,
2306                                         false_type);
2307         }
2308
2309         return (expression_t*) conditional;
2310 }
2311
2312 static expression_t *parse_extension(unsigned precedence)
2313 {
2314         eat(T___extension__);
2315
2316         /* TODO enable extensions */
2317
2318         return parse_sub_expression(precedence);
2319 }
2320
2321 #define CREATE_UNARY_EXPRESSION_PARSER(token_type, unexpression_type)     \
2322 static                                                                    \
2323 expression_t *parse_##unexpression_type(unsigned precedence)              \
2324 {                                                                         \
2325         eat(token_type);                                                      \
2326                                                                           \
2327         unary_expression_t *unary_expression                                  \
2328                 = allocate_ast_zero(sizeof(unary_expression[0]));                 \
2329         unary_expression->expression.type = EXPR_UNARY;                       \
2330         unary_expression->type            = unexpression_type;                \
2331         unary_expression->value           = parse_sub_expression(precedence); \
2332                                                                           \
2333         return (expression_t*) unary_expression;                              \
2334 }
2335
2336 CREATE_UNARY_EXPRESSION_PARSER('-', UNEXPR_NEGATE)
2337 CREATE_UNARY_EXPRESSION_PARSER('+', UNEXPR_PLUS)
2338 CREATE_UNARY_EXPRESSION_PARSER('!', UNEXPR_NOT)
2339 CREATE_UNARY_EXPRESSION_PARSER('*', UNEXPR_DEREFERENCE)
2340 CREATE_UNARY_EXPRESSION_PARSER('&', UNEXPR_TAKE_ADDRESS)
2341 CREATE_UNARY_EXPRESSION_PARSER('~', UNEXPR_BITWISE_NEGATE)
2342 CREATE_UNARY_EXPRESSION_PARSER(T_PLUSPLUS,   UNEXPR_PREFIX_INCREMENT)
2343 CREATE_UNARY_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_PREFIX_DECREMENT)
2344
2345 #define CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(token_type, unexpression_type) \
2346 static                                                                        \
2347 expression_t *parse_##unexpression_type(unsigned precedence,                  \
2348                                         expression_t *left)                   \
2349 {                                                                             \
2350         (void) precedence;                                                        \
2351         eat(token_type);                                                          \
2352                                                                               \
2353         unary_expression_t *unary_expression                                      \
2354                 = allocate_ast_zero(sizeof(unary_expression[0]));                     \
2355         unary_expression->expression.type = EXPR_UNARY;                           \
2356         unary_expression->type            = unexpression_type;                    \
2357         unary_expression->value           = left;                                 \
2358                                                                               \
2359         return (expression_t*) unary_expression;                                  \
2360 }
2361
2362 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_PLUSPLUS,   UNEXPR_POSTFIX_INCREMENT)
2363 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_POSTFIX_DECREMENT)
2364
2365 #define CREATE_BINEXPR_PARSER(token_type, binexpression_type)    \
2366 static                                                           \
2367 expression_t *parse_##binexpression_type(unsigned precedence,    \
2368                                          expression_t *left)     \
2369 {                                                                \
2370         eat(token_type);                                             \
2371                                                                  \
2372         expression_t *right = parse_sub_expression(precedence);      \
2373                                                                  \
2374         binary_expression_t *binexpr                                 \
2375                 = allocate_ast_zero(sizeof(binexpr[0]));                 \
2376         binexpr->expression.type = EXPR_BINARY;                      \
2377         binexpr->type            = binexpression_type;               \
2378         binexpr->left            = left;                             \
2379         binexpr->right           = right;                            \
2380                                                                  \
2381         return (expression_t*) binexpr;                              \
2382 }
2383
2384 CREATE_BINEXPR_PARSER(',', BINEXPR_COMMA)
2385 CREATE_BINEXPR_PARSER('*', BINEXPR_MUL)
2386 CREATE_BINEXPR_PARSER('/', BINEXPR_DIV)
2387 CREATE_BINEXPR_PARSER('%', BINEXPR_MOD)
2388 CREATE_BINEXPR_PARSER('+', BINEXPR_ADD)
2389 CREATE_BINEXPR_PARSER('-', BINEXPR_SUB)
2390 CREATE_BINEXPR_PARSER('<', BINEXPR_LESS)
2391 CREATE_BINEXPR_PARSER('>', BINEXPR_GREATER)
2392 CREATE_BINEXPR_PARSER('=', BINEXPR_ASSIGN)
2393 CREATE_BINEXPR_PARSER(T_EQUALEQUAL, BINEXPR_EQUAL)
2394 CREATE_BINEXPR_PARSER(T_EXCLAMATIONMARKEQUAL, BINEXPR_NOTEQUAL)
2395 CREATE_BINEXPR_PARSER(T_LESSEQUAL, BINEXPR_LESSEQUAL)
2396 CREATE_BINEXPR_PARSER(T_GREATEREQUAL, BINEXPR_GREATEREQUAL)
2397 CREATE_BINEXPR_PARSER('&', BINEXPR_BITWISE_AND)
2398 CREATE_BINEXPR_PARSER('|', BINEXPR_BITWISE_OR)
2399 CREATE_BINEXPR_PARSER('^', BINEXPR_BITWISE_XOR)
2400 CREATE_BINEXPR_PARSER(T_ANDAND, BINEXPR_LOGICAL_AND)
2401 CREATE_BINEXPR_PARSER(T_PIPEPIPE, BINEXPR_LOGICAL_OR)
2402 CREATE_BINEXPR_PARSER(T_LESSLESS, BINEXPR_SHIFTLEFT)
2403 CREATE_BINEXPR_PARSER(T_GREATERGREATER, BINEXPR_SHIFTRIGHT)
2404 CREATE_BINEXPR_PARSER(T_PLUSEQUAL, BINEXPR_ADD_ASSIGN)
2405 CREATE_BINEXPR_PARSER(T_MINUSEQUAL, BINEXPR_SUB_ASSIGN)
2406 CREATE_BINEXPR_PARSER(T_ASTERISKEQUAL, BINEXPR_MUL_ASSIGN)
2407 CREATE_BINEXPR_PARSER(T_SLASHEQUAL, BINEXPR_DIV_ASSIGN)
2408 CREATE_BINEXPR_PARSER(T_PERCENTEQUAL, BINEXPR_MOD_ASSIGN)
2409 CREATE_BINEXPR_PARSER(T_LESSLESSEQUAL, BINEXPR_SHIFTLEFT_ASSIGN)
2410 CREATE_BINEXPR_PARSER(T_GREATERGREATEREQUAL, BINEXPR_SHIFTRIGHT_ASSIGN)
2411 CREATE_BINEXPR_PARSER(T_ANDEQUAL, BINEXPR_BITWISE_AND_ASSIGN)
2412 CREATE_BINEXPR_PARSER(T_PIPEEQUAL, BINEXPR_BITWISE_OR_ASSIGN)
2413 CREATE_BINEXPR_PARSER(T_CARETEQUAL, BINEXPR_BITWISE_XOR_ASSIGN)
2414
2415 static expression_t *parse_sub_expression(unsigned precedence)
2416 {
2417         if(token.type < 0) {
2418                 return expected_expression_error();
2419         }
2420
2421         expression_parser_function_t *parser
2422                 = &expression_parsers[token.type];
2423         source_position_t             source_position = token.source_position;
2424         expression_t                 *left;
2425
2426         if(parser->parser != NULL) {
2427                 left = parser->parser(parser->precedence);
2428         } else {
2429                 left = parse_primary_expression();
2430         }
2431         assert(left != NULL);
2432         left->source_position = source_position;
2433
2434         while(true) {
2435                 if(token.type < 0) {
2436                         return expected_expression_error();
2437                 }
2438
2439                 parser = &expression_parsers[token.type];
2440                 if(parser->infix_parser == NULL)
2441                         break;
2442                 if(parser->infix_precedence < precedence)
2443                         break;
2444
2445                 left = parser->infix_parser(parser->infix_precedence, left);
2446
2447                 assert(left != NULL);
2448                 assert(left->type != EXPR_INVALID);
2449                 left->source_position = source_position;
2450         }
2451
2452         return left;
2453 }
2454
2455 static expression_t *parse_expression(void)
2456 {
2457         return parse_sub_expression(1);
2458 }
2459
2460
2461
2462 void register_expression_parser(parse_expression_function parser,
2463                                 int token_type, unsigned precedence)
2464 {
2465         expression_parser_function_t *entry = &expression_parsers[token_type];
2466
2467         if(entry->parser != NULL) {
2468                 fprintf(stderr, "for token ");
2469                 print_token_type(stderr, token_type);
2470                 fprintf(stderr, "\n");
2471                 panic("trying to register multiple expression parsers for a token");
2472         }
2473         entry->parser     = parser;
2474         entry->precedence = precedence;
2475 }
2476
2477 void register_expression_infix_parser(parse_expression_infix_function parser,
2478                                       int token_type, unsigned precedence)
2479 {
2480         expression_parser_function_t *entry = &expression_parsers[token_type];
2481
2482         if(entry->infix_parser != NULL) {
2483                 fprintf(stderr, "for token ");
2484                 print_token_type(stderr, token_type);
2485                 fprintf(stderr, "\n");
2486                 panic("trying to register multiple infix expression parsers for a "
2487                       "token");
2488         }
2489         entry->infix_parser     = parser;
2490         entry->infix_precedence = precedence;
2491 }
2492
2493 static void init_expression_parsers(void)
2494 {
2495         memset(&expression_parsers, 0, sizeof(expression_parsers));
2496
2497         register_expression_infix_parser(parse_BINEXPR_MUL,         '*',        16);
2498         register_expression_infix_parser(parse_BINEXPR_DIV,         '/',        16);
2499         register_expression_infix_parser(parse_BINEXPR_MOD,         '%',        16);
2500         register_expression_infix_parser(parse_BINEXPR_SHIFTLEFT,   T_LESSLESS, 16);
2501         register_expression_infix_parser(parse_BINEXPR_SHIFTRIGHT,
2502                                                               T_GREATERGREATER, 16);
2503         register_expression_infix_parser(parse_BINEXPR_ADD,         '+',        15);
2504         register_expression_infix_parser(parse_BINEXPR_SUB,         '-',        15);
2505         register_expression_infix_parser(parse_BINEXPR_LESS,        '<',        14);
2506         register_expression_infix_parser(parse_BINEXPR_GREATER,     '>',        14);
2507         register_expression_infix_parser(parse_BINEXPR_LESSEQUAL, T_LESSEQUAL,  14);
2508         register_expression_infix_parser(parse_BINEXPR_GREATEREQUAL,
2509                                                                 T_GREATEREQUAL, 14);
2510         register_expression_infix_parser(parse_BINEXPR_EQUAL,     T_EQUALEQUAL, 13);
2511         register_expression_infix_parser(parse_BINEXPR_NOTEQUAL,
2512                                                         T_EXCLAMATIONMARKEQUAL, 13);
2513         register_expression_infix_parser(parse_BINEXPR_BITWISE_AND, '&',        12);
2514         register_expression_infix_parser(parse_BINEXPR_BITWISE_XOR, '^',        11);
2515         register_expression_infix_parser(parse_BINEXPR_BITWISE_OR,  '|',        10);
2516         register_expression_infix_parser(parse_BINEXPR_LOGICAL_AND, T_ANDAND,    9);
2517         register_expression_infix_parser(parse_BINEXPR_LOGICAL_OR,  T_PIPEPIPE,  8);
2518         register_expression_infix_parser(parse_conditional_expression, '?',      7);
2519         register_expression_infix_parser(parse_BINEXPR_ASSIGN,      '=',         2);
2520         register_expression_infix_parser(parse_BINEXPR_ADD_ASSIGN, T_PLUSEQUAL,  2);
2521         register_expression_infix_parser(parse_BINEXPR_SUB_ASSIGN, T_MINUSEQUAL, 2);
2522         register_expression_infix_parser(parse_BINEXPR_MUL_ASSIGN,
2523                                                                 T_ASTERISKEQUAL, 2);
2524         register_expression_infix_parser(parse_BINEXPR_DIV_ASSIGN, T_SLASHEQUAL, 2);
2525         register_expression_infix_parser(parse_BINEXPR_MOD_ASSIGN,
2526                                                                  T_PERCENTEQUAL, 2);
2527         register_expression_infix_parser(parse_BINEXPR_SHIFTLEFT_ASSIGN,
2528                                                                 T_LESSLESSEQUAL, 2);
2529         register_expression_infix_parser(parse_BINEXPR_SHIFTRIGHT_ASSIGN,
2530                                                           T_GREATERGREATEREQUAL, 2);
2531         register_expression_infix_parser(parse_BINEXPR_BITWISE_AND_ASSIGN,
2532                                                                      T_ANDEQUAL, 2);
2533         register_expression_infix_parser(parse_BINEXPR_BITWISE_OR_ASSIGN,
2534                                                                     T_PIPEEQUAL, 2);
2535         register_expression_infix_parser(parse_BINEXPR_BITWISE_XOR_ASSIGN,
2536                                                                    T_CARETEQUAL, 2);
2537
2538         register_expression_infix_parser(parse_BINEXPR_COMMA,       ',',         1);
2539
2540         register_expression_infix_parser(parse_array_expression,        '[',    30);
2541         register_expression_infix_parser(parse_call_expression,         '(',    30);
2542         register_expression_infix_parser(parse_select_expression,       '.',    30);
2543         register_expression_infix_parser(parse_select_expression,
2544                                                                 T_MINUSGREATER, 30);
2545         register_expression_infix_parser(parse_UNEXPR_POSTFIX_INCREMENT,
2546                                          T_PLUSPLUS, 30);
2547         register_expression_infix_parser(parse_UNEXPR_POSTFIX_DECREMENT,
2548                                          T_MINUSMINUS, 30);
2549
2550         register_expression_parser(parse_UNEXPR_NEGATE,           '-',          25);
2551         register_expression_parser(parse_UNEXPR_PLUS,             '+',          25);
2552         register_expression_parser(parse_UNEXPR_NOT,              '!',          25);
2553         register_expression_parser(parse_UNEXPR_BITWISE_NEGATE,   '~',          25);
2554         register_expression_parser(parse_UNEXPR_DEREFERENCE,      '*',          25);
2555         register_expression_parser(parse_UNEXPR_TAKE_ADDRESS,     '&',          25);
2556         register_expression_parser(parse_UNEXPR_PREFIX_INCREMENT, T_PLUSPLUS,   25);
2557         register_expression_parser(parse_UNEXPR_PREFIX_DECREMENT, T_MINUSMINUS, 25);
2558         register_expression_parser(parse_sizeof,                  T_sizeof,     25);
2559         register_expression_parser(parse_extension,            T___extension__, 25);
2560 }
2561
2562
2563 static statement_t *parse_case_statement(void)
2564 {
2565         eat(T_case);
2566         case_label_statement_t *label = allocate_ast_zero(sizeof(label[0]));
2567         label->statement.type            = STATEMENT_CASE_LABEL;
2568         label->statement.source_position = token.source_position;
2569
2570         label->expression = parse_expression();
2571
2572         expect(':');
2573         label->statement.next = parse_statement();
2574
2575         return (statement_t*) label;
2576 }
2577
2578 static statement_t *parse_default_statement(void)
2579 {
2580         eat(T_default);
2581
2582         case_label_statement_t *label = allocate_ast_zero(sizeof(label[0]));
2583         label->statement.type            = STATEMENT_CASE_LABEL;
2584         label->statement.source_position = token.source_position;
2585
2586         expect(':');
2587         label->statement.next = parse_statement();
2588
2589         return (statement_t*) label;
2590 }
2591
2592 static statement_t *parse_label_statement(void)
2593 {
2594         eat(T_IDENTIFIER);
2595         expect(':');
2596         parse_statement();
2597
2598         return NULL;
2599 }
2600
2601 static statement_t *parse_if(void)
2602 {
2603         eat(T_if);
2604
2605         if_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2606         statement->statement.type            = STATEMENT_IF;
2607         statement->statement.source_position = token.source_position;
2608
2609         expect('(');
2610         statement->condition = parse_expression();
2611         expect(')');
2612
2613         statement->true_statement = parse_statement();
2614         if(token.type == T_else) {
2615                 next_token();
2616                 statement->false_statement = parse_statement();
2617         }
2618
2619         return (statement_t*) statement;
2620 }
2621
2622 static statement_t *parse_switch(void)
2623 {
2624         eat(T_switch);
2625
2626         switch_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2627         statement->statement.type            = STATEMENT_SWITCH;
2628         statement->statement.source_position = token.source_position;
2629
2630         expect('(');
2631         statement->expression = parse_expression();
2632         expect(')');
2633         statement->body = parse_statement();
2634
2635         return (statement_t*) statement;
2636 }
2637
2638 static statement_t *parse_while(void)
2639 {
2640         eat(T_while);
2641
2642         while_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2643         statement->statement.type            = STATEMENT_WHILE;
2644         statement->statement.source_position = token.source_position;
2645
2646         expect('(');
2647         statement->condition = parse_expression();
2648         expect(')');
2649         statement->body = parse_statement();
2650
2651         return (statement_t*) statement;
2652 }
2653
2654 static statement_t *parse_do(void)
2655 {
2656         eat(T_do);
2657
2658         do_while_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2659         statement->statement.type            = STATEMENT_DO_WHILE;
2660         statement->statement.source_position = token.source_position;
2661
2662         statement->body = parse_statement();
2663         expect(T_while);
2664         expect('(');
2665         statement->condition = parse_expression();
2666         expect(')');
2667         expect(';');
2668
2669         return (statement_t*) statement;
2670 }
2671
2672 static statement_t *parse_for(void)
2673 {
2674         eat(T_for);
2675
2676         for_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2677         statement->statement.type            = STATEMENT_FOR;
2678         statement->statement.source_position = token.source_position;
2679
2680         expect('(');
2681
2682         int         top          = environment_top();
2683         context_t  *last_context = context;
2684         set_context(&statement->context);
2685
2686         if(token.type != ';') {
2687                 if(is_declaration_specifier(&token, false)) {
2688                         parse_declaration();
2689                 } else {
2690                         statement->initialisation = parse_expression();
2691                         expect(';');
2692                 }
2693         } else {
2694                 expect(';');
2695         }
2696
2697         if(token.type != ';') {
2698                 statement->condition = parse_expression();
2699         }
2700         expect(';');
2701         if(token.type != ')') {
2702                 statement->step = parse_expression();
2703         }
2704         expect(')');
2705         statement->body = parse_statement();
2706
2707         assert(context == &statement->context);
2708         set_context(last_context);
2709         environment_pop_to(top);
2710
2711         return (statement_t*) statement;
2712 }
2713
2714 static statement_t *parse_goto(void)
2715 {
2716         eat(T_goto);
2717         expect(T_IDENTIFIER);
2718         expect(';');
2719
2720         return NULL;
2721 }
2722
2723 static statement_t *parse_continue(void)
2724 {
2725         eat(T_continue);
2726         expect(';');
2727
2728         statement_t *statement     = allocate_ast_zero(sizeof(statement[0]));
2729         statement->source_position = token.source_position;
2730         statement->type            = STATEMENT_CONTINUE;
2731
2732         return statement;
2733 }
2734
2735 static statement_t *parse_break(void)
2736 {
2737         eat(T_break);
2738         expect(';');
2739
2740         statement_t *statement     = allocate_ast_zero(sizeof(statement[0]));
2741         statement->source_position = token.source_position;
2742         statement->type            = STATEMENT_BREAK;
2743
2744         return statement;
2745 }
2746
2747 static statement_t *parse_return(void)
2748 {
2749         eat(T_return);
2750
2751         return_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2752
2753         statement->statement.type            = STATEMENT_RETURN;
2754         statement->statement.source_position = token.source_position;
2755         if(token.type != ';') {
2756                 statement->return_value = parse_expression();
2757         }
2758         expect(';');
2759
2760         return (statement_t*) statement;
2761 }
2762
2763 static statement_t *parse_declaration_statement(void)
2764 {
2765         declaration_t *before = last_declaration;
2766
2767         declaration_statement_t *statement
2768                 = allocate_ast_zero(sizeof(statement[0]));
2769         statement->statement.type            = STATEMENT_DECLARATION;
2770         statement->statement.source_position = token.source_position;
2771
2772         declaration_specifiers_t specifiers;
2773         memset(&specifiers, 0, sizeof(specifiers));
2774         parse_declaration_specifiers(&specifiers);
2775
2776         if(token.type == ';') {
2777                 eat(';');
2778         } else {
2779                 parse_init_declarators(&specifiers);
2780         }
2781
2782         if(before == NULL) {
2783                 statement->declarations_begin = context->declarations;
2784         } else {
2785                 statement->declarations_begin = before->next;
2786         }
2787         statement->declarations_end = last_declaration;
2788
2789         return (statement_t*) statement;
2790 }
2791
2792 static statement_t *parse_expression_statement(void)
2793 {
2794         expression_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
2795         statement->statement.type            = STATEMENT_EXPRESSION;
2796         statement->statement.source_position = token.source_position;
2797
2798         statement->expression = parse_expression();
2799
2800         expect(';');
2801
2802         return (statement_t*) statement;
2803 }
2804
2805 static statement_t *parse_statement(void)
2806 {
2807         declaration_t *declaration;
2808         statement_t   *statement = NULL;
2809
2810         /* declaration or statement */
2811         switch(token.type) {
2812         case T_case:
2813                 statement = parse_case_statement();
2814                 break;
2815
2816         case T_default:
2817                 statement = parse_default_statement();
2818                 break;
2819
2820         case '{':
2821                 statement = parse_compound_statement();
2822                 break;
2823
2824         case T_if:
2825                 statement = parse_if();
2826                 break;
2827
2828         case T_switch:
2829                 statement = parse_switch();
2830                 break;
2831
2832         case T_while:
2833                 statement = parse_while();
2834                 break;
2835
2836         case T_do:
2837                 statement = parse_do();
2838                 break;
2839
2840         case T_for:
2841                 statement = parse_for();
2842                 break;
2843
2844         case T_goto:
2845                 statement = parse_goto();
2846                 break;
2847
2848         case T_continue:
2849                 statement = parse_continue();
2850                 break;
2851
2852         case T_break:
2853                 statement = parse_break();
2854                 break;
2855
2856         case T_return:
2857                 statement = parse_return();
2858                 break;
2859
2860         case ';':
2861                 next_token();
2862                 statement = NULL;
2863                 break;
2864
2865         case T_IDENTIFIER:
2866                 if(look_ahead(1)->type == ':') {
2867                         statement = parse_label_statement();
2868                         break;
2869                 }
2870
2871                 declaration = token.v.symbol->declaration;
2872                 if(declaration != NULL &&
2873                                 declaration->storage_class == STORAGE_CLASS_TYPEDEF) {
2874                         statement = parse_declaration_statement();
2875                         break;
2876                 }
2877
2878                 statement = parse_expression_statement();
2879                 break;
2880
2881         case T___extension__:
2882                 /* this can be a prefix to a declaration or an expression statement */
2883                 /* we simply eat it now and parse the rest with tail recursion */
2884                 do {
2885                         next_token();
2886                 } while(token.type == T___extension__);
2887                 statement = parse_statement();
2888                 break;
2889
2890         DECLARATION_START
2891                 statement = parse_declaration_statement();
2892                 break;
2893
2894         default:
2895                 statement = parse_expression_statement();
2896                 break;
2897         }
2898
2899         assert(statement == NULL || statement->source_position.input_name != NULL);
2900
2901         return statement;
2902 }
2903
2904 static statement_t *parse_compound_statement(void)
2905 {
2906         eat('{');
2907
2908         compound_statement_t *compound_statement
2909                 = allocate_ast_zero(sizeof(compound_statement[0]));
2910         compound_statement->statement.type            = STATEMENT_COMPOUND;
2911         compound_statement->statement.source_position = token.source_position;
2912
2913         int        top          = environment_top();
2914         context_t *last_context = context;
2915         set_context(&compound_statement->context);
2916
2917         statement_t *last_statement = NULL;
2918
2919         while(token.type != '}' && token.type != T_EOF) {
2920                 statement_t *statement = parse_statement();
2921                 if(statement == NULL)
2922                         continue;
2923
2924                 if(last_statement != NULL) {
2925                         last_statement->next = statement;
2926                 } else {
2927                         compound_statement->statements = statement;
2928                 }
2929
2930                 while(statement->next != NULL)
2931                         statement = statement->next;
2932
2933                 last_statement = statement;
2934         }
2935
2936         assert(context == &compound_statement->context);
2937         set_context(last_context);
2938         environment_pop_to(top);
2939
2940         next_token();
2941
2942         return (statement_t*) compound_statement;
2943 }
2944
2945 static translation_unit_t *parse_translation_unit(void)
2946 {
2947         translation_unit_t *unit = allocate_ast_zero(sizeof(unit[0]));
2948
2949         assert(global_context == NULL);
2950         global_context = &unit->context;
2951
2952         assert(context == NULL);
2953         set_context(&unit->context);
2954
2955         while(token.type != T_EOF) {
2956                 parse_declaration();
2957         }
2958
2959         assert(context == &unit->context);
2960         context          = NULL;
2961         last_declaration = NULL;
2962
2963         assert(global_context == &unit->context);
2964         global_context = NULL;
2965
2966         return unit;
2967 }
2968
2969 translation_unit_t *parse(void)
2970 {
2971         obstack_init(&environment_obstack);
2972         environment_stack = NEW_ARR_F(environment_entry_t*, 0);
2973
2974         type_set_output(stderr);
2975
2976         lookahead_bufpos = 0;
2977         for(int i = 0; i < MAX_LOOKAHEAD + 2; ++i) {
2978                 next_token();
2979         }
2980         translation_unit_t *unit = parse_translation_unit();
2981
2982         DEL_ARR_F(environment_stack);
2983         obstack_free(&environment_obstack, NULL);
2984
2985         return unit;
2986 }
2987
2988 void init_parser(void)
2989 {
2990         init_expression_parsers();
2991         obstack_init(&temp_obst);
2992
2993         type_int        = make_atomic_type(ATOMIC_TYPE_INT, 0);
2994         type_double     = make_atomic_type(ATOMIC_TYPE_DOUBLE, 0);
2995         type_size_t     = make_atomic_type(ATOMIC_TYPE_UINT, 0);
2996         type_const_char = make_atomic_type(ATOMIC_TYPE_CHAR, TYPE_QUALIFIER_CONST);
2997         type_void       = make_atomic_type(ATOMIC_TYPE_VOID, 0);
2998         type_string     = make_pointer_type(type_const_char, 0);
2999 }
3000
3001 void exit_parser(void)
3002 {
3003         obstack_free(&temp_obst, NULL);
3004 }