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 <http://dinhe.net/~aredridel/.notmine/PDFs/Parsing/SCOTT,%20Elizabeth%20-%20SPPF-Style%20Parsing%20From%20Earley%20Recognizers.pdf> does the job probably better than I could. I like the term "bocage", but they could also be called "Scott trees". On Thu, May 25, 2017 at 9:38 PM, <[email protected]> wrote: > 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? > > -- > 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 [email protected]. > For more options, visit https://groups.google.com/d/optout. > -- 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 [email protected]. For more options, visit https://groups.google.com/d/optout.
