Theoretical Considerations
LR Parsing Algorithms

Builds State Machine Of Type 
Computes Lookaheads From 
Does Conflict Resolution By 
Parser 
LR(0) 
Canonical LR(1) 
Minimal LR(1) 
Minimal LR(k) 
Grammar 
State Machine 
Deterministic Parsing 
Non Deterministic Parsing 
Ambiguous Parsing 
LR(0)  yes     Has no lookaheads  Parsers are not very useful 
SLR(1)  yes     yes   Conflicts in grammar may produce an incorrect parser 
LALR(1)  yes      yes  Conflicts in grammar may produce an incorrect parser 
Canonical LR(1)   yes     yes  Conflicts in grammar may produce an incorrect parser 
Minimal LR(1)    yes    yes  Conflicts in grammar may produce an incorrect parser 
LR(k)     yes   yes  yes   
LR(*)    LRSTAR    LRSTAR   LRSTAR  
GLR  yes      yes    yes 
Papers Implemented In LRSTAR
Efficient Computation Of LALR(1) LookAhead
Sets [by DeRemer and Pennello, 1982, TOPLAS]
In 1979, this paper
was first published in SIGPlan Notices. It presents an elegant algorithm
for computing the the lookahead sets for an LR(0) state machine or
minimal LR(1) state machine, which enables the creation of LALR(1) or
minimal LR(1) parsers. The paper
also contains an algorithm, called DiGraph, for computing transitive
closure of directed graphs which performs about 3 times the speed of
Warshall's algorithm, for sparsely populated graphs.
Optimization Of Parser Tables For Portable
Compilers [by Dencker, Durre, Heuft, 1984,
TOPLAS] This paper
presents a matrix type of structure for parser tables. Making of a
boolean matrix allows one to use graph coloring on both the
terminaltransition matrix and the nonterminaltransition matrix. This
provides small parser tables which still offer excellent parsing speed,
which is linear in relation to the size of the input stream. Note: the
size of the grammar has no effect on parsing speed, which is the same
for all grammars (large or small).
A Practical General Method For Constructing LR(k)
Parsers [by David Pager, 1977, Acta Informatica]
This paper presents a method of constructing LR(1) parsers that are nearly the same
size as LALR(1) parsers, but have the increased languagerecognition
power of LR(1). The technique is to modify the canonical LR(1) state
building algorithm so that it merges states that are compatible. One
disadvantage is the loss of property #2 mentioned above. One advantage is
an increase in speed with the use of shiftreduce actions and default
reductions.
