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'
:start ::= language

language ::= number op_plus number
number ~ [\d]+
op_plus ~ '+'

:discard ~ whitespace
whitespace ~ [\s]+
END_BNF

input = "100 + 200"

parser.parse(input, grammar) # => ["100", "+", "200"]

See examples/ for a more thorough demonstration of this interface's capabilities, including a parser for JSON.

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 provide all parses of ambiguous input.
• Several other important features of the SLIF interface, on which this one is based.

Contributing

1. Fork it ( https://github.com/omarroth/marpa/fork )
2. Create your feature branch (git checkout -b my-new-feature)
3. Commit your changes (git commit -am 'Add some feature')
4. Push to the branch (git push origin my-new-feature)
5. Create a new Pull Request

Contributors

• omarroth Omar Roth - creator, maintainer