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