Re: Interesting article on ARG work

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

On 18-04-15 16:31 , Dan'l Miller wrote:
> 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.

You keep misunderstanding my point. I fully grant that GLR parsers 
mostly avoid exponential blow-up of the parsing process. But if the 
parser is not context-dependent, the number of complete parses 
considered during a GLR parse is exponential in the number of places in 
the sentence where the parse is ambiguous / non-deterministic, because 
the choices of parsing actions at each such place are not correlated.

In essence, without context dependency or some other similar mechanism 
to enforce uniform choice, a GLR parser for @ assumes that "@X" can be 
equivalent to "X" at one place, and to "--X" at another. This leads to 
an exponential number of complete parses, but more seriously, it does 
not match the intended semantics of @, so most of those parses are 
infeasible and can fail (I showed examples earlier).

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .