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 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 abstractsyntax tree (AST), thereby offering improved
productivity and reliability in the development of computerlanguage
software products. An example is given which shows how to define
the complete translation process from source language to intermediate
code.
