14 Mar 2003 11:19:20 -0500

Related articles |
---|

Non-LR(k)Languages rda@lemma-one.com (Rob Arthan) (2003-03-09) |

Re: Non-LR(k) Languages andrei@comp.nus.edu.sg (Andrei Stefan) (2003-03-14) |

Re: Non-LR(k) Languages torbenm@diku.dk (2003-03-14) |

From: | torbenm@diku.dk (Torben Ęgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | 14 Mar 2003 11:19:20 -0500 |

Organization: | Department of Computer Science, University of Copenhagen |

References: | 03-03-015 |

Keywords: | parse, LR(1) |

Posted-Date: | 14 Mar 2003 11:19:19 EST |

Rob Arthan <rda@lemma-one.com> writes:

*> I've been looking for an example of a language that can be defined by a*

*> context free grammar (ideally a non-ambiguous one), but not by any LR(k)*

*> grammar.*

The unambiguous grammar below describes the set of even-length

palindromic strings over the alphabet {a,b}

P -> \epsilon

P -> a P a

P -> b P b

it is easy to show that this can't be parsed by LR(k) for any fixed k,

as the question of whether to reduce by the first production or shift

in one of the other two requires lookahead to the end of the string.

It is also relatively easy to proof that no LR(k) grammar for this

language exist, as any grammar would have the same problem.

Basically, any syntax tree describing a palindrome would have to pair

up characters symmetrically about the middle, so the middle of the

string has to be recognized before reduction can be made.

Torben Mogensen

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.