An overview of Marpa from its author, Jeffrey Kegler:
Marpa is a parsing algorithm. It is new, but very much
based on the prior work of Jay Earley, Joop Leo, John
Aycock and R. Nigel Horspool.
Marpa is intended to replace, and to go well beyond,
recursive descent and the yacc family of parsers.
Marpa is fast. It parses in linear time:
o All grammar classes that recursive descent parses.
o The grammar class that the yacc family parses.
o In fact, all unambiguous grammars, as long as they
are free of unmarked middle recursions.
o Ambiguous grammars that are unions of a finite set
of any of the above grammars.
Marpa is powerful. Marpa will parse anything that can be
written in BNF. This includes any mixture of left, right
and middle recursions.
Marpa is convenient. Unlike recursive descent, you do not
have to write a parser - Marpa generates one from BNF.
Unlike PEG or yacc, parser generation is unrestricted and
exact. Marpa converts any grammar which can be written as
BNF into a parser which recognizes everything in the
language described by that BNF, and which rejects everything
that is not in that language. The programmer is not forced
to make arbitrary choices while parsing. If a rule has
several alternatives, each alternative is evaluated for as
long as it might yield a valid parse.
Marpa is flexible. Like recursive descent, Marpa allows you
to stop and do your own custom processing. Unlike recursive
descent, Marpa makes available to you detailed information
about the parse so far - which rules and symbols have been
recognized, with their locations, and which rules and
symbols are expected next. |
