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