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
 480             /*
 481              * Both break and continue to label need to be handled specially
 482              * within a labeled loop, so that they target that loop. If not in
 483              * a loop, then break targets its labeled statement. Labels can be
 484              * nested so we skip all labels immediately enclosing the nearest
 485              * non-label statement.
 486              */
 487             while (i < ss.length - 1 && ss[i+1].type == LABEL)
 488                 i++;
 489             if (i < ss.length - 1 && ss[i+1].isLoop)
 490                 i++;
 491             else if (tt == CONTINUE)
 492                 throw t.newSyntaxError("Invalid continue");
 493         } else {
 494             do {
 495                 if (--i < 0) {
 496                     throw t.newSyntaxError("Invalid " + ((tt == BREAK)
 497                                                          ? "break"
 498                                                          : "continue"));
 499                 }
 500             } while (!ss[i].isLoop && (tt != BREAK || ss[i].type != SWITCH));
 501         }
 502         n.target = ss[i];
 503         break;
 504
 505       case TRY:
 506         n = new Node(t);
 507         n.tryBlock = Block(t, x);
 508         n.catchClauses = [];
 509         while (t.match(CATCH)) {
 510             n2 = new Node(t);
 511             t.mustMatch(LEFT_PAREN);
 512             n2.varName = t.mustMatch(IDENTIFIER).value;
 513             if (t.match(IF)) {
 514                 if (x.ecmaStrictMode)
 515                     throw t.newSyntaxError("Illegal catch guard");
 516                 if (n.catchClauses.length && !n.catchClauses.top().guard)
 517                     throw t.newSyntaxError("Guarded catch after unguarded");
 518                 n2.guard = Expression(t, x);
 519             } else {
 520                 n2.guard = null;
 521             }
 522             t.mustMatch(RIGHT_PAREN);
 523             n2.block = Block(t, x);
 524             n.catchClauses.push(n2);
 525         }
 526         if (t.match(FINALLY))
 527             n.finallyBlock = Block(t, x);
 528         if (!n.catchClauses.length && !n.finallyBlock)
 529             throw t.newSyntaxError("Invalid try statement");
 530         return n;
 531
 532       case CATCH:
 533       case FINALLY:
 534         throw t.newSyntaxError(tokens[tt] + " without preceding try");
 535
 536       case THROW:
 537         n = new Node(t);
 538         n.exception = Expression(t, x);
 539         break;
 540
 541       case RETURN:
 542         if (!x.inFunction)
 543             throw t.newSyntaxError("Invalid return");
 544         n = new Node(t);
 545         tt = t.peekOnSameLine();
 546         if (tt != END && tt != NEWLINE && tt != SEMICOLON && tt != RIGHT_CURLY)
 547             n.value = Expression(t, x);
 548         break;
 549
 550       case WITH:
 551         n = new Node(t);
 552         n.object = ParenExpression(t, x);
 553         n.body = nest(t, x, n, Statement);
 554         return n;
 555
 556       case VAR:
 557       case CONST:
 558         n = Variables(t, x);
 559         break;
 560
 561       case DEBUGGER:
 562         n = new Node(t);
 563         break;
 564
 565       case NEWLINE:
 566       case SEMICOLON:
 567         n = new Node(t, SEMICOLON);
 568         n.expression = null;
 569         return n;
 570
 571       default:
 572         if (tt == IDENTIFIER) {
 573             t.scanOperand = false;
 574             tt = t.peek();
 575             t.scanOperand = true;
 576             if (tt == COLON) {
 577                 label = t.token.value;
 578                 ss = x.stmtStack;
 579                 for (i = ss.length-1; i >= 0; --i) {
 580                     if (ss[i].label == label)
 581                         throw t.newSyntaxError("Duplicate label");
 582                 }
 583                 t.get();
 584                 n = new Node(t, LABEL);
 585                 n.label = label;
 586                 n.statement = nest(t, x, n, Statement);
 587                 return n;
 588             }
 589         }
 590
 591         n = new Node(t, SEMICOLON);
 592         t.unget();
 593         n.expression = Expression(t, x);
 594         n.end = n.expression.end;
 595         break;
 596     }
 597
 598     if (t.lineno == t.token.lineno) {
 599         tt = t.peekOnSameLine();
 600         if (tt != END && tt != NEWLINE && tt != SEMICOLON && tt != RIGHT_CURLY)
 601             throw t.newSyntaxError("Missing ; before statement");
 602     }
 603     t.match(SEMICOLON);
 604     return n;
 605 }
 606
 607 function FunctionDefinition(t, x, requireName, functionForm) {
 608     var f = new Node(t);
 609     if (f.type != FUNCTION)
 610         f.type = (f.value == "get") ? GETTER : SETTER;
 611     if (t.match(IDENTIFIER))
 612         f.name = t.token.value;
 613     else if (requireName)
 614         throw t.newSyntaxError("Missing function identifier");
 615
 616     t.mustMatch(LEFT_PAREN);
 617     f.params = [];
 618     var tt;
 619     while ((tt = t.get()) != RIGHT_PAREN) {
 620         if (tt != IDENTIFIER)
 621             throw t.newSyntaxError("Missing formal parameter");
 622         f.params.push(t.token.value);
 623         if (t.peek() != RIGHT_PAREN)
 624             t.mustMatch(COMMA);
 625     }
 626
 627     t.mustMatch(LEFT_CURLY);
 628     var x2 = new CompilerContext(true);
 629     f.body = Script(t, x2);
 630     t.mustMatch(RIGHT_CURLY);
 631     f.end = t.token.end;
 632
 633     f.functionForm = functionForm;
 634     if (functionForm == DECLARED_FORM)
 635         x.funDecls.push(f);
 636     return f;
 637 }
 638
 639 function Variables(t, x) {
 640     var n = new Node(t);
 641     do {
 642         t.mustMatch(IDENTIFIER);
 643         var n2 = new Node(t);
 644         n2.name = n2.value;
 645         if (t.match(ASSIGN)) {
 646             if (t.token.assignOp)
 647                 throw t.newSyntaxError("Invalid variable initialization");
 648             n2.initializer = Expression(t, x, COMMA);
 649         }
 650         n2.readOnly = (n.type == CONST);
 651         n.push(n2);
 652         x.varDecls.push(n2);
 653     } while (t.match(COMMA));
 654     return n;
 655 }
 656
 657 function ParenExpression(t, x) {
 658     t.mustMatch(LEFT_PAREN);
 659     var n = Expression(t, x);
 660     t.mustMatch(RIGHT_PAREN);
 661     return n;
 662 }
 663
 664 var opPrecedence = {
 665     SEMICOLON: 0,
 666     COMMA: 1,
 667     ASSIGN: 2, HOOK: 2, COLON: 2,
 668     // The above all have to have the same precedence, see bug 330975.
 669     OR: 4,
 670     AND: 5,
 671     BITWISE_OR: 6,
 672     BITWISE_XOR: 7,
 673     BITWISE_AND: 8,
 674     EQ: 9, NE: 9, STRICT_EQ: 9, STRICT_NE: 9,
 675     LT: 10, LE: 10, GE: 10, GT: 10, IN: 10, INSTANCEOF: 10,
 676     LSH: 11, RSH: 11, URSH: 11,
 677     PLUS: 12, MINUS: 12,
 678     MUL: 13, DIV: 13, MOD: 13,
 679     DELETE: 14, VOID: 14, TYPEOF: 14, // PRE_INCREMENT: 14, PRE_DECREMENT: 14,
 680     NOT: 14, BITWISE_NOT: 14, UNARY_PLUS: 14, UNARY_MINUS: 14,
 681     INCREMENT: 15, DECREMENT: 15,     // postfix
 682     NEW: 16,
 683     DOT: 17
 684 };
 685
 686 // Map operator type code to precedence.
 687 for (i in opPrecedence)
 688     opPrecedence[GLOBAL[i]] = opPrecedence[i];
 689
 690 var opArity = {
 691     COMMA: -2,
 692     ASSIGN: 2,
 693     HOOK: 3,
 694     OR: 2,
 695     AND: 2,
 696     BITWISE_OR: 2,
 697     BITWISE_XOR: 2,
 698     BITWISE_AND: 2,
 699     EQ: 2, NE: 2, STRICT_EQ: 2, STRICT_NE: 2,
 700     LT: 2, LE: 2, GE: 2, GT: 2, IN: 2, INSTANCEOF: 2,
 701     LSH: 2, RSH: 2, URSH: 2,
 702     PLUS: 2, MINUS: 2,
 703     MUL: 2, DIV: 2, MOD: 2,
 704     DELETE: 1, VOID: 1, TYPEOF: 1,  // PRE_INCREMENT: 1, PRE_DECREMENT: 1,
 705     NOT: 1, BITWISE_NOT: 1, UNARY_PLUS: 1, UNARY_MINUS: 1,
 706     INCREMENT: 1, DECREMENT: 1,     // postfix
 707     NEW: 1, NEW_WITH_ARGS: 2, DOT: 2, INDEX: 2, CALL: 2,
 708     ARRAY_INIT: 1, OBJECT_INIT: 1, GROUP: 1
 709 };
 710
 711 // Map operator type code to arity.
 712 for (i in opArity)
 713     opArity[GLOBAL[i]] = opArity[i];
 714
 715 function Expression(t, x, stop) {
 716     var n, id, tt, operators = [], operands = [];
 717     var bl = x.bracketLevel, cl = x.curlyLevel, pl = x.parenLevel,
 718         hl = x.hookLevel;
 719
 720     function reduce() {
 721         var n = operators.pop();
 722         var op = n.type;
 723         var arity = opArity[op];
 724         if (arity == -2) {
 725             // Flatten left-associative trees.
 726             var left = operands.length >= 2 && operands[operands.length-2];
 727             if (left.type == op) {
 728                 var right = operands.pop();
 729                 left.push(right);
 730                 return left;
 731             }
 732             arity = 2;
 733         }
 734
 735         // Always use push to add operands to n, to update start and end.
 736         var a = operands.splice(operands.length - arity);
 737         for (var i = 0; i < arity; i++)
 738             n.push(a[i]);
 739
 740         // Include closing bracket or postfix operator in [start,end).
 741         if (n.end < t.token.end)
 742             n.end = t.token.end;
 743
 744         operands.push(n);
 745         return n;
 746     }
 747
 748 loop:
 749     while ((tt = t.get()) != END) {
 750         if (tt == stop &&
 751             x.bracketLevel == bl && x.curlyLevel == cl && x.parenLevel == pl &&
 752             x.hookLevel == hl) {
 753             // Stop only if tt matches the optional stop parameter, and that
 754             // token is not quoted by some kind of bracket.
 755             break;
 756         }
 757         switch (tt) {
 758           case SEMICOLON:
 759             // NB: cannot be empty, Statement handled that.
 760             break loop;
 761
 762           case ASSIGN:
 763           case HOOK:
 764           case COLON:
 765             if (t.scanOperand)
 766                 break loop;
 767             // Use >, not >=, for right-associative ASSIGN and HOOK/COLON.
 768             while (opPrecedence[operators.top().type] > opPrecedence[tt] ||
 769                    (tt == COLON && operators.top().type == ASSIGN)) {
 770                 reduce();
 771             }
 772             if (tt == COLON) {
 773                 n = operators.top();
 774                 if (n.type != HOOK)
 775                     throw t.newSyntaxError("Invalid label");
 776                 --x.hookLevel;
 777             } else {
 778                 operators.push(new Node(t));
 779                 if (tt == ASSIGN)
 780                     operands.top().assignOp = t.token.assignOp;
 781                 else
 782                     ++x.hookLevel;      // tt == HOOK
 783             }
 784             t.scanOperand = true;
 785             break;
 786
 787           case IN:
 788             // An in operator should not be parsed if we're parsing the head of
 789             // a for (...) loop, unless it is in the then part of a conditional
 790             // expression, or parenthesized somehow.
 791             if (x.inForLoopInit && !x.hookLevel &&
 792                 !x.bracketLevel && !x.curlyLevel && !x.parenLevel) {
 793                 break loop;
 794             }
 795             // FALL THROUGH
 796           case COMMA:
 797             // Treat comma as left-associative so reduce can fold left-heavy
 798             // COMMA trees into a single array.
 799             // FALL THROUGH
 800           case OR:
 801           case AND:
 802           case BITWISE_OR:
 803           case BITWISE_XOR:
 804           case BITWISE_AND:
 805           case EQ: case NE: case STRICT_EQ: case STRICT_NE:
 806           case LT: case LE: case GE: case GT:
 807           case INSTANCEOF:
 808           case LSH: case RSH: case URSH:
 809           case PLUS: case MINUS:
 810           case MUL: case DIV: case MOD:
 811           case DOT:
 812             if (t.scanOperand)
 813                 break loop;
 814             while (opPrecedence[operators.top().type] >= opPrecedence[tt])
 815                 reduce();
 816             if (tt == DOT) {
 817                 t.mustMatch(IDENTIFIER);
 818                 operands.push(new Node(t, DOT, operands.pop(), new Node(t)));
 819             } else {
 820                 operators.push(new Node(t));
 821                 t.scanOperand = true;
 822             }
 823             break;
 824
 825           case DELETE: case VOID: case TYPEOF:
 826           case NOT: case BITWISE_NOT: case UNARY_PLUS: case UNARY_MINUS:
 827           case NEW:
 828             if (!t.scanOperand)
 829                 break loop;
 830             operators.push(new Node(t));
 831             break;
 832
 833           case INCREMENT: case DECREMENT:
 834             if (t.scanOperand) {
 835                 operators.push(new Node(t));  // prefix increment or decrement
 836             } else {
 837                 // Don't cross a line boundary for postfix {in,de}crement.
 838                 if (t.tokens[(t.tokenIndex + t.lookahead - 1) & 3].lineno !=
 839                     t.lineno) {
 840                     break loop;
 841                 }
 842
 843                 // Use >, not >=, so postfix has higher precedence than prefix.
 844                 while (opPrecedence[operators.top().type] > opPrecedence[tt])
 845                     reduce();
 846                 n = new Node(t, tt, operands.pop());
 847                 n.postfix = true;
 848                 operands.push(n);
 849             }
 850             break;
 851
 852           case FUNCTION:
 853             if (!t.scanOperand)
 854                 break loop;
 855             operands.push(FunctionDefinition(t, x, false, EXPRESSED_FORM));
 856             t.scanOperand = false;
 857             break;
 858
 859           case NULL: case THIS: case TRUE: case FALSE:
 860           case IDENTIFIER: case NUMBER: case STRING: case REGEXP:
 861             if (!t.scanOperand)
 862                 break loop;
 863             operands.push(new Node(t));
 864             t.scanOperand = false;
 865             break;
 866
 867           case LEFT_BRACKET:
 868             if (t.scanOperand) {
 869                 // Array initialiser.  Parse using recursive descent, as the
 870                 // sub-grammar here is not an operator grammar.
 871                 n = new Node(t, ARRAY_INIT);
 872                 while ((tt = t.peek()) != RIGHT_BRACKET) {
 873                     if (tt == COMMA) {
 874                         t.get();
 875                         n.push(null);
 876                         continue;
 877                     }
 878                     n.push(Expression(t, x, COMMA));
 879                     if (!t.match(COMMA))
 880                         break;
 881                 }
 882                 t.mustMatch(RIGHT_BRACKET);
 883                 operands.push(n);
 884                 t.scanOperand = false;
 885             } else {
 886                 // Property indexing operator.
 887                 operators.push(new Node(t, INDEX));
 888                 t.scanOperand = true;
 889                 ++x.bracketLevel;
 890             }
 891             break;
 892
 893           case RIGHT_BRACKET:
 894             if (t.scanOperand || x.bracketLevel == bl)
 895                 break loop;
 896             while (reduce().type != INDEX)
 897                 continue;
 898             --x.bracketLevel;
 899             break;
 900
 901           case LEFT_CURLY:
 902             if (!t.scanOperand)
 903                 break loop;
 904             // Object initialiser.  As for array initialisers (see above),
 905             // parse using recursive descent.
 906             ++x.curlyLevel;
 907             n = new Node(t, OBJECT_INIT);
 908           object_init:
 909             if (!t.match(RIGHT_CURLY)) {
 910                 do {
 911                     tt = t.get();
 912                     if ((t.token.value == "get" || t.token.value == "set") &&
 913                         t.peek() == IDENTIFIER) {
 914                         if (x.ecmaStrictMode)
 915                             throw t.newSyntaxError("Illegal property accessor");
 916                         n.push(FunctionDefinition(t, x, true, EXPRESSED_FORM));
 917                     } else {
 918                         switch (tt) {
 919                           case IDENTIFIER:
 920                           case NUMBER:
 921                           case STRING:
 922                             id = new Node(t);
 923                             break;
 924                           case RIGHT_CURLY:
 925                             if (x.ecmaStrictMode)
 926                                 throw t.newSyntaxError("Illegal trailing ,");
 927                             break object_init;
 928                           default:
 929                             throw t.newSyntaxError("Invalid property name");
 930                         }
 931                         t.mustMatch(COLON);
 932                         n.push(new Node(t, PROPERTY_INIT, id,
 933                                         Expression(t, x, COMMA)));
 934                     }
 935                 } while (t.match(COMMA));
 936                 t.mustMatch(RIGHT_CURLY);
 937             }
 938             operands.push(n);
 939             t.scanOperand = false;
 940             --x.curlyLevel;
 941             break;
 942
 943           case RIGHT_CURLY:
 944             if (!t.scanOperand && x.curlyLevel != cl)
 945                 throw "PANIC: right curly botch";
 946             break loop;
 947
 948           case LEFT_PAREN:
 949             if (t.scanOperand) {
 950                 operators.push(new Node(t, GROUP));
 951             } else {
 952                 while (opPrecedence[operators.top().type] > opPrecedence[NEW])
 953                     reduce();
 954
 955                 // Handle () now, to regularize the n-ary case for n > 0.
 956                 // We must set scanOperand in case there are arguments and
 957                 // the first one is a regexp or unary+/-.
 958                 n = operators.top();
 959                 t.scanOperand = true;
 960                 if (t.match(RIGHT_PAREN)) {
 961                     if (n.type == NEW) {
 962                         --operators.length;
 963                         n.push(operands.pop());
 964                     } else {
 965                         n = new Node(t, CALL, operands.pop(),
 966                                      new Node(t, LIST));
 967                     }
 968                     operands.push(n);
 969                     t.scanOperand = false;
 970                     break;
 971                 }
 972                 if (n.type == NEW)
 973                     n.type = NEW_WITH_ARGS;
 974                 else
 975                     operators.push(new Node(t, CALL));
 976             }
 977             ++x.parenLevel;
 978             break;
 979
 980           case RIGHT_PAREN:
 981             if (t.scanOperand || x.parenLevel == pl)
 982                 break loop;
 983             while ((tt = reduce().type) != GROUP && tt != CALL &&
 984                    tt != NEW_WITH_ARGS) {
 985                 continue;
 986             }
 987             if (tt != GROUP) {
 988                 n = operands.top();
 989                 if (n[1].type != COMMA)
 990                     n[1] = new Node(t, LIST, n[1]);
 991                 else
 992                     n[1].type = LIST;
 993             }
 994             --x.parenLevel;
 995             break;
 996
 997           // Automatic semicolon insertion means we may scan across a newline
 998           // and into the beginning of another statement.  If so, break out of
 999           // the while loop and let the t.scanOperand logic handle errors.
1000           default:
1001             break loop;
1002         }
1003     }
1004
1005     if (x.hookLevel != hl)
1006         throw t.newSyntaxError("Missing : after ?");
1007     if (x.parenLevel != pl)
1008         throw t.newSyntaxError("Missing ) in parenthetical");
1009     if (x.bracketLevel != bl)
1010         throw t.newSyntaxError("Missing ] in index expression");
1011     if (t.scanOperand)
1012         throw t.newSyntaxError("Missing operand");
1013
1014     // Resume default mode, scanning for operands, not operators.
1015     t.scanOperand = true;
1016     t.unget();
1017     while (operators.length)
1018         reduce();
1019     return operands.pop();
1020 }
1021
1022 function parse(s, f, l) {
1023     var t = new Tokenizer(s, f, l);
1024     var x = new CompilerContext(false);
1025     var n = Script(t, x);
1026     if (!t.done)
1027         throw t.newSyntaxError("Syntax error");
1028     return n;
1029 }