Re: Constructing LL(k) tables

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

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