Re: LR(n) parsers

Thomas Schoebel <schoebel@bs5.informatik.uni-stuttgart.de>
19 Oct 91 10:45:38 GMT

          From comp.compilers

Related articles
[4 earlier articles]
Re: LR(n) parsers anw@maths.nott.ac.uk (1991-10-14)
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: Thomas Schoebel <schoebel@bs5.informatik.uni-stuttgart.de>
Keywords: parse, LR(1)
Organization: IfI, Univ. Stuttgart, W Germany
References: 91-10-036 91-10-076
Date: 19 Oct 91 10:45:38 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.


Let me add a notice: Whether a given grammer is ambiguous is an
undecidable problem (see Hopcroft/Ullman page 200). Since the LR(k)
property is decidable, there are a lot of grammars which are unambiguous
but are *not* LR(k) for any k.


> As for Early's parsing algorithm: it's O(n^3) in general, O(n^2) on
> unambiguous grammars, if my memory isn't shot; but does anyone know how
> its performance compares with an LR(k) parser, on LR(k) grammars, for
> small k? I'll bet it's not all that bad.


There are versions of Earley's algorithm which have the same asymptotic
complexity as LR (k) on LR(k) grammars. See the original Earley paper
(Comm. ACM 13:2 1970, p. 94-102)


-- Thomas
--


Post a followup to this message

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