parse.c

   1 #ifndef __GNUC__
   2 typedef int __builtin_va_list;
   3 #endif
   4 /*
   5  * Stupid C parser, version 1e-6.
   6  *
   7  * Let's see how hard this is to do.
   8  */
   9 #include <stdarg.h>
  10 #include <stdlib.h>
  11 #include <stdio.h>
  12 #include <string.h>
  13 #include <ctype.h>
  14 #include <unistd.h>
  15 #include <fcntl.h>
  16
  17 #include "lib.h"
  18 #include "token.h"
  19 #include "parse.h"
  20 #include "symbol.h"
  21 #include "scope.h"
  22
  23 void show_statement(struct statement *stmt)
  24 {
  25         if (!stmt) {
  26                 printf("\t<nostatement>");
  27                 return;
  28         }
  29         switch (stmt->type) {
  30         case STMT_RETURN:
  31                 printf("\treturn ");
  32                 show_expression(stmt->expression);
  33                 break;
  34         case STMT_COMPOUND:
  35                 printf("{\n");
  36                 if (stmt->syms) {
  37                         printf("\t");
  38                         show_symbol_list(stmt->syms, "\n\t");
  39                         printf("\n\n");
  40                 }
  41                 show_statement_list(stmt->stmts, ";\n");
  42                 printf("\n}\n\n");
  43                 break;
  44         case STMT_EXPRESSION:
  45                 printf("\t");
  46                 show_expression(stmt->expression);
  47                 return;
  48         case STMT_IF:
  49                 printf("\tif (");
  50                 show_expression(stmt->if_conditional);
  51                 printf(")\n");
  52                 show_statement(stmt->if_true);
  53                 if (stmt->if_false) {
  54                         printf("\nelse\n");
  55                         show_statement(stmt->if_false);
  56                 }
  57                 break;
  58         case STMT_SWITCH:
  59                 printf("\tswitch (");
  60                 show_expression(stmt->switch_expression);
  61                 printf(")\n");
  62                 show_statement(stmt->switch_statement);
  63                 break;
  64
  65         case STMT_CASE:
  66                 if (!stmt->case_expression)
  67                         printf("default");
  68                 else {
  69                         printf("case ");
  70                         show_expression(stmt->case_expression);
  71                         if (stmt->case_to) {
  72                                 printf(" ... ");
  73                                 show_expression(stmt->case_to);
  74                         }
  75                 }
  76                 printf(":");
  77                 show_statement(stmt->case_statement);
  78                 break;
  79
  80         case STMT_BREAK:
  81                 printf("break");
  82                 break;
  83
  84         default:
  85                 printf("WTF");
  86         }
  87 }
  88
  89 static void show_one_statement(struct statement *stmt, void *sep, int flags)
  90 {
  91         show_statement(stmt);
  92         if (!(flags & ITERATE_LAST))
  93                 printf("%s", (const char *)sep);
  94 }
  95
  96 void show_statement_list(struct statement_list *stmt, const char *sep)
  97 {
  98         statement_iterate(stmt, show_one_statement, (void *)sep);
  99 }
 100
 101 void show_expression(struct expression *expr)
 102 {
 103         if (!expr)
 104                 return;
 105
 106         printf("< ");
 107         switch (expr->type) {
 108         case EXPR_BINOP:
 109                 show_expression(expr->left);
 110                 printf(" %s ", show_special(expr->op));
 111                 show_expression(expr->right);
 112                 break;
 113         case EXPR_PREOP:
 114                 printf("%s<", show_special(expr->op));
 115                 show_expression(expr->unop);
 116                 printf(">");
 117                 break;
 118         case EXPR_POSTOP:
 119                 show_expression(expr->unop);
 120                 printf(" %s ", show_special(expr->op));
 121                 break;
 122         case EXPR_CONSTANT:
 123                 printf("%s", show_token(expr->token));
 124                 break;
 125         case EXPR_SYMBOL:
 126                 if (!expr->symbol) {
 127                         printf("<nosymbol>");
 128                         break;
 129                 }
 130                 printf("<%s:", show_token(expr->symbol->token));
 131                 show_type(expr->symbol);
 132                 printf(">");
 133                 break;
 134         case EXPR_DEREF:
 135                 show_expression(expr->deref);
 136                 printf("%s", show_special(expr->op));
 137                 printf("%s", show_token(expr->member));
 138                 break;
 139         case EXPR_CAST:
 140                 printf("<cast>(");
 141                 show_type(expr->cast_type);
 142                 printf(")");
 143                 show_expression(expr->cast_expression);
 144                 break;
 145         default:
 146                 printf("WTF");
 147         }
 148         printf(" >");
 149 }
 150
 151 static struct expression *alloc_expression(struct token *token, int type)
 152 {
 153         struct expression *expr = __alloc_expression(0);
 154         expr->type = type;
 155         expr->token = token;
 156         return expr;
 157 }
 158
 159 struct statement *alloc_statement(struct token * token, int type)
 160 {
 161         struct statement *stmt = __alloc_statement(0);
 162         stmt->type = type;
 163         return stmt;
 164 }
 165
 166 static int match_oplist(int op, ...)
 167 {
 168         va_list args;
 169
 170         va_start(args, op);
 171         for (;;) {
 172                 int nextop = va_arg(args, int);
 173                 if (!nextop)
 174                         return 0;
 175                 if (op == nextop)
 176                         return 1;
 177         }
 178 }
 179
 180 int lookup_type(struct token *token)
 181 {
 182         if (token->type == TOKEN_IDENT)
 183                 return lookup_symbol(token->ident, NS_TYPEDEF) != NULL;
 184         return 0;
 185 }
 186
 187 static struct token *comma_expression(struct token *, struct expression **);
 188 static struct token *compound_statement(struct token *, struct statement *);
 189 static struct token *initializer(struct token *token, struct ctype *type);
 190
 191 static struct token *parens_expression(struct token *token, struct expression **expr, const char *where)
 192 {
 193         token = expect(token, '(', where);
 194         if (match_op(token, '{')) {
 195                 struct expression *e = alloc_expression(token, EXPR_STATEMENT);
 196                 struct statement *stmt = alloc_statement(token, STMT_COMPOUND);
 197                 *expr = e;
 198                 e->statement = stmt;
 199                 start_symbol_scope();
 200                 token = compound_statement(token->next, stmt);
 201                 end_symbol_scope();
 202                 token = expect(token, '}', "at end of statement expression");
 203         } else
 204                 token = parse_expression(token, expr);
 205         return expect(token, ')', where);
 206 }
 207
 208 static struct token *primary_expression(struct token *token, struct expression **tree)
 209 {
 210         struct expression *expr = NULL;
 211
 212         switch (token->type) {
 213         case TOKEN_INTEGER:
 214         case TOKEN_FP:
 215         case TOKEN_CHAR:
 216                 expr = alloc_expression(token, EXPR_CONSTANT);
 217                 token = token->next;
 218                 break;
 219
 220         case TOKEN_IDENT: {
 221                 struct symbol *sym = lookup_symbol(token->ident, NS_SYMBOL);
 222                 if (!sym)
 223                         warn(token, "undefined identifier '%s'", token->ident->name);
 224                 expr = alloc_expression(token, EXPR_SYMBOL);
 225                 expr->symbol = sym;
 226                 token = token->next;
 227                 break;
 228         }
 229
 230         case TOKEN_STRING:
 231                 expr = alloc_expression(token, EXPR_CONSTANT);
 232                 do {
 233                         token = token->next;
 234                 } while (token->type == TOKEN_STRING);
 235                 break;
 236
 237         case TOKEN_SPECIAL:
 238                 if (token->special == '(') {
 239                         expr = alloc_expression(token, EXPR_PREOP);
 240                         expr->op = '(';
 241                         token = parens_expression(token, &expr->unop, "in expression");
 242                         break;
 243                 }
 244         default:
 245                 ;
 246         }
 247         *tree = expr;
 248         return token;
 249 }
 250
 251 static struct token *postfix_expression(struct token *token, struct expression **tree)
 252 {
 253         struct expression *expr = NULL;
 254
 255         token = primary_expression(token, &expr);
 256         while (expr && token->type == TOKEN_SPECIAL) {
 257                 switch (token->special) {
 258                 case '[': {                     /* Array dereference */
 259                         struct expression *array_expr = alloc_expression(token, EXPR_BINOP);
 260                         array_expr->op = '[';
 261                         array_expr->left = expr;
 262                         token = parse_expression(token->next, &array_expr->right);
 263                         token = expect(token, ']', "at end of array dereference");
 264                         expr = array_expr;
 265                         continue;
 266                 }
 267                 case SPECIAL_INCREMENT:         /* Post-increment */
 268                 case SPECIAL_DECREMENT: {       /* Post-decrement */
 269                         struct expression *post = alloc_expression(token, EXPR_POSTOP);
 270                         post->op = token->special;
 271                         post->unop = expr;
 272                         expr = post;
 273                         token = token->next;
 274                         continue;
 275                 }
 276                 case '.':                       /* Structure member dereference */
 277                 case SPECIAL_DEREFERENCE: {     /* Structure pointer member dereference */
 278                         struct expression *deref = alloc_expression(token, EXPR_DEREF);
 279                         deref->op = token->special;
 280                         deref->deref = expr;
 281                         token = token->next;
 282                         if (token->type != TOKEN_IDENT) {
 283                                 warn(token, "Expected member name");
 284                                 break;
 285                         }
 286                         deref->member = token;
 287                         token = token->next;
 288                         expr = deref;
 289                         continue;
 290                 }
 291
 292                 case '(': {                     /* Function call */
 293                         struct expression *call = alloc_expression(token, EXPR_BINOP);
 294                         call->op = '(';
 295                         call->left = expr;
 296                         token = comma_expression(token->next, &call->right);
 297                         token = expect(token, ')', "in function call");
 298                         expr = call;
 299                         continue;
 300                 }
 301
 302                 default:
 303                         break;
 304                 }
 305                 break;
 306         }
 307         *tree = expr;
 308         return token;
 309 }
 310
 311 static struct token *typename(struct token *, struct symbol **);
 312
 313 static struct token *cast_expression(struct token *token, struct expression **tree);
 314 static struct token *unary_expression(struct token *token, struct expression **tree)
 315 {
 316         if (token->type == TOKEN_IDENT &&
 317             (token->ident == &sizeof_ident ||
 318              token->ident == &__alignof___ident)) {
 319                 struct expression *sizeof_ex = alloc_expression(token, EXPR_SIZEOF);
 320                 *tree = sizeof_ex;
 321                 tree = &sizeof_ex->unop;
 322                 token = token->next;
 323                 if (!match_op(token, '(') || !lookup_type(token->next))
 324                         return unary_expression(token, &sizeof_ex->cast_expression);
 325                 token = typename(token->next, &sizeof_ex->cast_type);
 326                 return expect(token, ')', "at end of sizeof type-name");
 327         }
 328
 329         if (token->type == TOKEN_SPECIAL) {
 330                 if (match_oplist(token->special,
 331                     SPECIAL_INCREMENT, SPECIAL_DECREMENT,
 332                     '&', '*', '+', '-', '~', '!', 0)) {
 333                         struct expression *unary = alloc_expression(token, EXPR_PREOP);
 334                         unary->op = token->special;
 335                         *tree = unary;
 336                         return cast_expression(token->next, &unary->unop);
 337                 }
 338         }
 339
 340         return postfix_expression(token, tree);
 341 }
 342
 343 /*
 344  * Ambiguity: a '(' can be either a cast-expression or
 345  * a primary-expression depending on whether it is followed
 346  * by a type or not.
 347  */
 348 static struct token *cast_expression(struct token *token, struct expression **tree)
 349 {
 350         if (match_op(token, '(')) {
 351                 struct token *next = token->next;
 352                 if (lookup_type(next)) {
 353                         struct expression *cast = alloc_expression(next, EXPR_CAST);
 354
 355                         token = typename(next, &cast->cast_type);
 356                         token = expect(token, ')', "at end of cast operator");
 357                         if (match_op(token, '{'))
 358                                 return initializer(token, &cast->cast_type->ctype);
 359                         token = cast_expression(token, &cast->cast_expression);
 360                         *tree = cast;
 361                         return token;
 362                 }
 363         }
 364         return unary_expression(token, tree);
 365 }
 366
 367 /* Generic left-to-right binop parsing */
 368 static struct token *lr_binop_expression(struct token *token, struct expression **tree,
 369         struct token *(*inner)(struct token *, struct expression **), ...)
 370 {
 371         struct expression *left = NULL;
 372         struct token * next = inner(token, &left);
 373
 374         if (left) {
 375                 while (next->type == TOKEN_SPECIAL) {
 376                         struct expression *top, *right = NULL;
 377                         int op = next->special;
 378                         va_list args;
 379
 380                         va_start(args, inner);
 381                         for (;;) {
 382                                 int nextop = va_arg(args, int);
 383                                 if (!nextop)
 384                                         goto out;
 385                                 if (op == nextop)
 386                                         break;
 387                         }
 388                         va_end(args);
 389                         top = alloc_expression(next, EXPR_BINOP);
 390                         next = inner(next->next, &right);
 391                         if (!right) {
 392                                 warn(next, "No right hand side of '%s'-expression", show_special(op));
 393                                 break;
 394                         }
 395                         top->op = op;
 396                         top->left = left;
 397                         top->right = right;
 398                         left = top;
 399                 }
 400         }
 401 out:
 402         *tree = left;
 403         return next;
 404 }
 405
 406 static struct token *multiplicative_expression(struct token *token, struct expression **tree)
 407 {
 408         return lr_binop_expression(token, tree, cast_expression, '*', '/', '%', 0);
 409 }
 410
 411 static struct token *additive_expression(struct token *token, struct expression **tree)
 412 {
 413         return lr_binop_expression(token, tree, multiplicative_expression, '+', '-', 0);
 414 }
 415
 416 static struct token *shift_expression(struct token *token, struct expression **tree)
 417 {
 418         return lr_binop_expression(token, tree, additive_expression, SPECIAL_LEFTSHIFT, SPECIAL_RIGHTSHIFT, 0);
 419 }
 420
 421 static struct token *relational_expression(struct token *token, struct expression **tree)
 422 {
 423         return lr_binop_expression(token, tree, shift_expression, '<', '>', SPECIAL_LTE, SPECIAL_GTE, 0);
 424 }
 425
 426 static struct token *equality_expression(struct token *token, struct expression **tree)
 427 {
 428         return lr_binop_expression(token, tree, relational_expression, SPECIAL_EQUAL, SPECIAL_NOTEQUAL, 0);
 429 }
 430
 431 static struct token *bitwise_and_expression(struct token *token, struct expression **tree)
 432 {
 433         return lr_binop_expression(token, tree, equality_expression, '&', 0);
 434 }
 435
 436 static struct token *bitwise_xor_expression(struct token *token, struct expression **tree)
 437 {
 438         return lr_binop_expression(token, tree, bitwise_and_expression, '^', 0);
 439 }
 440
 441 static struct token *bitwise_or_expression(struct token *token, struct expression **tree)
 442 {
 443         return lr_binop_expression(token, tree, bitwise_xor_expression, '|', 0);
 444 }
 445
 446 static struct token *logical_and_expression(struct token *token, struct expression **tree)
 447 {
 448         return lr_binop_expression(token, tree, bitwise_or_expression, SPECIAL_LOGICAL_AND, 0);
 449 }
 450
 451 static struct token *logical_or_expression(struct token *token, struct expression **tree)
 452 {
 453         return lr_binop_expression(token, tree, logical_and_expression, SPECIAL_LOGICAL_OR, 0);
 454 }
 455
 456 struct token *conditional_expression(struct token *token, struct expression **tree)
 457 {
 458         token = logical_or_expression(token, tree);
 459         if (match_op(token, '?')) {
 460                 struct expression *expr = alloc_expression(token, EXPR_CONDITIONAL);
 461                 expr->op = token->special;
 462                 expr->left = *tree;
 463                 *tree = expr;
 464                 token = parse_expression(token->next, &expr->cond_true);
 465                 token = expect(token, ':', "in conditional expression");
 466                 token = conditional_expression(token, &expr->cond_false);
 467         }
 468         return token;
 469 }
 470
 471 struct token *assignment_expression(struct token *token, struct expression **tree)
 472 {
 473         token = conditional_expression(token, tree);
 474         if (token->type == TOKEN_SPECIAL) {
 475                 static const int assignments[] = {
 476                         '=', SPECIAL_ADD_ASSIGN, SPECIAL_MINUS_ASSIGN,
 477                         SPECIAL_TIMES_ASSIGN, SPECIAL_DIV_ASSIGN,
 478                         SPECIAL_MOD_ASSIGN, SPECIAL_SHL_ASSIGN,
 479                         SPECIAL_SHR_ASSIGN, SPECIAL_AND_ASSIGN,
 480                         SPECIAL_OR_ASSIGN, SPECIAL_XOR_ASSIGN };
 481                 int i, op = token->special;
 482                 for (i = 0; i < sizeof(assignments)/sizeof(int); i++)
 483                         if (assignments[i] == op) {
 484                                 struct expression * expr = alloc_expression(token, EXPR_BINOP);
 485                                 expr->left = *tree;
 486                                 expr->op = op;
 487                                 *tree = expr;
 488                                 return assignment_expression(token->next, &expr->right);
 489                         }
 490         }
 491         return token;
 492 }
 493
 494 struct token *comma_expression(struct token *token, struct expression **tree)
 495 {
 496         return lr_binop_expression(token, tree, assignment_expression, ',', 0);
 497 }
 498
 499 struct token *parse_expression(struct token *token, struct expression **tree)
 500 {
 501         return comma_expression(token,tree);
 502 }
 503
 504 static struct token *struct_declaration_list(struct token *token, struct symbol_list **list);
 505
 506 static void force_default_type(struct ctype *type)
 507 {
 508         if (!type->base_type)
 509                 type->base_type = &int_type;
 510 }
 511
 512 static struct symbol *indirect(struct symbol *base, int type)
 513 {
 514         struct symbol *sym = alloc_symbol(NULL, type);
 515
 516         sym->ctype.base_type = base;
 517         sym->ctype.modifiers = 0;
 518         force_default_type(&sym->ctype);
 519         return sym;
 520 }
 521
 522 static struct symbol *lookup_or_create_symbol(enum namespace ns, enum type type, struct token *token)
 523 {
 524         struct symbol *sym = lookup_symbol(token->ident, ns);
 525         if (!sym) {
 526                 sym = alloc_symbol(token, type);
 527                 bind_symbol(sym, token->ident, ns);
 528         }
 529         return sym;
 530 }
 531
 532 struct token *struct_union_enum_specifier(enum namespace ns, enum type type,
 533         struct token *token, struct ctype *ctype,
 534         struct token *(*parse)(struct token *, struct symbol *))
 535 {
 536         struct symbol *sym;
 537
 538         if (token->type == TOKEN_IDENT) {
 539                 sym = lookup_or_create_symbol(ns, type, token);
 540                 token = token->next;
 541                 ctype->base_type = sym;
 542                 if (match_op(token, '{')) {
 543                         token = parse(token->next, sym);
 544                         token = expect(token, '}', "at end of struct-union-enum-specifier");
 545                 }
 546                 return token;
 547         }
 548
 549         // private struct/union/enum type
 550         if (!match_op(token, '{')) {
 551                 warn(token, "expected declaration");
 552                 ctype->base_type = &bad_type;
 553                 return token;
 554         }
 555
 556         sym = alloc_symbol(token, type);
 557         token = parse(token->next, sym);
 558         ctype->base_type = sym->ctype.base_type;
 559         ctype->modifiers = sym->ctype.modifiers;
 560         return expect(token, '}', "at end of specifier");
 561 }
 562
 563 static struct token *parse_struct_declaration(struct token *token, struct symbol *sym)
 564 {
 565         return struct_declaration_list(token, &sym->symbol_list);
 566 }
 567
 568 struct token *struct_or_union_specifier(enum type type, struct token *token, struct ctype *ctype)
 569 {
 570         return struct_union_enum_specifier(NS_STRUCT, type, token, ctype, parse_struct_declaration);
 571 }
 572
 573 /* FIXME! */
 574 static struct token *parse_enum_declaration(struct token *token, struct symbol *sym)
 575 {
 576         return skip_to(token, '}');
 577 }
 578
 579 struct token *enum_specifier(struct token *token, struct ctype *ctype)
 580 {
 581         return struct_union_enum_specifier(NS_ENUM, SYM_ENUM, token, ctype, parse_enum_declaration);
 582 }
 583
 584 struct token *typeof_specifier(struct token *token, struct ctype *ctype)
 585 {
 586         struct symbol *sym;
 587         struct expression *expr;
 588
 589         if (match_op(token, '(') && lookup_type(token->next)) {
 590                 token = typename(token->next, &sym);
 591                 *ctype = sym->ctype;
 592                 return expect(token, ')', "after typeof");
 593         }
 594         token = parse_expression(token, &expr);
 595         /* look at type.. */
 596         ctype->base_type = &bad_type;
 597         return token;
 598 }
 599
 600 struct token *attribute_specifier(struct token *token, struct ctype *ctype)
 601 {
 602         int parens = 0;
 603
 604         token = expect(token, '(', "after attribute");
 605         token = expect(token, '(', "after attribute");
 606
 607         for (;;) {
 608                 if (eof_token(token))
 609                         break;
 610                 if (match_op(token, ';'))
 611                         break;
 612                 if (match_op(token, ')')) {
 613                         if (!parens)
 614                                 break;
 615                         parens--;
 616                 }
 617                 if (match_op(token, '('))
 618                         parens++;
 619                 token = token->next;
 620         }
 621
 622         token = expect(token, ')', "after attribute");
 623         token = expect(token, ')', "after attribute");
 624         return token;
 625 }
 626
 627 #define MOD_SPECIALBITS (SYM_STRUCTOF | SYM_UNIONOF | SYM_ENUMOF | SYM_ATTRIBUTE | SYM_TYPEOF)
 628
 629 static struct token *declaration_specifiers(struct token *next, struct ctype *ctype)
 630 {
 631         struct token *token;
 632
 633         while ( (token = next) != NULL ) {
 634                 struct ctype thistype;
 635                 struct ident *ident;
 636                 struct symbol *s, *type;
 637
 638                 next = token->next;
 639                 if (token->type != TOKEN_IDENT)
 640                         break;
 641                 ident = token->ident;
 642
 643                 s = lookup_symbol(ident, NS_TYPEDEF);
 644                 if (!s)
 645                         break;
 646                 thistype = s->ctype;
 647                 if (thistype.modifiers & MOD_SPECIALBITS) {
 648                         unsigned long mod = thistype.modifiers;
 649                         thistype.modifiers = mod & ~MOD_SPECIALBITS;
 650                         if (mod & SYM_STRUCTOF)
 651                                 next = struct_or_union_specifier(SYM_STRUCT, next, &thistype);
 652                         else if (mod & SYM_UNIONOF)
 653                                 next = struct_or_union_specifier(SYM_UNION, next, &thistype);
 654                         else if (mod & SYM_ENUMOF)
 655                                 next = enum_specifier(next, &thistype);
 656                         else if (mod & SYM_ATTRIBUTE)
 657                                 next = attribute_specifier(next, &thistype);
 658                         else if (mod & SYM_TYPEOF)
 659                                 next = typeof_specifier(next, &thistype);
 660                 }
 661
 662                 type = s->ctype.base_type;
 663                 if (type) {
 664                         if (type != ctype->base_type) {
 665                                 if (ctype->base_type) {
 666                                         warn(token, "Strange mix of types");
 667                                         continue;
 668                                 }
 669                                 ctype->base_type = type;
 670                         }
 671                 }
 672                 if (thistype.modifiers) {
 673                         unsigned long old = ctype->modifiers;
 674                         unsigned long extra = 0, dup;
 675
 676                         if (thistype.modifiers & old & SYM_LONG) {
 677                                 extra = SYM_LONGLONG | SYM_LONG;
 678                                 thistype.modifiers &= ~SYM_LONG;
 679                                 old &= ~SYM_LONG;
 680                         }
 681                         dup = (thistype.modifiers & old) | (extra & old) | (extra & thistype.modifiers);
 682                         if (dup)
 683                                 warn(token, "Just how %s do you want this type to be?",
 684                                         modifier_string(dup));
 685                         ctype->modifiers = old | thistype.modifiers | extra;
 686                 }
 687         }
 688         return token;
 689 }
 690
 691 static int constant_value(struct expression *expr)
 692 {
 693         return 0;
 694 }
 695
 696 static struct token *abstract_array_declarator(struct token *token, struct symbol **tree)
 697 {
 698         struct expression *expr;
 699         struct symbol *sym = *tree;
 700         token = parse_expression(token, &expr);
 701         sym->size = constant_value(expr);
 702         return token;
 703 }
 704
 705 static struct token *abstract_function_declarator(struct token *, struct symbol_list **);
 706 static struct token *declarator(struct token *token, struct symbol **tree, struct token **p);
 707
 708 static struct token *direct_declarator(struct token *token, struct symbol **tree, struct token **p)
 709 {
 710         if (p && token->type == TOKEN_IDENT) {
 711                 if (lookup_symbol(token->ident, NS_TYPEDEF)) {
 712                         warn(token, "unexpected type/qualifier");
 713                         return token;
 714                 }
 715                 *p = token;
 716                 token = token->next;
 717         }
 718
 719         for (;;) {
 720                 if (match_ident(token, &__attribute___ident) || match_ident(token, &__attribute_ident)) {
 721                         struct ctype ctype = { 0, };
 722                         token = attribute_specifier(token->next, &ctype);
 723                         continue;
 724                 }
 725                 if (token->type != TOKEN_SPECIAL)
 726                         return token;
 727
 728                 /*
 729                  * This can be either a parameter list or a grouping.
 730                  * For the direct (non-abstract) case, we know if must be
 731                  * a paramter list if we already saw the identifier.
 732                  * For the abstract case, we know if must be a parameter
 733                  * list if it is empty or starts with a type.
 734                  */
 735                 if (token->special == '(') {
 736                         struct token *next = token->next;
 737                         int fn = (p && *p) || match_op(next, ')') || lookup_type(next);
 738
 739                         if (!fn) {
 740                                 token = declarator(next, tree, p);
 741                                 token = expect(token, ')', "in nested declarator");
 742                                 continue;
 743                         }
 744
 745                         *tree = indirect(*tree, SYM_FN);
 746                         token = abstract_function_declarator(next, &(*tree)->arguments);
 747                         token = expect(token, ')', "in function declarator");
 748                         continue;
 749                 }
 750                 if (token->special == '[') {
 751                         *tree = indirect(*tree, SYM_ARRAY);
 752                         token = abstract_array_declarator(token->next, tree);
 753                         token = expect(token, ']', "in abstract_array_declarator");
 754                         continue;
 755                 }
 756                 if (token->special == ':') {
 757                         struct expression *expr;
 758                         *tree = indirect(*tree, SYM_BITFIELD);
 759                         token = conditional_expression(token->next, &expr);
 760                         continue;
 761                 }
 762                 break;
 763         }
 764         if (p) {
 765                 (*tree)->token = *p;
 766                 (*tree)->ident = *p;
 767         }
 768         return token;
 769 }
 770
 771 static struct token *pointer(struct token *token, struct symbol **tree, struct ctype *ctype)
 772 {
 773         force_default_type(ctype);
 774         (*tree)->ctype = *ctype;
 775         while (match_op(token,'*')) {
 776                 struct symbol *sym;
 777                 sym = alloc_symbol(token, SYM_PTR);
 778                 sym->ctype.base_type = *tree;
 779                 *tree = sym;
 780                 token = declaration_specifiers(token->next, &sym->ctype);
 781         }
 782         return token;
 783 }
 784
 785 static struct token *declarator(struct token *token, struct symbol **tree, struct token **p)
 786 {
 787         token = pointer(token, tree, &(*tree)->ctype);
 788         return direct_declarator(token, tree, p);
 789 }
 790
 791 static struct token *struct_declaration_list(struct token *token, struct symbol_list **list)
 792 {
 793         for (;;) {
 794                 struct ctype ctype = {0, };
 795
 796                 token = declaration_specifiers(token, &ctype);
 797                 for (;;) {
 798                         struct symbol *spec = alloc_symbol(token, SYM_TYPE);
 799                         struct ctype *base_type = &ctype;
 800                         struct symbol *declaration = spec;
 801                         struct token *ident = NULL;
 802                         token = pointer(token, &declaration, base_type);
 803                         token = direct_declarator(token, &declaration, &ident);
 804                         if (match_op(token, ':')) {
 805                                 struct expression *expr;
 806                                 token = parse_expression(token->next, &expr);
 807                         }
 808                         add_symbol(list, declaration);
 809                         if (!match_op(token, ','))
 810                                 break;
 811                         token = token->next;
 812                 }
 813                 if (!match_op(token, ';'))
 814                         break;
 815                 token = token->next;
 816         }
 817         return token;
 818 }
 819
 820 static struct token *parameter_declaration(struct token *token, struct symbol **tree)
 821 {
 822         struct token *ident = NULL;
 823         struct ctype ctype = { 0, }, *base_type;
 824
 825         token = declaration_specifiers(token, &ctype);
 826         *tree = alloc_symbol(token, SYM_TYPE);
 827         base_type = &ctype;
 828         token = pointer(token, tree, base_type);
 829         token = direct_declarator(token, tree, &ident);
 830         return token;
 831 }
 832
 833 static struct token *typename(struct token *token, struct symbol **p)
 834 {
 835         struct ctype ctype = { 0, };
 836         struct symbol *sym = alloc_symbol(token, SYM_TYPE);
 837         *p = sym;
 838         token = declaration_specifiers(token, &ctype);
 839         return declarator(token, &sym, NULL);
 840 }
 841
 842 struct token *expression_statement(struct token *token, struct expression **tree)
 843 {
 844         token = parse_expression(token, tree);
 845         return expect(token, ';', "at end of statement");
 846 }
 847
 848 static struct token *parse_asm_operands(struct token *token, struct statement *stmt)
 849 {
 850         struct expression *expr;
 851
 852         /* Allow empty operands */
 853         if (match_op(token->next, ':') || match_op(token->next, ')'))
 854                 return token->next;
 855         do {
 856                 token = primary_expression(token->next, &expr);
 857                 token = parens_expression(token, &expr, "in asm parameter");
 858         } while (match_op(token, ','));
 859         return token;
 860 }
 861
 862 static struct token *parse_asm_clobbers(struct token *token, struct statement *stmt)
 863 {
 864         struct expression *expr;
 865
 866         do {
 867                 token = primary_expression(token->next, &expr);
 868         } while (match_op(token, ','));
 869         return token;
 870 }
 871
 872 struct token *statement(struct token *token, struct statement **tree)
 873 {
 874         struct statement *stmt = alloc_statement(token, STMT_NONE);
 875
 876         *tree = stmt;
 877         if (token->type == TOKEN_IDENT) {
 878                 if (token->ident == &if_ident) {
 879                         stmt->type = STMT_IF;
 880                         token = parens_expression(token->next, &stmt->if_conditional, "after if");
 881                         token = statement(token, &stmt->if_true);
 882                         if (token->type != TOKEN_IDENT)
 883                                 return token;
 884                         if (token->ident != &else_ident)
 885                                 return token;
 886                         return statement(token->next, &stmt->if_false);
 887                 }
 888                 if (token->ident == &return_ident) {
 889                         stmt->type = STMT_RETURN;
 890                         return expression_statement(token->next, &stmt->expression);
 891                 }
 892                 if (token->ident == &break_ident) {
 893                         stmt->type = STMT_BREAK;
 894                         return expect(token->next, ';', "at end of statement");
 895                 }
 896                 if (token->ident == &continue_ident) {
 897                         stmt->type = STMT_CONTINUE;
 898                         return expect(token->next, ';', "at end of statement");
 899                 }
 900                 if (token->ident == &default_ident) {
 901                         token = token->next;
 902                         goto default_statement;
 903                 }
 904                 if (token->ident == &case_ident) {
 905                         token = parse_expression(token->next, &stmt->case_expression);
 906                         if (match_op(token, SPECIAL_ELLIPSIS))
 907                                 token = parse_expression(token->next, &stmt->case_to);
 908 default_statement:
 909                         stmt->type = STMT_CASE;
 910                         token = expect(token, ':', "after default/case");
 911                         return statement(token, &stmt->case_statement);
 912                 }
 913                 if (token->ident == &switch_ident) {
 914                         stmt->type = STMT_SWITCH;
 915                         token = parens_expression(token->next, &stmt->switch_expression, "after 'switch'");
 916                         return statement(token, &stmt->switch_statement);
 917                 }
 918                 if (token->ident == &for_ident) {
 919                         stmt->type = STMT_FOR;
 920                         token = expect(token->next, '(', "after 'for'");
 921                         token = parse_expression(token, &stmt->e1);
 922                         token = expect(token, ';', "in 'for'");
 923                         token = parse_expression(token, &stmt->e2);
 924                         token = expect(token, ';', "in 'for'");
 925                         token = parse_expression(token, &stmt->e3);
 926                         token = expect(token, ')', "in 'for'");
 927                         return statement(token, &stmt->iterate);
 928                 }
 929                 if (token->ident == &while_ident) {
 930                         stmt->type = STMT_WHILE;
 931                         token = parens_expression(token->next, &stmt->e1, "after 'while'");
 932                         return statement(token, &stmt->iterate);
 933                 }
 934                 if (token->ident == &do_ident) {
 935                         stmt->type = STMT_DO;
 936                         token = statement(token->next, &stmt->iterate);
 937                         if (token->type == TOKEN_IDENT && token->ident == &while_ident)
 938                                 token = token->next;
 939                         else
 940                                 warn(token, "expected 'while' after 'do'");
 941                         token = parens_expression(token, &stmt->e1, "after 'do-while'");
 942                         return expect(token, ';', "after statement");
 943                 }
 944                 if (token->ident == &goto_ident) {
 945                         stmt->type = STMT_GOTO;
 946                         token = token->next;
 947                         if (token->type == TOKEN_IDENT) {
 948                                 stmt->goto_label = token;
 949                                 token = token->next;
 950                         } else
 951                                 warn(token, "invalid label");
 952                         return expect(token, ';', "at end of statement");
 953                 }
 954                 if (token->ident == &asm_ident || token->ident == &__asm___ident || token->ident == &__asm_ident) {
 955                         struct expression *expr;
 956                         stmt->type = STMT_ASM;
 957                         token = token->next;
 958                         if (token->type == TOKEN_IDENT) {
 959                                 if (token->ident == &__volatile___ident || token->ident == &volatile_ident)
 960                                         token = token->next;
 961                         }
 962                         token = expect(token, '(', "after asm");
 963                         token = parse_expression(token->next, &expr);
 964                         if (match_op(token, ':'))
 965                                 token = parse_asm_operands(token, stmt);
 966                         if (match_op(token, ':'))
 967                                 token = parse_asm_operands(token, stmt);
 968                         if (match_op(token, ':'))
 969                                 token = parse_asm_clobbers(token, stmt);
 970                         token = expect(token, ')', "after asm");
 971                         return expect(token, ';', "at end of asm-statement");
 972                 }
 973                 if (match_op(token->next, ':')) {
 974                         stmt->type = STMT_LABEL;
 975                         stmt->label_identifier = token;
 976                         return statement(token->next->next, &stmt->label_statement);
 977                 }
 978         }
 979
 980         if (match_op(token, '{')) {
 981                 stmt->type = STMT_COMPOUND;
 982                 start_symbol_scope();
 983                 token = compound_statement(token->next, stmt);
 984                 end_symbol_scope();
 985
 986                 return expect(token, '}', "at end of compound statement");
 987         }
 988
 989         stmt->type = STMT_EXPRESSION;
 990         return expression_statement(token, &stmt->expression);
 991 }
 992
 993 struct token * statement_list(struct token *token, struct statement_list **list)
 994 {
 995         for (;;) {
 996                 struct statement * stmt;
 997                 if (eof_token(token))
 998                         break;
 999                 if (match_op(token, '}'))
1000                         break;
1001                 token = statement(token, &stmt);
1002                 add_statement(list, stmt);
1003         }
1004         return token;
1005 }
1006
1007 static struct token *parameter_type_list(struct token *token, struct symbol_list **list)
1008 {
1009         for (;;) {
1010                 struct symbol *sym = alloc_symbol(token, SYM_TYPE);
1011
1012                 token = parameter_declaration(token, &sym);
1013                 add_symbol(list, sym);
1014                 if (!match_op(token, ','))
1015                         break;
1016                 token = token->next;
1017
1018                 if (match_op(token, SPECIAL_ELLIPSIS)) {
1019                         /* FIXME: mark the function */
1020                         token = token->next;
1021                         break;
1022                 }
1023         }
1024         return token;
1025 }
1026
1027 static struct token *abstract_function_declarator(struct token *token, struct symbol_list **list)
1028 {
1029         return parameter_type_list(token, list);
1030 }
1031
1032 static struct token *external_declaration(struct token *token, struct symbol_list **list);
1033
1034 static struct token *compound_statement(struct token *token, struct statement *stmt)
1035 {
1036         while (!eof_token(token)) {
1037                 if (!lookup_type(token))
1038                         break;
1039                 token = external_declaration(token, &stmt->syms);
1040         }
1041         token = statement_list(token, &stmt->stmts);
1042         return token;
1043 }
1044
1045 static struct token *initializer_list(struct token *token, struct ctype *type)
1046 {
1047         for (;;) {
1048                 token = initializer(token, type);
1049                 if (!match_op(token, ','))
1050                         break;
1051                 token = token->next;
1052         }
1053         return token;
1054 }
1055
1056 static struct token *initializer(struct token *token, struct ctype *type)
1057 {
1058         struct expression *expr;
1059         if (match_op(token, '{')) {
1060                 token = initializer_list(token->next, type);
1061                 return expect(token, '}', "at end of initializer");
1062         }
1063         return assignment_expression(token, &expr);
1064 }
1065
1066 static void declare_argument(struct symbol *sym, void *data, int flags)
1067 {
1068         if (!sym->ident) {
1069                 warn(sym->token, "no identifier for function argument");
1070                 return;
1071         }
1072         bind_symbol(sym, sym->ident->ident, NS_SYMBOL);
1073 }
1074
1075 static struct token *external_declaration(struct token *token, struct symbol_list **list)
1076 {
1077         struct token *ident = NULL;
1078         struct symbol *decl;
1079         struct ctype ctype = { 0, };
1080
1081         /* Parse declaration-specifiers, if any */
1082         token = declaration_specifiers(token, &ctype);
1083
1084         decl = alloc_symbol(token, SYM_TYPE);
1085         token = pointer(token, &decl, &ctype);
1086         token = declarator(token, &decl, &ident);
1087
1088         /* Just a type declaration? */
1089         if (!ident)
1090                 return expect(token, ';', "end of type declaration");
1091
1092         /* type define declaration? */
1093         if (ctype.modifiers & SYM_TYPEDEF) {
1094                 ctype.modifiers &= ~SYM_TYPEDEF;
1095                 bind_symbol(indirect(decl, SYM_TYPEDEF), ident->ident, NS_TYPEDEF);
1096                 return expect(token, ';', "end of typedef");
1097         }
1098
1099         decl->ident = ident;
1100         add_symbol(list, decl);
1101         bind_symbol(decl, ident->ident, NS_SYMBOL);
1102
1103         if (decl->type == SYM_FN && match_op(token, '{')) {
1104                 decl->stmt = alloc_statement(token, STMT_COMPOUND);
1105                 start_symbol_scope();
1106                 symbol_iterate(decl->arguments, declare_argument, NULL);
1107                 token = compound_statement(token->next, decl->stmt);
1108                 end_symbol_scope();
1109                 return expect(token, '}', "at end of function");
1110         }
1111
1112         for (;;) {
1113                 if (match_op(token, '='))
1114                         token = initializer(token->next, &decl->ctype);
1115                 if (!match_op(token, ','))
1116                         break;
1117
1118                 ident = NULL;
1119                 decl = alloc_symbol(token, SYM_TYPE);
1120                 token = pointer(token, &decl, &ctype);
1121                 token = declarator(token->next, &decl, &ident);
1122                 if (!ident) {
1123                         warn(token, "expected identifier name in type definition");
1124                         return token;
1125                 }
1126
1127                 add_symbol(list, decl);
1128                 bind_symbol(decl, ident->ident, NS_SYMBOL);
1129         }
1130         return expect(token, ';', "at end of declaration");
1131 }
1132
1133 void translation_unit(struct token *token, struct symbol_list **list)
1134 {
1135         while (!eof_token(token))
1136                 token = external_declaration(token, list);
1137 }