Re: LR(n) parsers

mtxinu!angular! (Jim Shankland)
Fri, 18 Oct 1991 04:55:05 GMT

          From comp.compilers

Related articles
[2 earlier articles]
Re: LR(n) parsers (1991-10-14)
Re: LR(n) parsers (1991-10-14)
Re: LR(n) parsers (1991-10-14)
Re: LR(n) parsers (1991-10-14)
Re: LR(n) parsers (1991-10-15)
Re: LR(n) parsers (Nick Haines) (1991-10-16)
Re: LR(n) parsers mtxinu!angular! (1991-10-18)
Re: LR(n) parsers (Raul Deluth Miller-Rockwell) (1991-10-19)
Re: LR(n) parsers (Thomas Schoebel) (1991-10-19)
Re: LR(n) parsers (1991-10-22)
Re: LR(n) parsers (Thomas Schoebel) (1991-10-24)
Re: LR(n) parsers sankar@Neon.Stanford.EDU (Sriram Sankar) (1991-10-24)
Re: LR(n) parsers (1991-10-25)
[2 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: mtxinu!angular! (Jim Shankland)
Keywords: yacc, parse, lisp, grammar
Organization: Angular Systems
References: 91-10-036
Date: Fri, 18 Oct 1991 04:55:05 GMT

In article 91-10-036 Steve Boswell <> writes:
>What sort of easily-describable or commonly-occuring grammars are
>ambiguous for any amount of lookahead? .... My idea is to do a normal LR(1)
>transition table & parse in parallel with all possibilities every time
>there is more than one.
>[What you're proposing is more or less Earley's parsing scheme, which is
>quite slow. -John]

As long as we're getting pedantic about "automata" (alert the media!
there may be a hidden agenda!), let me point out that an ambiguous grammar
is ambiguous regardless of the parsing technique used: there will be two
distinct parses for at least one string in the language, regardless of
amount of lookahead. So if it's ambiguous, it's always "ambiguous for any
amount of lookahead". 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.

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.


Post a followup to this message

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