nsz Git - cparser/blob - parser.c

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