pd.if.org Git - pccts/blob - history.txt

   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 \f
  63                                                                  PCCTS
  64
  65
  66 (normally,  the  lookahead "pipe" was constantly full).  Russell Quong
  67 joined the project in the Spring of 1992 to aid in the semantic predi-
  68 cate  design.   Beginning  and  advanced  tutorials  were  created and
  69 released as well.  A makefile generator  was  included  that  sets  up
  70 dependencies  and  such  correctly  for  ANTLR and DLG.  Very few 1.00
  71 incompatibilities were introduced (1.00 was quite different from 1.00B
  72 in some areas).
  73
  74      1.10 was released on August 31, 1993 and incorporated bug  fixes,
  75 a  few  feature enhancements and a major new capability - an arbitrary
  76 lookahead operator (syntactic predicate), (alpha)?beta.  This  feature
  77 was  co-designed with Professor Russell Quong also at Purdue.  To sup-
  78 port infinite lookahead, a preprocessor flag, ZZINF_LOOK, was  created
  79 that  forced the ANTLR() macro to tokenize all input prior to parsing.
  80 Hence, at any moment, an action or predicate can see the entire  input
  81 sentence.   The predicate mechanism of 1.06 was extended to allow mul-
  82 tiple predicates to be hoisted; the syntactic context of  a  predicate
  83 was also moved along with the predicate.
  84
  85      In February of 1994, SORCERER (a  simple  tree-parser  generator)
  86 was  released.  This tool allows the user to parse child-sibling trees
  87 by specifying a grammar rather than building a recursive-descent  tree
  88 walker  by  hand.   Work  towards a library of tree transformations is
  89 underway.  Aaron Sawdey at The University of Minnesota became a second
  90 author of SORCERER after the initial release.
  91
  92      On April 1, 1994, PCCTS 1.20 was released.  This  was  the  first
  93 version  to  actively  support C++ output.  It also included important
  94 fixes regarding semantic predicates and (..)+ subrules.  This  version
  95 also introduced token classes, the "not" operator, and token ranges.
  96
  97      On June 19, 1994, SORCERER 1.00B9 was released.   Gary  Funck  of
  98 Intrepid  Technology  joined the SORCERER team and provided very valu-
  99 able suggestions regarding the "transform" mode of SORCERER.
 100
 101      On August 8, 1994, PCCTS 1.21 was released.  It mainly cleaned up
 102 the C++ output and included a number of bug fixes.
 103
 104      From the 1.21 release forward, the maintenance and support of all
 105 PCCTS  tools  will be primarily provided by Parr Research Corporation,
 106 Minneapolis MN---an organization founded on the principles  of  excel-
 107 lence in research and integrity in business; we are devoted to provid-
 108 ing really cool software tools.  Please see file PCCTS.FUTURE for more
 109 information.  All PCCTS tools currently in the public domain will con-
 110 tinue to be in the public domain.
 111
 112      Looking towards the future, a graphical user-interface is in  the
 113 design  phase.   This  would  allow  users  to view the syntax diagram
 114 representation of their grammars and would highlight  nondeterministic
 115 productions.   Parsing can be traced graphically as well.  This system
 116 will be built using a multiplatform window library.  We  also  antici-
 117 pate  the  introduction  of  a  sophisticated error handling mechanism
 118 called "parser exception handling" in a near future release.
 119
 120
 121
 122
 123                                                                 Page 2
 124 \f
 125                                                                  PCCTS
 126
 127
 128      Currently, PCCTS is used at over 1000 known academic, government,
 129 and  commercial  sites in 37 countries.  Of course, the true number of
 130 users 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 \f