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