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