Re: Constructing LL(k) tables

Hans-Peter Diettrich <>
Mon, 14 Nov 2011 01:56:01 +0100

          From comp.compilers

Related articles
Constructing LL(k) tables (Borneq) (2011-11-13)
Re: Constructing LL(k) tables (Hans-Peter Diettrich) (2011-11-14)
| List of all articles for this month |

From: Hans-Peter Diettrich <>
Newsgroups: comp.compilers
Date: Mon, 14 Nov 2011 01:56:01 +0100
Organization: Compilers Central
References: 11-11-034
Keywords: LL(1)
Posted-Date: 13 Nov 2011 21:20:35 EST

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.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.