Path: csiph.com!xmission!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Kaz Kylheku <773-297-7223@kylheku.com> Newsgroups: comp.compilers Subject: Re: How change grammar to equivalent LL(1) ? Date: Fri, 24 Apr 2020 18:13:58 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 82 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <20-04-010@comp.compilers> References: <19-12-023@comp.compilers> <20-04-009@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="80465"; mail-complaints-to="abuse@iecc.com" Keywords: parse Posted-Date: 24 Apr 2020 14:42:15 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:2513 On 2020-04-24, Lasse Hillerĝe Petersen wrote: > I know this is a very late reply, however, I sometimes forget to read > Usenet news for a while, I hope the moderator is forgiving. > > On Mon, 23 Dec 2019 05:57:50 -0500, Christopher F Clark wrote: > >> Just a slight comment on what Lasse Hillerĝe Petersen >> wrote: > >> is called left-factoring. > > I am aware, however the point was having the refactored action return a > function to adjust the direction of the parse tree. I am sure LISPers and > Schemers wouldn't consider this anything special (so ordinary perhaps > even, that I hadn't been able to find any written mention of it, until > today), but when I wrote it back in 2017 I looked at my code and thought > "hey, that's actually neat and general." > > Only today did I actually manage to find a paper, which, although I am > very rusty in the matter of formal proofs and theory, being just an > amateur hacker, to me reads like the theory behind "my" method: > > Thielecke, Hayo. (2012). Functional semantics of parsing actions, and > left recursion elimination as continuation passing. PPDP'12 - Proceedings > of the 2012 ACM SIGPLAN Principles and Practice of Declarative > Programming. 91-102. 10.1145/2370776.2370789. Both left and right recursion elimination are related to tail optimization and continuation passing. In a shift-reduce LALR(1) parser, right recursion consumes parser stack space. If you can refactor it to left recursion, it becomes stackless. There is also a strong connection to the "reduce" or "fold" function in functional programming. We can linguistically identify the "reduce" in a LALR(1) parser with "reduce", the function. "reduce" takes an accumulator, initialized to some value, and then decimates a sequence by repeatedly passing the accumulator as the left argument to a function, and the successive items of the sequence as the right argument. For each successive call, the return value of the previous call is used as the accumulator. If we write a left-recursive calculator using a parser generator, say with addition as the binary op: expr : expr '+' expr { $$ = $1 + $3; } | expr { $$ = $1; } ; expr : initial_value { $$ = $1 } ; this behaves like an iterative reduce over an input like '1 + 2 + 3 ...'. The accumulator is seeded with 1, and then threaded through the successive reductions without consuming parser stack space. Fold/reduce, grammar reductions, continuations and (tail-)recursion are all closely related. If a compiler's target run-time is continuation-based, then stackless tail calls are trivial to implement. All functions return by invoking their continuation already, and so to make a tail call to a function, you just call it, and give it your *own* continuation as the continuation argument. If that function invokes that continuationm, it will "return" to wherever you would have returned. To generate a regular non-tail call which will return back to the caller, the caller captures a local continuation and gives the callee that one. The accumulator object in a reduce is a kind of continuation: it summarizes everything that has been done so far, so the calculation can continue withut having to regress anywhere. Old values of the accumulator are never revisited, so the reduce job can be done iteratively: by assigning the new accumulator value over the old one. That is easily achieved without assignment by tail recursion. -- TXR Programming Lanuage: http://nongnu.org/txr Music DIY Mailing List: http://www.kylheku.com/diy ADA MP-1 Mailing List: http://www.kylheku.com/mp1