Parent Directory | Revision Log

Revision **461** -
(**hide annotations**)
(**download**)

*Mon Oct 5 10:59:35 2009 UTC*
(4 years, 11 months ago)
by *ph10*

File size: 8334 byte(s)

File size: 8334 byte(s)

Tidy up, remove trailing spaces, etc. for 8.00-RC1.

1 | nigel | 79 | .TH PCREMATCHING 3 |

2 | nigel | 77 | .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 | nigel | 93 | them, whereas the alternative algorithm finds all three. |

30 | nigel | 77 | . |

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 | nigel | 91 | There are two ways to search a tree: depth-first and breadth-first, and these |

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

40 | nigel | 77 | . |

41 | .SH "THE STANDARD MATCHING ALGORITHM" | ||

42 | .rs | ||

43 | .sp | ||

44 | ph10 | 148 | In the terminology of Jeffrey Friedl's book "Mastering Regular |

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

46 | nigel | 77 | 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 | nigel | 93 | .SH "THE ALTERNATIVE MATCHING ALGORITHM" |

67 | nigel | 77 | .rs |

68 | .sp | ||

69 | nigel | 93 | This algorithm conducts a breadth-first search of the tree. Starting from the |

70 | first matching point in the subject, it scans the subject string from left to | ||

71 | right, once, character by character, and as it does this, it remembers all the | ||

72 | paths through the tree that represent valid matches. In Friedl's terminology, | ||

73 | this is a kind of "DFA algorithm", though it is not implemented as a | ||

74 | traditional finite state machine (it keeps multiple states active | ||

75 | simultaneously). | ||

76 | nigel | 77 | .P |

77 | ph10 | 461 | Although the general principle of this matching algorithm is that it scans the |

78 | subject string only once, without backtracking, there is one exception: when a | ||

79 | lookaround assertion is encountered, the characters following or preceding the | ||

80 | ph10 | 456 | current point have to be independently inspected. |

81 | .P | ||

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

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

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

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

86 | ph10 | 456 | them, and in particular, it finds the longest. There is an option to stop the |

87 | algorithm after the first match (which is necessarily the shortest) is found. | ||

88 | nigel | 77 | .P |

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

90 | subject. If the pattern | ||

91 | .sp | ||

92 | cat(er(pillar)?) | ||

93 | .sp | ||

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

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

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

97 | matches that start at later positions. | ||

98 | .P | ||

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

100 | nigel | 93 | supported by the alternative matching algorithm. They are as follows: |

101 | nigel | 77 | .P |

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

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

104 | nigel | 93 | quantifiers are treated in exactly the same way. However, possessive |

105 | quantifiers can make a difference when what follows could also match what is | ||

106 | quantified, for example in a pattern like this: | ||

107 | .sp | ||

108 | ^a++\ew! | ||

109 | .sp | ||

110 | This pattern matches "aaab!" but not "aaa!", which would be matched by a | ||

111 | non-possessive quantifier. Similarly, if an atomic group is present, it is | ||

112 | matched as if it were a standalone pattern at the current point, and the | ||

113 | longest match is then "locked in" for the rest of the overall pattern. | ||

114 | nigel | 77 | .P |

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

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

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

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

119 | .P | ||

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

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

122 | .P | ||

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

124 | nigel | 93 | condition or test for a specific group recursion are not supported. |

125 | nigel | 77 | .P |

126 | ph10 | 168 | 5. Because many paths through the tree may be active, the \eK escape sequence, |

127 | which resets the start of the match when encountered (but may be on some paths | ||

128 | and not on others), is not supported. It causes an error if encountered. | ||

129 | .P | ||

130 | 6. Callouts are supported, but the value of the \fIcapture_top\fP field is | ||

131 | nigel | 77 | always 1, and the value of the \fIcapture_last\fP field is always -1. |

132 | .P | ||

133 | ph10 | 210 | 7. The \eC escape sequence, which (in the standard algorithm) matches a single |

134 | nigel | 93 | byte, even in UTF-8 mode, is not supported because the alternative algorithm |

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

136 | nigel | 77 | through the tree. |

137 | ph10 | 210 | .P |

138 | ph10 | 341 | 8. Except for (*FAIL), the backtracking control verbs such as (*PRUNE) are not |

139 | supported. (*FAIL) is supported, and behaves like a failing negative assertion. | ||

140 | nigel | 77 | . |

141 | nigel | 93 | .SH "ADVANTAGES OF THE ALTERNATIVE ALGORITHM" |

142 | nigel | 77 | .rs |

143 | .sp | ||

144 | nigel | 93 | Using the alternative matching algorithm provides the following advantages: |

145 | nigel | 77 | .P |

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

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

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

149 | callouts. | ||

150 | .P | ||

151 | ph10 | 426 | 2. Because the alternative algorithm scans the subject string just once, and |

152 | nigel | 93 | never needs to backtrack, it is possible to pass very long subject strings to |

153 | the matching function in several pieces, checking for partial matching each | ||

154 | ph10 | 456 | time. The |

155 | ph10 | 461 | .\" HREF |

156 | ph10 | 456 | \fBpcrepartial\fP |

157 | ph10 | 461 | .\" |

158 | ph10 | 456 | documentation gives details of partial matching. |

159 | nigel | 77 | . |

160 | ph10 | 456 | . |

161 | nigel | 93 | .SH "DISADVANTAGES OF THE ALTERNATIVE ALGORITHM" |

162 | nigel | 77 | .rs |

163 | .sp | ||

164 | nigel | 93 | The alternative algorithm suffers from a number of disadvantages: |

165 | nigel | 77 | .P |

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

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

168 | less susceptible to optimization. | ||

169 | .P | ||

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

171 | .P | ||

172 | nigel | 93 | 3. Although atomic groups are supported, their use does not provide the |

173 | performance advantage that it does for the standard algorithm. | ||

174 | ph10 | 99 | . |

175 | . | ||

176 | .SH AUTHOR | ||

177 | .rs | ||

178 | .sp | ||

179 | .nf | ||

180 | Philip Hazel | ||

181 | University Computing Service | ||

182 | Cambridge CB2 3QH, England. | ||

183 | .fi | ||

184 | . | ||

185 | . | ||

186 | .SH REVISION | ||

187 | .rs | ||

188 | .sp | ||

189 | .nf | ||

190 | ph10 | 456 | Last updated: 29 September 2009 |

191 | ph10 | 426 | Copyright (c) 1997-2009 University of Cambridge. |

192 | ph10 | 99 | .fi |

Name | Value |
---|---|

svn:eol-style |
native |

svn:keywords |
"Author Date Id Revision Url" |

webmaster@exim.org | ViewVC Help |

Powered by ViewVC 1.1.12 |