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, new Integer(2));
 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, new Integer(2));
 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, 2);
 354             b.add(parserLine, GET_PRESERVE);
 355             b.add(parserLine, CALLMETHOD, new Integer(n));
 356             break;
 357         }
 358         default: {
 359             pushBackToken();
 360             if(b.get(b.size-1) == LITERAL && b.getArg(b.size-1) != null)
 361                 b.set(b.size-1,GET,b.getArg(b.size-1));
 362             else
 363                 b.add(parserLine, GET);
 364             return;
 365         }
 366         }
 367     }
 368
 369
 370     /**
 371      *  Assuming that a complete expression has just been parsed,
 372      *  <tt>continueExpr</tt> will attempt to extend this expression by
 373      *  parsing additional tokens and appending additional bytecodes.
 374      *
 375      *  No operators with precedence less than <tt>minPrecedence</tt>
 376      *  will be parsed.
 377      *
 378      *  If any bytecodes are appended, they will not alter the stack
 379      *  depth.
 380      */
 381     private void continueExpr(JSFunction b, int minPrecedence) throws IOException {
 382         int saveParserLine = parserLine;
 383         _continueExpr(b, minPrecedence);
 384         parserLine = saveParserLine;
 385     }
 386     private void _continueExpr(JSFunction b, int minPrecedence) throws IOException {
 387         if (b == null) throw new Error("got null b; this should never happen");
 388         int tok = getToken();
 389         if (tok == -1) return;
 390         if (minPrecedence != -1 && (precedence[tok] < minPrecedence || (precedence[tok] == minPrecedence && !isRightAssociative[tok]))) {
 391             pushBackToken();
 392             return;
 393         }
 394
 395         switch (tok) {
 396         case LP: {  // invocation (not grouping)
 397             int n = parseArgs(b, 1);
 398             b.add(parserLine, CALL, new Integer(n));
 399             break;
 400         }
 401         case BITOR: case BITXOR: case BITAND: case SHEQ: case SHNE: case LSH:
 402         case RSH: case URSH: case MUL: case DIV: case MOD:
 403         case GT: case GE: case EQ: case NE: case LT: case LE: case SUB: {
 404             startExpr(b, precedence[tok]);
 405             b.add(parserLine, tok);
 406             break;
 407         }
 408         case ADD: {
 409             int count=1;
 410             int nextTok;
 411             do {
 412                 startExpr(b,precedence[tok]);
 413                 count++;
 414                 nextTok = getToken();
 415             } while(nextTok == tok);
 416             pushBackToken();
 417             b.add(parserLine, tok, new Integer(count));
 418             break;
 419         }
 420         case OR: case AND: {
 421             b.add(parserLine, tok == AND ? b.JF : b.JT, new Integer(0));       // test to see if we can short-circuit
 422             int size = b.size;
 423             startExpr(b, precedence[tok]);                                     // otherwise check the second value
 424             b.add(parserLine, JMP, new Integer(2));                            // leave the second value on the stack and jump to the end
 425             b.add(parserLine, LITERAL, tok == AND ?
 426                   new Boolean(false) : new Boolean(true));                     // target of the short-circuit jump is here
 427             b.set(size - 1, new Integer(b.size - size));                     // write the target of the short-circuit jump
 428             break;
 429         }
 430         case DOT: {
 431             // support foo..bar syntax for foo[""].bar
 432             if (peekToken() == DOT) {
 433                 string = "";
 434             } else {
 435                 consume(NAME);
 436             }
 437             b.add(parserLine, LITERAL, string);
 438             continueExprAfterAssignable(b,minPrecedence);
 439             break;
 440         }
 441         case LB: { // subscripting (not array constructor)
 442             startExpr(b, -1);
 443             consume(RB);
 444             continueExprAfterAssignable(b,minPrecedence);
 445             break;
 446         }
 447         case HOOK: {
 448             b.add(parserLine, JF, new Integer(0));                // jump to the if-false expression
 449             int size = b.size;
 450             startExpr(b, minPrecedence);                          // write the if-true expression
 451             b.add(parserLine, JMP, new Integer(0));               // if true, jump *over* the if-false expression
 452             b.set(size - 1, new Integer(b.size - size + 1));    // now we know where the target of the jump is
 453             consume(COLON);
 454             size = b.size;
 455             startExpr(b, minPrecedence);                          // write the if-false expression
 456             b.set(size - 1, new Integer(b.size - size + 1));    // this is the end; jump to here
 457             break;
 458         }
 459         case COMMA: {
 460             // pop the result of the previous expression, it is ignored
 461             b.add(parserLine,POP);
 462             startExpr(b,-1);
 463             break;
 464         }
 465         default: {
 466             pushBackToken();
 467             return;
 468         }
 469         }
 470
 471         continueExpr(b, minPrecedence);                           // try to continue the expression
 472     }
 473
 474     // parse a set of comma separated function arguments, assume LP has already been consumed
 475     // if swap is true, (because the function is already on the stack) we will SWAP after each argument to keep it on top
 476     private int parseArgs(JSFunction b, int pushdown) throws IOException {
 477         int i = 0;
 478         while(peekToken() != RP) {
 479             i++;
 480             if (peekToken() != COMMA) {
 481                 startExpr(b, NO_COMMA);
 482                 b.add(parserLine, SWAP, new Integer(pushdown));
 483                 if (peekToken() == RP) break;
 484             }
 485             consume(COMMA);
 486         }
 487         consume(RP);
 488         return i;
 489     }
 490
 491     /** Parse a block of statements which must be surrounded by LC..RC. */
 492     void parseBlock(JSFunction b) throws IOException { parseBlock(b, null); }
 493     void parseBlock(JSFunction b, String label) throws IOException {
 494         int saveParserLine = parserLine;
 495         _parseBlock(b, label);
 496         parserLine = saveParserLine;
 497     }
 498     void _parseBlock(JSFunction b, String label) throws IOException {
 499         if (peekToken() == -1) return;
 500         else if (peekToken() != LC) parseStatement(b, null);
 501         else {
 502             consume(LC);
 503             while(peekToken() != RC && peekToken() != -1) parseStatement(b, null);
 504             consume(RC);
 505         }
 506     }
 507
 508     /** Parse a single statement, consuming the RC or SEMI which terminates it. */
 509     void parseStatement(JSFunction b, String label) throws IOException {
 510         int saveParserLine = parserLine;
 511         _parseStatement(b, label);
 512         parserLine = saveParserLine;
 513     }
 514     void _parseStatement(JSFunction b, String label) throws IOException {
 515         int tok = peekToken();
 516         if (tok == -1) return;
 517         switch(tok = getToken()) {
 518
 519         case THROW: case ASSERT: case RETURN: {
 520             if (tok == RETURN && peekToken() == SEMI)
 521                 b.add(parserLine, LITERAL, null);
 522             else
 523                 startExpr(b, -1);
 524             b.add(parserLine, tok);
 525             consume(SEMI);
 526             break;
 527         }
 528         case BREAK: case CONTINUE: {
 529             if (peekToken() == NAME) consume(NAME);
 530             b.add(parserLine, tok, string);
 531             consume(SEMI);
 532             break;
 533         }
 534         case VAR: {
 535             b.add(parserLine, TOPSCOPE);                         // push the current scope
 536             while(true) {
 537                 consume(NAME);
 538                 b.add(parserLine, DECLARE, string);               // declare it
 539                 if (peekToken() == ASSIGN) {                     // if there is an '=' after the variable name
 540                     consume(ASSIGN);
 541                     startExpr(b, NO_COMMA);
 542                     b.add(parserLine, PUT);                      // assign it
 543                     b.add(parserLine, POP);                      // clean the stack
 544                 } else {
 545                     b.add(parserLine, POP);                      // pop the string pushed by declare
 546                 }
 547                 if (peekToken() != COMMA) break;
 548                 consume(COMMA);
 549             }
 550             b.add(parserLine, POP);                              // pop off the topscope
 551             if ((mostRecentlyReadToken != RC || peekToken() == SEMI) && peekToken() != -1 && mostRecentlyReadToken != SEMI) consume(SEMI);
 552             break;
 553         }
 554         case IF: {
 555             consume(LP);
 556             startExpr(b, -1);
 557             consume(RP);
 558
 559             b.add(parserLine, JF, new Integer(0));                    // if false, jump to the else-block
 560             int size = b.size;
 561             parseStatement(b, null);
 562
 563             if (peekToken() == ELSE) {
 564                 consume(ELSE);
 565                 b.add(parserLine, JMP, new Integer(0));               // if we took the true-block, jump over the else-block
 566                 b.set(size - 1, new Integer(b.size - size + 1));
 567                 size = b.size;
 568                 parseStatement(b, null);
 569             }
 570             b.set(size - 1, new Integer(b.size - size + 1));        // regardless of which branch we took, b[size] needs to point here
 571             break;
 572         }
 573         case WHILE: {
 574             consume(LP);
 575             if (label != null) b.add(parserLine, LABEL, label);
 576             b.add(parserLine, LOOP);
 577             int size = b.size;
 578             b.add(parserLine, POP);                                   // discard the first-iteration indicator
 579             startExpr(b, -1);
 580             b.add(parserLine, JT, new Integer(2));                    // if the while() clause is true, jump over the BREAK
 581             b.add(parserLine, BREAK);
 582             consume(RP);
 583             parseStatement(b, null);
 584             b.add(parserLine, CONTINUE);                              // if we fall out of the end, definately continue
 585             b.set(size - 1, new Integer(b.size - size + 1));        // end of the loop
 586             break;
 587         }
 588         case SWITCH: {
 589             consume(LP);
 590             if (label != null) b.add(parserLine, LABEL, label);
 591             b.add(parserLine, LOOP);
 592             int size0 = b.size;
 593             startExpr(b, -1);
 594             consume(RP);
 595             consume(LC);
 596             while(true)
 597                 if (peekToken() == CASE) {                         // we compile CASE statements like a bunch of if..else's
 598                     consume(CASE);
 599                     b.add(parserLine, DUP);                        // duplicate the switch() value; we'll consume one copy
 600                     startExpr(b, -1);
 601                     consume(COLON);
 602                     b.add(parserLine, EQ);                         // check if we should do this case-block
 603                     b.add(parserLine, JF, new Integer(0));         // if not, jump to the next one
 604                     int size = b.size;
 605                     while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) parseStatement(b, null);
 606                     b.set(size - 1, new Integer(1 + b.size - size));
 607                 } else if (peekToken() == DEFAULT) {
 608                     consume(DEFAULT);
 609                     consume(COLON);
 610                     while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) parseStatement(b, null);
 611                 } else if (peekToken() == RC) {
 612                     consume(RC);
 613                     b.add(parserLine, BREAK);                      // break out of the loop if we 'fall through'
 614                     break;
 615                 } else {
 616                     throw pe("expected CASE, DEFAULT, or RC; got " + codeToString[peekToken()]);
 617                 }
 618             b.set(size0 - 1, new Integer(b.size - size0 + 1));      // end of the loop
 619             break;
 620         }
 621
 622         case DO: {
 623             if (label != null) b.add(parserLine, LABEL, label);
 624             b.add(parserLine, LOOP);
 625             int size = b.size;
 626             parseStatement(b, null);
 627             consume(WHILE);
 628             consume(LP);
 629             startExpr(b, -1);
 630             b.add(parserLine, JT, new Integer(2));                  // check the while() clause; jump over the BREAK if true
 631             b.add(parserLine, BREAK);
 632             b.add(parserLine, CONTINUE);
 633             consume(RP);
 634             consume(SEMI);
 635             b.set(size - 1, new Integer(b.size - size + 1));      // end of the loop; write this location to the LOOP instruction
 636             break;
 637         }
 638
 639         case TRY: {
 640             b.add(parserLine, TRY); // try bytecode causes a TryMarker to be pushed
 641             int tryInsn = b.size - 1;
 642             // parse the expression to be TRYed
 643             parseStatement(b, null);
 644             // pop the try  marker. this is pushed when the TRY bytecode is executed
 645             b.add(parserLine, POP);
 646             // jump forward to the end of the catch block, start of the finally block
 647             b.add(parserLine, JMP);
 648             int successJMPInsn = b.size - 1;
 649
 650             if (peekToken() != CATCH && peekToken() != FINALLY)
 651                 throw pe("try without catch or finally");
 652
 653             int catchJMPDistance = -1;
 654             if (peekToken() == CATCH) {
 655                 catchJMPDistance = b.size - tryInsn;
 656                 String exceptionVar;
 657                 getToken();
 658                 consume(LP);
 659                 consume(NAME);
 660                 exceptionVar = string;
 661                 consume(RP);
 662                 b.add(parserLine, TOPSCOPE);                        // the exception is on top of the stack; put it to the chosen name
 663                 b.add(parserLine, SWAP);
 664                 b.add(parserLine, LITERAL,exceptionVar);
 665                 b.add(parserLine, SWAP);
 666                 b.add(parserLine, PUT);
 667                 b.add(parserLine, POP);
 668                 b.add(parserLine, POP);
 669                 parseStatement(b, null);
 670                 // pop the try and catch markers
 671                 b.add(parserLine,POP);
 672                 b.add(parserLine,POP);
 673             }
 674
 675             // jump here if no exception was thrown
 676             b.set(successJMPInsn, new Integer(b.size - successJMPInsn));
 677
 678             int finallyJMPDistance = -1;
 679             if (peekToken() == FINALLY) {
 680                 b.add(parserLine, LITERAL, null); // null FinallyData
 681                 finallyJMPDistance = b.size - tryInsn;
 682                 consume(FINALLY);
 683                 parseStatement(b, null);
 684                 b.add(parserLine,FINALLY_DONE);
 685             }
 686
 687             // setup the TRY arguments
 688             b.set(tryInsn, new int[] { catchJMPDistance, finallyJMPDistance });
 689
 690             break;
 691         }
 692
 693         case FOR: {
 694             consume(LP);
 695
 696             tok = getToken();
 697             boolean hadVar = false;                                      // if it's a for..in, we ignore the VAR
 698             if (tok == VAR) { hadVar = true; tok = getToken(); }
 699             String varName = string;
 700             boolean forIn = peekToken() == IN;                           // determine if this is a for..in loop or not
 701             pushBackToken(tok, varName);
 702
 703             if (forIn) {
 704                 b.add(parserLine, NEWSCOPE);                             // for-loops always create new scopes
 705                 b.add(parserLine, LITERAL, varName);                     // declare the new variable
 706                 b.add(parserLine, DECLARE);
 707
 708                 b.add(parserLine, LOOP);                                 // we actually only add this to ensure that BREAK works
 709                 b.add(parserLine, POP);                                  // discard the first-iteration indicator
 710                 int size = b.size;
 711                 consume(NAME);
 712                 consume(IN);
 713                 startExpr(b, -1);
 714                 b.add(parserLine, PUSHKEYS);                             // push the keys as an array; check the length
 715                 b.add(parserLine, LITERAL, "length");
 716                 b.add(parserLine, GET);
 717                 consume(RP);
 718
 719                 b.add(parserLine, LITERAL, new Integer(1));              // decrement the length
 720                 b.add(parserLine, SUB);
 721                 b.add(parserLine, DUP);
 722                 b.add(parserLine, LITERAL, new Integer(0));              // see if we've exhausted all the elements
 723                 b.add(parserLine, LT);
 724                 b.add(parserLine, JF, new Integer(2));
 725                 b.add(parserLine, BREAK);                                // if we have, then BREAK
 726                 b.add(parserLine, GET_PRESERVE);                         // get the key out of the keys array
 727                 b.add(parserLine, LITERAL, varName);
 728                 b.add(parserLine, PUT);                                  // write it to this[varName]
 729                 parseStatement(b, null);                                 // do some stuff
 730                 b.add(parserLine, CONTINUE);                             // continue if we fall out the bottom
 731
 732                 b.set(size - 1, new Integer(b.size - size + 1));       // BREAK to here
 733                 b.add(parserLine, OLDSCOPE);                             // restore the scope
 734
 735             } else {
 736                 if (hadVar) pushBackToken(VAR, null);                    // yeah, this actually matters
 737                 b.add(parserLine, NEWSCOPE);                             // grab a fresh scope
 738
 739                 parseStatement(b, null);                                 // initializer
 740                 JSFunction e2 =                                    // we need to put the incrementor before the test
 741                     new JSFunction(sourceName, parserLine, null, null);  // so we save the test here
 742                 if (peekToken() != SEMI)
 743                     startExpr(e2, -1);
 744                 else
 745                     e2.add(parserLine, b.LITERAL, Boolean.TRUE);         // handle the for(foo;;foo) case
 746                 consume(SEMI);
 747                 if (label != null) b.add(parserLine, LABEL, label);
 748                 b.add(parserLine, LOOP);
 749                 int size2 = b.size;
 750
 751                 b.add(parserLine, JT, new Integer(0));                   // if we're on the first iteration, jump over the incrementor
 752                 int size = b.size;
 753                 if (peekToken() != RP) {                                 // do the increment thing
 754                     startExpr(b, -1);
 755                     b.add(parserLine, POP);
 756                 }
 757                 b.set(size - 1, new Integer(b.size - size + 1));
 758                 consume(RP);
 759
 760                 b.paste(e2);                                             // ok, *now* test if we're done yet
 761                 b.add(parserLine, JT, new Integer(2));                   // break out if we don't meet the test
 762                 b.add(parserLine, BREAK);
 763                 parseStatement(b, null);
 764                 b.add(parserLine, CONTINUE);                             // if we fall out the bottom, CONTINUE
 765                 b.set(size2 - 1, new Integer(b.size - size2 + 1));     // end of the loop
 766
 767                 b.add(parserLine, OLDSCOPE);                             // get our scope back
 768             }
 769             break;
 770         }
 771
 772         case NAME: {  // either a label or an identifier; this is the one place we're not LL(1)
 773             String possiblyTheLabel = string;
 774             if (peekToken() == COLON) {      // label
 775                 consume(COLON);
 776                 parseStatement(b, possiblyTheLabel);
 777                 break;
 778             } else {                         // expression
 779                 pushBackToken(NAME, possiblyTheLabel);
 780                 startExpr(b, -1);
 781                 b.add(parserLine, POP);
 782                 if ((mostRecentlyReadToken != RC || peekToken() == SEMI) && peekToken() != -1 && mostRecentlyReadToken != SEMI) consume(SEMI);
 783                 break;
 784             }
 785         }
 786
 787         case SEMI: return;                                               // yep, the null statement is valid
 788
 789         case LC: {  // blocks are statements too
 790             pushBackToken();
 791             b.add(parserLine, NEWSCOPE);
 792             parseBlock(b, label);
 793             b.add(parserLine, OLDSCOPE);
 794             break;
 795         }
 796
 797         default: {  // hope that it's an expression
 798             pushBackToken();
 799             startExpr(b, -1);
 800             b.add(parserLine, POP);
 801             if ((mostRecentlyReadToken != RC || peekToken() == SEMI) && peekToken() != -1 && mostRecentlyReadToken != SEMI) consume(SEMI);
 802             break;
 803         }
 804         }
 805     }
 806
 807
 808     // ParserException //////////////////////////////////////////////////////////////////////
 809     private IOException pe(String s) { return new IOException(sourceName + ":" + parserLine + " " + s); }
 810
 811 }
 812