src/org/ibex/js/Parser.java

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