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