Re: LR(n) parsers (Boris Burshteyn)
Mon, 14 Oct 91 16:45:38 -0700

          From comp.compilers

Related articles
LR(n) parsers (Steve Boswell) (1991-10-10)
Re: LR(n) parsers (Karsten Nyblad, TFL, Denmark) (1991-10-13)
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: talking about LR(n) parsers (1991-10-15)
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)
[6 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Boris Burshteyn)
Keywords: parse, bibliography, LR(1)
Organization: Compilers Central
References: 91-10-036
Date: Mon, 14 Oct 91 16:45:38 -0700

There were several postings recently regarding fast lr(k)
algorithms, originally started from Steve Boswell's letter. One of the
other approaches is to utilize full LR algorithm, whoes ideas come to the
article of DAVID SPECTOR from SIGPLAN NOTICES, I believe in 1988 or 1989
(excuse me, I do not have the reference handy right now).

I have recently implemented full LR(1) parser in this manner. The
parser runs faster than UCB-derived YACC (2-times), than commercial PCYACC
(~40% faster) , and than BISON ( ~25%) on my test file. I expect to
conclude the work within the next couple of months. There still is a
place for optimization.

Briefly, the algorithm works as follows. First, the LR0 automata
is built. Then, for all the states with reduce-reduce conflicts, paths
wich lead to these states are being split. After that, lookaheads are
calculated for each state with reduce-reduce and/or with shift-reduce
conflicts. I calculated 1-lookaheads, but obviously k-lookaheads may be
calculated either statically, or dynamically at parse time (various
optimization techniques are available, like calculating k+1 lookaheads
from k-lookaheads). After the initial split there is no need for further

Thanks, Boris Burshteyn.
[The reference is David Spector, "Efficient Full LR(1) Parser Generation,"
SIGPLAN 23:12, December 1988, pp. 143-150. All of us serious compiler
nerds have 15 years of SIGPLANs in the attic. -John]

Post a followup to this message

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