Re: LR(n) parsers

In article 91-10-036 Steve Boswell <whatis@ucsd.edu> 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.


jas
--

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