Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Browse files

Solved merge conflicts

  • Loading branch information...
commit 9dedcc30c0bbc0b6d8ddf000e672bd110e351c69 2 parents 0fb60df + f5131ff
JOHAN GUSTAFSSON authored
Showing with 737 additions and 736 deletions.
  1. +14 −14 haskell.abs.js
  2. +67 −67 haskell.interpreter.js
  3. +1 −0  haskell.parser.js
  4. +655 −655 lib/jsparse.js
View
28 haskell.abs.js
@@ -1,15 +1,15 @@
-haskell.abs.Program = function() {
-
-};
-
-haskell.abs.Statement = function() {
-
-};
-
-haskell.abs.Expression = function() {
-
-};
-
-haskell.abs.Value = function() {
-
+haskell.abs.Program = function() {
+
+};
+
+haskell.abs.Statement = function() {
+
+};
+
+haskell.abs.Expression = function() {
+
+};
+
+haskell.abs.Value = function() {
+
}
View
134 haskell.interpreter.js
@@ -1,68 +1,68 @@
-function isInteger(x) {
- var y = parseInt(x);
- if (isNaN(y)) {
- return false;
- }
- return x== y && x.toString() == y.toString();
-}
-
-haskell.interpreter.interpret = function(env, ast) {
- var interpret = haskell.interpreter.interpret;
-
- if(ast.fun_name != undefined) {
- // eval function
- var f = env.get_symbol(ast.fun_name);
- env.set_arg_list(ast.arguments);
- var result = interpret(env, f.value);
- return result;
- } else if (ast.arguments != undefined) {
- for (var i = 0; i < ast.arguments.length; i++) {
- var arg = ast.arguments[i];
-
- if (env.arg_list.length > i) {
- var value = env.arg_list[i];
- value = value.toString();
- value = haskell.parser.parse(value, true).ast;
- env.set_symbol(arg, value, false);
- } else if (!env.exists_symbol(arg)) {
- var value = prompt("enter a value for " + arg);
- value = haskell.parser.parse(value, false).ast;
- env.set_symbol(arg, value, false);
- }
- }
-
- return interpret(env, ast.expr);
- } else if (ast.symbol != undefined) {
- switch (ast.symbol) {
- case '+':
- return interpret(env, ast.lhs) + interpret(env, ast.rhs);
- break;
- case '-':
- return interpret(env, ast.lhs) - interpret(env, ast.rhs);
- break;
- case '*':
- return interpret(env, ast.lhs) * interpret(env, ast.rhs);
- break;
- case '/':
- return interpret(env, ast.lhs) / interpret(env, ast.rhs);
- break;
- default:
- console.log("unknown symbol %o ast: %o", ast.symbol, ast);
- break;
- }
- } else {
- if (isInteger(ast)) {
- return ast;
- } else {
- // ast is a symbol so look it up
- var symbol = env.get_symbol(ast);
- if (symbol.evaluated) {
- return symbol.value;
- } else {
- var result = interpret(new haskell.env(), symbol.value);
- env.set_symbol(ast, result, true);
- return result;
- }
- }
- }
+function isInteger(x) {
+ var y = parseInt(x);
+ if (isNaN(y)) {
+ return false;
+ }
+ return x== y && x.toString() == y.toString();
+}
+
+haskell.interpreter.interpret = function(env, ast) {
+ var interpret = haskell.interpreter.interpret;
+
+ if(ast.fun_name != undefined) {
+ // eval function
+ var f = env.get_symbol(ast.fun_name);
+ env.set_arg_list(ast.arguments);
+ var result = interpret(env, f.value);
+ return result;
+ } else if (ast.arguments != undefined) {
+ for (var i = 0; i < ast.arguments.length; i++) {
+ var arg = ast.arguments[i];
+
+ if (env.arg_list.length > i) {
+ var value = env.arg_list[i];
+ value = value.toString();
+ value = haskell.parser.parse(value, true).ast;
+ env.set_symbol(arg, value, false);
+ } else if (!env.exists_symbol(arg)) {
+ var value = prompt("enter a value for " + arg);
+ value = haskell.parser.parse(value, false).ast;
+ env.set_symbol(arg, value, false);
+ }
+ }
+
+ return interpret(env, ast.expr);
+ } else if (ast.symbol != undefined) {
+ switch (ast.symbol) {
+ case '+':
+ return interpret(env, ast.lhs) + interpret(env, ast.rhs);
+ break;
+ case '-':
+ return interpret(env, ast.lhs) - interpret(env, ast.rhs);
+ break;
+ case '*':
+ return interpret(env, ast.lhs) * interpret(env, ast.rhs);
+ break;
+ case '/':
+ return interpret(env, ast.lhs) / interpret(env, ast.rhs);
+ break;
+ default:
+ console.log("unknown symbol %o ast: %o", ast.symbol, ast);
+ break;
+ }
+ } else {
+ if (isInteger(ast)) {
+ return ast;
+ } else {
+ // ast is a symbol so look it up
+ var symbol = env.get_symbol(ast);
+ if (symbol.evaluated) {
+ return symbol.value;
+ } else {
+ var result = interpret(new haskell.env(), symbol.value);
+ env.set_symbol(ast, result, true);
+ return result;
+ }
+ }
+ }
}
View
1  haskell.parser.js
@@ -22,6 +22,7 @@
* \return The ast
*/
haskell.parser.parse = function(code) {
+
var integer = action(repeat1(range('0', '9')), function(ast) { return new haskell.ast.Num(parseInt(ast.join(""))); });
var ident = action(repeat1(range('a', 'z')), function(ast) { return ast.join(""); });
View
1,310 lib/jsparse.js
@@ -1,655 +1,655 @@
-// Copyright (C) 2007 Chris Double.
-//
-// Redistribution and use in source and binary forms, with or without
-// modification, are permitted provided that the following conditions are met:
-//
-// 1. Redistributions of source code must retain the above copyright notice,
-// this list of conditions and the following disclaimer.
-//
-// 2. Redistributions in binary form must reproduce the above copyright notice,
-// this list of conditions and the following disclaimer in the documentation
-// and/or other materials provided with the distribution.
-//
-// THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
-// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
-// FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
-// DEVELOPERS AND CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
-// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
-// OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
-// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
-// OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
-// ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-//
-function identity(x) {
- return x;
-}
-
-function foldl(f, initial, seq) {
- for(var i=0; i< seq.length; ++i)
- initial = f(initial, seq[i]);
- return initial;
-}
-
-var memoize = true;
-
-function ParseState(input, index) {
- this.input = input;
- this.index = index || 0;
- this.length = input.length - this.index;
- this.cache = { };
- return this;
-}
-
-ParseState.prototype.from = function(index) {
- var r = new ParseState(this.input, this.index + index);
- r.cache = this.cache;
- r.length = this.length - index;
- return r;
-}
-
-ParseState.prototype.substring = function(start, end) {
- return this.input.substring(start + this.index, (end || this.length) + this.index);
-}
-
-ParseState.prototype.trimLeft = function() {
- var s = this.substring(0);
- var m = s.match(/^\s+/);
- return m ? this.from(m[0].length) : this;
-}
-
-ParseState.prototype.at = function(index) {
- return this.input.charAt(this.index + index);
-}
-
-ParseState.prototype.toString = function() {
- return 'PS"' + this.substring(0) + '"';
-}
-
-ParseState.prototype.getCached = function(pid) {
- if(!memoize)
- return false;
-
- var p = this.cache[pid];
- if(p)
- return p[this.index];
- else
- return false;
-}
-
-ParseState.prototype.putCached = function(pid, cached) {
- if(!memoize)
- return false;
-
- var p = this.cache[pid];
- if(p)
- p[this.index] = cached;
- else {
- p = this.cache[pid] = { };
- p[this.index] = cached;
- }
-}
-
-function ps(str) {
- return new ParseState(str);
-}
-
-// 'r' is the remaining string to be parsed.
-// 'matched' is the portion of the string that
-// was successfully matched by the parser.
-// 'ast' is the AST returned by the successfull parse.
-function make_result(r, matched, ast) {
- return { remaining: r, matched: matched, ast: ast };
-}
-
-var parser_id = 0;
-
-// 'token' is a parser combinator that given a string, returns a parser
-// that parses that string value. The AST contains the string that was parsed.
-function token(s) {
- var pid = parser_id++;
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
-
- var r = state.length >= s.length && state.substring(0,s.length) == s;
- if(r)
- cached = { remaining: state.from(s.length), matched: s, ast: s };
- else
- cached = false;
- savedState.putCached(pid, cached);
- return cached;
- };
-}
-
-// Like 'token' but for a single character. Returns a parser that given a string
-// containing a single character, parses that character value.
-function ch(c) {
- var pid = parser_id++;
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
- var r = state.length >= 1 && state.at(0) == c;
- if(r)
- cached = { remaining: state.from(1), matched: c, ast: c };
- else
- cached = false;
- savedState.putCached(pid, cached);
- return cached;
- };
-}
-
-// 'range' is a parser combinator that returns a single character parser
-// (similar to 'ch'). It parses single characters that are in the inclusive
-// range of the 'lower' and 'upper' bounds ("a" to "z" for example).
-function range(lower, upper) {
- var pid = parser_id++;
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
-
- if(state.length < 1)
- cached = false;
- else {
- var ch = state.at(0);
- if(ch >= lower && ch <= upper)
- cached = { remaining: state.from(1), matched: ch, ast: ch };
- else
- cached = false;
- }
- savedState.putCached(pid, cached);
- return cached;
- };
-}
-
-// Helper function to convert string literals to token parsers
-// and perform other implicit parser conversions.
-function toParser(p) {
- return (typeof(p) == "string") ? token(p) : p;
-}
-
-// Parser combinator that returns a parser that
-// skips whitespace before applying parser.
-function whitespace(p) {
- var p = toParser(p);
- var pid = parser_id++;
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
-
- cached = p(state.trimLeft());
- savedState.putCached(pid, cached);
- return cached;
- };
-}
-
-// Parser combinator that passes the AST generated from the parser 'p'
-// to the function 'f'. The result of 'f' is used as the AST in the result.
-function action(p, f) {
- var p = toParser(p);
- var pid = parser_id++;
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
-
- var x = p(state);
- if(x) {
- x.ast = f(x.ast);
- cached = x;
- }
- else {
- cached = false;
- }
- savedState.putCached(pid, cached);
- return cached;
- };
-}
-
-// Given a parser that produces an array as an ast, returns a
-// parser that produces an ast with the array joined by a separator.
-function join_action(p, sep) {
- return action(p, function(ast) { return ast.join(sep); });
-}
-
-// Given an ast of the form [ Expression, [ a, b, ...] ], convert to
-// [ [ [ Expression [ a ] ] b ] ... ]
-// This is used for handling left recursive entries in the grammar. e.g.
-// MemberExpression:
-// PrimaryExpression
-// FunctionExpression
-// MemberExpression [ Expression ]
-// MemberExpression . Identifier
-// new MemberExpression Arguments
-function left_factor(ast) {
- return foldl(function(v, action) {
- return [ v, action ];
- },
- ast[0],
- ast[1]);
-}
-
-// Return a parser that left factors the ast result of the original
-// parser.
-function left_factor_action(p) {
- return action(p, left_factor);
-}
-
-// 'negate' will negate a single character parser. So given 'ch("a")' it will successfully
-// parse any character except for 'a'. Or 'negate(range("a", "z"))' will successfully parse
-// anything except the lowercase characters a-z.
-function negate(p) {
- var p = toParser(p);
- var pid = parser_id++;
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
-
- if(state.length >= 1) {
- var r = p(state);
- if(!r)
- cached = make_result(state.from(1), state.at(0), state.at(0));
- else
- cached = false;
- }
- else {
- cached = false;
- }
- savedState.putCached(pid, cached);
- return cached;
- };
-}
-
-// 'end_p' is a parser that is successful if the input string is empty (ie. end of parse).
-function end_p(state) {
- if(state.length == 0)
- return make_result(state, undefined, undefined);
- else
- return false;
-}
-
-// 'nothing_p' is a parser that always fails.
-function nothing_p(state) {
- return false;
-}
-
-// 'sequence' is a parser combinator that processes a number of parsers in sequence.
-// It can take any number of arguments, each one being a parser. The parser that 'sequence'
-// returns succeeds if all the parsers in the sequence succeeds. It fails if any of them fail.
-function sequence() {
- var parsers = [];
- for(var i = 0; i < arguments.length; ++i)
- parsers.push(toParser(arguments[i]));
- var pid = parser_id++;
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached) {
- return cached;
- }
-
- var ast = [];
- var matched = "";
- var i;
- for(i=0; i< parsers.length; ++i) {
- var parser = parsers[i];
- var result = parser(state);
- if(result) {
- state = result.remaining;
- if(result.ast != undefined) {
- ast.push(result.ast);
- matched = matched + result.matched;
- }
- }
- else {
- break;
- }
- }
- if(i == parsers.length) {
- cached = make_result(state, matched, ast);
- }
- else
- cached = false;
- savedState.putCached(pid, cached);
- return cached;
- };
-}
-
-// Like sequence, but ignores whitespace between individual parsers.
-function wsequence() {
- var parsers = [];
- for(var i=0; i < arguments.length; ++i) {
- parsers.push(whitespace(toParser(arguments[i])));
- }
- return sequence.apply(null, parsers);
-}
-
-// 'choice' is a parser combinator that provides a choice between other parsers.
-// It takes any number of parsers as arguments and returns a parser that will try
-// each of the given parsers in order. The first one that succeeds results in a
-// successfull parse. It fails if all parsers fail.
-function choice() {
- var parsers = [];
- for(var i = 0; i < arguments.length; ++i)
- parsers.push(toParser(arguments[i]));
- var pid = parser_id++;
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached) {
- return cached;
- }
- var i;
- for(i=0; i< parsers.length; ++i) {
- var parser=parsers[i];
- var result = parser(state);
- if(result) {
- break;
- }
- }
- if(i == parsers.length)
- cached = false;
- else
- cached = result;
- savedState.putCached(pid, cached);
- return cached;
- }
-}
-
-// 'butnot' is a parser combinator that takes two parsers, 'p1' and 'p2'.
-// It returns a parser that succeeds if 'p1' matches and 'p2' does not, or
-// 'p1' matches and the matched text is longer that p2's.
-// Useful for things like: butnot(IdentifierName, ReservedWord)
-function butnot(p1,p2) {
- var p1 = toParser(p1);
- var p2 = toParser(p2);
- var pid = parser_id++;
-
- // match a but not b. if both match and b's matched text is shorter
- // than a's, a failed match is made
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
-
- var br = p2(state);
- if(!br) {
- cached = p1(state);
- } else {
- var ar = p1(state);
- if(ar.matched.length > br.matched.length)
- cached = ar;
- else
- cached = false;
- }
- savedState.putCached(pid, cached);
- return cached;
- }
-}
-
-// 'difference' is a parser combinator that takes two parsers, 'p1' and 'p2'.
-// It returns a parser that succeeds if 'p1' matches and 'p2' does not. If
-// both match then if p2's matched text is shorter than p1's it is successfull.
-function difference(p1,p2) {
- var p1 = toParser(p1);
- var p2 = toParser(p2);
- var pid = parser_id++;
-
- // match a but not b. if both match and b's matched text is shorter
- // than a's, a successfull match is made
- return function(state) {
- var savedState = sate;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
-
- var br = p2(state);
- if(!br) {
- cached = p1(state);
- } else {
- var ar = p1(state);
- if(ar.matched.length >= br.matched.length)
- cached = br;
- else
- cached = ar;
- }
- savedState.putCached(pid, cached);
- return cached;
- }
-}
-
-
-// 'xor' is a parser combinator that takes two parsers, 'p1' and 'p2'.
-// It returns a parser that succeeds if 'p1' or 'p2' match but fails if
-// they both match.
-function xor(p1, p2) {
- var p1 = toParser(p1);
- var p2 = toParser(p2);
- var pid = parser_id++;
-
- // match a or b but not both
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
-
- var ar = p1(state);
- var br = p2(state);
- if(ar && br)
- cached = false;
- else
- cached = ar || br;
- savedState.putCached(pid, cached);
- return cached;
- }
-}
-
-// A parser combinator that takes one parser. It returns a parser that
-// looks for zero or more matches of the original parser.
-function repeat0(p) {
- var p = toParser(p);
- var pid = parser_id++;
-
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached) {
- return cached;
- }
-
- var ast = [];
- var matched = "";
- var result;
- while(result = p(state)) {
- ast.push(result.ast);
- matched = matched + result.matched;
- if(result.remaining.index == state.index)
- break;
- state = result.remaining;
- }
- cached = make_result(state, matched, ast);
- savedState.putCached(pid, cached);
- return cached;
- }
-}
-
-// A parser combinator that takes one parser. It returns a parser that
-// looks for one or more matches of the original parser.
-function repeat1(p) {
- var p = toParser(p);
- var pid = parser_id++;
-
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
-
- var ast = [];
- var matched = "";
- var result= p(state);
- if(!result)
- cached = false;
- else {
- while(result) {
- ast.push(result.ast);
- matched = matched + result.matched;
- if(result.remaining.index == state.index)
- break;
- state = result.remaining;
- result = p(state);
- }
- cached = make_result(state, matched, ast);
- }
- savedState.putCached(pid, cached);
- return cached;
- }
-}
-
-// A parser combinator that takes one parser. It returns a parser that
-// matches zero or one matches of the original parser.
-function optional(p) {
- var p = toParser(p);
- var pid = parser_id++;
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
- var r = p(state);
- cached = r || make_result(state, "", false);
- savedState.putCached(pid, cached);
- return cached;
- }
-}
-
-// A parser combinator that ensures that the given parser succeeds but
-// ignores its result. This can be useful for parsing literals that you
-// don't want to appear in the ast. eg:
-// sequence(expect("("), Number, expect(")")) => ast: Number
-function expect(p) {
- return action(p, function(ast) { return undefined; });
-}
-
-function chain(p, s, f) {
- var p = toParser(p);
-
- return action(sequence(p, repeat0(action(sequence(s, p), f))),
- function(ast) { return [ast[0]].concat(ast[1]); });
-}
-
-// A parser combinator to do left chaining and evaluation. Like 'chain', it expects a parser
-// for an item and for a seperator. The seperator parser's AST result should be a function
-// of the form: function(lhs,rhs) { return x; }
-// Where 'x' is the result of applying some operation to the lhs and rhs AST's from the item
-// parser.
-function chainl(p, s) {
- var p = toParser(p);
- return action(sequence(p, repeat0(sequence(s, p))),
- function(ast) {
- return foldl(function(v, action) { return action[0](v, action[1]); }, ast[0], ast[1]);
- });
-}
-
-// A parser combinator that returns a parser that matches lists of things. The parser to
-// match the list item and the parser to match the seperator need to
-// be provided. The AST is the array of matched items.
-function list(p, s) {
- return chain(p, s, function(ast) { return ast[1]; });
-}
-
-// Like list, but ignores whitespace between individual parsers.
-function wlist() {
- var parsers = [];
- for(var i=0; i < arguments.length; ++i) {
- parsers.push(whitespace(arguments[i]));
- }
- return list.apply(null, parsers);
-}
-
-// A parser that always returns a zero length match
-function epsilon_p(state) {
- return make_result(state, "", undefined);
-}
-
-// Allows attaching of a function anywhere in the grammer. If the function returns
-// true then parse succeeds otherwise it fails. Can be used for testing if a symbol
-// is in the symbol table, etc.
-function semantic(f) {
- var pid = parser_id++;
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
- cached = f() ? make_result(state, "", undefined) : false;
- savedState.putCached(pid, cached);
- return cached;
- }
-}
-
-// The and predicate asserts that a certain conditional
-// syntax is satisfied before evaluating another production. Eg:
-// sequence(and("0"), oct_p)
-// (if a leading zero, then parse octal)
-// It succeeds if 'p' succeeds and fails if 'p' fails. It never
-// consume any input however, and doesn't put anything in the resulting
-// AST.
-function and(p) {
- var p = toParser(p);
- var pid = parser_id++;
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
- var r = p(state);
- cached = r ? make_result(state, "", undefined) : false;
- savedState.putCached(pid, cached);
- return cached;
- }
-}
-
-// The opposite of 'and'. It fails if 'p' succeeds and succeeds if
-// 'p' fails. It never consumes any input. This combined with 'and' can
-// be used for 'lookahead' and disambiguation of cases.
-//
-// Compare:
-// sequence("a",choice("+","++"),"b")
-// parses a+b
-// but not a++b because the + matches the first part and peg's don't
-// backtrack to other choice options if they succeed but later things fail.
-//
-// sequence("a",choice(sequence("+", not("+")),"++"),"b")
-// parses a+b
-// parses a++b
-//
-function not(p) {
- var p = toParser(p);
- var pid = parser_id++;
- return function(state) {
- var savedState = state;
- var cached = savedState.getCached(pid);
- if(cached)
- return cached;
- cached = p(state) ? false : make_result(state, "", undefined);
- savedState.putCached(pid, cached);
- return cached;
- }
-}
-
-var ws = whitespace;
-
+// Copyright (C) 2007 Chris Double.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// 1. Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+//
+// 2. Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+//
+// THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
+// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
+// FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+// DEVELOPERS AND CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
+// OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
+// OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+// ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+//
+function identity(x) {
+ return x;
+}
+
+function foldl(f, initial, seq) {
+ for(var i=0; i< seq.length; ++i)
+ initial = f(initial, seq[i]);
+ return initial;
+}
+
+var memoize = true;
+
+function ParseState(input, index) {
+ this.input = input;
+ this.index = index || 0;
+ this.length = input.length - this.index;
+ this.cache = { };
+ return this;
+}
+
+ParseState.prototype.from = function(index) {
+ var r = new ParseState(this.input, this.index + index);
+ r.cache = this.cache;
+ r.length = this.length - index;
+ return r;
+}
+
+ParseState.prototype.substring = function(start, end) {
+ return this.input.substring(start + this.index, (end || this.length) + this.index);
+}
+
+ParseState.prototype.trimLeft = function() {
+ var s = this.substring(0);
+ var m = s.match(/^\s+/);
+ return m ? this.from(m[0].length) : this;
+}
+
+ParseState.prototype.at = function(index) {
+ return this.input.charAt(this.index + index);
+}
+
+ParseState.prototype.toString = function() {
+ return 'PS"' + this.substring(0) + '"';
+}
+
+ParseState.prototype.getCached = function(pid) {
+ if(!memoize)
+ return false;
+
+ var p = this.cache[pid];
+ if(p)
+ return p[this.index];
+ else
+ return false;
+}
+
+ParseState.prototype.putCached = function(pid, cached) {
+ if(!memoize)
+ return false;
+
+ var p = this.cache[pid];
+ if(p)
+ p[this.index] = cached;
+ else {
+ p = this.cache[pid] = { };
+ p[this.index] = cached;
+ }
+}
+
+function ps(str) {
+ return new ParseState(str);
+}
+
+// 'r' is the remaining string to be parsed.
+// 'matched' is the portion of the string that
+// was successfully matched by the parser.
+// 'ast' is the AST returned by the successfull parse.
+function make_result(r, matched, ast) {
+ return { remaining: r, matched: matched, ast: ast };
+}
+
+var parser_id = 0;
+
+// 'token' is a parser combinator that given a string, returns a parser
+// that parses that string value. The AST contains the string that was parsed.
+function token(s) {
+ var pid = parser_id++;
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+
+ var r = state.length >= s.length && state.substring(0,s.length) == s;
+ if(r)
+ cached = { remaining: state.from(s.length), matched: s, ast: s };
+ else
+ cached = false;
+ savedState.putCached(pid, cached);
+ return cached;
+ };
+}
+
+// Like 'token' but for a single character. Returns a parser that given a string
+// containing a single character, parses that character value.
+function ch(c) {
+ var pid = parser_id++;
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+ var r = state.length >= 1 && state.at(0) == c;
+ if(r)
+ cached = { remaining: state.from(1), matched: c, ast: c };
+ else
+ cached = false;
+ savedState.putCached(pid, cached);
+ return cached;
+ };
+}
+
+// 'range' is a parser combinator that returns a single character parser
+// (similar to 'ch'). It parses single characters that are in the inclusive
+// range of the 'lower' and 'upper' bounds ("a" to "z" for example).
+function range(lower, upper) {
+ var pid = parser_id++;
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+
+ if(state.length < 1)
+ cached = false;
+ else {
+ var ch = state.at(0);
+ if(ch >= lower && ch <= upper)
+ cached = { remaining: state.from(1), matched: ch, ast: ch };
+ else
+ cached = false;
+ }
+ savedState.putCached(pid, cached);
+ return cached;
+ };
+}
+
+// Helper function to convert string literals to token parsers
+// and perform other implicit parser conversions.
+function toParser(p) {
+ return (typeof(p) == "string") ? token(p) : p;
+}
+
+// Parser combinator that returns a parser that
+// skips whitespace before applying parser.
+function whitespace(p) {
+ var p = toParser(p);
+ var pid = parser_id++;
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+
+ cached = p(state.trimLeft());
+ savedState.putCached(pid, cached);
+ return cached;
+ };
+}
+
+// Parser combinator that passes the AST generated from the parser 'p'
+// to the function 'f'. The result of 'f' is used as the AST in the result.
+function action(p, f) {
+ var p = toParser(p);
+ var pid = parser_id++;
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+
+ var x = p(state);
+ if(x) {
+ x.ast = f(x.ast);
+ cached = x;
+ }
+ else {
+ cached = false;
+ }
+ savedState.putCached(pid, cached);
+ return cached;
+ };
+}
+
+// Given a parser that produces an array as an ast, returns a
+// parser that produces an ast with the array joined by a separator.
+function join_action(p, sep) {
+ return action(p, function(ast) { return ast.join(sep); });
+}
+
+// Given an ast of the form [ Expression, [ a, b, ...] ], convert to
+// [ [ [ Expression [ a ] ] b ] ... ]
+// This is used for handling left recursive entries in the grammar. e.g.
+// MemberExpression:
+// PrimaryExpression
+// FunctionExpression
+// MemberExpression [ Expression ]
+// MemberExpression . Identifier
+// new MemberExpression Arguments
+function left_factor(ast) {
+ return foldl(function(v, action) {
+ return [ v, action ];
+ },
+ ast[0],
+ ast[1]);
+}
+
+// Return a parser that left factors the ast result of the original
+// parser.
+function left_factor_action(p) {
+ return action(p, left_factor);
+}
+
+// 'negate' will negate a single character parser. So given 'ch("a")' it will successfully
+// parse any character except for 'a'. Or 'negate(range("a", "z"))' will successfully parse
+// anything except the lowercase characters a-z.
+function negate(p) {
+ var p = toParser(p);
+ var pid = parser_id++;
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+
+ if(state.length >= 1) {
+ var r = p(state);
+ if(!r)
+ cached = make_result(state.from(1), state.at(0), state.at(0));
+ else
+ cached = false;
+ }
+ else {
+ cached = false;
+ }
+ savedState.putCached(pid, cached);
+ return cached;
+ };
+}
+
+// 'end_p' is a parser that is successful if the input string is empty (ie. end of parse).
+function end_p(state) {
+ if(state.length == 0)
+ return make_result(state, undefined, undefined);
+ else
+ return false;
+}
+
+// 'nothing_p' is a parser that always fails.
+function nothing_p(state) {
+ return false;
+}
+
+// 'sequence' is a parser combinator that processes a number of parsers in sequence.
+// It can take any number of arguments, each one being a parser. The parser that 'sequence'
+// returns succeeds if all the parsers in the sequence succeeds. It fails if any of them fail.
+function sequence() {
+ var parsers = [];
+ for(var i = 0; i < arguments.length; ++i)
+ parsers.push(toParser(arguments[i]));
+ var pid = parser_id++;
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached) {
+ return cached;
+ }
+
+ var ast = [];
+ var matched = "";
+ var i;
+ for(i=0; i< parsers.length; ++i) {
+ var parser = parsers[i];
+ var result = parser(state);
+ if(result) {
+ state = result.remaining;
+ if(result.ast != undefined) {
+ ast.push(result.ast);
+ matched = matched + result.matched;
+ }
+ }
+ else {
+ break;
+ }
+ }
+ if(i == parsers.length) {
+ cached = make_result(state, matched, ast);
+ }
+ else
+ cached = false;
+ savedState.putCached(pid, cached);
+ return cached;
+ };
+}
+
+// Like sequence, but ignores whitespace between individual parsers.
+function wsequence() {
+ var parsers = [];
+ for(var i=0; i < arguments.length; ++i) {
+ parsers.push(whitespace(toParser(arguments[i])));
+ }
+ return sequence.apply(null, parsers);
+}
+
+// 'choice' is a parser combinator that provides a choice between other parsers.
+// It takes any number of parsers as arguments and returns a parser that will try
+// each of the given parsers in order. The first one that succeeds results in a
+// successfull parse. It fails if all parsers fail.
+function choice() {
+ var parsers = [];
+ for(var i = 0; i < arguments.length; ++i)
+ parsers.push(toParser(arguments[i]));
+ var pid = parser_id++;
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached) {
+ return cached;
+ }
+ var i;
+ for(i=0; i< parsers.length; ++i) {
+ var parser=parsers[i];
+ var result = parser(state);
+ if(result) {
+ break;
+ }
+ }
+ if(i == parsers.length)
+ cached = false;
+ else
+ cached = result;
+ savedState.putCached(pid, cached);
+ return cached;
+ }
+}
+
+// 'butnot' is a parser combinator that takes two parsers, 'p1' and 'p2'.
+// It returns a parser that succeeds if 'p1' matches and 'p2' does not, or
+// 'p1' matches and the matched text is longer that p2's.
+// Useful for things like: butnot(IdentifierName, ReservedWord)
+function butnot(p1,p2) {
+ var p1 = toParser(p1);
+ var p2 = toParser(p2);
+ var pid = parser_id++;
+
+ // match a but not b. if both match and b's matched text is shorter
+ // than a's, a failed match is made
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+
+ var br = p2(state);
+ if(!br) {
+ cached = p1(state);
+ } else {
+ var ar = p1(state);
+ if(ar.matched.length > br.matched.length)
+ cached = ar;
+ else
+ cached = false;
+ }
+ savedState.putCached(pid, cached);
+ return cached;
+ }
+}
+
+// 'difference' is a parser combinator that takes two parsers, 'p1' and 'p2'.
+// It returns a parser that succeeds if 'p1' matches and 'p2' does not. If
+// both match then if p2's matched text is shorter than p1's it is successfull.
+function difference(p1,p2) {
+ var p1 = toParser(p1);
+ var p2 = toParser(p2);
+ var pid = parser_id++;
+
+ // match a but not b. if both match and b's matched text is shorter
+ // than a's, a successfull match is made
+ return function(state) {
+ var savedState = sate;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+
+ var br = p2(state);
+ if(!br) {
+ cached = p1(state);
+ } else {
+ var ar = p1(state);
+ if(ar.matched.length >= br.matched.length)
+ cached = br;
+ else
+ cached = ar;
+ }
+ savedState.putCached(pid, cached);
+ return cached;
+ }
+}
+
+
+// 'xor' is a parser combinator that takes two parsers, 'p1' and 'p2'.
+// It returns a parser that succeeds if 'p1' or 'p2' match but fails if
+// they both match.
+function xor(p1, p2) {
+ var p1 = toParser(p1);
+ var p2 = toParser(p2);
+ var pid = parser_id++;
+
+ // match a or b but not both
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+
+ var ar = p1(state);
+ var br = p2(state);
+ if(ar && br)
+ cached = false;
+ else
+ cached = ar || br;
+ savedState.putCached(pid, cached);
+ return cached;
+ }
+}
+
+// A parser combinator that takes one parser. It returns a parser that
+// looks for zero or more matches of the original parser.
+function repeat0(p) {
+ var p = toParser(p);
+ var pid = parser_id++;
+
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached) {
+ return cached;
+ }
+
+ var ast = [];
+ var matched = "";
+ var result;
+ while(result = p(state)) {
+ ast.push(result.ast);
+ matched = matched + result.matched;
+ if(result.remaining.index == state.index)
+ break;
+ state = result.remaining;
+ }
+ cached = make_result(state, matched, ast);
+ savedState.putCached(pid, cached);
+ return cached;
+ }
+}
+
+// A parser combinator that takes one parser. It returns a parser that
+// looks for one or more matches of the original parser.
+function repeat1(p) {
+ var p = toParser(p);
+ var pid = parser_id++;
+
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+
+ var ast = [];
+ var matched = "";
+ var result= p(state);
+ if(!result)
+ cached = false;
+ else {
+ while(result) {
+ ast.push(result.ast);
+ matched = matched + result.matched;
+ if(result.remaining.index == state.index)
+ break;
+ state = result.remaining;
+ result = p(state);
+ }
+ cached = make_result(state, matched, ast);
+ }
+ savedState.putCached(pid, cached);
+ return cached;
+ }
+}
+
+// A parser combinator that takes one parser. It returns a parser that
+// matches zero or one matches of the original parser.
+function optional(p) {
+ var p = toParser(p);
+ var pid = parser_id++;
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+ var r = p(state);
+ cached = r || make_result(state, "", false);
+ savedState.putCached(pid, cached);
+ return cached;
+ }
+}
+
+// A parser combinator that ensures that the given parser succeeds but
+// ignores its result. This can be useful for parsing literals that you
+// don't want to appear in the ast. eg:
+// sequence(expect("("), Number, expect(")")) => ast: Number
+function expect(p) {
+ return action(p, function(ast) { return undefined; });
+}
+
+function chain(p, s, f) {
+ var p = toParser(p);
+
+ return action(sequence(p, repeat0(action(sequence(s, p), f))),
+ function(ast) { return [ast[0]].concat(ast[1]); });
+}
+
+// A parser combinator to do left chaining and evaluation. Like 'chain', it expects a parser
+// for an item and for a seperator. The seperator parser's AST result should be a function
+// of the form: function(lhs,rhs) { return x; }
+// Where 'x' is the result of applying some operation to the lhs and rhs AST's from the item
+// parser.
+function chainl(p, s) {
+ var p = toParser(p);
+ return action(sequence(p, repeat0(sequence(s, p))),
+ function(ast) {
+ return foldl(function(v, action) { return action[0](v, action[1]); }, ast[0], ast[1]);
+ });
+}
+
+// A parser combinator that returns a parser that matches lists of things. The parser to
+// match the list item and the parser to match the seperator need to
+// be provided. The AST is the array of matched items.
+function list(p, s) {
+ return chain(p, s, function(ast) { return ast[1]; });
+}
+
+// Like list, but ignores whitespace between individual parsers.
+function wlist() {
+ var parsers = [];
+ for(var i=0; i < arguments.length; ++i) {
+ parsers.push(whitespace(arguments[i]));
+ }
+ return list.apply(null, parsers);
+}
+
+// A parser that always returns a zero length match
+function epsilon_p(state) {
+ return make_result(state, "", undefined);
+}
+
+// Allows attaching of a function anywhere in the grammer. If the function returns
+// true then parse succeeds otherwise it fails. Can be used for testing if a symbol
+// is in the symbol table, etc.
+function semantic(f) {
+ var pid = parser_id++;
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+ cached = f() ? make_result(state, "", undefined) : false;
+ savedState.putCached(pid, cached);
+ return cached;
+ }
+}
+
+// The and predicate asserts that a certain conditional
+// syntax is satisfied before evaluating another production. Eg:
+// sequence(and("0"), oct_p)
+// (if a leading zero, then parse octal)
+// It succeeds if 'p' succeeds and fails if 'p' fails. It never
+// consume any input however, and doesn't put anything in the resulting
+// AST.
+function and(p) {
+ var p = toParser(p);
+ var pid = parser_id++;
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+ var r = p(state);
+ cached = r ? make_result(state, "", undefined) : false;
+ savedState.putCached(pid, cached);
+ return cached;
+ }
+}
+
+// The opposite of 'and'. It fails if 'p' succeeds and succeeds if
+// 'p' fails. It never consumes any input. This combined with 'and' can
+// be used for 'lookahead' and disambiguation of cases.
+//
+// Compare:
+// sequence("a",choice("+","++"),"b")
+// parses a+b
+// but not a++b because the + matches the first part and peg's don't
+// backtrack to other choice options if they succeed but later things fail.
+//
+// sequence("a",choice(sequence("+", not("+")),"++"),"b")
+// parses a+b
+// parses a++b
+//
+function not(p) {
+ var p = toParser(p);
+ var pid = parser_id++;
+ return function(state) {
+ var savedState = state;
+ var cached = savedState.getCached(pid);
+ if(cached)
+ return cached;
+ cached = p(state) ? false : make_result(state, "", undefined);
+ savedState.putCached(pid, cached);
+ return cached;
+ }
+}
+
+var ws = whitespace;
+
Please sign in to comment.
Something went wrong with that request. Please try again.