30 Jun 1996 16:41:10 -0400

Related articles |
---|

LL vs LR languages (not grammars) platon!adrian@uunet.uu.net (1996-06-24) |

Re: LL vs LR languages (not grammars) leichter@smarts.com (Jerry Leichter) (1996-06-26) |

Re: LL vs LR languages (not grammars) ikastan@alumnae.caltech.edu (1996-06-30) |

Re: LL vs LR languages (not grammars) fjh@mundook.cs.mu.OZ.AU (1996-06-30) |

Re: LL vs LR languages (not grammars) schoebel@minnie.informatik.uni-stuttgart.de (1996-07-01) |

Re: LL vs LR languages (not grammars) ikastan@alumnae.caltech.edu (1996-07-01) |

Re: LL vs LR languages (not grammars) ikastan@alumnae.caltech.edu (1996-07-02) |

Re: LL vs LR languages (not grammars) schoebel@minnie.informatik.uni-stuttgart.de (1996-07-05) |

From: | ikastan@alumnae.caltech.edu (Ilias Kastanas) |

Newsgroups: | comp.compilers,comp.compilers.tools.pccts |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.