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