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