| The History of PCCTS | |
| The Purdue Compiler-Construction Tool Set | |
| Terence Parr | |
| Parr Research Corporation | |
| Minneapolis, Minnesota | |
| and | |
| University of Minnesota | |
| Army High Performance Computing Research Center | |
| [Updated 8-7-94] | |
| The PCCTS project began as a parser-generator project for a gra- | |
| duate course at Purdue University in the Fall of 1988 taught by Hank | |
| Dietz- translator-writing systems. Under the guidance of Professor | |
| Dietz, the parser generator, ANTLR (originally called YUCC), continued | |
| after the termination of the course and eventually became the subject | |
| of Terence Parr's Master's thesis. Originally, lexical analysis was | |
| performed via ALX which was soon replaced by Will Cohen's DLG in the | |
| Fall of 1989 (DFA-based lexical-analyzer generator, also an offshoot | |
| of the graduate translation course). | |
| The alpha version of ANTLR was totally rewritten resulting in | |
| 1.00B. Version 1.00B was released via an internet newsgroup | |
| (comp.compilers) posting in February of 1990 and quickly gathered a | |
| large following. 1.00B generated only LL(1) parsers, but allowed the | |
| merged description of lexical and syntactic analysis. It had rudimen- | |
| tary attribute handling similar to that of YACC and did not incor- | |
| porate rule parameters or return values; downward inheritance was very | |
| awkward. 1.00B-generated parsers terminated upon the first syntax | |
| error. Lexical classes (modes) were not allowed and DLG did not have | |
| an interactive mode. | |
| Upon starting his Ph.D. at Purdue in the Fall of 1990, Terence | |
| Parr began the second total rewrite of ANTLR. The method by which | |
| grammars may be practically analyzed to generate LL(k) lookahead | |
| information was discovered in August of 1990 just before his return. | |
| Version 1.00 incorporated this algorithm and included the AST mechan- | |
| ism, lexical classes, error classes, and automatic error recovery; | |
| code quality and portability were higher. In February of 1992 1.00 | |
| was released via an article in SIGPLAN Notices. Peter Dahl, Ph.D. | |
| candidate, and Professor Matt O'Keefe (both at the University of Min- | |
| nesota) tested this version extensively. Dana Hoggatt (Micro Data | |
| Base Systems, Inc.) came up with the idea of error grouping (strings | |
| attached to non-terminals) and tested 1.00 heavily. | |
| Version 1.06 was released in December 1992 and represented a | |
| large feature enhancement over 1.00. For example, rudimentary seman- | |
| tic predicates were introduced, error messages were significantly | |
| improved for k>1 lookahead and ANTLR parsers could indicate that loo- | |
| kahead fetches were to occur only when necessary for the parse | |
| Page 1 | |
| PCCTS | |
| (normally, the lookahead "pipe" was constantly full). Russell Quong | |
| joined the project in the Spring of 1992 to aid in the semantic predi- | |
| cate design. Beginning and advanced tutorials were created and | |
| released as well. A makefile generator was included that sets up | |
| dependencies and such correctly for ANTLR and DLG. Very few 1.00 | |
| incompatibilities were introduced (1.00 was quite different from 1.00B | |
| in some areas). | |
| 1.10 was released on August 31, 1993 and incorporated bug fixes, | |
| a few feature enhancements and a major new capability - an arbitrary | |
| lookahead operator (syntactic predicate), (alpha)?beta. This feature | |
| was co-designed with Professor Russell Quong also at Purdue. To sup- | |
| port infinite lookahead, a preprocessor flag, ZZINF_LOOK, was created | |
| that forced the ANTLR() macro to tokenize all input prior to parsing. | |
| Hence, at any moment, an action or predicate can see the entire input | |
| sentence. The predicate mechanism of 1.06 was extended to allow mul- | |
| tiple predicates to be hoisted; the syntactic context of a predicate | |
| was also moved along with the predicate. | |
| In February of 1994, SORCERER (a simple tree-parser generator) | |
| was released. This tool allows the user to parse child-sibling trees | |
| by specifying a grammar rather than building a recursive-descent tree | |
| walker by hand. Work towards a library of tree transformations is | |
| underway. Aaron Sawdey at The University of Minnesota became a second | |
| author of SORCERER after the initial release. | |
| On April 1, 1994, PCCTS 1.20 was released. This was the first | |
| version to actively support C++ output. It also included important | |
| fixes regarding semantic predicates and (..)+ subrules. This version | |
| also introduced token classes, the "not" operator, and token ranges. | |
| On June 19, 1994, SORCERER 1.00B9 was released. Gary Funck of | |
| Intrepid Technology joined the SORCERER team and provided very valu- | |
| able suggestions regarding the "transform" mode of SORCERER. | |
| On August 8, 1994, PCCTS 1.21 was released. It mainly cleaned up | |
| the C++ output and included a number of bug fixes. | |
| From the 1.21 release forward, the maintenance and support of all | |
| PCCTS tools will be primarily provided by Parr Research Corporation, | |
| Minneapolis MN---an organization founded on the principles of excel- | |
| lence in research and integrity in business; we are devoted to provid- | |
| ing really cool software tools. Please see file PCCTS.FUTURE for more | |
| information. All PCCTS tools currently in the public domain will con- | |
| tinue to be in the public domain. | |
| Looking towards the future, a graphical user-interface is in the | |
| design phase. This would allow users to view the syntax diagram | |
| representation of their grammars and would highlight nondeterministic | |
| productions. Parsing can be traced graphically as well. This system | |
| will be built using a multiplatform window library. We also antici- | |
| pate the introduction of a sophisticated error handling mechanism | |
| called "parser exception handling" in a near future release. | |
| Page 2 | |
| PCCTS | |
| Currently, PCCTS is used at over 1000 known academic, government, | |
| and commercial sites in 37 countries. Of course, the true number of | |
| users is unknown due to the large number of ftp sites. | |
| Credits | |
| _____________________________________________________________________________ | |
| _____________________________________________________________________________ | |
| |ANTLR 1.00A Terence Parr Hank Dietz | | |
| |ALX Terence Parr Hank Dietz | | |
| |ANTLR 1.00B Terence Parr Hank Dietz, Will Cohen | | |
| |DLG 1.00B Will Cohen Terence Parr, Hank Dietz | | |
| |NFA Relabelling Will Cohen | | |
| |LL(k) analysis Terence Parr Hank Dietz | | |
| |ANTLR 1.00 Terence Parr Hank Dietz, Will Cohen | | |
| |DLG 1.00 Will Cohen Terence Parr, Hank Dietz | | |
| |ANTLR 1.06 Terence Parr Will Cohen, Russell Quong, Hank Dietz| | |
| |DLG 1.06 Will Cohen Terence Parr, Hank Dietz | | |
| |ANTLR 1.10 Terence Parr Will Cohen, Russell Quong | | |
| |ANTLR 1.20 Terence Parr Will Cohen, Russell Quong | | |
| |ANTLR 1.21 Terence Parr Russell Quong | | |
| |DLG 1.10 Will Cohen Terence Parr | | |
| |DLG 1.20 Will Cohen Terence Parr | | |
| |DLG 1.21 Terence Parr | | |
| |Semantic predicates Terence Parr Russell Quonq | | |
| |Syntactic predicates Terence Parr Russell Quonq | | |
| |SORCERER 1.00A Terence Parr | | |
| |SORCERER 1.00B Terence Parr Aaron Sawdey | | |
| |SORCERER 1.00B9 Terence Parr Aaron Sawdey, Gary Funck | | |
| |___________________________________________________________________________| | |
| Page 3 | |