24 Jun 1996 15:03:30 -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) |

[1 later articles] |

From: | platon!adrian@uunet.uu.net (A Johnstone) |

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

Date: | 24 Jun 1996 15:03:30 -0400 |

Organization: | Royal Holloway, Univ of London |

Keywords: | parse, question |

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

Adrian

--

Dr Adrian Johnstone, Dean of the Science Faculty, Dept of Computer Science,

Royal Holloway, University of London, Egham, Surrey, TW20 0EX, England.

Email: adrian@dcs.rhbnc.ac.uk Tel: +44 (0)1784 443425 Fax: +44 (0)1784 443420

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.