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