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