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