LRGen: LR(1) parser generator


Home Downloads Feedback Comparison Theory Papers Documentation Contact

Papers Implemented In LRGen

On The Translation Of Languages From Left To Right
[by Donald Knuth, 1965, Information and Control]
This paper presents a method of constructing canonical LR(1) parsers that have beneficial properties: 1) no backtracking is ever required by the parser for making a wrong decision, 2) no erroneous reductions are made by the parser when a syntax error is encountered, 3) the parsing time is linear with respect to the length of the input stream. The main disadvantage of these canonical LR(1) parsers is the large size of the parser tables.

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 language-recognition 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 shift-reduce actions and default reductions.

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 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 terminal-transition matrix and the nonterminal-transition 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 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, content and processing of an abstract-syntax tree (AST), thereby offering improved productivity and reliability in the development of computer-language software products.  An example is given which shows how to define the complete translation process from source language to intermediate code.

(c) Copyright Paul B Mann 2018.  All rights reserved.