Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #336 > unrolled thread

Constructing LL(k) tables

Back to article view | Back to comp.compilers

Contents

  Constructing LL(k) tables Borneq <a.moderacja@gmail.com> - 2011-11-13 04:57 -0800
    Re: Constructing LL(k) tables Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2011-11-14 01:56 +0100

#336 — Constructing LL(k) tables

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? Which is algorithm to production
choosing ?

[toc] | [next] | [standalone]

#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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web