Ocean of Awareness
Mon, 01 Sep 2014
Marpa has a new web page
new official public website,
which Ron Savage has generously agreed to manage.
For those who have not heard of it,
Marpa is a parsing algorithm.
It is new, but very much based
on earlier work by 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:
- all the grammar classes that recursive descent parses;
- the grammar class that the yacc family parses;
- in fact, all unambiguous grammars, as long as they are free of unmarked middle recursions;
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,
all of the alternatives are considered for as long as they 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.
Comments on this post can be made in
Marpa's Google group.
posted at: 23:17 |
direct link to this entry