Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Browse files

Add PEG.js Lisp parser based on our example grammar; runs at similar …

…speed to our parser.
  • Loading branch information...
commit 6a67b43dc047e5bd550f8909c504c625f8dcd6a7 1 parent e02cf5b
@jcoglan authored
Showing with 861 additions and 0 deletions.
  1. +5 −0 examples/lisp.js
  2. +856 −0 examples/pegjs/lisp.js
View
5 examples/lisp.js
@@ -1,6 +1,7 @@
load('vendor/js.class/build/min/core.js');
load('build/stake-min.js');
load('examples/benchmark.js');
+load('examples/pegjs/lisp.js');
grammar = 'grammar CompiledLisp \
\
@@ -29,3 +30,7 @@ benchmark('Combinator parser', 20, function() {
CombinatorLispParser.parse(program);
});
+benchmark('PEG.js parser', 20, function() {
+ LispParser.parse(program);
+});
+
View
856 examples/pegjs/lisp.js
@@ -0,0 +1,856 @@
+LispParser = (function(){
+ /* Generated by PEG.js (http://pegjs.majda.cz/). */
+
+ var result = {
+ _startRule: "start",
+
+ _quoteString: function(s) {
+ /*
+ * ECMA-262, 5th ed., 7.8.4: All characters may appear literally in a string
+ * literal except for the closing quote character, backslash, carriage
+ * return, line separator, paragraph separator, and line feed. Any character
+ * may appear in the form of an escape sequence.
+ */
+ return '"' + s
+ .replace(/\\/g, '\\\\') // backslash
+ .replace(/"/g, '\\"') // closing quote character
+ .replace(/\r/g, '\\r') // carriage return
+ .replace(/\u2028/g, '\\u2028') // line separator
+ .replace(/\u2029/g, '\\u2029') // paragraph separator
+ .replace(/\n/g, '\\n') // line feed
+ + '"';
+ },
+
+ _arrayContains: function(array, value) {
+ /*
+ * Stupid IE does not have Array.prototype.indexOf, otherwise this function
+ * would be a one-liner.
+ */
+ var length = array.length;
+ for (var i = 0; i < length; i++) {
+ if (array[i] === value) {
+ return true;
+ }
+ }
+ return false;
+ },
+
+ _matchFailed: function(failure) {
+ if (this._pos > this._rightmostMatchFailuresPos) {
+ this._rightmostMatchFailuresPos = this._pos;
+ this._rightmostMatchFailuresExpected = [];
+ }
+
+ if (!this._arrayContains(this._rightmostMatchFailuresExpected, failure)) {
+ this._rightmostMatchFailuresExpected.push(failure);
+ }
+ },
+
+ _parse_start: function(context) {
+ var cacheKey = "start" + '@' + this._pos;
+ var cachedResult = this._cache[cacheKey];
+ if (cachedResult !== undefined) {
+ this._pos = cachedResult.nextPos;
+ return cachedResult.result;
+ }
+
+ var pos = this._pos;
+
+
+ var result1 = this._parse_cell(context);
+ if (result1 !== null) {
+ var result0 = [];
+ while (result1 !== null) {
+ result0.push(result1);
+ var result1 = this._parse_cell(context);
+ }
+ } else {
+ var result0 = null;
+ }
+
+
+
+ this._cache[cacheKey] = {
+ nextPos: this._pos,
+ result: result0
+ };
+ return result0;
+ },
+
+ _parse_cell: function(context) {
+ var cacheKey = "cell" + '@' + this._pos;
+ var cachedResult = this._cache[cacheKey];
+ if (cachedResult !== undefined) {
+ this._pos = cachedResult.nextPos;
+ return cachedResult.result;
+ }
+
+ var pos = this._pos;
+
+
+ var savedPos0 = this._pos;
+ var result3 = [];
+ var result9 = this._parse_space(context);
+ while (result9 !== null) {
+ result3.push(result9);
+ var result9 = this._parse_space(context);
+ }
+ if (result3 !== null) {
+ var result8 = this._parse_list(context);
+ if (result8 !== null) {
+ var result4 = result8;
+ } else {
+ var result7 = this._parse_atom(context);
+ if (result7 !== null) {
+ var result4 = result7;
+ } else {
+ var result4 = null;;
+ };
+ }
+ if (result4 !== null) {
+ var result5 = [];
+ var result6 = this._parse_space(context);
+ while (result6 !== null) {
+ result5.push(result6);
+ var result6 = this._parse_space(context);
+ }
+ if (result5 !== null) {
+ var result2 = [result3, result4, result5];
+ } else {
+ var result2 = null;
+ this._pos = savedPos0;
+ }
+ } else {
+ var result2 = null;
+ this._pos = savedPos0;
+ }
+ } else {
+ var result2 = null;
+ this._pos = savedPos0;
+ }
+
+
+
+ this._cache[cacheKey] = {
+ nextPos: this._pos,
+ result: result2
+ };
+ return result2;
+ },
+
+ _parse_list: function(context) {
+ var cacheKey = "list" + '@' + this._pos;
+ var cachedResult = this._cache[cacheKey];
+ if (cachedResult !== undefined) {
+ this._pos = cachedResult.nextPos;
+ return cachedResult.result;
+ }
+
+ var pos = this._pos;
+
+
+ var savedPos1 = this._pos;
+ if (this._input.substr(this._pos, 1) === "(") {
+ var result11 = "(";
+ this._pos += 1;
+ } else {
+ var result11 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed(this._quoteString("("));
+ }
+ }
+ if (result11 !== null) {
+ var result14 = this._parse_cell(context);
+ if (result14 !== null) {
+ var result12 = [];
+ while (result14 !== null) {
+ result12.push(result14);
+ var result14 = this._parse_cell(context);
+ }
+ } else {
+ var result12 = null;
+ }
+ if (result12 !== null) {
+ if (this._input.substr(this._pos, 1) === ")") {
+ var result13 = ")";
+ this._pos += 1;
+ } else {
+ var result13 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed(this._quoteString(")"));
+ }
+ }
+ if (result13 !== null) {
+ var result10 = [result11, result12, result13];
+ } else {
+ var result10 = null;
+ this._pos = savedPos1;
+ }
+ } else {
+ var result10 = null;
+ this._pos = savedPos1;
+ }
+ } else {
+ var result10 = null;
+ this._pos = savedPos1;
+ }
+
+
+
+ this._cache[cacheKey] = {
+ nextPos: this._pos,
+ result: result10
+ };
+ return result10;
+ },
+
+ _parse_atom: function(context) {
+ var cacheKey = "atom" + '@' + this._pos;
+ var cachedResult = this._cache[cacheKey];
+ if (cachedResult !== undefined) {
+ this._pos = cachedResult.nextPos;
+ return cachedResult.result;
+ }
+
+ var pos = this._pos;
+
+
+ var result19 = this._parse_boolean(context);
+ if (result19 !== null) {
+ var result15 = result19;
+ } else {
+ var result18 = this._parse_integer(context);
+ if (result18 !== null) {
+ var result15 = result18;
+ } else {
+ var result17 = this._parse_string(context);
+ if (result17 !== null) {
+ var result15 = result17;
+ } else {
+ var result16 = this._parse_symbol(context);
+ if (result16 !== null) {
+ var result15 = result16;
+ } else {
+ var result15 = null;;
+ };
+ };
+ };
+ }
+
+
+
+ this._cache[cacheKey] = {
+ nextPos: this._pos,
+ result: result15
+ };
+ return result15;
+ },
+
+ _parse_boolean: function(context) {
+ var cacheKey = "boolean" + '@' + this._pos;
+ var cachedResult = this._cache[cacheKey];
+ if (cachedResult !== undefined) {
+ this._pos = cachedResult.nextPos;
+ return cachedResult.result;
+ }
+
+ var pos = this._pos;
+
+
+ if (this._input.substr(this._pos, 2) === "#t") {
+ var result22 = "#t";
+ this._pos += 2;
+ } else {
+ var result22 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed(this._quoteString("#t"));
+ }
+ }
+ if (result22 !== null) {
+ var result20 = result22;
+ } else {
+ if (this._input.substr(this._pos, 2) === "#f") {
+ var result21 = "#f";
+ this._pos += 2;
+ } else {
+ var result21 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed(this._quoteString("#f"));
+ }
+ }
+ if (result21 !== null) {
+ var result20 = result21;
+ } else {
+ var result20 = null;;
+ };
+ }
+
+
+
+ this._cache[cacheKey] = {
+ nextPos: this._pos,
+ result: result20
+ };
+ return result20;
+ },
+
+ _parse_integer: function(context) {
+ var cacheKey = "integer" + '@' + this._pos;
+ var cachedResult = this._cache[cacheKey];
+ if (cachedResult !== undefined) {
+ this._pos = cachedResult.nextPos;
+ return cachedResult.result;
+ }
+
+ var pos = this._pos;
+
+
+ var savedPos2 = this._pos;
+ if (this._input.substr(this._pos).match(/^[1-9]/) !== null) {
+ var result24 = this._input.charAt(this._pos);
+ this._pos++;
+ } else {
+ var result24 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed('[' + "1-9" + ']');
+ }
+ }
+ if (result24 !== null) {
+ var result25 = [];
+ if (this._input.substr(this._pos).match(/^[0-9]/) !== null) {
+ var result26 = this._input.charAt(this._pos);
+ this._pos++;
+ } else {
+ var result26 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed('[' + "0-9" + ']');
+ }
+ }
+ while (result26 !== null) {
+ result25.push(result26);
+ if (this._input.substr(this._pos).match(/^[0-9]/) !== null) {
+ var result26 = this._input.charAt(this._pos);
+ this._pos++;
+ } else {
+ var result26 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed('[' + "0-9" + ']');
+ }
+ }
+ }
+ if (result25 !== null) {
+ var result23 = [result24, result25];
+ } else {
+ var result23 = null;
+ this._pos = savedPos2;
+ }
+ } else {
+ var result23 = null;
+ this._pos = savedPos2;
+ }
+
+
+
+ this._cache[cacheKey] = {
+ nextPos: this._pos,
+ result: result23
+ };
+ return result23;
+ },
+
+ _parse_string: function(context) {
+ var cacheKey = "string" + '@' + this._pos;
+ var cachedResult = this._cache[cacheKey];
+ if (cachedResult !== undefined) {
+ this._pos = cachedResult.nextPos;
+ return cachedResult.result;
+ }
+
+ var pos = this._pos;
+
+
+ var savedPos3 = this._pos;
+ if (this._input.substr(this._pos, 1) === "\"") {
+ var result28 = "\"";
+ this._pos += 1;
+ } else {
+ var result28 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed(this._quoteString("\""));
+ }
+ }
+ if (result28 !== null) {
+ var result29 = [];
+ var savedPos4 = this._pos;
+ if (this._input.substr(this._pos, 1) === "\\") {
+ var result34 = "\\";
+ this._pos += 1;
+ } else {
+ var result34 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed(this._quoteString("\\"));
+ }
+ }
+ if (result34 !== null) {
+ if (this._input.length > this._pos) {
+ var result35 = this._input.charAt(this._pos);
+ this._pos++;
+ } else {
+ var result35 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed('any character');
+ }
+ }
+ if (result35 !== null) {
+ var result33 = [result34, result35];
+ } else {
+ var result33 = null;
+ this._pos = savedPos4;
+ }
+ } else {
+ var result33 = null;
+ this._pos = savedPos4;
+ }
+ if (result33 !== null) {
+ var result31 = result33;
+ } else {
+ if (this._input.substr(this._pos).match(/^[^"]/) !== null) {
+ var result32 = this._input.charAt(this._pos);
+ this._pos++;
+ } else {
+ var result32 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed('[' + "^\"" + ']');
+ }
+ }
+ if (result32 !== null) {
+ var result31 = result32;
+ } else {
+ var result31 = null;;
+ };
+ }
+ while (result31 !== null) {
+ result29.push(result31);
+ var savedPos4 = this._pos;
+ if (this._input.substr(this._pos, 1) === "\\") {
+ var result34 = "\\";
+ this._pos += 1;
+ } else {
+ var result34 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed(this._quoteString("\\"));
+ }
+ }
+ if (result34 !== null) {
+ if (this._input.length > this._pos) {
+ var result35 = this._input.charAt(this._pos);
+ this._pos++;
+ } else {
+ var result35 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed('any character');
+ }
+ }
+ if (result35 !== null) {
+ var result33 = [result34, result35];
+ } else {
+ var result33 = null;
+ this._pos = savedPos4;
+ }
+ } else {
+ var result33 = null;
+ this._pos = savedPos4;
+ }
+ if (result33 !== null) {
+ var result31 = result33;
+ } else {
+ if (this._input.substr(this._pos).match(/^[^"]/) !== null) {
+ var result32 = this._input.charAt(this._pos);
+ this._pos++;
+ } else {
+ var result32 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed('[' + "^\"" + ']');
+ }
+ }
+ if (result32 !== null) {
+ var result31 = result32;
+ } else {
+ var result31 = null;;
+ };
+ }
+ }
+ if (result29 !== null) {
+ if (this._input.substr(this._pos, 1) === "\"") {
+ var result30 = "\"";
+ this._pos += 1;
+ } else {
+ var result30 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed(this._quoteString("\""));
+ }
+ }
+ if (result30 !== null) {
+ var result27 = [result28, result29, result30];
+ } else {
+ var result27 = null;
+ this._pos = savedPos3;
+ }
+ } else {
+ var result27 = null;
+ this._pos = savedPos3;
+ }
+ } else {
+ var result27 = null;
+ this._pos = savedPos3;
+ }
+
+
+
+ this._cache[cacheKey] = {
+ nextPos: this._pos,
+ result: result27
+ };
+ return result27;
+ },
+
+ _parse_symbol: function(context) {
+ var cacheKey = "symbol" + '@' + this._pos;
+ var cachedResult = this._cache[cacheKey];
+ if (cachedResult !== undefined) {
+ this._pos = cachedResult.nextPos;
+ return cachedResult.result;
+ }
+
+ var pos = this._pos;
+
+
+ var savedPos5 = this._pos;
+ var savedPos6 = this._pos;
+ var savedReportMatchFailuresVar0 = context.reportMatchFailures;
+ context.reportMatchFailures = false;
+ var result40 = this._parse_delimiter(context);
+ context.reportMatchFailures = savedReportMatchFailuresVar0;
+ if (result40 === null) {
+ var result38 = '';
+ } else {
+ var result38 = null;
+ this._pos = savedPos6;
+ }
+ if (result38 !== null) {
+ if (this._input.length > this._pos) {
+ var result39 = this._input.charAt(this._pos);
+ this._pos++;
+ } else {
+ var result39 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed('any character');
+ }
+ }
+ if (result39 !== null) {
+ var result37 = [result38, result39];
+ } else {
+ var result37 = null;
+ this._pos = savedPos5;
+ }
+ } else {
+ var result37 = null;
+ this._pos = savedPos5;
+ }
+ if (result37 !== null) {
+ var result36 = [];
+ while (result37 !== null) {
+ result36.push(result37);
+ var savedPos5 = this._pos;
+ var savedPos6 = this._pos;
+ var savedReportMatchFailuresVar0 = context.reportMatchFailures;
+ context.reportMatchFailures = false;
+ var result40 = this._parse_delimiter(context);
+ context.reportMatchFailures = savedReportMatchFailuresVar0;
+ if (result40 === null) {
+ var result38 = '';
+ } else {
+ var result38 = null;
+ this._pos = savedPos6;
+ }
+ if (result38 !== null) {
+ if (this._input.length > this._pos) {
+ var result39 = this._input.charAt(this._pos);
+ this._pos++;
+ } else {
+ var result39 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed('any character');
+ }
+ }
+ if (result39 !== null) {
+ var result37 = [result38, result39];
+ } else {
+ var result37 = null;
+ this._pos = savedPos5;
+ }
+ } else {
+ var result37 = null;
+ this._pos = savedPos5;
+ }
+ }
+ } else {
+ var result36 = null;
+ }
+
+
+
+ this._cache[cacheKey] = {
+ nextPos: this._pos,
+ result: result36
+ };
+ return result36;
+ },
+
+ _parse_space: function(context) {
+ var cacheKey = "space" + '@' + this._pos;
+ var cachedResult = this._cache[cacheKey];
+ if (cachedResult !== undefined) {
+ this._pos = cachedResult.nextPos;
+ return cachedResult.result;
+ }
+
+ var pos = this._pos;
+
+
+ if (this._input.substr(this._pos).match(/^[\s\n\r\t]/) !== null) {
+ var result41 = this._input.charAt(this._pos);
+ this._pos++;
+ } else {
+ var result41 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed('[' + "\\s\\n\\r\\t" + ']');
+ }
+ }
+
+
+
+ this._cache[cacheKey] = {
+ nextPos: this._pos,
+ result: result41
+ };
+ return result41;
+ },
+
+ _parse_paren: function(context) {
+ var cacheKey = "paren" + '@' + this._pos;
+ var cachedResult = this._cache[cacheKey];
+ if (cachedResult !== undefined) {
+ this._pos = cachedResult.nextPos;
+ return cachedResult.result;
+ }
+
+ var pos = this._pos;
+
+
+ if (this._input.substr(this._pos, 1) === "(") {
+ var result44 = "(";
+ this._pos += 1;
+ } else {
+ var result44 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed(this._quoteString("("));
+ }
+ }
+ if (result44 !== null) {
+ var result42 = result44;
+ } else {
+ if (this._input.substr(this._pos, 1) === ")") {
+ var result43 = ")";
+ this._pos += 1;
+ } else {
+ var result43 = null;
+ if (context.reportMatchFailures) {
+ this._matchFailed(this._quoteString(")"));
+ }
+ }
+ if (result43 !== null) {
+ var result42 = result43;
+ } else {
+ var result42 = null;;
+ };
+ }
+
+
+
+ this._cache[cacheKey] = {
+ nextPos: this._pos,
+ result: result42
+ };
+ return result42;
+ },
+
+ _parse_delimiter: function(context) {
+ var cacheKey = "delimiter" + '@' + this._pos;
+ var cachedResult = this._cache[cacheKey];
+ if (cachedResult !== undefined) {
+ this._pos = cachedResult.nextPos;
+ return cachedResult.result;
+ }
+
+ var pos = this._pos;
+
+
+ var result47 = this._parse_paren(context);
+ if (result47 !== null) {
+ var result45 = result47;
+ } else {
+ var result46 = this._parse_space(context);
+ if (result46 !== null) {
+ var result45 = result46;
+ } else {
+ var result45 = null;;
+ };
+ }
+
+
+
+ this._cache[cacheKey] = {
+ nextPos: this._pos,
+ result: result45
+ };
+ return result45;
+ },
+
+ /*
+ * Parses the input with a generated parser. If the parsing is successfull,
+ * returns a value explicitly or implicitly specified by the grammar from
+ * which the parser was generated (see |PEG.buildParser|). If the parsing is
+ * unsuccessful, throws |PEG.grammarParser.SyntaxError| describing the error.
+ */
+ parse: function(input) {
+ var that = this;
+
+ function initialize() {
+ that._input = input;
+ that._pos = 0;
+ that._rightmostMatchFailuresPos = 0;
+ that._rightmostMatchFailuresExpected = [];
+ that._cache = {};
+ }
+
+ function buildErrorMessage() {
+ function buildExpected(failuresExpected) {
+ switch (failuresExpected.length) {
+ case 0:
+ return 'end of input';
+ case 1:
+ return failuresExpected[0];
+ default:
+ failuresExpected.sort();
+ return failuresExpected.slice(0, failuresExpected.length - 1).join(', ')
+ + ' or '
+ + failuresExpected[failuresExpected.length - 1];
+ }
+ }
+
+ var expected = buildExpected(that._rightmostMatchFailuresExpected);
+ var pos = Math.max(that._pos, that._rightmostMatchFailuresPos);
+ var actual = pos < that._input.length
+ ? that._quoteString(that._input.charAt(pos))
+ : 'end of input';
+
+ return 'Expected ' + expected + ' but ' + actual + ' found.';
+ }
+
+ function computeErrorPosition() {
+ /*
+ * The first idea was to use |String.split| to break the input up to the
+ * error position along newlines and derive the line and column from
+ * there. However IE's |split| implementation is so broken that it was
+ * enough to prevent it.
+ */
+
+ var input = that._input;
+ var pos = that._rightmostMatchFailuresPos;
+ var line = 1;
+ var column = 1;
+ var seenCR = false;
+
+ for (var i = 0; i < pos; i++) {
+ var ch = input.charAt(i);
+ if (ch === '\n') {
+ if (!seenCR) { line++; }
+ column = 1;
+ seenCR = false;
+ } else if (ch === '\r' | ch === '\u2028' || ch === '\u2029') {
+ line++;
+ column = 1;
+ seenCR = true;
+ } else {
+ column++;
+ seenCR = false;
+ }
+ }
+
+ return { line: line, column: column };
+ }
+
+ initialize();
+
+ var initialContext = {
+ reportMatchFailures: true
+ };
+
+ var result = this['_parse_' + this._startRule](initialContext);
+
+ /*
+ * The parser is now in one of the following three states:
+ *
+ * 1. The parser successfully parsed the whole input.
+ *
+ * - |result !== null|
+ * - |that._pos === input.length|
+ * - |that._rightmostMatchFailuresExpected.length| may or may not contain
+ * something
+ *
+ * 2. The parser successfully parsed only a part of the input.
+ *
+ * - |result !== null|
+ * - |that._pos < input.length|
+ * - |that._rightmostMatchFailuresExpected.length| may or may not contain
+ * something
+ *
+ * 3. The parser did not successfully parse any part of the input.
+ *
+ * - |result === null|
+ * - |that._pos === 0|
+ * - |that._rightmostMatchFailuresExpected.length| contains at least one failure
+ *
+ * All code following this comment (including called functions) must
+ * handle these states.
+ */
+ if (result === null || this._pos !== input.length) {
+ var errorPosition = computeErrorPosition();
+ throw new this.SyntaxError(
+ buildErrorMessage(),
+ errorPosition.line,
+ errorPosition.column
+ );
+ }
+
+ return result;
+ },
+
+ /* Returns the parser source code. */
+ toSource: function() { return this._source; }
+ };
+
+ /* Thrown when a parser encounters a syntax error. */
+
+ result.SyntaxError = function(message, line, column) {
+ this.name = 'SyntaxError';
+ this.message = message;
+ this.line = line;
+ this.column = column;
+ };
+
+ result.SyntaxError.prototype = Error.prototype;
+
+ return result;
+})();
Please sign in to comment.
Something went wrong with that request. Please try again.