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 X-Received: by 10.107.39.80 with SMTP id n77mr3166073ion.117.1523799082300; Sun, 15 Apr 2018 06:31:22 -0700 (PDT) X-Received: by 2002:a9d:3286:: with SMTP id u6-v6mr406171otb.13.1523799081879; Sun, 15 Apr 2018 06:31:21 -0700 (PDT) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!feeder.eternal-september.org!news.uzoreto.com!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.iad1.usenetexpress.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!e130-v6no1708284itb.0!news-out.google.com!15-v6ni2168itg.0!nntp.google.com!e130-v6no1708280itb.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Sun, 15 Apr 2018 06:31:21 -0700 (PDT) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=47.185.233.194; posting-account=zwxLlwoAAAChLBU7oraRzNDnqQYkYbpo NNTP-Posting-Host: 47.185.233.194 References: <1b44444f-c1b3-414e-84fb-8798961487c3@googlegroups.com> <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> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <1e40f5f6-1ee6-4f90-9e0a-871b57d89037@googlegroups.com> Subject: Re: Interesting article on ARG work From: "Dan'l Miller" Injection-Date: Sun, 15 Apr 2018 13:31:22 +0000 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Received-Bytes: 3969 X-Received-Body-CRC: 3315771146 Xref: reader02.eternal-september.org comp.lang.ada:51514 Date: 2018-04-15T06:31:21-07:00 List-Id: 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 =E2=80=9Cjust GLR=E2=80=9D= and =E2=80=9Cplain > > GLR=E2=80=9D? There are 2 seminal references historically: Bernard La= ng > > (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 o= f this tutorial-survey paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=3D10.1.1.132.2321&rep=3Dr= ep1&type=3Dpdf If all of the branches of the GSS are thus merged, then GLR returns to LR t= emporarily 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 t= o the power of 0) main-trunk along the LR reduced-productions stack to 2 (e= quals 2 to the power of 1) when encountering a =E2=80=A2contiguous sequence= =E2=80=A2 of @-code, but then the exponential explosion stops at the end of= the =E2=80=A2contiguous sequence=E2=80=A2 of @-code as all branches of the= GSS are merged back to LR's single main-trunk.