This defines a class for processing a
Jacc grammar contained
in a file and specified using the popular UNIX yacc syntax for
building a table-driven LR-parser. The
yacc syntax is also
adapted to handle Java code for semantic actions and extended with
several useful additionnal functionalities.
An instance of this class can then be used to generate a Java
program implementing an LR parser for the specified grammar.
It provides methods for:
- reading a grammar by parsing a file containing it;
- building a grammar's objects (terminals, non-terminals, rules);
- analyzing the constructed grammar by computing the canonical
LR(0) states of its viable-prefix finite state automaton and
propagating the LALR(1) lookahead sets;
- showing the grammar with more details as indicated by a verbosity
level.
The most critical (
i.e., complex) part of computation is, of course,
the propagation of the LALR(1) lookahead sets. Traditional
yacc
implementations use the method developed by DeRemer and Penello. I use
an improved method due to Park, Choe, and Chang, which substantially
ameliorates the one by DeRemer and Penello. It is the most efficient
method as far as I know.
The format of the grammar file is essentially the same as that
required by yacc, with some minor differences, and a few
additional features. Not using the additional features makes it
essentially similar to the yacc format. For more details,
please read the description of the Jacc system and
grammar format assumed by this class and the rest of the
hlt.language.syntax package.
For detailed explanations of most constructions and algorithms
used by this package, please refer to the following:
- Alfred Aho, Ravi Sethi, and Jeffrey Ullman, Compilers.
Principles, Techniques, and Tools. Addison-Wesley, 1986.
- Joseph Park, K.M Choe, and C.H. Chang, "A new analysis of
LALR formalisms", ACM Transactions of Programming Languages
and Systems, 7(1), pp. 159-175 (Jan. 85).
- Frank DeRemer, and Thomas Penello, "Efficient computation of
lookahead sets", ACM Transactions of Programming Languages
and Systems, 4(4), pp. 615-749 (Oct. 82).
- Stephen C. Johnson, "Yacc: Yet Another Compiler Compiler,"
Computer Science Technical Report 32. AT&T Bell
Labs, Murray Hill, NJ, 1975. (Reprinted in the 4.3BSD Unix
Programmer's Manual, Supplementary Documents 1, PS1:15.
UC Berkeley, 1986.)