parse.c

   1 /*
   2  * Stupid C parser, version 1e-6.
   3  *
   4  * Let's see how hard this is to do.
   5  *
   6  * Copyright (C) 2003 Transmeta Corp, all rights reserved.
   7  */
   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 #include "expression.h"
  23
  24 struct statement *alloc_statement(struct position pos, int type)
  25 {
  26         struct statement *stmt = __alloc_statement(0);
  27         stmt->type = type;
  28         stmt->pos = pos;
  29         return stmt;
  30 }
  31
  32 static struct token *struct_declaration_list(struct token *token, struct symbol_list **list);
  33
  34 static struct symbol * indirect(struct position pos, struct ctype *ctype, int type)
  35 {
  36         struct symbol *sym = alloc_symbol(pos, type);
  37
  38         sym->ctype.base_type = ctype->base_type;
  39         sym->ctype.modifiers = ctype->modifiers & ~MOD_STORAGE;
  40
  41         ctype->base_type = sym;
  42         ctype->modifiers &= MOD_STORAGE;
  43         return sym;
  44 }
  45
  46 static struct symbol *lookup_or_create_symbol(enum namespace ns, enum type type, struct token *token)
  47 {
  48         struct symbol *sym = lookup_symbol(token->ident, ns);
  49         if (!sym) {
  50                 sym = alloc_symbol(token->pos, type);
  51                 sym->ident = token->ident;
  52                 bind_symbol(sym, token->ident, ns);
  53         }
  54         return sym;
  55 }
  56
  57 /*
  58  * NOTE! NS_LABEL is not just a different namespace,
  59  * it also ends up using function scope instead of the
  60  * regular symbol scope.
  61  */
  62 static struct symbol *label_symbol(struct token *token)
  63 {
  64         return lookup_or_create_symbol(NS_LABEL, SYM_LABEL, token);
  65 }
  66
  67 struct token *struct_union_enum_specifier(enum namespace ns, enum type type,
  68         struct token *token, struct ctype *ctype,
  69         struct token *(*parse)(struct token *, struct symbol *))
  70 {
  71         struct symbol *sym;
  72
  73         ctype->modifiers = 0;
  74         if (token_type(token) == TOKEN_IDENT) {
  75                 sym = lookup_or_create_symbol(ns, type, token);
  76                 token = token->next;
  77                 ctype->base_type = sym;
  78                 if (match_op(token, '{')) {
  79                         token = parse(token->next, sym);
  80                         token = expect(token, '}', "at end of struct-union-enum-specifier");
  81                 }
  82                 return token;
  83         }
  84
  85         // private struct/union/enum type
  86         if (!match_op(token, '{')) {
  87                 warn(token->pos, "expected declaration");
  88                 ctype->base_type = &bad_type;
  89                 return token;
  90         }
  91
  92         sym = alloc_symbol(token->pos, type);
  93         token = parse(token->next, sym);
  94         ctype->base_type = sym;
  95         return expect(token, '}', "at end of specifier");
  96 }
  97
  98 static struct token *parse_struct_declaration(struct token *token, struct symbol *sym)
  99 {
 100         return struct_declaration_list(token, &sym->symbol_list);
 101 }
 102
 103 struct token *struct_or_union_specifier(enum type type, struct token *token, struct ctype *ctype)
 104 {
 105         return struct_union_enum_specifier(NS_STRUCT, type, token, ctype, parse_struct_declaration);
 106 }
 107
 108 static struct token *parse_enum_declaration(struct token *token, struct symbol *parent)
 109 {
 110         int nextval = 0;
 111         while (token_type(token) == TOKEN_IDENT) {
 112                 struct token *next = token->next;
 113                 struct symbol *sym;
 114
 115                 sym = alloc_symbol(token->pos, SYM_NODE);
 116                 bind_symbol(sym, token->ident, NS_SYMBOL);
 117                 sym->ctype.base_type = parent;
 118
 119                 if (match_op(next, '=')) {
 120                         struct expression *expr;
 121                         next = constant_expression(next->next, &expr);
 122                         nextval = get_expression_value(expr);
 123                 }
 124                 sym->value = nextval;
 125
 126                 token = next;
 127                 if (!match_op(token, ','))
 128                         break;
 129                 token = token->next;
 130                 nextval = nextval + 1;
 131         }
 132         return token;
 133 }
 134
 135 struct token *enum_specifier(struct token *token, struct ctype *ctype)
 136 {
 137         return struct_union_enum_specifier(NS_ENUM, SYM_ENUM, token, ctype, parse_enum_declaration);
 138 }
 139
 140 struct token *typeof_specifier(struct token *token, struct ctype *ctype)
 141 {
 142         struct symbol *sym;
 143
 144         if (!match_op(token, '(')) {
 145                 warn(token->pos, "expected '(' after typeof");
 146                 return token;
 147         }
 148         if (lookup_type(token->next)) {
 149                 token = typename(token->next, &sym);
 150                 *ctype = sym->ctype;
 151         } else {
 152                 struct symbol *typeof_sym = alloc_symbol(token->pos, SYM_TYPEOF);
 153                 token = parse_expression(token->next, &typeof_sym->initializer);
 154
 155                 ctype->modifiers = 0;
 156                 ctype->base_type = typeof_sym;
 157         }
 158         return expect(token, ')', "after typeof");
 159 }
 160
 161 static void handle_attribute(struct ctype *ctype, struct ident *attribute, struct expression *expr)
 162 {
 163         if (match_string_ident(attribute, "packed")) {
 164                 ctype->alignment = 1;
 165                 return;
 166         }
 167         if (match_string_ident(attribute, "aligned")) {
 168                 ctype->alignment = get_expression_value(expr);
 169                 return;
 170         }
 171         if (match_string_ident(attribute, "nocast")) {
 172                 ctype->modifiers |= MOD_NOCAST;
 173                 return;
 174         }
 175         if (match_string_ident(attribute, "noderef")) {
 176                 ctype->modifiers |= MOD_NODEREF;
 177                 return;
 178         }
 179         if (match_string_ident(attribute, "address_space")) {
 180                 ctype->as = get_expression_value(expr);
 181                 return;
 182         }
 183         if (match_string_ident(attribute, "context")) {
 184                 if (expr->type == EXPR_COMMA) {
 185                         int mask = get_expression_value(expr->left);
 186                         int value = get_expression_value(expr->right);
 187                         if (value & ~mask) {
 188                                 warn(expr->pos, "nonsense attribute types");
 189                                 return;
 190                         }
 191                         ctype->contextmask |= mask;
 192                         ctype->context |= value;
 193                         return;
 194                 }
 195         }
 196 }
 197
 198
 199 struct token *attribute_specifier(struct token *token, struct ctype *ctype)
 200 {
 201         ctype->modifiers = 0;
 202         token = expect(token, '(', "after attribute");
 203         token = expect(token, '(', "after attribute");
 204
 205         for (;;) {
 206                 struct ident *attribute_name;
 207                 struct expression *attribute_expr;
 208
 209                 if (eof_token(token))
 210                         break;
 211                 if (match_op(token, ';'))
 212                         break;
 213                 if (token_type(token) != TOKEN_IDENT)
 214                         break;
 215                 attribute_name = token->ident;
 216                 token = token->next;
 217                 attribute_expr = NULL;
 218                 if (match_op(token, '('))
 219                         token = parens_expression(token, &attribute_expr, "in attribute");
 220                 handle_attribute(ctype, attribute_name, attribute_expr);
 221                 if (!match_op(token, ','))
 222                         break;
 223                 token = token->next;
 224         }
 225
 226         token = expect(token, ')', "after attribute");
 227         token = expect(token, ')', "after attribute");
 228         return token;
 229 }
 230
 231 #define MOD_SPECIALBITS (MOD_STRUCTOF | MOD_UNIONOF | MOD_ENUMOF | MOD_ATTRIBUTE | MOD_TYPEOF)
 232 #define MOD_SPECIFIER (MOD_CHAR | MOD_SHORT | MOD_LONG | MOD_LONGLONG | MOD_SIGNED | MOD_UNSIGNED)
 233
 234 struct symbol * ctype_integer(unsigned int spec)
 235 {
 236         static struct symbol *const integer_ctypes[][2] = {
 237                 { &llong_ctype, &ullong_ctype },
 238                 { &long_ctype,  &ulong_ctype  },
 239                 { &short_ctype, &ushort_ctype },
 240                 { &char_ctype,  &uchar_ctype  },
 241                 { &int_ctype,   &uint_ctype   },
 242         };
 243         struct symbol *const (*ctype)[2];
 244
 245         ctype = integer_ctypes;
 246         if (!(spec & MOD_LONGLONG)) {
 247                 ctype++;
 248                 if (!(spec & MOD_LONG)) {
 249                         ctype++;
 250                         if (!(spec & MOD_SHORT)) {
 251                                 ctype++;
 252                                 if (!(spec & MOD_CHAR))
 253                                         ctype++;
 254                         }
 255                 }
 256         }
 257         return ctype[0][(spec & MOD_UNSIGNED) != 0];
 258 }
 259
 260 struct symbol * ctype_fp(unsigned int spec)
 261 {
 262         if (spec & MOD_LONGLONG)
 263                 return &ldouble_ctype;
 264         if (spec & MOD_LONG)
 265                 return &double_ctype;
 266         return &float_ctype;
 267 }
 268
 269 static void apply_ctype(struct position pos, struct ctype *thistype, struct ctype *ctype)
 270 {
 271         unsigned long mod = thistype->modifiers;
 272
 273         if (mod) {
 274                 unsigned long old = ctype->modifiers;
 275                 unsigned long extra = 0, dup;
 276
 277                 if (mod & old & MOD_LONG) {
 278                         extra = MOD_LONGLONG | MOD_LONG;
 279                         mod &= ~MOD_LONG;
 280                         old &= ~MOD_LONG;
 281                 }
 282                 dup = (mod & old) | (extra & old) | (extra & mod);
 283                 if (dup)
 284                         warn(pos, "Just how %sdo you want this type to be?",
 285                                 modifier_string(dup));
 286                 ctype->modifiers = old | mod | extra;
 287         }
 288
 289         /* Context mask and value */
 290         if ((ctype->context ^ thistype->context) & (ctype->contextmask & thistype->contextmask)) {
 291                 warn(pos, "inconsistend attribute types");
 292                 thistype->context = 0;
 293                 thistype->contextmask = 0;
 294         }
 295         ctype->context |= thistype->context;
 296         ctype->contextmask |= thistype->contextmask;
 297
 298         /* Alignment */
 299         if (thistype->alignment & (thistype->alignment-1)) {
 300                 warn(pos, "I don't like non-power-of-2 alignments");
 301                 thistype->alignment = 0;
 302         }
 303         if (thistype->alignment > ctype->alignment)
 304                 ctype->alignment = thistype->alignment;
 305
 306         /* Address space */
 307         ctype->as = thistype->as;
 308 }
 309
 310
 311 static struct token *declaration_specifiers(struct token *next, struct ctype *ctype, int qual)
 312 {
 313         struct token *token;
 314
 315         while ( (token = next) != NULL ) {
 316                 struct ctype thistype;
 317                 struct ident *ident;
 318                 struct symbol *s, *type;
 319                 unsigned long mod;
 320
 321                 next = token->next;
 322                 if (token_type(token) != TOKEN_IDENT)
 323                         break;
 324                 ident = token->ident;
 325
 326                 s = lookup_symbol(ident, NS_TYPEDEF);
 327                 if (!s)
 328                         break;
 329                 thistype = s->ctype;
 330                 mod = thistype.modifiers;
 331                 if (qual && (mod & ~(MOD_ATTRIBUTE | MOD_CONST | MOD_VOLATILE)))
 332                         break;
 333                 if (mod & MOD_SPECIALBITS) {
 334                         if (mod & MOD_STRUCTOF)
 335                                 next = struct_or_union_specifier(SYM_STRUCT, next, &thistype);
 336                         else if (mod & MOD_UNIONOF)
 337                                 next = struct_or_union_specifier(SYM_UNION, next, &thistype);
 338                         else if (mod & MOD_ENUMOF)
 339                                 next = enum_specifier(next, &thistype);
 340                         else if (mod & MOD_ATTRIBUTE)
 341                                 next = attribute_specifier(next, &thistype);
 342                         else if (mod & MOD_TYPEOF)
 343                                 next = typeof_specifier(next, &thistype);
 344                         mod = thistype.modifiers;
 345                 }
 346                 type = thistype.base_type;
 347                 if (type) {
 348                         if (qual)
 349                                 break;
 350                         if (type != ctype->base_type) {
 351                                 if (ctype->base_type) {
 352                                         warn(token->pos, "Strange mix of types");
 353                                         continue;
 354                                 }
 355                                 ctype->base_type = type;
 356                         }
 357                 }
 358
 359                 apply_ctype(token->pos, &thistype, ctype);
 360         }
 361
 362         /* Turn the "virtual types" into real types with real sizes etc */
 363         if (!ctype->base_type && (ctype->modifiers & MOD_SPECIFIER))
 364                 ctype->base_type = &int_type;
 365
 366         if (ctype->base_type == &int_type) {
 367                 ctype->base_type = ctype_integer(ctype->modifiers & MOD_SPECIFIER);
 368                 ctype->modifiers &= ~MOD_SPECIFIER;
 369                 return token;
 370         }
 371         if (ctype->base_type == &fp_type) {
 372                 ctype->base_type = ctype_fp(ctype->modifiers & MOD_SPECIFIER);
 373                 ctype->modifiers &= ~MOD_SPECIFIER;
 374                 return token;
 375         }
 376         return token;
 377 }
 378
 379 static struct token *abstract_array_declarator(struct token *token, struct symbol *sym)
 380 {
 381         struct expression *expr = NULL;
 382
 383         token = parse_expression(token, &expr);
 384         if (expr)
 385                 sym->array_size = get_expression_value(expr);
 386         else
 387                 sym->array_size = -1;
 388         return token;
 389 }
 390
 391 static struct token *parameter_type_list(struct token *, struct symbol *);
 392 static struct token *declarator(struct token *token, struct symbol **tree, struct ident **p);
 393
 394 static struct token *direct_declarator(struct token *token, struct symbol **tree, struct ident **p)
 395 {
 396         struct ctype *ctype = &(*tree)->ctype;
 397
 398         if (p && token_type(token) == TOKEN_IDENT) {
 399                 *p = token->ident;
 400                 token = token->next;
 401         }
 402
 403         for (;;) {
 404                 if (match_ident(token, &__attribute___ident) || match_ident(token, &__attribute_ident)) {
 405                         struct ctype thistype = { 0, };
 406                         token = attribute_specifier(token->next, &thistype);
 407                         apply_ctype(token->pos, &thistype, ctype);
 408                         continue;
 409                 }
 410                 if (token_type(token) != TOKEN_SPECIAL)
 411                         return token;
 412
 413                 /*
 414                  * This can be either a parameter list or a grouping.
 415                  * For the direct (non-abstract) case, we know if must be
 416                  * a paramter list if we already saw the identifier.
 417                  * For the abstract case, we know if must be a parameter
 418                  * list if it is empty or starts with a type.
 419                  */
 420                 if (token->special == '(') {
 421                         struct symbol *sym;
 422                         struct token *next = token->next;
 423                         int fn = (p && *p) || match_op(next, ')') || lookup_type(next);
 424
 425                         if (!fn) {
 426                                 struct symbol *base_type = ctype->base_type;
 427                                 token = declarator(next, tree, p);
 428                                 token = expect(token, ')', "in nested declarator");
 429                                 while (ctype->base_type != base_type)
 430                                         ctype = &ctype->base_type->ctype;
 431                                 p = NULL;
 432                                 continue;
 433                         }
 434
 435                         sym = indirect(token->pos, ctype, SYM_FN);
 436                         token = parameter_type_list(next, sym);
 437                         token = expect(token, ')', "in function declarator");
 438                         continue;
 439                 }
 440                 if (token->special == '[') {
 441                         struct symbol *array = indirect(token->pos, ctype, SYM_ARRAY);
 442                         token = abstract_array_declarator(token->next, array);
 443                         token = expect(token, ']', "in abstract_array_declarator");
 444                         ctype = &array->ctype;
 445                         continue;
 446                 }
 447                 if (token->special == ':') {
 448                         struct symbol *bitfield;
 449                         struct expression *expr;
 450                         bitfield = indirect(token->pos, ctype, SYM_BITFIELD);
 451                         token = conditional_expression(token->next, &expr);
 452                         bitfield->fieldwidth = get_expression_value(expr);
 453                         continue;
 454                 }
 455                 break;
 456         }
 457         if (p) {
 458                 (*tree)->ident = *p;
 459         }
 460         return token;
 461 }
 462
 463 static struct token *pointer(struct token *token, struct ctype *ctype)
 464 {
 465         unsigned long modifiers;
 466         struct symbol *base_type;
 467
 468         modifiers = ctype->modifiers & ~(MOD_TYPEDEF | MOD_ATTRIBUTE);
 469         base_type = ctype->base_type;
 470         ctype->modifiers = modifiers;
 471
 472         while (match_op(token,'*')) {
 473                 struct symbol *ptr = alloc_symbol(token->pos, SYM_PTR);
 474                 ptr->ctype.modifiers = modifiers & ~MOD_STORAGE;
 475                 ptr->ctype.as = ctype->as;
 476                 ptr->ctype.context = ctype->context;
 477                 ptr->ctype.contextmask = ctype->contextmask;
 478                 ptr->ctype.base_type = base_type;
 479
 480                 base_type = ptr;
 481                 ctype->modifiers = modifiers & MOD_STORAGE;
 482                 ctype->base_type = base_type;
 483                 ctype->as = 0;
 484                 ctype->context = 0;
 485                 ctype->contextmask = 0;
 486
 487                 token = declaration_specifiers(token->next, ctype, 1);
 488         }
 489         return token;
 490 }
 491
 492 static struct token *declarator(struct token *token, struct symbol **tree, struct ident **p)
 493 {
 494         token = pointer(token, &(*tree)->ctype);
 495         return direct_declarator(token, tree, p);
 496 }
 497
 498 static struct token *struct_declaration_list(struct token *token, struct symbol_list **list)
 499 {
 500         while (!match_op(token, '}')) {
 501                 struct ctype ctype = {0, };
 502
 503                 token = declaration_specifiers(token, &ctype, 0);
 504                 for (;;) {
 505                         struct ident *ident = NULL;
 506                         struct symbol *decl = alloc_symbol(token->pos, SYM_NODE);
 507                         decl->ctype = ctype;
 508                         token = pointer(token, &decl->ctype);
 509                         token = direct_declarator(token, &decl, &ident);
 510                         if (match_op(token, ':')) {
 511                                 struct expression *expr;
 512                                 token = parse_expression(token->next, &expr);
 513                         }
 514                         add_symbol(list, decl);
 515                         if (!match_op(token, ','))
 516                                 break;
 517                         token = token->next;
 518                 }
 519                 if (!match_op(token, ';'))
 520                         break;
 521                 token = token->next;
 522         }
 523         return token;
 524 }
 525
 526 static struct token *parameter_declaration(struct token *token, struct symbol **tree)
 527 {
 528         struct ident *ident = NULL;
 529         struct symbol *sym;
 530         struct ctype ctype = { 0, };
 531
 532         token = declaration_specifiers(token, &ctype, 0);
 533         sym = alloc_symbol(token->pos, SYM_NODE);
 534         sym->ctype = ctype;
 535         *tree = sym;
 536         token = pointer(token, &sym->ctype);
 537         token = direct_declarator(token, tree, &ident);
 538         return token;
 539 }
 540
 541 struct token *typename(struct token *token, struct symbol **p)
 542 {
 543         struct symbol *sym = alloc_symbol(token->pos, SYM_NODE);
 544         *p = sym;
 545         token = declaration_specifiers(token, &sym->ctype, 0);
 546         return declarator(token, &sym, NULL);
 547 }
 548
 549 struct token *expression_statement(struct token *token, struct expression **tree)
 550 {
 551         token = parse_expression(token, tree);
 552         return expect(token, ';', "at end of statement");
 553 }
 554
 555 static struct token *parse_asm_operands(struct token *token, struct statement *stmt)
 556 {
 557         struct expression *expr;
 558
 559         /* Allow empty operands */
 560         if (match_op(token->next, ':') || match_op(token->next, ')'))
 561                 return token->next;
 562         do {
 563                 token = primary_expression(token->next, &expr);
 564                 token = parens_expression(token, &expr, "in asm parameter");
 565         } while (match_op(token, ','));
 566         return token;
 567 }
 568
 569 static struct token *parse_asm_clobbers(struct token *token, struct statement *stmt)
 570 {
 571         struct expression *expr;
 572
 573         do {
 574                 token = primary_expression(token->next, &expr);
 575         } while (match_op(token, ','));
 576         return token;
 577 }
 578
 579 /* Make a statement out of an expression */
 580 static struct statement *make_statement(struct expression *expr)
 581 {
 582         struct statement *stmt;
 583
 584         if (!expr)
 585                 return NULL;
 586         stmt = alloc_statement(expr->pos, STMT_EXPRESSION);
 587         stmt->expression = expr;
 588         return stmt;
 589 }
 590
 591 static void start_iterator(struct statement *stmt)
 592 {
 593         struct symbol *cont, *brk;
 594
 595         start_symbol_scope();
 596         cont = alloc_symbol(stmt->pos, SYM_NODE);
 597         cont->ident = &continue_ident;
 598         bind_symbol(cont, &continue_ident, NS_ITERATOR);
 599         brk = alloc_symbol(stmt->pos, SYM_NODE);
 600         brk->ident = &break_ident;
 601         bind_symbol(brk, &break_ident, NS_ITERATOR);
 602
 603         stmt->type = STMT_ITERATOR;
 604         stmt->iterator_break = brk;
 605         stmt->iterator_continue = cont;
 606 }
 607
 608 static void end_iterator(void)
 609 {
 610         start_symbol_scope();
 611 }
 612
 613 static void start_switch(struct statement *stmt)
 614 {
 615         struct symbol *brk;
 616
 617         start_symbol_scope();
 618         brk = alloc_symbol(stmt->pos, SYM_NODE);
 619         brk->ident = &break_ident;
 620         bind_symbol(brk, &break_ident, NS_ITERATOR);
 621
 622         stmt->type = STMT_SWITCH;
 623         stmt->switch_break = brk;
 624 }
 625
 626 static void end_switch(void)
 627 {
 628         start_symbol_scope();
 629 }
 630
 631 struct token *statement(struct token *token, struct statement **tree)
 632 {
 633         struct statement *stmt = alloc_statement(token->pos, STMT_NONE);
 634
 635         *tree = stmt;
 636         if (token_type(token) == TOKEN_IDENT) {
 637                 if (token->ident == &if_ident) {
 638                         stmt->type = STMT_IF;
 639                         token = parens_expression(token->next, &stmt->if_conditional, "after if");
 640                         token = statement(token, &stmt->if_true);
 641                         if (token_type(token) != TOKEN_IDENT)
 642                                 return token;
 643                         if (token->ident != &else_ident)
 644                                 return token;
 645                         return statement(token->next, &stmt->if_false);
 646                 }
 647                 if (token->ident == &return_ident) {
 648                         stmt->type = STMT_RETURN;
 649                         return expression_statement(token->next, &stmt->expression);
 650                 }
 651                 if (token->ident == &break_ident || token->ident == &continue_ident) {
 652                         struct symbol *target = lookup_symbol(token->ident, NS_ITERATOR);
 653                         stmt->type = STMT_GOTO;
 654                         stmt->goto_label = target;
 655                         if (!target)
 656                                 warn(stmt->pos, "break/continue not in iterator scope");
 657                         return expect(token->next, ';', "at end of statement");
 658                 }
 659                 if (token->ident == &default_ident) {
 660                         token = token->next;
 661                         goto default_statement;
 662                 }
 663                 if (token->ident == &case_ident) {
 664                         token = parse_expression(token->next, &stmt->case_expression);
 665                         if (match_op(token, SPECIAL_ELLIPSIS))
 666                                 token = parse_expression(token->next, &stmt->case_to);
 667 default_statement:
 668                         stmt->type = STMT_CASE;
 669                         token = expect(token, ':', "after default/case");
 670                         return statement(token, &stmt->case_statement);
 671                 }
 672                 if (token->ident == &switch_ident) {
 673                         stmt->type = STMT_SWITCH;
 674                         start_switch(stmt);
 675                         token = parens_expression(token->next, &stmt->switch_expression, "after 'switch'");
 676                         token = statement(token, &stmt->switch_statement);
 677                         end_switch();
 678                         return token;
 679                 }
 680                 if (token->ident == &for_ident) {
 681                         struct expression *e1, *e2, *e3;
 682                         struct statement *iterator;
 683
 684                         start_iterator(stmt);
 685                         token = expect(token->next, '(', "after 'for'");
 686                         token = parse_expression(token, &e1);
 687                         token = expect(token, ';', "in 'for'");
 688                         token = parse_expression(token, &e2);
 689                         token = expect(token, ';', "in 'for'");
 690                         token = parse_expression(token, &e3);
 691                         token = expect(token, ')', "in 'for'");
 692                         token = statement(token, &iterator);
 693
 694                         stmt->iterator_pre_statement = make_statement(e1);
 695                         stmt->iterator_pre_condition = e2;
 696                         stmt->iterator_post_statement = make_statement(e3);
 697                         stmt->iterator_post_condition = e2;
 698                         stmt->iterator_statement = iterator;
 699                         end_iterator();
 700
 701                         return token;
 702                 }
 703                 if (token->ident == &while_ident) {
 704                         struct expression *expr;
 705                         struct statement *iterator;
 706
 707                         start_iterator(stmt);
 708                         token = parens_expression(token->next, &expr, "after 'while'");
 709                         token = statement(token, &iterator);
 710
 711                         stmt->iterator_pre_condition = expr;
 712                         stmt->iterator_post_condition = expr;
 713                         stmt->iterator_statement = iterator;
 714                         end_iterator();
 715
 716                         return token;
 717                 }
 718                 if (token->ident == &do_ident) {
 719                         struct expression *expr;
 720                         struct statement *iterator;
 721
 722                         start_iterator(stmt);
 723                         token = statement(token->next, &iterator);
 724                         if (token_type(token) == TOKEN_IDENT && token->ident == &while_ident)
 725                                 token = token->next;
 726                         else
 727                                 warn(token->pos, "expected 'while' after 'do'");
 728                         token = parens_expression(token, &expr, "after 'do-while'");
 729
 730                         stmt->iterator_post_condition = expr;
 731                         stmt->iterator_statement = iterator;
 732                         end_iterator();
 733
 734                         return expect(token, ';', "after statement");
 735                 }
 736                 if (token->ident == &goto_ident) {
 737                         stmt->type = STMT_GOTO;
 738                         token = token->next;
 739                         if (token_type(token) == TOKEN_IDENT) {
 740                                 stmt->goto_label = label_symbol(token);
 741                                 token = token->next;
 742                         } else
 743                                 warn(token->pos, "invalid label");
 744                         return expect(token, ';', "at end of statement");
 745                 }
 746                 if (token->ident == &asm_ident || token->ident == &__asm___ident || token->ident == &__asm_ident) {
 747                         struct expression *expr;
 748                         stmt->type = STMT_ASM;
 749                         token = token->next;
 750                         if (token_type(token) == TOKEN_IDENT) {
 751                                 if (token->ident == &__volatile___ident || token->ident == &volatile_ident)
 752                                         token = token->next;
 753                         }
 754                         token = expect(token, '(', "after asm");
 755                         token = parse_expression(token->next, &expr);
 756                         if (match_op(token, ':'))
 757                                 token = parse_asm_operands(token, stmt);
 758                         if (match_op(token, ':'))
 759                                 token = parse_asm_operands(token, stmt);
 760                         if (match_op(token, ':'))
 761                                 token = parse_asm_clobbers(token, stmt);
 762                         token = expect(token, ')', "after asm");
 763                         return expect(token, ';', "at end of asm-statement");
 764                 }
 765                 if (match_op(token->next, ':')) {
 766                         stmt->type = STMT_LABEL;
 767                         stmt->label_identifier = label_symbol(token);
 768                         return statement(token->next->next, &stmt->label_statement);
 769                 }
 770         }
 771
 772         if (match_op(token, '{')) {
 773                 stmt->type = STMT_COMPOUND;
 774                 start_symbol_scope();
 775                 token = compound_statement(token->next, stmt);
 776                 end_symbol_scope();
 777
 778                 return expect(token, '}', "at end of compound statement");
 779         }
 780
 781         stmt->type = STMT_EXPRESSION;
 782         return expression_statement(token, &stmt->expression);
 783 }
 784
 785 struct token * statement_list(struct token *token, struct statement_list **list)
 786 {
 787         for (;;) {
 788                 struct statement * stmt;
 789                 if (eof_token(token))
 790                         break;
 791                 if (match_op(token, '}'))
 792                         break;
 793                 token = statement(token, &stmt);
 794                 add_statement(list, stmt);
 795         }
 796         return token;
 797 }
 798
 799 static struct token *parameter_type_list(struct token *token, struct symbol *fn)
 800 {
 801         struct symbol_list **list = &fn->arguments;
 802         for (;;) {
 803                 struct symbol *sym = alloc_symbol(token->pos, SYM_NODE);
 804
 805                 if (match_op(token, SPECIAL_ELLIPSIS)) {
 806                         fn->variadic = 1;
 807                         token = token->next;
 808                         break;
 809                 }
 810
 811                 token = parameter_declaration(token, &sym);
 812                 /* Special case: (void) */
 813                 if (!*list && !sym->ident && sym->ctype.base_type == &void_ctype)
 814                         break;
 815                 add_symbol(list, sym);
 816                 if (!match_op(token, ','))
 817                         break;
 818                 token = token->next;
 819
 820         }
 821         return token;
 822 }
 823
 824 static struct token *external_declaration(struct token *token, struct symbol_list **list);
 825
 826 struct token *compound_statement(struct token *token, struct statement *stmt)
 827 {
 828         while (!eof_token(token)) {
 829                 if (!lookup_type(token))
 830                         break;
 831                 token = external_declaration(token, &stmt->syms);
 832         }
 833         token = statement_list(token, &stmt->stmts);
 834         return token;
 835 }
 836
 837 static struct expression *identifier_expression(struct token *token)
 838 {
 839         struct expression *expr = alloc_expression(token->pos, EXPR_IDENTIFIER);
 840         expr->expr_ident = token->ident;
 841         return expr;
 842 }
 843
 844 static struct expression *index_expression(struct expression *from, struct expression *to)
 845 {
 846         int idx_from, idx_to;
 847         struct expression *expr = alloc_expression(from->pos, EXPR_INDEX);
 848
 849         idx_from = get_expression_value(from);
 850         idx_to = idx_from;
 851         if (to) {
 852                 idx_to = get_expression_value(to);
 853                 if (idx_to < idx_from)
 854                         warn(from->pos, "nonsense array initializer index range");
 855         }
 856         expr->idx_from = idx_from;
 857         expr->idx_to = idx_to;
 858         return expr;
 859 }
 860
 861 static struct token *initializer_list(struct expression_list **list, struct token *token)
 862 {
 863         for (;;) {
 864                 struct token *next = token->next;
 865                 struct expression *expr;
 866
 867                 if (match_op(token, '.') && (token_type(next) == TOKEN_IDENT) && match_op(next->next, '=')) {
 868                         add_expression(list, identifier_expression(next));
 869                         token = next->next->next;
 870                 } else if ((token_type(token) == TOKEN_IDENT) && match_op(next, ':')) {
 871                         add_expression(list, identifier_expression(token));
 872                         token = next->next;
 873                 } else if (match_op(token, '[')) {
 874                         struct expression *from = NULL, *to = NULL;
 875                         token = constant_expression(token->next, &from);
 876                         if (match_op(token, SPECIAL_ELLIPSIS))
 877                                 token = constant_expression(token->next, &to);
 878                         add_expression(list, index_expression(from, to));
 879                         token = expect(token, ']', "at end of initializer index");
 880                 }
 881
 882                 expr = NULL;
 883                 token = initializer(&expr, token);
 884                 if (!expr)
 885                         break;
 886                 add_expression(list, expr);
 887                 if (!match_op(token, ','))
 888                         break;
 889                 token = token->next;
 890         }
 891         return token;
 892 }
 893
 894 struct token *initializer(struct expression **tree, struct token *token)
 895 {
 896         if (match_op(token, '{')) {
 897                 struct expression *expr = alloc_expression(token->pos, EXPR_INITIALIZER);
 898                 *tree = expr;
 899                 token = initializer_list(&expr->expr_list, token->next);
 900                 return expect(token, '}', "at end of initializer");
 901         }
 902         return assignment_expression(token, tree);
 903 }
 904
 905 static void declare_argument(struct symbol *sym, void *data, int flags)
 906 {
 907         struct symbol *decl = data;
 908
 909         if (!sym->ident) {
 910                 warn(decl->pos, "no identifier for function argument");
 911                 return;
 912         }
 913         bind_symbol(sym, sym->ident, NS_SYMBOL);
 914 }
 915
 916 static struct token *external_declaration(struct token *token, struct symbol_list **list)
 917 {
 918         struct ident *ident = NULL;
 919         struct symbol *decl;
 920         struct ctype ctype = { 0, };
 921         struct symbol *base_type;
 922         int is_typedef;
 923
 924         /* Parse declaration-specifiers, if any */
 925         token = declaration_specifiers(token, &ctype, 0);
 926         decl = alloc_symbol(token->pos, SYM_NODE);
 927         decl->ctype = ctype;
 928         token = pointer(token, &decl->ctype);
 929         token = declarator(token, &decl, &ident);
 930
 931         /* Just a type declaration? */
 932         if (!ident)
 933                 return expect(token, ';', "end of type declaration");
 934
 935         decl->ident = ident;
 936
 937         /* type define declaration? */
 938         is_typedef = (ctype.modifiers & MOD_TYPEDEF) != 0;
 939         bind_symbol(decl, ident, is_typedef ? NS_TYPEDEF: NS_SYMBOL);
 940
 941         base_type = decl->ctype.base_type;
 942         if (!is_typedef && base_type && base_type->type == SYM_FN) {
 943                 if (match_op(token, '{')) {
 944                         if (decl->ctype.modifiers & MOD_EXTERN) {
 945                                 if (!(decl->ctype.modifiers & MOD_INLINE))
 946                                         warn(decl->pos, "function with external linkage has definition");
 947                                 decl->ctype.modifiers &= ~MOD_EXTERN;
 948                         }
 949                         base_type->stmt = alloc_statement(token->pos, STMT_COMPOUND);
 950                         start_function_scope();
 951                         symbol_iterate(base_type->arguments, declare_argument, decl);
 952                         token = compound_statement(token->next, base_type->stmt);
 953                         end_function_scope();
 954                         if (!(decl->ctype.modifiers & MOD_INLINE))
 955                                 add_symbol(list, decl);
 956                         return expect(token, '}', "at end of function");
 957                 }
 958                 decl->ctype.modifiers |= MOD_EXTERN;
 959         }
 960
 961         for (;;) {
 962                 if (!is_typedef && match_op(token, '=')) {
 963                         if (decl->ctype.modifiers & MOD_EXTERN) {
 964                                 warn(decl->pos, "symbol with external linkage has initializer");
 965                                 decl->ctype.modifiers &= ~MOD_EXTERN;
 966                         }
 967                         token = initializer(&decl->initializer, token->next);
 968                 }
 969                 if (!is_typedef && !(decl->ctype.modifiers & (MOD_EXTERN | MOD_INLINE)))
 970                         add_symbol(list, decl);
 971
 972                 if (!match_op(token, ','))
 973                         break;
 974
 975                 ident = NULL;
 976                 decl = alloc_symbol(token->pos, SYM_NODE);
 977                 decl->ctype = ctype;
 978                 token = pointer(token, &decl->ctype);
 979                 token = declarator(token->next, &decl, &ident);
 980                 if (!ident) {
 981                         warn(token->pos, "expected identifier name in type definition");
 982                         return token;
 983                 }
 984
 985                 bind_symbol(decl, ident, is_typedef ? NS_TYPEDEF: NS_SYMBOL);
 986         }
 987         return expect(token, ';', "at end of declaration");
 988 }
 989
 990 void translation_unit(struct token *token, struct symbol_list **list)
 991 {
 992         while (!eof_token(token))
 993                 token = external_declaration(token, list);
 994         // They aren't needed any more
 995         clear_token_alloc();
 996 }