Fri, 25 Jul 2014 21:58:49 -0400

Related articles |
---|

[17 earlier articles] |

Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (2014-07-20) |

Re: LR(1) Parsing : Error Handling & Recovery cdodd@acm.org (Chris Dodd) (2014-07-21) |

Re: LR(1) Parsing : Error Handling & Recovery DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2014-07-21) |

Re: LR(1) Parsing : Error Handling & Recovery drikosev@otenet.gr (Evangelos Drikos) (2014-07-21) |

Re: LR(1) Parsing : Error Handling & Recovery haberg-news@telia.com (Hans Aberg) (2014-07-21) |

Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (2014-07-21) |

Re: LR(1) Parsing : Error Handling & Recovery gneuner2@comcast.net (George Neuner) (2014-07-25) |

Re: LR(1) Parsing : Error Handling & Recovery cdodd@acm.org (Chris Dodd) (2014-07-26) |

Re: LR(1) Parsing : Error Handling & Recovery DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2014-07-28) |

Re: LR(1) Parsing : Error Handling & Recovery cdodd@acm.org (Chris Dodd) (2014-07-29) |

Re: LR(1) Parsing : Error Handling & Recovery monnier@iro.umontreal.ca (Stefan Monnier) (2014-08-06) |

Re: LR(1) Parsing : Error Handling & Recovery drikosev@otenet.gr (Evangelos Drikos) (2014-08-26) |

Re: LR(1) Parsing : Error Handling & Recovery haberg-news@telia.com (Hans Aberg) (2014-08-29) |

[1 later articles] |

From: | George Neuner <gneuner2@comcast.net> |

Newsgroups: | comp.compilers |

Date: | Fri, 25 Jul 2014 21:58:49 -0400 |

Organization: | A noiseless patient Spider |

References: | 14-07-023 14-07-024 14-07-030 14-07-031 14-07-041 14-07-046 |

Keywords: | parse, theory |

Posted-Date: | 25 Jul 2014 22:38:48 EDT |

On Mon, 21 Jul 2014 06:07:55 +0000 (UTC), Chris Dodd <cdodd@acm.org>

wrote:

*>George Neuner <gneuner2@comcast.net> wrote in news:14-07-041@comp.compilers:*

*>> LL(k) always can be refactored to single token lookahead, but it*

*>> causes an explosion of grammar states. E.g., given a single LL(3)*

*>> rule, an equivalent set of LL(1) rules must match every valid*

*>> combination of tokens at +1, +2 and +3.*

*>*

*>Not true -- LL(k+1) languages are a strict superset of LL(k) languages, so*

*>there exist LL(k) grammars that cannot be refactored to a smaller k.*

Yes and no.

For every LL(k) grammar where both k and the set T of tokens is fixed,

there is an equivalent LL(1) grammar. In the worst case, the

equivalent LL(1) grammar will have k**T rules.

Only where k or T is unbounded, so that the power set of {n:1<=n<=k}

lookahead tokens for some rule is not enumerable, can you not derive

an equivalent in LL(1).

The problem is that an LL({n:1<n<=k}) rule explodes multiplicatively

into an n-level tree of LL(1) rules, with each branch at each level

m<=n having to cover follow(m).

Meaning that it is effectively unworkable for any but small k.

Fortunately, for any reasonable LL(k>1) grammar, k will be bounded and

small, and the grammar will contain just a handful of rules requiring

the maximum k lookahead. Most rules will be LL({n:1<=n<k}) where n is

very small.

George

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.