Re: Non-LR(k) Languages

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

Return to the comp.compilers page.
Search the comp.compilers archives again.