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