Sat, 13 Feb 2010 21:33:20 -0500

Related articles |
---|

[9 earlier articles] |

Re: An example LL(K) language that is not LL(K-1) ? kkylheku@gmail.com (Kaz Kylheku) (2010-02-06) |

Re: An example LL(K) language that is not LL(K-1) ? klyjikoo@gmail.com (klyjikoo) (2010-02-06) |

Re: An example LL(K) language that is not LL(K-1) ? slkpg@cox.net (SLK Mail) (2010-02-06) |

Re: An example LL(K) language that is not LL(K-1) ? kkylheku@gmail.com (Kaz Kylheku) (2010-02-10) |

Re: An example LL(K) language that is not LL(K-1) ? cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-10) |

Re: An example LL(K) language that is not LL(K-1) ? klyjikoo@gmail.com (klyjikoo) (2010-02-14) |

Re: An example LL(K) language that is not LL(K-1) ? cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-13) |

From: | Chris F Clark <cfc@shell01.TheWorld.com> |

Newsgroups: | comp.compilers |

Date: | Sat, 13 Feb 2010 21:33:20 -0500 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 10-02-009 10-02-015 10-02-026 10-02-050 10-02-058 |

Keywords: | LL(1) |

Posted-Date: | 13 Feb 2010 21:57:58 EST |

klyjikoo <klyjikoo@gmail.com> writes:

*> Chris F Clark <cfc@shell01.TheWorld.com> wrote:*

*>>the following grammar should work:*

*>>*

*>>*

*>> S := A*

*>> A := B C*

*>> B := b A d // 1 form of recursion*

*>> B := b b A a d // other form of recursion, note the slight difference*

*>> B := a c*

*>> C := A*

*>> C := epsilon*

*>*

*>*

*> Your example also shows the difference between LR(k) and LL(k) grammars,*

*> similar to my example...*

Yes, you are correct, the above language is not LL(2) as I thought,

because both forms of recursion can pile up an indefinitely long

string of b characters before the central "a c" string, the language

cannot be parsed with an LL(k) grammar, becuase you cannot tell

strictly from the prefix what kind of recursion you have.

Obviously, the construction of a language that is precisely LL(2) is

more subtle than I thought. I still know you need at least one

central recursion in the language (otherwise, if the language has only

left recursion or right recursion, it is regular), but how you get it

so that two tokens are required to decipher the recursion rather than

just one (without requiring unbounded numbers of tokens), is something

I clearly don't have an intuition for, and I don't have a parsing text

handy here.

Sorry,

-Chris

******************************************************************************

Chris Clark email: christopher.f.clark@compiler-resources.com

Compiler Resources, Inc. Web Site: http://world.std.com/~compres

23 Bailey Rd voice: (508) 435-5016

Berlin, MA 01503 USA twitter: @intel_chris

------------------------------------------------------------------------------

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.