Makes sure all converters keys are lowercased before any conversion is taking place...
[jquery.git] / 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;