Mon, 14 Nov 2011 01:56:01 +0100

Related articles |
---|

Constructing LL(k) tables a.moderacja@gmail.com (Borneq) (2011-11-13) |

Re: Constructing LL(k) tables DrDiettrich1@aol.com (Hans-Peter Diettrich) (2011-11-14) |

From: | Hans-Peter Diettrich <DrDiettrich1@aol.com> |

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.

DoDi

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.