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