From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=unavailable autolearn_force=no version=3.4.4 Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!feeder.eternal-september.org!news.unit0.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Niklas Holsti Newsgroups: comp.lang.ada Subject: Re: Interesting article on ARG work Date: Sun, 15 Apr 2018 21:37:11 +0300 Organization: Tidorum Ltd Message-ID: References: <62ee0aac-49da-4925-b9aa-a16695b3fc45@googlegroups.com> <9879872e-c18a-4667-afe5-41ce0f54559f@googlegroups.com> <80db2d05-744f-4201-ba1b-4436f8040491@googlegroups.com> <59f9ab6d-d6ba-45ff-a6f0-c5699983d9e8@googlegroups.com> <1a390e22-f49f-4028-8e58-ca4d0f51e4b6@googlegroups.com> <195739aa-2f32-4cba-80ac-e60591e94712@googlegroups.com> <8c44fc67-2183-42d8-a61e-8a15ce2ba44c@googlegroups.com> <1e40f5f6-1ee6-4f90-9e0a-871b57d89037@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: individual.net AqCC522GPLOYhQjkWsZh7Af7sXrD3jW9xj0fRPL1k6i4aq+A7O Cancel-Lock: sha1:+H9E7rLEUfDaeY5WM5EG5bhqo1Y= User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:45.0) Gecko/20100101 Thunderbird/45.8.0 In-Reply-To: <1e40f5f6-1ee6-4f90-9e0a-871b57d89037@googlegroups.com> Xref: reader02.eternal-september.org comp.lang.ada:51528 Date: 2018-04-15T21:37:11+03:00 List-Id: 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 . @ .