Re: LR(n) parsers

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


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

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