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