Re: LR(n) parsers

In article 91-10-036 whatis@ucsd.edu (Steve Boswell) writes:


> What sort of easily-describable or commonly-occuring grammars are
> ambiguous for any amount of lookahead? ... Has there been any work
> done on LR(n) parsing engines like this? 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]


There are other general parsing schemes, such as Tomita's, or more
recently Rekers' GLR algorithm, developed by Jan Rekers at CWI in
Amsterdam. This will parse any context-free language, and does so much
faster than Earley's algorithm, except in cases of extreme ambiguity.
Timings on a SPARCstation 1:


1. Parsing a Pascal program (timings in seconds)


tokens 12 28 92 148 227 371 636 878


YACC - - - - 0.1 0.2 0.3 0.3
GLR 0.01 0.03 0.08 0.14 0.21 0.37 0.65 0.88
Earley 0.09 0.24 0.92 1.93 - - - -


2. Parsing a program with a highly ambiguous grammar:


a := b {+b}*


`+'s 1 3 5 7 10 13 15 17 20


possible parses 1 5 42 429 17k 743k 10M 130M 7G
Earley parse time 0.11 0.16 0.24 0.29 0.41 0.54 0.65 0.76 1.01
GLR parse time 0.02 0.02 0.04 0.09 0.19 0.43 0.69 1.08 1.98


The GLR was written in LeLisp and compiled with `Complice'. YACC is
YACC. The Earley was Freeley's implementation in Scheme, compiled with
T. N.b. long input sequences caused an apparently infinite sequence of
garbage collections for the Earley.


For more information, contact Jan (rekers@cwi.nl)
__
Nick Haines nickh@uk.co.harlqn tel: +44-223-872522
Harlequin Limited fax: +44-223-872519
Barrington Hall, Barrington, Cambridge, CB2 5RG, England.
--

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