parse.c

   1 #include "parse.h"
   2 #include "cc.h"
   3 #include "scanner.h"
   4 #include "const.h"
   5 #include "errors.h"
   6 #include "stdlib.h"
   7 #include "stdio.h"
   8 #include "stdarg.h"
   9
  10 // make-it-easier macros
  11 #define LEX (&cc->lex) // struct lexer *
  12 #define TOK (cc->lex.tok.tok) // tok_t
  13
  14 static void cc_accept(struct cc *cc, const char *description, ...);
  15 static void cc_sync(struct cc *cc, ...);
  16 static int get_precedence(tok_t tok);
  17 static bool cc_isglobal(struct cc *cc);
  18 static struct stree *cc_get_current_func(struct cc *cc);
  19 static struct stree *cc_parse_factor(struct cc *cc);
  20 static struct stree *cc_parse_expr(struct cc *cc);
  21 static struct stree *cc_parse_expr_nocomma(struct cc *cc);
  22 static bool cc_parse_struct(struct cc *cc, struct btype *struct_type_info);
  23 static bool cc_parse_type(struct cc *cc, struct btype *type_info);
  24 static struct stree *cc_parse_pointer_type(struct cc *cc, struct btype *type_info);
  25 static struct stree *cc_parse_parameters(struct cc *cc);
  26 static bool type_identical(struct btype *type1, struct btype *type2);
  27 static void cc_compare_functions(struct cc *cc, struct stree *func1, struct stree *func2);
  28 static void cc_parse_decl_function(struct cc *, struct stree **psym_node);
  29 static void cc_parse_decl_variable(struct cc *, struct stree **psym_node);
  30 static void cc_parse_statement(struct cc *cc);
  31 static void cc_parse_compound_stat(struct cc *cc);
  32 static void cc_parse_defn_function(struct cc *cc, struct stree *func);
  33 static bool cc_parse_decl(struct cc *cc, struct stree *insert_here);
  34
  35 // throw a 'foo expected but bar found' error
  36 void cc_expect(struct cc *cc, const char *fmt, ...)
  37 {
  38     va_list ap;
  39     va_start(ap, fmt);
  40     fprintf(stderr, "%s:%d: error: ", LEX->tok.tok_sloc.name, LEX->tok.tok_sloc.line);
  41     vfprintf(stderr, fmt, ap);
  42     va_end(ap);
  43     fprintf(stderr, " expected but \"%s\" found\n", lex_get_tok_str(LEX, TOK, LEX->tok.tok_str));
  44 }
  45
  46 // throw a compile error with explicit source code location (va_list form)
  47 void cc_error_loc_v(struct cc *cc, struct sloc *sloc, const char *fmt, va_list ap)
  48 {
  49     fprintf(stderr, "%s:%d: error: ", sloc->name, sloc->line);
  50     vfprintf(stderr, fmt, ap);
  51     fputc('\n', stderr);
  52 }
  53
  54 // throw a compile error with explicit source code location (... form)
  55 void cc_error_loc(struct cc *cc, struct sloc *sloc, const char *fmt, ...)
  56 {
  57     va_list ap;
  58     va_start(ap, fmt);
  59     cc_error_loc_v(cc, sloc, fmt, ap);
  60     va_end(ap);
  61 }
  62
  63 // throw a compile error at current token
  64 void cc_error(struct cc *cc, const char *fmt, ...)
  65 {
  66     va_list ap;
  67     va_start(ap, fmt);
  68     cc_error_loc_v(cc, &LEX->tok.tok_sloc, fmt, ap);
  69     va_end(ap);
  70 }
  71
  72 // If the next token is in the given set of tokens,
  73 // then accept it, otherwise throw an error.
  74 // 'description' describes what is wanted. This could be
  75 // a token or a non-terminal name (eg. "type" or "expression").
  76 // Token set is a zero-terminated list of tokens. Eg.:
  77 //   >  cc_accept(cc, "operator", '+', '-', TOK_SHL, 0);
  78 // would throw "operator expected, but '*' found" if the next
  79 // token wasn't either '+', '-' or TOK_SHL (<<)
  80 static void cc_accept(struct cc *cc, const char *description, ...)
  81 {
  82     va_list ap;
  83     tok_t tok;
  84     va_start(ap, description);
  85     while ((tok = va_arg(ap, int))){
  86         if (TOK == tok){
  87             // ok
  88             lex_next(LEX);
  89             return;
  90         }
  91     }
  92     cc_expect(cc, "%s", description);
  93 }
  94
  95 // keep eating tokens until the current token is in the given set.
  96 // The set is a zero-terminated list of tokens, eg.:
  97 //   >  cc_sync(cc, ')', ';', 0);
  98 static void cc_sync(struct cc *cc, ...)
  99 {
 100     va_list ap;
 101     tok_t tok;
 102     for (;;){
 103         va_start(ap, cc);
 104         while ((tok = va_arg(ap, int))){
 105             if (TOK == tok)
 106                 return;
 107         }
 108         va_end(ap);
 109         lex_next(LEX);
 110     }
 111 }
 112
 113 static struct {
 114     int prec; // operator precedence level (1=highest)
 115     tok_t tok;  // operator token
 116 } operator_table[] = {
 117     {1, '*'}, {1, '/'},    {1, '%'},                  // multiplicative
 118     {2, '+'}, {2, '-'},                            // additive
 119     {3, TOK_SHL}, {3, TOK_SHR},                    // shiftive?
 120     {4, '<'}, {4, TOK_LE}, {4, '>'}, {4, TOK_GE},  // comparison
 121     {5, TOK_EQ}, {5, TOK_NE},                      // equality
 122     {6, '&'},                                      // bitwise and
 123     {7, '^'},                                      // bitwise xor
 124     {8, '|'},                                      // bitwise or
 125     {9, TOK_LAND},                                 // logical and
 126     {10, TOK_LOR},                                 // logical or
 127     {11, '?'},                                     // ternary
 128     {12, '='}, {12, TOK_EADD}, {12, TOK_ESUB},     // augmented assignment
 129     {12, TOK_EMUL}, {12, TOK_EDIV}, {12, TOK_EMOD},// .
 130     {12, TOK_ESHL}, {12, TOK_ESHR}, {12, TOK_EAND},// .
 131     {12, TOK_EXOR}, {12, TOK_EOR},                 // .
 132     {13, ','},                                     // comma operator
 133 };
 134
 135 static int get_precedence(tok_t tok)
 136 {
 137     int i;
 138     for (i=0; i<(sizeof operator_table / sizeof *operator_table); i++){
 139         if (operator_table[i].tok == tok){
 140             return operator_table[i].prec;
 141         }
 142     }
 143     return 0;
 144 }
 145
 146 // return true if parser state is in global scope
 147 // (i.e. what is being passed is at global (file) scope)
 148 static bool cc_isglobal(struct cc *cc)
 149 {
 150     return (cc->scope == cc->stree);
 151 }
 152
 153 // return the current function node
 154 static struct stree *cc_get_current_func(struct cc *cc)
 155 {
 156     // TODO!
 157     return NULL;
 158 }
 159
 160 // parse a factor, except subexpressions (...),
 161 // due to cast/subexpression ambiguity
 162 static struct stree *cc_parse_factor(struct cc *cc)
 163 {
 164     struct stree *fac = NULL;
 165     if (lex_is_ident(LEX, TOK)){
 166         fac = stree_create();
 167         fac->form = STF_FACTOR;
 168         fac->tok = TOK;
 169         lex_next(LEX);
 170     } else if (TOK == TOK_NUMBER){
 171         fac = stree_create();
 172         fac->form = STF_FACTOR;
 173         fac->tok = TOK_NUMBER;
 174         const_parse_number(&fac->cv, LEX->tok.tok_str);
 175         lex_next(LEX);
 176     } else if (TOK == TOK_STR){
 177         fac = stree_create();
 178         fac->form = STF_FACTOR;
 179         fac->tok = TOK_STR;
 180         fac->cv.type = CBT_STRING;
 181         fac->cv.v.string = LEX->tok.tok_str; // steal the string data :)
 182         LEX->tok.tok_str = NULL;
 183         lex_next(LEX);
 184     } else {
 185         cc_expect(cc, "expression");
 186     }
 187     return fac;
 188 }
 189
 190 static struct stree *cc_parse_unary(struct cc *cc)
 191 {
 192     struct stree *fac, *un, *prefix_first = NULL, *prefix_last = NULL;
 193
 194     // prefix unary operators
 195     while (TOK == TOK_INC || TOK == TOK_DEC || TOK == '+'
 196       || TOK == '-' || TOK == '!' || TOK == '~' || TOK == '*'
 197       || TOK == '&' || TOK == TOK_sizeof){
 198         un = stree_create();
 199         un->form = STF_UNOP;
 200         un->tok = TOK;
 201         if (TOK == '+'){
 202             // The '+' does nothing. Does anyone ever use it?!
 203             fprintf(stderr, "You're using a unary plus? Weird.\n");
 204         }
 205 link_prefix_unop:
 206         if (prefix_last){
 207             stree_append_child(prefix_last, un);
 208         } else {
 209             prefix_first = un;
 210         }
 211         prefix_last = un;
 212         lex_next(LEX);
 213     }
 214
 215     // subexpression or cast
 216     // (a bit ambiguous)
 217     if (TOK == '('){
 218         struct stree *type_node;
 219         struct btype btype;
 220         lex_next(LEX);
 221         if (cc_parse_type(cc, &btype)){
 222             // cast
 223             type_node = cc_parse_pointer_type(cc, &btype);
 224             un = stree_create();
 225             un->form = STF_UNOP;
 226             un->tok = TOK_CAST;
 227             un->btype = btype;
 228             if (type_node){
 229                 // excessive type information
 230                 stree_append_child(un, type_node);
 231             }
 232             // I could choose between one goto, or reams and reams
 233             // of tangled spaghetti-loops.
 234             // I preferred the goto.
 235             // Sorry Dijkstra.
 236             goto link_prefix_unop;
 237         } else {
 238             fac = cc_parse_expr(cc);
 239             cc_accept(cc, "\")\"", ')', 0);
 240         }
 241     } else {
 242         fac = cc_parse_factor(cc);
 243     }
 244
 245     // postfix unary operators
 246     while (TOK == TOK_INC || TOK == TOK_DEC || TOK == '[' ||
 247       TOK == TOK_ARROW || TOK == '.' || TOK == '('){
 248         un = stree_create();
 249         un->form = STF_UNOP;
 250         stree_append_child(un, fac);
 251         if (TOK == TOK_INC){
 252             un->tok = TOK_POSTINC;
 253             lex_next(LEX);
 254         } else if (TOK == TOK_DEC){
 255             un->tok = TOK_POSTDEC;
 256             lex_next(LEX);
 257         } else if (TOK == '['){
 258             // array subscript
 259             struct stree *subscript;
 260             un->tok = '[';
 261             lex_next(LEX);
 262             subscript = cc_parse_expr(cc);
 263             if (subscript){
 264                 stree_append_child(un, subscript);
 265                 cc_accept(cc, "\"]\"", ']', 0);
 266             }
 267         } else if (TOK == '.' || TOK == TOK_ARROW){
 268             // struct/union member access
 269             struct stree *member_name;
 270             un->tok = TOK;
 271             lex_next(LEX);
 272             if (lex_is_ident(LEX, TOK)){
 273                 member_name = stree_create();
 274                 member_name->form = STF_ATOM;
 275                 member_name->tok = TOK;
 276                 stree_append_child(un, member_name);
 277                 lex_next(LEX);
 278             } else {
 279                 cc_expect(cc, "identifier (member name)");
 280             }
 281         } else if (TOK == '('){
 282             struct stree *argument;
 283             // function call
 284             un->tok = '(';
 285             lex_next(LEX);
 286             if (TOK != ')'){
 287                 do {
 288                     argument = cc_parse_expr_nocomma(cc);
 289                     if (argument){
 290                         stree_append_child(un, argument);
 291                     }
 292                 } while (TOK == ',' ? (lex_next(LEX), 1) : 0);
 293             }
 294             cc_accept(cc, "\")\"", ')', 0);
 295         }
 296         fac = un;
 297     }
 298
 299     if (prefix_last){
 300         stree_append_child(prefix_last, fac);
 301         return prefix_first;
 302     } else {
 303         return fac;
 304     }
 305 }
 306
 307 static struct stree *cc_parse_expr_internal(struct cc *cc, int min_prec)
 308 {
 309     struct stree *lhs, *rhs, *op_node, *node, *node_parent, *node_right;
 310     int prec, node_prec, op_tok;
 311     lhs = cc_parse_unary(cc);
 312     if (!lhs)
 313         return NULL;
 314     prec = get_precedence(TOK);
 315     while (prec != 0 && prec <= min_prec){
 316         op_tok = TOK;
 317         lex_next(LEX);
 318         rhs = cc_parse_unary(cc);
 319         if (!rhs){
 320             return lhs;
 321         }
 322         // find where to insert it
 323         node = lhs;
 324         node_parent = NULL;
 325         while (node && node->form == STF_BINOP){
 326             node_prec = get_precedence(node->tok);
 327             if (prec < node_prec){
 328                 // carry on descending
 329                 node_right = stree_right(node);
 330                 if (node_right){
 331                     node_parent = node;
 332                     node = node_right;
 333                 } else {
 334                     break;
 335                 }
 336             } else {
 337                 break;
 338             }
 339         }
 340         if (node){
 341             // insert between node and node_parent
 342             op_node = stree_create();
 343             op_node->form = STF_BINOP;
 344             op_node->tok = op_tok;
 345             if (node_parent){
 346                 stree_remove_child(node);
 347                 stree_append_child(op_node, node);
 348                 stree_append_child(op_node, rhs);
 349                 stree_append_child(node_parent, op_node);
 350             } else {
 351                 stree_append_child(op_node, node);
 352                 stree_append_child(op_node, rhs);
 353                 lhs = op_node;
 354             }
 355         } else {
 356             die("not sure");
 357         }
 358         prec = get_precedence(TOK);
 359     }
 360     return lhs;
 361 }
 362
 363 static struct stree *cc_parse_expr(struct cc *cc)
 364 {
 365     return cc_parse_expr_internal(cc, 13);
 366 }
 367
 368 // same as cc_parse_expr, but don't parse the comma operator
 369 // used in function calls
 370 static struct stree *cc_parse_expr_nocomma(struct cc *cc)
 371 {
 372     return cc_parse_expr_internal(cc, 12);
 373 }
 374
 375 // parse struct or union (they're syntactically identical)
 376 static bool cc_parse_struct(struct cc *cc, struct btype *struct_type_info)
 377 {
 378     struct stree *tag;
 379     struct btype type_info, original_type_info;
 380     struct stree *type_node, *sym_node;
 381     tag = stree_create();
 382     tag->form = STF_TAG;
 383     tag->sloc = LEX->tok.tok_sloc;
 384     lex_next(LEX);
 385     if (lex_is_ident(LEX, TOK)){
 386         // prev_tag = stree_find(cc->scope, STF_TAG, TOK); TODO
 387         tag->tok = TOK;
 388         tag->sloc = LEX->tok.tok_sloc;
 389         lex_next(LEX);
 390     }
 391     if (TOK == '{'){
 392         // struct definition
 393         lex_next(LEX);
 394         while (TOK != 0 && TOK != '}'){
 395             if (cc_parse_type(cc, &original_type_info)){
 396                 do {
 397                     type_info = original_type_info;
 398                     type_node = cc_parse_pointer_type(cc, &type_info);
 399                     if (!lex_is_ident(LEX, TOK)){
 400                         cc_expect(cc, "identifier");
 401                         if (type_node){
 402                             stree_destroy(type_node);
 403                         }
 404                         return false; // XXX: LEAKS?
 405                     }
 406                     sym_node = stree_create();
 407                     sym_node->form = STF_VARIABLE;
 408                     sym_node->btype = type_info;
 409                     sym_node->tok = TOK;
 410                     sym_node->sloc = LEX->tok.tok_sloc;
 411                     if (type_node){
 412                         stree_append_child(sym_node, type_node);
 413                     }
 414                     stree_append_child(tag, sym_node);
 415                     lex_next(LEX);
 416                     // TODO: check for duplicate fields
 417                 } while (TOK == ',' ? (lex_next(LEX), true) : false);
 418             } else {
 419                 // ???
 420                 cc_expect(cc, "field or \"}\"");
 421             }
 422             cc_accept(cc, "\";\"", ';', 0);
 423         }
 424         cc_accept(cc, "\"}\"", '}', 0);
 425     } else {
 426     }
 427     stree_append_child(cc->scope, tag);
 428     struct_type_info->base_type = BT_STRUCT;
 429     struct_type_info->node = tag;
 430     return true;
 431 }
 432
 433 static bool cc_parse_type(struct cc *cc, struct btype *type_info)
 434 {
 435     type_info->base_type = 0;
 436     type_info->qualifiers = 0;
 437     switch (TOK){
 438         case TOK_void:
 439             type_info->base_type = BT_VOID; // well, it's a type, isn't it?
 440             // (HINT: the check for variables of type void is not done here)
 441             break;
 442         case TOK_char:
 443             type_info->base_type = BT_CHAR;
 444             break;
 445         case TOK_int:
 446             type_info->base_type = BT_INT;
 447             break;
 448         case TOK_float:
 449             type_info->base_type = BT_FLOAT;
 450             break;
 451         case TOK_double:
 452             type_info->base_type = BT_DOUBLE;
 453             break;
 454         case TOK_struct:
 455         case TOK_union:
 456             return cc_parse_struct(cc, type_info);
 457         default:
 458             return false;
 459     }
 460     lex_next(LEX);
 461     return true;
 462 }
 463
 464 // Parse a pointer type: next token must be after initial type declaration
 465 // i.e.:  int *foo;
 466 //            ^--current token: '*'
 467 // Returns a sub-stree of additional type information.
 468 // THIS MUST BE PUT SOMEWHERE IN A TREE.
 469 // *type_info will be modified to represent the new pointer type
 470 static struct stree *cc_parse_pointer_type(struct cc *cc, struct btype *type_info)
 471 {
 472     struct stree *type_node = NULL, *new_type_node;
 473     while (TOK == '*'){
 474         // create a type node to store the excess type information
 475         new_type_node = stree_create();
 476         new_type_node->form = STF_TYPE;
 477         new_type_node->btype = *type_info;
 478         if (type_node){
 479             stree_append_child(type_node, new_type_node);
 480         }
 481         type_node = new_type_node;
 482         // create pointer type
 483         type_info->base_type = BT_POINTER;
 484         type_info->qualifiers = 0; // TODO: parse qualifiers
 485         type_info->node = new_type_node;
 486         // eat '*'
 487         lex_next(LEX);
 488     }
 489     return type_node;
 490 }
 491
 492 // Parse function parameters
 493 // void foo(int a, int b);
 494 //           ^-- current token: 'int'
 495 // returns an STF_PARAMETERS node full of parameters, or
 496 // NULL if there aren't any.
 497 static struct stree *cc_parse_parameters(struct cc *cc)
 498 {
 499     struct stree *parameters = NULL;
 500     if (TOK == TOK_void){
 501         // just 'void' - no parameters
 502         lex_next(LEX);
 503     } else if (TOK != ')'){
 504         parameters = stree_create(); // create parameter list
 505         parameters->form = STF_PARAMETERS;
 506         do {
 507             struct btype type_info;
 508             struct stree *type_node, *param_node;
 509             if (TOK == TOK_ELLIPSIS){
 510                 // variadic function
 511                 param_node = stree_create();
 512                 param_node->form = STF_VARIABLE;
 513                 param_node->tok = TOK_ELLIPSIS;
 514                 if (stree_child_count(parameters) == 0){
 515                     cc_error(cc, "a named argument is required before \"...\"");
 516                 }
 517                 lex_next(LEX);
 518                 if (TOK != ')'){
 519                     cc_error(cc, "variadic function's \"...\" must be placed at the end of the parameter list");
 520                     cc_sync(cc, ')', ';', 0);
 521                 }
 522             } else {
 523                 // parse parameter's type
 524                 if (!cc_parse_type(cc, &type_info)){
 525                     cc_expect(cc, "type");
 526                 }
 527                 type_node = cc_parse_pointer_type(cc, &type_info);
 528                 // create parameter node
 529                 param_node = stree_create();
 530                 param_node->form = STF_VARIABLE;
 531                 param_node->btype = type_info;
 532                 // save extra type info, if there is any
 533                 if (type_node){
 534                     stree_append_child(param_node, type_node);
 535                 }
 536                 // does the parameter have a name yet? it may not.
 537                 if (lex_is_ident(LEX, TOK)){
 538                     // parameter has a name
 539                     param_node->tok = TOK;
 540                     lex_next(LEX);
 541                 }
 542                 // if it doesn't, that's ok too
 543                 // as long as it's not a function definition;
 544                 // we don't know yet, though.
 545             }
 546             // Now, put the parameter in the list
 547             stree_append_child(parameters, param_node);
 548         } while (TOK == ',' ? (lex_next(LEX), true) : false);
 549     }
 550     cc_accept(cc, "\")\"", ')', 0);
 551     return parameters;
 552 }
 553
 554 // return true if the two types are identical
 555 static bool type_identical(struct btype *type1, struct btype *type2)
 556 {
 557 top:
 558     if (type1->base_type != type2->base_type)
 559         return false;
 560     // TODO: check qualifiers?
 561     if (type1->base_type == BT_POINTER){
 562         // compare pointed types
 563         type1 = &type1->node->btype;
 564         type2 = &type2->node->btype;
 565         goto top;
 566     }
 567     return true; // all checks passed
 568 }
 569
 570 // compare two functions, func1 and func2, for compatibility
 571 static void cc_compare_functions(struct cc *cc, struct stree *func1, struct stree *func2)
 572 {
 573     struct stree *param_list_1, *param_list_2, *param_1, *param_2;
 574     int n;
 575
 576     // check return types
 577     if (!type_identical(&func1->btype, &func2->btype)){
 578         cc_error_loc(cc, &func2->sloc, "conflicting types for \"%s\"",
 579           lex_get_tok_str(LEX, func2->tok, NULL));
 580         cc_error_loc(cc, &func1->sloc, "previous declaration of \"%s\" was here",
 581           lex_get_tok_str(LEX, func1->tok, NULL));
 582     }
 583
 584     // check parameters
 585     param_list_1 = stree_get_child_by_form(func1, STF_PARAMETERS);
 586     param_list_2 = stree_get_child_by_form(func2, STF_PARAMETERS);
 587     if (stree_child_count(param_list_1) != stree_child_count(param_list_2)){
 588         // different number of parameters
 589         cc_error_loc(cc, &func2->sloc, "conflicting number of parameters for \"%s\"",
 590           lex_get_tok_str(LEX, func2->tok, NULL));
 591         cc_error_loc(cc, &func1->sloc, "previous declaration of \"%s\" was here",
 592           lex_get_tok_str(LEX, func1->tok, NULL));
 593     } else {
 594         // check each parameter
 595         param_1 = NULL;
 596         param_2 = NULL;
 597         n = 0;
 598         while (stree_next_child(param_list_1, &param_1),
 599           stree_next_child(param_list_2, &param_2),
 600           (param_1 && param_2)){
 601             n++;
 602             if (param_1->tok == TOK_ELLIPSIS || param_2->tok == TOK_ELLIPSIS){
 603                 // variadic function
 604                 if (param_1->tok == TOK_ELLIPSIS && param_2->tok == TOK_ELLIPSIS){
 605                     // that's ok
 606                 } else {
 607                     cc_error_loc(cc, &func2->sloc, "\"%s\" is %svariadic, unlike previous declaration",
 608                       lex_get_tok_str(LEX, func2->tok, NULL),
 609                       param_1->tok == TOK_ELLIPSIS ? "not " : "");
 610                     cc_error_loc(cc, &func1->sloc, "previous declaration of \"%s\" was here",
 611                       lex_get_tok_str(LEX, func1->tok, NULL));
 612                 }
 613             }
 614             // compare parameter types
 615             else if (!type_identical(&param_1->btype, &param_2->btype)){
 616                 cc_error_loc(cc, &func2->sloc, "conflicting types for parameter %d of \"%s\"",
 617                   n, lex_get_tok_str(LEX, func2->tok, NULL));
 618                 cc_error_loc(cc, &func1->sloc, "previous declaration of \"%s\" was here",
 619                   lex_get_tok_str(LEX, func1->tok, NULL));
 620             }
 621             // merge name information
 622             if (param_2->tok)
 623                 param_1->tok = param_2->tok;
 624         }
 625     }
 626 }
 627
 628 static void cc_parse_decl_function(struct cc *cc, struct stree **psym_node)
 629 {
 630     struct stree *parameters, *prev_decl;
 631     struct stree *sym_node = *psym_node;
 632
 633     if (!cc_isglobal(cc)){
 634         // Is a nested function
 635         struct stree *current_func;
 636         current_func = cc_get_current_func(cc);
 637         cc_error(cc, "nested functions are not permitted: \"%s\" inside \"%s\"",
 638           lex_get_tok_str(LEX, sym_node->tok, NULL),
 639           current_func ? lex_get_tok_str(LEX, current_func->tok, NULL) : "???");
 640     }
 641
 642     // find previous declaration of this symbol
 643     prev_decl = stree_find_local(cc->scope, STF_FUNCTION, sym_node->tok);
 644     if (!prev_decl) prev_decl = stree_find_local(cc->scope, STF_VARIABLE, sym_node->tok);
 645     if (prev_decl){
 646         if (prev_decl->form == STF_FUNCTION){
 647             // must check that declarations match later
 648         } else {
 649             cc_error_loc(cc, &sym_node->sloc,
 650               "\"%s\" declared as different kind of symbol",
 651               lex_get_tok_str(LEX, sym_node->tok, NULL));
 652             cc_error_loc(cc, &prev_decl->sloc,
 653               "previous declaration of \"%s\" was here",
 654               lex_get_tok_str(LEX, sym_node->tok, NULL));
 655         }
 656     }
 657     sym_node->form = STF_FUNCTION;
 658     // parse parameters
 659     lex_next(LEX); // eat '('
 660     parameters = cc_parse_parameters(cc);
 661     if (parameters){
 662         stree_append_child(sym_node, parameters);
 663     }
 664     if (prev_decl && prev_decl->form == STF_FUNCTION){
 665         // make sure declarations match
 666         cc_compare_functions(cc, prev_decl, sym_node);
 667         // either way, we don't want two copies, so delete the later one
 668         stree_destroy(sym_node);
 669         *psym_node = NULL;
 670     }
 671 }
 672
 673 static void cc_parse_decl_variable(struct cc *cc, struct stree **psym_node)
 674 {
 675     struct stree *sym_node = *psym_node;
 676     struct stree *prev_defn;
 677
 678     if (sym_node->btype.base_type == BT_VOID){
 679         cc_error_loc(cc, &sym_node->sloc, "cannot declare variable \"%s\" of type void: impossible without vacuum pump",
 680         lex_get_tok_str(LEX, sym_node->tok, NULL));
 681     }
 682
 683     // find previous declaration of this symbol
 684     prev_defn = stree_find_local(cc->scope, STF_VARIABLE, sym_node->tok);
 685     if (prev_defn){
 686         if (prev_defn->storage_class == STOR_EXTERN
 687           || prev_defn->storage_class == STOR_COMMON){
 688             // that's OK
 689         } else {
 690             cc_error_loc(cc, &sym_node->sloc, "redefinition of \"%s\"",
 691               lex_get_tok_str(LEX, sym_node->tok, NULL));
 692             cc_error_loc(cc, &prev_defn->sloc,
 693               "previous definition of \"%s\" was here",
 694               lex_get_tok_str(LEX, sym_node->tok, NULL));
 695         }
 696
 697         if (prev_defn->storage_class == STOR_EXTERN
 698           && sym_node->storage_class != STOR_EXTERN){
 699             prev_defn->storage_class = 0;
 700         }
 701         stree_destroy(sym_node);
 702         sym_node = prev_defn;
 703         *psym_node = NULL; // XXX: is this correct?
 704     }
 705
 706     sym_node->form = STF_VARIABLE;
 707 }
 708
 709 static void cc_parse_if_while_stat(struct cc *cc)
 710 {
 711     struct stree *stat, *expr, *old_scope;
 712     stat = stree_create();
 713     stat->form = STF_STAT;
 714     stat->tok = TOK;
 715     stree_append_child(cc->scope, stat);
 716     lex_next(LEX);
 717     cc_accept(cc, "\"(\"", '(', 0);
 718     expr = cc_parse_expr(cc);
 719     cc_accept(cc, "\")\"", ')', 0);
 720     stree_append_child(stat, expr);
 721
 722     old_scope = cc->scope;
 723     cc->scope = stat;
 724     cc_parse_statement(cc);
 725     cc->scope = old_scope;
 726 }
 727
 728 static void cc_parse_do_stat(struct cc *cc)
 729 {
 730     struct stree *stat, *expr, *old_scope;
 731     stat = stree_create();
 732     stat->form = STF_STAT;
 733     stat->tok = TOK;
 734     stree_append_child(cc->scope, stat);
 735     lex_next(LEX);
 736
 737     old_scope = cc->scope;
 738     cc->scope = stat;
 739     cc_parse_statement(cc);
 740     cc->scope = old_scope;
 741
 742     cc_accept(cc, "\"while\"", TOK_while, 0);
 743     cc_accept(cc, "\"(\"", '(', 0);
 744     expr = cc_parse_expr(cc);
 745     cc_accept(cc, "\")\"", ')', 0);
 746     stree_append_child(stat, expr);
 747 }
 748
 749 static void cc_parse_for_stat(struct cc *cc)
 750 {
 751     struct stree *stat, *expr, *old_scope;
 752     int i;
 753
 754     stat = stree_create();
 755     stat->form = STF_STAT;
 756     stat->tok = TOK;
 757     stree_append_child(cc->scope, stat);
 758     lex_next(LEX);
 759     cc_accept(cc, "\"(\"", '(', 0);
 760
 761     for (i=0; i<3; i++){
 762         if (TOK == (i == 2 ? ')' : ';')){
 763             expr = stree_create();
 764             expr->form = STF_PASS;
 765         } else {
 766             expr = cc_parse_expr(cc);
 767         }
 768         stree_append_child(stat, expr);
 769         cc_accept(cc,
 770             i == 2 ? "\")\"" : "\";\"",
 771             i == 2 ? ')' : ';',
 772             0);
 773     }
 774
 775     old_scope = cc->scope;
 776     cc->scope = stat;
 777     cc_parse_statement(cc);
 778     cc->scope = old_scope;
 779 }
 780
 781 static void cc_parse_switch_stat(struct cc *cc)
 782 {
 783     struct stree *stat, *expr, *old_scope;
 784     stat = stree_create();
 785     stat->form = STF_STAT;
 786     stat->tok = TOK;
 787     stree_append_child(cc->scope, stat);
 788     lex_next(LEX);
 789     cc_accept(cc, "\"(\"", '(', 0);
 790     expr = cc_parse_expr(cc);
 791     cc_accept(cc, "\")\"", ')', 0);
 792     stree_append_child(stat, expr);
 793
 794     old_scope = cc->scope;
 795     cc->scope = stat;
 796     cc_parse_statement(cc);
 797     cc->scope = old_scope;
 798 }
 799
 800 static void cc_parse_statement(struct cc *cc)
 801 {
 802     struct stree *expr, *block, *old_scope, *stat, *label;
 803 top:
 804     if (TOK == TOK_if || TOK == TOK_while){
 805         cc_parse_if_while_stat(cc);
 806     } else if (TOK == TOK_do){
 807         cc_parse_do_stat(cc);
 808         cc_accept(cc, "\";\"", ';', 0);
 809     } else if (TOK == TOK_for){
 810         cc_parse_for_stat(cc);
 811     } else if (TOK == TOK_switch){
 812         cc_parse_switch_stat(cc);
 813     } else if (TOK == TOK_case){
 814         if (cc->switch_scope){
 815             label = stree_create();
 816             label->form = STF_LABEL;
 817             label->tok = TOK;
 818             stree_append_child(cc->scope, label);
 819             lex_next(LEX);
 820             expr = cc_parse_expr(cc);
 821             stree_append_child(label, expr);
 822             cc_accept(cc, "\":\"", ':', 0);
 823         } else {
 824             cc_error(cc, "case label not within a switch statement");
 825             cc_sync(cc, ':', ';', 0);
 826             lex_next(LEX);
 827         }
 828         goto top;
 829     } else if (TOK == TOK_continue || TOK == TOK_break){
 830         stat = stree_create();
 831         stat->form = STF_JUMP;
 832         stat->tok = TOK;
 833         stree_append_child(cc->scope, stat);
 834         lex_next(LEX);
 835         cc_accept(cc, "\"}\"", '}', 0);
 836     } else if (TOK == TOK_return){
 837         stat = stree_create();
 838         stat->form = STF_JUMP;
 839         stat->tok = TOK;
 840         stree_append_child(cc->scope, stat);
 841         lex_next(LEX);
 842         if (TOK != ';'){
 843             expr = cc_parse_expr(cc);
 844             stree_append_child(stat, expr);
 845         }
 846         cc_accept(cc, "\"}\"", '}', 0);
 847     } else if (TOK == TOK_goto){
 848         lex_next(LEX);
 849         if (lex_is_ident(LEX, TOK)){
 850             stat = stree_create();
 851             stat->form = STF_JUMP;
 852             stat->tok = TOK;
 853             stree_append_child(cc->scope, stat);
 854             lex_next(LEX);
 855             cc_accept(cc, "\";\"", ';', 0);
 856         } else {
 857             cc_expect(cc, "label");
 858         }
 859     } else if (TOK == '{'){
 860         lex_next(LEX);
 861         block = stree_create();
 862         block->form = STF_BLOCK;
 863         stree_append_child(cc->scope, block);
 864         old_scope = cc->scope;
 865         cc->scope = block;
 866         cc_parse_compound_stat(cc);
 867         cc->scope = old_scope;
 868         cc_accept(cc, "\"}\"", '}', 0);
 869     } else if (TOK == ';'){
 870         // null statement
 871         stat = stree_create();
 872         stat->form = STF_PASS;
 873         stree_append_child(cc->scope, stat);
 874         lex_next(LEX);
 875     } else {
 876         // is it a label?
 877         if (lex_is_ident(LEX, TOK)){
 878             struct token ident_token;
 879             token_dup(&LEX->tok, &ident_token);
 880             lex_next(LEX);
 881             if (TOK == ':'){
 882                 // label
 883                 label = stree_create();
 884                 label->form = STF_LABEL;
 885                 label->tok = ident_token.tok;
 886                 stree_append_child(cc->scope, label);
 887                 lex_next(LEX);
 888                 token_free(&ident_token);
 889                 goto top;
 890             } else {
 891                 // wasn't a label
 892                 lex_unget_tok(LEX, &ident_token);
 893             }
 894         }
 895         expr = cc_parse_expr(cc);
 896         if (expr){
 897             stree_append_child(cc->scope, expr);
 898             cc_accept(cc, "\";\"", ';', 0);
 899         }
 900     }
 901 }
 902
 903 static void cc_parse_compound_stat(struct cc *cc)
 904 {
 905     while (TOK != 0 && TOK != '}'){
 906         if (cc_parse_decl(cc, cc->scope)){
 907
 908         } else {
 909             cc_parse_statement(cc);
 910         }
 911     }
 912 }
 913
 914 static void cc_parse_defn_function(struct cc *cc, struct stree *func)
 915 {
 916     struct stree *old_scope, *block;
 917     // TODO: check presence of parameter names
 918     // TODO: parse body
 919     block = stree_create();
 920     block->sloc = LEX->tok.tok_sloc;
 921     block->form = STF_BLOCK;
 922     stree_append_child(func, block);
 923     old_scope = cc->scope;
 924     cc->scope = block;
 925     cc_parse_compound_stat(cc);
 926     cc->scope = old_scope;
 927 }
 928
 929 // Parse a declaration/definition.
 930 // Returns true if it found one, false if there's no declaration (no tokens will have been eaten).
 931 // Will return true on syntax error, since tokens were eaten.
 932 static bool cc_parse_decl(struct cc *cc, struct stree *insert_here)
 933 {
 934     struct btype type_info, original_type_info;
 935     struct stree *type_node, *sym_node = NULL;
 936     bool was_func_defn = false;
 937     enum storage_class storage_class = 0;
 938
 939     if (TOK == TOK_extern || TOK == TOK_static){
 940         if (TOK == TOK_extern){
 941             storage_class = STOR_EXTERN;
 942         } else {
 943             storage_class = STOR_STATIC;
 944         }
 945         lex_next(LEX);
 946     }
 947
 948     if (cc_parse_type(cc, &original_type_info)){
 949         do {
 950             // restore the type before the '*'s (pointer types)
 951             type_info = original_type_info;
 952             type_node = cc_parse_pointer_type(cc, &type_info);
 953             if (!lex_is_ident(LEX, TOK)){
 954                 cc_expect(cc, "identifier");
 955                 if (type_node){
 956                     stree_destroy(type_node);
 957                 }
 958                 return true;
 959             }
 960
 961             // variable declaration or definition
 962             // or function declaration or definition
 963             sym_node = stree_create();
 964             sym_node->btype = type_info;
 965             sym_node->storage_class = storage_class;
 966             sym_node->tok = TOK;
 967             sym_node->sloc = LEX->tok.tok_sloc;
 968             lex_next(LEX);
 969             // put the type info somewhere
 970             if (type_node){
 971                 stree_append_child(sym_node, type_node);
 972             }
 973             if (TOK == '('){
 974                 // it is a function
 975                 cc_parse_decl_function(cc, &sym_node);
 976                 if (TOK == '{'){
 977                     // function definition
 978                     lex_next(LEX);
 979                     cc_parse_defn_function(cc, sym_node);
 980                     cc_accept(cc, "\"}\"", '}', 0);
 981                     was_func_defn = true;
 982                 }
 983             } else {
 984                 // it is a variable
 985                 cc_parse_decl_variable(cc, &sym_node);
 986             }
 987             if (sym_node){
 988                 stree_append_child(insert_here, sym_node);
 989             }
 990         } while (TOK == ',' ? (lex_next(LEX), true) : false);
 991         if (!was_func_defn){
 992             cc_accept(cc, "\";\"", ';', 0);
 993         }
 994         return true;
 995     } else if (storage_class){
 996         cc_expect(cc, "declaration");
 997         return true;
 998     } else {
 999         // hmm.
1000         return false;
1001     }
1002 }
1003
1004 void cc_parse(struct cc *cc)
1005 {
1006     cc->stree = cc->scope = stree_create();
1007     while (TOK != 0){
1008         if (!cc_parse_decl(cc, cc->scope)){
1009             break;
1010         }
1011     }
1012 }