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