ch06_01.htm

来自「By Tom Christiansen and Nathan Torkingto」· HTM 代码 · 共 1,459 行 · 第 1/3 页

><I
>geod food</I
></CODE
></B
></CODE
>
<CODE
CLASS="userinput"
><B
><CODE
CLASS="replaceable"
><I
>geed food</I
></CODE
></B
></CODE
>
<CODE
CLASS="userinput"
><B
><CODE
CLASS="replaceable"
><I
>geed feed</I
></CODE
></B
></CODE
>
<CODE
CLASS="userinput"
><B
><CODE
CLASS="replaceable"
><I
>ged food</I
></CODE
></B
></CODE
>
<CODE
CLASS="userinput"
><B
><CODE
CLASS="replaceable"
><I
>ged fed</I
></CODE
></B
></CODE
>
<CODE
CLASS="userinput"
><B
><CODE
CLASS="replaceable"
><I
>egood food</I
></CODE
></B
></CODE
></PRE
><P
CLASS="para"
>The answer is the last one because the earliest point at which zero or more occurrences of <CODE
CLASS="literal"
>&quot;o&quot;</CODE
> could be found was right at the beginning of the string. Surprised? Regular expressions can do that to you.</P
><P
CLASS="para"
>Can you guess what adding <CODE
CLASS="literal"
>/g</CODE
><A
CLASS="indexterm"
NAME="ch06-idx-1000007466-0"
></A
> modifier to make the substitution global will do? Think of it this way: that string has many places where zero or more instances of <CODE
CLASS="literal"
>&quot;o&quot;</CODE
> occur &nbsp;-  eight, to be precise. The answer is <CODE
CLASS="literal"
>&quot;egeede</CODE
> <CODE
CLASS="literal"
>efeede&quot;</CODE
>.</P
><P
CLASS="para"
>Here's another example of where greed takes a back seat to eagerness:</P
><PRE
CLASS="programlisting"
>% echo ababacaca | perl -ne 'print &quot;$&amp;\n&quot; if /(a|ba|b)+(a|ac)+/'
<CODE
CLASS="userinput"
><B
><CODE
CLASS="replaceable"
><I
>ababa</I
></CODE
></B
></CODE
></PRE
><P
CLASS="para"
>That's because Perl uses what's called a traditional NFA,[<A
CLASS="footnote"
HREF="#ch06-pgfId-1000000612"
>2</A
>] a <A
CLASS="indexterm"
NAME="ch06-idx-1000007467-0"
></A
><A
CLASS="indexterm"
NAME="ch06-idx-1000007467-1"
></A
>non-deterministic finite automaton. This kind of matching engine is not guaranteed to return the longest <EM
CLASS="emphasis"
>overall</EM
> match, just the longest, leftmost match. You might think of Perl's greed as being left-to-right directed, not globally greedy.</P
><BLOCKQUOTE
CLASS="footnote"
><DIV
CLASS="footnote"
><P
CLASS="para"
><A
CLASS="footnote"
NAME="ch06-pgfId-1000000612"
>[2]</A
> As opposed to a POSIX-style NFA. See <EM
CLASS="emphasis"
>Mastering Regular Expressions</EM
> for the differences.</P
></DIV
></BLOCKQUOTE
><P
CLASS="para"
>But it doesn't have to be that way. Here's an example using <EM
CLASS="emphasis"
>awk</EM
>, a language that Perl borrows a lot from:</P
><PRE
CLASS="programlisting"
>% echo ababacaca | 
    awk 'match($0,/(a|ba|b)+(a|ac)+/) { print substr($0, RSTART, RLENGTH) }'
