Re: LR(n) parsers

The report "A Practical State Splitting Algorithm for Constructing
LR-parser" describes how to generate lookahead sets and split states so
that that usual LR(0) parsing automaton can accept LR(K) grammar. The
algorithm can detect when further state splitting does not give anything.
I.e. this report tells you how to convert an LALR(1) or SLR(1) parser
generator into and LR(K) generator. The report is based on the algorithm
for calculating lookahead set developed by the authors. That algorithm
was made before DeRemer and Pennello discovered that Tarjans algorithm for
finding strongly connected components could speed up algorithms for
lookahead set. Later results show that combining the authors' and
Tarjan's algorithms gives a very fast lookahead set generating algorithm.


I have another report describing how to extend DeRemer and Pennello
algorithm for lookaheads sets for LALR(1) parser to LALR(K).


"A Practical State Splitting Algorithm for Constructing LR-parsers"
Bent Bruun Kristensen and Ole Lehrmann Madsen
Report number DAIMI PB-115
Available from:
Computer Science Department
AARHUS UNIVERSITY
Ny Munkegade
DK-8000 Aarhus C
Denmark


"Efficient Computation of LALR(k) Look-Ahead sets"
Gurli Rohde
Available from me. (I will need your ordinary mail address).


Karsten Nyblad
TFL, A Danish Telecommunication Research Laboratory
E-mail: karsten@tfl.dk
--

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