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