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