src/org/xwt/js/Parser.java

   1 // Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
   2 package org.xwt.js;
   3
   4 import org.xwt.util.*;
   5 import java.io.*;
   6
   7 // FEATURE intern Integers/Numbers
   8
   9 /**
  10  *  Parses a stream of lexed tokens into a tree of JSFunction's.
  11  *
  12  *  There are three kinds of things we parse: blocks, statements, and
  13  *  expressions.
  14  *
  15  *  - Expressions are a special type of statement that evaluates to a
  16  *    value (for example, "break" is not an expression, * but "3+2"
  17  *    is).  Some tokens sequences start expressions (for * example,
  18  *    literal numbers) and others continue an expression which * has
  19  *    already been begun (for example, '+').  Finally, some *
  20  *    expressions are valid targets for an assignment operation; after
  21  *    * each of these expressions, continueExprAfterAssignable() is
  22  *    called * to check for an assignment operation.
  23  *
  24  *  - A statement ends with a semicolon and does not return a value.
  25  *
  26  *  - A block is a single statement or a sequence of statements
  27  *    surrounded by curly braces.
  28  *
  29  *  Each parsing method saves the parserLine before doing its actual
  30  *  work and restores it afterwards.  This ensures that parsing a
  31  *  subexpression does not modify the line number until a token
  32  *  *after* the subexpression has been consumed by the parent
  33  *  expression.
  34  *
  35  *  Technically it would be a better design for this class to build an
  36  *  intermediate parse tree and use that to emit bytecode.  Here's the
  37  *  tradeoff:
  38  *
  39  *  Advantages of building a parse tree:
  40  *  - easier to apply optimizations
  41  *  - would let us handle more sophisticated languages than JavaScript
  42  *
  43  *  Advantages of leaving out the parse tree
  44  *  - faster compilation
  45  *  - less load on the garbage collector
  46  *  - much simpler code, easier to understand
  47  *  - less error-prone
  48  *
  49  *  Fortunately JS is such a simple language that we can get away with
  50  *  the half-assed approach and still produce a working, complete
  51  *  compiler.
  52  *
  53  *  The bytecode language emitted doesn't really cause any appreciable
  54  *  semantic loss, and is itself a parseable language very similar to
  55  *  Forth or a postfix variant of LISP.  This means that the bytecode
  56  *  can be transformed into a parse tree, which can be manipulated.
  57  *  So if we ever want to add an optimizer, it could easily be done by
  58  *  producing a parse tree from the bytecode, optimizing that tree,
  59  *  and then re-emitting the bytecode.  The parse tree node class
  60  *  would also be much simpler since the bytecode language has so few
  61  *  operators.
  62  *
  63  *  Actually, the above paragraph is slightly inaccurate -- there are
  64  *  places where we push a value and then perform an arbitrary number
  65  *  of operations using it before popping it; this doesn't parse well.
  66  *  But these cases are clearly marked and easy to change if we do
  67  *  need to move to a parse tree format.
  68  */
  69 class Parser extends Lexer implements ByteCodes {
  70
  71
  72     // Constructors //////////////////////////////////////////////////////
  73
  74     public Parser(Reader r, String sourceName, int line) throws IOException { super(r, sourceName, line); }
  75
  76     /** for debugging */
  77     public static void main(String[] s) throws Exception {
  78         JSFunction block = new JSFunction("stdin", 0, new InputStreamReader(System.in), null);
  79         if (block == null) return;
  80         System.out.println(block);
  81     }
  82
  83
  84     // Statics ////////////////////////////////////////////////////////////
  85
  86     static byte[] precedence = new byte[MAX_TOKEN + 1];
  87     static boolean[] isRightAssociative = new boolean[MAX_TOKEN + 1];
  88     // Use this as the precedence when we want anything up to the comma
  89     private final static int NO_COMMA = 2;
  90     static {
  91         isRightAssociative[ASSIGN] =
  92             isRightAssociative[ASSIGN_BITOR] =
  93             isRightAssociative[ASSIGN_BITXOR] =
  94             isRightAssociative[ASSIGN_BITAND] =
  95             isRightAssociative[ASSIGN_LSH] =
  96             isRightAssociative[ASSIGN_RSH] =
  97             isRightAssociative[ASSIGN_URSH] =
  98             isRightAssociative[ASSIGN_ADD] =
  99             isRightAssociative[ASSIGN_SUB] =
 100             isRightAssociative[ASSIGN_MUL] =
 101             isRightAssociative[ASSIGN_DIV] =
 102             isRightAssociative[ASSIGN_MOD] = true;
 103
 104         precedence[COMMA] = 1;
 105         // 2 is intentionally left unassigned. we use minPrecedence==2 for comma separated lists
 106         precedence[ASSIGN] =
 107             precedence[ASSIGN_BITOR] =
 108             precedence[ASSIGN_BITXOR] =
 109             precedence[ASSIGN_BITAND] =
 110             precedence[ASSIGN_LSH] =
 111             precedence[ASSIGN_RSH] =
 112             precedence[ASSIGN_URSH] =
 113             precedence[ASSIGN_ADD] =
 114             precedence[ASSIGN_SUB] =
 115             precedence[ASSIGN_MUL] =
 116             precedence[ASSIGN_DIV] =
 117             precedence[ASSIGN_MOD] = 3;
 118         precedence[HOOK] = 4;
 119         precedence[OR] = 5;
 120         precedence[AND] = 6;
 121         precedence[BITOR] = 7;
 122         precedence[BITXOR] = 8;
 123         precedence[BITAND] = 9;
 124         precedence[EQ] = precedence[NE] = precedence[SHEQ] = precedence[SHNE] = 10;
 125         precedence[LT] = precedence[LE] = precedence[GT] = precedence[GE] = 11;
 126         precedence[LSH] = precedence[RSH] = precedence[URSH] = 12;
 127         precedence[ADD] = precedence[SUB] = 12;
 128         precedence[MUL] = precedence[DIV] = precedence[MOD] = 13;
 129         precedence[BITNOT] =  precedence[BANG] = precedence[TYPEOF] = 14;
 130         precedence[DOT] = precedence[LB] = precedence[LP] =  precedence[INC] = precedence[DEC] = 15;
 131     }
 132
 133
 134     // Parsing Logic /////////////////////////////////////////////////////////
 135
 136     /** gets a token and throws an exception if it is not <tt>code</tt> */
 137     private void consume(int code) throws IOException {
 138         if (getToken() != code) throw pe("expected " + codeToString[code] + ", got " + (op == -1 ? "EOF" : codeToString[op]));
 139     }
 140
 141     /**
 142      *  Parse the largest possible expression containing no operators
 143      *  of precedence below <tt>minPrecedence</tt> and append the
 144      *  bytecodes for that expression to <tt>appendTo</tt>; the
 145      *  appended bytecodes MUST grow the stack by exactly one element.
 146      */
 147     private void startExpr(JSFunction appendTo, int minPrecedence) throws IOException {
 148         int saveParserLine = parserLine;
 149         _startExpr(appendTo, minPrecedence);
 150         parserLine = saveParserLine;
 151     }
 152     private void _startExpr(JSFunction appendTo, int minPrecedence) throws IOException {
 153         int tok = getToken();
 154         JSFunction b = appendTo;
 155
 156         switch (tok) {
 157         case -1: throw pe("expected expression");
 158
 159         // all of these simply push values onto the stack
 160         case NUMBER: b.add(parserLine, LITERAL, number); break;
 161         case STRING: b.add(parserLine, LITERAL, string); break;
 162         case NULL: b.add(parserLine, LITERAL, null); break;
 163         case TRUE: case FALSE: b.add(parserLine, LITERAL, new Boolean(tok == TRUE)); break;
 164
 165         case LB: {
 166             b.add(parserLine, ARRAY, new Integer(0));                       // push an array onto the stack
 167             int size0 = b.size;
 168             int i = 0;
 169             if (peekToken() != RB)
 170                 while(true) {                                               // iterate over the initialization values
 171                     int size = b.size;
 172                     b.add(parserLine, LITERAL, new Integer(i++));           // push the index in the array to place it into
 173                     if (peekToken() == COMMA || peekToken() == RB)
 174                         b.add(parserLine, LITERAL, null);                   // for stuff like [1,,2,]
 175                     else
 176                         startExpr(b, NO_COMMA);                             // push the value onto the stack
 177                     b.add(parserLine, PUT);                                 // put it into the array
 178                     b.add(parserLine, POP);                                 // discard the value remaining on the stack
 179                     if (peekToken() == RB) break;
 180                     consume(COMMA);
 181                 }
 182             b.set(size0 - 1, new Integer(i));                               // back at the ARRAY instruction, write the size of the array
 183             consume(RB);
 184             break;
 185         }
 186         case SUB: {  // negative literal (like "3 * -1")
 187             consume(NUMBER);
 188             b.add(parserLine, LITERAL, new Double(number.doubleValue() * -1));
 189             break;
 190         }
 191         case LP: {  // grouping (not calling)
 192             startExpr(b, -1);
 193             consume(RP);
 194             break;
 195         }
 196         case INC: case DEC: {  // prefix (not postfix)
 197             startExpr(b, precedence[tok]);
 198             int prev = b.size - 1;
 199             if (b.get(prev) == GET && b.getArg(prev) != null)
 200                 b.set(prev, LITERAL, b.getArg(prev));
 201             else if(b.get(prev) == GET)
 202                 b.pop();
 203             else
 204                 throw pe("prefixed increment/decrement can only be performed on a valid assignment target");
 205             b.add(parserLine, GET_PRESERVE, Boolean.TRUE);
 206             b.add(parserLine, LITERAL, new Integer(1));
 207             b.add(parserLine, tok == INC ? ADD : SUB, null);
 208             b.add(parserLine, PUT, null);
 209             b.add(parserLine, SWAP, null);
 210             b.add(parserLine, POP, null);
 211             break;
 212         }
 213         case BANG: case BITNOT: case TYPEOF: {
 214             startExpr(b, precedence[tok]);
 215             b.add(parserLine, tok);
 216             break;
 217         }
 218         case LC: { // object constructor
 219             b.add(parserLine, OBJECT, null);                                     // put an object on the stack
 220             if (peekToken() != RC)
 221                 while(true) {
 222                     if (peekToken() != NAME && peekToken() != STRING)
 223                         throw pe("expected NAME or STRING");
 224                     getToken();
 225                     b.add(parserLine, LITERAL, string);                          // grab the key
 226                     consume(COLON);
 227                     startExpr(b, NO_COMMA);                                      // grab the value
 228                     b.add(parserLine, PUT);                                      // put the value into the object
 229                     b.add(parserLine, POP);                                      // discard the remaining value
 230                     if (peekToken() == RC) break;
 231                     consume(COMMA);
 232                     if (peekToken() == RC) break;                                // we permit {,,} -- I'm not sure if ECMA does
 233                 }
 234             consume(RC);
 235             break;
 236         }
 237         case NAME: {
 238             b.add(parserLine, TOPSCOPE);
 239             b.add(parserLine, LITERAL, string);
 240             continueExprAfterAssignable(b,minPrecedence);
 241             break;
 242         }
 243         case FUNCTION: {
 244             consume(LP);
 245             int numArgs = 0;
 246             JSFunction b2 = new JSFunction(sourceName, parserLine, null, null);
 247             b.add(parserLine, NEWFUNCTION, b2);
 248
 249             // function prelude; arguments array is already on the stack
 250             b2.add(parserLine, TOPSCOPE);
 251             b2.add(parserLine, SWAP);
 252             b2.add(parserLine, DECLARE, "arguments");                     // declare arguments (equivalent to 'var arguments;')
 253             b2.add(parserLine, SWAP);                                     // set this.arguments and leave the value on the stack
 254             b2.add(parserLine, PUT);
 255
 256             while(peekToken() != RP) {                                    // run through the list of argument names
 257                 numArgs++;
 258                 if (peekToken() == NAME) {
 259                     consume(NAME);                                        // a named argument
 260                     String varName = string;
 261
 262                     b2.add(parserLine, DUP);                              // dup the args array
 263                     b2.add(parserLine, GET, new Integer(numArgs - 1));   // retrieve it from the arguments array
 264                     b2.add(parserLine, TOPSCOPE);
 265                     b2.add(parserLine, SWAP);
 266                     b2.add(parserLine, DECLARE, varName);                  // declare the name
 267                     b2.add(parserLine, SWAP);
 268                     b2.add(parserLine, PUT);
 269                     b2.add(parserLine, POP);                               // pop the value
 270                     b2.add(parserLine, POP);                               // pop the scope
 271                 }
 272                 if (peekToken() == RP) break;
 273                 consume(COMMA);
 274             }
 275             consume(RP);
 276
 277             b2.numFormalArgs = numArgs;
 278             b2.add(parserLine, POP);                                      // pop off the arguments array
 279             b2.add(parserLine, POP);                                      // pop off TOPSCOPE
 280
 281            if(peekToken() != LC)
 282                 throw pe("JSFunctions must have a block surrounded by curly brackets");
 283
 284             parseBlock(b2, null);                                   // the function body
 285
 286             b2.add(parserLine, LITERAL, null);                        // in case we "fall out the bottom", return NULL
 287             b2.add(parserLine, RETURN);
 288
 289             break;
 290         }
 291         default: throw pe("expected expression, found " + codeToString[tok] + ", which cannot start an expression");
 292         }
 293
 294         // attempt to continue the expression
 295         continueExpr(b, minPrecedence);
 296     }
 297
 298
 299     /**
 300      *  Assuming that a complete assignable (lvalue) has just been
 301      *  parsed and the object and key are on the stack,
 302      *  <tt>continueExprAfterAssignable</tt> will attempt to parse an
 303      *  expression that modifies the assignable.  This method always
 304      *  decreases the stack depth by exactly one element.
 305      */
 306     private void continueExprAfterAssignable(JSFunction b,int minPrecedence) throws IOException {
 307         int saveParserLine = parserLine;
 308         _continueExprAfterAssignable(b,minPrecedence);
 309         parserLine = saveParserLine;
 310     }
 311     private void _continueExprAfterAssignable(JSFunction b,int minPrecedence) throws IOException {
 312         if (b == null) throw new Error("got null b; this should never happen");
 313         int tok = getToken();
 314         if (minPrecedence != -1 && (precedence[tok] < minPrecedence || (precedence[tok] == minPrecedence && !isRightAssociative[tok])))
 315             // force the default case
 316             tok = -1;
 317         switch(tok) {
 318         case ASSIGN_BITOR: case ASSIGN_BITXOR: case ASSIGN_BITAND: case ASSIGN_LSH: case ASSIGN_RSH: case ASSIGN_URSH:
 319         case ASSIGN_MUL: case ASSIGN_DIV: case ASSIGN_MOD: case ASSIGN_ADD: case ASSIGN_SUB: {
 320             b.add(parserLine, GET_PRESERVE);
 321             startExpr(b,  precedence[tok]);
 322             int size = b.size;
 323             if (tok == ASSIGN_ADD || tok == ASSIGN_SUB) {
 324                 b.add(parserLine, tok);
 325             }
 326             // tok-1 is always s/^ASSIGN_// (0 is BITOR, 1 is ASSIGN_BITOR, etc)
 327             b.add(parserLine, tok - 1, tok-1==ADD ? new Integer(2) : null);
 328             b.add(parserLine, PUT);
 329             b.add(parserLine, SWAP);
 330             b.add(parserLine, POP);
 331             if (tok == ASSIGN_ADD || tok == ASSIGN_SUB) b.set(size, tok, new Integer(b.size - size));
 332             break;
 333         }
 334         case INC: case DEC: { // postfix
 335             b.add(parserLine, GET_PRESERVE, Boolean.TRUE);
 336             b.add(parserLine, LITERAL, new Integer(1));
 337             b.add(parserLine, tok == INC ? ADD : SUB, null);
 338             b.add(parserLine, PUT, null);
 339             b.add(parserLine, SWAP, null);
 340             b.add(parserLine, POP, null);
 341             b.add(parserLine, LITERAL, new Integer(1));
 342             b.add(parserLine, tok == INC ? SUB : ADD, null);   // undo what we just did, since this is postfix
 343             break;
 344         }
 345         case ASSIGN: {
 346             startExpr(b, precedence[tok]);
 347             b.add(parserLine, PUT);
 348             b.add(parserLine, SWAP);
 349             b.add(parserLine, POP);
 350             break;
 351         }
 352         case LP: {
 353             int n = parseArgs(b, false);
 354
 355             // if the object supports GETCALL, we use this, and jump over the following two instructions
 356             b.add(parserLine,CALLMETHOD,new Integer(n));
 357             b.add(parserLine,GET);
 358             b.add(parserLine,CALL,new Integer(n));
 359             break;
 360         }
 361         default: {
 362             pushBackToken();
 363             if(b.get(b.size-1) == LITERAL && b.getArg(b.size-1) != null)
 364                 b.set(b.size-1,GET,b.getArg(b.size-1));
 365             else
 366                 b.add(parserLine, GET);
 367             return;
 368         }
 369         }
 370     }
 371
 372
 373     /**
 374      *  Assuming that a complete expression has just been parsed,
 375      *  <tt>continueExpr</tt> will attempt to extend this expression by
 376      *  parsing additional tokens and appending additional bytecodes.
 377      *
 378      *  No operators with precedence less than <tt>minPrecedence</tt>
 379      *  will be parsed.
 380      *
 381      *  If any bytecodes are appended, they will not alter the stack
 382      *  depth.
 383      */
 384     private void continueExpr(JSFunction b, int minPrecedence) throws IOException {
 385         int saveParserLine = parserLine;
 386         _continueExpr(b, minPrecedence);
 387         parserLine = saveParserLine;
 388     }
 389     private void _continueExpr(JSFunction b, int minPrecedence) throws IOException {
 390         if (b == null) throw new Error("got null b; this should never happen");
 391         int tok = getToken();
 392         if (tok == -1) return;
 393         if (minPrecedence != -1 && (precedence[tok] < minPrecedence || (precedence[tok] == minPrecedence && !isRightAssociative[tok]))) {
 394             pushBackToken();
 395             return;
 396         }
 397
 398         switch (tok) {
 399         case LP: {  // invocation (not grouping)
 400             int n = parseArgs(b, true);
 401             b.add(parserLine, CALL, new Integer(n));
 402             break;
 403         }
 404         case BITOR: case BITXOR: case BITAND: case SHEQ: case SHNE: case LSH:
 405         case RSH: case URSH: case MUL: case DIV: case MOD:
 406         case GT: case GE: case EQ: case NE: case LT: case LE: case SUB: {
 407             startExpr(b, precedence[tok]);
 408             b.add(parserLine, tok);
 409             break;
 410         }
 411         case ADD: {
 412             int count=1;
 413             int nextTok;
 414             do {
 415                 startExpr(b,precedence[tok]);
 416                 count++;
 417                 nextTok = getToken();
 418             } while(nextTok == tok);
 419             pushBackToken();
 420             b.add(parserLine, tok, new Integer(count));
 421             break;
 422         }
 423         case OR: case AND: {
 424             b.add(parserLine, tok == AND ? b.JF : b.JT, new Integer(0));       // test to see if we can short-circuit
 425             int size = b.size;
 426             startExpr(b, precedence[tok]);                                     // otherwise check the second value
 427             b.add(parserLine, JMP, new Integer(2));                            // leave the second value on the stack and jump to the end
 428             b.add(parserLine, LITERAL, tok == AND ?
 429                   new Boolean(false) : new Boolean(true));                     // target of the short-circuit jump is here
 430             b.set(size - 1, new Integer(b.size - size));                     // write the target of the short-circuit jump
 431             break;
 432         }
 433         case DOT: {
 434             // support foo..bar syntax for foo[""].bar
 435             if (peekToken() == DOT) {
 436                 string = "";
 437             } else {
 438                 consume(NAME);
 439             }
 440             b.add(parserLine, LITERAL, string);
 441             continueExprAfterAssignable(b,minPrecedence);
 442             break;
 443         }
 444         case LB: { // subscripting (not array constructor)
 445             startExpr(b, -1);
 446             consume(RB);
 447             continueExprAfterAssignable(b,minPrecedence);
 448             break;
 449         }
 450         case HOOK: {
 451             b.add(parserLine, JF, new Integer(0));                // jump to the if-false expression
 452             int size = b.size;
 453             startExpr(b, minPrecedence);                          // write the if-true expression
 454             b.add(parserLine, JMP, new Integer(0));               // if true, jump *over* the if-false expression
 455             b.set(size - 1, new Integer(b.size - size + 1));    // now we know where the target of the jump is
 456             consume(COLON);
 457             size = b.size;
 458             startExpr(b, minPrecedence);                          // write the if-false expression
 459             b.set(size - 1, new Integer(b.size - size + 1));    // this is the end; jump to here
 460             break;
 461         }
 462         case COMMA: {
 463             // pop the result of the previous expression, it is ignored
 464             b.add(parserLine,POP);
 465             startExpr(b,-1);
 466             break;
 467         }
 468         default: {
 469             pushBackToken();
 470             return;
 471         }
 472         }
 473
 474         continueExpr(b, minPrecedence);                           // try to continue the expression
 475     }
 476
 477     // parse a set of comma separated function arguments, assume LP has already been consumed
 478     // if swap is true, (because the function is already on the stack) we will SWAP after each argument to keep it on top
 479     private int parseArgs(JSFunction b, boolean swap) throws IOException {
 480         int i = 0;
 481         while(peekToken() != RP) {
 482             i++;
 483             if (peekToken() != COMMA) {
 484                 startExpr(b, NO_COMMA);
 485                 if (swap) b.add(parserLine, SWAP);
 486                 if (peekToken() == RP) break;
 487             }
 488             consume(COMMA);
 489         }
 490         consume(RP);
 491         return i;
 492     }
 493
 494     /** Parse a block of statements which must be surrounded by LC..RC. */
 495     void parseBlock(JSFunction b) throws IOException { parseBlock(b, null); }
 496     void parseBlock(JSFunction b, String label) throws IOException {
 497         int saveParserLine = parserLine;
 498         _parseBlock(b, label);
 499         parserLine = saveParserLine;
 500     }
 501     void _parseBlock(JSFunction b, String label) throws IOException {
 502         if (peekToken() == -1) return;
 503         else if (peekToken() != LC) parseStatement(b, null);
 504         else {
 505             consume(LC);
 506             while(peekToken() != RC && peekToken() != -1) parseStatement(b, null);
 507             consume(RC);
 508         }
 509     }
 510
 511     /** Parse a single statement, consuming the RC or SEMI which terminates it. */
 512     void parseStatement(JSFunction b, String label) throws IOException {
 513         int saveParserLine = parserLine;
 514         _parseStatement(b, label);
 515         parserLine = saveParserLine;
 516     }
 517     void _parseStatement(JSFunction b, String label) throws IOException {
 518         int tok = peekToken();
 519         if (tok == -1) return;
 520         switch(tok = getToken()) {
 521
 522         case THROW: case ASSERT: case RETURN: {
 523             if (tok == RETURN && peekToken() == SEMI)
 524                 b.add(parserLine, LITERAL, null);
 525             else
 526                 startExpr(b, -1);
 527             b.add(parserLine, tok);
 528             consume(SEMI);
 529             break;
 530         }
 531         case BREAK: case CONTINUE: {
 532             if (peekToken() == NAME) consume(NAME);
 533             b.add(parserLine, tok, string);
 534             consume(SEMI);
 535             break;
 536         }
 537         case VAR: {
 538             b.add(parserLine, TOPSCOPE);                         // push the current scope
 539             while(true) {
 540                 consume(NAME);
 541                 b.add(parserLine, DECLARE, string);               // declare it
 542                 if (peekToken() == ASSIGN) {                     // if there is an '=' after the variable name
 543                     consume(ASSIGN);
 544                     startExpr(b, NO_COMMA);
 545                     b.add(parserLine, PUT);                      // assign it
 546                     b.add(parserLine, POP);                      // clean the stack
 547                 } else {
 548                     b.add(parserLine, POP);                      // pop the string pushed by declare
 549                 }
 550                 if (peekToken() != COMMA) break;
 551                 consume(COMMA);
 552             }
 553             b.add(parserLine, POP);                              // pop off the topscope
 554             if ((mostRecentlyReadToken != RC || peekToken() == SEMI) && peekToken() != -1 && mostRecentlyReadToken != SEMI) consume(SEMI);
 555             break;
 556         }
 557         case IF: {
 558             consume(LP);
 559             startExpr(b, -1);
 560             consume(RP);
 561
 562             b.add(parserLine, JF, new Integer(0));                    // if false, jump to the else-block
 563             int size = b.size;
 564             parseStatement(b, null);
 565
 566             if (peekToken() == ELSE) {
 567                 consume(ELSE);
 568                 b.add(parserLine, JMP, new Integer(0));               // if we took the true-block, jump over the else-block
 569                 b.set(size - 1, new Integer(b.size - size + 1));
 570                 size = b.size;
 571                 parseStatement(b, null);
 572             }
 573             b.set(size - 1, new Integer(b.size - size + 1));        // regardless of which branch we took, b[size] needs to point here
 574             break;
 575         }
 576         case WHILE: {
 577             consume(LP);
 578             if (label != null) b.add(parserLine, LABEL, label);
 579             b.add(parserLine, LOOP);
 580             int size = b.size;
 581             b.add(parserLine, POP);                                   // discard the first-iteration indicator
 582             startExpr(b, -1);
 583             b.add(parserLine, JT, new Integer(2));                    // if the while() clause is true, jump over the BREAK
 584             b.add(parserLine, BREAK);
 585             consume(RP);
 586             parseStatement(b, null);
 587             b.add(parserLine, CONTINUE);                              // if we fall out of the end, definately continue
 588             b.set(size - 1, new Integer(b.size - size + 1));        // end of the loop
 589             break;
 590         }
 591         case SWITCH: {
 592             consume(LP);
 593             if (label != null) b.add(parserLine, LABEL, label);
 594             b.add(parserLine, LOOP);
 595             int size0 = b.size;
 596             startExpr(b, -1);
 597             consume(RP);
 598             consume(LC);
 599             while(true)
 600                 if (peekToken() == CASE) {                         // we compile CASE statements like a bunch of if..else's
 601                     consume(CASE);
 602                     b.add(parserLine, DUP);                        // duplicate the switch() value; we'll consume one copy
 603                     startExpr(b, -1);
 604                     consume(COLON);
 605                     b.add(parserLine, EQ);                         // check if we should do this case-block
 606                     b.add(parserLine, JF, new Integer(0));         // if not, jump to the next one
 607                     int size = b.size;
 608                     while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) parseStatement(b, null);
 609                     b.set(size - 1, new Integer(1 + b.size - size));
 610                 } else if (peekToken() == DEFAULT) {
 611                     consume(DEFAULT);
 612                     consume(COLON);
 613                     while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) parseStatement(b, null);
 614                 } else if (peekToken() == RC) {
 615                     consume(RC);
 616                     b.add(parserLine, BREAK);                      // break out of the loop if we 'fall through'
 617                     break;
 618                 } else {
 619                     throw pe("expected CASE, DEFAULT, or RC; got " + codeToString[peekToken()]);
 620                 }
 621             b.set(size0 - 1, new Integer(b.size - size0 + 1));      // end of the loop
 622             break;
 623         }
 624
 625         case DO: {
 626             if (label != null) b.add(parserLine, LABEL, label);
 627             b.add(parserLine, LOOP);
 628             int size = b.size;
 629             parseStatement(b, null);
 630             consume(WHILE);
 631             consume(LP);
 632             startExpr(b, -1);
 633             b.add(parserLine, JT, new Integer(2));                  // check the while() clause; jump over the BREAK if true
 634             b.add(parserLine, BREAK);
 635             b.add(parserLine, CONTINUE);
 636             consume(RP);
 637             consume(SEMI);
 638             b.set(size - 1, new Integer(b.size - size + 1));      // end of the loop; write this location to the LOOP instruction
 639             break;
 640         }
 641
 642         case TRY: {
 643             b.add(parserLine, TRY); // try bytecode causes a TryMarker to be pushed
 644             int tryInsn = b.size - 1;
 645             // parse the expression to be TRYed
 646             parseStatement(b, null);
 647             // pop the try  marker. this is pushed when the TRY bytecode is executed
 648             b.add(parserLine, POP);
 649             // jump forward to the end of the catch block, start of the finally block
 650             b.add(parserLine, JMP);
 651             int successJMPInsn = b.size - 1;
 652
 653             if (peekToken() != CATCH && peekToken() != FINALLY)
 654                 throw pe("try without catch or finally");
 655
 656             int catchJMPDistance = -1;
 657             if (peekToken() == CATCH) {
 658                 catchJMPDistance = b.size - tryInsn;
 659                 String exceptionVar;
 660                 getToken();
 661                 consume(LP);
 662                 consume(NAME);
 663                 exceptionVar = string;
 664                 consume(RP);
 665                 b.add(parserLine, TOPSCOPE);                        // the exception is on top of the stack; put it to the chosen name
 666                 b.add(parserLine, SWAP);
 667                 b.add(parserLine, LITERAL,exceptionVar);
 668                 b.add(parserLine, SWAP);
 669                 b.add(parserLine, PUT);
 670                 b.add(parserLine, POP);
 671                 b.add(parserLine, POP);
 672                 parseStatement(b, null);
 673                 // pop the try and catch markers
 674                 b.add(parserLine,POP);
 675                 b.add(parserLine,POP);
 676             }
 677
 678             // jump here if no exception was thrown
 679             b.set(successJMPInsn, new Integer(b.size - successJMPInsn));
 680
 681             int finallyJMPDistance = -1;
 682             if (peekToken() == FINALLY) {
 683                 b.add(parserLine, LITERAL, null); // null FinallyData
 684                 finallyJMPDistance = b.size - tryInsn;
 685                 consume(FINALLY);
 686                 parseStatement(b, null);
 687                 b.add(parserLine,FINALLY_DONE);
 688             }
 689
 690             // setup the TRY arguments
 691             b.set(tryInsn, new int[] { catchJMPDistance, finallyJMPDistance });
 692
 693             break;
 694         }
 695
 696         case FOR: {
 697             consume(LP);
 698
 699             tok = getToken();
 700             boolean hadVar = false;                                      // if it's a for..in, we ignore the VAR
 701             if (tok == VAR) { hadVar = true; tok = getToken(); }
 702             String varName = string;
 703             boolean forIn = peekToken() == IN;                           // determine if this is a for..in loop or not
 704             pushBackToken(tok, varName);
 705
 706             if (forIn) {
 707                 b.add(parserLine, NEWSCOPE);                             // for-loops always create new scopes
 708                 b.add(parserLine, LITERAL, varName);                     // declare the new variable
 709                 b.add(parserLine, DECLARE);
 710
 711                 b.add(parserLine, LOOP);                                 // we actually only add this to ensure that BREAK works
 712                 b.add(parserLine, POP);                                  // discard the first-iteration indicator
 713                 int size = b.size;
 714                 consume(NAME);
 715                 consume(IN);
 716                 startExpr(b, -1);
 717                 b.add(parserLine, PUSHKEYS);                             // push the keys as an array; check the length
 718                 b.add(parserLine, LITERAL, "length");
 719                 b.add(parserLine, GET);
 720                 consume(RP);
 721
 722                 b.add(parserLine, LITERAL, new Integer(1));              // decrement the length
 723                 b.add(parserLine, SUB);
 724                 b.add(parserLine, DUP);
 725                 b.add(parserLine, LITERAL, new Integer(0));              // see if we've exhausted all the elements
 726                 b.add(parserLine, LT);
 727                 b.add(parserLine, JF, new Integer(2));
 728                 b.add(parserLine, BREAK);                                // if we have, then BREAK
 729                 b.add(parserLine, GET_PRESERVE);                         // get the key out of the keys array
 730                 b.add(parserLine, LITERAL, varName);
 731                 b.add(parserLine, PUT);                                  // write it to this[varName]
 732                 parseStatement(b, null);                                 // do some stuff
 733                 b.add(parserLine, CONTINUE);                             // continue if we fall out the bottom
 734
 735                 b.set(size - 1, new Integer(b.size - size + 1));       // BREAK to here
 736                 b.add(parserLine, OLDSCOPE);                             // restore the scope
 737
 738             } else {
 739                 if (hadVar) pushBackToken(VAR, null);                    // yeah, this actually matters
 740                 b.add(parserLine, NEWSCOPE);                             // grab a fresh scope
 741
 742                 parseStatement(b, null);                                 // initializer
 743                 JSFunction e2 =                                    // we need to put the incrementor before the test
 744                     new JSFunction(sourceName, parserLine, null, null);  // so we save the test here
 745                 if (peekToken() != SEMI)
 746                     startExpr(e2, -1);
 747                 else
 748                     e2.add(parserLine, b.LITERAL, Boolean.TRUE);         // handle the for(foo;;foo) case
 749                 consume(SEMI);
 750                 if (label != null) b.add(parserLine, LABEL, label);
 751                 b.add(parserLine, LOOP);
 752                 int size2 = b.size;
 753
 754                 b.add(parserLine, JT, new Integer(0));                   // if we're on the first iteration, jump over the incrementor
 755                 int size = b.size;
 756                 if (peekToken() != RP) {                                 // do the increment thing
 757                     startExpr(b, -1);
 758                     b.add(parserLine, POP);
 759                 }
 760                 b.set(size - 1, new Integer(b.size - size + 1));
 761                 consume(RP);
 762
 763                 b.paste(e2);                                             // ok, *now* test if we're done yet
 764                 b.add(parserLine, JT, new Integer(2));                   // break out if we don't meet the test
 765                 b.add(parserLine, BREAK);
 766                 parseStatement(b, null);
 767                 b.add(parserLine, CONTINUE);                             // if we fall out the bottom, CONTINUE
 768                 b.set(size2 - 1, new Integer(b.size - size2 + 1));     // end of the loop
 769
 770                 b.add(parserLine, OLDSCOPE);                             // get our scope back
 771             }
 772             break;
 773         }
 774
 775         case NAME: {  // either a label or an identifier; this is the one place we're not LL(1)
 776             String possiblyTheLabel = string;
 777             if (peekToken() == COLON) {      // label
 778                 consume(COLON);
 779                 parseStatement(b, possiblyTheLabel);
 780                 break;
 781             } else {                         // expression
 782                 pushBackToken(NAME, possiblyTheLabel);
 783                 startExpr(b, -1);
 784                 b.add(parserLine, POP);
 785                 if ((mostRecentlyReadToken != RC || peekToken() == SEMI) && peekToken() != -1 && mostRecentlyReadToken != SEMI) consume(SEMI);
 786                 break;
 787             }
 788         }
 789
 790         case SEMI: return;                                               // yep, the null statement is valid
 791
 792         case LC: {  // blocks are statements too
 793             pushBackToken();
 794             b.add(parserLine, NEWSCOPE);
 795             parseBlock(b, label);
 796             b.add(parserLine, OLDSCOPE);
 797             break;
 798         }
 799
 800         default: {  // hope that it's an expression
 801             pushBackToken();
 802             startExpr(b, -1);
 803             b.add(parserLine, POP);
 804             if ((mostRecentlyReadToken != RC || peekToken() == SEMI) && peekToken() != -1 && mostRecentlyReadToken != SEMI) consume(SEMI);
 805             break;
 806         }
 807         }
 808     }
 809
 810
 811     // ParserException //////////////////////////////////////////////////////////////////////
 812     private IOException pe(String s) { return new IOException(sourceName + ":" + parserLine + " " + s); }
 813
 814 }
 815