Re: LR(n) parsers

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

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