nsz Git - cparser/blob - parser.c

   1 #include <config.h>
   2
   3 #include <assert.h>
   4 #include <stdarg.h>
   5
   6 #include "lexer_t.h"
   7 #include "token_t.h"
   8 #include "type_t.h"
   9 #include "type_hash.h"
  10 #include "ast_t.h"
  11 #include "adt/bitfiddle.h"
  12 #include "adt/error.h"
  13
  14 #define PRINT_TOKENS
  15
  16 static token_t token;
  17
  18 static inline
  19 void *allocate_ast_zero(size_t size)
  20 {
  21         void *res = allocate_ast(size);
  22         memset(res, 0, size);
  23         return res;
  24 }
  25
  26 static inline
  27 void next_token(void)
  28 {
  29         lexer_next_token(&token);
  30
  31 #ifdef PRINT_TOKENS
  32         print_token(stderr, &token);
  33         fprintf(stderr, "\n");
  34 #endif
  35 }
  36
  37 static inline
  38 void eat(token_type_t type)
  39 {
  40         assert(token.type == type);
  41         next_token();
  42 }
  43
  44 void parser_print_error_prefix(void)
  45 {
  46     fputs(source_position.input_name, stderr);
  47     fputc(':', stderr);
  48     fprintf(stderr, "%d", source_position.linenr);
  49     fputs(": error: ", stderr);
  50 }
  51
  52 static
  53 void parse_error(const char *message)
  54 {
  55         parser_print_error_prefix();
  56         fprintf(stderr, "parse error: %s\n", message);
  57 }
  58
  59 static
  60 void parse_error_expected(const char *message, ...)
  61 {
  62         va_list args;
  63         int first = 1;
  64
  65         if(message != NULL) {
  66                 parser_print_error_prefix();
  67                 fprintf(stderr, "%s\n", message);
  68         }
  69         parser_print_error_prefix();
  70         fputs("Parse error: got ", stderr);
  71         print_token(stderr, &token);
  72         fputs(", expected ", stderr);
  73
  74         va_start(args, message);
  75         token_type_t token_type = va_arg(args, token_type_t);
  76         while(token_type != 0) {
  77                 if(first == 1) {
  78                         first = 0;
  79                 } else {
  80                         fprintf(stderr, ", ");
  81                 }
  82                 print_token_type(stderr, token_type);
  83                 token_type = va_arg(args, token_type_t);
  84         }
  85         va_end(args);
  86         fprintf(stderr, "\n");
  87 }
  88
  89 static
  90 void eat_until_semi(void)
  91 {
  92         while(token.type != ';') {
  93                 next_token();
  94                 if(token.type == T_EOF)
  95                         return;
  96         }
  97         next_token();
  98 }
  99
 100 #define expect(expected)                           \
 101     if(UNLIKELY(token.type != (expected))) {       \
 102         parse_error_expected(NULL, (expected), 0); \
 103         eat_until_semi();                          \
 104         return NULL;                               \
 105     }                                              \
 106     next_token();
 107
 108 #define expect_void(expected)                      \
 109     if(UNLIKELY(token.type != (expected))) {       \
 110         parse_error_expected(NULL, (expected), 0); \
 111         eat_until_semi();                          \
 112         return;                                    \
 113     }                                              \
 114     next_token();
 115
 116
 117 typedef enum {
 118         SPECIFIER_SIGNED    = 1 << 0,
 119         SPECIFIER_UNSIGNED  = 1 << 1,
 120         SPECIFIER_LONG      = 1 << 2,
 121         SPECIFIER_INT       = 1 << 3,
 122         SPECIFIER_DOUBLE    = 1 << 4,
 123         SPECIFIER_CHAR      = 1 << 5,
 124         SPECIFIER_SHORT     = 1 << 6,
 125         SPECIFIER_LONG_LONG = 1 << 7,
 126         SPECIFIER_FLOAT     = 1 << 8,
 127         SPECIFIER_BOOL      = 1 << 9,
 128         SPECIFIER_VOID      = 1 << 10,
 129 #ifdef PROVIDE_COMPLEX
 130         SPECIFIER_COMPLEX   = 1 << 11,
 131 #endif
 132 #ifdef PROVIDE_IMAGINARY
 133         SPECIFIER_IMAGINARY = 1 << 12,
 134 #endif
 135 } specifiers_t;
 136
 137 typedef enum {
 138         STORAGE_CLASS_NONE,
 139         STORAGE_CLASS_TYPEDEF,
 140         STORAGE_CLASS_EXTERN,
 141         STORAGE_CLASS_STATIC,
 142         STORAGE_CLASS_AUTO,
 143         STORAGE_CLASS_REGISTER
 144 } storage_class_t;
 145
 146 typedef struct declaration_specifiers_t  declaration_specifiers_t;
 147 struct declaration_specifiers_t {
 148         storage_class_t  storage_class;
 149         type_t          *type;
 150 };
 151
 152 static
 153 void parse_declaration_specifiers(declaration_specifiers_t *specifiers)
 154 {
 155         type_type_t        type_type       = TYPE_INVALID;
 156         atomic_type_type_t atomic_type     = ATOMIC_TYPE_INVALID;
 157         unsigned           type_qualifiers = 0;
 158         unsigned           type_specifiers = 0;
 159
 160         while(1) {
 161                 switch(token.type) {
 162
 163                 /* storage class */
 164 #define MATCH_STORAGE_CLASS(token, class)                                \
 165                 case token:                                                      \
 166                         if(specifiers->storage_class != STORAGE_CLASS_NONE) {        \
 167                                 parse_error("multiple storage classes in declaration "   \
 168                                             "specifiers");                               \
 169                         }                                                            \
 170                         specifiers->storage_class = class;                           \
 171                         next_token();                                                \
 172                         break;
 173
 174                 MATCH_STORAGE_CLASS(T_typedef,  STORAGE_CLASS_TYPEDEF)
 175                 MATCH_STORAGE_CLASS(T_extern,   STORAGE_CLASS_EXTERN)
 176                 MATCH_STORAGE_CLASS(T_static,   STORAGE_CLASS_STATIC)
 177                 MATCH_STORAGE_CLASS(T_auto,     STORAGE_CLASS_AUTO)
 178                 MATCH_STORAGE_CLASS(T_register, STORAGE_CLASS_REGISTER)
 179
 180                 /* type qualifiers */
 181 #define MATCH_TYPE_QUALIFIER(token, qualifier)                          \
 182                 case token:                                                     \
 183                         type_qualifiers |= qualifier;                               \
 184                         next_token();                                               \
 185                         break;
 186
 187                 MATCH_TYPE_QUALIFIER(T_const,    TYPE_QUALIFIER_CONST);
 188                 MATCH_TYPE_QUALIFIER(T_restrict, TYPE_QUALIFIER_RESTRICT);
 189                 MATCH_TYPE_QUALIFIER(T_volatile, TYPE_QUALIFIER_VOLATILE);
 190                 MATCH_TYPE_QUALIFIER(T_inline,   TYPE_QUALIFIER_INLINE);
 191
 192                 /* type specifiers */
 193 #define MATCH_SPECIFIER(token, specifier, name)                         \
 194                 case token:                                                     \
 195                         next_token();                                               \
 196                         if(type_specifiers & specifier) {                           \
 197                                 parse_error("multiple " name " type specifiers given"); \
 198                         } else {                                                    \
 199                                 type_specifiers |= specifier;                           \
 200                         }                                                           \
 201                         break;
 202
 203                 MATCH_SPECIFIER(T_void,       SPECIFIER_VOID,      "void")
 204                 MATCH_SPECIFIER(T_char,       SPECIFIER_CHAR,      "char")
 205                 MATCH_SPECIFIER(T_short,      SPECIFIER_SHORT,     "short")
 206                 MATCH_SPECIFIER(T_int,        SPECIFIER_INT,       "int")
 207                 MATCH_SPECIFIER(T_float,      SPECIFIER_FLOAT,     "float")
 208                 MATCH_SPECIFIER(T_double,     SPECIFIER_DOUBLE,    "double")
 209                 MATCH_SPECIFIER(T_signed,     SPECIFIER_SIGNED,    "signed")
 210                 MATCH_SPECIFIER(T_unsigned,   SPECIFIER_UNSIGNED,  "unsigned")
 211                 MATCH_SPECIFIER(T__Bool,      SPECIFIER_BOOL,      "_Bool")
 212 #ifdef PROVIDE_COMPLEX
 213                 MATCH_SPECIFIER(T__Complex,   SPECIFIER_COMPLEX,   "_Complex")
 214 #endif
 215 #ifdef PROVIDE_IMAGINARY
 216                 MATCH_SPECIFIER(T__Imaginary, SPECIFIER_IMAGINARY, "_Imaginary")
 217 #endif
 218                 case T_long:
 219                         next_token();
 220                         if(type_specifiers & SPECIFIER_LONG_LONG) {
 221                                 parse_error("too many long type specifiers given");
 222                         } else if(type_specifiers & SPECIFIER_LONG) {
 223                                 type_specifiers |= SPECIFIER_LONG_LONG;
 224                         } else {
 225                                 type_specifiers |= SPECIFIER_LONG;
 226                         }
 227                         break;
 228
 229                 case T_struct:
 230                 case T_enum:
 231                         /* TODO */
 232                         assert(0);
 233                         break;
 234
 235                 /* function specifier */
 236                 default:
 237                         goto finish_specifiers;
 238                 }
 239         }
 240
 241 finish_specifiers:
 242         if(type_type == TYPE_INVALID) {
 243                 /* match valid basic types */
 244                 switch(type_specifiers) {
 245                 case SPECIFIER_VOID:
 246                         atomic_type = ATOMIC_TYPE_VOID;
 247                         break;
 248                 case SPECIFIER_CHAR:
 249                         atomic_type = ATOMIC_TYPE_CHAR;
 250                         break;
 251                 case SPECIFIER_SIGNED | SPECIFIER_CHAR:
 252                         atomic_type = ATOMIC_TYPE_SCHAR;
 253                         break;
 254                 case SPECIFIER_UNSIGNED | SPECIFIER_CHAR:
 255                         atomic_type = ATOMIC_TYPE_UCHAR;
 256                         break;
 257                 case SPECIFIER_SHORT:
 258                 case SPECIFIER_SIGNED | SPECIFIER_SHORT:
 259                 case SPECIFIER_SHORT | SPECIFIER_INT:
 260                 case SPECIFIER_SIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
 261                         atomic_type = ATOMIC_TYPE_SHORT;
 262                         break;
 263                 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT:
 264                 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
 265                         atomic_type = ATOMIC_TYPE_USHORT;
 266                         break;
 267                 case SPECIFIER_INT:
 268                 case SPECIFIER_SIGNED:
 269                 case SPECIFIER_SIGNED | SPECIFIER_INT:
 270                         atomic_type = ATOMIC_TYPE_INT;
 271                         break;
 272                 case SPECIFIER_UNSIGNED:
 273                 case SPECIFIER_UNSIGNED | SPECIFIER_INT:
 274                         atomic_type = ATOMIC_TYPE_UINT;
 275                         break;
 276                 case SPECIFIER_LONG:
 277                 case SPECIFIER_SIGNED | SPECIFIER_LONG:
 278                 case SPECIFIER_LONG | SPECIFIER_INT:
 279                 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_INT:
 280                         atomic_type = ATOMIC_TYPE_LONG;
 281                         break;
 282                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG:
 283                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_INT:
 284                         atomic_type = ATOMIC_TYPE_ULONG;
 285                         break;
 286                 case SPECIFIER_LONG_LONG:
 287                 case SPECIFIER_SIGNED | SPECIFIER_LONG_LONG:
 288                 case SPECIFIER_LONG_LONG | SPECIFIER_INT:
 289                 case SPECIFIER_SIGNED | SPECIFIER_LONG_LONG | SPECIFIER_INT:
 290                         atomic_type = ATOMIC_TYPE_LONGLONG;
 291                         break;
 292                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG_LONG:
 293                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG_LONG | SPECIFIER_INT:
 294                         atomic_type = ATOMIC_TYPE_ULONGLONG;
 295                         break;
 296                 case SPECIFIER_FLOAT:
 297                         atomic_type = ATOMIC_TYPE_FLOAT;
 298                         break;
 299                 case SPECIFIER_DOUBLE:
 300                         atomic_type = ATOMIC_TYPE_DOUBLE;
 301                         break;
 302                 case SPECIFIER_LONG | SPECIFIER_DOUBLE:
 303                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE;
 304                         break;
 305                 case SPECIFIER_BOOL:
 306                         atomic_type = ATOMIC_TYPE_BOOL;
 307                         break;
 308 #ifdef PROVIDE_COMPLEX
 309                 case SPECIFIER_FLOAT | SPECIFIER_COMPLEX:
 310                         atomic_type = ATOMIC_TYPE_FLOAT_COMPLEX;
 311                         break;
 312                 case SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
 313                         atomic_type = ATOMIC_TYPE_DOUBLE_COMPLEX;
 314                         break;
 315                 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
 316                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE_COMPLEX;
 317                         break;
 318 #endif
 319 #ifdef PROVIDE_IMAGINARY
 320                 case SPECIFIER_FLOAT | SPECIFIER_IMAGINARY:
 321                         atomic_type = ATOMIC_TYPE_FLOAT_IMAGINARY;
 322                         break;
 323                 case SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
 324                         atomic_type = ATOMIC_TYPE_DOUBLE_IMAGINARY;
 325                         break;
 326                 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
 327                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY;
 328                         break;
 329 #endif
 330                 default:
 331                         /* invalid specifier combination, give an error message */
 332                         if(type_specifiers == 0) {
 333                                 parse_error("no type specifiers given in declaration");
 334                         } else if((type_specifiers & SPECIFIER_SIGNED) &&
 335                                   (type_specifiers & SPECIFIER_UNSIGNED)) {
 336                                 parse_error("signed and unsigned specifiers gives");
 337                         } else if(type_specifiers & (SPECIFIER_SIGNED | SPECIFIER_UNSIGNED)) {
 338                                 parse_error("only integer types can be signed or unsigned");
 339                         } else {
 340                                 parse_error("multiple datatypes in declaration");
 341                         }
 342                         atomic_type = ATOMIC_TYPE_INVALID;
 343                 }
 344
 345                 atomic_type_t *type = obstack_alloc(type_obst, sizeof(type[0]));
 346                 memset(type, 0, sizeof(type[0]));
 347                 type->type.type       = TYPE_ATOMIC;
 348                 type->type.qualifiers = type_qualifiers;
 349                 type->atype           = atomic_type;
 350
 351                 type_t *result = typehash_insert((type_t*) type);
 352                 if(result != (type_t*) type) {
 353                         obstack_free(type_obst, type);
 354                 }
 355
 356                 specifiers->type = result;
 357
 358                 fprintf(stderr, "Specifiers type: ");
 359                 print_type(stderr, result);
 360                 fprintf(stderr, "\n");
 361         } else {
 362                 if(type_specifiers != 0) {
 363                         parse_error("multiple datatypes in declaration");
 364                 }
 365         }
 366 }
 367
 368 static
 369 unsigned parse_type_qualifiers()
 370 {
 371         unsigned type_qualifiers = 0;
 372
 373         while(1) {
 374                 switch(token.type) {
 375                 /* type qualifiers */
 376                 MATCH_TYPE_QUALIFIER(T_const,    TYPE_QUALIFIER_CONST);
 377                 MATCH_TYPE_QUALIFIER(T_restrict, TYPE_QUALIFIER_RESTRICT);
 378                 MATCH_TYPE_QUALIFIER(T_volatile, TYPE_QUALIFIER_VOLATILE);
 379                 MATCH_TYPE_QUALIFIER(T_inline,   TYPE_QUALIFIER_INLINE);
 380
 381                 default:
 382                         return type_qualifiers;
 383                 }
 384         }
 385 }
 386
 387 static
 388 void parse_declarator(const declaration_specifiers_t *specifiers)
 389 {
 390         type_t *type = specifiers->type;
 391
 392         while(token.type == '*') {
 393                 /* pointer */
 394                 next_token();
 395
 396                 pointer_type_t *pointer_type
 397                         = obstack_alloc(type_obst, sizeof(pointer_type[0]));
 398                 memset(pointer_type, 0, sizeof(pointer_type[0]));
 399                 pointer_type->type.type = TYPE_POINTER;
 400                 pointer_type->points_to = type;
 401
 402                 pointer_type->type.qualifiers = parse_type_qualifiers();
 403
 404                 type_t *result = typehash_insert((type_t*) pointer_type);
 405                 if(result != (type_t*) pointer_type) {
 406                         obstack_free(type_obst, pointer_type);
 407                 }
 408
 409                 type = result;
 410         }
 411
 412         switch(token.type) {
 413         case T_IDENTIFIER:
 414                 (void) token.v.symbol;
 415                 next_token();
 416                 break;
 417         case '(':
 418                 next_token();
 419                 parse_declarator(specifiers);
 420                 expect_void(')');
 421                 return;
 422         default:
 423                 parse_error("problem while parsing declarator");
 424         }
 425
 426         if(token.type == '(') {
 427                 next_token();
 428
 429                 /* parse parameter-type-list or identifier-list */
 430
 431                 expect_void(')');
 432         } else if(token.type == '[') {
 433                 next_token();
 434
 435                 /* multiple type qualifiers, and static */
 436
 437                 /* assignment_expression or '*' or nothing */
 438
 439                 expect_void(']');
 440         }
 441
 442         fprintf(stderr, "Declarator type: ");
 443         print_type(stderr, type);
 444         fprintf(stderr, "\n");
 445 }
 446
 447 void parse_init_declarators(const declaration_specifiers_t *specifiers)
 448 {
 449         parse_declarator(specifiers);
 450         if(token.type == '=') {
 451                 next_token();
 452                 //parse_initialize();
 453         }
 454 }
 455
 456 void parse_declaration(void)
 457 {
 458         declaration_specifiers_t specifiers;
 459         memset(&specifiers, 0, sizeof(specifiers));
 460         parse_declaration_specifiers(&specifiers);
 461
 462         parse_init_declarators(&specifiers);
 463 }
 464
 465
 466
 467 static
 468 expression_t *parse_sub_expression(unsigned precedence);
 469 static
 470 expression_t *parse_expression(void);
 471
 472 typedef expression_t* (*parse_expression_function) (unsigned precedence);
 473 typedef expression_t* (*parse_expression_infix_function) (unsigned precedence,
 474                                                           expression_t *left);
 475
 476 typedef struct expression_parser_function_t expression_parser_function_t;
 477 struct expression_parser_function_t {
 478         unsigned                         precedence;
 479         parse_expression_function        parser;
 480         unsigned                         infix_precedence;
 481         parse_expression_infix_function  infix_parser;
 482 };
 483
 484 expression_parser_function_t expression_parsers[T_LAST_TOKEN];
 485
 486 static
 487 expression_t *expected_expression_error(void)
 488 {
 489         parser_print_error_prefix();
 490         fprintf(stderr, "expected expression, got token ");
 491         print_token(stderr, & token);
 492         fprintf(stderr, "\n");
 493
 494         expression_t *expression = allocate_ast_zero(sizeof(expression[0]));
 495         expression->type = EXPR_INVALID;
 496         next_token();
 497
 498         return expression;
 499 }
 500
 501 static
 502 expression_t *parse_string_const(void)
 503 {
 504         string_literal_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
 505
 506         cnst->expression.type = EXPR_STRING_LITERAL;
 507         cnst->value           = token.v.string;
 508
 509         next_token();
 510
 511         return (expression_t*) cnst;
 512 }
 513
 514 static
 515 expression_t *parse_int_const(void)
 516 {
 517         const_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
 518
 519         cnst->expression.type = EXPR_CONST;
 520         cnst->value           = token.v.intvalue;
 521
 522         next_token();
 523
 524         return (expression_t*) cnst;
 525 }
 526
 527 static
 528 expression_t *parse_reference(void)
 529 {
 530         reference_expression_t *ref = allocate_ast_zero(sizeof(ref[0]));
 531
 532         ref->expression.type            = EXPR_REFERENCE;
 533         ref->symbol                     = token.v.symbol;
 534
 535         next_token();
 536
 537         return (expression_t*) ref;
 538 }
 539
 540 static
 541 expression_t *parse_brace_expression(void)
 542 {
 543         eat('(');
 544
 545         expression_t *result = parse_expression();
 546         expect(')');
 547
 548         return result;
 549 }
 550
 551 static
 552 expression_t *parse_primary_expression(void)
 553 {
 554         switch(token.type) {
 555         case T_INTEGER:
 556                 return parse_int_const();
 557         case T_STRING_LITERAL:
 558                 return parse_string_const();
 559         case T_IDENTIFIER:
 560                 return parse_reference();
 561         case '(':
 562                 return parse_brace_expression();
 563         }
 564
 565         /* TODO: error message */
 566         return NULL;
 567 }
 568
 569 static
 570 expression_t *parse_array_expression(unsigned precedence,
 571                                      expression_t *array_ref)
 572 {
 573         (void) precedence;
 574
 575         eat('[');
 576
 577         array_access_expression_t *array_access
 578                 = allocate_ast_zero(sizeof(array_access[0]));
 579
 580         array_access->expression.type = EXPR_ARRAY_ACCESS;
 581         array_access->array_ref       = array_ref;
 582         array_access->index           = parse_expression();
 583
 584         if(token.type != ']') {
 585                 parse_error_expected("Problem while parsing array access", ']', 0);
 586                 return NULL;
 587         }
 588         next_token();
 589
 590         return (expression_t*) array_access;
 591 }
 592
 593 static
 594 expression_t *parse_sizeof(unsigned precedence)
 595 {
 596         (void) precedence;
 597         eat(T_sizeof);
 598         /* TODO... */
 599
 600         return NULL;
 601 }
 602
 603 static
 604 expression_t *parse_select_expression(unsigned precedence,
 605                                       expression_t *compound)
 606 {
 607         (void) precedence;
 608
 609         assert(token.type == '.' || token.type == T_SELECT);
 610         next_token();
 611
 612         select_expression_t *select = allocate_ast_zero(sizeof(select[0]));
 613
 614         select->expression.type = EXPR_SELECT;
 615         select->compound        = compound;
 616
 617         if(token.type != T_IDENTIFIER) {
 618                 parse_error_expected("Problem while parsing compound select",
 619                                      T_IDENTIFIER, 0);
 620                 return NULL;
 621         }
 622         select->symbol = token.v.symbol;
 623         next_token();
 624
 625         return (expression_t*) select;
 626 }
 627
 628 static
 629 expression_t *parse_call_expression(unsigned precedence,
 630                                     expression_t *expression)
 631 {
 632         (void) precedence;
 633         call_expression_t *call = allocate_ast_zero(sizeof(call[0]));
 634
 635         call->expression.type            = EXPR_CALL;
 636         call->method                     = expression;
 637
 638         /* parse arguments */
 639         eat('(');
 640
 641         if(token.type != ')') {
 642                 call_argument_t *last_argument = NULL;
 643
 644                 while(1) {
 645                         call_argument_t *argument = allocate_ast_zero(sizeof(argument[0]));
 646
 647                         argument->expression = parse_expression();
 648                         if(last_argument == NULL) {
 649                                 call->arguments = argument;
 650                         } else {
 651                                 last_argument->next = argument;
 652                         }
 653                         last_argument = argument;
 654
 655                         if(token.type != ',')
 656                                 break;
 657                         next_token();
 658                 }
 659         }
 660         expect(')');
 661
 662         return (expression_t*) call;
 663 }
 664
 665 #define CREATE_UNARY_EXPRESSION_PARSER(token_type, unexpression_type)     \
 666 static                                                                    \
 667 expression_t *parse_##unexpression_type(unsigned precedence)              \
 668 {                                                                         \
 669         eat(token_type);                                                      \
 670                                                                           \
 671         unary_expression_t *unary_expression                                  \
 672                 = allocate_ast_zero(sizeof(unary_expression[0]));                 \
 673         unary_expression->expression.type = EXPR_UNARY;                       \
 674         unary_expression->type            = unexpression_type;                \
 675         unary_expression->value           = parse_sub_expression(precedence); \
 676                                                                           \
 677         return (expression_t*) unary_expression;                              \
 678 }
 679
 680 CREATE_UNARY_EXPRESSION_PARSER('-', UNEXPR_NEGATE);
 681 CREATE_UNARY_EXPRESSION_PARSER('+', UNEXPR_PLUS);
 682 CREATE_UNARY_EXPRESSION_PARSER('!', UNEXPR_NOT);
 683 CREATE_UNARY_EXPRESSION_PARSER('*', UNEXPR_DEREFERENCE);
 684 CREATE_UNARY_EXPRESSION_PARSER('&', UNEXPR_TAKE_ADDRESS);
 685 CREATE_UNARY_EXPRESSION_PARSER('~', UNEXPR_BITWISE_NEGATE);
 686 CREATE_UNARY_EXPRESSION_PARSER(T_PLUSPLUS,   UNEXPR_PREFIX_INCREMENT);
 687 CREATE_UNARY_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_PREFIX_DECREMENT);
 688
 689 #define CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(token_type, unexpression_type) \
 690 static                                                                        \
 691 expression_t *parse_##unexpression_type(unsigned precedence,                  \
 692                                         expression_t *left)                   \
 693 {                                                                             \
 694         (void) precedence;                                                        \
 695         eat(token_type);                                                          \
 696                                                                               \
 697         unary_expression_t *unary_expression                                      \
 698                 = allocate_ast_zero(sizeof(unary_expression[0]));                     \
 699         unary_expression->expression.type = EXPR_UNARY;                           \
 700         unary_expression->type            = unexpression_type;                    \
 701         unary_expression->value           = left;                                 \
 702                                                                               \
 703         return (expression_t*) unary_expression;                                  \
 704 }
 705
 706 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_PLUSPLUS,   UNEXPR_POSTFIX_INCREMENT);
 707 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_POSTFIX_DECREMENT);
 708
 709 #define CREATE_BINEXPR_PARSER(token_type, binexpression_type)    \
 710 static                                                           \
 711 expression_t *parse_##binexpression_type(unsigned precedence,    \
 712                                          expression_t *left)     \
 713 {                                                                \
 714         eat(token_type);                                             \
 715                                                                  \
 716         expression_t *right = parse_sub_expression(precedence);      \
 717                                                                  \
 718         binary_expression_t *binexpr                                 \
 719                 = allocate_ast_zero(sizeof(binexpr[0]));                 \
 720         binexpr->expression.type            = EXPR_BINARY;           \
 721         binexpr->type                       = binexpression_type;    \
 722         binexpr->left                       = left;                  \
 723         binexpr->right                      = right;                 \
 724                                                                  \
 725         return (expression_t*) binexpr;                              \
 726 }
 727
 728 CREATE_BINEXPR_PARSER('*', BINEXPR_MUL);
 729 CREATE_BINEXPR_PARSER('/', BINEXPR_DIV);
 730 CREATE_BINEXPR_PARSER('+', BINEXPR_ADD);
 731 CREATE_BINEXPR_PARSER('-', BINEXPR_SUB);
 732 CREATE_BINEXPR_PARSER('<', BINEXPR_LESS);
 733 CREATE_BINEXPR_PARSER('>', BINEXPR_GREATER);
 734 CREATE_BINEXPR_PARSER('=', BINEXPR_ASSIGN);
 735 CREATE_BINEXPR_PARSER(T_EQUALEQUAL, BINEXPR_EQUAL);
 736 CREATE_BINEXPR_PARSER(T_SLASHEQUAL, BINEXPR_NOTEQUAL);
 737 CREATE_BINEXPR_PARSER(T_LESSEQUAL, BINEXPR_LESSEQUAL);
 738 CREATE_BINEXPR_PARSER(T_GREATEREQUAL, BINEXPR_GREATEREQUAL);
 739 CREATE_BINEXPR_PARSER('&', BINEXPR_BITWISE_AND);
 740 CREATE_BINEXPR_PARSER('|', BINEXPR_BITWISE_OR);
 741 CREATE_BINEXPR_PARSER('^', BINEXPR_BITWISE_XOR);
 742 CREATE_BINEXPR_PARSER(T_LESSLESS, BINEXPR_SHIFTLEFT);
 743 CREATE_BINEXPR_PARSER(T_GREATERGREATER, BINEXPR_SHIFTRIGHT);
 744
 745 static
 746 expression_t *parse_sub_expression(unsigned precedence)
 747 {
 748         if(token.type < 0) {
 749                 return expected_expression_error();
 750         }
 751
 752         expression_parser_function_t *parser
 753                 = &expression_parsers[token.type];
 754         source_position_t             source_position = source_position;
 755         expression_t                 *left;
 756
 757         if(parser->parser != NULL) {
 758                 left = parser->parser(parser->precedence);
 759         } else {
 760                 left = parse_primary_expression();
 761         }
 762         if(left != NULL)
 763                 left->source_position = source_position;
 764
 765         while(1) {
 766                 if(token.type < 0) {
 767                         return expected_expression_error();
 768                 }
 769
 770                 parser = &expression_parsers[token.type];
 771                 if(parser->infix_parser == NULL)
 772                         break;
 773                 if(parser->infix_precedence < precedence)
 774                         break;
 775
 776                 left = parser->infix_parser(parser->infix_precedence, left);
 777                 if(left != NULL)
 778                         left->source_position = source_position;
 779         }
 780
 781         return left;
 782 }
 783
 784 static
 785 expression_t *parse_expression(void)
 786 {
 787         return parse_sub_expression(1);
 788 }
 789
 790
 791
 792 void register_expression_parser(parse_expression_function parser,
 793                                 int token_type, unsigned precedence)
 794 {
 795         expression_parser_function_t *entry = &expression_parsers[token_type];
 796
 797         if(entry->parser != NULL) {
 798                 fprintf(stderr, "for token ");
 799                 print_token_type(stderr, token_type);
 800                 fprintf(stderr, "\n");
 801                 panic("trying to register multiple expression parsers for a token");
 802         }
 803         entry->parser     = parser;
 804         entry->precedence = precedence;
 805 }
 806
 807 void register_expression_infix_parser(parse_expression_infix_function parser,
 808                                       int token_type, unsigned precedence)
 809 {
 810         expression_parser_function_t *entry = &expression_parsers[token_type];
 811
 812         if(entry->infix_parser != NULL) {
 813                 fprintf(stderr, "for token ");
 814                 print_token_type(stderr, token_type);
 815                 fprintf(stderr, "\n");
 816                 panic("trying to register multiple infix expression parsers for a "
 817                       "token");
 818         }
 819         entry->infix_parser     = parser;
 820         entry->infix_precedence = precedence;
 821 }
 822
 823 static
 824 void init_expression_parsers(void)
 825 {
 826         memset(&expression_parsers, 0, sizeof(expression_parsers));
 827
 828         register_expression_infix_parser(parse_BINEXPR_MUL,       '*', 16);
 829         register_expression_infix_parser(parse_BINEXPR_DIV,       '/', 16);
 830         register_expression_infix_parser(parse_BINEXPR_SHIFTLEFT,
 831                                    T_LESSLESS, 16);
 832         register_expression_infix_parser(parse_BINEXPR_SHIFTRIGHT,
 833                                    T_GREATERGREATER, 16);
 834         register_expression_infix_parser(parse_BINEXPR_ADD,       '+', 15);
 835         register_expression_infix_parser(parse_BINEXPR_SUB,       '-', 15);
 836         register_expression_infix_parser(parse_BINEXPR_LESS,      '<', 14);
 837         register_expression_infix_parser(parse_BINEXPR_GREATER,   '>', 14);
 838         register_expression_infix_parser(parse_BINEXPR_LESSEQUAL, T_LESSEQUAL, 14);
 839         register_expression_infix_parser(parse_BINEXPR_GREATEREQUAL,
 840                                    T_GREATEREQUAL, 14);
 841         register_expression_infix_parser(parse_BINEXPR_EQUAL,     T_EQUALEQUAL, 13);
 842         register_expression_infix_parser(parse_BINEXPR_NOTEQUAL,
 843                                          T_EXCLAMATIONMARKEQUAL, 13);
 844         register_expression_infix_parser(parse_BINEXPR_BITWISE_AND, '&',        12);
 845         register_expression_infix_parser(parse_BINEXPR_BITWISE_XOR, '^',        11);
 846         register_expression_infix_parser(parse_BINEXPR_BITWISE_OR,  '|',        10);
 847         register_expression_infix_parser(parse_BINEXPR_ASSIGN,      T_EQUAL,     2);
 848
 849         register_expression_infix_parser(parse_array_expression,        '[',    30);
 850         register_expression_infix_parser(parse_call_expression,         '(',    30);
 851         register_expression_infix_parser(parse_select_expression,       '.',    30);
 852         register_expression_infix_parser(parse_select_expression,  T_SELECT,    30);
 853         register_expression_infix_parser(parse_UNEXPR_POSTFIX_INCREMENT,
 854                                          T_PLUSPLUS, 30);
 855         register_expression_infix_parser(parse_UNEXPR_POSTFIX_DECREMENT,
 856                                          T_MINUSMINUS, 30);
 857
 858         register_expression_parser(parse_UNEXPR_NEGATE,           '-',          25);
 859         register_expression_parser(parse_UNEXPR_PLUS,             '+',          25);
 860         register_expression_parser(parse_UNEXPR_NOT,              '!',          25);
 861         register_expression_parser(parse_UNEXPR_BITWISE_NEGATE,   '~',          25);
 862         register_expression_parser(parse_UNEXPR_DEREFERENCE,      '*',          25);
 863         register_expression_parser(parse_UNEXPR_TAKE_ADDRESS,     '&',          25);
 864         register_expression_parser(parse_UNEXPR_PREFIX_INCREMENT, T_PLUSPLUS,   25);
 865         register_expression_parser(parse_UNEXPR_PREFIX_DECREMENT, T_MINUSMINUS, 25);
 866         register_expression_parser(parse_sizeof,                  T_sizeof,     25);
 867 }
 868
 869
 870 static
 871 statement_t *parse_compound_statement(void);
 872
 873 static
 874 statement_t *parse_statement(void);
 875
 876 static
 877 statement_t *parse_case_statement(void)
 878 {
 879         eat(T_case);
 880         parse_expression();
 881         expect(':');
 882         parse_statement();
 883
 884         return NULL;
 885 }
 886
 887 static
 888 statement_t *parse_default_statement(void)
 889 {
 890         eat(T_default);
 891         expect(':');
 892         parse_statement();
 893
 894         return NULL;
 895 }
 896
 897 static
 898 statement_t *parse_label_statement(void)
 899 {
 900         eat(T_IDENTIFIER);
 901         expect(';');
 902         parse_statement();
 903
 904         return NULL;
 905 }
 906
 907 static
 908 statement_t *parse_if(void)
 909 {
 910         eat(T_if);
 911         expect('(');
 912         parse_expression();
 913         expect(')');
 914
 915         parse_statement();
 916         if(token.type == T_else) {
 917                 next_token();
 918                 parse_statement();
 919         }
 920
 921         return NULL;
 922 }
 923
 924 static
 925 statement_t *parse_switch(void)
 926 {
 927         eat(T_switch);
 928         expect('(');
 929         parse_expression();
 930         expect(')');
 931         parse_statement();
 932
 933         return NULL;
 934 }
 935
 936 static
 937 statement_t *parse_while(void)
 938 {
 939         eat(T_while);
 940         expect('(');
 941         parse_expression();
 942         expect(')');
 943         parse_statement();
 944
 945         return NULL;
 946 }
 947
 948 static
 949 statement_t *parse_do(void)
 950 {
 951         eat(T_do);
 952         parse_statement();
 953         expect(T_while);
 954         expect('(');
 955         parse_expression();
 956         expect(')');
 957
 958         return NULL;
 959 }
 960
 961 static
 962 statement_t *parse_for(void)
 963 {
 964         eat(T_for);
 965         expect('(');
 966         if(token.type != ';') {
 967                 /* TODO not correct... this could also be a declaration */
 968                 parse_expression();
 969         }
 970         expect(';');
 971         if(token.type != ';') {
 972                 parse_expression();
 973         }
 974         expect(';');
 975         if(token.type != ')') {
 976                 parse_expression();
 977         }
 978         expect(')');
 979         parse_statement();
 980
 981         return NULL;
 982 }
 983
 984 static
 985 statement_t *parse_goto(void)
 986 {
 987         eat(T_goto);
 988         expect(T_IDENTIFIER);
 989         expect(';');
 990
 991         return NULL;
 992 }
 993
 994 static
 995 statement_t *parse_continue(void)
 996 {
 997         eat(T_continue);
 998         expect(';');
 999
1000         return NULL;
1001 }
1002
1003 static
1004 statement_t *parse_break(void)
1005 {
1006         eat(T_break);
1007         expect(';');
1008
1009         return NULL;
1010 }
1011
1012 static
1013 statement_t *parse_return(void)
1014 {
1015         eat(T_return);
1016         parse_expression();
1017         expect(';');
1018
1019         return NULL;
1020 }
1021
1022 static
1023 statement_t *parse_statement(void)
1024 {
1025         statement_t *statement = NULL;
1026
1027         /* declaration or statement */
1028         switch(token.type) {
1029         case T_case:
1030                 statement = parse_case_statement();
1031                 break;
1032
1033         case T_default:
1034                 statement = parse_default_statement();
1035                 break;
1036
1037         case T_IDENTIFIER:
1038                 statement = parse_label_statement();
1039                 break;
1040
1041         case '{':
1042                 statement = parse_compound_statement();
1043                 break;
1044
1045         case T_if:
1046                 statement = parse_if();
1047                 break;
1048
1049         case T_switch:
1050                 statement = parse_switch();
1051                 break;
1052
1053         case T_while:
1054                 statement = parse_while();
1055                 break;
1056
1057         case T_do:
1058                 statement = parse_do();
1059                 break;
1060
1061         case T_for:
1062                 statement = parse_for();
1063                 break;
1064
1065         case T_goto:
1066                 statement = parse_goto();
1067                 break;
1068
1069         case T_continue:
1070                 statement = parse_continue();
1071                 break;
1072
1073         case T_break:
1074                 statement = parse_break();
1075                 break;
1076
1077         case T_return:
1078                 statement = parse_return();
1079                 break;
1080
1081         case ';':
1082                 statement = NULL;
1083                 break;
1084         }
1085
1086         return statement;
1087 }
1088
1089 static
1090 statement_t *parse_compound_statement(void)
1091 {
1092         expect('{');
1093
1094         while(token.type != '}') {
1095                 parse_statement();
1096         }
1097         next_token();
1098
1099         return NULL;
1100 }
1101
1102 static
1103 void parse_translation_unit(void)
1104 {
1105         /*
1106         declaration_specifiers_t specifiers;
1107         memset(&specifiers, 0, sizeof(specifiers));
1108         parse_declaration_specifiers(&specifiers);
1109         */
1110
1111         while(token.type != T_EOF) {
1112                 if(token.type == '{') {
1113                         next_token();
1114                         continue;
1115                 }
1116
1117                 parse_declaration();
1118                 /* multiple declarations? */
1119
1120                 if(token.type == '{') {
1121                         parse_compound_statement();
1122                 } else if(token.type == ';') {
1123                         next_token();
1124                 } else {
1125                         parse_error_expected("while parsing declarations", '{', ';', 0);
1126                 }
1127         }
1128 }
1129
1130 void parse(void)
1131 {
1132         next_token();
1133         parse_translation_unit();
1134 }
1135
1136 void init_parser(void)
1137 {
1138         init_expression_parsers();
1139 }
1140
1141 void exit_parser(void)
1142 {
1143 }