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 namespc;
  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 stack_entry_t  *label_stack       = NULL;
  33 static context_t      *global_context    = NULL;
  34 static context_t      *context           = NULL;
  35 static declaration_t  *last_declaration  = NULL;
  36 static declaration_t  *current_function  = NULL;
  37 static struct obstack  temp_obst;
  38 static bool            found_error;
  39
  40 static type_t         *type_int         = NULL;
  41 static type_t         *type_uint        = NULL;
  42 static type_t         *type_long_double = NULL;
  43 static type_t         *type_double      = NULL;
  44 static type_t         *type_float       = NULL;
  45 static type_t         *type_const_char  = NULL;
  46 static type_t         *type_string      = NULL;
  47 static type_t         *type_void        = NULL;
  48 static type_t         *type_void_ptr    = NULL;
  49 static type_t         *type_size_t      = NULL;
  50 static type_t         *type_ptrdiff_t   = NULL;
  51
  52 static statement_t *parse_compound_statement(void);
  53 static statement_t *parse_statement(void);
  54
  55 static expression_t *parse_sub_expression(unsigned precedence);
  56 static expression_t *parse_expression(void);
  57 static type_t       *parse_typename(void);
  58
  59 #define STORAGE_CLASSES     \
  60         case T_typedef:         \
  61         case T_extern:          \
  62         case T_static:          \
  63         case T_auto:            \
  64         case T_register:
  65
  66 #define TYPE_QUALIFIERS     \
  67         case T_const:           \
  68         case T_restrict:        \
  69         case T_volatile:        \
  70         case T_inline:
  71
  72 #ifdef PROVIDE_COMPLEX
  73 #define COMPLEX_SPECIFIERS  \
  74         case T__Complex:
  75 #define IMAGINARY_SPECIFIERS \
  76         case T__Imaginary:
  77 #else
  78 #define COMPLEX_SPECIFIERS
  79 #define IMAGINARY_SPECIFIERS
  80 #endif
  81
  82 #define TYPE_SPECIFIERS     \
  83         case T_void:            \
  84         case T_char:            \
  85         case T_short:           \
  86         case T_int:             \
  87         case T_long:            \
  88         case T_float:           \
  89         case T_double:          \
  90         case T_signed:          \
  91         case T_unsigned:        \
  92         case T__Bool:           \
  93         case T_struct:          \
  94         case T_union:           \
  95         case T_enum:            \
  96         case T___typeof__:      \
  97         COMPLEX_SPECIFIERS      \
  98         IMAGINARY_SPECIFIERS
  99
 100 #define DECLARATION_START   \
 101         STORAGE_CLASSES         \
 102         TYPE_QUALIFIERS         \
 103         TYPE_SPECIFIERS
 104
 105 #define TYPENAME_START      \
 106         TYPE_QUALIFIERS         \
 107         TYPE_SPECIFIERS
 108
 109 static inline void *allocate_ast_zero(size_t size)
 110 {
 111         void *res = allocate_ast(size);
 112         memset(res, 0, size);
 113         return res;
 114 }
 115
 116 static inline void *allocate_type_zero(size_t size)
 117 {
 118         void *res = obstack_alloc(type_obst, size);
 119         memset(res, 0, size);
 120         return res;
 121 }
 122
 123 static inline void free_type(void *type)
 124 {
 125         obstack_free(type_obst, type);
 126 }
 127
 128 /**
 129  * returns the top element of the environment stack
 130  */
 131 static inline size_t environment_top(void)
 132 {
 133         return ARR_LEN(environment_stack);
 134 }
 135
 136 static inline size_t label_top(void)
 137 {
 138         return ARR_LEN(label_stack);
 139 }
 140
 141
 142
 143 static inline void next_token(void)
 144 {
 145         token                              = lookahead_buffer[lookahead_bufpos];
 146         lookahead_buffer[lookahead_bufpos] = lexer_token;
 147         lexer_next_token();
 148
 149         lookahead_bufpos = (lookahead_bufpos+1) % MAX_LOOKAHEAD;
 150
 151 #ifdef PRINT_TOKENS
 152         print_token(stderr, &token);
 153         fprintf(stderr, "\n");
 154 #endif
 155 }
 156
 157 static inline const token_t *look_ahead(int num)
 158 {
 159         assert(num > 0 && num <= MAX_LOOKAHEAD);
 160         int pos = (lookahead_bufpos+num-1) % MAX_LOOKAHEAD;
 161         return & lookahead_buffer[pos];
 162 }
 163
 164 #define eat(token_type)  do { assert(token.type == token_type); next_token(); } while(0)
 165
 166 static void error(void)
 167 {
 168         found_error = true;
 169 #ifdef ABORT_ON_ERROR
 170         abort();
 171 #endif
 172 }
 173
 174 static void parser_print_prefix_pos(const source_position_t source_position)
 175 {
 176     fputs(source_position.input_name, stderr);
 177     fputc(':', stderr);
 178     fprintf(stderr, "%d", source_position.linenr);
 179     fputs(": ", stderr);
 180 }
 181
 182 static void parser_print_error_prefix_pos(
 183                 const source_position_t source_position)
 184 {
 185         parser_print_prefix_pos(source_position);
 186         fputs("error: ", stderr);
 187         error();
 188 }
 189
 190 static void parser_print_error_prefix(void)
 191 {
 192         parser_print_error_prefix_pos(token.source_position);
 193 }
 194
 195 static void parse_error(const char *message)
 196 {
 197         parser_print_error_prefix();
 198         fprintf(stderr, "parse error: %s\n", message);
 199 }
 200
 201 static void parser_print_warning_prefix_pos(
 202                 const source_position_t source_position)
 203 {
 204         parser_print_prefix_pos(source_position);
 205         fputs("warning: ", stderr);
 206 }
 207
 208 static void parse_warning_pos(const source_position_t source_position,
 209                               const char *const message)
 210 {
 211         parser_print_prefix_pos(source_position);
 212         fprintf(stderr, "warning: %s\n", message);
 213 }
 214
 215 static void parse_warning(const char *message)
 216 {
 217         parse_warning_pos(token.source_position, message);
 218 }
 219
 220 static void parse_error_expected(const char *message, ...)
 221 {
 222         va_list args;
 223         int first = 1;
 224
 225         if(message != NULL) {
 226                 parser_print_error_prefix();
 227                 fprintf(stderr, "%s\n", message);
 228         }
 229         parser_print_error_prefix();
 230         fputs("Parse error: got ", stderr);
 231         print_token(stderr, &token);
 232         fputs(", expected ", stderr);
 233
 234         va_start(args, message);
 235         token_type_t token_type = va_arg(args, token_type_t);
 236         while(token_type != 0) {
 237                 if(first == 1) {
 238                         first = 0;
 239                 } else {
 240                         fprintf(stderr, ", ");
 241                 }
 242                 print_token_type(stderr, token_type);
 243                 token_type = va_arg(args, token_type_t);
 244         }
 245         va_end(args);
 246         fprintf(stderr, "\n");
 247 }
 248
 249 static void print_type_quoted(type_t *type)
 250 {
 251         fputc('\'', stderr);
 252         print_type(type);
 253         fputc('\'', stderr);
 254 }
 255
 256 static void type_error(const char *msg, const source_position_t source_position,
 257                        type_t *type)
 258 {
 259         parser_print_error_prefix_pos(source_position);
 260         fprintf(stderr, "%s, but found type ", msg);
 261         print_type_quoted(type);
 262         fputc('\n', stderr);
 263 }
 264
 265 static void type_error_incompatible(const char *msg,
 266                 const source_position_t source_position, type_t *type1, type_t *type2)
 267 {
 268         parser_print_error_prefix_pos(source_position);
 269         fprintf(stderr, "%s, incompatible types: ", msg);
 270         print_type_quoted(type1);
 271         fprintf(stderr, " - ");
 272         print_type_quoted(type2);
 273         fprintf(stderr, ")\n");
 274 }
 275
 276 static void eat_block(void)
 277 {
 278         if(token.type == '{')
 279                 next_token();
 280
 281         while(token.type != '}') {
 282                 if(token.type == T_EOF)
 283                         return;
 284                 if(token.type == '{') {
 285                         eat_block();
 286                         continue;
 287                 }
 288                 next_token();
 289         }
 290         eat('}');
 291 }
 292
 293 static void eat_statement(void)
 294 {
 295         while(token.type != ';') {
 296                 if(token.type == T_EOF)
 297                         return;
 298                 if(token.type == '}')
 299                         return;
 300                 if(token.type == '{') {
 301                         eat_block();
 302                         continue;
 303                 }
 304                 next_token();
 305         }
 306         eat(';');
 307 }
 308
 309 static void eat_brace(void)
 310 {
 311         if(token.type == '(')
 312                 next_token();
 313
 314         while(token.type != ')') {
 315                 if(token.type == T_EOF)
 316                         return;
 317                 if(token.type == ')' || token.type == ';' || token.type == '}') {
 318                         return;
 319                 }
 320                 if(token.type == '(') {
 321                         eat_brace();
 322                         continue;
 323                 }
 324                 if(token.type == '{') {
 325                         eat_block();
 326                         continue;
 327                 }
 328                 next_token();
 329         }
 330         eat(')');
 331 }
 332
 333 #define expect(expected)                           \
 334     if(UNLIKELY(token.type != (expected))) {       \
 335         parse_error_expected(NULL, (expected), 0); \
 336         eat_statement();                           \
 337         return NULL;                               \
 338     }                                              \
 339     next_token();
 340
 341 #define expect_block(expected)                     \
 342     if(UNLIKELY(token.type != (expected))) {       \
 343         parse_error_expected(NULL, (expected), 0); \
 344         eat_block();                               \
 345         return NULL;                               \
 346     }                                              \
 347     next_token();
 348
 349 #define expect_void(expected)                      \
 350     if(UNLIKELY(token.type != (expected))) {       \
 351         parse_error_expected(NULL, (expected), 0); \
 352         eat_statement();                           \
 353         return;                                    \
 354     }                                              \
 355     next_token();
 356
 357 static void set_context(context_t *new_context)
 358 {
 359         context = new_context;
 360
 361         last_declaration = new_context->declarations;
 362         if(last_declaration != NULL) {
 363                 while(last_declaration->next != NULL) {
 364                         last_declaration = last_declaration->next;
 365                 }
 366         }
 367 }
 368
 369 /**
 370  * called when we find a 2nd declarator for an identifier we already have a
 371  * declarator for
 372  */
 373 static bool is_compatible_declaration (declaration_t *declaration,
 374                                       declaration_t *previous)
 375 {
 376         /* TODO: not correct yet */
 377         return declaration->type == previous->type;
 378 }
 379
 380 static declaration_t *get_declaration(symbol_t *symbol, namespace_t namespc)
 381 {
 382         declaration_t *declaration = symbol->declaration;
 383         for( ; declaration != NULL; declaration = declaration->symbol_next) {
 384                 if(declaration->namespc == namespc)
 385                         return declaration;
 386         }
 387
 388         return NULL;
 389 }
 390
 391 static const char *get_namespace_prefix(namespace_t namespc)
 392 {
 393         switch(namespc) {
 394         case NAMESPACE_NORMAL:
 395                 return "";
 396         case NAMESPACE_UNION:
 397                 return "union ";
 398         case NAMESPACE_STRUCT:
 399                 return "struct ";
 400         case NAMESPACE_ENUM:
 401                 return "enum ";
 402         case NAMESPACE_LABEL:
 403                 return "label ";
 404         }
 405         panic("invalid namespace found");
 406 }
 407
 408 /**
 409  * pushs an environment_entry on the environment stack and links the
 410  * corresponding symbol to the new entry
 411  */
 412 static declaration_t *stack_push(stack_entry_t **stack_ptr,
 413                                  declaration_t *declaration,
 414                                  context_t *parent_context)
 415 {
 416         symbol_t    *symbol    = declaration->symbol;
 417         namespace_t  namespc = (namespace_t)declaration->namespc;
 418
 419         /* a declaration should be only pushed once */
 420         assert(declaration->parent_context == NULL);
 421         declaration->parent_context = parent_context;
 422
 423         declaration_t *previous_declaration = get_declaration(symbol, namespc);
 424         assert(declaration != previous_declaration);
 425         if(previous_declaration != NULL
 426                         && previous_declaration->parent_context == context) {
 427                 if(!is_compatible_declaration(declaration, previous_declaration)) {
 428                         parser_print_error_prefix_pos(declaration->source_position);
 429                         fprintf(stderr, "definition of symbol %s%s with type ",
 430                                         get_namespace_prefix(namespc), symbol->string);
 431                         print_type_quoted(declaration->type);
 432                         fputc('\n', stderr);
 433                         parser_print_error_prefix_pos(
 434                                         previous_declaration->source_position);
 435                         fprintf(stderr, "is incompatible with previous declaration "
 436                                         "of type ");
 437                         print_type_quoted(previous_declaration->type);
 438                         fputc('\n', stderr);
 439                 } else {
 440                         const storage_class_t old_storage = previous_declaration->storage_class;
 441                         const storage_class_t new_storage = declaration->storage_class;
 442                         if (current_function == NULL) {
 443                                 if (old_storage != STORAGE_CLASS_STATIC &&
 444                                     new_storage == STORAGE_CLASS_STATIC) {
 445                                         parser_print_error_prefix_pos(declaration->source_position);
 446                                         fprintf(stderr,
 447                                                 "static declaration of '%s' follows non-static declaration\n",
 448                                                 symbol->string);
 449                                         parser_print_error_prefix_pos(previous_declaration->source_position);
 450                                         fprintf(stderr, "previous declaration of '%s' was here\n",
 451                                                 symbol->string);
 452                                 } else {
 453                                         if (old_storage == STORAGE_CLASS_EXTERN) {
 454                                                 if (new_storage == STORAGE_CLASS_NONE) {
 455                                                         previous_declaration->storage_class = STORAGE_CLASS_NONE;
 456                                                 }
 457                                         } else {
 458                                                 parser_print_warning_prefix_pos(declaration->source_position);
 459                                                 fprintf(stderr, "redundant declaration for '%s'\n",
 460                                                                                 symbol->string);
 461                                                 parser_print_warning_prefix_pos(previous_declaration->source_position);
 462                                                 fprintf(stderr, "previous declaration of '%s' was here\n",
 463                                                                                 symbol->string);
 464                                         }
 465                                 }
 466                         } else {
 467                                 if (old_storage == STORAGE_CLASS_EXTERN &&
 468                                                 new_storage == STORAGE_CLASS_EXTERN) {
 469                                         parser_print_warning_prefix_pos(declaration->source_position);
 470                                         fprintf(stderr, "redundant extern declaration for '%s'\n",
 471                                                 symbol->string);
 472                                         parser_print_warning_prefix_pos(previous_declaration->source_position);
 473                                         fprintf(stderr, "previous declaration of '%s' was here\n",
 474                                                 symbol->string);
 475                                 } else {
 476                                         parser_print_error_prefix_pos(declaration->source_position);
 477                                         if (old_storage == new_storage) {
 478                                                 fprintf(stderr, "redeclaration of '%s'\n", symbol->string);
 479                                         } else {
 480                                                 fprintf(stderr, "redeclaration of '%s' with different linkage\n", symbol->string);
 481                                         }
 482                                         parser_print_error_prefix_pos(previous_declaration->source_position);
 483                                         fprintf(stderr, "previous declaration of '%s' was here\n",
 484                                                 symbol->string);
 485                                 }
 486                         }
 487                 }
 488                 return previous_declaration;
 489         }
 490
 491         /* remember old declaration */
 492         stack_entry_t entry;
 493         entry.symbol          = symbol;
 494         entry.old_declaration = symbol->declaration;
 495         entry.namespc       = namespc;
 496         ARR_APP1(stack_entry_t, *stack_ptr, entry);
 497
 498         /* replace/add declaration into declaration list of the symbol */
 499         if(symbol->declaration == NULL) {
 500                 symbol->declaration = declaration;
 501         } else {
 502                 declaration_t *iter_last = NULL;
 503                 declaration_t *iter      = symbol->declaration;
 504                 for( ; iter != NULL; iter_last = iter, iter = iter->symbol_next) {
 505                         /* replace an entry? */
 506                         if(iter->namespc == namespc) {
 507                                 if(iter_last == NULL) {
 508                                         symbol->declaration = declaration;
 509                                 } else {
 510                                         iter_last->symbol_next = declaration;
 511                                 }
 512                                 declaration->symbol_next = iter->symbol_next;
 513                                 break;
 514                         }
 515                 }
 516                 if(iter == NULL) {
 517                         assert(iter_last->symbol_next == NULL);
 518                         iter_last->symbol_next = declaration;
 519                 }
 520         }
 521
 522         return declaration;
 523 }
 524
 525 static declaration_t *environment_push(declaration_t *declaration)
 526 {
 527         assert(declaration->source_position.input_name != NULL);
 528         return stack_push(&environment_stack, declaration, context);
 529 }
 530
 531 static declaration_t *label_push(declaration_t *declaration)
 532 {
 533         return stack_push(&label_stack, declaration, &current_function->context);
 534 }
 535
 536 /**
 537  * pops symbols from the environment stack until @p new_top is the top element
 538  */
 539 static void stack_pop_to(stack_entry_t **stack_ptr, size_t new_top)
 540 {
 541         stack_entry_t *stack = *stack_ptr;
 542         size_t         top   = ARR_LEN(stack);
 543         size_t         i;
 544
 545         assert(new_top <= top);
 546         if(new_top == top)
 547                 return;
 548
 549         for(i = top; i > new_top; --i) {
 550                 stack_entry_t *entry = & stack[i - 1];
 551
 552                 declaration_t *old_declaration = entry->old_declaration;
 553                 symbol_t      *symbol          = entry->symbol;
 554                 namespace_t    namespc         = (namespace_t)entry->namespc;
 555
 556                 /* replace/remove declaration */
 557                 declaration_t *declaration = symbol->declaration;
 558                 assert(declaration != NULL);
 559                 if(declaration->namespc == namespc) {
 560                         if(old_declaration == NULL) {
 561                                 symbol->declaration = declaration->symbol_next;
 562                         } else {
 563                                 symbol->declaration = old_declaration;
 564                         }
 565                 } else {
 566                         declaration_t *iter_last = declaration;
 567                         declaration_t *iter      = declaration->symbol_next;
 568                         for( ; iter != NULL; iter_last = iter, iter = iter->symbol_next) {
 569                                 /* replace an entry? */
 570                                 if(iter->namespc == namespc) {
 571                                         assert(iter_last != NULL);
 572                                         iter_last->symbol_next = old_declaration;
 573                                         old_declaration->symbol_next = iter->symbol_next;
 574                                         break;
 575                                 }
 576                         }
 577                         assert(iter != NULL);
 578                 }
 579         }
 580
 581         ARR_SHRINKLEN(*stack_ptr, (int) new_top);
 582 }
 583
 584 static void environment_pop_to(size_t new_top)
 585 {
 586         stack_pop_to(&environment_stack, new_top);
 587 }
 588
 589 static void label_pop_to(size_t new_top)
 590 {
 591         stack_pop_to(&label_stack, new_top);
 592 }
 593
 594
 595 static int get_rank(const type_t *type)
 596 {
 597         /* The C-standard allows promoting to int or unsigned int (see § 7.2.2
 598          * and esp. footnote 108). However we can't fold constants (yet), so we
 599          * can't decide wether unsigned int is possible, while int always works.
 600          * (unsigned int would be preferable when possible... for stuff like
 601          *  struct { enum { ... } bla : 4; } ) */
 602         if(type->type == TYPE_ENUM)
 603                 return ATOMIC_TYPE_INT;
 604
 605         assert(type->type == TYPE_ATOMIC);
 606         atomic_type_t      *atomic_type = (atomic_type_t*) type;
 607         atomic_type_type_t  atype       = atomic_type->atype;
 608         return atype;
 609 }
 610
 611 static type_t *promote_integer(type_t *type)
 612 {
 613         if(get_rank(type) < ATOMIC_TYPE_INT)
 614                 type = type_int;
 615
 616         return type;
 617 }
 618
 619 static expression_t *create_cast_expression(expression_t *expression,
 620                                             type_t *dest_type)
 621 {
 622         unary_expression_t *cast = allocate_ast_zero(sizeof(cast[0]));
 623
 624         cast->expression.type     = EXPR_UNARY;
 625         cast->type                = UNEXPR_CAST;
 626         cast->value               = expression;
 627         cast->expression.datatype = dest_type;
 628
 629         return (expression_t*) cast;
 630 }
 631
 632 static bool is_null_expression(const expression_t *const expr)
 633 {
 634         if (expr->type != EXPR_CONST) return false;
 635
 636         type_t *const type = skip_typeref(expr->datatype);
 637         if (!is_type_integer(type)) return false;
 638
 639         const const_t *const const_expr = (const const_t*)expr;
 640         return const_expr->v.int_value == 0;
 641 }
 642
 643 static expression_t *create_implicit_cast(expression_t *expression,
 644                                           type_t *dest_type)
 645 {
 646         type_t *source_type = expression->datatype;
 647
 648         if(source_type == NULL)
 649                 return expression;
 650
 651         source_type = skip_typeref(source_type);
 652         dest_type   = skip_typeref(dest_type);
 653
 654         if(source_type == dest_type)
 655                 return expression;
 656
 657         if(dest_type->type == TYPE_ATOMIC) {
 658                 if(source_type->type != TYPE_ATOMIC)
 659                         panic("casting of non-atomic types not implemented yet");
 660
 661                 if(is_type_floating(dest_type) && !is_type_scalar(source_type)) {
 662                         type_error_incompatible("can't cast types",
 663                                                 expression->source_position,
 664                                                 source_type, dest_type);
 665                         return expression;
 666                 }
 667
 668                 return create_cast_expression(expression, dest_type);
 669         }
 670         if(dest_type->type == TYPE_POINTER) {
 671                 pointer_type_t *pointer_type
 672                         = (pointer_type_t*) dest_type;
 673                 switch (source_type->type) {
 674                         case TYPE_ATOMIC:
 675                                 if (is_null_expression(expression)) {
 676                                         return create_cast_expression(expression, dest_type);
 677                                 }
 678                                 break;
 679
 680                         case TYPE_POINTER:
 681                                 if (pointers_compatible(source_type, dest_type)) {
 682                                         return create_cast_expression(expression, dest_type);
 683                                 }
 684                                 break;
 685
 686                         case TYPE_ARRAY: {
 687                                 array_type_t *const array_type = (array_type_t*) source_type;
 688                                 if (types_compatible(array_type->element_type,
 689                                                                                                                  pointer_type->points_to)) {
 690                                         return create_cast_expression(expression, dest_type);
 691                                 }
 692                                 break;
 693                         }
 694
 695                         default:
 696                                 panic("casting of non-atomic types not implemented yet");
 697                 }
 698
 699                 type_error_incompatible("can't implicitly cast types",
 700                                         expression->source_position,
 701                                         source_type, dest_type);
 702                 return expression;
 703         }
 704
 705         panic("casting of non-atomic types not implemented yet");
 706 }
 707
 708 static void semantic_assign(type_t *orig_type_left, expression_t **right,
 709                             const char *context)
 710 {
 711         type_t *orig_type_right = (*right)->datatype;
 712
 713         if(orig_type_right == NULL)
 714                 return;
 715
 716         type_t *const type_left  = skip_typeref(orig_type_left);
 717         type_t *const type_right = skip_typeref(orig_type_right);
 718
 719         if (type_left == type_right) {
 720                 return;
 721         }
 722
 723         if ((is_type_arithmetic(type_left) && is_type_arithmetic(type_right)) ||
 724             (type_left->type == TYPE_POINTER && is_null_expression(*right)) ||
 725             (type_left->type == TYPE_POINTER && type_right->type == TYPE_POINTER)) {
 726                 *right = create_implicit_cast(*right, type_left);
 727                 return;
 728         }
 729
 730         if (type_left->type == TYPE_POINTER) {
 731                 switch (type_right->type) {
 732                         case TYPE_FUNCTION: {
 733                                 pointer_type_t *const ptr_type = (pointer_type_t*)type_left;
 734                                 if (ptr_type->points_to == type_right) {
 735                                         return;
 736                                 }
 737                                 break;
 738                         }
 739
 740                         case TYPE_ARRAY: {
 741                                 pointer_type_t *const ptr_type = (pointer_type_t*)type_left;
 742                                 array_type_t   *const arr_type = (array_type_t*)type_right;
 743                                 if (ptr_type->points_to == arr_type->element_type) {
 744                                         return;
 745                                 }
 746                                 break;
 747                         }
 748
 749                         default: break;
 750                 }
 751         }
 752
 753         /* TODO: improve error message */
 754         parser_print_error_prefix();
 755         fprintf(stderr, "incompatible types in %s\n", context);
 756         parser_print_error_prefix();
 757         print_type_quoted(type_left);
 758         fputs(" <- ", stderr);
 759         print_type_quoted(type_right);
 760         fputs("\n", stderr);
 761 }
 762
 763 static expression_t *parse_constant_expression(void)
 764 {
 765         /* start parsing at precedence 7 (conditional expression) */
 766         return parse_sub_expression(7);
 767 }
 768
 769 static expression_t *parse_assignment_expression(void)
 770 {
 771         /* start parsing at precedence 2 (assignment expression) */
 772         return parse_sub_expression(2);
 773 }
 774
 775 typedef struct declaration_specifiers_t  declaration_specifiers_t;
 776 struct declaration_specifiers_t {
 777         storage_class_t  storage_class;
 778         bool             is_inline;
 779         type_t          *type;
 780 };
 781
 782 static void parse_compound_type_entries(void);
 783 static declaration_t *parse_declarator(
 784                 const declaration_specifiers_t *specifiers, type_t *type,
 785                 bool may_be_abstract);
 786 static declaration_t *record_declaration(declaration_t *declaration);
 787
 788 static const char *parse_string_literals(void)
 789 {
 790         assert(token.type == T_STRING_LITERAL);
 791         const char *result = token.v.string;
 792
 793         next_token();
 794
 795         while(token.type == T_STRING_LITERAL) {
 796                 result = concat_strings(result, token.v.string);
 797                 next_token();
 798         }
 799
 800         return result;
 801 }
 802
 803 static void parse_attributes(void)
 804 {
 805         while(true) {
 806                 switch(token.type) {
 807                 case T___attribute__:
 808                         next_token();
 809
 810                         expect_void('(');
 811                         int depth = 1;
 812                         while(depth > 0) {
 813                                 switch(token.type) {
 814                                 case T_EOF:
 815                                         parse_error("EOF while parsing attribute");
 816                                         break;
 817                                 case '(':
 818                                         next_token();
 819                                         depth++;
 820                                         break;
 821                                 case ')':
 822                                         next_token();
 823                                         depth--;
 824                                         break;
 825                                 default:
 826                                         next_token();
 827                                 }
 828                         }
 829                         break;
 830                 case T_asm:
 831                         next_token();
 832                         expect_void('(');
 833                         if(token.type != T_STRING_LITERAL) {
 834                                 parse_error_expected("while parsing assembler attribute",
 835                                                      T_STRING_LITERAL);
 836                                 eat_brace();
 837                                 break;
 838                         } else {
 839                                 parse_string_literals();
 840                         }
 841                         expect_void(')');
 842                         break;
 843                 default:
 844                         goto attributes_finished;
 845                 }
 846         }
 847
 848 attributes_finished:
 849         ;
 850 }
 851
 852 #if 0
 853 static designator_t *parse_designation(void)
 854 {
 855         if(token.type != '[' && token.type != '.')
 856                 return NULL;
 857
 858         designator_t *result = NULL;
 859         designator_t *last   = NULL;
 860
 861         while(1) {
 862                 designator_t *designator;
 863                 switch(token.type) {
 864                 case '[':
 865                         designator = allocate_ast_zero(sizeof(designator[0]));
 866                         next_token();
 867                         designator->array_access = parse_constant_expression();
 868                         expect(']');
 869                         break;
 870                 case '.':
 871                         designator = allocate_ast_zero(sizeof(designator[0]));
 872                         next_token();
 873                         if(token.type != T_IDENTIFIER) {
 874                                 parse_error_expected("while parsing designator",
 875                                                      T_IDENTIFIER, 0);
 876                                 return NULL;
 877                         }
 878                         designator->symbol = token.v.symbol;
 879                         next_token();
 880                         break;
 881                 default:
 882                         expect('=');
 883                         return result;
 884                 }
 885
 886                 assert(designator != NULL);
 887                 if(last != NULL) {
 888                         last->next = designator;
 889                 } else {
 890                         result = designator;
 891                 }
 892                 last = designator;
 893         }
 894 }
 895 #endif
 896
 897 static initializer_t *initializer_from_expression(type_t *type,
 898                                                   expression_t *expression)
 899 {
 900         initializer_value_t *result = allocate_ast_zero(sizeof(result[0]));
 901
 902         /* TODO check that expression is a constant expression */
 903
 904         /* § 6.7.8.14/15 char array may be initialized by string literals */
 905         if(type->type == TYPE_ARRAY && expression->type == EXPR_STRING_LITERAL) {
 906                 array_type_t *array_type   = (array_type_t*) type;
 907                 type_t       *element_type = array_type->element_type;
 908
 909                 if(element_type->type == TYPE_ATOMIC) {
 910                         atomic_type_t      *atomic_type = (atomic_type_t*) element_type;
 911                         atomic_type_type_t  atype       = atomic_type->atype;
 912
 913                         /* TODO handle wide strings */
 914                         if(atype == ATOMIC_TYPE_CHAR
 915                                         || atype == ATOMIC_TYPE_SCHAR
 916                                         || atype == ATOMIC_TYPE_UCHAR) {
 917                                 /* it's fine TODO: check for length of string array... */
 918                                 goto initializer_from_expression_finished;
 919                         }
 920                 }
 921         }
 922
 923         semantic_assign(type, &expression, "initializer");
 924
 925 initializer_from_expression_finished:
 926         result->initializer.type = INITIALIZER_VALUE;
 927         result->value            = expression;
 928
 929         return (initializer_t*) result;
 930 }
 931
 932 static initializer_t *parse_sub_initializer(type_t *type,
 933                                             expression_t *expression,
 934                                             type_t *expression_type);
 935
 936 static initializer_t *parse_sub_initializer_elem(type_t *type)
 937 {
 938         if(token.type == '{') {
 939                 return parse_sub_initializer(type, NULL, NULL);
 940         }
 941
 942         expression_t *expression      = parse_assignment_expression();
 943         type_t       *expression_type = skip_typeref(expression->datatype);
 944
 945         return parse_sub_initializer(type, expression, expression_type);
 946 }
 947
 948 static bool had_initializer_brace_warning;
 949
 950 static initializer_t *parse_sub_initializer(type_t *type,
 951                                             expression_t *expression,
 952                                             type_t *expression_type)
 953 {
 954         if(is_type_scalar(type)) {
 955                 /* there might be extra {} hierarchies */
 956                 if(token.type == '{') {
 957                         next_token();
 958                         if(!had_initializer_brace_warning) {
 959                                 parse_warning("braces around scalar initializer");
 960                                 had_initializer_brace_warning = true;
 961                         }
 962                         initializer_t *result = parse_sub_initializer(type, NULL, NULL);
 963                         if(token.type == ',') {
 964                                 next_token();
 965                                 /* TODO: warn about excessive elements */
 966                         }
 967                         expect_block('}');
 968                         return result;
 969                 }
 970
 971                 if(expression == NULL) {
 972                         expression = parse_assignment_expression();
 973                 }
 974                 return initializer_from_expression(type, expression);
 975         }
 976
 977         /* TODO: ignore qualifiers, comparing pointers is probably
 978          * not correct */
 979         if(expression != NULL && expression_type == type) {
 980                 initializer_value_t *result = allocate_ast_zero(sizeof(result[0]));
 981                 result->initializer.type    = INITIALIZER_VALUE;
 982
 983                 if(type != NULL) {
 984                         semantic_assign(type, &expression, "initializer");
 985                 }
 986                 result->value = expression;
 987
 988                 return (initializer_t*) result;
 989         }
 990
 991         bool read_paren = false;
 992         if(token.type == '{') {
 993                 next_token();
 994                 read_paren = true;
 995         }
 996
 997         /* descend into subtype */
 998         initializer_t  *result = NULL;
 999         initializer_t **elems;
1000         if(type->type == TYPE_ARRAY) {
1001                 array_type_t *array_type   = (array_type_t*) type;
1002                 type_t       *element_type = array_type->element_type;
1003                 element_type               = skip_typeref(element_type);
1004
1005                 initializer_t *sub;
1006                 had_initializer_brace_warning = false;
1007                 if(expression == NULL) {
1008                         sub = parse_sub_initializer_elem(element_type);
1009                 } else {
1010                         sub = parse_sub_initializer(element_type, expression,
1011                                                     expression_type);
1012                 }
1013
1014                 /* didn't match the subtypes -> try the parent type */
1015                 if(sub == NULL) {
1016                         assert(!read_paren);
1017                         return NULL;
1018                 }
1019
1020                 elems = NEW_ARR_F(initializer_t*, 0);
1021                 ARR_APP1(initializer_t*, elems, sub);
1022
1023                 while(true) {
1024                         if(token.type == '}')
1025                                 break;
1026                         expect_block(',');
1027                         if(token.type == '}')
1028                                 break;
1029
1030                         initializer_t *sub
1031                                 = parse_sub_initializer(element_type, NULL, NULL);
1032                         if(sub == NULL) {
1033                                 /* TODO error, do nicer cleanup */
1034                                 parse_error("member initializer didn't match");
1035                                 DEL_ARR_F(elems);
1036                                 return NULL;
1037                         }
1038                         ARR_APP1(initializer_t*, elems, sub);
1039                 }
1040         } else {
1041                 assert(type->type == TYPE_COMPOUND_STRUCT
1042                                 || type->type == TYPE_COMPOUND_UNION);
1043                 compound_type_t *compound_type = (compound_type_t*) type;
1044                 context_t       *context       = & compound_type->declaration->context;
1045
1046                 declaration_t *first = context->declarations;
1047                 if(first == NULL)
1048                         return NULL;
1049                 type_t *first_type = first->type;
1050                 first_type         = skip_typeref(first_type);
1051
1052                 initializer_t *sub;
1053                 had_initializer_brace_warning = false;
1054                 if(expression == NULL) {
1055                         sub = parse_sub_initializer_elem(first_type);
1056                 } else {
1057                         sub = parse_sub_initializer(first_type, expression,expression_type);
1058                 }
1059
1060                 /* didn't match the subtypes -> try our parent type */
1061                 if(sub == NULL) {
1062                         assert(!read_paren);
1063                         return NULL;
1064                 }
1065
1066                 elems = NEW_ARR_F(initializer_t*, 0);
1067                 ARR_APP1(initializer_t*, elems, sub);
1068
1069                 declaration_t *iter  = first->next;
1070                 for( ; iter != NULL; iter = iter->next) {
1071                         if(iter->symbol == NULL)
1072                                 continue;
1073                         if(iter->namespc != NAMESPACE_NORMAL)
1074                                 continue;
1075
1076                         if(token.type == '}')
1077                                 break;
1078                         expect_block(',');
1079
1080                         type_t *iter_type = iter->type;
1081                         iter_type         = skip_typeref(iter_type);
1082
1083                         initializer_t *sub = parse_sub_initializer(iter_type, NULL, NULL);
1084                         if(sub == NULL) {
1085                                 /* TODO error, do nicer cleanup*/
1086                                 parse_error("member initializer didn't match");
1087                                 DEL_ARR_F(elems);
1088                                 return NULL;
1089                         }
1090                         ARR_APP1(initializer_t*, elems, sub);
1091                 }
1092         }
1093
1094         int    len        = ARR_LEN(elems);
1095         size_t elems_size = sizeof(initializer_t*) * len;
1096
1097         initializer_list_t *init = allocate_ast_zero(sizeof(init[0]) + elems_size);
1098
1099         init->initializer.type = INITIALIZER_LIST;
1100         init->len              = len;
1101         memcpy(init->initializers, elems, elems_size);
1102         DEL_ARR_F(elems);
1103
1104         result = (initializer_t*) init;
1105
1106         if(read_paren) {
1107                 if(token.type == ',')
1108                         next_token();
1109                 expect('}');
1110         }
1111         return result;
1112 }
1113
1114 static initializer_t *parse_initializer(type_t *type)
1115 {
1116         initializer_t *result;
1117
1118         type = skip_typeref(type);
1119
1120         if(token.type != '{') {
1121                 expression_t *expression = parse_assignment_expression();
1122                 return initializer_from_expression(type, expression);
1123         }
1124
1125         if(is_type_scalar(type)) {
1126                 /* § 6.7.8.11 */
1127                 eat('{');
1128
1129                 expression_t *expression = parse_assignment_expression();
1130                 result = initializer_from_expression(type, expression);
1131
1132                 if(token.type == ',')
1133                         next_token();
1134
1135                 expect('}');
1136                 return result;
1137         } else {
1138                 result = parse_sub_initializer(type, NULL, NULL);
1139         }
1140
1141         return result;
1142 }
1143
1144
1145
1146 static declaration_t *parse_compound_type_specifier(bool is_struct)
1147 {
1148         if(is_struct) {
1149                 eat(T_struct);
1150         } else {
1151                 eat(T_union);
1152         }
1153
1154         symbol_t      *symbol      = NULL;
1155         declaration_t *declaration = NULL;
1156
1157         if (token.type == T___attribute__) {
1158                 /* TODO */
1159                 parse_attributes();
1160         }
1161
1162         if(token.type == T_IDENTIFIER) {
1163                 symbol = token.v.symbol;
1164                 next_token();
1165
1166                 if(is_struct) {
1167                         declaration = get_declaration(symbol, NAMESPACE_STRUCT);
1168                 } else {
1169                         declaration = get_declaration(symbol, NAMESPACE_UNION);
1170                 }
1171         } else if(token.type != '{') {
1172                 if(is_struct) {
1173                         parse_error_expected("while parsing struct type specifier",
1174                                              T_IDENTIFIER, '{', 0);
1175                 } else {
1176                         parse_error_expected("while parsing union type specifier",
1177                                              T_IDENTIFIER, '{', 0);
1178                 }
1179
1180                 return NULL;
1181         }
1182
1183         if(declaration == NULL) {
1184                 declaration = allocate_type_zero(sizeof(declaration[0]));
1185
1186                 if(is_struct) {
1187                         declaration->namespc = NAMESPACE_STRUCT;
1188                 } else {
1189                         declaration->namespc = NAMESPACE_UNION;
1190                 }
1191                 declaration->source_position = token.source_position;
1192                 declaration->symbol          = symbol;
1193                 record_declaration(declaration);
1194         }
1195
1196         if(token.type == '{') {
1197                 if(declaration->init.is_defined) {
1198                         assert(symbol != NULL);
1199                         parser_print_error_prefix();
1200                         fprintf(stderr, "multiple definition of %s %s\n",
1201                                         is_struct ? "struct" : "union", symbol->string);
1202                         declaration->context.declarations = NULL;
1203                 }
1204                 declaration->init.is_defined = true;
1205
1206                 int         top          = environment_top();
1207                 context_t  *last_context = context;
1208                 set_context(& declaration->context);
1209
1210                 parse_compound_type_entries();
1211                 parse_attributes();
1212
1213                 assert(context == & declaration->context);
1214                 set_context(last_context);
1215                 environment_pop_to(top);
1216         }
1217
1218         return declaration;
1219 }
1220
1221 static void parse_enum_entries(type_t *enum_type)
1222 {
1223         eat('{');
1224
1225         if(token.type == '}') {
1226                 next_token();
1227                 parse_error("empty enum not allowed");
1228                 return;
1229         }
1230
1231         do {
1232                 declaration_t *entry = allocate_ast_zero(sizeof(entry[0]));
1233
1234                 if(token.type != T_IDENTIFIER) {
1235                         parse_error_expected("while parsing enum entry", T_IDENTIFIER, 0);
1236                         eat_block();
1237                         return;
1238                 }
1239                 entry->storage_class   = STORAGE_CLASS_ENUM_ENTRY;
1240                 entry->type            = enum_type;
1241                 entry->symbol          = token.v.symbol;
1242                 entry->source_position = token.source_position;
1243                 next_token();
1244
1245                 if(token.type == '=') {
1246                         next_token();
1247                         entry->init.enum_value = parse_constant_expression();
1248
1249                         /* TODO semantic */
1250                 }
1251
1252                 record_declaration(entry);
1253
1254                 if(token.type != ',')
1255                         break;
1256                 next_token();
1257         } while(token.type != '}');
1258
1259         expect_void('}');
1260 }
1261
1262 static declaration_t *parse_enum_specifier(void)
1263 {
1264         eat(T_enum);
1265
1266         declaration_t *declaration;
1267         symbol_t      *symbol;
1268
1269         if(token.type == T_IDENTIFIER) {
1270                 symbol = token.v.symbol;
1271                 next_token();
1272
1273                 declaration = get_declaration(symbol, NAMESPACE_ENUM);
1274         } else if(token.type != '{') {
1275                 parse_error_expected("while parsing enum type specifier",
1276                                      T_IDENTIFIER, '{', 0);
1277                 return NULL;
1278         } else {
1279                 declaration = NULL;
1280                 symbol      = NULL;
1281         }
1282
1283         if(declaration == NULL) {
1284                 declaration = allocate_type_zero(sizeof(declaration[0]));
1285
1286                 declaration->namespc       = NAMESPACE_ENUM;
1287                 declaration->source_position = token.source_position;
1288                 declaration->symbol          = symbol;
1289         }
1290
1291         if(token.type == '{') {
1292                 if(declaration->init.is_defined) {
1293                         parser_print_error_prefix();
1294                         fprintf(stderr, "multiple definitions of enum %s\n",
1295                                 symbol->string);
1296                 }
1297                 record_declaration(declaration);
1298                 declaration->init.is_defined = 1;
1299
1300                 parse_enum_entries(NULL);
1301                 parse_attributes();
1302         }
1303
1304         return declaration;
1305 }
1306
1307 /**
1308  * if a symbol is a typedef to another type, return true
1309  */
1310 static bool is_typedef_symbol(symbol_t *symbol)
1311 {
1312         const declaration_t *const declaration =
1313                 get_declaration(symbol, NAMESPACE_NORMAL);
1314         return
1315                 declaration != NULL &&
1316                 declaration->storage_class == STORAGE_CLASS_TYPEDEF;
1317 }
1318
1319 static type_t *parse_typeof(void)
1320 {
1321         eat(T___typeof__);
1322
1323         type_t *type;
1324
1325         expect('(');
1326
1327         expression_t *expression  = NULL;
1328
1329 restart:
1330         switch(token.type) {
1331         case T___extension__:
1332                 /* this can be a prefix to a typename or an expression */
1333                 /* we simply eat it now. */
1334                 do {
1335                         next_token();
1336                 } while(token.type == T___extension__);
1337                 goto restart;
1338
1339         case T_IDENTIFIER:
1340                 if(is_typedef_symbol(token.v.symbol)) {
1341                         type = parse_typename();
1342                 } else {
1343                         expression = parse_expression();
1344                         type       = expression->datatype;
1345                 }
1346                 break;
1347
1348         TYPENAME_START
1349                 type = parse_typename();
1350                 break;
1351
1352         default:
1353                 expression = parse_expression();
1354                 type       = expression->datatype;
1355                 break;
1356         }
1357
1358         expect(')');
1359
1360         typeof_type_t *typeof = allocate_type_zero(sizeof(typeof[0]));
1361         typeof->type.type     = TYPE_TYPEOF;
1362         typeof->expression    = expression;
1363         typeof->typeof_type   = type;
1364
1365         return (type_t*) typeof;
1366 }
1367
1368 typedef enum {
1369         SPECIFIER_SIGNED    = 1 << 0,
1370         SPECIFIER_UNSIGNED  = 1 << 1,
1371         SPECIFIER_LONG      = 1 << 2,
1372         SPECIFIER_INT       = 1 << 3,
1373         SPECIFIER_DOUBLE    = 1 << 4,
1374         SPECIFIER_CHAR      = 1 << 5,
1375         SPECIFIER_SHORT     = 1 << 6,
1376         SPECIFIER_LONG_LONG = 1 << 7,
1377         SPECIFIER_FLOAT     = 1 << 8,
1378         SPECIFIER_BOOL      = 1 << 9,
1379         SPECIFIER_VOID      = 1 << 10,
1380 #ifdef PROVIDE_COMPLEX
1381         SPECIFIER_COMPLEX   = 1 << 11,
1382         SPECIFIER_IMAGINARY = 1 << 12,
1383 #endif
1384 } specifiers_t;
1385
1386 static type_t *create_builtin_type(symbol_t *symbol)
1387 {
1388         builtin_type_t *type = allocate_type_zero(sizeof(type[0]));
1389         type->type.type      = TYPE_BUILTIN;
1390         type->symbol         = symbol;
1391         /* TODO... */
1392         type->real_type      = type_int;
1393
1394         return (type_t*) type;
1395 }
1396
1397 static type_t *get_typedef_type(symbol_t *symbol)
1398 {
1399         declaration_t *declaration = get_declaration(symbol, NAMESPACE_NORMAL);
1400         if(declaration == NULL
1401                         || declaration->storage_class != STORAGE_CLASS_TYPEDEF)
1402                 return NULL;
1403
1404         typedef_type_t *typedef_type = allocate_type_zero(sizeof(typedef_type[0]));
1405         typedef_type->type.type    = TYPE_TYPEDEF;
1406         typedef_type->declaration  = declaration;
1407
1408         return (type_t*) typedef_type;
1409 }
1410
1411 static void parse_declaration_specifiers(declaration_specifiers_t *specifiers)
1412 {
1413         type_t        *type            = NULL;
1414         unsigned       type_qualifiers = 0;
1415         unsigned       type_specifiers = 0;
1416         int            newtype         = 0;
1417
1418         while(true) {
1419                 switch(token.type) {
1420
1421                 /* storage class */
1422 #define MATCH_STORAGE_CLASS(token, class)                                \
1423                 case token:                                                      \
1424                         if(specifiers->storage_class != STORAGE_CLASS_NONE) {        \
1425                                 parse_error("multiple storage classes in declaration "   \
1426                                             "specifiers");                               \
1427                         }                                                            \
1428                         specifiers->storage_class = class;                           \
1429                         next_token();                                                \
1430                         break;
1431
1432                 MATCH_STORAGE_CLASS(T_typedef,  STORAGE_CLASS_TYPEDEF)
1433                 MATCH_STORAGE_CLASS(T_extern,   STORAGE_CLASS_EXTERN)
1434                 MATCH_STORAGE_CLASS(T_static,   STORAGE_CLASS_STATIC)
1435                 MATCH_STORAGE_CLASS(T_auto,     STORAGE_CLASS_AUTO)
1436                 MATCH_STORAGE_CLASS(T_register, STORAGE_CLASS_REGISTER)
1437
1438                 /* type qualifiers */
1439 #define MATCH_TYPE_QUALIFIER(token, qualifier)                          \
1440                 case token:                                                     \
1441                         type_qualifiers |= qualifier;                               \
1442                         next_token();                                               \
1443                         break;
1444
1445                 MATCH_TYPE_QUALIFIER(T_const,    TYPE_QUALIFIER_CONST);
1446                 MATCH_TYPE_QUALIFIER(T_restrict, TYPE_QUALIFIER_RESTRICT);
1447                 MATCH_TYPE_QUALIFIER(T_volatile, TYPE_QUALIFIER_VOLATILE);
1448
1449                 case T___extension__:
1450                         /* TODO */
1451                         next_token();
1452                         break;
1453
1454                 /* type specifiers */
1455 #define MATCH_SPECIFIER(token, specifier, name)                         \
1456                 case token:                                                     \
1457                         next_token();                                               \
1458                         if(type_specifiers & specifier) {                           \
1459                                 parse_error("multiple " name " type specifiers given"); \
1460                         } else {                                                    \
1461                                 type_specifiers |= specifier;                           \
1462                         }                                                           \
1463                         break;
1464
1465                 MATCH_SPECIFIER(T_void,       SPECIFIER_VOID,      "void")
1466                 MATCH_SPECIFIER(T_char,       SPECIFIER_CHAR,      "char")
1467                 MATCH_SPECIFIER(T_short,      SPECIFIER_SHORT,     "short")
1468                 MATCH_SPECIFIER(T_int,        SPECIFIER_INT,       "int")
1469                 MATCH_SPECIFIER(T_float,      SPECIFIER_FLOAT,     "float")
1470                 MATCH_SPECIFIER(T_double,     SPECIFIER_DOUBLE,    "double")
1471                 MATCH_SPECIFIER(T_signed,     SPECIFIER_SIGNED,    "signed")
1472                 MATCH_SPECIFIER(T_unsigned,   SPECIFIER_UNSIGNED,  "unsigned")
1473                 MATCH_SPECIFIER(T__Bool,      SPECIFIER_BOOL,      "_Bool")
1474 #ifdef PROVIDE_COMPLEX
1475                 MATCH_SPECIFIER(T__Complex,   SPECIFIER_COMPLEX,   "_Complex")
1476                 MATCH_SPECIFIER(T__Imaginary, SPECIFIER_IMAGINARY, "_Imaginary")
1477 #endif
1478                 case T_inline:
1479                         next_token();
1480                         specifiers->is_inline = true;
1481                         break;
1482
1483                 case T_long:
1484                         next_token();
1485                         if(type_specifiers & SPECIFIER_LONG_LONG) {
1486                                 parse_error("multiple type specifiers given");
1487                         } else if(type_specifiers & SPECIFIER_LONG) {
1488                                 type_specifiers |= SPECIFIER_LONG_LONG;
1489                         } else {
1490                                 type_specifiers |= SPECIFIER_LONG;
1491                         }
1492                         break;
1493
1494                 /* TODO: if type != NULL for the following rules should issue
1495                  * an error */
1496                 case T_struct: {
1497                         compound_type_t *compound_type
1498                                 = allocate_type_zero(sizeof(compound_type[0]));
1499                         compound_type->type.type = TYPE_COMPOUND_STRUCT;
1500                         compound_type->declaration = parse_compound_type_specifier(true);
1501
1502                         type = (type_t*) compound_type;
1503                         break;
1504                 }
1505                 case T_union: {
1506                         compound_type_t *compound_type
1507                                 = allocate_type_zero(sizeof(compound_type[0]));
1508                         compound_type->type.type = TYPE_COMPOUND_UNION;
1509                         compound_type->declaration = parse_compound_type_specifier(false);
1510
1511                         type = (type_t*) compound_type;
1512                         break;
1513                 }
1514                 case T_enum: {
1515                         enum_type_t *enum_type = allocate_type_zero(sizeof(enum_type[0]));
1516                         enum_type->type.type   = TYPE_ENUM;
1517                         enum_type->declaration = parse_enum_specifier();
1518
1519                         type = (type_t*) enum_type;
1520                         break;
1521                 }
1522                 case T___typeof__:
1523                         type = parse_typeof();
1524                         break;
1525                 case T___builtin_va_list:
1526                         type = create_builtin_type(token.v.symbol);
1527                         next_token();
1528                         break;
1529
1530                 case T___attribute__:
1531                         /* TODO */
1532                         parse_attributes();
1533                         break;
1534
1535                 case T_IDENTIFIER: {
1536                         type_t *typedef_type = get_typedef_type(token.v.symbol);
1537
1538                         if(typedef_type == NULL)
1539                                 goto finish_specifiers;
1540
1541                         next_token();
1542                         type = typedef_type;
1543                         break;
1544                 }
1545
1546                 /* function specifier */
1547                 default:
1548                         goto finish_specifiers;
1549                 }
1550         }
1551
1552 finish_specifiers:
1553
1554         if(type == NULL) {
1555                 atomic_type_type_t atomic_type;
1556
1557                 /* match valid basic types */
1558                 switch(type_specifiers) {
1559                 case SPECIFIER_VOID:
1560                         atomic_type = ATOMIC_TYPE_VOID;
1561                         break;
1562                 case SPECIFIER_CHAR:
1563                         atomic_type = ATOMIC_TYPE_CHAR;
1564                         break;
1565                 case SPECIFIER_SIGNED | SPECIFIER_CHAR:
1566                         atomic_type = ATOMIC_TYPE_SCHAR;
1567                         break;
1568                 case SPECIFIER_UNSIGNED | SPECIFIER_CHAR:
1569                         atomic_type = ATOMIC_TYPE_UCHAR;
1570                         break;
1571                 case SPECIFIER_SHORT:
1572                 case SPECIFIER_SIGNED | SPECIFIER_SHORT:
1573                 case SPECIFIER_SHORT | SPECIFIER_INT:
1574                 case SPECIFIER_SIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
1575                         atomic_type = ATOMIC_TYPE_SHORT;
1576                         break;
1577                 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT:
1578                 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
1579                         atomic_type = ATOMIC_TYPE_USHORT;
1580                         break;
1581                 case SPECIFIER_INT:
1582                 case SPECIFIER_SIGNED:
1583                 case SPECIFIER_SIGNED | SPECIFIER_INT:
1584                         atomic_type = ATOMIC_TYPE_INT;
1585                         break;
1586                 case SPECIFIER_UNSIGNED:
1587                 case SPECIFIER_UNSIGNED | SPECIFIER_INT:
1588                         atomic_type = ATOMIC_TYPE_UINT;
1589                         break;
1590                 case SPECIFIER_LONG:
1591                 case SPECIFIER_SIGNED | SPECIFIER_LONG:
1592                 case SPECIFIER_LONG | SPECIFIER_INT:
1593                 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_INT:
1594                         atomic_type = ATOMIC_TYPE_LONG;
1595                         break;
1596                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG:
1597                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_INT:
1598                         atomic_type = ATOMIC_TYPE_ULONG;
1599                         break;
1600                 case SPECIFIER_LONG | SPECIFIER_LONG_LONG:
1601                 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG:
1602                 case SPECIFIER_LONG | SPECIFIER_LONG_LONG | SPECIFIER_INT:
1603                 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG
1604                         | SPECIFIER_INT:
1605                         atomic_type = ATOMIC_TYPE_LONGLONG;
1606                         break;
1607                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG:
1608                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_LONG_LONG
1609                         | SPECIFIER_INT:
1610                         atomic_type = ATOMIC_TYPE_ULONGLONG;
1611                         break;
1612                 case SPECIFIER_FLOAT:
1613                         atomic_type = ATOMIC_TYPE_FLOAT;
1614                         break;
1615                 case SPECIFIER_DOUBLE:
1616                         atomic_type = ATOMIC_TYPE_DOUBLE;
1617                         break;
1618                 case SPECIFIER_LONG | SPECIFIER_DOUBLE:
1619                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE;
1620                         break;
1621                 case SPECIFIER_BOOL:
1622                         atomic_type = ATOMIC_TYPE_BOOL;
1623                         break;
1624 #ifdef PROVIDE_COMPLEX
1625                 case SPECIFIER_FLOAT | SPECIFIER_COMPLEX:
1626                         atomic_type = ATOMIC_TYPE_FLOAT_COMPLEX;
1627                         break;
1628                 case SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
1629                         atomic_type = ATOMIC_TYPE_DOUBLE_COMPLEX;
1630                         break;
1631                 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
1632                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE_COMPLEX;
1633                         break;
1634                 case SPECIFIER_FLOAT | SPECIFIER_IMAGINARY:
1635                         atomic_type = ATOMIC_TYPE_FLOAT_IMAGINARY;
1636                         break;
1637                 case SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
1638                         atomic_type = ATOMIC_TYPE_DOUBLE_IMAGINARY;
1639                         break;
1640                 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
1641                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY;
1642                         break;
1643 #endif
1644                 default:
1645                         /* invalid specifier combination, give an error message */
1646                         if(type_specifiers == 0) {
1647 #ifndef STRICT_C99
1648                                 parse_warning("no type specifiers in declaration (using int)");
1649                                 atomic_type = ATOMIC_TYPE_INT;
1650                                 break;
1651 #else
1652                                 parse_error("no type specifiers given in declaration");
1653 #endif
1654                         } else if((type_specifiers & SPECIFIER_SIGNED) &&
1655                                   (type_specifiers & SPECIFIER_UNSIGNED)) {
1656                                 parse_error("signed and unsigned specifiers gives");
1657                         } else if(type_specifiers & (SPECIFIER_SIGNED | SPECIFIER_UNSIGNED)) {
1658                                 parse_error("only integer types can be signed or unsigned");
1659                         } else {
1660                                 parse_error("multiple datatypes in declaration");
1661                         }
1662                         atomic_type = ATOMIC_TYPE_INVALID;
1663                 }
1664
1665                 atomic_type_t *atype = allocate_type_zero(sizeof(atype[0]));
1666                 atype->type.type     = TYPE_ATOMIC;
1667                 atype->atype         = atomic_type;
1668                 newtype              = 1;
1669
1670                 type = (type_t*) atype;
1671         } else {
1672                 if(type_specifiers != 0) {
1673                         parse_error("multiple datatypes in declaration");
1674                 }
1675         }
1676
1677         type->qualifiers = (type_qualifier_t)type_qualifiers;
1678
1679         type_t *result = typehash_insert(type);
1680         if(newtype && result != (type_t*) type) {
1681                 free_type(type);
1682         }
1683
1684         specifiers->type = result;
1685 }
1686
1687 static unsigned parse_type_qualifiers(void)
1688 {
1689         unsigned type_qualifiers = TYPE_QUALIFIER_NONE;
1690
1691         while(true) {
1692                 switch(token.type) {
1693                 /* type qualifiers */
1694                 MATCH_TYPE_QUALIFIER(T_const,    TYPE_QUALIFIER_CONST);
1695                 MATCH_TYPE_QUALIFIER(T_restrict, TYPE_QUALIFIER_RESTRICT);
1696                 MATCH_TYPE_QUALIFIER(T_volatile, TYPE_QUALIFIER_VOLATILE);
1697
1698                 default:
1699                         return type_qualifiers;
1700                 }
1701         }
1702 }
1703
1704 static void parse_identifier_list(void)
1705 {
1706         while(true) {
1707                 if(token.type != T_IDENTIFIER) {
1708                         parse_error_expected("while parsing parameter identifier list",
1709                                              T_IDENTIFIER, 0);
1710                         return;
1711                 }
1712                 next_token();
1713                 if(token.type != ',')
1714                         break;
1715                 next_token();
1716         }
1717 }
1718
1719 static declaration_t *parse_parameter(void)
1720 {
1721         declaration_specifiers_t specifiers;
1722         memset(&specifiers, 0, sizeof(specifiers));
1723
1724         parse_declaration_specifiers(&specifiers);
1725
1726         declaration_t *declaration
1727                 = parse_declarator(&specifiers, specifiers.type, true);
1728
1729         /* TODO check declaration constraints for parameters */
1730         if(declaration->storage_class == STORAGE_CLASS_TYPEDEF) {
1731                 parse_error("typedef not allowed in parameter list");
1732         }
1733
1734         /* Array as last part of a paramter type is just syntactic sugar.  Turn it
1735          * into a pointer */
1736         if (declaration->type->type == TYPE_ARRAY) {
1737                 const array_type_t *const arr_type =
1738                         (const array_type_t*)declaration->type;
1739                 declaration->type =
1740                         make_pointer_type(arr_type->element_type, TYPE_QUALIFIER_NONE);
1741         }
1742
1743         return declaration;
1744 }
1745
1746 static declaration_t *parse_parameters(function_type_t *type)
1747 {
1748         if(token.type == T_IDENTIFIER) {
1749                 symbol_t      *symbol = token.v.symbol;
1750                 if(!is_typedef_symbol(symbol)) {
1751                         /* TODO: K&R style C parameters */
1752                         parse_identifier_list();
1753                         return NULL;
1754                 }
1755         }
1756
1757         if(token.type == ')') {
1758                 type->unspecified_parameters = 1;
1759                 return NULL;
1760         }
1761         if(token.type == T_void && look_ahead(1)->type == ')') {
1762                 next_token();
1763                 return NULL;
1764         }
1765
1766         declaration_t        *declarations = NULL;
1767         declaration_t        *declaration;
1768         declaration_t        *last_declaration = NULL;
1769         function_parameter_t *parameter;
1770         function_parameter_t *last_parameter = NULL;
1771
1772         while(true) {
1773                 switch(token.type) {
1774                 case T_DOTDOTDOT:
1775                         next_token();
1776                         type->variadic = 1;
1777                         return declarations;
1778
1779                 case T_IDENTIFIER:
1780                 case T___extension__:
1781                 DECLARATION_START
1782                         declaration = parse_parameter();
1783
1784                         parameter       = allocate_type_zero(sizeof(parameter[0]));
1785                         parameter->type = declaration->type;
1786
1787                         if(last_parameter != NULL) {
1788                                 last_declaration->next = declaration;
1789                                 last_parameter->next   = parameter;
1790                         } else {
1791                                 type->parameters = parameter;
1792                                 declarations     = declaration;
1793                         }
1794                         last_parameter   = parameter;
1795                         last_declaration = declaration;
1796                         break;
1797
1798                 default:
1799                         return declarations;
1800                 }
1801                 if(token.type != ',')
1802                         return declarations;
1803                 next_token();
1804         }
1805 }
1806
1807 typedef enum {
1808         CONSTRUCT_INVALID,
1809         CONSTRUCT_POINTER,
1810         CONSTRUCT_FUNCTION,
1811         CONSTRUCT_ARRAY
1812 } construct_type_type_t;
1813
1814 typedef struct construct_type_t construct_type_t;
1815 struct construct_type_t {
1816         construct_type_type_t  type;
1817         construct_type_t      *next;
1818 };
1819
1820 typedef struct parsed_pointer_t parsed_pointer_t;
1821 struct parsed_pointer_t {
1822         construct_type_t  construct_type;
1823         type_qualifier_t  type_qualifiers;
1824 };
1825
1826 typedef struct construct_function_type_t construct_function_type_t;
1827 struct construct_function_type_t {
1828         construct_type_t    construct_type;
1829         function_type_t    *function_type;
1830 };
1831
1832 typedef struct parsed_array_t parsed_array_t;
1833 struct parsed_array_t {
1834         construct_type_t  construct_type;
1835         type_qualifier_t  type_qualifiers;
1836         bool              is_static;
1837         bool              is_variable;
1838         expression_t     *size;
1839 };
1840
1841 typedef struct construct_base_type_t construct_base_type_t;
1842 struct construct_base_type_t {
1843         construct_type_t  construct_type;
1844         type_t           *type;
1845 };
1846
1847 static construct_type_t *parse_pointer_declarator(void)
1848 {
1849         eat('*');
1850
1851         parsed_pointer_t *pointer = obstack_alloc(&temp_obst, sizeof(pointer[0]));
1852         memset(pointer, 0, sizeof(pointer[0]));
1853         pointer->construct_type.type = CONSTRUCT_POINTER;
1854         pointer->type_qualifiers     = parse_type_qualifiers();
1855
1856         return (construct_type_t*) pointer;
1857 }
1858
1859 static construct_type_t *parse_array_declarator(void)
1860 {
1861         eat('[');
1862
1863         parsed_array_t *array = obstack_alloc(&temp_obst, sizeof(array[0]));
1864         memset(array, 0, sizeof(array[0]));
1865         array->construct_type.type = CONSTRUCT_ARRAY;
1866
1867         if(token.type == T_static) {
1868                 array->is_static = true;
1869                 next_token();
1870         }
1871
1872         type_qualifier_t type_qualifiers = parse_type_qualifiers();
1873         if(type_qualifiers != 0) {
1874                 if(token.type == T_static) {
1875                         array->is_static = true;
1876                         next_token();
1877                 }
1878         }
1879         array->type_qualifiers = type_qualifiers;
1880
1881         if(token.type == '*' && look_ahead(1)->type == ']') {
1882                 array->is_variable = true;
1883                 next_token();
1884         } else if(token.type != ']') {
1885                 array->size = parse_assignment_expression();
1886         }
1887
1888         expect(']');
1889
1890         return (construct_type_t*) array;
1891 }
1892
1893 static construct_type_t *parse_function_declarator(declaration_t *declaration)
1894 {
1895         eat('(');
1896
1897         function_type_t *type = allocate_type_zero(sizeof(type[0]));
1898         type->type.type       = TYPE_FUNCTION;
1899
1900         declaration_t *parameters = parse_parameters(type);
1901         if(declaration != NULL) {
1902                 declaration->context.declarations = parameters;
1903         }
1904
1905         construct_function_type_t *construct_function_type =
1906                 obstack_alloc(&temp_obst, sizeof(construct_function_type[0]));
1907         memset(construct_function_type, 0, sizeof(construct_function_type[0]));
1908         construct_function_type->construct_type.type = CONSTRUCT_FUNCTION;
1909         construct_function_type->function_type       = type;
1910
1911         expect(')');
1912
1913         return (construct_type_t*) construct_function_type;
1914 }
1915
1916 static construct_type_t *parse_inner_declarator(declaration_t *declaration,
1917                 bool may_be_abstract)
1918 {
1919         /* construct a single linked list of construct_type_t's which describe
1920          * how to construct the final declarator type */
1921         construct_type_t *first = NULL;
1922         construct_type_t *last  = NULL;
1923
1924         /* pointers */
1925         while(token.type == '*') {
1926                 construct_type_t *type = parse_pointer_declarator();
1927
1928                 if(last == NULL) {
1929                         first = type;
1930                         last  = type;
1931                 } else {
1932                         last->next = type;
1933                         last       = type;
1934                 }
1935         }
1936
1937         /* TODO: find out if this is correct */
1938         parse_attributes();
1939
1940         construct_type_t *inner_types = NULL;
1941
1942         switch(token.type) {
1943         case T_IDENTIFIER:
1944                 if(declaration == NULL) {
1945                         parse_error("no identifier expected in typename");
1946                 } else {
1947                         declaration->symbol          = token.v.symbol;
1948                         declaration->source_position = token.source_position;
1949                 }
1950                 next_token();
1951                 break;
1952         case '(':
1953                 next_token();
1954                 inner_types = parse_inner_declarator(declaration, may_be_abstract);
1955                 expect(')');
1956                 break;
1957         default:
1958                 if(may_be_abstract)
1959                         break;
1960                 parse_error_expected("while parsing declarator", T_IDENTIFIER, '(', 0);
1961                 /* avoid a loop in the outermost scope, because eat_statement doesn't
1962                  * eat '}' */
1963                 if(token.type == '}' && current_function == NULL) {
1964                         next_token();
1965                 } else {
1966                         eat_statement();
1967                 }
1968                 return NULL;
1969         }
1970
1971         construct_type_t *p = last;
1972
1973         while(true) {
1974                 construct_type_t *type;
1975                 switch(token.type) {
1976                 case '(':
1977                         type = parse_function_declarator(declaration);
1978                         break;
1979                 case '[':
1980                         type = parse_array_declarator();
1981                         break;
1982                 default:
1983                         goto declarator_finished;
1984                 }
1985
1986                 /* insert in the middle of the list (behind p) */
1987                 if(p != NULL) {
1988                         type->next = p->next;
1989                         p->next    = type;
1990                 } else {
1991                         type->next = first;
1992                         first      = type;
1993                 }
1994                 if(last == p) {
1995                         last = type;
1996                 }
1997         }
1998
1999 declarator_finished:
2000         parse_attributes();
2001
2002         /* append inner_types at the end of the list, we don't to set last anymore
2003          * as it's not needed anymore */
2004         if(last == NULL) {
2005                 assert(first == NULL);
2006                 first = inner_types;
2007         } else {
2008                 last->next = inner_types;
2009         }
2010
2011         return first;
2012 }
2013
2014 static type_t *construct_declarator_type(construct_type_t *construct_list,
2015                                          type_t *type)
2016 {
2017         construct_type_t *iter = construct_list;
2018         for( ; iter != NULL; iter = iter->next) {
2019                 parsed_pointer_t          *parsed_pointer;
2020                 parsed_array_t            *parsed_array;
2021                 construct_function_type_t *construct_function_type;
2022                 function_type_t           *function_type;
2023                 pointer_type_t            *pointer_type;
2024                 array_type_t              *array_type;
2025
2026                 switch(iter->type) {
2027                 case CONSTRUCT_INVALID:
2028                         panic("invalid type construction found");
2029                 case CONSTRUCT_FUNCTION:
2030                         construct_function_type = (construct_function_type_t*) iter;
2031                         function_type           = construct_function_type->function_type;
2032
2033                         function_type->result_type = type;
2034                         type                       = (type_t*) function_type;
2035                         break;
2036
2037                 case CONSTRUCT_POINTER:
2038                         parsed_pointer = (parsed_pointer_t*) iter;
2039                         pointer_type   = allocate_type_zero(sizeof(pointer_type[0]));
2040
2041                         pointer_type->type.type       = TYPE_POINTER;
2042                         pointer_type->points_to       = type;
2043                         pointer_type->type.qualifiers = parsed_pointer->type_qualifiers;
2044                         type                          = (type_t*) pointer_type;
2045                         break;
2046
2047                 case CONSTRUCT_ARRAY:
2048                         parsed_array  = (parsed_array_t*) iter;
2049                         array_type    = allocate_type_zero(sizeof(array_type[0]));
2050
2051                         array_type->type.type       = TYPE_ARRAY;
2052                         array_type->element_type    = type;
2053                         array_type->type.qualifiers = parsed_array->type_qualifiers;
2054                         array_type->is_static       = parsed_array->is_static;
2055                         array_type->is_variable     = parsed_array->is_variable;
2056                         array_type->size            = parsed_array->size;
2057                         type                        = (type_t*) array_type;
2058                         break;
2059                 }
2060
2061                 type_t *hashed_type = typehash_insert((type_t*) type);
2062                 if(hashed_type != type) {
2063                         /* the function type was constructed earlier freeing it here will
2064                          * destroy other types... */
2065                         if(iter->type != CONSTRUCT_FUNCTION) {
2066                                 free_type(type);
2067                         }
2068                         type = hashed_type;
2069                 }
2070         }
2071
2072         return type;
2073 }
2074
2075 static declaration_t *parse_declarator(
2076                 const declaration_specifiers_t *specifiers,
2077                 type_t *type, bool may_be_abstract)
2078 {
2079         declaration_t *declaration = allocate_ast_zero(sizeof(declaration[0]));
2080         declaration->storage_class = specifiers->storage_class;
2081         declaration->is_inline     = specifiers->is_inline;
2082
2083         construct_type_t *construct_type
2084                 = parse_inner_declarator(declaration, may_be_abstract);
2085         declaration->type = construct_declarator_type(construct_type, type);
2086
2087         if(construct_type != NULL) {
2088                 obstack_free(&temp_obst, construct_type);
2089         }
2090
2091         return declaration;
2092 }
2093
2094 static type_t *parse_abstract_declarator(type_t *base_type)
2095 {
2096         construct_type_t *construct_type = parse_inner_declarator(NULL, 1);
2097
2098         type_t *result = construct_declarator_type(construct_type, base_type);
2099         if(construct_type != NULL) {
2100                 obstack_free(&temp_obst, construct_type);
2101         }
2102
2103         return result;
2104 }
2105
2106 static declaration_t *record_declaration(declaration_t *declaration)
2107 {
2108         assert(context != NULL);
2109
2110         symbol_t *symbol = declaration->symbol;
2111         if(symbol != NULL) {
2112                 declaration_t *alias = environment_push(declaration);
2113                 if(alias != declaration)
2114                         return alias;
2115         } else {
2116                 declaration->parent_context = context;
2117         }
2118
2119         if(last_declaration != NULL) {
2120                 last_declaration->next = declaration;
2121         } else {
2122                 context->declarations = declaration;
2123         }
2124         last_declaration = declaration;
2125
2126         return declaration;
2127 }
2128
2129 static void parser_error_multiple_definition(declaration_t *previous,
2130                                              declaration_t *declaration)
2131 {
2132         parser_print_error_prefix_pos(declaration->source_position);
2133         fprintf(stderr, "multiple definition of symbol '%s'\n",
2134                 declaration->symbol->string);
2135         parser_print_error_prefix_pos(previous->source_position);
2136         fprintf(stderr, "this is the location of the previous definition.\n");
2137 }
2138
2139 static void parse_init_declarators(const declaration_specifiers_t *specifiers)
2140 {
2141         while(true) {
2142                 declaration_t *ndeclaration
2143                         = parse_declarator(specifiers, specifiers->type, false);
2144
2145                 declaration_t *declaration = record_declaration(ndeclaration);
2146
2147                 type_t *orig_type = declaration->type;
2148                 type_t *type      = skip_typeref(orig_type);
2149                 if(type->type != TYPE_FUNCTION && declaration->is_inline) {
2150                         parser_print_warning_prefix_pos(declaration->source_position);
2151                         fprintf(stderr, "variable '%s' declared 'inline'\n",
2152                                 declaration->symbol->string);
2153                 }
2154
2155                 if(token.type == '=') {
2156                         next_token();
2157
2158                         /* TODO: check that this is an allowed type (no function type) */
2159
2160                         if(declaration->init.initializer != NULL) {
2161                                 parser_error_multiple_definition(declaration, ndeclaration);
2162                         }
2163
2164                         initializer_t *initializer = parse_initializer(type);
2165
2166                         if(type->type == TYPE_ARRAY && initializer != NULL) {
2167                                 assert(initializer->type == INITIALIZER_LIST);
2168
2169                                 initializer_list_t *list = (initializer_list_t*) initializer;
2170                                 array_type_t       *array_type = (array_type_t*) type;
2171
2172                                 if(array_type->size == NULL) {
2173                                         const_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
2174
2175                                         cnst->expression.type     = EXPR_CONST;
2176                                         cnst->expression.datatype = type_size_t;
2177                                         cnst->v.int_value         = list->len;
2178
2179                                         array_type->size = (expression_t*) cnst;
2180                                 }
2181                         }
2182
2183
2184                         ndeclaration->init.initializer = initializer;
2185                 } else if(token.type == '{') {
2186                         if(type->type != TYPE_FUNCTION) {
2187                                 parser_print_error_prefix();
2188                                 fprintf(stderr, "declarator '");
2189                                 print_type_ext(orig_type, declaration->symbol, NULL);
2190                                 fprintf(stderr, "' has a body but is not a function type.\n");
2191                                 eat_block();
2192                                 continue;
2193                         }
2194
2195                         if(declaration->init.statement != NULL) {
2196                                 parser_error_multiple_definition(declaration, ndeclaration);
2197                         }
2198                         if(ndeclaration != declaration) {
2199                                 memcpy(&declaration->context, &ndeclaration->context,
2200                                        sizeof(declaration->context));
2201                         }
2202
2203                         int         top          = environment_top();
2204                         context_t  *last_context = context;
2205                         set_context(&declaration->context);
2206
2207                         /* push function parameters */
2208                         declaration_t *parameter = declaration->context.declarations;
2209                         for( ; parameter != NULL; parameter = parameter->next) {
2210                                 environment_push(parameter);
2211                         }
2212
2213                         int            label_stack_top      = label_top();
2214                         declaration_t *old_current_function = current_function;
2215                         current_function                    = declaration;
2216
2217                         statement_t *statement = parse_compound_statement();
2218
2219                         assert(current_function == declaration);
2220                         current_function = old_current_function;
2221                         label_pop_to(label_stack_top);
2222
2223                         assert(context == &declaration->context);
2224                         set_context(last_context);
2225                         environment_pop_to(top);
2226
2227                         declaration->init.statement = statement;
2228                         return;
2229                 }
2230
2231                 if(token.type != ',')
2232                         break;
2233                 next_token();
2234         }
2235         expect_void(';');
2236 }
2237
2238 static void parse_struct_declarators(const declaration_specifiers_t *specifiers)
2239 {
2240         while(1) {
2241                 if(token.type == ':') {
2242                         next_token();
2243                         parse_constant_expression();
2244                         /* TODO (bitfields) */
2245                 } else {
2246                         declaration_t *declaration
2247                                 = parse_declarator(specifiers, specifiers->type, true);
2248
2249                         /* TODO: check constraints for struct declarations */
2250                         /* TODO: check for doubled fields */
2251                         record_declaration(declaration);
2252
2253                         if(token.type == ':') {
2254                                 next_token();
2255                                 parse_constant_expression();
2256                                 /* TODO (bitfields) */
2257                         }
2258                 }
2259
2260                 if(token.type != ',')
2261                         break;
2262                 next_token();
2263         }
2264         expect_void(';');
2265 }
2266
2267 static void parse_compound_type_entries(void)
2268 {
2269         eat('{');
2270
2271         while(token.type != '}' && token.type != T_EOF) {
2272                 declaration_specifiers_t specifiers;
2273                 memset(&specifiers, 0, sizeof(specifiers));
2274                 parse_declaration_specifiers(&specifiers);
2275
2276                 parse_struct_declarators(&specifiers);
2277         }
2278         if(token.type == T_EOF) {
2279                 parse_error("unexpected error while parsing struct");
2280         }
2281         next_token();
2282 }
2283
2284 static void parse_declaration(void)
2285 {
2286         source_position_t source_position = token.source_position;
2287
2288         declaration_specifiers_t specifiers;
2289         memset(&specifiers, 0, sizeof(specifiers));
2290         parse_declaration_specifiers(&specifiers);
2291
2292         if(token.type == ';') {
2293                 if (specifiers.storage_class != STORAGE_CLASS_NONE) {
2294                         parse_warning_pos(source_position,
2295                                           "useless keyword in empty declaration");
2296                 }
2297                 switch (specifiers.type->type) {
2298                         case TYPE_COMPOUND_STRUCT:
2299                         case TYPE_COMPOUND_UNION: {
2300                                 const compound_type_t *const comp_type =
2301                                         (const compound_type_t*)specifiers.type;
2302                                 if (comp_type->declaration->symbol == NULL) {
2303                                         parse_warning_pos(source_position,
2304                                                                                                                 "unnamed struct/union that defines no instances");
2305                                 }
2306                                 break;
2307                         }
2308
2309                         case TYPE_ENUM: break;
2310
2311                         default:
2312                                 parse_warning_pos(source_position, "empty declaration");
2313                                 break;
2314                 }
2315
2316                 next_token();
2317
2318                 declaration_t *declaration = allocate_ast_zero(sizeof(declaration[0]));
2319
2320                 declaration->type            = specifiers.type;
2321                 declaration->storage_class   = specifiers.storage_class;
2322                 declaration->source_position = source_position;
2323                 record_declaration(declaration);
2324                 return;
2325         }
2326         parse_init_declarators(&specifiers);
2327 }
2328
2329 static type_t *parse_typename(void)
2330 {
2331         declaration_specifiers_t specifiers;
2332         memset(&specifiers, 0, sizeof(specifiers));
2333         parse_declaration_specifiers(&specifiers);
2334         if(specifiers.storage_class != STORAGE_CLASS_NONE) {
2335                 /* TODO: improve error message, user does probably not know what a
2336                  * storage class is...
2337                  */
2338                 parse_error("typename may not have a storage class");
2339         }
2340
2341         type_t *result = parse_abstract_declarator(specifiers.type);
2342
2343         return result;
2344 }
2345
2346
2347
2348
2349 typedef expression_t* (*parse_expression_function) (unsigned precedence);
2350 typedef expression_t* (*parse_expression_infix_function) (unsigned precedence,
2351                                                           expression_t *left);
2352
2353 typedef struct expression_parser_function_t expression_parser_function_t;
2354 struct expression_parser_function_t {
2355         unsigned                         precedence;
2356         parse_expression_function        parser;
2357         unsigned                         infix_precedence;
2358         parse_expression_infix_function  infix_parser;
2359 };
2360
2361 expression_parser_function_t expression_parsers[T_LAST_TOKEN];
2362
2363 static expression_t *make_invalid_expression(void)
2364 {
2365         expression_t *expression    = allocate_ast_zero(sizeof(expression[0]));
2366         expression->type            = EXPR_INVALID;
2367         expression->source_position = token.source_position;
2368         return expression;
2369 }
2370
2371 static expression_t *expected_expression_error(void)
2372 {
2373         parser_print_error_prefix();
2374         fprintf(stderr, "expected expression, got token ");
2375         print_token(stderr, & token);
2376         fprintf(stderr, "\n");
2377
2378         next_token();
2379
2380         return make_invalid_expression();
2381 }
2382
2383 static expression_t *parse_string_const(void)
2384 {
2385         string_literal_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
2386
2387         cnst->expression.type     = EXPR_STRING_LITERAL;
2388         cnst->expression.datatype = type_string;
2389         cnst->value               = parse_string_literals();
2390
2391         return (expression_t*) cnst;
2392 }
2393
2394 static expression_t *parse_int_const(void)
2395 {
2396         const_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
2397
2398         cnst->expression.type     = EXPR_CONST;
2399         cnst->expression.datatype = token.datatype;
2400         cnst->v.int_value         = token.v.intvalue;
2401
2402         next_token();
2403
2404         return (expression_t*) cnst;
2405 }
2406
2407 static expression_t *parse_float_const(void)
2408 {
2409         const_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
2410
2411         cnst->expression.type     = EXPR_CONST;
2412         cnst->expression.datatype = token.datatype;
2413         cnst->v.float_value       = token.v.floatvalue;
2414
2415         next_token();
2416
2417         return (expression_t*) cnst;
2418 }
2419
2420 static declaration_t *create_implicit_function(symbol_t *symbol,
2421                 const source_position_t source_position)
2422 {
2423         function_type_t *function_type
2424                 = allocate_type_zero(sizeof(function_type[0]));
2425
2426         function_type->type.type              = TYPE_FUNCTION;
2427         function_type->result_type            = type_int;
2428         function_type->unspecified_parameters = true;
2429
2430         type_t *type = typehash_insert((type_t*) function_type);
2431         if(type != (type_t*) function_type) {
2432                 free_type(function_type);
2433         }
2434
2435         declaration_t *declaration = allocate_ast_zero(sizeof(declaration[0]));
2436
2437         declaration->storage_class   = STORAGE_CLASS_EXTERN;
2438         declaration->type            = type;
2439         declaration->symbol          = symbol;
2440         declaration->source_position = source_position;
2441
2442         /* prepend the implicit definition to the global context
2443          * this is safe since the symbol wasn't declared as anything else yet
2444          */
2445         assert(symbol->declaration == NULL);
2446
2447         context_t *last_context = context;
2448         context = global_context;
2449
2450         environment_push(declaration);
2451         declaration->next     = context->declarations;
2452         context->declarations = declaration;
2453
2454         context = last_context;
2455
2456         return declaration;
2457 }
2458
2459 static expression_t *parse_reference(void)
2460 {
2461         reference_expression_t *ref = allocate_ast_zero(sizeof(ref[0]));
2462
2463         ref->expression.type = EXPR_REFERENCE;
2464         ref->symbol          = token.v.symbol;
2465
2466         declaration_t *declaration = get_declaration(ref->symbol, NAMESPACE_NORMAL);
2467
2468         source_position_t source_position = token.source_position;
2469         next_token();
2470
2471         if(declaration == NULL) {
2472 #ifndef STRICT_C99
2473                 /* an implicitly defined function */
2474                 if(token.type == '(') {
2475                         parser_print_prefix_pos(token.source_position);
2476                         fprintf(stderr, "warning: implicit declaration of function '%s'\n",
2477                                 ref->symbol->string);
2478
2479                         declaration = create_implicit_function(ref->symbol,
2480                                                                source_position);
2481                 } else
2482 #endif
2483                 {
2484                         parser_print_error_prefix();
2485                         fprintf(stderr, "unknown symbol '%s' found.\n", ref->symbol->string);
2486                         return (expression_t*) ref;
2487                 }
2488         }
2489
2490         ref->declaration         = declaration;
2491         ref->expression.datatype = declaration->type;
2492
2493         return (expression_t*) ref;
2494 }
2495
2496 static void check_cast_allowed(expression_t *expression, type_t *dest_type)
2497 {
2498         (void) expression;
2499         (void) dest_type;
2500         /* TODO check if explicit cast is allowed and issue warnings/errors */
2501 }
2502
2503 static expression_t *parse_cast(void)
2504 {
2505         unary_expression_t *cast = allocate_ast_zero(sizeof(cast[0]));
2506
2507         cast->expression.type            = EXPR_UNARY;
2508         cast->type                       = UNEXPR_CAST;
2509         cast->expression.source_position = token.source_position;
2510
2511         type_t *type  = parse_typename();
2512
2513         expect(')');
2514         expression_t *value = parse_sub_expression(20);
2515
2516         check_cast_allowed(value, type);
2517
2518         cast->expression.datatype = type;
2519         cast->value               = value;
2520
2521         return (expression_t*) cast;
2522 }
2523
2524 static expression_t *parse_statement_expression(void)
2525 {
2526         statement_expression_t *expression
2527                 = allocate_ast_zero(sizeof(expression[0]));
2528         expression->expression.type = EXPR_STATEMENT;
2529
2530         statement_t *statement = parse_compound_statement();
2531         expression->statement  = statement;
2532         if(statement == NULL) {
2533                 expect(')');
2534                 return NULL;
2535         }
2536
2537         assert(statement->type == STATEMENT_COMPOUND);
2538         compound_statement_t *compound_statement
2539                 = (compound_statement_t*) statement;
2540
2541         /* find last statement and use it's type */
2542         const statement_t *last_statement = NULL;
2543         const statement_t *iter           = compound_statement->statements;
2544         for( ; iter != NULL; iter = iter->next) {
2545                 last_statement = iter;
2546         }
2547
2548         if(last_statement->type == STATEMENT_EXPRESSION) {
2549                 const expression_statement_t *expression_statement =
2550                         (const expression_statement_t*) last_statement;
2551                 expression->expression.datatype
2552                         = expression_statement->expression->datatype;
2553         } else {
2554                 expression->expression.datatype = type_void;
2555         }
2556
2557         expect(')');
2558
2559         return (expression_t*) expression;
2560 }
2561
2562 static expression_t *parse_brace_expression(void)
2563 {
2564         eat('(');
2565
2566         switch(token.type) {
2567         case '{':
2568                 /* gcc extension: a stement expression */
2569                 return parse_statement_expression();
2570
2571         TYPE_QUALIFIERS
2572         TYPE_SPECIFIERS
2573                 return parse_cast();
2574         case T_IDENTIFIER:
2575                 if(is_typedef_symbol(token.v.symbol)) {
2576                         return parse_cast();
2577                 }
2578         }
2579
2580         expression_t *result = parse_expression();
2581         expect(')');
2582
2583         return result;
2584 }
2585
2586 static expression_t *parse_function_keyword(void)
2587 {
2588         next_token();
2589         /* TODO */
2590
2591         if (current_function == NULL) {
2592                 parse_error("'__func__' used outside of a function");
2593         }
2594
2595         string_literal_t *expression = allocate_ast_zero(sizeof(expression[0]));
2596         expression->expression.type     = EXPR_FUNCTION;
2597         expression->expression.datatype = type_string;
2598         expression->value               = "TODO: FUNCTION";
2599
2600         return (expression_t*) expression;
2601 }
2602
2603 static expression_t *parse_pretty_function_keyword(void)
2604 {
2605         eat(T___PRETTY_FUNCTION__);
2606         /* TODO */
2607
2608         string_literal_t *expression = allocate_ast_zero(sizeof(expression[0]));
2609         expression->expression.type     = EXPR_PRETTY_FUNCTION;
2610         expression->expression.datatype = type_string;
2611         expression->value               = "TODO: PRETTY FUNCTION";
2612
2613         return (expression_t*) expression;
2614 }
2615
2616 static designator_t *parse_designator(void)
2617 {
2618         designator_t *result = allocate_ast_zero(sizeof(result[0]));
2619
2620         if(token.type != T_IDENTIFIER) {
2621                 parse_error_expected("while parsing member designator",
2622                                      T_IDENTIFIER, 0);
2623                 eat_brace();
2624                 return NULL;
2625         }
2626         result->symbol = token.v.symbol;
2627         next_token();
2628
2629         designator_t *last_designator = result;
2630         while(true) {
2631                 if(token.type == '.') {
2632                         next_token();
2633                         if(token.type != T_IDENTIFIER) {
2634                                 parse_error_expected("while parsing member designator",
2635                                                      T_IDENTIFIER, 0);
2636                                 eat_brace();
2637                                 return NULL;
2638                         }
2639                         designator_t *designator = allocate_ast_zero(sizeof(result[0]));
2640                         designator->symbol       = token.v.symbol;
2641                         next_token();
2642
2643                         last_designator->next = designator;
2644                         last_designator       = designator;
2645                         continue;
2646                 }
2647                 if(token.type == '[') {
2648                         next_token();
2649                         designator_t *designator = allocate_ast_zero(sizeof(result[0]));
2650                         designator->array_access = parse_expression();
2651                         if(designator->array_access == NULL) {
2652                                 eat_brace();
2653                                 return NULL;
2654                         }
2655                         expect(']');
2656
2657                         last_designator->next = designator;
2658                         last_designator       = designator;
2659                         continue;
2660                 }
2661                 break;
2662         }
2663
2664         return result;
2665 }
2666
2667 static expression_t *parse_offsetof(void)
2668 {
2669         eat(T___builtin_offsetof);
2670
2671         offsetof_expression_t *expression
2672                 = allocate_ast_zero(sizeof(expression[0]));
2673         expression->expression.type     = EXPR_OFFSETOF;
2674         expression->expression.datatype = type_size_t;
2675
2676         expect('(');
2677         expression->type = parse_typename();
2678         expect(',');
2679         expression->designator = parse_designator();
2680         expect(')');
2681
2682         return (expression_t*) expression;
2683 }
2684
2685 static expression_t *parse_va_arg(void)
2686 {
2687         eat(T___builtin_va_arg);
2688
2689         va_arg_expression_t *expression = allocate_ast_zero(sizeof(expression[0]));
2690         expression->expression.type     = EXPR_VA_ARG;
2691
2692         expect('(');
2693         expression->arg = parse_assignment_expression();
2694         expect(',');
2695         expression->expression.datatype = parse_typename();
2696         expect(')');
2697
2698         return (expression_t*) expression;
2699 }
2700
2701 static type_t *make_function_1_type(type_t *result_type, type_t *argument_type)
2702 {
2703         function_parameter_t *parameter = allocate_type_zero(sizeof(parameter[0]));
2704         parameter->type = argument_type;
2705
2706         function_type_t *type = allocate_type_zero(sizeof(type[0]));
2707         type->type.type   = TYPE_FUNCTION;
2708         type->result_type = result_type;
2709         type->parameters  = parameter;
2710
2711         type_t *result = typehash_insert((type_t*) type);
2712         if(result != (type_t*) type) {
2713                 free_type(type);
2714         }
2715
2716         return result;
2717 }
2718
2719 static expression_t *parse_builtin_symbol(void)
2720 {
2721         builtin_symbol_expression_t *expression
2722                 = allocate_ast_zero(sizeof(expression[0]));
2723         expression->expression.type = EXPR_BUILTIN_SYMBOL;
2724
2725         expression->symbol = token.v.symbol;
2726
2727         type_t *type;
2728         switch(token.type) {
2729         case T___builtin_alloca:
2730                 type = make_function_1_type(type_void_ptr, type_size_t);
2731                 break;
2732         }
2733
2734         next_token();
2735
2736         expression->expression.datatype = type;
2737         return (expression_t*) expression;
2738 }
2739
2740 static expression_t *parse_primary_expression(void)
2741 {
2742         switch(token.type) {
2743         case T_INTEGER:
2744                 return parse_int_const();
2745         case T_FLOATINGPOINT:
2746                 return parse_float_const();
2747         case T_STRING_LITERAL:
2748                 return parse_string_const();
2749         case T_IDENTIFIER:
2750                 return parse_reference();
2751         case T___FUNCTION__:
2752         case T___func__:
2753                 return parse_function_keyword();
2754         case T___PRETTY_FUNCTION__:
2755                 return parse_pretty_function_keyword();
2756         case T___builtin_offsetof:
2757                 return parse_offsetof();
2758         case T___builtin_va_arg:
2759                 return parse_va_arg();
2760         case T___builtin_alloca:
2761         case T___builtin_expect:
2762         case T___builtin_va_start:
2763         case T___builtin_va_end:
2764                 return parse_builtin_symbol();
2765
2766         case '(':
2767                 return parse_brace_expression();
2768         }
2769
2770         parser_print_error_prefix();
2771         fprintf(stderr, "unexpected token ");
2772         print_token(stderr, &token);
2773         fprintf(stderr, "\n");
2774         eat_statement();
2775
2776         return make_invalid_expression();
2777 }
2778
2779 static expression_t *parse_array_expression(unsigned precedence,
2780                                             expression_t *array_ref)
2781 {
2782         (void) precedence;
2783
2784         eat('[');
2785
2786         expression_t *index = parse_expression();
2787
2788         array_access_expression_t *array_access
2789                 = allocate_ast_zero(sizeof(array_access[0]));
2790
2791         array_access->expression.type = EXPR_ARRAY_ACCESS;
2792         array_access->array_ref       = array_ref;
2793         array_access->index           = index;
2794
2795         type_t *type_left  = skip_typeref(array_ref->datatype);
2796         type_t *type_right = skip_typeref(index->datatype);
2797
2798         if(type_left != NULL && type_right != NULL) {
2799                 if(type_left->type == TYPE_POINTER) {
2800                         pointer_type_t *pointer           = (pointer_type_t*) type_left;
2801                         array_access->expression.datatype = pointer->points_to;
2802                 } else if(type_left->type == TYPE_ARRAY) {
2803                         array_type_t *array_type          = (array_type_t*) type_left;
2804                         array_access->expression.datatype = array_type->element_type;
2805                 } else if(type_right->type == TYPE_POINTER) {
2806                         pointer_type_t *pointer           = (pointer_type_t*) type_right;
2807                         array_access->expression.datatype = pointer->points_to;
2808                 } else if(type_right->type == TYPE_ARRAY) {
2809                         array_type_t *array_type          = (array_type_t*) type_right;
2810                         array_access->expression.datatype = array_type->element_type;
2811                 } else {
2812                         parser_print_error_prefix();
2813                         fprintf(stderr, "array access on object with non-pointer types ");
2814                         print_type_quoted(type_left);
2815                         fprintf(stderr, ", ");
2816                         print_type_quoted(type_right);
2817                         fprintf(stderr, "\n");
2818                 }
2819         }
2820
2821         if(token.type != ']') {
2822                 parse_error_expected("Problem while parsing array access", ']', 0);
2823                 return (expression_t*) array_access;
2824         }
2825         next_token();
2826
2827         return (expression_t*) array_access;
2828 }
2829
2830 static bool is_declaration_specifier(const token_t *token,
2831                                      bool only_type_specifiers)
2832 {
2833         switch(token->type) {
2834                 TYPE_SPECIFIERS
2835                         return 1;
2836                 case T_IDENTIFIER:
2837                         return is_typedef_symbol(token->v.symbol);
2838                 STORAGE_CLASSES
2839                 TYPE_QUALIFIERS
2840                         if(only_type_specifiers)
2841                                 return 0;
2842                         return 1;
2843
2844                 default:
2845                         return 0;
2846         }
2847 }
2848
2849 static expression_t *parse_sizeof(unsigned precedence)
2850 {
2851         eat(T_sizeof);
2852
2853         sizeof_expression_t *sizeof_expression
2854                 = allocate_ast_zero(sizeof(sizeof_expression[0]));
2855         sizeof_expression->expression.type     = EXPR_SIZEOF;
2856         sizeof_expression->expression.datatype = type_size_t;
2857
2858         if(token.type == '(' && is_declaration_specifier(look_ahead(1), true)) {
2859                 next_token();
2860                 sizeof_expression->type = parse_typename();
2861                 expect(')');
2862         } else {
2863                 expression_t *expression           = parse_sub_expression(precedence);
2864                 sizeof_expression->type            = expression->datatype;
2865                 sizeof_expression->size_expression = expression;
2866         }
2867
2868         return (expression_t*) sizeof_expression;
2869 }
2870
2871 static expression_t *parse_select_expression(unsigned precedence,
2872                                              expression_t *compound)
2873 {
2874         (void) precedence;
2875         assert(token.type == '.' || token.type == T_MINUSGREATER);
2876
2877         bool is_pointer = (token.type == T_MINUSGREATER);
2878         next_token();
2879
2880         select_expression_t *select = allocate_ast_zero(sizeof(select[0]));
2881
2882         select->expression.type = EXPR_SELECT;
2883         select->compound        = compound;
2884
2885         if(token.type != T_IDENTIFIER) {
2886                 parse_error_expected("while parsing select", T_IDENTIFIER, 0);
2887                 return (expression_t*) select;
2888         }
2889         symbol_t *symbol = token.v.symbol;
2890         select->symbol   = symbol;
2891         next_token();
2892
2893         type_t *orig_type = compound->datatype;
2894         if(orig_type == NULL)
2895                 return make_invalid_expression();
2896
2897         type_t *type = skip_typeref(orig_type);
2898
2899         type_t *type_left = type;
2900         if(is_pointer) {
2901                 if(type->type != TYPE_POINTER) {
2902                         parser_print_error_prefix();
2903                         fprintf(stderr, "left hand side of '->' is not a pointer, but ");
2904                         print_type_quoted(orig_type);
2905                         fputc('\n', stderr);
2906                         return make_invalid_expression();
2907                 }
2908                 pointer_type_t *pointer_type = (pointer_type_t*) type;
2909                 type_left                    = pointer_type->points_to;
2910         }
2911         type_left = skip_typeref(type_left);
2912
2913         if(type_left->type != TYPE_COMPOUND_STRUCT
2914                         && type_left->type != TYPE_COMPOUND_UNION) {
2915                 parser_print_error_prefix();
2916                 fprintf(stderr, "request for member '%s' in something not a struct or "
2917                         "union, but ", symbol->string);
2918                 print_type_quoted(type_left);
2919                 fputc('\n', stderr);
2920                 return make_invalid_expression();
2921         }
2922
2923         compound_type_t *compound_type = (compound_type_t*) type_left;
2924         declaration_t   *declaration   = compound_type->declaration;
2925
2926         if(!declaration->init.is_defined) {
2927                 parser_print_error_prefix();
2928                 fprintf(stderr, "request for member '%s' of incomplete type ",
2929                         symbol->string);
2930                 print_type_quoted(type_left);
2931                 fputc('\n', stderr);
2932                 return make_invalid_expression();
2933         }
2934
2935         declaration_t *iter = declaration->context.declarations;
2936         for( ; iter != NULL; iter = iter->next) {
2937                 if(iter->symbol == symbol) {
2938                         break;
2939                 }
2940         }
2941         if(iter == NULL) {
2942                 parser_print_error_prefix();
2943                 print_type_quoted(type_left);
2944                 fprintf(stderr, " has no member named '%s'\n", symbol->string);
2945                 return make_invalid_expression();
2946         }
2947
2948         select->compound_entry      = iter;
2949         select->expression.datatype = iter->type;
2950         return (expression_t*) select;
2951 }
2952
2953 static expression_t *parse_call_expression(unsigned precedence,
2954                                            expression_t *expression)
2955 {
2956         (void) precedence;
2957         call_expression_t *call = allocate_ast_zero(sizeof(call[0]));
2958         call->expression.type   = EXPR_CALL;
2959         call->function          = expression;
2960
2961         function_type_t *function_type;
2962         type_t          *orig_type     = expression->datatype;
2963         type_t          *type          = skip_typeref(orig_type);
2964
2965         if(type->type == TYPE_POINTER) {
2966                 pointer_type_t *pointer_type = (pointer_type_t*) type;
2967
2968                 type = skip_typeref(pointer_type->points_to);
2969         }
2970         if (type->type == TYPE_FUNCTION) {
2971                 function_type             = (function_type_t*) type;
2972                 call->expression.datatype = function_type->result_type;
2973         } else {
2974                 parser_print_error_prefix();
2975                 fputs("called object '", stderr);
2976                 print_expression(expression);
2977                 fputs("' (type ", stderr);
2978                 print_type_quoted(orig_type);
2979                 fputs(") is not a function\n", stderr);
2980
2981                 function_type             = NULL;
2982                 call->expression.datatype = NULL;
2983         }
2984
2985         /* parse arguments */
2986         eat('(');
2987
2988         if(token.type != ')') {
2989                 call_argument_t *last_argument = NULL;
2990
2991                 while(true) {
2992                         call_argument_t *argument = allocate_ast_zero(sizeof(argument[0]));
2993
2994                         argument->expression = parse_assignment_expression();
2995                         if(last_argument == NULL) {
2996                                 call->arguments = argument;
2997                         } else {
2998                                 last_argument->next = argument;
2999                         }
3000                         last_argument = argument;
3001
3002                         if(token.type != ',')
3003                                 break;
3004                         next_token();
3005                 }
3006         }
3007         expect(')');
3008
3009         if(function_type != NULL) {
3010                 function_parameter_t *parameter = function_type->parameters;
3011                 call_argument_t      *argument  = call->arguments;
3012                 for( ; parameter != NULL && argument != NULL;
3013                                 parameter = parameter->next, argument = argument->next) {
3014                         type_t *expected_type = parameter->type;
3015                         /* TODO report context in error messages */
3016                         argument->expression = create_implicit_cast(argument->expression,
3017                                                                     expected_type);
3018                 }
3019                 /* too few parameters */
3020                 if(parameter != NULL) {
3021                         parser_print_error_prefix();
3022                         fprintf(stderr, "too few arguments to function '");
3023                         print_expression(expression);
3024                         fprintf(stderr, "'\n");
3025                 } else if(argument != NULL) {
3026                         /* too many parameters */
3027                         if(!function_type->variadic
3028                                         && !function_type->unspecified_parameters) {
3029                                 parser_print_error_prefix();
3030                                 fprintf(stderr, "too many arguments to function '");
3031                                 print_expression(expression);
3032                                 fprintf(stderr, "'\n");
3033                         } else {
3034                                 /* do default promotion */
3035                                 for( ; argument != NULL; argument = argument->next) {
3036                                         type_t *type = argument->expression->datatype;
3037
3038                                         if(type == NULL)
3039                                                 continue;
3040
3041                                         if(is_type_integer(type)) {
3042                                                 type = promote_integer(type);
3043                                         } else if(type == type_float) {
3044                                                 type = type_double;
3045                                         }
3046                                         argument->expression
3047                                                 = create_implicit_cast(argument->expression, type);
3048                                 }
3049                         }
3050                 }
3051         }
3052
3053         return (expression_t*) call;
3054 }
3055
3056 static type_t *semantic_arithmetic(type_t *type_left, type_t *type_right);
3057
3058 static expression_t *parse_conditional_expression(unsigned precedence,
3059                                                   expression_t *expression)
3060 {
3061         eat('?');
3062
3063         conditional_expression_t *conditional
3064                 = allocate_ast_zero(sizeof(conditional[0]));
3065         conditional->expression.type = EXPR_CONDITIONAL;
3066         conditional->condition       = expression;
3067
3068         /* 6.5.15.2 */
3069         type_t *condition_type_orig = conditional->condition->datatype;
3070         if(condition_type_orig != NULL) {
3071                 type_t *condition_type      = skip_typeref(condition_type_orig);
3072                 if(condition_type != NULL && !is_type_scalar(condition_type)) {
3073                         type_error("expected a scalar type", expression->source_position,
3074                                            condition_type_orig);
3075                 }
3076         }
3077
3078         expression_t *const t_expr = parse_expression();
3079         conditional->true_expression = t_expr;
3080         expect(':');
3081         expression_t *const f_expr = parse_sub_expression(precedence);
3082         conditional->false_expression = f_expr;
3083
3084         type_t *const true_type  = t_expr->datatype;
3085         if(true_type == NULL)
3086                 return (expression_t*) conditional;
3087         type_t *const false_type = f_expr->datatype;
3088         if(false_type == NULL)
3089                 return (expression_t*) conditional;
3090
3091         type_t *const skipped_true_type  = skip_typeref(true_type);
3092         type_t *const skipped_false_type = skip_typeref(false_type);
3093
3094         /* 6.5.15.3 */
3095         if (skipped_true_type == skipped_false_type) {
3096                 conditional->expression.datatype = skipped_true_type;
3097         } else if (is_type_arithmetic(skipped_true_type) &&
3098                    is_type_arithmetic(skipped_false_type)) {
3099                 type_t *const result = semantic_arithmetic(skipped_true_type,
3100                                                            skipped_false_type);
3101                 conditional->true_expression  = create_implicit_cast(t_expr, result);
3102                 conditional->false_expression = create_implicit_cast(f_expr, result);
3103                 conditional->expression.datatype = result;
3104         } else if (skipped_true_type->type == TYPE_POINTER &&
3105                    skipped_false_type->type == TYPE_POINTER &&
3106                           true /* TODO compatible points_to types */) {
3107                 /* TODO */
3108         } else if(/* (is_null_ptr_const(skipped_true_type) &&
3109                       skipped_false_type->type == TYPE_POINTER)
3110                || (is_null_ptr_const(skipped_false_type) &&
3111                    skipped_true_type->type == TYPE_POINTER) TODO*/ false) {
3112                 /* TODO */
3113         } else if(/* 1 is pointer to object type, other is void* */ false) {
3114                 /* TODO */
3115         } else {
3116                 type_error_incompatible("while parsing conditional",
3117                                         expression->source_position, true_type,
3118                                         skipped_false_type);
3119         }
3120
3121         return (expression_t*) conditional;
3122 }
3123
3124 static expression_t *parse_extension(unsigned precedence)
3125 {
3126         eat(T___extension__);
3127
3128         /* TODO enable extensions */
3129
3130         return parse_sub_expression(precedence);
3131 }
3132
3133 static expression_t *parse_builtin_classify_type(const unsigned precedence)
3134 {
3135         eat(T___builtin_classify_type);
3136
3137         classify_type_expression_t *const classify_type_expr =
3138                 allocate_ast_zero(sizeof(classify_type_expr[0]));
3139         classify_type_expr->expression.type     = EXPR_CLASSIFY_TYPE;
3140         classify_type_expr->expression.datatype = type_int;
3141
3142         expect('(');
3143         expression_t *const expression = parse_sub_expression(precedence);
3144         expect(')');
3145         classify_type_expr->type_expression = expression;
3146
3147         return (expression_t*)classify_type_expr;
3148 }
3149
3150 static void semantic_incdec(unary_expression_t *expression)
3151 {
3152         type_t *orig_type = expression->value->datatype;
3153         if(orig_type == NULL)
3154                 return;
3155
3156         type_t *type = skip_typeref(orig_type);
3157         if(!is_type_arithmetic(type) && type->type != TYPE_POINTER) {
3158                 /* TODO: improve error message */
3159                 parser_print_error_prefix();
3160                 fprintf(stderr, "operation needs an arithmetic or pointer type\n");
3161                 return;
3162         }
3163
3164         expression->expression.datatype = orig_type;
3165 }
3166
3167 static void semantic_unexpr_arithmetic(unary_expression_t *expression)
3168 {
3169         type_t *orig_type = expression->value->datatype;
3170         if(orig_type == NULL)
3171                 return;
3172
3173         type_t *type = skip_typeref(orig_type);
3174         if(!is_type_arithmetic(type)) {
3175                 /* TODO: improve error message */
3176                 parser_print_error_prefix();
3177                 fprintf(stderr, "operation needs an arithmetic type\n");
3178                 return;
3179         }
3180
3181         expression->expression.datatype = orig_type;
3182 }
3183
3184 static void semantic_unexpr_scalar(unary_expression_t *expression)
3185 {
3186         type_t *orig_type = expression->value->datatype;
3187         if(orig_type == NULL)
3188                 return;
3189
3190         type_t *type = skip_typeref(orig_type);
3191         if (!is_type_scalar(type)) {
3192                 parse_error("operand of ! must be of scalar type\n");
3193                 return;
3194         }
3195
3196         expression->expression.datatype = orig_type;
3197 }
3198
3199 static void semantic_unexpr_integer(unary_expression_t *expression)
3200 {
3201         type_t *orig_type = expression->value->datatype;
3202         if(orig_type == NULL)
3203                 return;
3204
3205         type_t *type = skip_typeref(orig_type);
3206         if (!is_type_integer(type)) {
3207                 parse_error("operand of ~ must be of integer type\n");
3208                 return;
3209         }
3210
3211         expression->expression.datatype = orig_type;
3212 }
3213
3214 static void semantic_dereference(unary_expression_t *expression)
3215 {
3216         type_t *orig_type = expression->value->datatype;
3217         if(orig_type == NULL)
3218                 return;
3219
3220         type_t *type = skip_typeref(orig_type);
3221         switch (type->type) {
3222                 case TYPE_ARRAY: {
3223                         array_type_t *const array_type  = (array_type_t*)type;
3224                         expression->expression.datatype = array_type->element_type;
3225                         break;
3226                 }
3227
3228                 case TYPE_POINTER: {
3229                         pointer_type_t *pointer_type    = (pointer_type_t*)type;
3230                         expression->expression.datatype = pointer_type->points_to;
3231                         break;
3232                 }
3233
3234                 default:
3235                         parser_print_error_prefix();
3236                         fputs("'Unary *' needs pointer or arrray type, but type ", stderr);
3237                         print_type_quoted(orig_type);
3238                         fputs(" given.\n", stderr);
3239                         return;
3240         }
3241 }
3242
3243 static void semantic_take_addr(unary_expression_t *expression)
3244 {
3245         type_t *orig_type = expression->value->datatype;
3246         if(orig_type == NULL)
3247                 return;
3248
3249         expression_t *value = expression->value;
3250         if(value->type == EXPR_REFERENCE) {
3251                 reference_expression_t *reference   = (reference_expression_t*) value;
3252                 declaration_t          *declaration = reference->declaration;
3253                 if(declaration != NULL) {
3254                         declaration->address_taken = 1;
3255                 }
3256         }
3257
3258         expression->expression.datatype = make_pointer_type(orig_type, 0);
3259 }
3260
3261 #define CREATE_UNARY_EXPRESSION_PARSER(token_type, unexpression_type, sfunc)   \
3262 static expression_t *parse_##unexpression_type(unsigned precedence)            \
3263 {                                                                              \
3264         eat(token_type);                                                           \
3265                                                                                \
3266         unary_expression_t *unary_expression                                       \
3267                 = allocate_ast_zero(sizeof(unary_expression[0]));                      \
3268         unary_expression->expression.type     = EXPR_UNARY;                        \
3269         unary_expression->type                = unexpression_type;                 \
3270         unary_expression->value               = parse_sub_expression(precedence);  \
3271                                                                                    \
3272         sfunc(unary_expression);                                                   \
3273                                                                                \
3274         return (expression_t*) unary_expression;                                   \
3275 }
3276
3277 CREATE_UNARY_EXPRESSION_PARSER('-', UNEXPR_NEGATE, semantic_unexpr_arithmetic)
3278 CREATE_UNARY_EXPRESSION_PARSER('+', UNEXPR_PLUS,   semantic_unexpr_arithmetic)
3279 CREATE_UNARY_EXPRESSION_PARSER('!', UNEXPR_NOT,    semantic_unexpr_scalar)
3280 CREATE_UNARY_EXPRESSION_PARSER('*', UNEXPR_DEREFERENCE, semantic_dereference)
3281 CREATE_UNARY_EXPRESSION_PARSER('&', UNEXPR_TAKE_ADDRESS, semantic_take_addr)
3282 CREATE_UNARY_EXPRESSION_PARSER('~', UNEXPR_BITWISE_NEGATE,
3283                                semantic_unexpr_integer)
3284 CREATE_UNARY_EXPRESSION_PARSER(T_PLUSPLUS,   UNEXPR_PREFIX_INCREMENT,
3285                                semantic_incdec)
3286 CREATE_UNARY_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_PREFIX_DECREMENT,
3287                                semantic_incdec)
3288
3289 #define CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(token_type, unexpression_type, \
3290                                                sfunc)                         \
3291 static expression_t *parse_##unexpression_type(unsigned precedence,           \
3292                                                expression_t *left)            \
3293 {                                                                             \
3294         (void) precedence;                                                        \
3295         eat(token_type);                                                          \
3296                                                                               \
3297         unary_expression_t *unary_expression                                      \
3298                 = allocate_ast_zero(sizeof(unary_expression[0]));                     \
3299         unary_expression->expression.type     = EXPR_UNARY;                       \
3300         unary_expression->type                = unexpression_type;                \
3301         unary_expression->value               = left;                             \
3302                                                                                   \
3303         sfunc(unary_expression);                                                  \
3304                                                                               \
3305         return (expression_t*) unary_expression;                                  \
3306 }
3307
3308 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_PLUSPLUS,   UNEXPR_POSTFIX_INCREMENT,
3309                                        semantic_incdec)
3310 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_POSTFIX_DECREMENT,
3311                                        semantic_incdec)
3312
3313 static type_t *semantic_arithmetic(type_t *type_left, type_t *type_right)
3314 {
3315         /* TODO: handle complex + imaginary types */
3316
3317         /* § 6.3.1.8 Usual arithmetic conversions */
3318         if(type_left == type_long_double || type_right == type_long_double) {
3319                 return type_long_double;
3320         } else if(type_left == type_double || type_right == type_double) {
3321                 return type_double;
3322         } else if(type_left == type_float || type_right == type_float) {
3323                 return type_float;
3324         }
3325
3326         type_right = promote_integer(type_right);
3327         type_left  = promote_integer(type_left);
3328
3329         if(type_left == type_right)
3330                 return type_left;
3331
3332         bool signed_left  = is_type_signed(type_left);
3333         bool signed_right = is_type_signed(type_right);
3334         if(get_rank(type_left) < get_rank(type_right)) {
3335                 if(signed_left == signed_right || !signed_right) {
3336                         return type_right;
3337                 } else {
3338                         return type_left;
3339                 }
3340         } else {
3341                 if(signed_left == signed_right || !signed_left) {
3342                         return type_left;
3343                 } else {
3344                         return type_right;
3345                 }
3346         }
3347 }
3348
3349 static void semantic_binexpr_arithmetic(binary_expression_t *expression)
3350 {
3351         expression_t *left       = expression->left;
3352         expression_t *right      = expression->right;
3353         type_t       *orig_type_left  = left->datatype;
3354         type_t       *orig_type_right = right->datatype;
3355
3356         if(orig_type_left == NULL || orig_type_right == NULL)
3357                 return;
3358
3359         type_t *type_left  = skip_typeref(orig_type_left);
3360         type_t *type_right = skip_typeref(orig_type_right);
3361
3362         if(!is_type_arithmetic(type_left) || !is_type_arithmetic(type_right)) {
3363                 /* TODO: improve error message */
3364                 parser_print_error_prefix();
3365                 fprintf(stderr, "operation needs arithmetic types\n");
3366                 return;
3367         }
3368
3369         type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
3370         expression->left  = create_implicit_cast(left, arithmetic_type);
3371         expression->right = create_implicit_cast(right, arithmetic_type);
3372         expression->expression.datatype = arithmetic_type;
3373 }
3374
3375 static void semantic_shift_op(binary_expression_t *expression)
3376 {
3377         expression_t *left       = expression->left;
3378         expression_t *right      = expression->right;
3379         type_t       *orig_type_left  = left->datatype;
3380         type_t       *orig_type_right = right->datatype;
3381
3382         if(orig_type_left == NULL || orig_type_right == NULL)
3383                 return;
3384
3385         type_t *type_left  = skip_typeref(orig_type_left);
3386         type_t *type_right = skip_typeref(orig_type_right);
3387
3388         if(!is_type_integer(type_left) || !is_type_integer(type_right)) {
3389                 /* TODO: improve error message */
3390                 parser_print_error_prefix();
3391                 fprintf(stderr, "operation needs integer types\n");
3392                 return;
3393         }
3394
3395         type_left  = promote_integer(type_left);
3396         type_right = promote_integer(type_right);
3397
3398         expression->left  = create_implicit_cast(left, type_left);
3399         expression->right = create_implicit_cast(right, type_right);
3400         expression->expression.datatype = type_left;
3401 }
3402
3403 static void semantic_add(binary_expression_t *expression)
3404 {
3405         expression_t *left            = expression->left;
3406         expression_t *right           = expression->right;
3407         type_t       *orig_type_left  = left->datatype;
3408         type_t       *orig_type_right = right->datatype;
3409
3410         if(orig_type_left == NULL || orig_type_right == NULL)
3411                 return;
3412
3413         type_t *type_left  = skip_typeref(orig_type_left);
3414         type_t *type_right = skip_typeref(orig_type_right);
3415
3416         /* § 5.6.5 */
3417         if(is_type_arithmetic(type_left) && is_type_arithmetic(type_right)) {
3418                 type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
3419                 expression->left  = create_implicit_cast(left, arithmetic_type);
3420                 expression->right = create_implicit_cast(right, arithmetic_type);
3421                 expression->expression.datatype = arithmetic_type;
3422                 return;
3423         } else if(type_left->type == TYPE_POINTER && is_type_integer(type_right)) {
3424                 expression->expression.datatype = type_left;
3425         } else if(type_right->type == TYPE_POINTER && is_type_integer(type_left)) {
3426                 expression->expression.datatype = type_right;
3427         } else if (type_left->type == TYPE_ARRAY && is_type_integer(type_right)) {
3428                 const array_type_t *const arr_type = (const array_type_t*)type_left;
3429                 expression->expression.datatype =
3430                   make_pointer_type(arr_type->element_type, TYPE_QUALIFIER_NONE);
3431         } else if (type_right->type == TYPE_ARRAY && is_type_integer(type_left)) {
3432                 const array_type_t *const arr_type = (const array_type_t*)type_right;
3433                 expression->expression.datatype =
3434                         make_pointer_type(arr_type->element_type, TYPE_QUALIFIER_NONE);
3435         } else {
3436                 parser_print_error_prefix();
3437                 fprintf(stderr, "invalid operands to binary + (");
3438                 print_type_quoted(orig_type_left);
3439                 fprintf(stderr, ", ");
3440                 print_type_quoted(orig_type_right);
3441                 fprintf(stderr, ")\n");
3442         }
3443 }
3444
3445 static void semantic_sub(binary_expression_t *expression)
3446 {
3447         expression_t *left            = expression->left;
3448         expression_t *right           = expression->right;
3449         type_t       *orig_type_left  = left->datatype;
3450         type_t       *orig_type_right = right->datatype;
3451
3452         if(orig_type_left == NULL || orig_type_right == NULL)
3453                 return;
3454
3455         type_t       *type_left       = skip_typeref(orig_type_left);
3456         type_t       *type_right      = skip_typeref(orig_type_right);
3457
3458         /* § 5.6.5 */
3459         if(is_type_arithmetic(type_left) && is_type_arithmetic(type_right)) {
3460                 type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
3461                 expression->left  = create_implicit_cast(left, arithmetic_type);
3462                 expression->right = create_implicit_cast(right, arithmetic_type);
3463                 expression->expression.datatype = arithmetic_type;
3464                 return;
3465         } else if(type_left->type == TYPE_POINTER && is_type_integer(type_right)) {
3466                 expression->expression.datatype = type_left;
3467         } else if(type_left->type == TYPE_POINTER &&
3468                         type_right->type == TYPE_POINTER) {
3469                 if(!pointers_compatible(type_left, type_right)) {
3470                         parser_print_error_prefix();
3471                         fprintf(stderr, "pointers to incompatible objects to binary - (");
3472                         print_type_quoted(orig_type_left);
3473                         fprintf(stderr, ", ");
3474                         print_type_quoted(orig_type_right);
3475                         fprintf(stderr, ")\n");
3476                 } else {
3477                         expression->expression.datatype = type_ptrdiff_t;
3478                 }
3479         } else {
3480                 parser_print_error_prefix();
3481                 fprintf(stderr, "invalid operands to binary - (");
3482                 print_type_quoted(orig_type_left);
3483                 fprintf(stderr, ", ");
3484                 print_type_quoted(orig_type_right);
3485                 fprintf(stderr, ")\n");
3486         }
3487 }
3488
3489 static void semantic_comparison(binary_expression_t *expression)
3490 {
3491         expression_t *left            = expression->left;
3492         expression_t *right           = expression->right;
3493         type_t       *orig_type_left  = left->datatype;
3494         type_t       *orig_type_right = right->datatype;
3495
3496         if(orig_type_left == NULL || orig_type_right == NULL)
3497                 return;
3498
3499         type_t *type_left  = skip_typeref(orig_type_left);
3500         type_t *type_right = skip_typeref(orig_type_right);
3501
3502         /* TODO non-arithmetic types */
3503         if(is_type_arithmetic(type_left) && is_type_arithmetic(type_right)) {
3504                 type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
3505                 expression->left  = create_implicit_cast(left, arithmetic_type);
3506                 expression->right = create_implicit_cast(right, arithmetic_type);
3507                 expression->expression.datatype = arithmetic_type;
3508         } else if (type_left->type  == TYPE_POINTER &&
3509                    type_right->type == TYPE_POINTER) {
3510                 /* TODO check compatibility */
3511         } else if (type_left->type == TYPE_POINTER) {
3512                 expression->right = create_implicit_cast(right, type_left);
3513         } else if (type_right->type == TYPE_POINTER) {
3514                 expression->left = create_implicit_cast(left, type_right);
3515         } else {
3516                 type_error_incompatible("invalid operands in comparison",
3517                                         token.source_position, type_left, type_right);
3518         }
3519         expression->expression.datatype = type_int;
3520 }
3521
3522 static void semantic_arithmetic_assign(binary_expression_t *expression)
3523 {
3524         expression_t *left            = expression->left;
3525         expression_t *right           = expression->right;
3526         type_t       *orig_type_left  = left->datatype;
3527         type_t       *orig_type_right = right->datatype;
3528
3529         if(orig_type_left == NULL || orig_type_right == NULL)
3530                 return;
3531
3532         type_t *type_left  = skip_typeref(orig_type_left);
3533         type_t *type_right = skip_typeref(orig_type_right);
3534
3535         if(!is_type_arithmetic(type_left) || !is_type_arithmetic(type_right)) {
3536                 /* TODO: improve error message */
3537                 parser_print_error_prefix();
3538                 fprintf(stderr, "operation needs arithmetic types\n");
3539                 return;
3540         }
3541
3542         /* combined instructions are tricky. We can't create an implicit cast on
3543          * the left side, because we need the uncasted form for the store.
3544          * The ast2firm pass has to know that left_type must be right_type
3545          * for the arithmeitc operation and create a cast by itself */
3546         type_t *arithmetic_type = semantic_arithmetic(type_left, type_right);
3547         expression->right       = create_implicit_cast(right, arithmetic_type);
3548         expression->expression.datatype = type_left;
3549 }
3550
3551 static void semantic_arithmetic_addsubb_assign(binary_expression_t *expression)
3552 {
3553         expression_t *left            = expression->left;
3554         expression_t *right           = expression->right;
3555         type_t       *orig_type_left  = left->datatype;
3556         type_t       *orig_type_right = right->datatype;
3557
3558         if(orig_type_left == NULL || orig_type_right == NULL)
3559                 return;
3560
3561         type_t *type_left  = skip_typeref(orig_type_left);
3562         type_t *type_right = skip_typeref(orig_type_right);
3563
3564         if (is_type_arithmetic(type_left) && is_type_arithmetic(type_right)) {
3565                 /* combined instructions are tricky. We can't create an implicit cast on
3566                  * the left side, because we need the uncasted form for the store.
3567                  * The ast2firm pass has to know that left_type must be right_type
3568                  * for the arithmeitc operation and create a cast by itself */
3569                 type_t *const arithmetic_type = semantic_arithmetic(type_left, type_right);
3570                 expression->right = create_implicit_cast(right, arithmetic_type);
3571                 expression->expression.datatype = type_left;
3572         } else if (type_left->type == TYPE_POINTER && is_type_integer(type_right)) {
3573                 expression->expression.datatype = type_left;
3574         } else {
3575                 parser_print_error_prefix();
3576                 fputs("Incompatible types ", stderr);
3577                 print_type_quoted(orig_type_left);
3578                 fputs(" and ", stderr);
3579                 print_type_quoted(orig_type_right);
3580                 fputs(" in assignment\n", stderr);
3581                 return;
3582         }
3583 }
3584
3585 static void semantic_logical_op(binary_expression_t *expression)
3586 {
3587         expression_t *left            = expression->left;
3588         expression_t *right           = expression->right;
3589         type_t       *orig_type_left  = left->datatype;
3590         type_t       *orig_type_right = right->datatype;
3591
3592         if(orig_type_left == NULL || orig_type_right == NULL)
3593                 return;
3594
3595         type_t *type_left  = skip_typeref(orig_type_left);
3596         type_t *type_right = skip_typeref(orig_type_right);
3597
3598         if (!is_type_scalar(type_left) || !is_type_scalar(type_right)) {
3599                 /* TODO: improve error message */
3600                 parser_print_error_prefix();
3601                 fprintf(stderr, "operation needs scalar types\n");
3602                 return;
3603         }
3604
3605         expression->expression.datatype = type_int;
3606 }
3607
3608 static void semantic_binexpr_assign(binary_expression_t *expression)
3609 {
3610         expression_t *left       = expression->left;
3611         type_t       *type_left  = left->datatype;
3612
3613         if(type_left == NULL)
3614                 return;
3615
3616         if (type_left->type == TYPE_ARRAY) {
3617                 parse_error("Cannot assign to arrays.");
3618         } else if (type_left != NULL) {
3619                 semantic_assign(type_left, &expression->right, "assignment");
3620         }
3621
3622         expression->expression.datatype = type_left;
3623 }
3624
3625 static void semantic_comma(binary_expression_t *expression)
3626 {
3627         expression->expression.datatype = expression->right->datatype;
3628 }
3629
3630 #define CREATE_BINEXPR_PARSER(token_type, binexpression_type, sfunc, lr) \
3631 static expression_t *parse_##binexpression_type(unsigned precedence,     \
3632                                                 expression_t *left)      \
3633 {                                                                        \
3634         eat(token_type);                                                     \
3635                                                                          \
3636         expression_t *right = parse_sub_expression(precedence + lr);         \
3637                                                                          \
3638         binary_expression_t *binexpr                                         \
3639                 = allocate_ast_zero(sizeof(binexpr[0]));                         \
3640         binexpr->expression.type     = EXPR_BINARY;                          \
3641         binexpr->type                = binexpression_type;                   \
3642         binexpr->left                = left;                                 \
3643         binexpr->right               = right;                                \
3644         sfunc(binexpr);                                                      \
3645                                                                          \
3646         return (expression_t*) binexpr;                                      \
3647 }
3648
3649 CREATE_BINEXPR_PARSER(',', BINEXPR_COMMA,          semantic_comma, 1)
3650 CREATE_BINEXPR_PARSER('*', BINEXPR_MUL,            semantic_binexpr_arithmetic, 1)
3651 CREATE_BINEXPR_PARSER('/', BINEXPR_DIV,            semantic_binexpr_arithmetic, 1)
3652 CREATE_BINEXPR_PARSER('%', BINEXPR_MOD,            semantic_binexpr_arithmetic, 1)
3653 CREATE_BINEXPR_PARSER('+', BINEXPR_ADD,            semantic_add, 1)
3654 CREATE_BINEXPR_PARSER('-', BINEXPR_SUB,            semantic_sub, 1)
3655 CREATE_BINEXPR_PARSER('<', BINEXPR_LESS,           semantic_comparison, 1)
3656 CREATE_BINEXPR_PARSER('>', BINEXPR_GREATER,        semantic_comparison, 1)
3657 CREATE_BINEXPR_PARSER('=', BINEXPR_ASSIGN,         semantic_binexpr_assign, 0)
3658 CREATE_BINEXPR_PARSER(T_EQUALEQUAL, BINEXPR_EQUAL, semantic_comparison, 1)
3659 CREATE_BINEXPR_PARSER(T_EXCLAMATIONMARKEQUAL, BINEXPR_NOTEQUAL,
3660                       semantic_comparison, 1)
3661 CREATE_BINEXPR_PARSER(T_LESSEQUAL, BINEXPR_LESSEQUAL, semantic_comparison, 1)
3662 CREATE_BINEXPR_PARSER(T_GREATEREQUAL, BINEXPR_GREATEREQUAL,
3663                       semantic_comparison, 1)
3664 CREATE_BINEXPR_PARSER('&', BINEXPR_BITWISE_AND,    semantic_binexpr_arithmetic, 1)
3665 CREATE_BINEXPR_PARSER('|', BINEXPR_BITWISE_OR,     semantic_binexpr_arithmetic, 1)
3666 CREATE_BINEXPR_PARSER('^', BINEXPR_BITWISE_XOR,    semantic_binexpr_arithmetic, 1)
3667 CREATE_BINEXPR_PARSER(T_ANDAND, BINEXPR_LOGICAL_AND,  semantic_logical_op, 1)
3668 CREATE_BINEXPR_PARSER(T_PIPEPIPE, BINEXPR_LOGICAL_OR, semantic_logical_op, 1)
3669 CREATE_BINEXPR_PARSER(T_LESSLESS, BINEXPR_SHIFTLEFT,
3670                       semantic_shift_op, 1)
3671 CREATE_BINEXPR_PARSER(T_GREATERGREATER, BINEXPR_SHIFTRIGHT,
3672                       semantic_shift_op, 1)
3673 CREATE_BINEXPR_PARSER(T_PLUSEQUAL, BINEXPR_ADD_ASSIGN,
3674                       semantic_arithmetic_addsubb_assign, 0)
3675 CREATE_BINEXPR_PARSER(T_MINUSEQUAL, BINEXPR_SUB_ASSIGN,
3676                       semantic_arithmetic_addsubb_assign, 0)
3677 CREATE_BINEXPR_PARSER(T_ASTERISKEQUAL, BINEXPR_MUL_ASSIGN,
3678                       semantic_arithmetic_assign, 0)
3679 CREATE_BINEXPR_PARSER(T_SLASHEQUAL, BINEXPR_DIV_ASSIGN,
3680                       semantic_arithmetic_assign, 0)
3681 CREATE_BINEXPR_PARSER(T_PERCENTEQUAL, BINEXPR_MOD_ASSIGN,
3682                       semantic_arithmetic_assign, 0)
3683 CREATE_BINEXPR_PARSER(T_LESSLESSEQUAL, BINEXPR_SHIFTLEFT_ASSIGN,
3684                       semantic_arithmetic_assign, 0)
3685 CREATE_BINEXPR_PARSER(T_GREATERGREATEREQUAL, BINEXPR_SHIFTRIGHT_ASSIGN,
3686                       semantic_arithmetic_assign, 0)
3687 CREATE_BINEXPR_PARSER(T_ANDEQUAL, BINEXPR_BITWISE_AND_ASSIGN,
3688                       semantic_arithmetic_assign, 0)
3689 CREATE_BINEXPR_PARSER(T_PIPEEQUAL, BINEXPR_BITWISE_OR_ASSIGN,
3690                       semantic_arithmetic_assign, 0)
3691 CREATE_BINEXPR_PARSER(T_CARETEQUAL, BINEXPR_BITWISE_XOR_ASSIGN,
3692                       semantic_arithmetic_assign, 0)
3693
3694 static expression_t *parse_sub_expression(unsigned precedence)
3695 {
3696         if(token.type < 0) {
3697                 return expected_expression_error();
3698         }
3699
3700         expression_parser_function_t *parser
3701                 = &expression_parsers[token.type];
3702         source_position_t             source_position = token.source_position;
3703         expression_t                 *left;
3704
3705         if(parser->parser != NULL) {
3706                 left = parser->parser(parser->precedence);
3707         } else {
3708                 left = parse_primary_expression();
3709         }
3710         assert(left != NULL);
3711         left->source_position = source_position;
3712
3713         while(true) {
3714                 if(token.type < 0) {
3715                         return expected_expression_error();
3716                 }
3717
3718                 parser = &expression_parsers[token.type];
3719                 if(parser->infix_parser == NULL)
3720                         break;
3721                 if(parser->infix_precedence < precedence)
3722                         break;
3723
3724                 left = parser->infix_parser(parser->infix_precedence, left);
3725
3726                 assert(left != NULL);
3727                 assert(left->type != EXPR_UNKNOWN);
3728                 left->source_position = source_position;
3729         }
3730
3731         return left;
3732 }
3733
3734 static expression_t *parse_expression(void)
3735 {
3736         return parse_sub_expression(1);
3737 }
3738
3739
3740
3741 static void register_expression_parser(parse_expression_function parser,
3742                                        int token_type, unsigned precedence)
3743 {
3744         expression_parser_function_t *entry = &expression_parsers[token_type];
3745
3746         if(entry->parser != NULL) {
3747                 fprintf(stderr, "for token ");
3748                 print_token_type(stderr, token_type);
3749                 fprintf(stderr, "\n");
3750                 panic("trying to register multiple expression parsers for a token");
3751         }
3752         entry->parser     = parser;
3753         entry->precedence = precedence;
3754 }
3755
3756 static void register_expression_infix_parser(
3757                 parse_expression_infix_function parser, int token_type,
3758                 unsigned precedence)
3759 {
3760         expression_parser_function_t *entry = &expression_parsers[token_type];
3761
3762         if(entry->infix_parser != NULL) {
3763                 fprintf(stderr, "for token ");
3764                 print_token_type(stderr, token_type);
3765                 fprintf(stderr, "\n");
3766                 panic("trying to register multiple infix expression parsers for a "
3767                       "token");
3768         }
3769         entry->infix_parser     = parser;
3770         entry->infix_precedence = precedence;
3771 }
3772
3773 static void init_expression_parsers(void)
3774 {
3775         memset(&expression_parsers, 0, sizeof(expression_parsers));
3776
3777         register_expression_infix_parser(parse_BINEXPR_MUL,         '*',        16);
3778         register_expression_infix_parser(parse_BINEXPR_DIV,         '/',        16);
3779         register_expression_infix_parser(parse_BINEXPR_MOD,         '%',        16);
3780         register_expression_infix_parser(parse_BINEXPR_SHIFTLEFT,   T_LESSLESS, 16);
3781         register_expression_infix_parser(parse_BINEXPR_SHIFTRIGHT,
3782                                                               T_GREATERGREATER, 16);
3783         register_expression_infix_parser(parse_BINEXPR_ADD,         '+',        15);
3784         register_expression_infix_parser(parse_BINEXPR_SUB,         '-',        15);
3785         register_expression_infix_parser(parse_BINEXPR_LESS,        '<',        14);
3786         register_expression_infix_parser(parse_BINEXPR_GREATER,     '>',        14);
3787         register_expression_infix_parser(parse_BINEXPR_LESSEQUAL, T_LESSEQUAL,  14);
3788         register_expression_infix_parser(parse_BINEXPR_GREATEREQUAL,
3789                                                                 T_GREATEREQUAL, 14);
3790         register_expression_infix_parser(parse_BINEXPR_EQUAL,     T_EQUALEQUAL, 13);
3791         register_expression_infix_parser(parse_BINEXPR_NOTEQUAL,
3792                                                         T_EXCLAMATIONMARKEQUAL, 13);
3793         register_expression_infix_parser(parse_BINEXPR_BITWISE_AND, '&',        12);
3794         register_expression_infix_parser(parse_BINEXPR_BITWISE_XOR, '^',        11);
3795         register_expression_infix_parser(parse_BINEXPR_BITWISE_OR,  '|',        10);
3796         register_expression_infix_parser(parse_BINEXPR_LOGICAL_AND, T_ANDAND,    9);
3797         register_expression_infix_parser(parse_BINEXPR_LOGICAL_OR,  T_PIPEPIPE,  8);
3798         register_expression_infix_parser(parse_conditional_expression, '?',      7);
3799         register_expression_infix_parser(parse_BINEXPR_ASSIGN,      '=',         2);
3800         register_expression_infix_parser(parse_BINEXPR_ADD_ASSIGN, T_PLUSEQUAL,  2);
3801         register_expression_infix_parser(parse_BINEXPR_SUB_ASSIGN, T_MINUSEQUAL, 2);
3802         register_expression_infix_parser(parse_BINEXPR_MUL_ASSIGN,
3803                                                                 T_ASTERISKEQUAL, 2);
3804         register_expression_infix_parser(parse_BINEXPR_DIV_ASSIGN, T_SLASHEQUAL, 2);
3805         register_expression_infix_parser(parse_BINEXPR_MOD_ASSIGN,
3806                                                                  T_PERCENTEQUAL, 2);
3807         register_expression_infix_parser(parse_BINEXPR_SHIFTLEFT_ASSIGN,
3808                                                                 T_LESSLESSEQUAL, 2);
3809         register_expression_infix_parser(parse_BINEXPR_SHIFTRIGHT_ASSIGN,
3810                                                           T_GREATERGREATEREQUAL, 2);
3811         register_expression_infix_parser(parse_BINEXPR_BITWISE_AND_ASSIGN,
3812                                                                      T_ANDEQUAL, 2);
3813         register_expression_infix_parser(parse_BINEXPR_BITWISE_OR_ASSIGN,
3814                                                                     T_PIPEEQUAL, 2);
3815         register_expression_infix_parser(parse_BINEXPR_BITWISE_XOR_ASSIGN,
3816                                                                    T_CARETEQUAL, 2);
3817
3818         register_expression_infix_parser(parse_BINEXPR_COMMA,       ',',         1);
3819
3820         register_expression_infix_parser(parse_array_expression,        '[',    30);
3821         register_expression_infix_parser(parse_call_expression,         '(',    30);
3822         register_expression_infix_parser(parse_select_expression,       '.',    30);
3823         register_expression_infix_parser(parse_select_expression,
3824                                                                 T_MINUSGREATER, 30);
3825         register_expression_infix_parser(parse_UNEXPR_POSTFIX_INCREMENT,
3826                                          T_PLUSPLUS, 30);
3827         register_expression_infix_parser(parse_UNEXPR_POSTFIX_DECREMENT,
3828                                          T_MINUSMINUS, 30);
3829
3830         register_expression_parser(parse_UNEXPR_NEGATE,           '-',          25);
3831         register_expression_parser(parse_UNEXPR_PLUS,             '+',          25);
3832         register_expression_parser(parse_UNEXPR_NOT,              '!',          25);
3833         register_expression_parser(parse_UNEXPR_BITWISE_NEGATE,   '~',          25);
3834         register_expression_parser(parse_UNEXPR_DEREFERENCE,      '*',          25);
3835         register_expression_parser(parse_UNEXPR_TAKE_ADDRESS,     '&',          25);
3836         register_expression_parser(parse_UNEXPR_PREFIX_INCREMENT, T_PLUSPLUS,   25);
3837         register_expression_parser(parse_UNEXPR_PREFIX_DECREMENT, T_MINUSMINUS, 25);
3838         register_expression_parser(parse_sizeof,                  T_sizeof,     25);
3839         register_expression_parser(parse_extension,            T___extension__, 25);
3840         register_expression_parser(parse_builtin_classify_type,
3841                                                      T___builtin_classify_type, 25);
3842 }
3843
3844
3845 static statement_t *parse_case_statement(void)
3846 {
3847         eat(T_case);
3848         case_label_statement_t *label = allocate_ast_zero(sizeof(label[0]));
3849         label->statement.type            = STATEMENT_CASE_LABEL;
3850         label->statement.source_position = token.source_position;
3851
3852         label->expression = parse_expression();
3853
3854         expect(':');
3855         label->label_statement = parse_statement();
3856
3857         return (statement_t*) label;
3858 }
3859
3860 static statement_t *parse_default_statement(void)
3861 {
3862         eat(T_default);
3863
3864         case_label_statement_t *label = allocate_ast_zero(sizeof(label[0]));
3865         label->statement.type            = STATEMENT_CASE_LABEL;
3866         label->statement.source_position = token.source_position;
3867
3868         expect(':');
3869         label->label_statement = parse_statement();
3870
3871         return (statement_t*) label;
3872 }
3873
3874 static declaration_t *get_label(symbol_t *symbol)
3875 {
3876         declaration_t *candidate = get_declaration(symbol, NAMESPACE_LABEL);
3877         assert(current_function != NULL);
3878         /* if we found a label in the same function, then we already created the
3879          * declaration */
3880         if(candidate != NULL
3881                         && candidate->parent_context == &current_function->context) {
3882                 return candidate;
3883         }
3884
3885         /* otherwise we need to create a new one */
3886         declaration_t *declaration = allocate_ast_zero(sizeof(declaration[0]));
3887         declaration->namespc     = NAMESPACE_LABEL;
3888         declaration->symbol        = symbol;
3889
3890         label_push(declaration);
3891
3892         return declaration;
3893 }
3894
3895 static statement_t *parse_label_statement(void)
3896 {
3897         assert(token.type == T_IDENTIFIER);
3898         symbol_t *symbol = token.v.symbol;
3899         next_token();
3900
3901         declaration_t *label = get_label(symbol);
3902
3903         /* if source position is already set then the label is defined twice,
3904          * otherwise it was just mentioned in a goto so far */
3905         if(label->source_position.input_name != NULL) {
3906                 parser_print_error_prefix();
3907                 fprintf(stderr, "duplicate label '%s'\n", symbol->string);
3908                 parser_print_error_prefix_pos(label->source_position);
3909                 fprintf(stderr, "previous definition of '%s' was here\n",
3910                         symbol->string);
3911         } else {
3912                 label->source_position = token.source_position;
3913         }
3914
3915         label_statement_t *label_statement = allocate_ast_zero(sizeof(label[0]));
3916
3917         label_statement->statement.type            = STATEMENT_LABEL;
3918         label_statement->statement.source_position = token.source_position;
3919         label_statement->label                     = label;
3920
3921         expect(':');
3922
3923         if(token.type == '}') {
3924                 parse_error("label at end of compound statement");
3925                 return (statement_t*) label_statement;
3926         } else {
3927                 label_statement->label_statement = parse_statement();
3928         }
3929
3930         return (statement_t*) label_statement;
3931 }
3932
3933 static statement_t *parse_if(void)
3934 {
3935         eat(T_if);
3936
3937         if_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
3938         statement->statement.type            = STATEMENT_IF;
3939         statement->statement.source_position = token.source_position;
3940
3941         expect('(');
3942         statement->condition = parse_expression();
3943         expect(')');
3944
3945         statement->true_statement = parse_statement();
3946         if(token.type == T_else) {
3947                 next_token();
3948                 statement->false_statement = parse_statement();
3949         }
3950
3951         return (statement_t*) statement;
3952 }
3953
3954 static statement_t *parse_switch(void)
3955 {
3956         eat(T_switch);
3957
3958         switch_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
3959         statement->statement.type            = STATEMENT_SWITCH;
3960         statement->statement.source_position = token.source_position;
3961
3962         expect('(');
3963         statement->expression = parse_expression();
3964         expect(')');
3965         statement->body = parse_statement();
3966
3967         return (statement_t*) statement;
3968 }
3969
3970 static statement_t *parse_while(void)
3971 {
3972         eat(T_while);
3973
3974         while_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
3975         statement->statement.type            = STATEMENT_WHILE;
3976         statement->statement.source_position = token.source_position;
3977
3978         expect('(');
3979         statement->condition = parse_expression();
3980         expect(')');
3981         statement->body = parse_statement();
3982
3983         return (statement_t*) statement;
3984 }
3985
3986 static statement_t *parse_do(void)
3987 {
3988         eat(T_do);
3989
3990         do_while_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
3991         statement->statement.type            = STATEMENT_DO_WHILE;
3992         statement->statement.source_position = token.source_position;
3993
3994         statement->body = parse_statement();
3995         expect(T_while);
3996         expect('(');
3997         statement->condition = parse_expression();
3998         expect(')');
3999         expect(';');
4000
4001         return (statement_t*) statement;
4002 }
4003
4004 static statement_t *parse_for(void)
4005 {
4006         eat(T_for);
4007
4008         for_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
4009         statement->statement.type            = STATEMENT_FOR;
4010         statement->statement.source_position = token.source_position;
4011
4012         expect('(');
4013
4014         int         top          = environment_top();
4015         context_t  *last_context = context;
4016         set_context(&statement->context);
4017
4018         if(token.type != ';') {
4019                 if(is_declaration_specifier(&token, false)) {
4020                         parse_declaration();
4021                 } else {
4022                         statement->initialisation = parse_expression();
4023                         expect(';');
4024                 }
4025         } else {
4026                 expect(';');
4027         }
4028
4029         if(token.type != ';') {
4030                 statement->condition = parse_expression();
4031         }
4032         expect(';');
4033         if(token.type != ')') {
4034                 statement->step = parse_expression();
4035         }
4036         expect(')');
4037         statement->body = parse_statement();
4038
4039         assert(context == &statement->context);
4040         set_context(last_context);
4041         environment_pop_to(top);
4042
4043         return (statement_t*) statement;
4044 }
4045
4046 static statement_t *parse_goto(void)
4047 {
4048         eat(T_goto);
4049
4050         if(token.type != T_IDENTIFIER) {
4051                 parse_error_expected("while parsing goto", T_IDENTIFIER, 0);
4052                 eat_statement();
4053                 return NULL;
4054         }
4055         symbol_t *symbol = token.v.symbol;
4056         next_token();
4057
4058         declaration_t *label = get_label(symbol);
4059
4060         goto_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
4061
4062         statement->statement.type            = STATEMENT_GOTO;
4063         statement->statement.source_position = token.source_position;
4064
4065         statement->label = label;
4066
4067         expect(';');
4068
4069         return (statement_t*) statement;
4070 }
4071
4072 static statement_t *parse_continue(void)
4073 {
4074         eat(T_continue);
4075         expect(';');
4076
4077         statement_t *statement     = allocate_ast_zero(sizeof(statement[0]));
4078         statement->type            = STATEMENT_CONTINUE;
4079         statement->source_position = token.source_position;
4080
4081         return statement;
4082 }
4083
4084 static statement_t *parse_break(void)
4085 {
4086         eat(T_break);
4087         expect(';');
4088
4089         statement_t *statement     = allocate_ast_zero(sizeof(statement[0]));
4090         statement->type            = STATEMENT_BREAK;
4091         statement->source_position = token.source_position;
4092
4093         return statement;
4094 }
4095
4096 static statement_t *parse_return(void)
4097 {
4098         eat(T_return);
4099
4100         return_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
4101
4102         statement->statement.type            = STATEMENT_RETURN;
4103         statement->statement.source_position = token.source_position;
4104
4105         assert(current_function->type->type == TYPE_FUNCTION);
4106         function_type_t *function_type = (function_type_t*) current_function->type;
4107         type_t          *return_type   = function_type->result_type;
4108
4109         expression_t *return_value;
4110         if(token.type != ';') {
4111                 return_value = parse_expression();
4112
4113                 if(return_type == type_void && return_value->datatype != type_void) {
4114                         parse_warning("'return' with a value, in function returning void");
4115                         return_value = NULL;
4116                 } else {
4117                         if(return_type != NULL) {
4118                                 semantic_assign(return_type, &return_value, "'return'");
4119                         }
4120                 }
4121         } else {
4122                 return_value = NULL;
4123                 if(return_type != type_void) {
4124                         parse_warning("'return' without value, in function returning "
4125                                       "non-void");
4126                 }
4127         }
4128         statement->return_value = return_value;
4129
4130         expect(';');
4131
4132         return (statement_t*) statement;
4133 }
4134
4135 static statement_t *parse_declaration_statement(void)
4136 {
4137         declaration_t *before = last_declaration;
4138
4139         declaration_statement_t *statement
4140                 = allocate_ast_zero(sizeof(statement[0]));
4141         statement->statement.type            = STATEMENT_DECLARATION;
4142         statement->statement.source_position = token.source_position;
4143
4144         declaration_specifiers_t specifiers;
4145         memset(&specifiers, 0, sizeof(specifiers));
4146         parse_declaration_specifiers(&specifiers);
4147
4148         if(token.type == ';') {
4149                 eat(';');
4150         } else {
4151                 parse_init_declarators(&specifiers);
4152         }
4153
4154         if(before == NULL) {
4155                 statement->declarations_begin = context->declarations;
4156         } else {
4157                 statement->declarations_begin = before->next;
4158         }
4159         statement->declarations_end = last_declaration;
4160
4161         return (statement_t*) statement;
4162 }
4163
4164 static statement_t *parse_expression_statement(void)
4165 {
4166         expression_statement_t *statement = allocate_ast_zero(sizeof(statement[0]));
4167         statement->statement.type            = STATEMENT_EXPRESSION;
4168         statement->statement.source_position = token.source_position;
4169
4170         statement->expression = parse_expression();
4171
4172         expect(';');
4173
4174         return (statement_t*) statement;
4175 }
4176
4177 static statement_t *parse_statement(void)
4178 {
4179         statement_t   *statement = NULL;
4180
4181         /* declaration or statement */
4182         switch(token.type) {
4183         case T_case:
4184                 statement = parse_case_statement();
4185                 break;
4186
4187         case T_default:
4188                 statement = parse_default_statement();
4189                 break;
4190
4191         case '{':
4192                 statement = parse_compound_statement();
4193                 break;
4194
4195         case T_if:
4196                 statement = parse_if();
4197                 break;
4198
4199         case T_switch:
4200                 statement = parse_switch();
4201                 break;
4202
4203         case T_while:
4204                 statement = parse_while();
4205                 break;
4206
4207         case T_do:
4208                 statement = parse_do();
4209                 break;
4210
4211         case T_for:
4212                 statement = parse_for();
4213                 break;
4214
4215         case T_goto:
4216                 statement = parse_goto();
4217                 break;
4218
4219         case T_continue:
4220                 statement = parse_continue();
4221                 break;
4222
4223         case T_break:
4224                 statement = parse_break();
4225                 break;
4226
4227         case T_return:
4228                 statement = parse_return();
4229                 break;
4230
4231         case ';':
4232                 next_token();
4233                 statement = NULL;
4234                 break;
4235
4236         case T_IDENTIFIER:
4237                 if(look_ahead(1)->type == ':') {
4238                         statement = parse_label_statement();
4239                         break;
4240                 }
4241
4242                 if(is_typedef_symbol(token.v.symbol)) {
4243                         statement = parse_declaration_statement();
4244                         break;
4245                 }
4246
4247                 statement = parse_expression_statement();
4248                 break;
4249
4250         case T___extension__:
4251                 /* this can be a prefix to a declaration or an expression statement */
4252                 /* we simply eat it now and parse the rest with tail recursion */
4253                 do {
4254                         next_token();
4255                 } while(token.type == T___extension__);
4256                 statement = parse_statement();
4257                 break;
4258
4259         DECLARATION_START
4260                 statement = parse_declaration_statement();
4261                 break;
4262
4263         default:
4264                 statement = parse_expression_statement();
4265                 break;
4266         }
4267
4268         assert(statement == NULL || statement->source_position.input_name != NULL);
4269
4270         return statement;
4271 }
4272
4273 static statement_t *parse_compound_statement(void)
4274 {
4275         compound_statement_t *compound_statement
4276                 = allocate_ast_zero(sizeof(compound_statement[0]));
4277         compound_statement->statement.type            = STATEMENT_COMPOUND;
4278         compound_statement->statement.source_position = token.source_position;
4279
4280         eat('{');
4281
4282         int        top          = environment_top();
4283         context_t *last_context = context;
4284         set_context(&compound_statement->context);
4285
4286         statement_t *last_statement = NULL;
4287
4288         while(token.type != '}' && token.type != T_EOF) {
4289                 statement_t *statement = parse_statement();
4290                 if(statement == NULL)
4291                         continue;
4292
4293                 if(last_statement != NULL) {
4294                         last_statement->next = statement;
4295                 } else {
4296                         compound_statement->statements = statement;
4297                 }
4298
4299                 while(statement->next != NULL)
4300                         statement = statement->next;
4301
4302                 last_statement = statement;
4303         }
4304
4305         if(token.type != '}') {
4306                 parser_print_error_prefix_pos(
4307                                 compound_statement->statement.source_position);
4308                 fprintf(stderr, "end of file while looking for closing '}'\n");
4309         }
4310         next_token();
4311
4312         assert(context == &compound_statement->context);
4313         set_context(last_context);
4314         environment_pop_to(top);
4315
4316         return (statement_t*) compound_statement;
4317 }
4318
4319 static translation_unit_t *parse_translation_unit(void)
4320 {
4321         translation_unit_t *unit = allocate_ast_zero(sizeof(unit[0]));
4322
4323         assert(global_context == NULL);
4324         global_context = &unit->context;
4325
4326         assert(context == NULL);
4327         set_context(&unit->context);
4328
4329         while(token.type != T_EOF) {
4330                 parse_declaration();
4331         }
4332
4333         assert(context == &unit->context);
4334         context          = NULL;
4335         last_declaration = NULL;
4336
4337         assert(global_context == &unit->context);
4338         global_context = NULL;
4339
4340         return unit;
4341 }
4342
4343 translation_unit_t *parse(void)
4344 {
4345         environment_stack = NEW_ARR_F(stack_entry_t, 0);
4346         label_stack       = NEW_ARR_F(stack_entry_t, 0);
4347         found_error       = false;
4348
4349         type_set_output(stderr);
4350         ast_set_output(stderr);
4351
4352         lookahead_bufpos = 0;
4353         for(int i = 0; i < MAX_LOOKAHEAD + 2; ++i) {
4354                 next_token();
4355         }
4356         translation_unit_t *unit = parse_translation_unit();
4357
4358         DEL_ARR_F(environment_stack);
4359         DEL_ARR_F(label_stack);
4360
4361         if(found_error)
4362                 return NULL;
4363
4364         return unit;
4365 }
4366
4367 void init_parser(void)
4368 {
4369         init_expression_parsers();
4370         obstack_init(&temp_obst);
4371
4372         type_int         = make_atomic_type(ATOMIC_TYPE_INT, 0);
4373         type_uint        = make_atomic_type(ATOMIC_TYPE_UINT, 0);
4374         type_long_double = make_atomic_type(ATOMIC_TYPE_LONG_DOUBLE, 0);
4375         type_double      = make_atomic_type(ATOMIC_TYPE_DOUBLE, 0);
4376         type_float       = make_atomic_type(ATOMIC_TYPE_FLOAT, 0);
4377         type_size_t      = make_atomic_type(ATOMIC_TYPE_ULONG, 0);
4378         type_ptrdiff_t   = make_atomic_type(ATOMIC_TYPE_LONG, 0);
4379         type_const_char  = make_atomic_type(ATOMIC_TYPE_CHAR, TYPE_QUALIFIER_CONST);
4380         type_void        = make_atomic_type(ATOMIC_TYPE_VOID, 0);
4381         type_void_ptr    = make_pointer_type(type_void, 0);
4382         type_string      = make_pointer_type(type_const_char, 0);
4383 }
4384
4385 void exit_parser(void)
4386 {
4387         obstack_free(&temp_obst, NULL);
4388 }