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(*)    YES    YES   YES  
GLR  yes      yes    yes 
Papers Related to LR Parser Generation
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, which enables the creation of LALR(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. NOTE: These algorithms have been
implemented in LRSTAR.
Optimization Of Parser Tables For Portable
Compilers [by Dencker, Durre, Heuft, 1984,
TOPLAS] This paper presents matrix structures 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 offer excellent parsing speed.
NOTE: These matrix structures have been implemented in LRSTAR.
Measuring And Extending LR(1) Parser Generation
[by Xin Chen, 2009, PhD dissertation]
This paper is extremely useful to parsergenerator authors and provides a stateoftheart
in depth analysis of the LR parsing methods available. It describes several algorithms
for implementing optimized LR(1) parsertable construction. It also explains why LR(1)
is the best choice for parsing of computer language. NOTE: One of the algorithms described
in this paper is being implemented in LRSTAR, but is difficult and requires a lot of time.
A
Translational BNF Grammar Notation (TBNF)
[by Paul B Mann, 2006, SIGPLAN Notices]
Some new BNF grammar notations are presented which allows one to specify the
structure and content an abstractsyntax tree (AST), thereby offering improved
productivity and reliability in the development of parsers for computerlanguages.
An example is given which shows how to define, in the grammar, the complete translation
process from source language to intermediate language.
NOTE: Most of this TBNF notation has been implemented in LRSTAR.
The FourMatrix LR Parser Tables.
[by Paul B Mann, in the future?]
A further refinement on the optimizedparsertables for portable compilers.
This paper describes the fourmatrixdatastructures useful for veryfast LR parsing.
NOTE: These data structures have been implemented in LRSTAR parsers.
An Efficient LR(*) Parsing Algorithm.
[by Paul B Mann, in the future?]
An efficient method of doing LR(k) nondeterministic parsing at runtime, which
offers advantages over doing LR(k) grammar analysis.
NOTE: This algorithm has been implemented in LRSTAR parsers.
