Re: LL vs LR languages (not grammars)

Jerry Leichter <>
26 Jun 1996 11:34:44 -0400

          From comp.compilers

Related articles
LL vs LR languages (not grammars) platon! (1996-06-24)
Re: LL vs LR languages (not grammars) (Jerry Leichter) (1996-06-26)
Re: LL vs LR languages (not grammars) (1996-06-30)
Re: LL vs LR languages (not grammars) (1996-06-30)
Re: LL vs LR languages (not grammars) (1996-07-01)
Re: LL vs LR languages (not grammars) (1996-07-01)
Re: LL vs LR languages (not grammars) (1996-07-02)
Re: LL vs LR languages (not grammars) (1996-07-05)
| List of all articles for this month |

From: Jerry Leichter <>
Newsgroups: comp.compilers,
Date: 26 Jun 1996 11:34:44 -0400
Organization: System Management ARTS
References: 96-06-103
Keywords: parse

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

Post a followup to this message

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