Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: George Neuner Newsgroups: comp.compilers Subject: Re: LL(*) Date: Mon, 21 Mar 2022 15:47:54 -0400 Organization: A noiseless patient Spider Lines: 48 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <22-03-046@comp.compilers> References: <22-03-039@comp.compilers> <22-03-043@comp.compilers> <22-03-045@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="7768"; mail-complaints-to="abuse@iecc.com" Keywords: LL(1) Posted-Date: 21 Mar 2022 15:52:50 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:2948 On Sun, 20 Mar 2022 20:05:41 +0200, Christopher F Clark wrote: >George Neuner gets this right: > >> Terence Parr both invented LL(*) and is the author of the ANTLR tool. >> AFAIK, Parr's own papers and books are the only sources of information >> about the method. > >> >If is the simplest idea make LL(1) with several conflicts and first >> >speculative trying all paths, and backtrack? > >> No, the simplest idea was LL(k) with a fixed value of 'k'. I don't >> believe Parr developed the method, but he was one of the pioneers of >> using it. Parr authored PCCTS which used LL(k), and early versions of >> ANTLR [prior to LL(*)] also used it. > >> LL(*) eliminates the need for the developer to figure out what 'k' is >> optimal for the grammar: too low results in conflicts, too high may >> waste processing effort. > >Terence's original paper, "Breaking the atomic k-tuple" made LL(k) >feasible, basically by doing each extra amount of lookahead 1 at a time. >Thus,LL(1) if no conflicts done, For those rules with LL(1) conflicts, >try LL(2), etc. No backtracking ever. No speculative execution either(*). >Just figure out how many tokens you need to read before you can >disambiguate which rule applies It is nearly always a fixed number. >If it isn't, the grammar is not LL(k) for any k. And, the if-then-else hack >takes care of one of the main problem cases where it isn't. So Parr did invent a way to make fixed 'k' more practical to use. I was not aware of that - thank you. >The latest version ANTLR4 does a slightly different variation on that, >by building a RTN that solves the problem. That's almost the same as >building an LR parser, but not quite. The only place one notices the >difference is when one has indirect (nested) left recursion. ANTLR4 >doesn't allow that. > >*) syntactic predicates are essentiaily speculative execution, but they >aren't strictly a part of LL(k) ANTLR also has so-called "semantic" predicates which can invoke user supplied functions and continue with or fail the current rule based on the results. George