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                 case T_IDENTIFIER:
 228                         /* TODO */
 229                         assert(0);
 230                         break;
 231
 232                 /* function specifier */
 233                 default:
 234                         return;;
 235                 }
 236         }
 237
 238         if(type_type == TYPE_INVALID) {
 239                 /* match valid basic types */
 240                 switch(type_specifiers) {
 241                 case SPECIFIER_VOID:
 242                         atomic_type = ATOMIC_TYPE_VOID;
 243                         break;
 244                 case SPECIFIER_CHAR:
 245                         atomic_type = ATOMIC_TYPE_CHAR;
 246                         break;
 247                 case SPECIFIER_SIGNED | SPECIFIER_CHAR:
 248                         atomic_type = ATOMIC_TYPE_SCHAR;
 249                         break;
 250                 case SPECIFIER_UNSIGNED | SPECIFIER_CHAR:
 251                         atomic_type = ATOMIC_TYPE_UCHAR;
 252                         break;
 253                 case SPECIFIER_SHORT:
 254                 case SPECIFIER_SIGNED | SPECIFIER_SHORT:
 255                 case SPECIFIER_SHORT | SPECIFIER_INT:
 256                 case SPECIFIER_SIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
 257                         atomic_type = ATOMIC_TYPE_SHORT;
 258                         break;
 259                 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT:
 260                 case SPECIFIER_UNSIGNED | SPECIFIER_SHORT | SPECIFIER_INT:
 261                         atomic_type = ATOMIC_TYPE_USHORT;
 262                         break;
 263                 case SPECIFIER_INT:
 264                 case SPECIFIER_SIGNED:
 265                 case SPECIFIER_SIGNED | SPECIFIER_INT:
 266                         atomic_type = ATOMIC_TYPE_INT;
 267                         break;
 268                 case SPECIFIER_UNSIGNED:
 269                 case SPECIFIER_UNSIGNED | SPECIFIER_INT:
 270                         atomic_type = ATOMIC_TYPE_UINT;
 271                         break;
 272                 case SPECIFIER_LONG:
 273                 case SPECIFIER_SIGNED | SPECIFIER_LONG:
 274                 case SPECIFIER_LONG | SPECIFIER_INT:
 275                 case SPECIFIER_SIGNED | SPECIFIER_LONG | SPECIFIER_INT:
 276                         atomic_type = ATOMIC_TYPE_LONG;
 277                         break;
 278                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG:
 279                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG | SPECIFIER_INT:
 280                         atomic_type = ATOMIC_TYPE_ULONG;
 281                         break;
 282                 case SPECIFIER_LONG_LONG:
 283                 case SPECIFIER_SIGNED | SPECIFIER_LONG_LONG:
 284                 case SPECIFIER_LONG_LONG | SPECIFIER_INT:
 285                 case SPECIFIER_SIGNED | SPECIFIER_LONG_LONG | SPECIFIER_INT:
 286                         atomic_type = ATOMIC_TYPE_LONGLONG;
 287                         break;
 288                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG_LONG:
 289                 case SPECIFIER_UNSIGNED | SPECIFIER_LONG_LONG | SPECIFIER_INT:
 290                         atomic_type = ATOMIC_TYPE_ULONGLONG;
 291                         break;
 292                 case SPECIFIER_FLOAT:
 293                         atomic_type = ATOMIC_TYPE_FLOAT;
 294                         break;
 295                 case SPECIFIER_DOUBLE:
 296                         atomic_type = ATOMIC_TYPE_DOUBLE;
 297                         break;
 298                 case SPECIFIER_LONG | SPECIFIER_DOUBLE:
 299                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE;
 300                         break;
 301                 case SPECIFIER_BOOL:
 302                         atomic_type = ATOMIC_TYPE_BOOL;
 303                         break;
 304 #ifdef PROVIDE_COMPLEX
 305                 case SPECIFIER_FLOAT | SPECIFIER_COMPLEX:
 306                         atomic_type = ATOMIC_TYPE_FLOAT_COMPLEX;
 307                         break;
 308                 case SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
 309                         atomic_type = ATOMIC_TYPE_DOUBLE_COMPLEX;
 310                         break;
 311                 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_COMPLEX:
 312                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE_COMPLEX;
 313                         break;
 314 #endif
 315 #ifdef PROVIDE_IMAGINARY
 316                 case SPECIFIER_FLOAT | SPECIFIER_IMAGINARY:
 317                         atomic_type = ATOMIC_TYPE_FLOAT_IMAGINARY;
 318                         break;
 319                 case SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
 320                         atomic_type = ATOMIC_TYPE_DOUBLE_IMAGINARY;
 321                         break;
 322                 case SPECIFIER_LONG | SPECIFIER_DOUBLE | SPECIFIER_IMAGINARY:
 323                         atomic_type = ATOMIC_TYPE_LONG_DOUBLE_IMAGINARY;
 324                         break;
 325 #endif
 326                 default:
 327                         /* invalid specifier combination, give an error message */
 328                         if(type_specifiers == 0) {
 329                                 parse_error("no type specifiers given in declaration");
 330                         } else if((type_specifiers & SPECIFIER_SIGNED) &&
 331                                   (type_specifiers & SPECIFIER_UNSIGNED)) {
 332                                 parse_error("signed and unsigned specifiers gives");
 333                         } else if(type_specifiers & (SPECIFIER_SIGNED | SPECIFIER_UNSIGNED)) {
 334                                 parse_error("only integer types can be signed or unsigned");
 335                         } else {
 336                                 parse_error("multiple datatypes in declaration");
 337                         }
 338                 }
 339         } else {
 340                 if(type_specifiers != 0) {
 341                         parse_error("multiple datatypes in declaration");
 342                 }
 343         }
 344 }
 345
 346 typedef struct declarator_t declarator_t;
 347 struct declarator_t {
 348         /* pointer stuff... */
 349         symbol_t     *symbol;
 350
 351         declarator_t *next;
 352 };
 353
 354 declarator_t *parse_declarator(void)
 355 {
 356         while(token.type == '*') {
 357                 /* pointer */
 358                 next_token();
 359                 //parse_type_qualifiers();
 360         }
 361
 362         declarator_t *declarator;
 363
 364         switch(token.type) {
 365         case T_IDENTIFIER:
 366                 declarator = allocate_ast_zero(sizeof(declarator[0]));
 367                 declarator->symbol = token.v.symbol;
 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 declarator_t *parse_init_declarator(void)
 398 {
 399         declarator_t *declarator = parse_declarator();
 400         if(token.type == '=') {
 401                 next_token();
 402                 //parse_initialize();
 403         }
 404
 405         return 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
 421 #if 0
 422 namespace_t *parse(FILE *in, const char *input_name)
 423 {
 424         namespace_t *namespace = parse_namespace();
 425
 426         return namespace;
 427 }
 428 #endif
 429
 430
 431
 432 static
 433 expression_t *parse_sub_expression(unsigned precedence);
 434 static
 435 expression_t *parse_expression(void);
 436
 437 typedef expression_t* (*parse_expression_function) (unsigned precedence);
 438 typedef expression_t* (*parse_expression_infix_function) (unsigned precedence,
 439                                                           expression_t *left);
 440
 441 typedef struct expression_parser_function_t expression_parser_function_t;
 442 struct expression_parser_function_t {
 443         unsigned                         precedence;
 444         parse_expression_function        parser;
 445         unsigned                         infix_precedence;
 446         parse_expression_infix_function  infix_parser;
 447 };
 448
 449 expression_parser_function_t expression_parsers[T_LAST_TOKEN];
 450
 451 static
 452 expression_t *expected_expression_error(void)
 453 {
 454         parser_print_error_prefix();
 455         fprintf(stderr, "expected expression, got token ");
 456         print_token(stderr, & token);
 457         fprintf(stderr, "\n");
 458
 459         expression_t *expression = allocate_ast_zero(sizeof(expression[0]));
 460         expression->type = EXPR_INVALID;
 461         next_token();
 462
 463         return expression;
 464 }
 465
 466 static
 467 expression_t *parse_string_const(void)
 468 {
 469         string_literal_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
 470
 471         cnst->expression.type = EXPR_STRING_LITERAL;
 472         cnst->value           = token.v.string;
 473
 474         next_token();
 475
 476         return (expression_t*) cnst;
 477 }
 478
 479 static
 480 expression_t *parse_int_const(void)
 481 {
 482         const_t *cnst = allocate_ast_zero(sizeof(cnst[0]));
 483
 484         cnst->expression.type = EXPR_CONST;
 485         cnst->value           = token.v.intvalue;
 486
 487         next_token();
 488
 489         return (expression_t*) cnst;
 490 }
 491
 492 static
 493 expression_t *parse_reference(void)
 494 {
 495         reference_expression_t *ref = allocate_ast_zero(sizeof(ref[0]));
 496
 497         ref->expression.type            = EXPR_REFERENCE;
 498         ref->symbol                     = token.v.symbol;
 499
 500         next_token();
 501
 502         return (expression_t*) ref;
 503 }
 504
 505 static
 506 expression_t *parse_brace_expression(void)
 507 {
 508         eat('(');
 509
 510         expression_t *result = parse_expression();
 511         expect(')');
 512
 513         return result;
 514 }
 515
 516 static
 517 expression_t *parse_primary_expression(void)
 518 {
 519         switch(token.type) {
 520         case T_INTEGER:
 521                 return parse_int_const();
 522         case T_STRING_LITERAL:
 523                 return parse_string_const();
 524         case T_IDENTIFIER:
 525                 return parse_reference();
 526         case '(':
 527                 return parse_brace_expression();
 528         }
 529
 530         /* TODO: error message */
 531         return NULL;
 532 }
 533
 534 static
 535 expression_t *parse_array_expression(unsigned precedence,
 536                                      expression_t *array_ref)
 537 {
 538         (void) precedence;
 539
 540         eat('[');
 541
 542         array_access_expression_t *array_access
 543                 = allocate_ast_zero(sizeof(array_access[0]));
 544
 545         array_access->expression.type = EXPR_ARRAY_ACCESS;
 546         array_access->array_ref       = array_ref;
 547         array_access->index           = parse_expression();
 548
 549         if(token.type != ']') {
 550                 parse_error_expected("Problem while parsing array access", ']', 0);
 551                 return NULL;
 552         }
 553         next_token();
 554
 555         return (expression_t*) array_access;
 556 }
 557
 558 static
 559 expression_t *parse_sizeof(unsigned precedence)
 560 {
 561         (void) precedence;
 562         eat(T_sizeof);
 563         /* TODO... */
 564
 565         return NULL;
 566 }
 567
 568 static
 569 expression_t *parse_select_expression(unsigned precedence,
 570                                       expression_t *compound)
 571 {
 572         (void) precedence;
 573
 574         assert(token.type == '.' || token.type == T_SELECT);
 575         next_token();
 576
 577         select_expression_t *select = allocate_ast_zero(sizeof(select[0]));
 578
 579         select->expression.type = EXPR_SELECT;
 580         select->compound        = compound;
 581
 582         if(token.type != T_IDENTIFIER) {
 583                 parse_error_expected("Problem while parsing compound select",
 584                                      T_IDENTIFIER, 0);
 585                 return NULL;
 586         }
 587         select->symbol = token.v.symbol;
 588         next_token();
 589
 590         return (expression_t*) select;
 591 }
 592
 593 static
 594 expression_t *parse_call_expression(unsigned precedence,
 595                                     expression_t *expression)
 596 {
 597         (void) precedence;
 598         call_expression_t *call = allocate_ast_zero(sizeof(call[0]));
 599
 600         call->expression.type            = EXPR_CALL;
 601         call->method                     = expression;
 602
 603         /* parse arguments */
 604         eat('(');
 605
 606         if(token.type != ')') {
 607                 call_argument_t *last_argument = NULL;
 608
 609                 while(1) {
 610                         call_argument_t *argument = allocate_ast_zero(sizeof(argument[0]));
 611
 612                         argument->expression = parse_expression();
 613                         if(last_argument == NULL) {
 614                                 call->arguments = argument;
 615                         } else {
 616                                 last_argument->next = argument;
 617                         }
 618                         last_argument = argument;
 619
 620                         if(token.type != ',')
 621                                 break;
 622                         next_token();
 623                 }
 624         }
 625         expect(')');
 626
 627         return (expression_t*) call;
 628 }
 629
 630 #define CREATE_UNARY_EXPRESSION_PARSER(token_type, unexpression_type)     \
 631 static                                                                    \
 632 expression_t *parse_##unexpression_type(unsigned precedence)              \
 633 {                                                                         \
 634         eat(token_type);                                                      \
 635                                                                           \
 636         unary_expression_t *unary_expression                                  \
 637                 = allocate_ast_zero(sizeof(unary_expression[0]));                 \
 638         unary_expression->expression.type = EXPR_UNARY;                       \
 639         unary_expression->type            = unexpression_type;                \
 640         unary_expression->value           = parse_sub_expression(precedence); \
 641                                                                           \
 642         return (expression_t*) unary_expression;                              \
 643 }
 644
 645 CREATE_UNARY_EXPRESSION_PARSER('-', UNEXPR_NEGATE);
 646 CREATE_UNARY_EXPRESSION_PARSER('+', UNEXPR_PLUS);
 647 CREATE_UNARY_EXPRESSION_PARSER('!', UNEXPR_NOT);
 648 CREATE_UNARY_EXPRESSION_PARSER('*', UNEXPR_DEREFERENCE);
 649 CREATE_UNARY_EXPRESSION_PARSER('&', UNEXPR_TAKE_ADDRESS);
 650 CREATE_UNARY_EXPRESSION_PARSER('~', UNEXPR_BITWISE_NEGATE);
 651 CREATE_UNARY_EXPRESSION_PARSER(T_PLUSPLUS,   UNEXPR_PREFIX_INCREMENT);
 652 CREATE_UNARY_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_PREFIX_DECREMENT);
 653
 654 #define CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(token_type, unexpression_type) \
 655 static                                                                        \
 656 expression_t *parse_##unexpression_type(unsigned precedence,                  \
 657                                         expression_t *left)                   \
 658 {                                                                             \
 659         (void) precedence;                                                        \
 660         eat(token_type);                                                          \
 661                                                                               \
 662         unary_expression_t *unary_expression                                      \
 663                 = allocate_ast_zero(sizeof(unary_expression[0]));                     \
 664         unary_expression->expression.type = EXPR_UNARY;                           \
 665         unary_expression->type            = unexpression_type;                    \
 666         unary_expression->value           = left;                                 \
 667                                                                               \
 668         return (expression_t*) unary_expression;                                  \
 669 }
 670
 671 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_PLUSPLUS,   UNEXPR_POSTFIX_INCREMENT);
 672 CREATE_UNARY_POSTFIX_EXPRESSION_PARSER(T_MINUSMINUS, UNEXPR_POSTFIX_DECREMENT);
 673
 674 #define CREATE_BINEXPR_PARSER(token_type, binexpression_type)    \
 675 static                                                           \
 676 expression_t *parse_##binexpression_type(unsigned precedence,    \
 677                                          expression_t *left)     \
 678 {                                                                \
 679         eat(token_type);                                             \
 680                                                                  \
 681         expression_t *right = parse_sub_expression(precedence);      \
 682                                                                  \
 683         binary_expression_t *binexpr                                 \
 684                 = allocate_ast_zero(sizeof(binexpr[0]));                 \
 685         binexpr->expression.type            = EXPR_BINARY;           \
 686         binexpr->type                       = binexpression_type;    \
 687         binexpr->left                       = left;                  \
 688         binexpr->right                      = right;                 \
 689                                                                  \
 690         return (expression_t*) binexpr;                              \
 691 }
 692
 693 CREATE_BINEXPR_PARSER('*', BINEXPR_MUL);
 694 CREATE_BINEXPR_PARSER('/', BINEXPR_DIV);
 695 CREATE_BINEXPR_PARSER('+', BINEXPR_ADD);
 696 CREATE_BINEXPR_PARSER('-', BINEXPR_SUB);
 697 CREATE_BINEXPR_PARSER('<', BINEXPR_LESS);
 698 CREATE_BINEXPR_PARSER('>', BINEXPR_GREATER);
 699 CREATE_BINEXPR_PARSER('=', BINEXPR_ASSIGN);
 700 CREATE_BINEXPR_PARSER(T_EQUALEQUAL, BINEXPR_EQUAL);
 701 CREATE_BINEXPR_PARSER(T_SLASHEQUAL, BINEXPR_NOTEQUAL);
 702 CREATE_BINEXPR_PARSER(T_LESSEQUAL, BINEXPR_LESSEQUAL);
 703 CREATE_BINEXPR_PARSER(T_GREATEREQUAL, BINEXPR_GREATEREQUAL);
 704 CREATE_BINEXPR_PARSER('&', BINEXPR_BITWISE_AND);
 705 CREATE_BINEXPR_PARSER('|', BINEXPR_BITWISE_OR);
 706 CREATE_BINEXPR_PARSER('^', BINEXPR_BITWISE_XOR);
 707 CREATE_BINEXPR_PARSER(T_LESSLESS, BINEXPR_SHIFTLEFT);
 708 CREATE_BINEXPR_PARSER(T_GREATERGREATER, BINEXPR_SHIFTRIGHT);
 709
 710 static
 711 expression_t *parse_sub_expression(unsigned precedence)
 712 {
 713         if(token.type < 0) {
 714                 return expected_expression_error();
 715         }
 716
 717         expression_parser_function_t *parser
 718                 = &expression_parsers[token.type];
 719         source_position_t             source_position = source_position;
 720         expression_t                 *left;
 721
 722         if(parser->parser != NULL) {
 723                 left = parser->parser(parser->precedence);
 724         } else {
 725                 left = parse_primary_expression();
 726         }
 727         if(left != NULL)
 728                 left->source_position = source_position;
 729
 730         while(1) {
 731                 if(token.type < 0) {
 732                         return expected_expression_error();
 733                 }
 734
 735                 parser = &expression_parsers[token.type];
 736                 if(parser->infix_parser == NULL)
 737                         break;
 738                 if(parser->infix_precedence < precedence)
 739                         break;
 740
 741                 left = parser->infix_parser(parser->infix_precedence, left);
 742                 if(left != NULL)
 743                         left->source_position = source_position;
 744         }
 745
 746         return left;
 747 }
 748
 749 static
 750 expression_t *parse_expression(void)
 751 {
 752         return parse_sub_expression(1);
 753 }
 754
 755
 756
 757 void register_expression_parser(parse_expression_function parser,
 758                                 int token_type, unsigned precedence)
 759 {
 760         expression_parser_function_t *entry = &expression_parsers[token_type];
 761
 762         if(entry->parser != NULL) {
 763                 fprintf(stderr, "for token ");
 764                 print_token_type(stderr, token_type);
 765                 fprintf(stderr, "\n");
 766                 panic("trying to register multiple expression parsers for a token");
 767         }
 768         entry->parser     = parser;
 769         entry->precedence = precedence;
 770 }
 771
 772 void register_expression_infix_parser(parse_expression_infix_function parser,
 773                                       int token_type, unsigned precedence)
 774 {
 775         expression_parser_function_t *entry = &expression_parsers[token_type];
 776
 777         if(entry->infix_parser != NULL) {
 778                 fprintf(stderr, "for token ");
 779                 print_token_type(stderr, token_type);
 780                 fprintf(stderr, "\n");
 781                 panic("trying to register multiple infix expression parsers for a "
 782                       "token");
 783         }
 784         entry->infix_parser     = parser;
 785         entry->infix_precedence = precedence;
 786 }
 787
 788 static
 789 void init_expression_parsers(void)
 790 {
 791         memset(&expression_parsers, 0, sizeof(expression_parsers));
 792
 793         register_expression_infix_parser(parse_BINEXPR_MUL,       '*', 16);
 794         register_expression_infix_parser(parse_BINEXPR_DIV,       '/', 16);
 795         register_expression_infix_parser(parse_BINEXPR_SHIFTLEFT,
 796                                    T_LESSLESS, 16);
 797         register_expression_infix_parser(parse_BINEXPR_SHIFTRIGHT,
 798                                    T_GREATERGREATER, 16);
 799         register_expression_infix_parser(parse_BINEXPR_ADD,       '+', 15);
 800         register_expression_infix_parser(parse_BINEXPR_SUB,       '-', 15);
 801         register_expression_infix_parser(parse_BINEXPR_LESS,      '<', 14);
 802         register_expression_infix_parser(parse_BINEXPR_GREATER,   '>', 14);
 803         register_expression_infix_parser(parse_BINEXPR_LESSEQUAL, T_LESSEQUAL, 14);
 804         register_expression_infix_parser(parse_BINEXPR_GREATEREQUAL,
 805                                    T_GREATEREQUAL, 14);
 806         register_expression_infix_parser(parse_BINEXPR_EQUAL,     T_EQUALEQUAL, 13);
 807         register_expression_infix_parser(parse_BINEXPR_NOTEQUAL,
 808                                          T_EXCLAMATIONMARKEQUAL, 13);
 809         register_expression_infix_parser(parse_BINEXPR_BITWISE_AND, '&',        12);
 810         register_expression_infix_parser(parse_BINEXPR_BITWISE_XOR, '^',        11);
 811         register_expression_infix_parser(parse_BINEXPR_BITWISE_OR,  '|',        10);
 812         register_expression_infix_parser(parse_BINEXPR_ASSIGN,      T_EQUAL,     2);
 813
 814         register_expression_infix_parser(parse_array_expression,        '[',    30);
 815         register_expression_infix_parser(parse_call_expression,         '(',    30);
 816         register_expression_infix_parser(parse_select_expression,       '.',    30);
 817         register_expression_infix_parser(parse_select_expression,  T_SELECT,    30);
 818         register_expression_infix_parser(parse_UNEXPR_POSTFIX_INCREMENT,
 819                                          T_PLUSPLUS, 30);
 820         register_expression_infix_parser(parse_UNEXPR_POSTFIX_DECREMENT,
 821                                          T_MINUSMINUS, 30);
 822
 823         register_expression_parser(parse_UNEXPR_NEGATE,           '-',          25);
 824         register_expression_parser(parse_UNEXPR_PLUS,             '+',          25);
 825         register_expression_parser(parse_UNEXPR_NOT,              '!',          25);
 826         register_expression_parser(parse_UNEXPR_BITWISE_NEGATE,   '~',          25);
 827         register_expression_parser(parse_UNEXPR_DEREFERENCE,      '*',          25);
 828         register_expression_parser(parse_UNEXPR_TAKE_ADDRESS,     '&',          25);
 829         register_expression_parser(parse_UNEXPR_PREFIX_INCREMENT, T_PLUSPLUS,   25);
 830         register_expression_parser(parse_UNEXPR_PREFIX_DECREMENT, T_MINUSMINUS, 25);
 831         register_expression_parser(parse_sizeof,                  T_sizeof,     25);
 832 }
 833
 834
 835 static
 836 statement_t *parse_compound_statement(void);
 837
 838 static
 839 statement_t *parse_statement(void);
 840
 841 static
 842 statement_t *parse_case_statement(void)
 843 {
 844         eat(T_case);
 845         parse_expression();
 846         expect(':');
 847         parse_statement();
 848
 849         return NULL;
 850 }
 851
 852 static
 853 statement_t *parse_default_statement(void)
 854 {
 855         eat(T_default);
 856         expect(':');
 857         parse_statement();
 858
 859         return NULL;
 860 }
 861
 862 static
 863 statement_t *parse_label_statement(void)
 864 {
 865         eat(T_IDENTIFIER);
 866         expect(';');
 867         parse_statement();
 868
 869         return NULL;
 870 }
 871
 872 static
 873 statement_t *parse_if(void)
 874 {
 875         eat(T_if);
 876         expect('(');
 877         parse_expression();
 878         expect(')');
 879
 880         parse_statement();
 881         if(token.type == T_else) {
 882                 next_token();
 883                 parse_statement();
 884         }
 885
 886         return NULL;
 887 }
 888
 889 static
 890 statement_t *parse_switch(void)
 891 {
 892         eat(T_switch);
 893         expect('(');
 894         parse_expression();
 895         expect(')');
 896         parse_statement();
 897
 898         return NULL;
 899 }
 900
 901 static
 902 statement_t *parse_while(void)
 903 {
 904         eat(T_while);
 905         expect('(');
 906         parse_expression();
 907         expect(')');
 908         parse_statement();
 909
 910         return NULL;
 911 }
 912
 913 static
 914 statement_t *parse_do(void)
 915 {
 916         eat(T_do);
 917         parse_statement();
 918         expect(T_while);
 919         expect('(');
 920         parse_expression();
 921         expect(')');
 922
 923         return NULL;
 924 }
 925
 926 static
 927 statement_t *parse_for(void)
 928 {
 929         eat(T_for);
 930         expect('(');
 931         if(token.type != ';') {
 932                 /* TODO not correct... this could also be a declaration */
 933                 parse_expression();
 934         }
 935         expect(';');
 936         if(token.type != ';') {
 937                 parse_expression();
 938         }
 939         expect(';');
 940         if(token.type != ')') {
 941                 parse_expression();
 942         }
 943         expect(')');
 944         parse_statement();
 945
 946         return NULL;
 947 }
 948
 949 static
 950 statement_t *parse_goto(void)
 951 {
 952         eat(T_goto);
 953         expect(T_IDENTIFIER);
 954         expect(';');
 955
 956         return NULL;
 957 }
 958
 959 static
 960 statement_t *parse_continue(void)
 961 {
 962         eat(T_continue);
 963         expect(';');
 964
 965         return NULL;
 966 }
 967
 968 static
 969 statement_t *parse_break(void)
 970 {
 971         eat(T_break);
 972         expect(';');
 973
 974         return NULL;
 975 }
 976
 977 static
 978 statement_t *parse_return(void)
 979 {
 980         eat(T_return);
 981         parse_expression();
 982         expect(';');
 983
 984         return NULL;
 985 }
 986
 987 static
 988 statement_t *parse_statement(void)
 989 {
 990         statement_t *statement = NULL;
 991
 992         /* declaration or statement */
 993         switch(token.type) {
 994         case T_case:
 995                 statement = parse_case_statement();
 996                 break;
 997
 998         case T_default:
 999                 statement = parse_default_statement();
1000                 break;
1001
1002         case T_IDENTIFIER:
1003                 statement = parse_label_statement();
1004                 break;
1005
1006         case '{':
1007                 statement = parse_compound_statement();
1008                 break;
1009
1010         case T_if:
1011                 statement = parse_if();
1012                 break;
1013
1014         case T_switch:
1015                 statement = parse_switch();
1016                 break;
1017
1018         case T_while:
1019                 statement = parse_while();
1020                 break;
1021
1022         case T_do:
1023                 statement = parse_do();
1024                 break;
1025
1026         case T_for:
1027                 statement = parse_for();
1028                 break;
1029
1030         case T_goto:
1031                 statement = parse_goto();
1032                 break;
1033
1034         case T_continue:
1035                 statement = parse_continue();
1036                 break;
1037
1038         case T_break:
1039                 statement = parse_break();
1040                 break;
1041
1042         case T_return:
1043                 statement = parse_return();
1044                 break;
1045
1046         case ';':
1047                 statement = NULL;
1048                 break;
1049         }
1050
1051         return statement;
1052 }
1053
1054 static
1055 statement_t *parse_compound_statement(void)
1056 {
1057         expect('{');
1058
1059         while(token.type != '}') {
1060                 parse_statement();
1061         }
1062         next_token();
1063
1064         return NULL;
1065 }
1066
1067 static
1068 void parse_translation_unit(void)
1069 {
1070         declaration_specifiers_t specifiers;
1071         memset(&specifiers, 0, sizeof(specifiers));
1072         parse_declaration_specifiers(&specifiers);
1073
1074         while(token.type != T_EOF) {
1075                 if(token.type == '{') {
1076                         next_token();
1077                         continue;
1078                 }
1079
1080                 declarator_t *declarators = parse_declarator();
1081                 (void) declarators;
1082                 /* multiple declarations? */
1083
1084                 if(token.type == '{') {
1085                         parse_compound_statement();
1086                 } else if(token.type == ';') {
1087                         next_token();
1088                 }
1089         }
1090 }
1091
1092 void parse(void)
1093 {
1094         next_token();
1095         parse_translation_unit();
1096 }
1097
1098 void init_parser(void)
1099 {
1100         init_expression_parsers();
1101 }
1102
1103 void exit_parser(void)
1104 {
1105 }