nsz Git - cparser/blob - parser.c

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