Re: LL vs LR languages (not grammars) (Ilias Kastanas)
30 Jun 1996 16:41:10 -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: (Ilias Kastanas)
Newsgroups: comp.compilers,
Date: 30 Jun 1996 16:41:10 -0400
Organization: Caltech Alumni Association
Expires: July 9, 1996
References: 96-06-103 96-06-109
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.)

Jerry Leichter <> wrote:
>I'm not sure what L(oo) would be. A machine with truely infinite lookahead,

presumably, unbounded lookahead (since we are not dealing with
      strings of length >= omega)

>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

Such a machine, of course, cannot be finite; it needs an infinite
      number of states. But in that case we can forget about lookahead; the
      machine can proceed by table lookup.

>*any* language - not just the computable ones! I'll assume you are looking
>for languages that are not LL(k) for any k.

This seems sensible, because unbounded lookahead has another problem.
      Suppose the machine is finite after all -- a finite control and a stack.
      To really use such lookahead, it must be allowed stack operations (else
      there is a de facto bound k). But in that case it is effectively a
      2-way PDA, and can recognize non-CFLs like {a^n b^n c^n}.

| 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.

Somehow this seems to be what unbounded lookahead tries to fix; the
      machine wants to be able to "see" the far-away 'e' or 'o' symbol.

What if we resurrect a weak version of it: the machine cannot store
      extensive information about what it sees in long lookahead forays... i.e.
      no stack use; it can only check for finitely many possibilities, through
      its finite control.

What is the effect of adding such a capability? It does not manage,
      it seems, nondeterministic tasks like recognizing {ww^R}. It amounts to
      allowing the finite control a stint as a 2-way FA. 2-way FAs are of course
      equivalent to FAs as to acceptance. But what happens here?


Post a followup to this message

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