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