[COFF] [TUHS] Re: Regex archaeology

[Nelson H. F. Beebe via COFF]

Will Senn asked about ALGOL 60 and regular expressions.

Here are some large bibliographic sources in those areas:

	https://www.math.utah.edu/pub/tex/bib/algol68.bib
	https://www.math.utah.edu/pub/tex/bib/algol-bulletin.bib
	https://www.math.utah.edu/pub/tex/bib/string-matching.bib

[As usual, change the final ".bib" to ".html" if you like to have live
hyperlinks in Web browser.]

Russ Cox's fine work on regexp engines is recorded in the latter.

Recently, GNU gawk switched from its older regexp engine to a new one
with Unicode support, MINRX, written by Mike Haertel.  It has been
under discussion in the list archives at

	https://lists.gnu.org/mailman/private/gawk-devel/

and Mike is actively working on tuning it.

In my recent test builds at Utah on O(100) physical and virtual
machines, the test release, gawk-5.4.1a, has passed all of its tests
on a majority of machines, and most of the tests on several others.
For the latter, the causes of the test failures are mostly due to
peculiarities of those systems, and the regexp tests all pass.  I
expect that there will be an official gawk release in the next few
weeks.  Thus, Will can play with both the Cox and Haertel engines for
his own work.

The Cox engine prevents O(N**2) growth in run times for some unusual,
and also unlikely, regular expressions, which is a BIG achievement in
string searching. I don't know how the Haertel engine fares in that
area.  Perhaps other list readers can comment?

-------------------------------------------------------------------------------
- Nelson H. F. Beebe                    Tel: +1 801 581 5254                  -
- University of Utah                                                          -
- Department of Mathematics, 110 LCB    Internet e-mail: beebe at math.utah.edu  -
- 155 S 1400 E RM 233                       beebe at acm.org  beebe at computer.org -
- Salt Lake City, UT 84112-0090, USA    URL: https://www.math.utah.edu/~beebe -
-------------------------------------------------------------------------------