nsz Git - cparser/blob - parser.c

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