nsz Git - cparser/blob - parser.c

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