Tomita's observation on pointers in Earley's algorithm

[axh...@ualr.edu]

From Parsing Techniques (Grune & Jacobs, p. 210),

In his 1970 article, Earley gives a method of constructing the parse tree(s) while parsing, by keeping with each item a pointer back to the item that caused it to be present. Tomita [162, p. 74-77] has, however, shown that this method will produce incorrect parse trees on certain ambiguous grammars. 

In the theory paper I don't remember any references to this regarding Marpa's pointer scheme. Leo and Aycock & Horspool's papers don't seem to mention it either. I haven't grokked the algorithm yet, so I've probably missed something in the details. Does Marpa address this issue?

[Jeffrey Kegler]

Marpa uses its own pointer scheme, which is not derived from Jay Earley's, and does not have the bug Tomita reports.  (At this point Marpa has been very widely used, and if its method of constructing parse trees had that or any similar bugs, I'd expect we'd have seen it a while ago.)  I did look at the suggestions for a pointer scheme in Aycock and Horspool and IIRC my scheme is consistent with their ideas.

Most of the apparatus that actually makes a parser usable, I developed independently.  That includes the bocage though it turned out to be exactly the same as Elizabeth Scott's SPPF data structure.  Scott was (I believe) first, but I was unaware of her work until mine was complete.  So closely do the two resemble each other, that I will never write up a theory paper for the bocage -- Scott's paper does the job probably better than I could.  I like the term "bocage", but they could also be called "Scott trees".

--
You received this message because you are subscribed to the Google Groups "marpa parser" group.
To unsubscribe from this group and stop receiving emails from it, send an email to marpa-parser+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[axh...@ualr.edu]

I'll look closer at A&H, then. And thanks for pointing me to Scott's paper. I was very fuzzy on how the parse forests were constructed.

To unsubscribe from this group and stop receiving emails from it, send an email to marpa-parser...@googlegroups.com.