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.
On Thursday, May 25, 2017 at 11:55:12 PM UTC-5, Jeffrey Kegler wrote: > > 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] <javascript:>> 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] <javascript:>. >> 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.
