build/lib/parse-js.js

   1 /***********************************************************************
   2
   3   A JavaScript tokenizer / parser / beautifier / compressor.
   4
   5   This version is suitable for Node.js.  With minimal changes (the
   6   exports stuff) it should work on any JS platform.
   7
   8   This file contains the tokenizer/parser.  It is a port to JavaScript
   9   of parse-js [1], a JavaScript parser library written in Common Lisp
  10   by Marijn Haverbeke.  Thank you Marijn!
  11
  12   [1] http://marijn.haverbeke.nl/parse-js/
  13
  14   Exported functions:
  15
  16     - tokenizer(code) -- returns a function.  Call the returned
  17       function to fetch the next token.
  18
  19     - parse(code) -- returns an AST of the given JavaScript code.
  20
  21   -------------------------------- (C) ---------------------------------
  22
  23                            Author: Mihai Bazon
  24                          <mihai.bazon@gmail.com>
  25                        http://mihai.bazon.net/blog
  26
  27   Distributed under the BSD license:
  28
  29     Copyright 2010 (c) Mihai Bazon <mihai.bazon@gmail.com>
  30     Based on parse-js (http://marijn.haverbeke.nl/parse-js/).
  31
  32     Redistribution and use in source and binary forms, with or without
  33     modification, are permitted provided that the following conditions
  34     are met:
  35
  36         * Redistributions of source code must retain the above
  37           copyright notice, this list of conditions and the following
  38           disclaimer.
  39
  40         * Redistributions in binary form must reproduce the above
  41           copyright notice, this list of conditions and the following
  42           disclaimer in the documentation and/or other materials
  43           provided with the distribution.
  44
  45     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER “AS IS” AND ANY
  46     EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  47     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  48     PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE
  49     LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
  50     OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  51     PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  52     PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  53     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
  54     TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
  55     THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  56     SUCH DAMAGE.
  57
  58  ***********************************************************************/
  59
  60 /* -----[ Tokenizer (constants) ]----- */
  61
  62 var KEYWORDS = array_to_hash([
  63         "break",
  64         "case",
  65         "catch",
  66         "const",
  67         "continue",
  68         "default",
  69         "delete",
  70         "do",
  71         "else",
  72         "finally",
  73         "for",
  74         "function",
  75         "if",
  76         "in",
  77         "instanceof",
  78         "new",
  79         "return",
  80         "switch",
  81         "throw",
  82         "try",
  83         "typeof",
  84         "var",
  85         "void",
  86         "while",
  87         "with"
  88 ]);
  89
  90 var RESERVED_WORDS = array_to_hash([
  91         "abstract",
  92         "boolean",
  93         "byte",
  94         "char",
  95         "class",
  96         "debugger",
  97         "double",
  98         "enum",
  99         "export",
 100         "extends",
 101         "final",
 102         "float",
 103         "goto",
 104         "implements",
 105         "import",
 106         "int",
 107         "interface",
 108         "long",
 109         "native",
 110         "package",
 111         "private",
 112         "protected",
 113         "public",
 114         "short",
 115         "static",
 116         "super",
 117         "synchronized",
 118         "throws",
 119         "transient",
 120         "volatile"
 121 ]);
 122
 123 var KEYWORDS_BEFORE_EXPRESSION = array_to_hash([
 124         "return",
 125         "new",
 126         "delete",
 127         "throw",
 128         "else",
 129         "case"
 130 ]);
 131
 132 var KEYWORDS_ATOM = array_to_hash([
 133         "false",
 134         "null",
 135         "true",
 136         "undefined"
 137 ]);
 138
 139 var OPERATOR_CHARS = array_to_hash(characters("+-*&%=<>!?|~^"));
 140
 141 var RE_HEX_NUMBER = /^0x[0-9a-f]+$/i;
 142 var RE_OCT_NUMBER = /^0[0-7]+$/;
 143 var RE_DEC_NUMBER = /^\d*\.?\d*(?:e[+-]?\d*(?:\d\.?|\.?\d)\d*)?$/i;
 144
 145 var OPERATORS = array_to_hash([
 146         "in",
 147         "instanceof",
 148         "typeof",
 149         "new",
 150         "void",
 151         "delete",
 152         "++",
 153         "--",
 154         "+",
 155         "-",
 156         "!",
 157         "~",
 158         "&",
 159         "|",
 160         "^",
 161         "*",
 162         "/",
 163         "%",
 164         ">>",
 165         "<<",
 166         ">>>",
 167         "<",
 168         ">",
 169         "<=",
 170         ">=",
 171         "==",
 172         "===",
 173         "!=",
 174         "!==",
 175         "?",
 176         "=",
 177         "+=",
 178         "-=",
 179         "/=",
 180         "*=",
 181         "%=",
 182         ">>=",
 183         "<<=",
 184         ">>>=",
 185         "~=",
 186         "%=",
 187         "|=",
 188         "^=",
 189         "&=",
 190         "&&",
 191         "||"
 192 ]);
 193
 194 var WHITESPACE_CHARS = array_to_hash(characters(" \n\r\t"));
 195
 196 var PUNC_BEFORE_EXPRESSION = array_to_hash(characters("[{}(,.;:"));
 197
 198 var PUNC_CHARS = array_to_hash(characters("[]{}(),;:"));
 199
 200 var REGEXP_MODIFIERS = array_to_hash(characters("gmsiy"));
 201
 202 /* -----[ Tokenizer ]----- */
 203
 204 function is_alphanumeric_char(ch) {
 205         ch = ch.charCodeAt(0);
 206         return (ch >= 48 && ch <= 57) ||
 207                 (ch >= 65 && ch <= 90) ||
 208                 (ch >= 97 && ch <= 122);
 209 };
 210
 211 function is_identifier_char(ch) {
 212         return is_alphanumeric_char(ch) || ch == "$" || ch == "_";
 213 };
 214
 215 function is_digit(ch) {
 216         ch = ch.charCodeAt(0);
 217         return ch >= 48 && ch <= 57;
 218 };
 219
 220 function parse_js_number(num) {
 221         if (RE_HEX_NUMBER.test(num)) {
 222                 return parseInt(num.substr(2), 16);
 223         } else if (RE_OCT_NUMBER.test(num)) {
 224                 return parseInt(num.substr(1), 8);
 225         } else if (RE_DEC_NUMBER.test(num)) {
 226                 return parseFloat(num);
 227         }
 228 };
 229
 230 function JS_Parse_Error(message, line, col, pos) {
 231         this.message = message;
 232         this.line = line;
 233         this.col = col;
 234         this.pos = pos;
 235         try {
 236                 ({})();
 237         } catch(ex) {
 238                 this.stack = ex.stack;
 239         };
 240 };
 241
 242 JS_Parse_Error.prototype.toString = function() {
 243         return this.message + " (line: " + this.line + ", col: " + this.col + ", pos: " + this.pos + ")" + "\n\n" + this.stack;
 244 };
 245
 246 function js_error(message, line, col, pos) {
 247         throw new JS_Parse_Error(message, line, col, pos);
 248 };
 249
 250 function is_token(token, type, val) {
 251         return token.type == type && (val == null || token.value == val);
 252 };
 253
 254 var EX_EOF = {};
 255
 256 function tokenizer($TEXT, skip_comments) {
 257
 258         var S = {
 259                 text           : $TEXT.replace(/\r\n?|[\n\u2028\u2029]/g, "\n").replace(/^\uFEFF/, ''),
 260                 pos            : 0,
 261                 tokpos         : 0,
 262                 line           : 0,
 263                 tokline        : 0,
 264                 col            : 0,
 265                 tokcol         : 0,
 266                 newline_before : false,
 267                 regex_allowed  : false
 268         };
 269
 270         function peek() { return S.text.charAt(S.pos); };
 271
 272         function next(signal_eof) {
 273                 var ch = S.text.charAt(S.pos++);
 274                 if (signal_eof && !ch)
 275                         throw EX_EOF;
 276                 if (ch == "\n") {
 277                         S.newline_before = true;
 278                         ++S.line;
 279                         S.col = 0;
 280                 } else {
 281                         ++S.col;
 282                 }
 283                 return ch;
 284         };
 285
 286         function eof() {
 287                 return !S.peek();
 288         };
 289
 290         function find(what, signal_eof) {
 291                 var pos = S.text.indexOf(what, S.pos);
 292                 if (signal_eof && pos == -1) throw EX_EOF;
 293                 return pos;
 294         };
 295
 296         function start_token() {
 297                 S.tokline = S.line;
 298                 S.tokcol = S.col;
 299                 S.tokpos = S.pos;
 300         };
 301
 302         function token(type, value) {
 303                 S.regex_allowed = ((type == "operator" && !HOP(UNARY_POSTFIX, value)) ||
 304                                    (type == "keyword" && HOP(KEYWORDS_BEFORE_EXPRESSION, value)) ||
 305                                    (type == "punc" && HOP(PUNC_BEFORE_EXPRESSION, value)));
 306                 var ret = {
 307                         type  : type,
 308                         value : value,
 309                         line  : S.tokline,
 310                         col   : S.tokcol,
 311                         pos   : S.tokpos,
 312                         nlb   : S.newline_before
 313                 };
 314                 S.newline_before = false;
 315                 return ret;
 316         };
 317
 318         function skip_whitespace() {
 319                 while (HOP(WHITESPACE_CHARS, peek()))
 320                         next();
 321         };
 322
 323         function read_while(pred) {
 324                 var ret = "", ch = peek(), i = 0;
 325                 while (ch && pred(ch, i++)) {
 326                         ret += next();
 327                         ch = peek();
 328                 }
 329                 return ret;
 330         };
 331
 332         function parse_error(err) {
 333                 js_error(err, S.tokline, S.tokcol, S.tokpos);
 334         };
 335
 336         function read_num(prefix) {
 337                 var has_e = false, after_e = false, has_x = false, has_dot = prefix == ".";
 338                 var num = read_while(function(ch, i){
 339                         if (ch == "x" || ch == "X") {
 340                                 if (has_x) return false;
 341                                 return has_x = true;
 342                         }
 343                         if (!has_x && (ch == "E" || ch == "e")) {
 344                                 if (has_e) return false;
 345                                 return has_e = after_e = true;
 346                         }
 347                         if (ch == "-") {
 348                                 if (after_e || (i == 0 && !prefix)) return true;
 349                                 return false;
 350                         }
 351                         if (ch == "+") return after_e;
 352                         after_e = false;
 353                         if (ch == ".") {
 354                                 if (!has_dot)
 355                                         return has_dot = true;
 356                                 return false;
 357                         }
 358                         return is_alphanumeric_char(ch);
 359                 });
 360                 if (prefix)
 361                         num = prefix + num;
 362                 var valid = parse_js_number(num);
 363                 if (!isNaN(valid)) {
 364                         return token("num", valid);
 365                 } else {
 366                         parse_error("Invalid syntax: " + num);
 367                 }
 368         };
 369
 370         function read_escaped_char() {
 371                 var ch = next(true);
 372                 switch (ch) {
 373                     case "n" : return "\n";
 374                     case "r" : return "\r";
 375                     case "t" : return "\t";
 376                     case "b" : return "\b";
 377                     case "v" : return "\v";
 378                     case "f" : return "\f";
 379                     case "0" : return "\0";
 380                     case "x" : return String.fromCharCode(hex_bytes(2));
 381                     case "u" : return String.fromCharCode(hex_bytes(4));
 382                     default  : return ch;
 383                 }
 384         };
 385
 386         function hex_bytes(n) {
 387                 var num = 0;
 388                 for (; n > 0; --n) {
 389                         var digit = parseInt(next(true), 16);
 390                         if (isNaN(digit))
 391                                 parse_error("Invalid hex-character pattern in string");
 392                         num = (num << 4) | digit;
 393                 }
 394                 return num;
 395         };
 396
 397         function read_string() {
 398                 return with_eof_error("Unterminated string constant", function(){
 399                         var quote = next(), ret = "";
 400                         for (;;) {
 401                                 var ch = next(true);
 402                                 if (ch == "\\") ch = read_escaped_char();
 403                                 else if (ch == quote) break;
 404                                 ret += ch;
 405                         }
 406                         return token("string", ret);
 407                 });
 408         };
 409
 410         function read_line_comment() {
 411                 next();
 412                 var i = find("\n"), ret;
 413                 if (i == -1) {
 414                         ret = S.text.substr(S.pos);
 415                         S.pos = S.text.length;
 416                 } else {
 417                         ret = S.text.substring(S.pos, i);
 418                         S.pos = i;
 419                 }
 420                 return token("comment1", ret);
 421         };
 422
 423         function read_multiline_comment() {
 424                 next();
 425                 return with_eof_error("Unterminated multiline comment", function(){
 426                         var i = find("*/", true),
 427                             text = S.text.substring(S.pos, i),
 428                             tok = token("comment2", text);
 429                         S.pos = i + 2;
 430                         S.line += text.split("\n").length - 1;
 431                         S.newline_before = text.indexOf("\n") >= 0;
 432                         return tok;
 433                 });
 434         };
 435
 436         function read_regexp() {
 437                 return with_eof_error("Unterminated regular expression", function(){
 438                         var prev_backslash = false, regexp = "", ch, in_class = false;
 439                         while ((ch = next(true))) if (prev_backslash) {
 440                                 regexp += "\\" + ch;
 441                                 prev_backslash = false;
 442                         } else if (ch == "[") {
 443                                 in_class = true;
 444                                 regexp += ch;
 445                         } else if (ch == "]" && in_class) {
 446                                 in_class = false;
 447                                 regexp += ch;
 448                         } else if (ch == "/" && !in_class) {
 449                                 break;
 450                         } else if (ch == "\\") {
 451                                 prev_backslash = true;
 452                         } else {
 453                                 regexp += ch;
 454                         }
 455                         var mods = read_while(function(ch){
 456                                 return HOP(REGEXP_MODIFIERS, ch);
 457                         });
 458                         return token("regexp", [ regexp, mods ]);
 459                 });
 460         };
 461
 462         function read_operator(prefix) {
 463                 function grow(op) {
 464                         var bigger = op + peek();
 465                         if (HOP(OPERATORS, bigger)) {
 466                                 next();
 467                                 return grow(bigger);
 468                         } else {
 469                                 return op;
 470                         }
 471                 };
 472                 return token("operator", grow(prefix || next()));
 473         };
 474
 475         var handle_slash = skip_comments ? function() {
 476                 next();
 477                 var regex_allowed = S.regex_allowed;
 478                 switch (peek()) {
 479                     case "/": read_line_comment(); S.regex_allowed = regex_allowed; return next_token();
 480                     case "*": read_multiline_comment(); S.regex_allowed = regex_allowed; return next_token();
 481                 }
 482                 return S.regex_allowed ? read_regexp() : read_operator("/");
 483         } : function() {
 484                 next();
 485                 switch (peek()) {
 486                     case "/": return read_line_comment();
 487                     case "*": return read_multiline_comment();
 488                 }
 489                 return S.regex_allowed ? read_regexp() : read_operator("/");
 490         };
 491
 492         function handle_dot() {
 493                 next();
 494                 return is_digit(peek())
 495                         ? read_num(".")
 496                         : token("punc", ".");
 497         };
 498
 499         function read_word() {
 500                 var word = read_while(is_identifier_char);
 501                 return !HOP(KEYWORDS, word)
 502                         ? token("name", word)
 503                         : HOP(OPERATORS, word)
 504                         ? token("operator", word)
 505                         : HOP(KEYWORDS_ATOM, word)
 506                         ? token("atom", word)
 507                         : token("keyword", word);
 508         };
 509
 510         function with_eof_error(eof_error, cont) {
 511                 try {
 512                         return cont();
 513                 } catch(ex) {
 514                         if (ex === EX_EOF) parse_error(eof_error);
 515                         else throw ex;
 516                 }
 517         };
 518
 519         function next_token(force_regexp) {
 520                 if (force_regexp)
 521                         return read_regexp();
 522                 skip_whitespace();
 523                 start_token();
 524                 var ch = peek();
 525                 if (!ch) return token("eof");
 526                 if (is_digit(ch)) return read_num();
 527                 if (ch == '"' || ch == "'") return read_string();
 528                 if (HOP(PUNC_CHARS, ch)) return token("punc", next());
 529                 if (ch == ".") return handle_dot();
 530                 if (ch == "/") return handle_slash();
 531                 if (HOP(OPERATOR_CHARS, ch)) return read_operator();
 532                 if (is_identifier_char(ch)) return read_word();
 533                 parse_error("Unexpected character '" + ch + "'");
 534         };
 535
 536         next_token.context = function(nc) {
 537                 if (nc) S = nc;
 538                 return S;
 539         };
 540
 541         return next_token;
 542
 543 };
 544
 545 /* -----[ Parser (constants) ]----- */
 546
 547 var UNARY_PREFIX = array_to_hash([
 548         "typeof",
 549         "void",
 550         "delete",
 551         "--",
 552         "++",
 553         "!",
 554         "~",
 555         "-",
 556         "+"
 557 ]);
 558
 559 var UNARY_POSTFIX = array_to_hash([ "--", "++" ]);
 560
 561 var ASSIGNMENT = (function(a, ret, i){
 562         while (i < a.length) {
 563                 ret[a[i]] = a[i].substr(0, a[i].length - 1);
 564                 i++;
 565         }
 566         return ret;
 567 })(
 568         ["+=", "-=", "/=", "*=", "%=", ">>=", "<<=", ">>>=", "~=", "%=", "|=", "^=", "&="],
 569         { "=": true },
 570         0
 571 );
 572
 573 var PRECEDENCE = (function(a, ret){
 574         for (var i = 0, n = 1; i < a.length; ++i, ++n) {
 575                 var b = a[i];
 576                 for (var j = 0; j < b.length; ++j) {
 577                         ret[b[j]] = n;
 578                 }
 579         }
 580         return ret;
 581 })(
 582         [
 583                 ["||"],
 584                 ["&&"],
 585                 ["|"],
 586                 ["^"],
 587                 ["&"],
 588                 ["==", "===", "!=", "!=="],
 589                 ["<", ">", "<=", ">=", "in", "instanceof"],
 590                 [">>", "<<", ">>>"],
 591                 ["+", "-"],
 592                 ["*", "/", "%"]
 593         ],
 594         {}
 595 );
 596
 597 var STATEMENTS_WITH_LABELS = array_to_hash([ "for", "do", "while", "switch" ]);
 598
 599 var ATOMIC_START_TOKEN = array_to_hash([ "atom", "num", "string", "regexp", "name" ]);
 600
 601 /* -----[ Parser ]----- */
 602
 603 function NodeWithToken(str, start, end) {
 604         this.name = str;
 605         this.start = start;
 606         this.end = end;
 607 };
 608
 609 NodeWithToken.prototype.toString = function() { return this.name; };
 610
 611 function parse($TEXT, strict_mode, embed_tokens) {
 612
 613         var S = {
 614                 input: tokenizer($TEXT, true),
 615                 token: null,
 616                 prev: null,
 617                 peeked: null,
 618                 in_function: 0,
 619                 in_loop: 0,
 620                 labels: []
 621         };
 622
 623         S.token = next();
 624
 625         function is(type, value) {
 626                 return is_token(S.token, type, value);
 627         };
 628
 629         function peek() { return S.peeked || (S.peeked = S.input()); };
 630
 631         function next() {
 632                 S.prev = S.token;
 633                 if (S.peeked) {
 634                         S.token = S.peeked;
 635                         S.peeked = null;
 636                 } else {
 637                         S.token = S.input();
 638                 }
 639                 return S.token;
 640         };
 641
 642         function prev() {
 643                 return S.prev;
 644         };
 645
 646         function croak(msg, line, col, pos) {
 647                 var ctx = S.input.context();
 648                 js_error(msg,
 649                          line != null ? line : ctx.tokline,
 650                          col != null ? col : ctx.tokcol,
 651                          pos != null ? pos : ctx.tokpos);
 652         };
 653
 654         function token_error(token, msg) {
 655                 croak(msg, token.line, token.col);
 656         };
 657
 658         function unexpected(token) {
 659                 if (token == null)
 660                         token = S.token;
 661                 token_error(token, "Unexpected token: " + token.type + " (" + token.value + ")");
 662         };
 663
 664         function expect_token(type, val) {
 665                 if (is(type, val)) {
 666                         return next();
 667                 }
 668                 token_error(S.token, "Unexpected token " + S.token.type + ", expected " + type);
 669         };
 670
 671         function expect(punc) { return expect_token("punc", punc); };
 672
 673         function can_insert_semicolon() {
 674                 return !strict_mode && (
 675                         S.token.nlb || is("eof") || is("punc", "}")
 676                 );
 677         };
 678
 679         function semicolon() {
 680                 if (is("punc", ";")) next();
 681                 else if (!can_insert_semicolon()) unexpected();
 682         };
 683
 684         function as() {
 685                 return slice(arguments);
 686         };
 687
 688         function parenthesised() {
 689                 expect("(");
 690                 var ex = expression();
 691                 expect(")");
 692                 return ex;
 693         };
 694
 695         function add_tokens(str, start, end) {
 696                 return new NodeWithToken(str, start, end);
 697         };
 698
 699         var statement = embed_tokens ? function() {
 700                 var start = S.token;
 701                 var stmt = $statement();
 702                 stmt[0] = add_tokens(stmt[0], start, prev());
 703                 return stmt;
 704         } : $statement;
 705
 706         function $statement() {
 707                 if (is("operator", "/")) {
 708                         S.peeked = null;
 709                         S.token = S.input(true); // force regexp
 710                 }
 711                 switch (S.token.type) {
 712                     case "num":
 713                     case "string":
 714                     case "regexp":
 715                     case "operator":
 716                     case "atom":
 717                         return simple_statement();
 718
 719                     case "name":
 720                         return is_token(peek(), "punc", ":")
 721                                 ? labeled_statement(prog1(S.token.value, next, next))
 722                                 : simple_statement();
 723
 724                     case "punc":
 725                         switch (S.token.value) {
 726                             case "{":
 727                                 return as("block", block_());
 728                             case "[":
 729                             case "(":
 730                                 return simple_statement();
 731                             case ";":
 732                                 next();
 733                                 return as("block");
 734                             default:
 735                                 unexpected();
 736                         }
 737
 738                     case "keyword":
 739                         switch (prog1(S.token.value, next)) {
 740                             case "break":
 741                                 return break_cont("break");
 742
 743                             case "continue":
 744                                 return break_cont("continue");
 745
 746                             case "debugger":
 747                                 semicolon();
 748                                 return as("debugger");
 749
 750                             case "do":
 751                                 return (function(body){
 752                                         expect_token("keyword", "while");
 753                                         return as("do", prog1(parenthesised, semicolon), body);
 754                                 })(in_loop(statement));
 755
 756                             case "for":
 757                                 return for_();
 758
 759                             case "function":
 760                                 return function_(true);
 761
 762                             case "if":
 763                                 return if_();
 764
 765                             case "return":
 766                                 if (S.in_function == 0)
 767                                         croak("'return' outside of function");
 768                                 return as("return",
 769                                           is("punc", ";")
 770                                           ? (next(), null)
 771                                           : can_insert_semicolon()
 772                                           ? null
 773                                           : prog1(expression, semicolon));
 774
 775                             case "switch":
 776                                 return as("switch", parenthesised(), switch_block_());
 777
 778                             case "throw":
 779                                 return as("throw", prog1(expression, semicolon));
 780
 781                             case "try":
 782                                 return try_();
 783
 784                             case "var":
 785                                 return prog1(var_, semicolon);
 786
 787                             case "const":
 788                                 return prog1(const_, semicolon);
 789
 790                             case "while":
 791                                 return as("while", parenthesised(), in_loop(statement));
 792
 793                             case "with":
 794                                 return as("with", parenthesised(), statement());
 795
 796                             default:
 797                                 unexpected();
 798                         }
 799                 }
 800         };
 801
 802         function labeled_statement(label) {
 803                 S.labels.push(label);
 804                 var start = S.token, stat = statement();
 805                 if (strict_mode && !HOP(STATEMENTS_WITH_LABELS, stat[0]))
 806                         unexpected(start);
 807                 S.labels.pop();
 808                 return as("label", label, stat);
 809         };
 810
 811         function simple_statement() {
 812                 return as("stat", prog1(expression, semicolon));
 813         };
 814
 815         function break_cont(type) {
 816                 var name = is("name") ? S.token.value : null;
 817                 if (name != null) {
 818                         next();
 819                         if (!member(name, S.labels))
 820                                 croak("Label " + name + " without matching loop or statement");
 821                 }
 822                 else if (S.in_loop == 0)
 823                         croak(type + " not inside a loop or switch");
 824                 semicolon();
 825                 return as(type, name);
 826         };
 827
 828         function for_() {
 829                 expect("(");
 830                 var has_var = is("keyword", "var");
 831                 if (has_var)
 832                         next();
 833                 if (is("name") && is_token(peek(), "operator", "in")) {
 834                         // for (i in foo)
 835                         var name = S.token.value;
 836                         next(); next();
 837                         var obj = expression();
 838                         expect(")");
 839                         return as("for-in", has_var, name, obj, in_loop(statement));
 840                 } else {
 841                         // classic for
 842                         var init = is("punc", ";") ? null : has_var ? var_() : expression();
 843                         expect(";");
 844                         var test = is("punc", ";") ? null : expression();
 845                         expect(";");
 846                         var step = is("punc", ")") ? null : expression();
 847                         expect(")");
 848                         return as("for", init, test, step, in_loop(statement));
 849                 }
 850         };
 851
 852         function function_(in_statement) {
 853                 var name = is("name") ? prog1(S.token.value, next) : null;
 854                 if (in_statement && !name)
 855                         unexpected();
 856                 expect("(");
 857                 return as(in_statement ? "defun" : "function",
 858                           name,
 859                           // arguments
 860                           (function(first, a){
 861                                   while (!is("punc", ")")) {
 862                                           if (first) first = false; else expect(",");
 863                                           if (!is("name")) unexpected();
 864                                           a.push(S.token.value);
 865                                           next();
 866                                   }
 867                                   next();
 868                                   return a;
 869                           })(true, []),
 870                           // body
 871                           (function(){
 872                                   ++S.in_function;
 873                                   var loop = S.in_loop;
 874                                   S.in_loop = 0;
 875                                   var a = block_();
 876                                   --S.in_function;
 877                                   S.in_loop = loop;
 878                                   return a;
 879                           })());
 880         };
 881
 882         function if_() {
 883                 var cond = parenthesised(), body = statement(), belse;
 884                 if (is("keyword", "else")) {
 885                         next();
 886                         belse = statement();
 887                 }
 888                 return as("if", cond, body, belse);
 889         };
 890
 891         function block_() {
 892                 expect("{");
 893                 var a = [];
 894                 while (!is("punc", "}")) {
 895                         if (is("eof")) unexpected();
 896                         a.push(statement());
 897                 }
 898                 next();
 899                 return a;
 900         };
 901
 902         var switch_block_ = curry(in_loop, function(){
 903                 expect("{");
 904                 var a = [], cur = null;
 905                 while (!is("punc", "}")) {
 906                         if (is("eof")) unexpected();
 907                         if (is("keyword", "case")) {
 908                                 next();
 909                                 cur = [];
 910                                 a.push([ expression(), cur ]);
 911                                 expect(":");
 912                         }
 913                         else if (is("keyword", "default")) {
 914                                 next();
 915                                 expect(":");
 916                                 cur = [];
 917                                 a.push([ null, cur ]);
 918                         }
 919                         else {
 920                                 if (!cur) unexpected();
 921                                 cur.push(statement());
 922                         }
 923                 }
 924                 next();
 925                 return a;
 926         });
 927
 928         function try_() {
 929                 var body = block_(), bcatch, bfinally;
 930                 if (is("keyword", "catch")) {
 931                         next();
 932                         expect("(");
 933                         if (!is("name"))
 934                                 croak("Name expected");
 935                         var name = S.token.value;
 936                         next();
 937                         expect(")");
 938                         bcatch = [ name, block_() ];
 939                 }
 940                 if (is("keyword", "finally")) {
 941                         next();
 942                         bfinally = block_();
 943                 }
 944                 if (!bcatch && !bfinally)
 945                         croak("Missing catch/finally blocks");
 946                 return as("try", body, bcatch, bfinally);
 947         };
 948
 949         function vardefs() {
 950                 var a = [];
 951                 for (;;) {
 952                         if (!is("name"))
 953                                 unexpected();
 954                         var name = S.token.value;
 955                         next();
 956                         if (is("operator", "=")) {
 957                                 next();
 958                                 a.push([ name, expression(false) ]);
 959                         } else {
 960                                 a.push([ name ]);
 961                         }
 962                         if (!is("punc", ","))
 963                                 break;
 964                         next();
 965                 }
 966                 return a;
 967         };
 968
 969         function var_() {
 970                 return as("var", vardefs());
 971         };
 972
 973         function const_() {
 974                 return as("const", vardefs());
 975         };
 976
 977         function new_() {
 978                 var newexp = expr_atom(false), args;
 979                 if (is("punc", "(")) {
 980                         next();
 981                         args = expr_list(")");
 982                 } else {
 983                         args = [];
 984                 }
 985                 return subscripts(as("new", newexp, args), true);
 986         };
 987
 988         function expr_atom(allow_calls) {
 989                 if (is("operator", "new")) {
 990                         next();
 991                         return new_();
 992                 }
 993                 if (is("operator") && HOP(UNARY_PREFIX, S.token.value)) {
 994                         return make_unary("unary-prefix",
 995                                           prog1(S.token.value, next),
 996                                           expr_atom(allow_calls));
 997                 }
 998                 if (is("punc")) {
 999                         switch (S.token.value) {
1000                             case "(":
1001                                 next();
1002                                 return subscripts(prog1(expression, curry(expect, ")")), allow_calls);
1003                             case "[":
1004                                 next();
1005                                 return subscripts(array_(), allow_calls);
1006                             case "{":
1007                                 next();
1008                                 return subscripts(object_(), allow_calls);
1009                         }
1010                         unexpected();
1011                 }
1012                 if (is("keyword", "function")) {
1013                         next();
1014                         return subscripts(function_(false), allow_calls);
1015                 }
1016                 if (HOP(ATOMIC_START_TOKEN, S.token.type)) {
1017                         var atom = S.token.type == "regexp"
1018                                 ? as("regexp", S.token.value[0], S.token.value[1])
1019                                 : as(S.token.type, S.token.value);
1020                         return subscripts(prog1(atom, next), allow_calls);
1021                 }
1022                 unexpected();
1023         };
1024
1025         function expr_list(closing, allow_trailing_comma) {
1026                 var first = true, a = [];
1027                 while (!is("punc", closing)) {
1028                         if (first) first = false; else expect(",");
1029                         if (allow_trailing_comma && is("punc", closing))
1030                                 break;
1031                         a.push(expression(false));
1032                 }
1033                 next();
1034                 return a;
1035         };
1036
1037         function array_() {
1038                 return as("array", expr_list("]", !strict_mode));
1039         };
1040
1041         function object_() {
1042                 var first = true, a = [];
1043                 while (!is("punc", "}")) {
1044                         if (first) first = false; else expect(",");
1045                         if (!strict_mode && is("punc", "}"))
1046                                 // allow trailing comma
1047                                 break;
1048                         var type = S.token.type;
1049                         var name = as_property_name();
1050                         if (type == "name" && (name == "get" || name == "set") && !is("punc", ":")) {
1051                                 a.push([ as_name(), function_(false), name ]);
1052                         } else {
1053                                 expect(":");
1054                                 a.push([ name, expression(false) ]);
1055                         }
1056                 }
1057                 next();
1058                 return as("object", a);
1059         };
1060
1061         function as_property_name() {
1062                 switch (S.token.type) {
1063                     case "num":
1064                     case "string":
1065                         return prog1(S.token.value, next);
1066                 }
1067                 return as_name();
1068         };
1069
1070         function as_name() {
1071                 switch (S.token.type) {
1072                     case "name":
1073                     case "operator":
1074                     case "keyword":
1075                     case "atom":
1076                         return prog1(S.token.value, next);
1077                     default:
1078                         unexpected();
1079                 }
1080         };
1081
1082         function subscripts(expr, allow_calls) {
1083                 if (is("punc", ".")) {
1084                         next();
1085                         return subscripts(as("dot", expr, as_name()), allow_calls);
1086                 }
1087                 if (is("punc", "[")) {
1088                         next();
1089                         return subscripts(as("sub", expr, prog1(expression, curry(expect, "]"))), allow_calls);
1090                 }
1091                 if (allow_calls && is("punc", "(")) {
1092                         next();
1093                         return subscripts(as("call", expr, expr_list(")")), true);
1094                 }
1095                 if (allow_calls && is("operator") && HOP(UNARY_POSTFIX, S.token.value)) {
1096                         return prog1(curry(make_unary, "unary-postfix", S.token.value, expr),
1097                                      next);
1098                 }
1099                 return expr;
1100         };
1101
1102         function make_unary(tag, op, expr) {
1103                 if ((op == "++" || op == "--") && !is_assignable(expr))
1104                         croak("Invalid use of " + op + " operator");
1105                 return as(tag, op, expr);
1106         };
1107
1108         function expr_op(left, min_prec) {
1109                 var op = is("operator") ? S.token.value : null;
1110                 var prec = op != null ? PRECEDENCE[op] : null;
1111                 if (prec != null && prec > min_prec) {
1112                         next();
1113                         var right = expr_op(expr_atom(true), prec);
1114                         return expr_op(as("binary", op, left, right), min_prec);
1115                 }
1116                 return left;
1117         };
1118
1119         function expr_ops() {
1120                 return expr_op(expr_atom(true), 0);
1121         };
1122
1123         function maybe_conditional() {
1124                 var expr = expr_ops();
1125                 if (is("operator", "?")) {
1126                         next();
1127                         var yes = expression(false);
1128                         expect(":");
1129                         return as("conditional", expr, yes, expression(false));
1130                 }
1131                 return expr;
1132         };
1133
1134         function is_assignable(expr) {
1135                 switch (expr[0]) {
1136                     case "dot":
1137                     case "sub":
1138                         return true;
1139                     case "name":
1140                         return expr[1] != "this";
1141                 }
1142         };
1143
1144         function maybe_assign() {
1145                 var left = maybe_conditional(), val = S.token.value;
1146                 if (is("operator") && HOP(ASSIGNMENT, val)) {
1147                         if (is_assignable(left)) {
1148                                 next();
1149                                 return as("assign", ASSIGNMENT[val], left, maybe_assign());
1150                         }
1151                         croak("Invalid assignment");
1152                 }
1153                 return left;
1154         };
1155
1156         function expression(commas) {
1157                 if (arguments.length == 0)
1158                         commas = true;
1159                 var expr = maybe_assign();
1160                 if (commas && is("punc", ",")) {
1161                         next();
1162                         return as("seq", expr, expression());
1163                 }
1164                 return expr;
1165         };
1166
1167         function in_loop(cont) {
1168                 try {
1169                         ++S.in_loop;
1170                         return cont();
1171                 } finally {
1172                         --S.in_loop;
1173                 }
1174         };
1175
1176         return as("toplevel", (function(a){
1177                 while (!is("eof"))
1178                         a.push(statement());
1179                 return a;
1180         })([]));
1181
1182 };
1183
1184 /* -----[ Utilities ]----- */
1185
1186 function curry(f) {
1187         var args = slice(arguments, 1);
1188         return function() { return f.apply(this, args.concat(slice(arguments))); };
1189 };
1190
1191 function prog1(ret) {
1192         if (ret instanceof Function)
1193                 ret = ret();
1194         for (var i = 1, n = arguments.length; --n > 0; ++i)
1195                 arguments[i]();
1196         return ret;
1197 };
1198
1199 function array_to_hash(a) {
1200         var ret = {};
1201         for (var i = 0; i < a.length; ++i)
1202                 ret[a[i]] = true;
1203         return ret;
1204 };
1205
1206 function slice(a, start) {
1207         return Array.prototype.slice.call(a, start == null ? 0 : start);
1208 };
1209
1210 function characters(str) {
1211         return str.split("");
1212 };
1213
1214 function member(name, array) {
1215         for (var i = array.length; --i >= 0;)
1216                 if (array[i] === name)
1217                         return true;
1218         return false;
1219 };
1220
1221 function HOP(obj, prop) {
1222         return Object.prototype.hasOwnProperty.call(obj, prop);
1223 };
1224
1225 /* -----[ Exports ]----- */
1226
1227 exports.tokenizer = tokenizer;
1228 exports.parse = parse;
1229 exports.slice = slice;
1230 exports.curry = curry;
1231 exports.member = member;
1232 exports.array_to_hash = array_to_hash;
1233 exports.PRECEDENCE = PRECEDENCE;
1234 exports.KEYWORDS_ATOM = KEYWORDS_ATOM;
1235 exports.RESERVED_WORDS = RESERVED_WORDS;
1236 exports.KEYWORDS = KEYWORDS;
1237 exports.ATOMIC_START_TOKEN = ATOMIC_START_TOKEN;
1238 exports.OPERATORS = OPERATORS;
1239 exports.is_alphanumeric_char = is_alphanumeric_char;