Re: Interesting article on ARG work

["Dan'l Miller" <optikos@verizon.net>]

On Sunday, April 15, 2018 at 2:50:15 AM UTC-5, Niklas Holsti wrote:
> On 18-04-10 22:46 , Dan'l Miller wrote:
> > On Tuesday, April 10, 2018 at 2:23:24 PM UTC-5, Niklas Holsti wrote:
> >> For a GLR parser,
> >>
> >> _just_ a GLR parser
> >>
> >> _just_ GLR parsing.
> >>
> >> In plain GLR parsing
> >>
> >> That is true for the "Fork-Merge LR" (FMLR) parsing in the paper
> >> you referenced, but that is not GLR.
> >>
> >> _just_ a GLR
> >
> > Which flavor of generalized LR are you taking as the sole seminal
> > reference to definitively brand the official “just GLR” and “plain
> > GLR”?  There are 2 seminal references historically:  Bernard Lang
> > (1974) and Tomita Masaru (1985).  Lang's versus Tomita's 2 approaches
> > to GLR are substantially different.

Clearly Tomita's popularization of GLR in 1985 uses forking and merging of the reduced-productions stack, as called graph-structured stack (GSS).  You can clearly see the merging of the branches along the GSS in section 4.6 of this tutorial-survey paper:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.132.2321&rep=rep1&type=pdf

If all of the branches of the GSS are thus merged, then GLR returns to LR temporarily until the next arbitrary-length look-ahead is encountered.  This is what eliminates the exponential explosion that you keep fearing.  Yes, a trivial exponential explosion would occur for @-code:  from 1 (equals 2 to the power of 0) main-trunk along the LR reduced-productions stack to 2 (equals 2 to the power of 1) when encountering a •contiguous sequence• of @-code, but then the exponential explosion stops at the end of the •contiguous sequence• of @-code as all branches of the GSS are merged back to LR's single main-trunk.