[mirror_edk2.git] / Tools / CCode / Source / Pccts / history.txt

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