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