parser.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 #include "ast.h"
   6 #include "hashmap.h"
   7
   8 #define T_DIV 0
   9 #define T_EQ 1
  10 #define T_GETS 2
  11 #define T_MINUS 3
  12 #define T_PLUS 4
  13 #define T_PROD 5
  14 #define T_LPAREN 6
  15 #define T_RPAREN 7
  16 #define T_AS 8
  17 #define T_ALL 9
  18 #define T_BOOL 10
  19 #define T_BUT 11
  20 #define T_CHAR 12
  21 #define T_DO 13
  22 #define T_DONE 14
  23 #define T_FALSE 15
  24 #define T_FOR 16
  25 #define T_INPUTC 17
  26 #define T_INPUTN 18
  27 #define T_MAX 19
  28 #define T_MIN 20
  29 #define T_NEXT 21
  30 #define T_NOT 22
  31 #define T_PREV 23
  32 #define T_PRINT 24
  33 #define T_PUSH 25
  34 #define T_TRUE 26
  35 #define T_WHILE 27
  36 #define T_COMBEGIN 28
  37 #define T_COMEND 29
  38 #define T_EOF 30
  39 #define T_UNKNOWN 31
  40 #define T_VARNAME 32
  41
  42 typedef short TOKEN;
  43
  44 static FILE *in;
  45 static char *last_string_seen;
  46 static int lss_sz = 0, token_pushed = 0, lineno = 1;
  47 static TOKEN forced_token;
  48
  49 void was_expecting(const char *s)
  50 {
  51   fprintf(stderr, "Line %d: Fatal: was expecting %s\n", lineno, s);
  52   exit(-1);
  53 }
  54
  55 void unexpected(const char *s)
  56 {
  57   fprintf(stderr, "Line %d: Fatal: unexpected %s\n", lineno, s);
  58   exit(-1);
  59 }
  60
  61 int next_char()
  62 {
  63   int c = 0;
  64
  65   while (c == 0)
  66     c = fgetc(in);
  67
  68   if (c == '\n')
  69     lineno++;
  70
  71   if (c >= 'A' && c <= 'Z')
  72     return c - 'A' + 'a';
  73   if (c == '\t' || c == '\n')
  74     return ' ';
  75
  76   return c;
  77 }
  78
  79 static TOKEN nt_varname(const char *prefix, char first)
  80 {
  81   int pre_len = strlen(prefix);
  82   int min_len = ((31 > pre_len) ? 31 : (2 * pre_len)) + 1;
  83   int slen = pre_len;
  84   char *ip, c = first;
  85
  86   if (!((c <= 'z' && c >= 'a') || (c <= '9' && c >= '0') || c == '_')) {
  87     return T_UNKNOWN;
  88   }
  89
  90   if (last_string_seen == NULL) {
  91     last_string_seen = malloc(sizeof (char) * min_len);
  92     lss_sz = min_len;
  93   } else if (min_len > lss_sz) {
  94     last_string_seen = realloc(last_string_seen, sizeof (char) * min_len);
  95     lss_sz = min_len;
  96   }
  97
  98   strcpy(last_string_seen, prefix);
  99   ip = last_string_seen + pre_len;
 100
 101   while (1) {
 102     if (!((c <= 'z' && c >= 'a') || (c <= '9' && c >= '0') || c == '_'))
 103       break;
 104
 105     *ip++ = c;
 106     if (++slen >= lss_sz) {
 107       lss_sz *= 2;
 108       last_string_seen = realloc(last_string_seen, sizeof (char) * lss_sz);
 109       ip = last_string_seen + slen;
 110     }
 111
 112     c = next_char();
 113   }
 114
 115   ungetc(c, in);
 116   *ip = '\0';
 117
 118   return T_VARNAME;
 119 }
 120
 121 static TOKEN nt_a()
 122 {
 123   int c;
 124
 125   switch (c = next_char()) {
 126   case 's':
 127     switch (c = next_char()) {
 128     case EOF:
 129     case ' ':
 130       return T_AS;
 131     default:
 132       return nt_varname("as", c);
 133     }
 134   case 'l':
 135     switch (c = next_char()) {
 136     case 'l':
 137       switch (c = next_char()) {
 138       case EOF:
 139       case ' ':
 140         return T_ALL;
 141       default:
 142         return nt_varname("all", c);
 143       }
 144     default:
 145       return nt_varname("al", c);
 146     }
 147   default:
 148     return nt_varname("a", c);
 149   }
 150 }
 151
 152 static TOKEN nt_b()
 153 {
 154   int c;
 155
 156   switch (c = next_char()) {
 157   case 'o':
 158     switch (c = next_char()) {
 159     case 'o':
 160       switch (c = next_char()) {
 161       case 'l':
 162         switch (c = next_char()) {
 163         case EOF:
 164         case ' ':
 165           return T_BOOL;
 166         default:
 167           return nt_varname("bool", c);
 168         }
 169       default:
 170         return nt_varname("boo", c);
 171       }
 172     default:
 173       return nt_varname("bo", c);
 174     }
 175   case 'u':
 176     switch (c = next_char()) {
 177     case 't':
 178       switch (c = next_char()) {
 179       case EOF:
 180       case ' ':
 181         return T_BUT;
 182       default:
 183         return nt_varname("but", c);
 184       }
 185     default:
 186       return nt_varname("bu", c);
 187     }
 188   default:
 189     return nt_varname("b", c);
 190   }
 191 }
 192
 193 static TOKEN nt_c()
 194 {
 195   int c;
 196
 197   switch (c = next_char()) {
 198   case 'h':
 199     switch (c = next_char()) {
 200     case 'a':
 201       switch (c = next_char()) {
 202       case 'r':
 203         switch (c = next_char()) {
 204         case EOF:
 205         case ' ':
 206           return T_CHAR;
 207         default:
 208           return nt_varname("char", c);
 209         }
 210       default:
 211         return nt_varname("cha", c);
 212       }
 213     default:
 214       return nt_varname("ch", c);
 215     }
 216   default:
 217     return nt_varname("c", c);
 218   }
 219 }
 220
 221 static TOKEN nt_d()
 222 {
 223   int c;
 224
 225   switch (c = next_char()) {
 226   case 'o':
 227     switch (c = next_char()) {
 228     case EOF:
 229     case ' ':
 230       return T_DO;
 231     case 'n':
 232       switch (c = next_char()) {
 233       case 'e':
 234         switch (c = next_char()) {
 235         case EOF:
 236         case ' ':
 237           return T_DONE;
 238         default:
 239           return nt_varname("done", c);
 240         }
 241       default:
 242         return nt_varname("don", c);
 243       }
 244     default:
 245       return nt_varname("do", c);
 246     }
 247   default:
 248     return nt_varname("d", c);
 249   }
 250 }
 251
 252 static TOKEN nt_f()
 253 {
 254   int c;
 255
 256   switch (c = next_char()) {
 257   case 'o':
 258     switch (c = next_char()) {
 259     case 'r':
 260       switch (c = next_char()) {
 261       case EOF:
 262       case ' ':
 263         return T_FOR;
 264       default:
 265         return nt_varname("for", c);
 266       }
 267     default:
 268       return nt_varname("fo", c);
 269     }
 270   case 'a':
 271     switch (c = next_char()) {
 272     case 'l':
 273       switch (c = next_char()) {
 274       case 's':
 275         switch (c = next_char()) {
 276         case 'e':
 277           switch (c = next_char()) {
 278           case EOF:
 279           case ' ':
 280             return T_FALSE;
 281           default:
 282             return nt_varname("false", c);
 283           }
 284         default:
 285           return nt_varname("fals", c);
 286         }
 287       default:
 288         return nt_varname("fal", c);
 289       }
 290     default:
 291       return nt_varname("fa", c);
 292     }
 293   default:
 294     return nt_varname("f", c);
 295   }
 296 }
 297
 298 static TOKEN nt_i()
 299 {
 300   int c;
 301
 302   switch (c = next_char()) {
 303   case 'n':
 304     switch (c = next_char()) {
 305     case 'p':
 306       switch (c = next_char()) {
 307       case 'u':
 308         switch (c = next_char()) {
 309         case 't':
 310           switch (c = next_char()) {
 311           case 'c':
 312             switch (c = next_char()) {
 313             case EOF:
 314             case ' ':
 315               return T_INPUTC;
 316             default:
 317               return nt_varname("inputc", c);
 318             }
 319           case 'n':
 320             switch (c = next_char()) {
 321             case EOF:
 322             case ' ':
 323               return T_INPUTN;
 324             default:
 325               return nt_varname("inputn", c);
 326             }
 327           default:
 328             return nt_varname("input", c);
 329           }
 330         default:
 331           return nt_varname("inpu", c);
 332         }
 333       default:
 334         return nt_varname("inp", c);
 335       }
 336     default:
 337       return nt_varname("in", c);
 338     }
 339   default:
 340     return nt_varname("i", c);
 341   }
 342 }
 343
 344 static TOKEN nt_m()
 345 {
 346   int c;
 347
 348   switch (c = next_char()) {
 349   case 'a':
 350     switch (c = next_char()) {
 351     case 'x':
 352       switch (c = next_char()) {
 353       case EOF:
 354       case ' ':
 355         return T_MAX;
 356       default:
 357         return nt_varname("max", c);
 358       }
 359     default:
 360       return nt_varname("ma", c);
 361     }
 362   case 'i':
 363     switch (c = next_char()) {
 364     case 'n':
 365       switch (c = next_char()) {
 366       case EOF:
 367       case ' ':
 368         return T_MIN;
 369       default:
 370         return nt_varname("min", c);
 371       }
 372     default:
 373       return nt_varname("mi", c);
 374     }
 375   default:
 376     return nt_varname("m", c);
 377   }
 378 }
 379
 380 static TOKEN nt_n()
 381 {
 382   int c;
 383
 384   switch (c = next_char()) {
 385   case 'e':
 386     switch (c = next_char()) {
 387     case 'x':
 388       switch (c = next_char()) {
 389       case 't':
 390         switch (c = next_char()) {
 391         case EOF:
 392         case ' ':
 393           return T_NEXT;
 394         default:
 395           return nt_varname("next", c);
 396         }
 397       default:
 398         return nt_varname("nex", c);
 399       }
 400     default:
 401       return nt_varname("ne", c);
 402     }
 403   case 'o':
 404     switch (c = next_char()) {
 405     case 't':
 406       switch (c = next_char()) {
 407       case EOF:
 408       case ' ':
 409         return T_NOT;
 410       default:
 411         return nt_varname("not", c);
 412       }
 413     default:
 414       return nt_varname("no", c);
 415     }
 416   default:
 417     return nt_varname("n", c);
 418   }
 419 }
 420
 421 static TOKEN nt_p()
 422 {
 423   int c;
 424
 425   switch (c = next_char()) {
 426   case 'r':
 427     switch (c = next_char()) {
 428     case 'e':
 429       switch (c = next_char()) {
 430       case 'v':
 431         switch (c = next_char()) {
 432         case EOF:
 433         case ' ':
 434           return T_PREV;
 435         default:
 436           return nt_varname("prev", c);
 437         }
 438       default:
 439         return nt_varname("pre", c);
 440       }
 441     case 'i':
 442       switch (c = next_char()) {
 443       case 'n':
 444         switch (c = next_char()) {
 445         case 't':
 446           switch (c = next_char()) {
 447           case EOF:
 448           case ' ':
 449             return T_PRINT;
 450           default:
 451             return nt_varname("print", c);
 452           }
 453         default:
 454           return nt_varname("prin", c);
 455         }
 456       default:
 457         return nt_varname("pri", c);
 458       }
 459     default:
 460       return nt_varname("pr", c);
 461     }
 462   case 'u':
 463     switch (c = next_char()) {
 464     case 's':
 465       switch (c = next_char()) {
 466       case 'h':
 467         switch (c = next_char()) {
 468         case EOF:
 469         case ' ':
 470           return T_PUSH;
 471         default:
 472           return nt_varname("push", c);
 473         }
 474       default:
 475         return nt_varname("pus", c);
 476       }
 477     default:
 478       return nt_varname("pu", c);
 479     }
 480   default:
 481     return nt_varname("p", c);
 482   }
 483 }
 484
 485 static TOKEN nt_t()
 486 {
 487   int c;
 488
 489   switch (c = next_char()) {
 490   case 'r':
 491     switch (c = next_char()) {
 492     case 'u':
 493       switch (c = next_char()) {
 494       case 'e':
 495         switch (c = next_char()) {
 496         case EOF:
 497         case ' ':
 498           return T_TRUE;
 499         default:
 500           return nt_varname("true", c);
 501         }
 502       default:
 503         return nt_varname("tru", c);
 504       }
 505     default:
 506       return nt_varname("tr", c);
 507     }
 508   default:
 509     return nt_varname("t", c);
 510   }
 511 }
 512
 513 static TOKEN nt_w()
 514 {
 515   int c;
 516
 517   switch (c = next_char()) {
 518   case 'h':
 519     switch (c = next_char()) {
 520     case 'i':
 521       switch (c = next_char()) {
 522       case 'l':
 523         switch (c = next_char()) {
 524         case 'e':
 525           switch (c = next_char()) {
 526           case EOF:
 527           case ' ':
 528             return T_WHILE;
 529           default:
 530             return nt_varname("while", c);
 531           }
 532         default:
 533           return nt_varname("whil", c);
 534         }
 535       default:
 536         return nt_varname("whi", c);
 537       }
 538     default:
 539       return nt_varname("wh", c);
 540     }
 541   default:
 542     return nt_varname("w", c);
 543   }
 544 }
 545
 546 static TOKEN nt_lparen()
 547 {
 548   char c = next_char();
 549
 550   if (c == '*')
 551     return T_COMBEGIN;
 552
 553   ungetc(c, in);
 554   return T_LPAREN;
 555 }
 556
 557 static TOKEN nt_asterisk()
 558 {
 559   if (next_char() == ')')
 560     return T_COMEND;
 561   else
 562     return T_PROD;
 563 }
 564
 565 static TOKEN nt_lt()
 566 {
 567   if (next_char() == '-')
 568     return T_GETS;
 569   else
 570     return T_UNKNOWN;
 571 }
 572
 573 TOKEN next_raw_tok()
 574 {
 575   int c = next_char();
 576
 577   while (c == ' ')
 578     c = next_char();
 579
 580   switch (c) {
 581   case EOF:
 582     return T_EOF;
 583   case '+':
 584     return T_PLUS;
 585   case '-':
 586     return T_MINUS;
 587   case '/':
 588     return T_DIV;
 589   case '=':
 590     return T_EQ;
 591   case ')':
 592     return T_RPAREN;
 593   case '(':
 594     return nt_lparen();
 595   case '*':
 596     return nt_asterisk();
 597   case '<':
 598     return nt_lt();
 599   case 'a':
 600     return nt_a();
 601   case 'b':
 602     return nt_b();
 603   case 'c':
 604     return nt_c();
 605   case 'd':
 606     return nt_d();
 607   case 'f':
 608     return nt_f();
 609   case 'i':
 610     return nt_i();
 611   case 'm':
 612     return nt_m();
 613   case 'n':
 614     return nt_n();
 615   case 'p':
 616     return nt_p();
 617   case 't':
 618     return nt_t();
 619   case 'w':
 620     return nt_w();
 621   default:
 622     return nt_varname("", c);
 623   }
 624 }
 625
 626 void push_back_token(TOKEN t)
 627 {
 628   token_pushed = 1;
 629   forced_token = t;
 630 }
 631
 632 TOKEN next_token()
 633 {
 634   TOKEN t;
 635   int comment_depth = 0;
 636
 637   if (token_pushed) {
 638     token_pushed = 0;
 639     return forced_token;
 640   }
 641
 642   t = next_raw_tok();
 643
 644   if (t == T_COMBEGIN) {
 645     comment_depth++;
 646     t = next_raw_tok();
 647     do {
 648       if (t == T_COMBEGIN)
 649         comment_depth++;
 650       else if (t == T_COMEND) {
 651         if (comment_depth == 0) {
 652           unexpected("*)");
 653         } else
 654           comment_depth--;
 655       } else if (t == T_EOF) {
 656         fprintf(stderr, "Line %d: Fatal: unterminated comment\n", lineno);
 657         exit(-1);
 658       }
 659       t = next_raw_tok();
 660     } while (comment_depth > 0 || t == T_COMBEGIN);
 661   }
 662
 663   return t;
 664 }
 665
 666 /* binding levels.  5 is tightest binding (parens, vars), 0 is loosest
 667    (eq testing) */
 668 ast *expr_0();
 669 ast *expr_1();
 670 ast *expr_2();
 671 ast *expr_3();
 672 ast *expr_4();
 673 ast *expr_5();
 674
 675 ast *expr_0()
 676 {
 677   ast *e1 = expr_1();
 678   ast *to_return;
 679   TOKEN t = next_token();
 680
 681   if (t == T_EQ) {
 682     to_return = malloc(sizeof (ast));
 683     to_return->type = A_DUAL;
 684     to_return->adata.adual = malloc(sizeof (ast_dual));
 685     to_return->adata.adual->operator = EQ;
 686     to_return->adata.adual->arg_1 = e1;
 687     to_return->adata.adual->arg_2 = expr_1();
 688   } else {
 689     push_back_token(t);
 690     to_return = e1;
 691   }
 692
 693   return to_return;
 694 }
 695
 696 ast *expr_1()
 697 {
 698   TOKEN t = next_token();
 699   ast *to_return;
 700
 701   if (t == T_MINUS || t == T_TRUE || t == T_FALSE || t == T_VARNAME
 702       || t == T_LPAREN) {
 703     push_back_token(t);
 704     return expr_2();
 705   }
 706
 707   to_return = malloc(sizeof (ast));
 708   if (t == T_MIN || t == T_MAX) {
 709     to_return->type = A_DUAL;
 710     to_return->adata.adual = malloc(sizeof (ast_dual));
 711     to_return->adata.adual->operator =(t == T_MIN) ? MIN : MAX;
 712     to_return->adata.adual->arg_1 = expr_2();
 713     to_return->adata.adual->arg_2 = expr_2();
 714   } else if (t == T_NOT || t == T_BOOL || t == T_CHAR || t == T_NEXT
 715              || t == T_PREV) {
 716     to_return->type = A_UNARY;
 717     to_return->adata.aunary = malloc(sizeof (ast_unary));
 718     switch (t) {
 719     case T_NOT:
 720       to_return->adata.aunary->operator = NOT;
 721       break;
 722     case T_BOOL:
 723       to_return->adata.aunary->operator = CBOOL;
 724       break;
 725     case T_CHAR:
 726       to_return->adata.aunary->operator = CCHAR;
 727       break;
 728     case T_NEXT:
 729       to_return->adata.aunary->operator = NEXT;
 730       break;
 731     case T_PREV:
 732       to_return->adata.aunary->operator = PREV;
 733       break;
 734     }
 735     to_return->adata.aunary->arg = expr_2();
 736   } else {
 737     was_expecting("operator, -, constant, variable name, or (");
 738   }
 739   return to_return;
 740 }
 741
 742 ast *expr_2()
 743 {
 744   ast *e1 = expr_3();
 745   ast *to_return = e1;
 746   TOKEN t = next_token();
 747
 748   while (t == T_PLUS || t == T_MINUS) {
 749     e1 = to_return;
 750     to_return = malloc(sizeof (ast));
 751     to_return->type = A_DUAL;
 752     to_return->adata.adual = malloc(sizeof (ast_dual));
 753     to_return->adata.adual->operator =(t == T_PLUS) ? SUM : DIFF;
 754     to_return->adata.adual->arg_1 = e1;
 755     to_return->adata.adual->arg_2 = expr_3();
 756     t = next_token();
 757   }
 758   push_back_token(t);
 759   return to_return;
 760 }
 761
 762 ast *expr_3()
 763 {
 764   ast *e1 = expr_4();
 765   ast *to_return = e1;
 766   TOKEN t = next_token();
 767
 768   while (t == T_PROD || t == T_DIV) {
 769     e1 = to_return;
 770     to_return = malloc(sizeof (ast));
 771     to_return->type = A_DUAL;
 772     to_return->adata.adual = malloc(sizeof (ast_dual));
 773     to_return->adata.adual->operator =(t == T_PROD) ? PRODUCT : DIV;
 774     to_return->adata.adual->arg_1 = e1;
 775     to_return->adata.adual->arg_2 = expr_4();
 776     t = next_token();
 777   }
 778   push_back_token(t);
 779   return to_return;
 780 }
 781
 782 ast *expr_4()
 783 {
 784   TOKEN t = next_token();
 785   ast *to_return;
 786
 787   if (t == T_MINUS) {
 788     to_return = malloc(sizeof (ast));
 789     to_return->type = A_UNARY;
 790     to_return->adata.aunary = malloc(sizeof (ast_unary));
 791     to_return->adata.aunary->operator = NEGATION;
 792     to_return->adata.aunary->arg = expr_5();
 793     return to_return;
 794   }
 795
 796   push_back_token(t);
 797   return expr_5();
 798 }
 799
 800 ast *expr_5()
 801 {
 802   TOKEN t = next_token();
 803   ast *to_return;
 804
 805   if (t == T_TRUE)
 806     return const_true;
 807   if (t == T_FALSE)
 808     return const_false;
 809   if (t == T_VARNAME) {
 810     to_return = malloc(sizeof (ast));
 811     to_return->type = A_VAR;
 812     to_return->adata.avar = find_var(last_string_seen);
 813     return to_return;
 814   }
 815   if (t == T_LPAREN) {
 816     to_return = expr_0();
 817     if (next_token() != T_RPAREN)
 818       was_expecting(")");
 819     return to_return;
 820   }
 821   was_expecting("expression");
 822   return NULL;
 823 }
 824
 825 ast *build_expr()
 826 {
 827   return expr_0();
 828 }
 829
 830 ast_func *build_func(TOKEN first)
 831 {
 832   ast_func *to_return = malloc(sizeof (ast_func));
 833
 834   switch (first) {
 835   case T_PUSH:
 836     to_return->operator = PUSH;
 837     to_return->arg_1 = build_expr(0);
 838     break;
 839   case T_PRINT:
 840     to_return->operator = PRINT;
 841     to_return->arg_1 = build_expr(0);
 842     break;
 843   case T_INPUTC:
 844     to_return->operator = INPUTC;
 845     break;
 846   case T_INPUTN:
 847     to_return->operator = INPUTN;
 848     break;
 849   case T_VARNAME:
 850     to_return->operator = ASSIGN;
 851     to_return->arg_1 = malloc(sizeof (ast));
 852     if (next_token() != T_GETS)
 853       was_expecting("assignment");
 854     to_return->arg_1->type = A_VAR;
 855     to_return->arg_1->adata.avar = find_var(last_string_seen);
 856     to_return->arg_2 = build_expr(0);
 857     break;
 858   default:
 859     was_expecting("known function");
 860   }
 861
 862   return to_return;
 863 }
 864
 865 ast_seq *build_seq();
 866
 867 ast_while *build_while()
 868 {
 869   ast_while *to_return = malloc(sizeof (ast_while));
 870
 871   to_return->condition = build_expr(0);
 872
 873   if (next_token() != T_DO)
 874     was_expecting("do");
 875
 876   to_return->commands = build_seq(1);
 877
 878   return to_return;
 879 }
 880
 881 int stoi(const char *s)
 882 {
 883   if (!strcmp(s, "one"))
 884     return 1;
 885   if (!strcmp(s, "two"))
 886     return 2;
 887   if (!strcmp(s, "three"))
 888     return 3;
 889   if (!strcmp(s, "four"))
 890     return 4;
 891   if (!strcmp(s, "five"))
 892     return 5;
 893   if (!strcmp(s, "six"))
 894     return 6;
 895   if (!strcmp(s, "seven"))
 896     return 7;
 897   if (!strcmp(s, "eight"))
 898     return 8;
 899   if (!strcmp(s, "nine"))
 900     return 9;
 901   return -1;
 902 }
 903
 904 const char *itos(int i)
 905 {
 906   switch (i) {
 907   case 1:
 908     return "one";
 909   case 2:
 910     return "two";
 911   case 3:
 912     return "three";
 913   case 4:
 914     return "four";
 915   case 5:
 916     return "five";
 917   case 6:
 918     return "six";
 919   case 7:
 920     return "seven";
 921   case 8:
 922     return "eight";
 923   case 9:
 924     return "nine";
 925   default:
 926     return "none";
 927   }
 928 }
 929
 930 ast_for *build_for()
 931 {
 932   ast_for *to_return = malloc(sizeof (ast_for));
 933   int k1 = -1, k2 = -1, ktmp, is_range, is_remove = 0;
 934   const char *kref = NULL;
 935   int max_knights = 8, max_knights_remove = 8;
 936   char c;
 937   TOKEN t;
 938
 939   to_return->num_knights = 0;
 940   to_return->num_knights_remove = 0;
 941   to_return->iterable_knights = malloc(max_knights * sizeof (char *));
 942   to_return->removable_knights = malloc(max_knights_remove * sizeof (char *));
 943
 944   do {
 945     is_range = 0;
 946     t = next_token();
 947     switch (t) {
 948     case T_ALL:
 949       k1 = 1;
 950       k2 = 9;
 951       is_range = 1;
 952       break;
 953     case T_BUT:
 954       is_remove = 1;
 955       break;
 956     case T_VARNAME:
 957       k1 = stoi(last_string_seen);
 958       if ((c = next_char()) == '.') {
 959         if (k1 < 0)
 960           was_expecting("literal knight name");
 961         if ((c = next_char()) == '.') {
 962           is_range = 1;
 963           t = next_token();
 964           if (t != T_VARNAME)
 965             was_expecting("range-ending knight reference");
 966           k2 = stoi(last_string_seen);
 967           if (k2 < 0)
 968             was_expecting("literal knight reference ('one', 'eight', etc)");
 969         } else {
 970           was_expecting("..");
 971         }
 972       } else {
 973         kref = last_string_seen;
 974       }
 975       break;
 976     case T_AS:
 977       break;
 978     default:
 979       was_expecting("variable name, all, but, or as");
 980     }
 981
 982     if (t != T_AS && t != T_BUT) {
 983       if (is_range) {
 984         if (k1 >= k2) {
 985           fprintf(stderr, "Line %d: Fatal: range %d..%d is invalid\n", lineno,
 986                   k1, k2);
 987           exit(-1);
 988         }
 989
 990         if (!is_remove) {
 991           if (to_return->num_knights + (k2 - k1 + 1) >= max_knights) {
 992             max_knights += k2 - k1;
 993             to_return->iterable_knights = realloc(to_return->iterable_knights,
 994                                                   max_knights *
 995                                                   sizeof (char *));
 996           }
 997         } else {
 998           if (to_return->num_knights_remove + (k2 - k1 + 1) >=
 999               max_knights_remove) {
1000             max_knights_remove += k2 - k1;
1001             to_return->removable_knights = realloc(to_return->removable_knights,
1002                                                    max_knights_remove *
1003                                                    sizeof (char *));
1004           }
1005         }
1006
1007         if (!is_remove) {
1008           for (ktmp = k1; ktmp <= k2; ++ktmp) {
1009             kref = itos(ktmp);
1010             to_return->iterable_knights[to_return->num_knights] =
1011                 malloc(sizeof (char) * (strlen(kref) + 1));
1012             strcpy(to_return->iterable_knights[to_return->num_knights], kref);
1013             to_return->num_knights++;
1014           }
1015           max_knights += (k2 - k1 + 1);
1016         } else {
1017           for (ktmp = k1; ktmp <= k2; ++ktmp) {
1018             kref = itos(ktmp);
1019             to_return->removable_knights[to_return->num_knights_remove] =
1020                 malloc(sizeof (char) * (strlen(kref) + 1));
1021             strcpy(to_return->removable_knights[to_return->num_knights_remove],
1022                    kref);
1023             to_return->num_knights_remove++;
1024           }
1025           max_knights_remove += (k2 - k1 + 1);
1026         }
1027
1028       } else {
1029         if (!is_remove) {
1030           if (to_return->num_knights + 1 >= max_knights) {
1031             max_knights *= 2;
1032             to_return->iterable_knights = realloc(to_return->iterable_knights,
1033                                                   max_knights *
1034                                                   sizeof (char *));
1035           }
1036           to_return->iterable_knights[to_return->num_knights] =
1037               malloc(sizeof (char) * (strlen(kref) + 1));
1038           strcpy(to_return->iterable_knights[to_return->num_knights], kref);
1039           to_return->num_knights++;
1040         } else {
1041           if (to_return->num_knights_remove + 1 >= max_knights_remove) {
1042             max_knights_remove *= 2;
1043             to_return->removable_knights = realloc(to_return->removable_knights,
1044                                                    max_knights_remove *
1045                                                    sizeof (char *));
1046           }
1047           to_return->removable_knights[to_return->num_knights_remove] =
1048               malloc(sizeof (char) * (strlen(kref) + 1));
1049           strcpy(to_return->removable_knights[to_return->num_knights_remove],
1050                  kref);
1051           to_return->num_knights_remove++;
1052         }
1053       }
1054     }
1055   } while (t != T_AS);
1056
1057   t = next_token();
1058   if (t != T_VARNAME)
1059     was_expecting("variable");
1060
1061   to_return->variable = find_var(last_string_seen);
1062
1063   t = next_token();
1064   if (t != T_DO)
1065     was_expecting("do");
1066
1067   to_return->commands = build_seq(1);
1068
1069   return to_return;
1070 }
1071
1072 ast_seq *build_seq(int expect_done)
1073 {
1074   ast_seq *to_return = calloc(1, sizeof (ast_seq));
1075   ast_seq *current = to_return;
1076   TOKEN t;
1077
1078   while (1) {
1079     t = next_token();
1080     if (t == T_DONE || t == T_EOF) {
1081       if (expect_done == (t == T_DONE)) {
1082         return to_return;
1083       } else {
1084         unexpected("done or EOF");
1085       }
1086     }
1087     current->data = calloc(1, sizeof (ast));
1088     if (t == T_WHILE) {
1089       current->data->type = A_WHILE;
1090       current->data->adata.awhile = build_while();
1091     } else if (t == T_FOR) {
1092       current->data->type = A_FOR;
1093       current->data->adata.afor = build_for();
1094     } else {
1095       current->data->type = A_FUNC;
1096       current->data->adata.afunc = build_func(t);
1097     }
1098     current->next = calloc(1, sizeof (ast_seq));
1099     current = current->next;
1100   }
1101 }
1102
1103 ast *build(FILE * input)
1104 {
1105   ast *to_return = malloc(sizeof (ast));
1106
1107   if (!input) {
1108     fprintf(stderr, "Could not open input file\n");
1109     exit(-1);
1110   }
1111
1112   in = input;
1113
1114   to_return->type = A_SEQ;
1115   to_return->adata.aseq = build_seq(0);
1116   return to_return;
1117 }