5

Marpa is an implementation of an Earley parser for Perl.

Earley parsers are parsers which can handle very ambiguous grammars in cubic time in the general case - O(n3).

There are some Earley parsers or recognizers which are not fully usable tools missing vital aspects such as being able to iterate through each parse tree in the parse forest when the parse was successful but ambiguous.

I'm only interested in tools which support access to the full abstract parse forest.

Marpa uses a C library, libmarpa, for its backend, and it's open source so other projects can integrate it.

I'm looking for an implementation of an Earley parser for Node.js that's either built on libmarpa, or is comparable to it.

Requirements

  • Must support grammars with at least as much ambiguity as Marpa can handle.
  • Must not be just a recognizer but a full parser producing a parse forest.
  • Must not produce merely one possible parse tree for ambiguous inputs, but a full parse forest.
Improve this question
4
  • Marpa is a C library, so it might be possible to compile Marpa into JavaScript using Emscripten. JavaScript Moony Parser can parse strings using ambiguous grammars, but I do not know whether it can generate a full parse forest.
    – Anderson Green
    Mar 20 '15 at 21:04
  • At the time I played with Moony Parser I recall it only returned one possible parse and thus was a recognizer but gave you no way access and process the alternative ambiguous parses in the forest. This is essential when a grammar is inherently ambiguous but that can be sorted out by the semantics at the next level. It may have changed since then.
    – hippietrail
    Mar 21 '15 at 1:21
  • The Nearley parser for node.js looks very promising, since it is able to generate an array of multiple parsings for ambiguous grammars. I'm not sure if it will produce an entire parse forest in all cases, though.
    – Anderson Green
    Aug 22 '15 at 23:12
  • 1
    Also, it might be possible to automatically translate Marpa's source code into JavaScript using Perlito. I haven't yet tested this solution, though.
    – Anderson Green
    Aug 22 '15 at 23:16
5

Please, excuse my self-promotion - but recently I developed tiny JavaScript implementation of Earley parser, which can extract multiple syntax trees (which have very simple structure, and can be easily traversed).

The library (single JS file) and examples can be found here: https://github.com/lagodiuk/earley-parser-js

Improve this answer
2
  • 2
    Self-promotion is welcomed as long as it is disclosed and not spam. Clearly, yours is the welcomed kind! :-)
    – RockPaperLz- Mask it or Casket ♦
    Nov 4 '15 at 5:10
  • 1
    @RockPaperLizard thank you for your feedback! :-)
    – stemm
    Nov 5 '15 at 0:34
1

Another suggestion is nearley (https://github.com/kach/nearley). The project is actively being developed and has decent speeds, can take advantage of tokenizers, etc.

Improve this answer
1
  • Documentation isn't thorough, but it seems to be good. Having a built-in support for lexer/tokenizer would be a welcome bonus; presently, you must use a third-party module like Moo.
    – Harry
    Apr 27 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.