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


Jerry Leichter <leichter@smarts.com> 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?




Ilias
--

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