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