1 2 3 4 The History of PCCTS 5 6 The Purdue Compiler-Construction Tool Set 7 8 9 Terence Parr 10 Parr Research Corporation 11 Minneapolis, Minnesota 12 and 13 University of Minnesota 14 Army High Performance Computing Research Center 15 16 [Updated 8-7-94] 17 18 19 The PCCTS project began as a parser-generator project for a gra- 20duate course at Purdue University in the Fall of 1988 taught by Hank 21Dietz- translator-writing systems. Under the guidance of Professor 22Dietz, the parser generator, ANTLR (originally called YUCC), continued 23after the termination of the course and eventually became the subject 24of Terence Parr's Master's thesis. Originally, lexical analysis was 25performed via ALX which was soon replaced by Will Cohen's DLG in the 26Fall of 1989 (DFA-based lexical-analyzer generator, also an offshoot 27of the graduate translation course). 28 29 The alpha version of ANTLR was totally rewritten resulting in 301.00B. Version 1.00B was released via an internet newsgroup 31(comp.compilers) posting in February of 1990 and quickly gathered a 32large following. 1.00B generated only LL(1) parsers, but allowed the 33merged description of lexical and syntactic analysis. It had rudimen- 34tary attribute handling similar to that of YACC and did not incor- 35porate rule parameters or return values; downward inheritance was very 36awkward. 1.00B-generated parsers terminated upon the first syntax 37error. Lexical classes (modes) were not allowed and DLG did not have 38an interactive mode. 39 40 Upon starting his Ph.D. at Purdue in the Fall of 1990, Terence 41Parr began the second total rewrite of ANTLR. The method by which 42grammars may be practically analyzed to generate LL(k) lookahead 43information was discovered in August of 1990 just before his return. 44Version 1.00 incorporated this algorithm and included the AST mechan- 45ism, lexical classes, error classes, and automatic error recovery; 46code quality and portability were higher. In February of 1992 1.00 47was released via an article in SIGPLAN Notices. Peter Dahl, Ph.D. 48candidate, and Professor Matt O'Keefe (both at the University of Min- 49nesota) tested this version extensively. Dana Hoggatt (Micro Data 50Base Systems, Inc.) came up with the idea of error grouping (strings 51attached to non-terminals) and tested 1.00 heavily. 52 53 Version 1.06 was released in December 1992 and represented a 54large feature enhancement over 1.00. For example, rudimentary seman- 55tic predicates were introduced, error messages were significantly 56improved for k>1 lookahead and ANTLR parsers could indicate that loo- 57kahead fetches were to occur only when necessary for the parse 58 59 60 61 Page 1 62 63 PCCTS 64 65 66(normally, the lookahead "pipe" was constantly full). Russell Quong 67joined the project in the Spring of 1992 to aid in the semantic predi- 68cate design. Beginning and advanced tutorials were created and 69released as well. A makefile generator was included that sets up 70dependencies and such correctly for ANTLR and DLG. Very few 1.00 71incompatibilities were introduced (1.00 was quite different from 1.00B 72in some areas). 73 74 1.10 was released on August 31, 1993 and incorporated bug fixes, 75a few feature enhancements and a major new capability - an arbitrary 76lookahead operator (syntactic predicate), (alpha)?beta. This feature 77was co-designed with Professor Russell Quong also at Purdue. To sup- 78port infinite lookahead, a preprocessor flag, ZZINF_LOOK, was created 79that forced the ANTLR() macro to tokenize all input prior to parsing. 80Hence, at any moment, an action or predicate can see the entire input 81sentence. The predicate mechanism of 1.06 was extended to allow mul- 82tiple predicates to be hoisted; the syntactic context of a predicate 83was also moved along with the predicate. 84 85 In February of 1994, SORCERER (a simple tree-parser generator) 86was released. This tool allows the user to parse child-sibling trees 87by specifying a grammar rather than building a recursive-descent tree 88walker by hand. Work towards a library of tree transformations is 89underway. Aaron Sawdey at The University of Minnesota became a second 90author of SORCERER after the initial release. 91 92 On April 1, 1994, PCCTS 1.20 was released. This was the first 93version to actively support C++ output. It also included important 94fixes regarding semantic predicates and (..)+ subrules. This version 95also introduced token classes, the "not" operator, and token ranges. 96 97 On June 19, 1994, SORCERER 1.00B9 was released. Gary Funck of 98Intrepid Technology joined the SORCERER team and provided very valu- 99able suggestions regarding the "transform" mode of SORCERER. 100 101 On August 8, 1994, PCCTS 1.21 was released. It mainly cleaned up 102the C++ output and included a number of bug fixes. 103 104 From the 1.21 release forward, the maintenance and support of all 105PCCTS tools will be primarily provided by Parr Research Corporation, 106Minneapolis MN---an organization founded on the principles of excel- 107lence in research and integrity in business; we are devoted to provid- 108ing really cool software tools. Please see file PCCTS.FUTURE for more 109information. All PCCTS tools currently in the public domain will con- 110tinue to be in the public domain. 111 112 Looking towards the future, a graphical user-interface is in the 113design phase. This would allow users to view the syntax diagram 114representation of their grammars and would highlight nondeterministic 115productions. Parsing can be traced graphically as well. This system 116will be built using a multiplatform window library. We also antici- 117pate the introduction of a sophisticated error handling mechanism 118called "parser exception handling" in a near future release. 119 120 121 122 123 Page 2 124 125 PCCTS 126 127 128 Currently, PCCTS is used at over 1000 known academic, government, 129and commercial sites in 37 countries. Of course, the true number of 130users is unknown due to the large number of ftp sites. 131 Credits 132 133_____________________________________________________________________________ 134_____________________________________________________________________________ 135|ANTLR 1.00A Terence Parr Hank Dietz | 136|ALX Terence Parr Hank Dietz | 137|ANTLR 1.00B Terence Parr Hank Dietz, Will Cohen | 138|DLG 1.00B Will Cohen Terence Parr, Hank Dietz | 139|NFA Relabelling Will Cohen | 140|LL(k) analysis Terence Parr Hank Dietz | 141|ANTLR 1.00 Terence Parr Hank Dietz, Will Cohen | 142|DLG 1.00 Will Cohen Terence Parr, Hank Dietz | 143|ANTLR 1.06 Terence Parr Will Cohen, Russell Quong, Hank Dietz| 144|DLG 1.06 Will Cohen Terence Parr, Hank Dietz | 145|ANTLR 1.10 Terence Parr Will Cohen, Russell Quong | 146|ANTLR 1.20 Terence Parr Will Cohen, Russell Quong | 147|ANTLR 1.21 Terence Parr Russell Quong | 148|DLG 1.10 Will Cohen Terence Parr | 149|DLG 1.20 Will Cohen Terence Parr | 150|DLG 1.21 Terence Parr | 151|Semantic predicates Terence Parr Russell Quonq | 152|Syntactic predicates Terence Parr Russell Quonq | 153|SORCERER 1.00A Terence Parr | 154|SORCERER 1.00B Terence Parr Aaron Sawdey | 155|SORCERER 1.00B9 Terence Parr Aaron Sawdey, Gary Funck | 156|___________________________________________________________________________| 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 Page 3 186 187