Marpa efficiency and tree building

[Jeffrey Kegler]

Elsewhere, "@tef" started a discussion about parsing Ruby, and Marpa came up.  @tef (expressing skepticism re Marpa) made an excellent point -- that if I was using the usual methods for tree building, my claims of linear time for large classes of ambiguous grammars are only true in a technical sense.  That is, I may "recognize" a parse in O(n), but building the parse forest may take O(n^2) time or worse.

In fact, Marpa's bocage uses binarized trees and reuses nodes, so when Marpa's recognition is linear, its tree building is as well. Building Marpa's bocage is linear in the size of the recognizer's tables, so whatever time/space complexity you see in the recognizer, that's what you get out of the bocage.

At roughly the same time I was developing the parse "bocage", Elisabeth Scott was publishing articles about SPPF's, which do the same job.  I did not read Scott's excellent articles until a couple of years after I developed the parse bocage.  The two techniques are extremely similar.  I've never bothered looking up dates, but my guess is that E. Scott's work precedes mine.  I hope I may be allowed to assert, however, that I believe that "bocage" is a much nicer name for the concept than SPPF.

[Ron Savage]

Hi Jeffrey

I did not look at the docs for a long time, but have you documented (in
Marpa or elsewhere) this bocage?

On 17/04/13 11:01, Jeffrey Kegler wrote:
> Elsewhere, "@tef" started a discussion about parsing Ruby

> <http://programmingisterrible.com/post/42432568185/how-to-parse-ruby>,

--
Ron Savage
http://savage.net.au/
Ph: 0421 920 622

[Jeffrey Kegler]

As far as user interface goes, yes.  The bocage from the user interface point of view is very low profile -- just a step between the recce and evaluation, and one that's invisible at the higher levels.  When I do the ASF, his aspect of Marpa will become much more visible.

As far as implementation and theory goes, no.  My current theory paper only covers the recognizer.  I started with that because traditionally the recognition part of the problem receives the most attention from theorists.  In fact, as E. Scott correctly points out, parsing theorists tend to treat parsing as if recognition is 100% of the problem, and building and evaluating trees is trivial.  The theory paper for Marpa's recognizer took me 2-3 months to write, and I'd expect a full write-up of the tree building and evaluation would take about the same amount of time.

jeffrey