<CODE
CLASS="userinput"
><B
><CODE
CLASS="replaceable"
><I
>ababacaca</I
></CODE
></B
></CODE
></PRE
><P
CLASS="para"
>Choosing how to implement pattern matching depends mainly on two factors: are the expressions nonregular (do they use backreferences), and what needs to be returned (yes/no, range of whole match, ranges of subexpressions). Tools like <EM
CLASS="emphasis"
>awk</EM
>, <EM
CLASS="emphasis"
>egrep</EM
>, and <EM
CLASS="emphasis"
>lex</EM
> use regular expressions and only need a yes/no answer or the range of the whole match. This is exactly what <A
CLASS="indexterm"
NAME="ch06-idx-1000008226-0"
></A
><A
CLASS="indexterm"
NAME="ch06-idx-1000008226-1"
></A
>DFAs can support, and because DFAs are faster and simpler, these tools have traditionally used DFA implementations. Pattern matching within programs and libraries, such as <EM
CLASS="emphasis"
>ed</EM
>, <EM
CLASS="emphasis"
>regex</EM
>, and <EM
CLASS="emphasis"
>perl</EM
>, is another kettle of fish; typically, we need to support nonregular expressions and we need to know what parts of the string were matched by various parts of the pattern. This is a much harder problem with potentially exponential run times. The natural algorithm for this problem is an NFA, and therein lies both a problem and an opportunity. The problem is that NFAs are slow. The opportunity is that significant performance gains can be made by rewriting the patterns to exploit how the particular NFA implementation runs. This is a major part of Jeffrey Friedl's book, <EM
CLASS="emphasis"
>Mastering Regular Expressions</EM
>.<A
CLASS="indexterm"
NAME="ch06-idx-1000007479-0"
></A
><A
CLASS="indexterm"
NAME="ch06-idx-1000007479-1"
></A
><A
CLASS="indexterm"
NAME="ch06-idx-1000007479-2"
></A
><A
CLASS="indexterm"
NAME="ch06-idx-1000007479-3"
></A
><A
CLASS="indexterm"
NAME="ch06-idx-1000007479-4"
></A
></P
><P
CLASS="para"
><A
CLASS="indexterm"
NAME="ch06-idx-1000007477-0"
></A
><A
CLASS="indexterm"
NAME="ch06-idx-1000007477-1"
></A
>The last and most powerful of the three tricky bits in pattern matching is backtracking. For a pattern to match, the entire regular expression must match, not just part of it. So if the beginning of a pattern containing a quantifier succeeds in a way that causes later parts in the pattern to fail, the matching engine backs up and tries to find another match for the beginning part &nbsp;-  that's why it's called backtracking. Essentially, it means that the engine is going to try different possibilities, systematically investigating alternate matches until it finds one that works. In some pattern matching implementations, you keep backtracking in case other submatches make the overall match longer. Perl's matcher doesn't do that; as soon as one possibility works, it uses that &nbsp;-  until and unless something later on in the pattern fails, forcing a backtrack to retry another possible way of matching. This is discussed in <A
CLASS="xref"
HREF="ch06_17.htm"
TITLE="Detecting Duplicate Words"
>Recipe 6.16</A
>.</P
></DIV
><DIV
CLASS="sect2"
><H3
CLASS="sect2"
><A
CLASS="title"
NAME="ch06-chap06_pattern_matching_0"
>Pattern-Matching Modifiers</A
></H3
><P
CLASS="para"
><A
CLASS="indexterm"
NAME="ch06-idx-1000010775-0"
></A
>Pattern-matching modifiers are a lot easier to list and learn than the different metacharacters. Here's a brief summary of them:</P
><TABLE
CLASS="informaltable"
BORDER="1"
CELLPADDING="3"
><TBODY
CLASS="tbody"
><TR
CLASS="row"
VALIGN="TOP"
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
><CODE
CLASS="literal"
>/i</CODE
></P
></TD
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
>Ignore alphabetic case (locale-aware)</P
></TD
></TR
><TR
CLASS="row"
VALIGN="TOP"
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
><CODE
CLASS="literal"
>/x</CODE
></P
></TD
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
>Ignore most whitespace in pattern and permit comments</P
></TD
></TR
><TR
CLASS="row"
VALIGN="TOP"
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
><CODE
CLASS="literal"
>/g</CODE
></P
></TD
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
>Global &nbsp;-  match/substitute as often as possible</P
></TD
></TR
><TR
CLASS="row"
VALIGN="TOP"
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
><CODE
CLASS="literal"
>/gc</CODE
></P
></TD
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
>Don't reset search position on failed match</P
></TD
></TR
><TR
CLASS="row"
VALIGN="TOP"
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
><CODE
CLASS="literal"
>/s</CODE
></P
></TD
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
>Let <CODE
CLASS="literal"
>. </CODE
>match newline; also, ignore deprecated <CODE
CLASS="literal"
>$*</CODE
></P
></TD
></TR
><TR
CLASS="row"
VALIGN="TOP"
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
><CODE
CLASS="literal"
>/m</CODE
></P
></TD
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
>Let <CODE
CLASS="literal"
>^ </CODE
>and <CODE
CLASS="literal"
>$</CODE
> match next to embedded <CODE
CLASS="literal"
>\n</CODE
></P
></TD
></TR
><TR
CLASS="row"
VALIGN="TOP"
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
><CODE
CLASS="literal"
>/o</CODE
></P
></TD
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
>Compile pattern once only</P
></TD
></TR
><TR
CLASS="row"
VALIGN="TOP"
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
><CODE
CLASS="literal"
>/e</CODE
></P
></TD
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
>Righthand side of a <CODE
CLASS="literal"
>s/// </CODE
>is code to <CODE
CLASS="literal"
>eval</CODE
></P
></TD
></TR
><TR
CLASS="row"
VALIGN="TOP"
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
><CODE
CLASS="literal"
>/ee</CODE
></P
></TD
><TD
CLASS="entry"
ROWSPAN="1"
COLSPAN="1"
><P
CLASS="para"
>Righthand side of a <CODE
CLASS="literal"
>s/// </CODE
>is a string to <CODE
CLASS="literal"
>eval</CODE
>, then run as code, and its return value <CODE
CLASS="literal"
>eval</CODE
>'led again.</P
></TD
></TR
></TBODY