js/narcissus/jsparse.js

   1 /* vim: set sw=4 ts=8 et tw=78: */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is the Narcissus JavaScript engine.
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Brendan Eich <brendan@mozilla.org>.
  19  * Portions created by the Initial Developer are Copyright (C) 2004
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *
  24  * Alternatively, the contents of this file may be used under the terms of
  25  * either the GNU General Public License Version 2 or later (the "GPL"), or
  26  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27  * in which case the provisions of the GPL or the LGPL are applicable instead
  28  * of those above. If you wish to allow use of your version of this file only
  29  * under the terms of either the GPL or the LGPL, and not to allow others to
  30  * use your version of this file under the terms of the MPL, indicate your
  31  * decision by deleting the provisions above and replace them with the notice
  32  * and other provisions required by the GPL or the LGPL. If you do not delete
  33  * the provisions above, a recipient may use your version of this file under
  34  * the terms of any one of the MPL, the GPL or the LGPL.
  35  *
  36  * ***** END LICENSE BLOCK ***** */
  37
  38 /*
  39  * Narcissus - JS implemented in JS.
  40  *
  41  * Lexical scanner and parser.
  42  */
  43
  44 // Build a regexp that recognizes operators and punctuators (except newline).
  45 var opRegExpSrc = "^";
  46 for (i in opTypeNames) {
  47     if (i == '\n')
  48         continue;
  49     if (opRegExpSrc != "^")
  50         opRegExpSrc += "|^";
  51     opRegExpSrc += i.replace(/[?|^&(){}\[\]+\-*\/\.]/g, "\\$&");
  52 }
  53 var opRegExp = new RegExp(opRegExpSrc);
  54
  55 // A regexp to match floating point literals (but not integer literals).
  56 var fpRegExp = /^\d+\.\d*(?:[eE][-+]?\d+)?|^\d+(?:\.\d*)?[eE][-+]?\d+|^\.\d+(?:[eE][-+]?\d+)?/;
  57
  58 // A regexp to match regexp literals.
  59 var reRegExp = /^\/((?:\\.|\[(?:\\.|[^\]])*\]|[^\/])+)\/([gimy]*)/;
  60
  61 function Tokenizer(s, f, l) {
  62     this.cursor = 0;
  63     this.source = String(s);
  64     this.tokens = [];
  65     this.tokenIndex = 0;
  66     this.lookahead = 0;
  67     this.scanNewlines = false;
  68     this.scanOperand = true;
  69     this.filename = f || "";
  70     this.lineno = l || 1;
  71 }
  72
  73 Tokenizer.prototype = {
  74     get input() {
  75         return this.source.substring(this.cursor);
  76     },
  77
  78     get done() {
  79         return this.peek() == END;
  80     },
  81
  82     get token() {
  83         return this.tokens[this.tokenIndex];
  84     },
  85
  86     match: function (tt) {
  87         return this.get() == tt || this.unget();
  88     },
  89
  90     mustMatch: function (tt) {
  91         if (!this.match(tt))
  92             throw this.newSyntaxError("Missing " + tokens[tt].toLowerCase());
  93         return this.token;
  94     },
  95
  96     peek: function () {
  97         var tt, next;
  98         if (this.lookahead) {
  99             next = this.tokens[(this.tokenIndex + this.lookahead) & 3];
 100             if (this.scanNewlines && next.lineno != this.lineno)
 101                 tt = NEWLINE;
 102             else
 103                 tt = next.type;
 104         } else {
 105             tt = this.get();
 106             this.unget();
 107         }
 108         return tt;
 109     },
 110
 111     peekOnSameLine: function () {
 112         this.scanNewlines = true;
 113         var tt = this.peek();
 114         this.scanNewlines = false;
 115         return tt;
 116     },
 117
 118     get: function () {
 119         var token;
 120         while (this.lookahead) {
 121             --this.lookahead;
 122             this.tokenIndex = (this.tokenIndex + 1) & 3;
 123             token = this.tokens[this.tokenIndex];
 124             if (token.type != NEWLINE || this.scanNewlines)
 125                 return token.type;
 126         }
 127
 128         for (;;) {
 129             var input = this.input;
 130             var match = (this.scanNewlines ? /^[ \t]+/ : /^\s+/)(input);
 131             if (match) {
 132                 var spaces = match[0];
 133                 this.cursor += spaces.length;
 134                 var newlines = spaces.match(/\n/g);
 135                 if (newlines)
 136                     this.lineno += newlines.length;
 137                 input = this.input;
 138             }
 139
 140             if (!(match = /^\/(?:\*(?:.|\n)*?\*\/|\/.*)/(input)))
 141                 break;
 142             var comment = match[0];
 143             this.cursor += comment.length;
 144             newlines = comment.match(/\n/g);
 145             if (newlines)
 146                 this.lineno += newlines.length
 147         }
 148
 149         this.tokenIndex = (this.tokenIndex + 1) & 3;
 150         token = this.tokens[this.tokenIndex];
 151         if (!token)
 152             this.tokens[this.tokenIndex] = token = {};
 153
 154         if (!input)
 155             return token.type = END;
 156
 157         if ((match = fpRegExp(input))) {
 158             token.type = NUMBER;
 159             token.value = parseFloat(match[0]);
 160         } else if ((match = /^0[xX][\da-fA-F]+|^0[0-7]*|^\d+/(input))) {
 161             token.type = NUMBER;
 162             token.value = parseInt(match[0]);
 163         } else if ((match = /^[$_\w]+/(input))) {       // FIXME no ES3 unicode
 164             var id = match[0];
 165             token.type = keywords[id] || IDENTIFIER;
 166             token.value = id;
 167         } else if ((match = /^"(?:\\.|[^"])*"|^'(?:\\.|[^'])*'/(input))) { //"){
 168             token.type = STRING;
 169             token.value = eval(match[0]);
 170         } else if (this.scanOperand && (match = reRegExp(input))) {
 171             token.type = REGEXP;
 172             token.value = new RegExp(match[1], match[2]);
 173         } else if ((match = opRegExp(input))) {
 174             var op = match[0];
 175             if (assignOps[op] && input[op.length] == '=') {
 176                 token.type = ASSIGN;
 177                 token.assignOp = GLOBAL[opTypeNames[op]];
 178                 match[0] += '=';
 179             } else {
 180                 token.type = GLOBAL[opTypeNames[op]];
 181                 if (this.scanOperand &&
 182                     (token.type == PLUS || token.type == MINUS)) {
 183                     token.type += UNARY_PLUS - PLUS;
 184                 }
 185                 token.assignOp = null;
 186             }
 187             token.value = op;
 188         } else if (this.scanNewlines && (match = /^\n/(input))) {
 189             token.type = NEWLINE;
 190         } else {
 191             throw this.newSyntaxError("Illegal token");
 192         }
 193
 194         token.start = this.cursor;
 195         this.cursor += match[0].length;
 196         token.end = this.cursor;
 197         token.lineno = this.lineno;
 198         return token.type;
 199     },
 200
 201     unget: function () {
 202         if (++this.lookahead == 4) throw "PANIC: too much lookahead!";
 203         this.tokenIndex = (this.tokenIndex - 1) & 3;
 204     },
 205
 206     newSyntaxError: function (m) {
 207         var e = new SyntaxError(m, this.filename, this.lineno);
 208         e.source = this.source;
 209         e.cursor = this.cursor;
 210         return e;
 211     }
 212 };
 213
 214 function CompilerContext(inFunction) {
 215     this.inFunction = inFunction;
 216     this.stmtStack = [];
 217     this.funDecls = [];
 218     this.varDecls = [];
 219 }
 220
 221 var CCp = CompilerContext.prototype;
 222 CCp.bracketLevel = CCp.curlyLevel = CCp.parenLevel = CCp.hookLevel = 0;
 223 CCp.ecmaStrictMode = CCp.inForLoopInit = false;
 224
 225 function Script(t, x) {
 226     var n = Statements(t, x);
 227     n.type = SCRIPT;
 228     n.funDecls = x.funDecls;
 229     n.varDecls = x.varDecls;
 230     return n;
 231 }
 232
 233 // Node extends Array, which we extend slightly with a top-of-stack method.
 234 Array.prototype.__defineProperty__(
 235     'top',
 236     function () {
 237         return this.length && this[this.length-1];
 238     },
 239     false, false, true
 240 );
 241
 242 function Node(t, type) {
 243     var token = t.token;
 244     if (token) {
 245         this.type = type || token.type;
 246         this.value = token.value;
 247         this.lineno = token.lineno;
 248         this.start = token.start;
 249         this.end = token.end;
 250     } else {
 251         this.type = type;
 252         this.lineno = t.lineno;
 253     }
 254     this.tokenizer = t;
 255
 256     for (var i = 2; i < arguments.length; i++)
 257         this.push(arguments[i]);
 258 }
 259
 260 var Np = Node.prototype = new Array;
 261 Np.constructor = Node;
 262 Np.toSource = Object.prototype.toSource;
 263
 264 // Always use push to add operands to an expression, to update start and end.
 265 Np.push = function (kid) {
 266     if (kid.start < this.start)
 267         this.start = kid.start;
 268     if (this.end < kid.end)
 269         this.end = kid.end;
 270     return Array.prototype.push.call(this, kid);
 271 }
 272
 273 Node.indentLevel = 0;
 274
 275 function tokenstr(tt) {
 276     var t = tokens[tt];
 277     return /^\W/.test(t) ? opTypeNames[t] : t.toUpperCase();
 278 }
 279
 280 Np.toString = function () {
 281     var a = [];
 282     for (var i in this) {
 283         if (this.hasOwnProperty(i) && i != 'type' && i != 'target')
 284             a.push({id: i, value: this[i]});
 285     }
 286     a.sort(function (a,b) { return (a.id < b.id) ? -1 : 1; });
 287     const INDENTATION = "    ";
 288     var n = ++Node.indentLevel;
 289     var s = "{\n" + INDENTATION.repeat(n) + "type: " + tokenstr(this.type);
 290     for (i = 0; i < a.length; i++)
 291         s += ",\n" + INDENTATION.repeat(n) + a[i].id + ": " + a[i].value;
 292     n = --Node.indentLevel;
 293     s += "\n" + INDENTATION.repeat(n) + "}";
 294     return s;
 295 }
 296
 297 Np.getSource = function () {
 298     return this.tokenizer.source.slice(this.start, this.end);
 299 };
 300
 301 Np.__defineGetter__('filename',
 302                     function () { return this.tokenizer.filename; });
 303
 304 String.prototype.__defineProperty__(
 305     'repeat',
 306     function (n) {
 307         var s = "", t = this + s;
 308         while (--n >= 0)
 309             s += t;
 310         return s;
 311     },
 312     false, false, true
 313 );
 314
 315 // Statement stack and nested statement handler.
 316 function nest(t, x, node, func, end) {
 317     x.stmtStack.push(node);
 318     var n = func(t, x);
 319     x.stmtStack.pop();
 320     end && t.mustMatch(end);
 321     return n;
 322 }
 323
 324 function Statements(t, x) {
 325     var n = new Node(t, BLOCK);
 326     x.stmtStack.push(n);
 327     while (!t.done && t.peek() != RIGHT_CURLY)
 328         n.push(Statement(t, x));
 329     x.stmtStack.pop();
 330     return n;
 331 }
 332
 333 function Block(t, x) {
 334     t.mustMatch(LEFT_CURLY);
 335     var n = Statements(t, x);
 336     t.mustMatch(RIGHT_CURLY);
 337     return n;
 338 }
 339
 340 const DECLARED_FORM = 0, EXPRESSED_FORM = 1, STATEMENT_FORM = 2;
 341
 342 function Statement(t, x) {
 343     var i, label, n, n2, ss, tt = t.get();
 344
 345     // Cases for statements ending in a right curly return early, avoiding the
 346     // common semicolon insertion magic after this switch.
 347     switch (tt) {
 348       case FUNCTION:
 349         return FunctionDefinition(t, x, true,
 350                                   (x.stmtStack.length > 1)
 351                                   ? STATEMENT_FORM
 352                                   : DECLARED_FORM);
 353
 354       case LEFT_CURLY:
 355         n = Statements(t, x);
 356         t.mustMatch(RIGHT_CURLY);
 357         return n;
 358
 359       case IF:
 360         n = new Node(t);
 361         n.condition = ParenExpression(t, x);
 362         x.stmtStack.push(n);
 363         n.thenPart = Statement(t, x);
 364         n.elsePart = t.match(ELSE) ? Statement(t, x) : null;
 365         x.stmtStack.pop();
 366         return n;
 367
 368       case SWITCH:
 369         n = new Node(t);
 370         t.mustMatch(LEFT_PAREN);
 371         n.discriminant = Expression(t, x);
 372         t.mustMatch(RIGHT_PAREN);
 373         n.cases = [];
 374         n.defaultIndex = -1;
 375         x.stmtStack.push(n);
 376         t.mustMatch(LEFT_CURLY);
 377         while ((tt = t.get()) != RIGHT_CURLY) {
 378             switch (tt) {
 379               case DEFAULT:
 380                 if (n.defaultIndex >= 0)
 381                     throw t.newSyntaxError("More than one switch default");
 382                 // FALL THROUGH
 383               case CASE:
 384                 n2 = new Node(t);
 385                 if (tt == DEFAULT)
 386                     n.defaultIndex = n.cases.length;
 387                 else
 388                     n2.caseLabel = Expression(t, x, COLON);
 389                 break;
 390               default:
 391                 throw t.newSyntaxError("Invalid switch case");
 392             }
 393             t.mustMatch(COLON);
 394             n2.statements = new Node(t, BLOCK);
 395             while ((tt=t.peek()) != CASE && tt != DEFAULT && tt != RIGHT_CURLY)
 396                 n2.statements.push(Statement(t, x));
 397             n.cases.push(n2);
 398         }
 399         x.stmtStack.pop();
 400         return n;
 401
 402       case FOR:
 403         n = new Node(t);
 404         n.isLoop = true;
 405         t.mustMatch(LEFT_PAREN);
 406         if ((tt = t.peek()) != SEMICOLON) {
 407             x.inForLoopInit = true;
 408             if (tt == VAR || tt == CONST) {
 409                 t.get();
 410                 n2 = Variables(t, x);
 411             } else {
 412                 n2 = Expression(t, x);
 413             }
 414             x.inForLoopInit = false;
 415         }
 416         if (n2 && t.match(IN)) {
 417             n.type = FOR_IN;
 418             if (n2.type == VAR) {
 419                 if (n2.length != 1) {
 420                     throw new SyntaxError("Invalid for..in left-hand side",
 421                                           t.filename, n2.lineno);
 422                 }
 423
 424                 // NB: n2[0].type == IDENTIFIER and n2[0].value == n2[0].name.
 425                 n.iterator = n2[0];
 426                 n.varDecl = n2;
 427             } else {
 428                 n.iterator = n2;
 429                 n.varDecl = null;
 430             }
 431             n.object = Expression(t, x);
 432         } else {
 433             n.setup = n2 || null;
 434             t.mustMatch(SEMICOLON);
 435             n.condition = (t.peek() == SEMICOLON) ? null : Expression(t, x);
 436             t.mustMatch(SEMICOLON);
 437             n.update = (t.peek() == RIGHT_PAREN) ? null : Expression(t, x);
 438         }
 439         t.mustMatch(RIGHT_PAREN);
 440         n.body = nest(t, x, n, Statement);
 441         return n;
 442
 443       case WHILE:
 444         n = new Node(t);
 445         n.isLoop = true;
 446         n.condition = ParenExpression(t, x);
 447         n.body = nest(t, x, n, Statement);
 448         return n;
 449
 450       case DO:
 451         n = new Node(t);
 452         n.isLoop = true;
 453         n.body = nest(t, x, n, Statement, WHILE);
 454         n.condition = ParenExpression(t, x);
 455         if (!x.ecmaStrictMode) {
 456             // <script language="JavaScript"> (without version hints) may need
 457             // automatic semicolon insertion without a newline after do-while.
 458             // See http://bugzilla.mozilla.org/show_bug.cgi?id=238945.
 459             t.match(SEMICOLON);
 460             return n;
 461         }
 462         break;
 463
 464       case BREAK:
 465       case CONTINUE:
 466         n = new Node(t);
 467         if (t.peekOnSameLine() == IDENTIFIER) {
 468             t.get();
 469             n.label = t.token.value;
 470         }
 471         ss = x.stmtStack;
 472         i = ss.length;
 473         label = n.label;
 474         if (label) {
 475             do {
 476                 if (--i < 0)
 477                     throw t.newSyntaxError("Label not found");
 478             } while (ss[i].label != label);
 479         } else {
 480             do {
 481                 if (--i < 0) {
 482                     throw t.newSyntaxError("Invalid " + ((tt == BREAK)
 483                                                          ? "break"
 484                                                          : "continue"));
 485                 }
 486             } while (!ss[i].isLoop && (tt != BREAK || ss[i].type != SWITCH));
 487         }
 488         n.target = ss[i];
 489         break;
 490
 491       case TRY:
 492         n = new Node(t);
 493         n.tryBlock = Block(t, x);
 494         n.catchClauses = [];
 495         while (t.match(CATCH)) {
 496             n2 = new Node(t);
 497             t.mustMatch(LEFT_PAREN);
 498             n2.varName = t.mustMatch(IDENTIFIER).value;
 499             if (t.match(IF)) {
 500                 if (x.ecmaStrictMode)
 501                     throw t.newSyntaxError("Illegal catch guard");
 502                 if (n.catchClauses.length && !n.catchClauses.top().guard)
 503                     throw t.newSyntaxError("Guarded catch after unguarded");
 504                 n2.guard = Expression(t, x);
 505             } else {
 506                 n2.guard = null;
 507             }
 508             t.mustMatch(RIGHT_PAREN);
 509             n2.block = Block(t, x);
 510             n.catchClauses.push(n2);
 511         }
 512         if (t.match(FINALLY))
 513             n.finallyBlock = Block(t, x);
 514         if (!n.catchClauses.length && !n.finallyBlock)
 515             throw t.newSyntaxError("Invalid try statement");
 516         return n;
 517
 518       case CATCH:
 519       case FINALLY:
 520         throw t.newSyntaxError(tokens[tt] + " without preceding try");
 521
 522       case THROW:
 523         n = new Node(t);
 524         n.exception = Expression(t, x);
 525         break;
 526
 527       case RETURN:
 528         if (!x.inFunction)
 529             throw t.newSyntaxError("Invalid return");
 530         n = new Node(t);
 531         tt = t.peekOnSameLine();
 532         if (tt != END && tt != NEWLINE && tt != SEMICOLON && tt != RIGHT_CURLY)
 533             n.value = Expression(t, x);
 534         break;
 535
 536       case WITH:
 537         n = new Node(t);
 538         n.object = ParenExpression(t, x);
 539         n.body = nest(t, x, n, Statement);
 540         return n;
 541
 542       case VAR:
 543       case CONST:
 544         n = Variables(t, x);
 545         break;
 546
 547       case DEBUGGER:
 548         n = new Node(t);
 549         break;
 550
 551       case NEWLINE:
 552       case SEMICOLON:
 553         n = new Node(t, SEMICOLON);
 554         n.expression = null;
 555         return n;
 556
 557       default:
 558         if (tt == IDENTIFIER) {
 559             t.scanOperand = false;
 560             tt = t.peek();
 561             t.scanOperand = true;
 562             if (tt == COLON) {
 563                 label = t.token.value;
 564                 ss = x.stmtStack;
 565                 for (i = ss.length-1; i >= 0; --i) {
 566                     if (ss[i].label == label)
 567                         throw t.newSyntaxError("Duplicate label");
 568                 }
 569                 t.get();
 570                 n = new Node(t, LABEL);
 571                 n.label = label;
 572                 n.statement = nest(t, x, n, Statement);
 573                 return n;
 574             }
 575         }
 576
 577         n = new Node(t, SEMICOLON);
 578         t.unget();
 579         n.expression = Expression(t, x);
 580         n.end = n.expression.end;
 581         break;
 582     }
 583
 584     if (t.lineno == t.token.lineno) {
 585         tt = t.peekOnSameLine();
 586         if (tt != END && tt != NEWLINE && tt != SEMICOLON && tt != RIGHT_CURLY)
 587             throw t.newSyntaxError("Missing ; before statement");
 588     }
 589     t.match(SEMICOLON);
 590     return n;
 591 }
 592
 593 function FunctionDefinition(t, x, requireName, functionForm) {
 594     var f = new Node(t);
 595     if (f.type != FUNCTION)
 596         f.type = (f.value == "get") ? GETTER : SETTER;
 597     if (t.match(IDENTIFIER))
 598         f.name = t.token.value;
 599     else if (requireName)
 600         throw t.newSyntaxError("Missing function identifier");
 601
 602     t.mustMatch(LEFT_PAREN);
 603     f.params = [];
 604     var tt;
 605     while ((tt = t.get()) != RIGHT_PAREN) {
 606         if (tt != IDENTIFIER)
 607             throw t.newSyntaxError("Missing formal parameter");
 608         f.params.push(t.token.value);
 609         if (t.peek() != RIGHT_PAREN)
 610             t.mustMatch(COMMA);
 611     }
 612
 613     t.mustMatch(LEFT_CURLY);
 614     var x2 = new CompilerContext(true);
 615     f.body = Script(t, x2);
 616     t.mustMatch(RIGHT_CURLY);
 617     f.end = t.token.end;
 618
 619     f.functionForm = functionForm;
 620     if (functionForm == DECLARED_FORM)
 621         x.funDecls.push(f);
 622     return f;
 623 }
 624
 625 function Variables(t, x) {
 626     var n = new Node(t);
 627     do {
 628         t.mustMatch(IDENTIFIER);
 629         var n2 = new Node(t);
 630         n2.name = n2.value;
 631         if (t.match(ASSIGN)) {
 632             if (t.token.assignOp)
 633                 throw t.newSyntaxError("Invalid variable initialization");
 634             n2.initializer = Expression(t, x, COMMA);
 635         }
 636         n2.readOnly = (n.type == CONST);
 637         n.push(n2);
 638         x.varDecls.push(n2);
 639     } while (t.match(COMMA));
 640     return n;
 641 }
 642
 643 function ParenExpression(t, x) {
 644     t.mustMatch(LEFT_PAREN);
 645     var n = Expression(t, x);
 646     t.mustMatch(RIGHT_PAREN);
 647     return n;
 648 }
 649
 650 var opPrecedence = {
 651     SEMICOLON: 0,
 652     COMMA: 1,
 653     ASSIGN: 2, HOOK: 2, COLON: 2,
 654     // The above all have to have the same precedence, see bug 330975.
 655     OR: 4,
 656     AND: 5,
 657     BITWISE_OR: 6,
 658     BITWISE_XOR: 7,
 659     BITWISE_AND: 8,
 660     EQ: 9, NE: 9, STRICT_EQ: 9, STRICT_NE: 9,
 661     LT: 10, LE: 10, GE: 10, GT: 10, IN: 10, INSTANCEOF: 10,
 662     LSH: 11, RSH: 11, URSH: 11,
 663     PLUS: 12, MINUS: 12,
 664     MUL: 13, DIV: 13, MOD: 13,
 665     DELETE: 14, VOID: 14, TYPEOF: 14, // PRE_INCREMENT: 14, PRE_DECREMENT: 14,
 666     NOT: 14, BITWISE_NOT: 14, UNARY_PLUS: 14, UNARY_MINUS: 14,
 667     INCREMENT: 15, DECREMENT: 15,     // postfix
 668     NEW: 16,
 669     DOT: 17
 670 };
 671
 672 // Map operator type code to precedence.
 673 for (i in opPrecedence)
 674     opPrecedence[GLOBAL[i]] = opPrecedence[i];
 675
 676 var opArity = {
 677     COMMA: -2,
 678     ASSIGN: 2,
 679     HOOK: 3,
 680     OR: 2,
 681     AND: 2,
 682     BITWISE_OR: 2,
 683     BITWISE_XOR: 2,
 684     BITWISE_AND: 2,
 685     EQ: 2, NE: 2, STRICT_EQ: 2, STRICT_NE: 2,
 686     LT: 2, LE: 2, GE: 2, GT: 2, IN: 2, INSTANCEOF: 2,
 687     LSH: 2, RSH: 2, URSH: 2,
 688     PLUS: 2, MINUS: 2,
 689     MUL: 2, DIV: 2, MOD: 2,
 690     DELETE: 1, VOID: 1, TYPEOF: 1,  // PRE_INCREMENT: 1, PRE_DECREMENT: 1,
 691     NOT: 1, BITWISE_NOT: 1, UNARY_PLUS: 1, UNARY_MINUS: 1,
 692     INCREMENT: 1, DECREMENT: 1,     // postfix
 693     NEW: 1, NEW_WITH_ARGS: 2, DOT: 2, INDEX: 2, CALL: 2,
 694     ARRAY_INIT: 1, OBJECT_INIT: 1, GROUP: 1
 695 };
 696
 697 // Map operator type code to arity.
 698 for (i in opArity)
 699     opArity[GLOBAL[i]] = opArity[i];
 700
 701 function Expression(t, x, stop) {
 702     var n, id, tt, operators = [], operands = [];
 703     var bl = x.bracketLevel, cl = x.curlyLevel, pl = x.parenLevel,
 704         hl = x.hookLevel;
 705
 706     function reduce() {
 707         var n = operators.pop();
 708         var op = n.type;
 709         var arity = opArity[op];
 710         if (arity == -2) {
 711             // Flatten left-associative trees.
 712             var left = operands.length >= 2 && operands[operands.length-2];
 713             if (left.type == op) {
 714                 var right = operands.pop();
 715                 left.push(right);
 716                 return left;
 717             }
 718             arity = 2;
 719         }
 720
 721         // Always use push to add operands to n, to update start and end.
 722         var a = operands.splice(operands.length - arity);
 723         for (var i = 0; i < arity; i++)
 724             n.push(a[i]);
 725
 726         // Include closing bracket or postfix operator in [start,end).
 727         if (n.end < t.token.end)
 728             n.end = t.token.end;
 729
 730         operands.push(n);
 731         return n;
 732     }
 733
 734 loop:
 735     while ((tt = t.get()) != END) {
 736         if (tt == stop &&
 737             x.bracketLevel == bl && x.curlyLevel == cl && x.parenLevel == pl &&
 738             x.hookLevel == hl) {
 739             // Stop only if tt matches the optional stop parameter, and that
 740             // token is not quoted by some kind of bracket.
 741             break;
 742         }
 743         switch (tt) {
 744           case SEMICOLON:
 745             // NB: cannot be empty, Statement handled that.
 746             break loop;
 747
 748           case ASSIGN:
 749           case HOOK:
 750           case COLON:
 751             if (t.scanOperand)
 752                 break loop;
 753             // Use >, not >=, for right-associative ASSIGN and HOOK/COLON.
 754             while (opPrecedence[operators.top().type] > opPrecedence[tt] ||
 755                    (tt == COLON && operators.top().type == ASSIGN)) {
 756                 reduce();
 757             }
 758             if (tt == COLON) {
 759                 n = operators.top();
 760                 if (n.type != HOOK)
 761                     throw t.newSyntaxError("Invalid label");
 762                 --x.hookLevel;
 763             } else {
 764                 operators.push(new Node(t));
 765                 if (tt == ASSIGN)
 766                     operands.top().assignOp = t.token.assignOp;
 767                 else
 768                     ++x.hookLevel;      // tt == HOOK
 769             }
 770             t.scanOperand = true;
 771             break;
 772
 773           case IN:
 774             // An in operator should not be parsed if we're parsing the head of
 775             // a for (...) loop, unless it is in the then part of a conditional
 776             // expression, or parenthesized somehow.
 777             if (x.inForLoopInit && !x.hookLevel &&
 778                 !x.bracketLevel && !x.curlyLevel && !x.parenLevel) {
 779                 break loop;
 780             }
 781             // FALL THROUGH
 782           case COMMA:
 783             // Treat comma as left-associative so reduce can fold left-heavy
 784             // COMMA trees into a single array.
 785             // FALL THROUGH
 786           case OR:
 787           case AND:
 788           case BITWISE_OR:
 789           case BITWISE_XOR:
 790           case BITWISE_AND:
 791           case EQ: case NE: case STRICT_EQ: case STRICT_NE:
 792           case LT: case LE: case GE: case GT:
 793           case INSTANCEOF:
 794           case LSH: case RSH: case URSH:
 795           case PLUS: case MINUS:
 796           case MUL: case DIV: case MOD:
 797           case DOT:
 798             if (t.scanOperand)
 799                 break loop;
 800             while (opPrecedence[operators.top().type] >= opPrecedence[tt])
 801                 reduce();
 802             if (tt == DOT) {
 803                 t.mustMatch(IDENTIFIER);
 804                 operands.push(new Node(t, DOT, operands.pop(), new Node(t)));
 805             } else {
 806                 operators.push(new Node(t));
 807                 t.scanOperand = true;
 808             }
 809             break;
 810
 811           case DELETE: case VOID: case TYPEOF:
 812           case NOT: case BITWISE_NOT: case UNARY_PLUS: case UNARY_MINUS:
 813           case NEW:
 814             if (!t.scanOperand)
 815                 break loop;
 816             operators.push(new Node(t));
 817             break;
 818
 819           case INCREMENT: case DECREMENT:
 820             if (t.scanOperand) {
 821                 operators.push(new Node(t));  // prefix increment or decrement
 822             } else {
 823                 // Don't cross a line boundary for postfix {in,de}crement.
 824                 if (t.tokens[(t.tokenIndex + t.lookahead - 1) & 3].lineno !=
 825                     t.lineno) {
 826                     break loop;
 827                 }
 828
 829                 // Use >, not >=, so postfix has higher precedence than prefix.
 830                 while (opPrecedence[operators.top().type] > opPrecedence[tt])
 831                     reduce();
 832                 n = new Node(t, tt, operands.pop());
 833                 n.postfix = true;
 834                 operands.push(n);
 835             }
 836             break;
 837
 838           case FUNCTION:
 839             if (!t.scanOperand)
 840                 break loop;
 841             operands.push(FunctionDefinition(t, x, false, EXPRESSED_FORM));
 842             t.scanOperand = false;
 843             break;
 844
 845           case NULL: case THIS: case TRUE: case FALSE:
 846           case IDENTIFIER: case NUMBER: case STRING: case REGEXP:
 847             if (!t.scanOperand)
 848                 break loop;
 849             operands.push(new Node(t));
 850             t.scanOperand = false;
 851             break;
 852
 853           case LEFT_BRACKET:
 854             if (t.scanOperand) {
 855                 // Array initialiser.  Parse using recursive descent, as the
 856                 // sub-grammar here is not an operator grammar.
 857                 n = new Node(t, ARRAY_INIT);
 858                 while ((tt = t.peek()) != RIGHT_BRACKET) {
 859                     if (tt == COMMA) {
 860                         t.get();
 861                         n.push(null);
 862                         continue;
 863                     }
 864                     n.push(Expression(t, x, COMMA));
 865                     if (!t.match(COMMA))
 866                         break;
 867                 }
 868                 t.mustMatch(RIGHT_BRACKET);
 869                 operands.push(n);
 870                 t.scanOperand = false;
 871             } else {
 872                 // Property indexing operator.
 873                 operators.push(new Node(t, INDEX));
 874                 t.scanOperand = true;
 875                 ++x.bracketLevel;
 876             }
 877             break;
 878
 879           case RIGHT_BRACKET:
 880             if (t.scanOperand || x.bracketLevel == bl)
 881                 break loop;
 882             while (reduce().type != INDEX)
 883                 continue;
 884             --x.bracketLevel;
 885             break;
 886
 887           case LEFT_CURLY:
 888             if (!t.scanOperand)
 889                 break loop;
 890             // Object initialiser.  As for array initialisers (see above),
 891             // parse using recursive descent.
 892             ++x.curlyLevel;
 893             n = new Node(t, OBJECT_INIT);
 894           object_init:
 895             if (!t.match(RIGHT_CURLY)) {
 896                 do {
 897                     tt = t.get();
 898                     if ((t.token.value == "get" || t.token.value == "set") &&
 899                         t.peek() == IDENTIFIER) {
 900                         if (x.ecmaStrictMode)
 901                             throw t.newSyntaxError("Illegal property accessor");
 902                         n.push(FunctionDefinition(t, x, true, EXPRESSED_FORM));
 903                     } else {
 904                         switch (tt) {
 905                           case IDENTIFIER:
 906                           case NUMBER:
 907                           case STRING:
 908                             id = new Node(t);
 909                             break;
 910                           case RIGHT_CURLY:
 911                             if (x.ecmaStrictMode)
 912                                 throw t.newSyntaxError("Illegal trailing ,");
 913                             break object_init;
 914                           default:
 915                             throw t.newSyntaxError("Invalid property name");
 916                         }
 917                         t.mustMatch(COLON);
 918                         n.push(new Node(t, PROPERTY_INIT, id,
 919                                         Expression(t, x, COMMA)));
 920                     }
 921                 } while (t.match(COMMA));
 922                 t.mustMatch(RIGHT_CURLY);
 923             }
 924             operands.push(n);
 925             t.scanOperand = false;
 926             --x.curlyLevel;
 927             break;
 928
 929           case RIGHT_CURLY:
 930             if (!t.scanOperand && x.curlyLevel != cl)
 931                 throw "PANIC: right curly botch";
 932             break loop;
 933
 934           case LEFT_PAREN:
 935             if (t.scanOperand) {
 936                 operators.push(new Node(t, GROUP));
 937             } else {
 938                 while (opPrecedence[operators.top().type] > opPrecedence[NEW])
 939                     reduce();
 940
 941                 // Handle () now, to regularize the n-ary case for n > 0.
 942                 // We must set scanOperand in case there are arguments and
 943                 // the first one is a regexp or unary+/-.
 944                 n = operators.top();
 945                 t.scanOperand = true;
 946                 if (t.match(RIGHT_PAREN)) {
 947                     if (n.type == NEW) {
 948                         --operators.length;
 949                         n.push(operands.pop());
 950                     } else {
 951                         n = new Node(t, CALL, operands.pop(),
 952                                      new Node(t, LIST));
 953                     }
 954                     operands.push(n);
 955                     t.scanOperand = false;
 956                     break;
 957                 }
 958                 if (n.type == NEW)
 959                     n.type = NEW_WITH_ARGS;
 960                 else
 961                     operators.push(new Node(t, CALL));
 962             }
 963             ++x.parenLevel;
 964             break;
 965
 966           case RIGHT_PAREN:
 967             if (t.scanOperand || x.parenLevel == pl)
 968                 break loop;
 969             while ((tt = reduce().type) != GROUP && tt != CALL &&
 970                    tt != NEW_WITH_ARGS) {
 971                 continue;
 972             }
 973             if (tt != GROUP) {
 974                 n = operands.top();
 975                 if (n[1].type != COMMA)
 976                     n[1] = new Node(t, LIST, n[1]);
 977                 else
 978                     n[1].type = LIST;
 979             }
 980             --x.parenLevel;
 981             break;
 982
 983           // Automatic semicolon insertion means we may scan across a newline
 984           // and into the beginning of another statement.  If so, break out of
 985           // the while loop and let the t.scanOperand logic handle errors.
 986           default:
 987             break loop;
 988         }
 989     }
 990
 991     if (x.hookLevel != hl)
 992         throw t.newSyntaxError("Missing : after ?");
 993     if (x.parenLevel != pl)
 994         throw t.newSyntaxError("Missing ) in parenthetical");
 995     if (x.bracketLevel != bl)
 996         throw t.newSyntaxError("Missing ] in index expression");
 997     if (t.scanOperand)
 998         throw t.newSyntaxError("Missing operand");
 999
1000     // Resume default mode, scanning for operands, not operators.
1001     t.scanOperand = true;
1002     t.unget();
1003     while (operators.length)
1004         reduce();
1005     return operands.pop();
1006 }
1007
1008 function parse(s, f, l) {
1009     var t = new Tokenizer(s, f, l);
1010     var x = new CompilerContext(false);
1011     var n = Script(t, x);
1012     if (!t.done)
1013         throw t.newSyntaxError("Syntax error");
1014     return n;
1015 }