aumouvantsillage/persil.js

JavaScript implmentation of an Earley parser

A JavaScript implementation of an Earley parser

This is a straightforward implementation of an Earley parser using the improvement by Aycock and Horspool (2002).

This library also provides:

• BNF and EBNF front-ends for entering grammars.
• Support for the generation of Abstract Syntax Trees (in the EBNF front-end).
• Support for parsers with, or without, scanner. A default non-optimized scanner is provided.

Building

Install node.js and the grunt CLI.

sudo apt-get install nodejs
sudo npm install grunt-cli -g

At the root of the source tree, run:

npm install

Finally, build the project using the following command:

grunt

Examples

The source code of the examples can be found in the src/examples/ folder. After building the project, the executable demos are in dist/examples/.

For instance, type the following command to run the scannerless expression evaluator derived from the EBNF grammar at src/examples/calc-scannerless/calc.ebnf:

node dist/examples/calc-scannerless/calc.ebnf.js

References

• Earley Parser at Wikipedia.
• Earley Parsing Explained by Loup Vaillant.

Disclaimer

The author develops this parser for his own enlightenment. He shares the source code in the hope that others can learn from it or give useful feedback.

persil.js's Issues

EBNF compile script: add option to create a grammar with scanner

In cli/compile-ebnf.js, add support for the scanner option.

EBNF: Optimize generated grammar

Currently, the EBNF compiler creates a new rule for each subexpression.
In some cases, rule inlining can reduce the number of states created by the parser.