4 Mar
2023
4 Mar
'23
1:19 a.m.
On 3/3/23 6:42 AM, Ralph Corderoy wrote:
I think Grant is after what Russ addresses in sentence
2. :-)
You are mostly correct. The motivation for this thread is very much so
wanting to learn "how best to use today's regular expression
implementations". However there is also the part of me that wants to
have a little bit of understanding behind why the former is the case.
Yes, Friedl does show that wonderfully. From long-ago
memory, Friedl
understands enough to have diagrams of NFAs and DFAs clocking through
their inputs, showing the differences in number of states, etc.
It seems like I need to find another copy of Friedl's book. -- My
current copy is boxed up for a move nearly 1k miles away. :-/
Yes, Friedl says an NFA must recursively backtrack.
As Russ says in #3,
it was a ‘widespread belief’. Friedl didn't originate it; I ‘knew’ it
before reading his book. Friedl was at the sharp end of regexps,
needing to process large amounts of text, at Yahoo! IIRC. He
investigated how the programs available behaved; he didn't start at the
theory and come up with a new program best suited to his needs.
It sounds like I'm coming from a similar position of "what is the best*
way to process this corpus" more than "what is the underlying theory
behind what I'm wanting to do".
Russ's stuff is great. He refuted that
widespread belief, for one
thing. But Russ isn't trying to teach a programmer how to best use the
regexp engine in sed, grep, egrep, Perl, PCRE, ... whereas Friedl takes
the many pages needed to do this.
:-)
It depends what one wants to learn first.
I'm learning that I'm more of a technician that wants to know how to use
the existing tools to the best of his / their ability. While having
some interest in theory behind things.
As Friedl says in the post Russ linked to:
‘As a user, you don't care if it's regular, nonregular, unregular,
irregular, or incontinent. So long as you know what you can expect
from it (something this chapter will show you), you know all you need
to care about.
Yep. That's the position that I would be in if someone were paying me
to write the REs that I'm writing.
‘For those wishing to learn more about the theory
of regular expressions,
the classic computer-science text is chapter 3 of Aho, Sethi, and
Ullman's Compilers — Principles, Techniques, and Tools (Addison-Wesley,
1986), commonly called “The Dragon Book” due to the cover design.
More specifically, this is the “red dragon”. The “green dragon”
is its predecessor, Aho and Ullman's Principles of Compiler Design.’
This all sounds interesting to me, and like something I might add to my
collection of books. But it also sounds like something that will be an
up hill read and vast learning opportunity.
In addition to the Dragon Book, Hopcroft and
Ullman's ‘Automata Theory,
Languages, and Computation’ goes further into the subject. Chapter two
has DFA, NFA, epsilon transitions, and uses searching text as an
example. Chapter three is regular expressions, four is regular
languages. Pushdown automata is chapter six.
Too many books, not enough time to read. :-)
Yep. Even inventorying and keeping track of the books can be time
consuming. -- Thankfully I took some time to do exactly that and have
access to that information on the super computer in my pocket.
--
Grant. . . .
unix || die