jscc

Jscc is a simple parser generator written in javascript. It allows you to generate an LALR parser for a language you define using a context-free grammar specification. This grammar is given as a pure javascript data structure as follows:

{
  nonterminal: [
    symbol, ... , function(values) { /* reduce */ },
    ...
  ],
  ...
}

This grammar (similar to BNF) is an object with nonterminal symbols as keys. Its values are sequences of nonempty symbol strings (terminal or nonterminal) to which nonterminal can expand, followed by a reduce function that is called when reducing the immediately preceding string sequence (i.e. the production) with an array of values corresponding to the symbols in the production. The reduce function should return a new value representing nonterminal for this production.

Any string in the grammar not appearing as a key in the grammar object is interpreted literally as a terminal symbol. Jscc also accepts a tokens object mapping terminal symbols to regular expressions that serves as a built-in lexer.

jscc.generate(grammar, start, tokens);

A call to generate specifies the language's grammar, the start symbol for the grammar, and an optional tokens object. The call returns a function that parses a given string, calling the associated reduce functions on any reduction steps. When called without an argument, this function returns a compact, JSON-serializable representation of the state machine generated for the grammar, which can be supplied in place of start to generate (along with the same grammar) to quickly generate the same parser function.

var machine = jscc.generate(grammar, start)(); // JSON-serializable; suitable for hard-coding
jscc.generate(grammar, machine, tokens);

Use json2js for a compact representation of machine to copy into your code.

Example

Below is a call to generate that creates a parser for a simple calculator.

var calculate = jscc.generate({
  addition: [
    'addition', '+', 'multiplication', function(e) { return e[0] + e[2]; },
    'addition', '-', 'multiplication', function(e) { return e[0] - e[2]; },
    'multiplication', function(e) { return e[0]; }
  ],
  multiplication: [
    'multiplication', '*', 'group', function(e) { return e[0] * e[2]; },
    'multiplication', '/', 'group', function(e) { return e[0] / e[2]; },
    'group', function(e) { return e[0]; }
  ],
  group: [
    '(', 'addition', ')', function(e) { return e[1]; },
    'number', function(e) { return parseInt(e[0], 10); }
  ]
}, 'addition', {
  number: /[0-9]+/,
  '': /\s+/ // empty string token denotes characters to ignore
});

You can try the calculator below. The result will appear beside the button, and the parse tree will appear below.