[TUHS] Re: Nice video with Brian Kernighan

[Douglas McIlroy <douglas.mcilroy@dartmouth.edu>]

Brian's tribute to the brilliant regex mechanism that awk borrowed
from egrep  spurred memories.

For more than forty years I claimed credit for stimulating Ken to
liberate grep from ed. Then, thanks to TUHS, I learned that I had
merely caused Ken to spring from the closet a program he had already
made for his own use.

There's a related story for egrep. Al Aho made a deterministic
regular-expression recognizer as a faster replacement for the
non-deterministic recognizer in grep. He also extended the domain of
patterns to full regular expressions, including alternation; thus the
"e" in egrep.

About the same time, I built on Norm Shryer's personal calendar
utility. I wanted to generalize Norm's strict syntax for dates to
cover most any (American) representation of dates, and to warn about
tomorrow's calendar as well as today's--where "tomorrow" could extend
across a weekend or holiday.

Egrep was just the tool I needed for picking the dates out of a
free-form calendar file. I wrote a little program that built an egrep
pattern based on today's date. The following mouthful for Saturday,
August 20 covers Sunday and Monday, too. (Note that, in egrep, newline
is a synonym for |, the alternation operator.)

        (^|[ (,;])(([Aa]ug[^ ]* *|(08|8)/)0*20)([^0123456789]|$)
        (^|[ (,;])(([Aa]ug[^ ]* *|(08|8)/)0*21)([^0123456789]|$)
        (^|[ (,;])(([Aa]ug[^ ]* *|(08|8)/)0*22)([^0123456789]|$)

It worked like a charm, except that it took a good part of a minute to
handle even a tiny calendar file. The reason: the state count of the
deterministic automaton was exponentially larger than the regular
regular expression; and egrep had to build the automaton before it
could run it. Al was mortified that an early serious use of egrep
should be such a turkey.

But Al was undaunted. He replaced the automaton construction with an
equivalent lazy algorithm that constructed a state only when the
recognizer was about to visit it. This made egrep into the brilliant
tool that Brian praised.

What I don't know is whether the calendar program stimulated the idea
of lazy implementation, or whether Al, like Ken before him with grep,
already had the idea up his sleeve.

Doug