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 Linus Torvalds, 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 struct token *attribute_specifier(struct token *token, struct ctype *ctype)
 162 {
 163         int parens = 0;
 164
 165         token = expect(token, '(', "after attribute");
 166         token = expect(token, '(', "after attribute");
 167
 168         for (;;) {
 169                 if (eof_token(token))
 170                         break;
 171                 if (match_op(token, ';'))
 172                         break;
 173                 if (match_op(token, ')')) {
 174                         if (!parens)
 175                                 break;
 176                         parens--;
 177                 }
 178                 if (match_op(token, '('))
 179                         parens++;
 180                 token = token->next;
 181         }
 182
 183         token = expect(token, ')', "after attribute");
 184         token = expect(token, ')', "after attribute");
 185         return token;
 186 }
 187
 188 #define MOD_SPECIALBITS (MOD_STRUCTOF | MOD_UNIONOF | MOD_ENUMOF | MOD_ATTRIBUTE | MOD_TYPEOF)
 189
 190 static struct token *type_qualifiers(struct token *next, struct ctype *ctype)
 191 {
 192         struct token *token;
 193         while ( (token = next) != NULL ) {
 194                 struct symbol *s, *base_type;
 195                 unsigned long mod;
 196
 197                 next = token->next;
 198                 if (token_type(token) != TOKEN_IDENT)
 199                         break;
 200                 s = lookup_symbol(token->ident, NS_TYPEDEF);
 201                 if (!s)
 202                         break;
 203                 mod = s->ctype.modifiers;
 204                 base_type = s->ctype.base_type;
 205                 if (base_type)
 206                         break;
 207                 if (mod & ~(MOD_CONST | MOD_VOLATILE))
 208                         break;
 209                 ctype->modifiers |= mod;
 210         }
 211         return token;
 212 }
 213
 214 #define MOD_SPECIFIER (MOD_CHAR | MOD_SHORT | MOD_LONG | MOD_LONGLONG | MOD_SIGNED | MOD_UNSIGNED)
 215
 216 struct symbol * ctype_integer(unsigned int spec)
 217 {
 218         static struct symbol *const integer_ctypes[][2] = {
 219                 { &llong_ctype, &ullong_ctype },
 220                 { &long_ctype,  &ulong_ctype  },
 221                 { &short_ctype, &ushort_ctype },
 222                 { &char_ctype,  &uchar_ctype  },
 223                 { &int_ctype,   &uint_ctype   },
 224         };
 225         struct symbol *const (*ctype)[2];
 226
 227         ctype = integer_ctypes;
 228         if (!(spec & MOD_LONGLONG)) {
 229                 ctype++;
 230                 if (!(spec & MOD_LONG)) {
 231                         ctype++;
 232                         if (!(spec & MOD_SHORT)) {
 233                                 ctype++;
 234                                 if (!(spec & MOD_CHAR))
 235                                         ctype++;
 236                         }
 237                 }
 238         }
 239         return ctype[0][(spec & MOD_UNSIGNED) != 0];
 240 }
 241
 242 struct symbol * ctype_fp(unsigned int spec)
 243 {
 244         if (spec & MOD_LONGLONG)
 245                 return &ldouble_ctype;
 246         if (spec & MOD_LONG)
 247                 return &double_ctype;
 248         return &float_ctype;
 249 }
 250
 251 static struct token *declaration_specifiers(struct token *next, struct ctype *ctype)
 252 {
 253         struct token *token;
 254
 255         while ( (token = next) != NULL ) {
 256                 struct ctype thistype;
 257                 struct ident *ident;
 258                 struct symbol *s, *type;
 259                 unsigned long mod;
 260
 261                 next = token->next;
 262                 if (token_type(token) != TOKEN_IDENT)
 263                         break;
 264                 ident = token->ident;
 265
 266                 s = lookup_symbol(ident, NS_TYPEDEF);
 267                 if (!s)
 268                         break;
 269                 thistype = s->ctype;
 270                 mod = thistype.modifiers;
 271                 if (mod & MOD_SPECIALBITS) {
 272                         if (mod & MOD_STRUCTOF)
 273                                 next = struct_or_union_specifier(SYM_STRUCT, next, &thistype);
 274                         else if (mod & MOD_UNIONOF)
 275                                 next = struct_or_union_specifier(SYM_UNION, next, &thistype);
 276                         else if (mod & MOD_ENUMOF)
 277                                 next = enum_specifier(next, &thistype);
 278                         else if (mod & MOD_ATTRIBUTE)
 279                                 next = attribute_specifier(next, &thistype);
 280                         else if (mod & MOD_TYPEOF)
 281                                 next = typeof_specifier(next, &thistype);
 282                         mod = thistype.modifiers;
 283                 }
 284
 285                 type = thistype.base_type;
 286                 if (type) {
 287                         if (type != ctype->base_type) {
 288                                 if (ctype->base_type) {
 289                                         warn(token->pos, "Strange mix of types");
 290                                         continue;
 291                                 }
 292                                 ctype->base_type = type;
 293                         }
 294                 }
 295                 if (mod) {
 296                         unsigned long old = ctype->modifiers;
 297                         unsigned long extra = 0, dup;
 298
 299                         if (mod & old & MOD_LONG) {
 300                                 extra = MOD_LONGLONG | MOD_LONG;
 301                                 mod &= ~MOD_LONG;
 302                                 old &= ~MOD_LONG;
 303                         }
 304                         dup = (mod & old) | (extra & old) | (extra & mod);
 305                         if (dup)
 306                                 warn(token->pos, "Just how %s do you want this type to be?",
 307                                         modifier_string(dup));
 308                         ctype->modifiers = old | mod | extra;
 309                 }
 310         }
 311
 312         /* Turn the "virtual types" into real types with real sizes etc */
 313         if (!ctype->base_type && (ctype->modifiers & MOD_SPECIFIER))
 314                 ctype->base_type = &int_type;
 315
 316         if (ctype->base_type == &int_type) {
 317                 ctype->base_type = ctype_integer(ctype->modifiers & MOD_SPECIFIER);
 318                 ctype->modifiers &= ~MOD_SPECIFIER;
 319                 return token;
 320         }
 321         if (ctype->base_type == &fp_type) {
 322                 ctype->base_type = ctype_fp(ctype->modifiers & MOD_SPECIFIER);
 323                 ctype->modifiers &= ~MOD_SPECIFIER;
 324                 return token;
 325         }
 326         return token;
 327 }
 328
 329 static struct token *abstract_array_declarator(struct token *token, struct symbol *sym)
 330 {
 331         struct expression *expr = NULL;
 332
 333         token = parse_expression(token, &expr);
 334         if (expr)
 335                 sym->array_size = get_expression_value(expr);
 336         else
 337                 sym->array_size = -1;
 338         return token;
 339 }
 340
 341 static struct token *parameter_type_list(struct token *, struct symbol *);
 342 static struct token *declarator(struct token *token, struct symbol **tree, struct ident **p);
 343
 344 static struct token *direct_declarator(struct token *token, struct symbol **tree, struct ident **p)
 345 {
 346         struct ctype *ctype = &(*tree)->ctype;
 347
 348         if (p && token_type(token) == TOKEN_IDENT) {
 349                 *p = token->ident;
 350                 token = token->next;
 351         }
 352
 353         for (;;) {
 354                 if (match_ident(token, &__attribute___ident) || match_ident(token, &__attribute_ident)) {
 355                         struct ctype ctype = { 0, };
 356                         token = attribute_specifier(token->next, &ctype);
 357                         continue;
 358                 }
 359                 if (token_type(token) != TOKEN_SPECIAL)
 360                         return token;
 361
 362                 /*
 363                  * This can be either a parameter list or a grouping.
 364                  * For the direct (non-abstract) case, we know if must be
 365                  * a paramter list if we already saw the identifier.
 366                  * For the abstract case, we know if must be a parameter
 367                  * list if it is empty or starts with a type.
 368                  */
 369                 if (token->special == '(') {
 370                         struct symbol *sym;
 371                         struct token *next = token->next;
 372                         int fn = (p && *p) || match_op(next, ')') || lookup_type(next);
 373
 374                         if (!fn) {
 375                                 struct symbol *base_type = ctype->base_type;
 376                                 token = declarator(next, tree, p);
 377                                 token = expect(token, ')', "in nested declarator");
 378                                 while (ctype->base_type != base_type)
 379                                         ctype = &ctype->base_type->ctype;
 380                                 p = NULL;
 381                                 continue;
 382                         }
 383
 384                         sym = indirect(token->pos, ctype, SYM_FN);
 385                         token = parameter_type_list(next, sym);
 386                         token = expect(token, ')', "in function declarator");
 387                         continue;
 388                 }
 389                 if (token->special == '[') {
 390                         struct symbol *array = indirect(token->pos, ctype, SYM_ARRAY);
 391                         token = abstract_array_declarator(token->next, array);
 392                         token = expect(token, ']', "in abstract_array_declarator");
 393                         continue;
 394                 }
 395                 if (token->special == ':') {
 396                         struct symbol *bitfield;
 397                         struct expression *expr;
 398                         bitfield = indirect(token->pos, ctype, SYM_BITFIELD);
 399                         token = conditional_expression(token->next, &expr);
 400                         bitfield->fieldwidth = get_expression_value(expr);
 401                         continue;
 402                 }
 403                 break;
 404         }
 405         if (p) {
 406                 (*tree)->ident = *p;
 407         }
 408         return token;
 409 }
 410
 411 static struct token *pointer(struct token *token, struct ctype *ctype)
 412 {
 413         unsigned long modifiers;
 414         struct symbol *base_type;
 415
 416         modifiers = ctype->modifiers & ~(MOD_TYPEDEF | MOD_ATTRIBUTE);
 417         base_type = ctype->base_type;
 418         ctype->modifiers = modifiers;
 419
 420         while (match_op(token,'*')) {
 421                 struct symbol *ptr = alloc_symbol(token->pos, SYM_PTR);
 422                 ptr->ctype.modifiers = modifiers & ~MOD_STORAGE;
 423                 ptr->ctype.base_type = base_type;
 424
 425                 base_type = ptr;
 426                 ctype->modifiers = modifiers & MOD_STORAGE;
 427                 ctype->base_type = base_type;
 428
 429                 token = type_qualifiers(token->next, ctype);
 430         }
 431         return token;
 432 }
 433
 434 static struct token *declarator(struct token *token, struct symbol **tree, struct ident **p)
 435 {
 436         token = pointer(token, &(*tree)->ctype);
 437         return direct_declarator(token, tree, p);
 438 }
 439
 440 static struct token *struct_declaration_list(struct token *token, struct symbol_list **list)
 441 {
 442         while (!match_op(token, '}')) {
 443                 struct ctype ctype = {0, };
 444
 445                 token = declaration_specifiers(token, &ctype);
 446                 for (;;) {
 447                         struct ident *ident = NULL;
 448                         struct symbol *decl = alloc_symbol(token->pos, SYM_NODE);
 449                         decl->ctype = ctype;
 450                         token = pointer(token, &decl->ctype);
 451                         token = direct_declarator(token, &decl, &ident);
 452                         if (match_op(token, ':')) {
 453                                 struct expression *expr;
 454                                 token = parse_expression(token->next, &expr);
 455                         }
 456                         add_symbol(list, decl);
 457                         if (!match_op(token, ','))
 458                                 break;
 459                         token = token->next;
 460                 }
 461                 if (!match_op(token, ';'))
 462                         break;
 463                 token = token->next;
 464         }
 465         return token;
 466 }
 467
 468 static struct token *parameter_declaration(struct token *token, struct symbol **tree)
 469 {
 470         struct ident *ident = NULL;
 471         struct symbol *sym;
 472         struct ctype ctype = { 0, };
 473
 474         token = declaration_specifiers(token, &ctype);
 475         sym = alloc_symbol(token->pos, SYM_NODE);
 476         sym->ctype = ctype;
 477         *tree = sym;
 478         token = pointer(token, &sym->ctype);
 479         token = direct_declarator(token, tree, &ident);
 480         return token;
 481 }
 482
 483 struct token *typename(struct token *token, struct symbol **p)
 484 {
 485         struct symbol *sym = alloc_symbol(token->pos, SYM_NODE);
 486         *p = sym;
 487         token = declaration_specifiers(token, &sym->ctype);
 488         return declarator(token, &sym, NULL);
 489 }
 490
 491 struct token *expression_statement(struct token *token, struct expression **tree)
 492 {
 493         token = parse_expression(token, tree);
 494         return expect(token, ';', "at end of statement");
 495 }
 496
 497 static struct token *parse_asm_operands(struct token *token, struct statement *stmt)
 498 {
 499         struct expression *expr;
 500
 501         /* Allow empty operands */
 502         if (match_op(token->next, ':') || match_op(token->next, ')'))
 503                 return token->next;
 504         do {
 505                 token = primary_expression(token->next, &expr);
 506                 token = parens_expression(token, &expr, "in asm parameter");
 507         } while (match_op(token, ','));
 508         return token;
 509 }
 510
 511 static struct token *parse_asm_clobbers(struct token *token, struct statement *stmt)
 512 {
 513         struct expression *expr;
 514
 515         do {
 516                 token = primary_expression(token->next, &expr);
 517         } while (match_op(token, ','));
 518         return token;
 519 }
 520
 521 /* Make a statement out of an expression */
 522 static struct statement *make_statement(struct expression *expr)
 523 {
 524         struct statement *stmt;
 525
 526         if (!expr)
 527                 return NULL;
 528         stmt = alloc_statement(expr->pos, STMT_EXPRESSION);
 529         stmt->expression = expr;
 530         return stmt;
 531 }
 532
 533 struct token *statement(struct token *token, struct statement **tree)
 534 {
 535         struct statement *stmt = alloc_statement(token->pos, STMT_NONE);
 536
 537         *tree = stmt;
 538         if (token_type(token) == TOKEN_IDENT) {
 539                 if (token->ident == &if_ident) {
 540                         stmt->type = STMT_IF;
 541                         token = parens_expression(token->next, &stmt->if_conditional, "after if");
 542                         token = statement(token, &stmt->if_true);
 543                         if (token_type(token) != TOKEN_IDENT)
 544                                 return token;
 545                         if (token->ident != &else_ident)
 546                                 return token;
 547                         return statement(token->next, &stmt->if_false);
 548                 }
 549                 if (token->ident == &return_ident) {
 550                         stmt->type = STMT_RETURN;
 551                         return expression_statement(token->next, &stmt->expression);
 552                 }
 553                 if (token->ident == &break_ident) {
 554                         stmt->type = STMT_BREAK;
 555                         return expect(token->next, ';', "at end of statement");
 556                 }
 557                 if (token->ident == &continue_ident) {
 558                         stmt->type = STMT_CONTINUE;
 559                         return expect(token->next, ';', "at end of statement");
 560                 }
 561                 if (token->ident == &default_ident) {
 562                         token = token->next;
 563                         goto default_statement;
 564                 }
 565                 if (token->ident == &case_ident) {
 566                         token = parse_expression(token->next, &stmt->case_expression);
 567                         if (match_op(token, SPECIAL_ELLIPSIS))
 568                                 token = parse_expression(token->next, &stmt->case_to);
 569 default_statement:
 570                         stmt->type = STMT_CASE;
 571                         token = expect(token, ':', "after default/case");
 572                         return statement(token, &stmt->case_statement);
 573                 }
 574                 if (token->ident == &switch_ident) {
 575                         stmt->type = STMT_SWITCH;
 576                         token = parens_expression(token->next, &stmt->switch_expression, "after 'switch'");
 577                         return statement(token, &stmt->switch_statement);
 578                 }
 579                 if (token->ident == &for_ident) {
 580                         struct expression *e1, *e2, *e3;
 581                         struct statement *iterator;
 582
 583                         token = expect(token->next, '(', "after 'for'");
 584                         token = parse_expression(token, &e1);
 585                         token = expect(token, ';', "in 'for'");
 586                         token = parse_expression(token, &e2);
 587                         token = expect(token, ';', "in 'for'");
 588                         token = parse_expression(token, &e3);
 589                         token = expect(token, ')', "in 'for'");
 590                         token = statement(token, &iterator);
 591
 592                         stmt->type = STMT_ITERATOR;
 593                         stmt->iterator_pre_statement = make_statement(e1);
 594                         stmt->iterator_pre_condition = e2;
 595                         stmt->iterator_post_statement = make_statement(e3);
 596                         stmt->iterator_post_condition = e2;
 597                         stmt->iterator_statement = iterator;
 598
 599                         return token;
 600                 }
 601                 if (token->ident == &while_ident) {
 602                         struct expression *expr;
 603                         struct statement *iterator;
 604
 605                         token = parens_expression(token->next, &expr, "after 'while'");
 606                         token = statement(token, &iterator);
 607
 608                         stmt->type = STMT_ITERATOR;
 609                         stmt->iterator_pre_condition = expr;
 610                         stmt->iterator_post_condition = expr;
 611                         stmt->iterator_statement = iterator;
 612
 613                         return token;
 614                 }
 615                 if (token->ident == &do_ident) {
 616                         struct expression *expr;
 617                         struct statement *iterator;
 618
 619                         token = statement(token->next, &iterator);
 620                         if (token_type(token) == TOKEN_IDENT && token->ident == &while_ident)
 621                                 token = token->next;
 622                         else
 623                                 warn(token->pos, "expected 'while' after 'do'");
 624                         token = parens_expression(token, &expr, "after 'do-while'");
 625
 626                         stmt->type = STMT_ITERATOR;
 627                         stmt->iterator_post_condition = expr;
 628                         stmt->iterator_statement = iterator;
 629
 630                         return expect(token, ';', "after statement");
 631                 }
 632                 if (token->ident == &goto_ident) {
 633                         stmt->type = STMT_GOTO;
 634                         token = token->next;
 635                         if (token_type(token) == TOKEN_IDENT) {
 636                                 stmt->goto_label = label_symbol(token);
 637                                 token = token->next;
 638                         } else
 639                                 warn(token->pos, "invalid label");
 640                         return expect(token, ';', "at end of statement");
 641                 }
 642                 if (token->ident == &asm_ident || token->ident == &__asm___ident || token->ident == &__asm_ident) {
 643                         struct expression *expr;
 644                         stmt->type = STMT_ASM;
 645                         token = token->next;
 646                         if (token_type(token) == TOKEN_IDENT) {
 647                                 if (token->ident == &__volatile___ident || token->ident == &volatile_ident)
 648                                         token = token->next;
 649                         }
 650                         token = expect(token, '(', "after asm");
 651                         token = parse_expression(token->next, &expr);
 652                         if (match_op(token, ':'))
 653                                 token = parse_asm_operands(token, stmt);
 654                         if (match_op(token, ':'))
 655                                 token = parse_asm_operands(token, stmt);
 656                         if (match_op(token, ':'))
 657                                 token = parse_asm_clobbers(token, stmt);
 658                         token = expect(token, ')', "after asm");
 659                         return expect(token, ';', "at end of asm-statement");
 660                 }
 661                 if (match_op(token->next, ':')) {
 662                         stmt->type = STMT_LABEL;
 663                         stmt->label_identifier = label_symbol(token);
 664                         return statement(token->next->next, &stmt->label_statement);
 665                 }
 666         }
 667
 668         if (match_op(token, '{')) {
 669                 stmt->type = STMT_COMPOUND;
 670                 start_symbol_scope();
 671                 token = compound_statement(token->next, stmt);
 672                 end_symbol_scope();
 673
 674                 return expect(token, '}', "at end of compound statement");
 675         }
 676
 677         stmt->type = STMT_EXPRESSION;
 678         return expression_statement(token, &stmt->expression);
 679 }
 680
 681 struct token * statement_list(struct token *token, struct statement_list **list)
 682 {
 683         for (;;) {
 684                 struct statement * stmt;
 685                 if (eof_token(token))
 686                         break;
 687                 if (match_op(token, '}'))
 688                         break;
 689                 token = statement(token, &stmt);
 690                 add_statement(list, stmt);
 691         }
 692         return token;
 693 }
 694
 695 static struct token *parameter_type_list(struct token *token, struct symbol *fn)
 696 {
 697         struct symbol_list **list = &fn->arguments;
 698         for (;;) {
 699                 struct symbol *sym = alloc_symbol(token->pos, SYM_NODE);
 700
 701                 if (match_op(token, SPECIAL_ELLIPSIS)) {
 702                         fn->variadic = 1;
 703                         token = token->next;
 704                         break;
 705                 }
 706
 707                 token = parameter_declaration(token, &sym);
 708                 /* Special case: (void) */
 709                 if (!*list && !sym->ident && sym->ctype.base_type == &void_ctype)
 710                         break;
 711                 add_symbol(list, sym);
 712                 if (!match_op(token, ','))
 713                         break;
 714                 token = token->next;
 715
 716         }
 717         return token;
 718 }
 719
 720 static struct token *external_declaration(struct token *token, struct symbol_list **list);
 721
 722 struct token *compound_statement(struct token *token, struct statement *stmt)
 723 {
 724         while (!eof_token(token)) {
 725                 if (!lookup_type(token))
 726                         break;
 727                 token = external_declaration(token, &stmt->syms);
 728         }
 729         token = statement_list(token, &stmt->stmts);
 730         return token;
 731 }
 732
 733 static struct expression *identifier_expression(struct token *token)
 734 {
 735         struct expression *expr = alloc_expression(token->pos, EXPR_IDENTIFIER);
 736         expr->expr_ident = token->ident;
 737         return expr;
 738 }
 739
 740 static struct expression *index_expression(struct expression *from, struct expression *to)
 741 {
 742         int idx_from, idx_to;
 743         struct expression *expr = alloc_expression(from->pos, EXPR_INDEX);
 744
 745         idx_from = get_expression_value(from);
 746         idx_to = idx_from;
 747         if (to) {
 748                 idx_to = get_expression_value(to);
 749                 if (idx_to < idx_from)
 750                         warn(from->pos, "nonsense array initializer index range");
 751         }
 752         expr->idx_from = idx_from;
 753         expr->idx_to = idx_to;
 754         return expr;
 755 }
 756
 757 static struct token *initializer_list(struct expression_list **list, struct token *token)
 758 {
 759         for (;;) {
 760                 struct token *next = token->next;
 761                 struct expression *expr;
 762
 763                 if (match_op(token, '.') && (token_type(next) == TOKEN_IDENT) && match_op(next->next, '=')) {
 764                         add_expression(list, identifier_expression(next));
 765                         token = next->next->next;
 766                 } else if ((token_type(token) == TOKEN_IDENT) && match_op(next, ':')) {
 767                         add_expression(list, identifier_expression(token));
 768                         token = next->next;
 769                 } else if (match_op(token, '[')) {
 770                         struct expression *from = NULL, *to = NULL;
 771                         token = constant_expression(token->next, &from);
 772                         if (match_op(token, SPECIAL_ELLIPSIS))
 773                                 token = constant_expression(token->next, &to);
 774                         add_expression(list, index_expression(from, to));
 775                         token = expect(token, ']', "at end of initializer index");
 776                 }
 777
 778                 expr = NULL;
 779                 token = initializer(&expr, token);
 780                 if (!expr)
 781                         break;
 782                 add_expression(list, expr);
 783                 if (!match_op(token, ','))
 784                         break;
 785                 token = token->next;
 786         }
 787         return token;
 788 }
 789
 790 struct token *initializer(struct expression **tree, struct token *token)
 791 {
 792         if (match_op(token, '{')) {
 793                 struct expression *expr = alloc_expression(token->pos, EXPR_INITIALIZER);
 794                 *tree = expr;
 795                 token = initializer_list(&expr->expr_list, token->next);
 796                 return expect(token, '}', "at end of initializer");
 797         }
 798         return assignment_expression(token, tree);
 799 }
 800
 801 static void declare_argument(struct symbol *sym, void *data, int flags)
 802 {
 803         struct symbol *decl = data;
 804
 805         if (!sym->ident) {
 806                 warn(decl->pos, "no identifier for function argument");
 807                 return;
 808         }
 809         bind_symbol(sym, sym->ident, NS_SYMBOL);
 810 }
 811
 812 static struct token *external_declaration(struct token *token, struct symbol_list **list)
 813 {
 814         struct ident *ident = NULL;
 815         struct symbol *decl;
 816         struct ctype ctype = { 0, };
 817         struct symbol *base_type;
 818
 819         /* Parse declaration-specifiers, if any */
 820         token = declaration_specifiers(token, &ctype);
 821         decl = alloc_symbol(token->pos, SYM_NODE);
 822         decl->ctype = ctype;
 823         token = pointer(token, &decl->ctype);
 824         token = declarator(token, &decl, &ident);
 825
 826         /* Just a type declaration? */
 827         if (!ident)
 828                 return expect(token, ';', "end of type declaration");
 829
 830         decl->ident = ident;
 831
 832         /* type define declaration? */
 833         if (ctype.modifiers & MOD_TYPEDEF) {
 834                 bind_symbol(decl, ident, NS_TYPEDEF);
 835         } else {
 836                 add_symbol(list, decl);
 837                 bind_symbol(decl, ident, NS_SYMBOL);
 838         }
 839
 840         base_type = decl->ctype.base_type;
 841         if (base_type && base_type->type == SYM_FN && match_op(token, '{')) {
 842                 base_type->stmt = alloc_statement(token->pos, STMT_COMPOUND);
 843                 start_function_scope();
 844                 symbol_iterate(base_type->arguments, declare_argument, decl);
 845                 token = compound_statement(token->next, base_type->stmt);
 846                 end_function_scope();
 847                 return expect(token, '}', "at end of function");
 848         }
 849
 850         for (;;) {
 851                 if (match_op(token, '='))
 852                         token = initializer(&decl->initializer, token->next);
 853                 if (!match_op(token, ','))
 854                         break;
 855
 856                 ident = NULL;
 857                 decl = alloc_symbol(token->pos, SYM_NODE);
 858                 decl->ctype = ctype;
 859                 token = pointer(token, &decl->ctype);
 860                 token = declarator(token->next, &decl, &ident);
 861                 if (!ident) {
 862                         warn(token->pos, "expected identifier name in type definition");
 863                         return token;
 864                 }
 865
 866                 if (ctype.modifiers & MOD_TYPEDEF) {
 867                         bind_symbol(decl, ident, NS_TYPEDEF);
 868                 } else {
 869                         add_symbol(list, decl);
 870                         bind_symbol(decl, ident, NS_SYMBOL);
 871                 }
 872         }
 873         return expect(token, ';', "at end of declaration");
 874 }
 875
 876 void translation_unit(struct token *token, struct symbol_list **list)
 877 {
 878         while (!eof_token(token))
 879                 token = external_declaration(token, list);
 880         // They aren't needed any more
 881         clear_token_alloc();
 882 }