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