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