marpa
Marpa is a parsing algorithm.
From the official Marpa website:
Marpa is fast. It parses in linear time:
- all the grammar classes that recursive descent parses;
- the grammar class that the yacc family parses;
- in fact, any unambiguous grammars, with a couple of exceptions that are not likely to be an issue in practice (see quibbles); and
- all ambiguous grammars that are unions of a finite set of any of the above grammars.
(emphasis added)
Installation
Add this to your application's shard.yml
:
dependencies:
marpa:
github: omarroth/marpa
Usage
require "marpa"
parser = Marpa::Parser.new
grammar = <<-'END_BNF'
# Grammar from https://metacpan.org/pod/distribution/Marpa-R2/pod/Semantics.pod
:start ::= Expression
Expression ::= Number
| '(' Expression ')'
|| Expression '**' Expression
|| Expression '*' Expression
| Expression '/' Expression
|| Expression '+' Expression
| Expression '-' Expression
Number ~ [\d]+
:discard ~ whitespace
whitespace ~ [\s]+
END_BNF
input = "3 + 5 * 10"
pp parser.parse(input, grammar) # => [["3"], "+", [["5"], "*", ["10"]]]
See examples/
for a more thorough demonstration of this interface's capabilities, including a JSON parser.
Features
- Support for PCREs in lexing (see
examples/json/
for example). - Speed guarantees of the original Marpa algorithm (see above).
- Supports ambiguous and null rules.
Limitations
- Does not currently allow user to access all parses of ambiguous input.
- Several other important features of the SLIF interface, on which this one is based.
Contributing
- Fork it ( https://github.com/omarroth/marpa/fork )
- Create your feature branch (git checkout -b my-new-feature)
- Commit your changes (git commit -am 'Add some feature')
- Push to the branch (git push origin my-new-feature)
- Create a new Pull Request
Contributors
- omarroth Omar Roth - creator, maintainer