nsz Git - cparser/blob - parser.c

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