Parent Directory | Revision Log

Revision **79** -
(**show annotations**)
(**download**)

*Sat Feb 24 21:40:52 2007 UTC*
(7 years, 5 months ago)
by *nigel*

File size: 7133 byte(s)

File size: 7133 byte(s)

Load pcre-6.1 into code/trunk.

1 | .TH PCREMATCHING 3 |

2 | .SH NAME |

3 | PCRE - Perl-compatible regular expressions |

4 | .SH "PCRE MATCHING ALGORITHMS" |

5 | .rs |

6 | .sp |

7 | This document describes the two different algorithms that are available in PCRE |

8 | for matching a compiled regular expression against a given subject string. The |

9 | "standard" algorithm is the one provided by the \fBpcre_exec()\fP function. |

10 | This works in the same was as Perl's matching function, and provides a |

11 | Perl-compatible matching operation. |

12 | .P |

13 | An alternative algorithm is provided by the \fBpcre_dfa_exec()\fP function; |

14 | this operates in a different way, and is not Perl-compatible. It has advantages |

15 | and disadvantages compared with the standard algorithm, and these are described |

16 | below. |

17 | .P |

18 | When there is only one possible way in which a given subject string can match a |

19 | pattern, the two algorithms give the same answer. A difference arises, however, |

20 | when there are multiple possibilities. For example, if the pattern |

21 | .sp |

22 | ^<.*> |

23 | .sp |

24 | is matched against the string |

25 | .sp |

26 | <something> <something else> <something further> |

27 | .sp |

28 | there are three possible answers. The standard algorithm finds only one of |

29 | them, whereas the DFA algorithm finds all three. |

30 | . |

31 | .SH "REGULAR EXPRESSIONS AS TREES" |

32 | .rs |

33 | .sp |

34 | The set of strings that are matched by a regular expression can be represented |

35 | as a tree structure. An unlimited repetition in the pattern makes the tree of |

36 | infinite size, but it is still a tree. Matching the pattern to a given subject |

37 | string (from a given starting point) can be thought of as a search of the tree. |

38 | There are two standard ways to search a tree: depth-first and breadth-first, |

39 | and these correspond to the two matching algorithms provided by PCRE. |

40 | . |

41 | .SH "THE STANDARD MATCHING ALGORITHM" |

42 | .rs |

43 | .sp |

44 | In the terminology of Jeffrey Friedl's book \fIMastering Regular |

45 | Expressions\fP, the standard algorithm is an "NFA algorithm". It conducts a |

46 | depth-first search of the pattern tree. That is, it proceeds along a single |

47 | path through the tree, checking that the subject matches what is required. When |

48 | there is a mismatch, the algorithm tries any alternatives at the current point, |

49 | and if they all fail, it backs up to the previous branch point in the tree, and |

50 | tries the next alternative branch at that level. This often involves backing up |

51 | (moving to the left) in the subject string as well. The order in which |

52 | repetition branches are tried is controlled by the greedy or ungreedy nature of |

53 | the quantifier. |

54 | .P |

55 | If a leaf node is reached, a matching string has been found, and at that point |

56 | the algorithm stops. Thus, if there is more than one possible match, this |

57 | algorithm returns the first one that it finds. Whether this is the shortest, |

58 | the longest, or some intermediate length depends on the way the greedy and |

59 | ungreedy repetition quantifiers are specified in the pattern. |

60 | .P |

61 | Because it ends up with a single path through the tree, it is relatively |

62 | straightforward for this algorithm to keep track of the substrings that are |

63 | matched by portions of the pattern in parentheses. This provides support for |

64 | capturing parentheses and back references. |

65 | . |

66 | .SH "THE DFA MATCHING ALGORITHM" |

67 | .rs |

68 | .sp |

69 | DFA stands for "deterministic finite automaton", but you do not need to |

70 | understand the origins of that name. This algorithm conducts a breadth-first |

71 | search of the tree. Starting from the first matching point in the subject, it |

72 | scans the subject string from left to right, once, character by character, and |

73 | as it does this, it remembers all the paths through the tree that represent |

