Re: LL vs LR languages (not grammars)

A Johnstone wrote:
| We're looking at top down vs bottom up parsers with infinite
| lookahead. Everybody knows that LL(1) grammars are more restrictive
| than LR(1) grammars, but are there any _languages_ which are
| inherently LR and not LL(oo)? (LL with infinite lookahead, ie LL(k)
| with k = oo.)


I'm not sure what L(oo) would be. A machine with truely infinite lookahead,
which could switch to a state on for each possible lookahead, could recognize
*any* language - not just the computable ones! I'll assume you are looking
for languages that are not LL(k) for any k.


| Note that I am assuming (1) that infinite lookahead is
| available, so that LL problems associated with left factorisation are
| done away with, and that algorithms to remove (2) epsilon productions
| and (3) left recursion are also applied to the grammar. Under these
| assumptions, is top down as powerful as bottom up? We seem to have
| managed to convince ourselves that for every language described by an
| LR grammar there is a grammar without left recursion that describes the
| same language.


Yes, such language exist. Here's a simple one:


L = { x^{2n}y^{2n} e, x^{2n+1}y^{2n+1} o}


I can't give you a formal proof off-hand, but should be pretty clear that
grammars for L must have roughly the form:


S <- E e
S <- O o
E <- x O y
E <- lambda
O <- x E y


This is easy to parse in LR(1) since you get to wait for the trailing "e" or
"o" before selecting a production for S. On the other hand, an LL(k) grammar,
if handed a string that starts with k+1 x's, is stuck - it must at that point
"commit itself" to on production or another (from among left-recursion-removed
versions of the first two productions), and it can't possibly do so.


-- Jerry
--

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