LRSTAR: LR(*) parser generator for C++


Home Downloads Feedback Comparison Theoretical Documentation Contact

Theoretical Considerations

LR Parsing Algorithms

Builds State Machine Of Type Computes Lookaheads From Does Conflict Resolution By
Canonical LR(1) Minimal LR(1) Minimal LR(k)
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
GLR yes yes yes

Papers Related to LR Parser Generation

Efficient Computation Of LALR(1) Look-Ahead 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 look-ahead 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 terminal-transition matrix and the nonterminal-transition 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 parser-generator authors and provides a state-of-the-art in depth analysis of the LR parsing methods available. It describes several algorithms for implementing optimized LR(1) parser-table 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 abstract-syntax tree (AST), thereby offering improved productivity and reliability in the development of parsers for computer-languages.  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 Four-Matrix LR Parser Tables.
[by Paul B Mann, in the future?]
A further refinement on the optimized-parser-tables for portable compilers. This paper describes the four-matrix-data-structures useful for very-fast 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.

(c) Copyright LRTEC 2020.  All rights reserved.