74 | valid matches. |

75 | .P |

76 | The scan continues until either the end of the subject is reached, or there are |

77 | no more unterminated paths. At this point, terminated paths represent the |

78 | different matching possibilities (if there are none, the match has failed). |

79 | Thus, if there is more than one possible match, this algorithm finds all of |

80 | them, and in particular, it finds the longest. In PCRE, there is an option to |

81 | stop the algorithm after the first match (which is necessarily the shortest) |

82 | has been found. |

83 | .P |

84 | Note that all the matches that are found start at the same point in the |

85 | subject. If the pattern |

86 | .sp |

87 | cat(er(pillar)?) |

88 | .sp |

89 | is matched against the string "the caterpillar catchment", the result will be |

90 | the three strings "cat", "cater", and "caterpillar" that start at the fourth |

91 | character of the subject. The algorithm does not automatically move on to find |

92 | matches that start at later positions. |

93 | .P |

94 | There are a number of features of PCRE regular expressions that are not |

95 | supported by the DFA matching algorithm. They are as follows: |

96 | .P |

97 | 1. Because the algorithm finds all possible matches, the greedy or ungreedy |

98 | nature of repetition quantifiers is not relevant. Greedy and ungreedy |

99 | quantifiers are treated in exactly the same way. |

100 | .P |

101 | 2. When dealing with multiple paths through the tree simultaneously, it is not |

102 | straightforward to keep track of captured substrings for the different matching |

103 | possibilities, and PCRE's implementation of this algorithm does not attempt to |

104 | do this. This means that no captured substrings are available. |

105 | .P |

106 | 3. Because no substrings are captured, back references within the pattern are |

107 | not supported, and cause errors if encountered. |

108 | .P |

109 | 4. For the same reason, conditional expressions that use a backreference as the |

110 | condition are not supported. |

111 | .P |

112 | 5. Callouts are supported, but the value of the \fIcapture_top\fP field is |

113 | always 1, and the value of the \fIcapture_last\fP field is always -1. |

114 | .P |

115 | 6. |

116 | The \eC escape sequence, which (in the standard algorithm) matches a single |

117 | byte, even in UTF-8 mode, is not supported because the DFA algorithm moves |

118 | through the subject string one character at a time, for all active paths |

119 | through the tree. |

120 | . |

121 | .SH "ADVANTAGES OF THE DFA ALGORITHM" |

122 | .rs |

123 | .sp |

124 | Using the DFA matching algorithm provides the following advantages: |

125 | .P |

126 | 1. All possible matches (at a single point in the subject) are automatically |

127 | found, and in particular, the longest match is found. To find more than one |

128 | match using the standard algorithm, you have to do kludgy things with |

129 | callouts. |

130 | .P |

131 | 2. There is much better support for partial matching. The restrictions on the |

132 | content of the pattern that apply when using the standard algorithm for partial |

133 | matching do not apply to the DFA algorithm. For non-anchored patterns, the |

134 | starting position of a partial match is available. |

135 | .P |

136 | 3. Because the DFA algorithm scans the subject string just once, and never |

137 | needs to backtrack, it is possible to pass very long subject strings to the |

138 | matching function in several pieces, checking for partial matching each time. |

139 | . |

140 | .SH "DISADVANTAGES OF THE DFA ALGORITHM" |

141 | .rs |

142 | .sp |

143 | The DFA algorithm suffers from a number of disadvantages: |

144 | .P |

145 | 1. It is substantially slower than the standard algorithm. This is partly |

146 | because it has to search for all possible matches, but is also because it is |

147 | less susceptible to optimization. |

148 | .P |

149 | 2. Capturing parentheses and back references are not supported. |

150 | .P |

151 | 3. The "atomic group" feature of PCRE regular expressions is supported, but |

152 | does not provide the advantage that it does for the standard algorithm. |

153 | .P |

154 | .in 0 |

155 | Last updated: 28 February 2005 |

156 | .br |

157 | Copyright (c) 1997-2005 University of Cambridge. |

webmaster@exim.org | ViewVC Help |

Powered by ViewVC 1.1.12 |