Ocean of Awareness

[ Cross-posted by invitation from its home on the Ocean of Awareness blog. ]

Marpa has a 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; and
  • all 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

Comments on this post can be made in Marpa's Google group.