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         case LB: {
 164             b.add(parserLine, ARRAY, JS.ZERO);                       // push an array onto the stack
 165             int size0 = b.size;
 166             int i = 0;
 167             if (peekToken() != RB)
 168                 while(true) {                                               // iterate over the initialization values
 169                     int size = b.size;
 170                     b.add(parserLine, LITERAL, JS.N(i++));           // push the index in the array to place it into
 171                     if (peekToken() == COMMA || peekToken() == RB)
 172                         b.add(parserLine, LITERAL, null);                   // for stuff like [1,,2,]
 173                     else
 174                         startExpr(b, NO_COMMA);                             // push the value onto the stack
 175                     b.add(parserLine, PUT);                                 // put it into the array
 176                     b.add(parserLine, POP);                                 // discard the value remaining on the stack
 177                     if (peekToken() == RB) break;
 178                     consume(COMMA);
 179                 }
 180             b.set(size0 - 1, JS.N(i));                               // back at the ARRAY instruction, write the size of the array
 181             consume(RB);
 182             break;
 183         }
 184         case SUB: {  // negative literal (like "3 * -1")
 185             consume(NUMBER);
 186             b.add(parserLine, LITERAL, JS.N(number.doubleValue() * -1));
 187             break;
 188         }
 189         case LP: {  // grouping (not calling)
 190             startExpr(b, -1);
 191             consume(RP);
 192             break;
 193         }
 194         case INC: case DEC: {  // prefix (not postfix)
 195             startExpr(b, precedence[tok]);
 196             int prev = b.size - 1;
 197             if (b.get(prev) == GET && b.getArg(prev) != null)
 198                 b.set(prev, LITERAL, b.getArg(prev));
 199             else if(b.get(prev) == GET)
 200                 b.pop();
 201             else
 202                 throw pe("prefixed increment/decrement can only be performed on a valid assignment target");
 203             b.add(parserLine, GET_PRESERVE, Boolean.TRUE);
 204             b.add(parserLine, LITERAL, JS.N(1));
 205             b.add(parserLine, tok == INC ? ADD : SUB, JS.N(2));
 206             b.add(parserLine, PUT, null);
 207             b.add(parserLine, SWAP, null);
 208             b.add(parserLine, POP, null);
 209             break;
 210         }
 211         case BANG: case BITNOT: case TYPEOF: {
 212             startExpr(b, precedence[tok]);
 213             b.add(parserLine, tok);
 214             break;
 215         }
 216         case LC: { // object constructor
 217             b.add(parserLine, OBJECT, null);                                     // put an object on the stack
 218             if (peekToken() != RC)
 219                 while(true) {
 220                     if (peekToken() != NAME && peekToken() != STRING)
 221                         throw pe("expected NAME or STRING");
 222                     getToken();
 223                     b.add(parserLine, LITERAL, string);                          // grab the key
 224                     consume(COLON);
 225                     startExpr(b, NO_COMMA);                                      // grab the value
 226                     b.add(parserLine, PUT);                                      // put the value into the object
 227                     b.add(parserLine, POP);                                      // discard the remaining value
 228                     if (peekToken() == RC) break;
 229                     consume(COMMA);
 230                     if (peekToken() == RC) break;                                // we permit {,,} -- I'm not sure if ECMA does
 231                 }
 232             consume(RC);
 233             break;
 234         }
 235         case NAME: {
 236             b.add(parserLine, TOPSCOPE);
 237             b.add(parserLine, LITERAL, string);
 238             continueExprAfterAssignable(b,minPrecedence);
 239             break;
 240         }
 241         case FUNCTION: {
 242             consume(LP);
 243             int numArgs = 0;
 244             JSFunction b2 = new JSFunction(sourceName, parserLine, null);
 245             b.add(parserLine, NEWFUNCTION, b2);
 246
 247             // function prelude; arguments array is already on the stack
 248             b2.add(parserLine, TOPSCOPE);
 249             b2.add(parserLine, SWAP);
 250             b2.add(parserLine, DECLARE, "arguments");                     // declare arguments (equivalent to 'var arguments;')
 251             b2.add(parserLine, SWAP);                                     // set this.arguments and leave the value on the stack
 252             b2.add(parserLine, PUT);
 253
 254             while(peekToken() != RP) {                                    // run through the list of argument names
 255                 numArgs++;
 256                 if (peekToken() == NAME) {
 257                     consume(NAME);                                        // a named argument
 258                     String varName = string;
 259
 260                     b2.add(parserLine, DUP);                              // dup the args array
 261                     b2.add(parserLine, GET, JS.N(numArgs - 1));   // retrieve it from the arguments array
 262                     b2.add(parserLine, TOPSCOPE);
 263                     b2.add(parserLine, SWAP);
 264                     b2.add(parserLine, DECLARE, varName);                  // declare the name
 265                     b2.add(parserLine, SWAP);
 266                     b2.add(parserLine, PUT);
 267                     b2.add(parserLine, POP);                               // pop the value
 268                     b2.add(parserLine, POP);                               // pop the scope
 269                 }
 270                 if (peekToken() == RP) break;
 271                 consume(COMMA);
 272             }
 273             consume(RP);
 274
 275             b2.numFormalArgs = numArgs;
 276             b2.add(parserLine, POP);                                      // pop off the arguments array
 277             b2.add(parserLine, POP);                                      // pop off TOPSCOPE
 278
 279            if(peekToken() != LC)
 280                 throw pe("JSFunctions must have a block surrounded by curly brackets");
 281
 282             parseBlock(b2, null);                                   // the function body
 283
 284             b2.add(parserLine, LITERAL, null);                        // in case we "fall out the bottom", return NULL
 285             b2.add(parserLine, RETURN);
 286
 287             break;
 288         }
 289         default: throw pe("expected expression, found " + codeToString[tok] + ", which cannot start an expression");
 290         }
 291
 292         // attempt to continue the expression
 293         continueExpr(b, minPrecedence);
 294     }
 295
 296
 297     /**
 298      *  Assuming that a complete assignable (lvalue) has just been
 299      *  parsed and the object and key are on the stack,
 300      *  <tt>continueExprAfterAssignable</tt> will attempt to parse an
 301      *  expression that modifies the assignable.  This method always
 302      *  decreases the stack depth by exactly one element.
 303      */
 304     private void continueExprAfterAssignable(JSFunction b,int minPrecedence) throws IOException {
 305         int saveParserLine = parserLine;
 306         _continueExprAfterAssignable(b,minPrecedence);
 307         parserLine = saveParserLine;
 308     }
 309     private void _continueExprAfterAssignable(JSFunction b,int minPrecedence) throws IOException {
 310         if (b == null) throw new Error("got null b; this should never happen");
 311         int tok = getToken();
 312         if (minPrecedence != -1 && (precedence[tok] < minPrecedence || (precedence[tok] == minPrecedence && !isRightAssociative[tok])))
 313             // force the default case
 314             tok = -1;
 315         switch(tok) {
 316         case ASSIGN_BITOR: case ASSIGN_BITXOR: case ASSIGN_BITAND: case ASSIGN_LSH: case ASSIGN_RSH: case ASSIGN_URSH:
 317         case ASSIGN_MUL: case ASSIGN_DIV: case ASSIGN_MOD: case ASSIGN_ADD: case ASSIGN_SUB: {
 318             b.add(parserLine, GET_PRESERVE);
 319             startExpr(b,  precedence[tok]);
 320             int size = b.size;
 321             if (tok == ASSIGN_ADD || tok == ASSIGN_SUB) {
 322                 b.add(parserLine, tok);
 323             }
 324             // tok-1 is always s/^ASSIGN_// (0 is BITOR, 1 is ASSIGN_BITOR, etc)
 325             b.add(parserLine, tok - 1, tok-1==ADD ? JS.N(2) : null);
 326             b.add(parserLine, PUT);
 327             b.add(parserLine, SWAP);
 328             b.add(parserLine, POP);
 329             if (tok == ASSIGN_ADD || tok == ASSIGN_SUB) b.set(size, tok, JS.N(b.size - size));
 330             break;
 331         }
 332         case INC: case DEC: { // postfix
 333             b.add(parserLine, GET_PRESERVE, Boolean.TRUE);
 334             b.add(parserLine, LITERAL, JS.N(1));
 335             b.add(parserLine, tok == INC ? ADD : SUB, JS.N(2));
 336             b.add(parserLine, PUT, null);
 337             b.add(parserLine, SWAP, null);
 338             b.add(parserLine, POP, null);
 339             b.add(parserLine, LITERAL, JS.N(1));
 340             b.add(parserLine, tok == INC ? SUB : ADD, null);   // undo what we just did, since this is postfix
 341             break;
 342         }
 343         case ASSIGN: {
 344             startExpr(b, precedence[tok]);
 345             b.add(parserLine, PUT);
 346             b.add(parserLine, SWAP);
 347             b.add(parserLine, POP);
 348             break;
 349         }
 350         case LP: {
 351
 352             // Method calls are implemented by doing a GET_PRESERVE
 353             // first.  If the object supports method calls, it will
 354             // return JS.METHOD
 355             int n = parseArgs(b, 2);
 356             b.add(parserLine, GET_PRESERVE);
 357             b.add(parserLine, CALLMETHOD, JS.N(n));
 358             break;
 359         }
 360         default: {
 361             pushBackToken();
 362             if(b.get(b.size-1) == LITERAL && b.getArg(b.size-1) != null)
 363                 b.set(b.size-1,GET,b.getArg(b.size-1));
 364             else
 365                 b.add(parserLine, GET);
 366             return;
 367         }
 368         }
 369     }
 370
 371
 372     /**
 373      *  Assuming that a complete expression has just been parsed,
 374      *  <tt>continueExpr</tt> will attempt to extend this expression by
 375      *  parsing additional tokens and appending additional bytecodes.
 376      *
 377      *  No operators with precedence less than <tt>minPrecedence</tt>
 378      *  will be parsed.
 379      *
 380      *  If any bytecodes are appended, they will not alter the stack
 381      *  depth.
 382      */
 383     private void continueExpr(JSFunction b, int minPrecedence) throws IOException {
 384         int saveParserLine = parserLine;
 385         _continueExpr(b, minPrecedence);
 386         parserLine = saveParserLine;
 387     }
 388     private void _continueExpr(JSFunction b, int minPrecedence) throws IOException {
 389         if (b == null) throw new Error("got null b; this should never happen");
 390         int tok = getToken();
 391         if (tok == -1) return;
 392         if (minPrecedence != -1 && (precedence[tok] < minPrecedence || (precedence[tok] == minPrecedence && !isRightAssociative[tok]))) {
 393             pushBackToken();
 394             return;
 395         }
 396
 397         switch (tok) {
 398         case LP: {  // invocation (not grouping)
 399             int n = parseArgs(b, 1);
 400             b.add(parserLine, CALL, JS.N(n));
 401             break;
 402         }
 403         case BITOR: case BITXOR: case BITAND: case SHEQ: case SHNE: case LSH:
 404         case RSH: case URSH: case MUL: case DIV: case MOD:
 405         case GT: case GE: case EQ: case NE: case LT: case LE: case SUB: {
 406             startExpr(b, precedence[tok]);
 407             b.add(parserLine, tok);
 408             break;
 409         }
 410         case ADD: {
 411             int count=1;
 412             int nextTok;
 413             do {
 414                 startExpr(b,precedence[tok]);
 415                 count++;
 416                 nextTok = getToken();
 417             } while(nextTok == tok);
 418             pushBackToken();
 419             b.add(parserLine, tok, JS.N(count));
 420             break;
 421         }
 422         case OR: case AND: {
 423             b.add(parserLine, tok == AND ? b.JF : b.JT, JS.ZERO);       // test to see if we can short-circuit
 424             int size = b.size;
 425             startExpr(b, precedence[tok]);                                     // otherwise check the second value
 426             b.add(parserLine, JMP, JS.N(2));                            // leave the second value on the stack and jump to the end
 427             b.add(parserLine, LITERAL, tok == AND ?
 428                   JS.B(false) : JS.B(true));                     // target of the short-circuit jump is here
 429             b.set(size - 1, JS.N(b.size - size));                     // write the target of the short-circuit jump
 430             break;
 431         }
 432         case DOT: {
 433             // support foo..bar syntax for foo[""].bar
 434             if (peekToken() == DOT) {
 435                 string = "";
 436             } else {
 437                 consume(NAME);
 438             }
 439             b.add(parserLine, LITERAL, string);
 440             continueExprAfterAssignable(b,minPrecedence);
 441             break;
 442         }
 443         case LB: { // subscripting (not array constructor)
 444             startExpr(b, -1);
 445             consume(RB);
 446             continueExprAfterAssignable(b,minPrecedence);
 447             break;
 448         }
 449         case HOOK: {
 450             b.add(parserLine, JF, JS.ZERO);                // jump to the if-false expression
 451             int size = b.size;
 452             startExpr(b, minPrecedence);                          // write the if-true expression
 453             b.add(parserLine, JMP, JS.ZERO);               // if true, jump *over* the if-false expression
 454             b.set(size - 1, JS.N(b.size - size + 1));    // now we know where the target of the jump is
 455             consume(COLON);
 456             size = b.size;
 457             startExpr(b, minPrecedence);                          // write the if-false expression
 458             b.set(size - 1, JS.N(b.size - size + 1));    // this is the end; jump to here
 459             break;
 460         }
 461         case COMMA: {
 462             // pop the result of the previous expression, it is ignored
 463             b.add(parserLine,POP);
 464             startExpr(b,-1);
 465             break;
 466         }
 467         default: {
 468             pushBackToken();
 469             return;
 470         }
 471         }
 472
 473         continueExpr(b, minPrecedence);                           // try to continue the expression
 474     }
 475
 476     // parse a set of comma separated function arguments, assume LP has already been consumed
 477     // if swap is true, (because the function is already on the stack) we will SWAP after each argument to keep it on top
 478     private int parseArgs(JSFunction b, int pushdown) throws IOException {
 479         int i = 0;
 480         while(peekToken() != RP) {
 481             i++;
 482             if (peekToken() != COMMA) {
 483                 startExpr(b, NO_COMMA);
 484                 b.add(parserLine, SWAP, JS.N(pushdown));
 485                 if (peekToken() == RP) break;
 486             }
 487             consume(COMMA);
 488         }
 489         consume(RP);
 490         return i;
 491     }
 492
 493     /** Parse a block of statements which must be surrounded by LC..RC. */
 494     void parseBlock(JSFunction b) throws IOException { parseBlock(b, null); }
 495     void parseBlock(JSFunction b, String label) throws IOException {
 496         int saveParserLine = parserLine;
 497         _parseBlock(b, label);
 498         parserLine = saveParserLine;
 499     }
 500     void _parseBlock(JSFunction b, String label) throws IOException {
 501         if (peekToken() == -1) return;
 502         else if (peekToken() != LC) parseStatement(b, null);
 503         else {
 504             consume(LC);
 505             while(peekToken() != RC && peekToken() != -1) parseStatement(b, null);
 506             consume(RC);
 507         }
 508     }
 509
 510     /** Parse a single statement, consuming the RC or SEMI which terminates it. */
 511     void parseStatement(JSFunction b, String label) throws IOException {
 512         int saveParserLine = parserLine;
 513         _parseStatement(b, label);
 514         parserLine = saveParserLine;
 515     }
 516     void _parseStatement(JSFunction b, String label) throws IOException {
 517         int tok = peekToken();
 518         if (tok == -1) return;
 519         switch(tok = getToken()) {
 520
 521         case THROW: case ASSERT: case RETURN: {
 522             if (tok == RETURN && peekToken() == SEMI)
 523                 b.add(parserLine, LITERAL, null);
 524             else
 525                 startExpr(b, -1);
 526             b.add(parserLine, tok);
 527             consume(SEMI);
 528             break;
 529         }
 530         case BREAK: case CONTINUE: {
 531             if (peekToken() == NAME) consume(NAME);
 532             b.add(parserLine, tok, string);
 533             consume(SEMI);
 534             break;
 535         }
 536         case VAR: {
 537             b.add(parserLine, TOPSCOPE);                         // push the current scope
 538             while(true) {
 539                 consume(NAME);
 540                 b.add(parserLine, DECLARE, string);               // declare it
 541                 if (peekToken() == ASSIGN) {                     // if there is an '=' after the variable name
 542                     consume(ASSIGN);
 543                     startExpr(b, NO_COMMA);
 544                     b.add(parserLine, PUT);                      // assign it
 545                     b.add(parserLine, POP);                      // clean the stack
 546                 } else {
 547                     b.add(parserLine, POP);                      // pop the string pushed by declare
 548                 }
 549                 if (peekToken() != COMMA) break;
 550                 consume(COMMA);
 551             }
 552             b.add(parserLine, POP);                              // pop off the topscope
 553             if ((mostRecentlyReadToken != RC || peekToken() == SEMI) && peekToken() != -1 && mostRecentlyReadToken != SEMI) consume(SEMI);
 554             break;
 555         }
 556         case IF: {
 557             consume(LP);
 558             startExpr(b, -1);
 559             consume(RP);
 560
 561             b.add(parserLine, JF, JS.ZERO);                    // if false, jump to the else-block
 562             int size = b.size;
 563             parseStatement(b, null);
 564
 565             if (peekToken() == ELSE) {
 566                 consume(ELSE);
 567                 b.add(parserLine, JMP, JS.ZERO);               // if we took the true-block, jump over the else-block
 568                 b.set(size - 1, JS.N(b.size - size + 1));
 569                 size = b.size;
 570                 parseStatement(b, null);
 571             }
 572             b.set(size - 1, JS.N(b.size - size + 1));        // regardless of which branch we took, b[size] needs to point here
 573             break;
 574         }
 575         case WHILE: {
 576             consume(LP);
 577             if (label != null) b.add(parserLine, LABEL, label);
 578             b.add(parserLine, LOOP);
 579             int size = b.size;
 580             b.add(parserLine, POP);                                   // discard the first-iteration indicator
 581             startExpr(b, -1);
 582             b.add(parserLine, JT, JS.N(2));                    // if the while() clause is true, jump over the BREAK
 583             b.add(parserLine, BREAK);
 584             consume(RP);
 585             parseStatement(b, null);
 586             b.add(parserLine, CONTINUE);                              // if we fall out of the end, definately continue
 587             b.set(size - 1, JS.N(b.size - size + 1));        // end of the loop
 588             break;
 589         }
 590         case SWITCH: {
 591             consume(LP);
 592             if (label != null) b.add(parserLine, LABEL, label);
 593             b.add(parserLine, LOOP);
 594             int size0 = b.size;
 595             startExpr(b, -1);
 596             consume(RP);
 597             consume(LC);
 598             while(true)
 599                 if (peekToken() == CASE) {                         // we compile CASE statements like a bunch of if..else's
 600                     consume(CASE);
 601                     b.add(parserLine, DUP);                        // duplicate the switch() value; we'll consume one copy
 602                     startExpr(b, -1);
 603                     consume(COLON);
 604                     b.add(parserLine, EQ);                         // check if we should do this case-block
 605                     b.add(parserLine, JF, JS.ZERO);         // if not, jump to the next one
 606                     int size = b.size;
 607                     while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) parseStatement(b, null);
 608                     b.set(size - 1, JS.N(1 + b.size - size));
 609                 } else if (peekToken() == DEFAULT) {
 610                     consume(DEFAULT);
 611                     consume(COLON);
 612                     while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) parseStatement(b, null);
 613                 } else if (peekToken() == RC) {
 614                     consume(RC);
 615                     b.add(parserLine, BREAK);                      // break out of the loop if we 'fall through'
 616                     break;
 617                 } else {
 618                     throw pe("expected CASE, DEFAULT, or RC; got " + codeToString[peekToken()]);
 619                 }
 620             b.set(size0 - 1, JS.N(b.size - size0 + 1));      // end of the loop
 621             break;
 622         }
 623
 624         case DO: {
 625             if (label != null) b.add(parserLine, LABEL, label);
 626             b.add(parserLine, LOOP);
 627             int size = b.size;
 628             parseStatement(b, null);
 629             consume(WHILE);
 630             consume(LP);
 631             startExpr(b, -1);
 632             b.add(parserLine, JT, JS.N(2));                  // check the while() clause; jump over the BREAK if true
 633             b.add(parserLine, BREAK);
 634             b.add(parserLine, CONTINUE);
 635             consume(RP);
 636             consume(SEMI);
 637             b.set(size - 1, JS.N(b.size - size + 1));      // end of the loop; write this location to the LOOP instruction
 638             break;
 639         }
 640
 641         case TRY: {
 642             b.add(parserLine, TRY); // try bytecode causes a TryMarker to be pushed
 643             int tryInsn = b.size - 1;
 644             // parse the expression to be TRYed
 645             parseStatement(b, null);
 646             // pop the try  marker. this is pushed when the TRY bytecode is executed
 647             b.add(parserLine, POP);
 648             // jump forward to the end of the catch block, start of the finally block
 649             b.add(parserLine, JMP);
 650             int successJMPInsn = b.size - 1;
 651
 652             if (peekToken() != CATCH && peekToken() != FINALLY)
 653                 throw pe("try without catch or finally");
 654
 655             int catchJMPDistance = -1;
 656             if (peekToken() == CATCH) {
 657                 catchJMPDistance = b.size - tryInsn;
 658                 String exceptionVar;
 659                 getToken();
 660                 consume(LP);
 661                 consume(NAME);
 662                 exceptionVar = string;
 663                 consume(RP);
 664                 b.add(parserLine, TOPSCOPE);                        // the exception is on top of the stack; put it to the chosen name
 665                 b.add(parserLine, SWAP);
 666                 b.add(parserLine, LITERAL,exceptionVar);
 667                 b.add(parserLine, SWAP);
 668                 b.add(parserLine, PUT);
 669                 b.add(parserLine, POP);
 670                 b.add(parserLine, POP);
 671                 parseStatement(b, null);
 672                 // pop the try and catch markers
 673                 b.add(parserLine,POP);
 674                 b.add(parserLine,POP);
 675             }
 676
 677             // jump here if no exception was thrown
 678             b.set(successJMPInsn, JS.N(b.size - successJMPInsn));
 679
 680             int finallyJMPDistance = -1;
 681             if (peekToken() == FINALLY) {
 682                 b.add(parserLine, LITERAL, null); // null FinallyData
 683                 finallyJMPDistance = b.size - tryInsn;
 684                 consume(FINALLY);
 685                 parseStatement(b, null);
 686                 b.add(parserLine,FINALLY_DONE);
 687             }
 688
 689             // setup the TRY arguments
 690             b.set(tryInsn, new int[] { catchJMPDistance, finallyJMPDistance });
 691
 692             break;
 693         }
 694
 695         case FOR: {
 696             consume(LP);
 697
 698             tok = getToken();
 699             boolean hadVar = false;                                      // if it's a for..in, we ignore the VAR
 700             if (tok == VAR) { hadVar = true; tok = getToken(); }
 701             String varName = string;
 702             boolean forIn = peekToken() == IN;                           // determine if this is a for..in loop or not
 703             pushBackToken(tok, varName);
 704
 705             if (forIn) {
 706                 b.add(parserLine, NEWSCOPE);                             // for-loops always create new scopes
 707                 b.add(parserLine, LITERAL, varName);                     // declare the new variable
 708                 b.add(parserLine, DECLARE);
 709
 710                 b.add(parserLine, LOOP);                                 // we actually only add this to ensure that BREAK works
 711                 b.add(parserLine, POP);                                  // discard the first-iteration indicator
 712                 int size = b.size;
 713                 consume(NAME);
 714                 consume(IN);
 715                 startExpr(b, -1);
 716                 b.add(parserLine, PUSHKEYS);                             // push the keys as an array; check the length
 717                 b.add(parserLine, LITERAL, "length");
 718                 b.add(parserLine, GET);
 719                 consume(RP);
 720
 721                 b.add(parserLine, LITERAL, JS.N(1));              // decrement the length
 722                 b.add(parserLine, SUB);
 723                 b.add(parserLine, DUP);
 724                 b.add(parserLine, LITERAL, JS.ZERO);              // see if we've exhausted all the elements
 725                 b.add(parserLine, LT);
 726                 b.add(parserLine, JF, JS.N(2));
 727                 b.add(parserLine, BREAK);                                // if we have, then BREAK
 728                 b.add(parserLine, GET_PRESERVE);                         // get the key out of the keys array
 729                 b.add(parserLine, LITERAL, varName);
 730                 b.add(parserLine, PUT);                                  // write it to this[varName]
 731                 parseStatement(b, null);                                 // do some stuff
 732                 b.add(parserLine, CONTINUE);                             // continue if we fall out the bottom
 733
 734                 b.set(size - 1, JS.N(b.size - size + 1));       // BREAK to here
 735                 b.add(parserLine, OLDSCOPE);                             // restore the scope
 736
 737             } else {
 738                 if (hadVar) pushBackToken(VAR, null);                    // yeah, this actually matters
 739                 b.add(parserLine, NEWSCOPE);                             // grab a fresh scope
 740
 741                 parseStatement(b, null);                                 // initializer
 742                 JSFunction e2 =                                    // we need to put the incrementor before the test
 743                     new JSFunction(sourceName, parserLine, null);  // so we save the test here
 744                 if (peekToken() != SEMI)
 745                     startExpr(e2, -1);
 746                 else
 747                     e2.add(parserLine, b.LITERAL, Boolean.TRUE);         // handle the for(foo;;foo) case
 748                 consume(SEMI);
 749                 if (label != null) b.add(parserLine, LABEL, label);
 750                 b.add(parserLine, LOOP);
 751                 int size2 = b.size;
 752
 753                 b.add(parserLine, JT, JS.ZERO);                   // if we're on the first iteration, jump over the incrementor
 754                 int size = b.size;
 755                 if (peekToken() != RP) {                                 // do the increment thing
 756                     startExpr(b, -1);
 757                     b.add(parserLine, POP);
 758                 }
 759                 b.set(size - 1, JS.N(b.size - size + 1));
 760                 consume(RP);
 761
 762                 b.paste(e2);                                             // ok, *now* test if we're done yet
 763                 b.add(parserLine, JT, JS.N(2));                   // break out if we don't meet the test
 764                 b.add(parserLine, BREAK);
 765                 parseStatement(b, null);
 766                 b.add(parserLine, CONTINUE);                             // if we fall out the bottom, CONTINUE
 767                 b.set(size2 - 1, JS.N(b.size - size2 + 1));     // end of the loop
 768
 769                 b.add(parserLine, OLDSCOPE);                             // get our scope back
 770             }
 771             break;
 772         }
 773
 774         case NAME: {  // either a label or an identifier; this is the one place we're not LL(1)
 775             String possiblyTheLabel = string;
 776             if (peekToken() == COLON) {      // label
 777                 consume(COLON);
 778                 parseStatement(b, possiblyTheLabel);
 779                 break;
 780             } else {                         // expression
 781                 pushBackToken(NAME, possiblyTheLabel);
 782                 startExpr(b, -1);
 783                 b.add(parserLine, POP);
 784                 if ((mostRecentlyReadToken != RC || peekToken() == SEMI) && peekToken() != -1 && mostRecentlyReadToken != SEMI) consume(SEMI);
 785                 break;
 786             }
 787         }
 788
 789         case SEMI: return;                                               // yep, the null statement is valid
 790
 791         case LC: {  // blocks are statements too
 792             pushBackToken();
 793             b.add(parserLine, NEWSCOPE);
 794             parseBlock(b, label);
 795             b.add(parserLine, OLDSCOPE);
 796             break;
 797         }
 798
 799         default: {  // hope that it's an expression
 800             pushBackToken();
 801             startExpr(b, -1);
 802             b.add(parserLine, POP);
 803             if ((mostRecentlyReadToken != RC || peekToken() == SEMI) && peekToken() != -1 && mostRecentlyReadToken != SEMI) consume(SEMI);
 804             break;
 805         }
 806         }
 807     }
 808
 809
 810     // ParserException //////////////////////////////////////////////////////////////////////
 811     private IOException pe(String s) { return new IOException(sourceName + ":" + parserLine + " " + s); }
 812
 813 }
 814