Re: Interesting article on ARG work

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

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 
> nondeterministic choice separately at each occurrence of a "@", so there 
> 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 following URL's design would be wiser and practical (e.g., where @ is isomorphic to #if DEBUG in the C preprocessor and thus exactly one CONFIG…X in this paper).  This paper explains quite lucidly the fork-merge of the temporarily bifurcated reduced-production stack.  Note that this paper solves the general case of numerous conditional-compilation CONFIG…Xs.  Here with @-code there is exactly one such conditional-compilation configurator per compilation unit.  The reduced-production stack will temporarily bifurcate into exactly 2 parallel reduced-production stacks (and have exactly 2 alternative AST subtrees extant concurrently for the affected lines of source code).  Then those 2 bifurcations will be merged again into a traditional LR reduced-production stack upon lack of an @ prefix after a contiguous sequence of @-code lines.  The GLR is driven by a bifurcatable lexical-analysis layer that intentionally (dynamically) introduces an ambiguity.  Niklas, 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 grammar itself, dynamically injected by the lexical-analysis layer, a programmer's unwisely-excessively-deeply nested conditional-compilation via a preprocessor, 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 there exists GLL for bifurcating the top-down recursive-descent call-stack, such as via generators.  It is merely a difference of which stack is being bifurcated into 2 temporarily-both-entertained stacks (to produce 2 alternative 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 •reactive•-system's observance of a stream of tokens.  (But I digress to that Rx/Ix prior discussion here on comp.lang.ada.)