Re: Non-LR(k) Languages (Torben Ęgidius Mogensen)
14 Mar 2003 11:19:20 -0500

          From comp.compilers

Related articles
Non-LR(k)Languages (Rob Arthan) (2003-03-09)
Re: Non-LR(k) Languages (Andrei Stefan) (2003-03-14)
Re: Non-LR(k) Languages (2003-03-14)
| List of all articles for this month |

From: (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 <> 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.