diff options
Diffstat (limited to 'doc/html/pcrematching.html')
| -rw-r--r-- | doc/html/pcrematching.html | 192 |
1 files changed, 192 insertions, 0 deletions
diff --git a/doc/html/pcrematching.html b/doc/html/pcrematching.html new file mode 100644 index 0000000..eb381b7 --- /dev/null +++ b/doc/html/pcrematching.html @@ -0,0 +1,192 @@ +<html> +<head> +<title>pcrematching specification</title> +</head> +<body bgcolor="#FFFFFF" text="#00005A" link="#0066FF" alink="#3399FF" vlink="#2222BB"> +<h1>pcrematching man page</h1> +<p> +Return to the <a href="index.html">PCRE index page</a>. +</p> +<p> +This page is part of the PCRE HTML documentation. It was generated automatically +from the original man page. If there is any nonsense in it, please consult the +man page, in case the conversion went wrong. +<br> +<ul> +<li><a name="TOC1" href="#SEC1">PCRE MATCHING ALGORITHMS</a> +<li><a name="TOC2" href="#SEC2">REGULAR EXPRESSIONS AS TREES</a> +<li><a name="TOC3" href="#SEC3">THE STANDARD MATCHING ALGORITHM</a> +<li><a name="TOC4" href="#SEC4">THE DFA MATCHING ALGORITHM</a> +<li><a name="TOC5" href="#SEC5">ADVANTAGES OF THE DFA ALGORITHM</a> +<li><a name="TOC6" href="#SEC6">DISADVANTAGES OF THE DFA ALGORITHM</a> +</ul> +<br><a name="SEC1" href="#TOC1">PCRE MATCHING ALGORITHMS</a><br> +<P> +This document describes the two different algorithms that are available in PCRE +for matching a compiled regular expression against a given subject string. The +"standard" algorithm is the one provided by the <b>pcre_exec()</b> function. +This works in the same was as Perl's matching function, and provides a +Perl-compatible matching operation. +</P> +<P> +An alternative algorithm is provided by the <b>pcre_dfa_exec()</b> function; +this operates in a different way, and is not Perl-compatible. It has advantages +and disadvantages compared with the standard algorithm, and these are described +below. +</P> +<P> +When there is only one possible way in which a given subject string can match a +pattern, the two algorithms give the same answer. A difference arises, however, +when there are multiple possibilities. For example, if the pattern +<pre> + ^<.*> +</pre> +is matched against the string +<pre> + <something> <something else> <something further> +</pre> +there are three possible answers. The standard algorithm finds only one of +them, whereas the DFA algorithm finds all three. +</P> +<br><a name="SEC2" href="#TOC1">REGULAR EXPRESSIONS AS TREES</a><br> +<P> +The set of strings that are matched by a regular expression can be represented +as a tree structure. An unlimited repetition in the pattern makes the tree of +infinite size, but it is still a tree. Matching the pattern to a given subject +string (from a given starting point) can be thought of as a search of the tree. +There are two standard ways to search a tree: depth-first and breadth-first, +and these correspond to the two matching algorithms provided by PCRE. +</P> +<br><a name="SEC3" href="#TOC1">THE STANDARD MATCHING ALGORITHM</a><br> +<P> +In the terminology of Jeffrey Friedl's book \fIMastering Regular +Expressions\fP, the standard algorithm is an "NFA algorithm". It conducts a +depth-first search of the pattern tree. That is, it proceeds along a single +path through the tree, checking that the subject matches what is required. When +there is a mismatch, the algorithm tries any alternatives at the current point, +and if they all fail, it backs up to the previous branch point in the tree, and +tries the next alternative branch at that level. This often involves backing up +(moving to the left) in the subject string as well. The order in which +repetition branches are tried is controlled by the greedy or ungreedy nature of +the quantifier. +</P> +<P> +If a leaf node is reached, a matching string has been found, and at that point +the algorithm stops. Thus, if there is more than one possible match, this +algorithm returns the first one that it finds. Whether this is the shortest, +the longest, or some intermediate length depends on the way the greedy and +ungreedy repetition quantifiers are specified in the pattern. +</P> +<P> +Because it ends up with a single path through the tree, it is relatively +straightforward for this algorithm to keep track of the substrings that are +matched by portions of the pattern in parentheses. This provides support for +capturing parentheses and back references. +</P> +<br><a name="SEC4" href="#TOC1">THE DFA MATCHING ALGORITHM</a><br> +<P> +DFA stands for "deterministic finite automaton", but you do not need to +understand the origins of that name. This algorithm conducts a breadth-first +search of the tree. Starting from the first matching point in the subject, it +scans the subject string from left to right, once, character by character, and +as it does this, it remembers all the paths through the tree that represent +valid matches. +</P> +<P> +The scan continues until either the end of the subject is reached, or there are +no more unterminated paths. At this point, terminated paths represent the +different matching possibilities (if there are none, the match has failed). +Thus, if there is more than one possible match, this algorithm finds all of +them, and in particular, it finds the longest. In PCRE, there is an option to +stop the algorithm after the first match (which is necessarily the shortest) +has been found. +</P> +<P> +Note that all the matches that are found start at the same point in the +subject. If the pattern +<pre> + cat(er(pillar)?) +</pre> +is matched against the string "the caterpillar catchment", the result will be +the three strings "cat", "cater", and "caterpillar" that start at the fourth +character of the subject. The algorithm does not automatically move on to find +matches that start at later positions. +</P> +<P> +There are a number of features of PCRE regular expressions that are not +supported by the DFA matching algorithm. They are as follows: +</P> +<P> +1. Because the algorithm finds all possible matches, the greedy or ungreedy +nature of repetition quantifiers is not relevant. Greedy and ungreedy +quantifiers are treated in exactly the same way. +</P> +<P> +2. When dealing with multiple paths through the tree simultaneously, it is not +straightforward to keep track of captured substrings for the different matching +possibilities, and PCRE's implementation of this algorithm does not attempt to +do this. This means that no captured substrings are available. +</P> +<P> +3. Because no substrings are captured, back references within the pattern are +not supported, and cause errors if encountered. +</P> +<P> +4. For the same reason, conditional expressions that use a backreference as the +condition are not supported. +</P> +<P> +5. Callouts are supported, but the value of the <i>capture_top</i> field is +always 1, and the value of the <i>capture_last</i> field is always -1. +</P> +<P> +6. +The \C escape sequence, which (in the standard algorithm) matches a single +byte, even in UTF-8 mode, is not supported because the DFA algorithm moves +through the subject string one character at a time, for all active paths +through the tree. +</P> +<br><a name="SEC5" href="#TOC1">ADVANTAGES OF THE DFA ALGORITHM</a><br> +<P> +Using the DFA matching algorithm provides the following advantages: +</P> +<P> +1. All possible matches (at a single point in the subject) are automatically +found, and in particular, the longest match is found. To find more than one +match using the standard algorithm, you have to do kludgy things with +callouts. +</P> +<P> +2. There is much better support for partial matching. The restrictions on the +content of the pattern that apply when using the standard algorithm for partial +matching do not apply to the DFA algorithm. For non-anchored patterns, the +starting position of a partial match is available. +</P> +<P> +3. Because the DFA algorithm scans the subject string just once, and never +needs to backtrack, it is possible to pass very long subject strings to the +matching function in several pieces, checking for partial matching each time. +</P> +<br><a name="SEC6" href="#TOC1">DISADVANTAGES OF THE DFA ALGORITHM</a><br> +<P> +The DFA algorithm suffers from a number of disadvantages: +</P> +<P> +1. It is substantially slower than the standard algorithm. This is partly +because it has to search for all possible matches, but is also because it is +less susceptible to optimization. +</P> +<P> +2. Capturing parentheses and back references are not supported. +</P> +<P> +3. The "atomic group" feature of PCRE regular expressions is supported, but +does not provide the advantage that it does for the standard algorithm. +</P> +<P> +Last updated: 28 February 2005 +<br> +Copyright © 1997-2005 University of Cambridge. +<p> +Return to the <a href="index.html">PCRE index page</a>. +</p> |