Re: LR(n) parsers

drw@riesz.mit.edu (Dale R. Worley)
Tue, 22 Oct 1991 01:06:22 GMT

          From comp.compilers
Related articles
[5 earlier articles]
Re: LR(n) parsers bburshte@pyrps5.eng.pyramid.com (1991-10-14)
Re: LR(n) parsers mareb@levels.unisa.edu.au (1991-10-15)
Re: LR(n) parsers nickh@harlqn.co.uk (Nick Haines) (1991-10-16)
Re: LR(n) parsers mtxinu!angular!jas@uunet.uu.net (1991-10-18)
Re: LR(n) parsers rockwell@socrates.umd.edu (Raul Deluth Miller-Rockwell) (1991-10-19)
Re: LR(n) parsers schoebel@bs5.informatik.uni-stuttgart.de (Thomas Schoebel) (1991-10-19)
Re: LR(n) parsers drw@riesz.mit.edu (1991-10-22)
Re: LR(n) parsers schoebel@bs5.informatik.uni-stuttgart.de (Thomas Schoebel) (1991-10-24)
Re: LR(n) parsers sankar@Neon.Stanford.EDU (Sriram Sankar) (1991-10-24)
Re: LR(n) parsers ge@sci.kun.nl (1991-10-25)
Re: LR(n) parsers schoebel@bs5.informatik.uni-stuttgart.de (Thomas Schoebel) (1991-10-25)
Re: LR(n) parsers markh@csd4.csd.uwm.edu (1991-11-06)
| List of all articles for this month |
Newsgroups: comp.compilers
From: drw@riesz.mit.edu (Dale R. Worley)
Keywords: parse, LR(1)
Organization: MIT Dept. of Tetrapilotomy, Cambridge, MA, USA
References: 91-10-036 91-10-076
Date: Tue, 22 Oct 1991 01:06:22 GMT

In article 91-10-076 mtxinu!angular!jas@uunet.uu.net (Jim Shankland) writes:
      An *unambiguous* grammar may require k tokens of
      lookahead (k > 0 and finite) to be LR-parsable; but for any such grammar,
      there is an equivalent grammar -- one describing the same language -- that
      requires k-1 tokens of lookahead. By induction, you can take k down to 0.


When was this proven? Last I heard was that it wasn't known of LR(k) was
larger than LR(0). Also, is it known yet if there are unambiguous CF
languages that aren't LR?


Dale
[Maybe he meant 1 rather than 0. -John]
--

Post a followup to this message

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