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 2002:a24:5088:: with SMTP id m130-v6mr541150itb.7.1523297308220; Mon, 09 Apr 2018 11:08:28 -0700 (PDT) X-Received: by 2002:a9d:5888:: with SMTP id x8-v6mr1450900otg.0.1523297308124; Mon, 09 Apr 2018 11:08:28 -0700 (PDT) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!feeder.eternal-september.org!paganini.bofh.team!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!k65-v6no2107428ita.0!news-out.google.com!u64-v6ni4346itb.0!nntp.google.com!k65-v6no2107421ita.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Mon, 9 Apr 2018 11:08:27 -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> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: Subject: Re: Interesting article on ARG work From: "Dan'l Miller" Injection-Date: Mon, 09 Apr 2018 18:08:28 +0000 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Xref: reader02.eternal-september.org comp.lang.ada:51420 Date: 2018-04-09T11:08:27-07:00 List-Id: On Monday, April 9, 2018 at 11:12:56 AM UTC-5, Niklas Holsti wrote: > On 18-04-08 22:48 , Dan'l Miller wrote: > ... but the GLR parser would apply this=20 > nondeterministic choice separately at each occurrence of a "@", so there= =20 > would be an exponentially large set of alternative parse attempts. Good Lord! What an especially inappropriate design to intentionally cause = combinatorial explosion. Why look for the worst possible design? The foll= owing URL's design would be wiser and practical (e.g., where @ is isomorphi= c to #if DEBUG in the C preprocessor and thus exactly one CONFIG=E2=80=A6X = in this paper). This paper explains quite lucidly the fork-merge of the te= mporarily bifurcated reduced-production stack. Note that this paper solves= the general case of numerous conditional-compilation CONFIG=E2=80=A6Xs. H= ere with @-code there is exactly one such conditional-compilation configura= tor per compilation unit. The reduced-production stack will temporarily bi= furcate into exactly 2 parallel reduced-production stacks (and have exactly= 2 alternative AST subtrees extant concurrently for the affected lines of s= ource code). Then those 2 bifurcations will be merged again into a traditi= onal LR reduced-production stack upon lack of an @ prefix after a contiguou= s sequence of @-code lines. The GLR is driven by a bifurcatable lexical-an= alysis layer that intentionally (dynamically) introduces an ambiguity. Nik= las, you seem to be thinking that @ would appear in the GLRed BNF. No, it = would not, at least not in an exemplary implementation. In GLR, the origin= of the ambiguity can be from a variety of origins: codified in the gramma= r itself, dynamically injected by the lexical-analysis layer, a programmer'= s unwisely-excessively-deeply nested conditional-compilation via a preproce= ssor, and so forth. https://cs.nyu.edu/rgrimm/papers/pldi12.pdf And if bottom-up parsing is too out-of-vogue for anyone out there, then the= re exists GLL for bifurcating the top-down recursive-descent call-stack, su= ch as via generators. It is merely a difference of which stack is being bi= furcated into 2 temporarily-both-entertained stacks (to produce 2 alternati= ve AST subtrees extant concurrently for the affected lines of source code) = before being merged back together as 1) a traditional LL call-stack of guesses that turned out correct or 2) a traditional LR reduced-production stack of =E2=80=A2reactive=E2=80=A2-= system's observance of a stream of tokens. (But I digress to that Rx/Ix pr= ior discussion here on comp.lang.ada.)