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