26 Jun 1996 11:34:44 -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: | Jerry Leichter <leichter@smarts.com> |

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

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.