Mastering Regular Expressions (2nd Edition) [Electronic resources] نسخه متنی

4.7 Summary

If you understood everything in this chapter the first time you read it, you probably
didn't need to read it in the first place. It's heady stuff, to say the least. It took
me quite a while to understand it, and then longer still to understand it. I hope this one concise presentation makes it easier for you. I've tried to keep the explanation
simple without falling into the trap of oversimplification (an unfortunately
all-too-common occurrence which hinders true understanding). This chapter has a
lot in it, so I've included a lot of section references in the following summary, for
when you'd like to quickly check back on something.

There are two underlying technologies commonly used to implement a regex
match engine, "regex-directed NFA" (see Section 4.3.1) and "text-directed DFA" (see Section 4.3.2). The
abbreviations are spelled out in Section 4.3.3.

Combine the two technologies with the POSIX standard (see Section 4.6.2), and for practical purposes, there are three types of engines:

Traditional NFA (gas-guzzling, power-on-demand)

POSIX NFA (gas-guzzling, standard-compliant)

DFA (POSIX or not)(electric, steady-as-she-goes)

To get the most out of a utility, you need to understand which type of engine it
uses, and craft your regular expressions appropriately. The most common type is
the Traditional NFA, followed by the DFA. Table 4-1 lists a few common tools and their engine types, and the section "Testing the Engine Type" (see Section 4.1.4)
shows how you can test the type yourself.

One overriding rule regardless of engine type: matches starting sooner take precedence
over matches starting later. This is due to how the engine's "transmission"
tests the regex at each point in the string (see Section 4.2.2).

For the match attempt starting at any given spot:

DFA Text-Directed Engines

Find the longest possible match, period. That's it. End of discussion (see Section 4.6.1). Consistent, very fast (see Section 4.6.3), and boring to talk about.

NFA Regex-Directed Engines

Must "work through" a match. The soul of NFA matching is backtracking (see Section 4.4, Section 4.4.4). The metacharacters control the match: the standard quantifiers (star and friends) are greedy (see Section 4.2.3), while others may be lazy or possessive (see Section 4.5.6). Alternation is ordered (see Section 4.5.9) in a traditional NFA, but greedy with a
POSIX NFA.

POSIX NFA Must find the longest match, period. But, it's not boring, as you must worry about efficiency (the subject of Chapter 6).

Traditional NFA Is the most expressive type of regex engine, since you can use the regex-directed nature of the engine to craft exactly the match you want.

Understanding the concepts and practices covered in this chapter is the foundation
for writing correct and efficient regular expressions, which just happens to be the
subject of the next two chapters.