From: Hans-Peter Diettrich Newsgroups: comp.compilers Subject: Re: Constructing LL(k) tables Date: Mon, 14 Nov 2011 01:56:01 +0100 Organization: Compilers Central Lines: 36 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <11-11-035@comp.compilers> References: <11-11-034@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: leila.iecc.com 1321237235 26716 64.57.183.58 (14 Nov 2011 02:20:35 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Mon, 14 Nov 2011 02:20:35 +0000 (UTC) Keywords: LL(1) Posted-Date: 13 Nov 2011 21:20:35 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.stben.net!news.ecp.fr!news.glorb.com!usenet.stanford.edu!news.iecc.com!nerds-end Xref: x330-a1.tempe.blueboxinc.net comp.compilers:337 Borneq schrieb: > To construct LL(1) table M: > for each production A->alpha do: > for each terminal a from FIRST(alpha) (a<>eps) add production A->alpha > to M[A,a] > if eps is in FIRST(alpha), for each b from FOLLOW(A) add A->alpha to > M[A,b] > > If grammar is not LL(1), in one table position there will be more than > one production. Can I construct LL(k) tables simply by splitting cells > with more than one production? IMO you have already constructed an LL(k) table, which is a list and not a fixed-size array, and which differs from an LL(1) table by having multiple M[*,a] entries. This may be what you mean with "splitting cells", like e.g. M[{A,B},a]. An LL(1) automaton cannot have multiple target states for one terminal, an LL(k) automaton or parser generator can deal with such tables. A PEG analyzer simply ignores all attempts to rewrite M[A,a] by another M[B,a], but the resulting LL(1) table may not represent what you want. You can try to expand such an LL(k) table into LL(k-1), until you reach an LL(1) table - if you are very lucky (exponential explosion). Or you can expand the table structure from M1[A,a] into M2[A,a,b], equivalent to LL(2), and continue until you get a table free of ambiguities - if ever. The problem with LL(k) tables is not their construction, since above list can be constructed by the known algorithm. Instead the problem is the *use* of such a table, that requires an LL(k) automaton, parser generator, or table converter. DoDi