コメント
Here's an approach to create a multidimensional array according to a string's delimiters, i.e. we want to analyze...
"some text (aaa(b(c1)(c2)d)e)(test) more text"
... as multidimensional layers.
<?php
$string = "some text (aaa(b(c1)(c2)d)e)(test) more text";
/*
* Analyses the string multidimensionally by its opening and closing delimiters
*/
function recursiveSplit($string, $layer) {
preg_match_all("/\((([^()]*|(?R))*)\)/",$string,$matches);
// iterate thru matches and continue recursive split
if (count($matches) > 1) {
for ($i = 0; $i < count($matches[1]); $i++) {
if (is_string($matches[1][$i])) {
if (strlen($matches[1][$i]) > 0) {
echo "<pre>Layer ".$layer.": ".$matches[1][$i]."</pre><br />";
recursiveSplit($matches[1][$i], $layer + 1);
}
}
}
}
}
recursiveSplit($string, 0);
/*
Output:
Layer 0: aaa(b(c1)(c2)d)e
Layer 1: b(c1)(c2)d
Layer 2: c1
Layer 2: c2
Layer 0: test
*/
?>
再帰的パターン
どうすればカッコに括られた文字列とマッチできるか、という問題を 考えて見ましょう。このとき、カッコは何回でもネストできるとします。 再帰が使えないとすると、パターンを用いて、せいぜい、ある一定の深さの ネストまでしかマッチできないでしょう。任意の深さのネストを 処理することは不可能です。Perl 5.6 では、正規表現において再帰を行う 実験的な機能が導入されています。 PCRE では、再帰という特殊なケースに対して専用のシーケンス (?R) が導入されました。上記のカッコ問題を解決する PCRE のコードは 以下のようになります（PCRE_EXTENDED オプションが設定され空白文字が無視されると仮定）。
\( ( (?>[^()]+) | (?R) )* \)
まず、このパターンは開きカッコにマッチします。続いて、 カッコ以外の文字が並んでいるか、または、再帰的にパターン自体に マッチする（すなわち正しくカッコで括られている）かする部分文字列に 何回でもマッチします。最後に閉じカッコにマッチします。
このパターン例には、ネストした無制限の繰り返しが含まれているため、 マッチが成功し得ない文字列に対してこのパターンが適用される場合も考えて、 カッコ以外の文字列にマッチングさせる部分に再試行無しのサブパターンを 使うことが重要です。例えば、このパターンを
(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa()
という文字列に適用すると、「マッチしない」という判定が速やかに
行われます。しかし、再試行無しのサブパターンを使わないと、
対象文字列を分割し得る + と * の繰り返し数の種類が非常に多く、
そのすべてが確認された後にマッチの失敗が報告されるため、
マッチングに非常に時間がかかります。
キャプチャ用サブパターンにセットされる値は、そのサブパターンに 値がセットされ得る最も外側で最も後の再帰レベルからのものになります。 上記のパターンを
(ab(cd)ef)
にマッチングさせると、キャプチャされる値は "ef" であり、
最上位レベルの最後の値です
\( ( ( (?>[^()]+) | (?R) )* ) \)
次のようにカッコを追加すると、キャプチャされる文字列は、"ab(cd)ef"
となり、最上位レベルのカッコの中身となります。一つのパターン中に
15 以上のキャプチャ用サブパターンを用いると、PCRE は
再帰を行っている間のデータ保存用に追加の記憶領域を確保する必要が
あります。記憶領域が確保できない場合、メモリ不足エラーを再帰の内側から
出力する手段がないため、最初の 15 個のキャプチャ用サブパターンに
ついてのみデータが保存されます。
(?1), (?2) といった記法が 再帰的サブパターンとして使用可能です。 (?P<name>foo) あるいは (?P&name) といった名前付きのサブパターンも使用可能です。
この再帰的サブパターンの記法は（数字によるものも名前によるものの双方とも） 参照するカッコの外で使用でき、プログラム言語のサブルーチンの様に処理されます。 前に示した例で、パターン (sens|respons)e and \1ibility は "sense and sensibility" および "response and responsibility" にはマッチしますが "sense and responsibility" にはマッチしませんでした。 一方、パターン (sens|respons)e and (?1)ibility は、 上記 2 つに加え "sense and responsibility" にもマッチします。 ただし、参照先のサブパターンの後に記述する必要があります。
対象文字列の最大の長さは、integer 型の最大の値となります。 しかし、PCRE は再帰を使用してサブパターンの処理や繰り返し処理を行います。 つまり、そのパターンで処理する対象文字列の長さによって、 使用可能なスタック空間の大きさが制限されるということです。
add a note
User Contributed Notes
再帰的パターン
Onyxagargaryll
03-Mar-2011 01:49
jonah at nucleussystems dot com
22-Dec-2010 03:18
An unexpected behavior came up that introduced a very hard-to-track bug in some code I was working on. It has to do with the preg_match_all PREG_OFFSET_CAPTURE flag. When you capture the offset of a sub-match, it's offset is given _relative_ to it's parent. For example, if you extract the value between < and > recursively in this string:
<this is a <string>>
You will get an array that looks like this:
Array
(
[0] => Array
(
[0] => Array
(
[0] => <this is a <string>>
[1] => 0
)
[1] => Array
(
[0] => this is a <string>
[1] => 1
)
)
[1] => Array
(
[0] => Array
(
[0] => <string>
[1] => 0
)
[1] => Array
(
[0] => string
[1] => 1
)
)
)
Notice that the offset in the last index is one, not the twelve we expected. The best way to solve this problem is to run over the results with a recursive function, adding the parent's offset.
emanueledelgrande at email dot it
10-Jan-2010 12:47
The recursion in regular expressions is the only way to allow the parsing of HTML code with nested tags of indefinite depth.
It seems it's not yet a spreaded practice; not so much contents are available on the web regarding regexp recursion, and until now no user contribute notes have been published on this manual page.
I made several tests with complex patterns to get tags with specific attributes or namespaces, studying the recursion of a subpattern only instead of the full pattern.
Here's an example that may power a fast LL parser with recursive descent (http://en.wikipedia.org/wiki/Recursive_descent_parser):
$pattern = "/<([\w]+)([^>]*?) (([\s]*\/>)| (>((([^<]*?|<\!\-\-.*?\-\->)| (?R))*)<\/\\1[\s]*>))/xsm";
The performances of a preg_match or preg_match_all function call over an avarage (x)HTML document are quite fast and may drive you to chose this way instead of classic DOM object methods, which have a lot of limits and are usually poor in performance with their workarounds, too.
I post a sample application in a brief function (easy to be turned into OOP), which returns an array of objects:
<?php
// test function:
function parse($html) {
// I have split the pattern in two lines not to have long lines alerts by the PHP.net form:
$pattern = "/<([\w]+)([^>]*?)(([\s]*\/>)|".
"(>((([^<]*?|<\!\-\-.*?\-\->)|(?R))*)<\/\\1[\s]*>))/sm";
preg_match_all($pattern, $html, $matches, PREG_OFFSET_CAPTURE);
$elements = array();
foreach ($matches[0] as $key => $match) {
$elements[] = (object)array(
'node' => $match[0],
'offset' => $match[1],
'tagname' => $matches[1][$key][0],
'attributes' => isset($matches[2][$key][0]) ? $matches[2][$key][0] : '',
'omittag' => ($matches[4][$key][1] > -1), // boolean
'inner_html' => isset($matches[6][$key][0]) ? $matches[6][$key][0] : ''
);
}
return $elements;
}
// random html nodes as example:
$html = <<<EOD
<div id="airport">
<div geo:position="1.234324,3.455546" class="index">
<!-- comment test:
<div class="index_top" />
-->
<div class="element decorator">
<ul class="lister">
<li onclick="javascript:item.showAttribute('desc');">
<h3 class="outline">
<a href="http://php.net/manual/en/regexp.reference.recursive.php" onclick="openPopup()">Link</a>
</h3>
<div class="description">Sample description</div>
</li>
</ul>
</div>
<div class="clean-line"></div>
</div>
</div>
<div id="omittag_test" rel="rootChild" />
EOD;
// application:
$elements = parse($html);
if (count($elements) > 0) {
echo "Elements found: <b>".count($elements)."</b><br />";
foreach ($elements as $element) {
echo "<p>Tpl node: <pre>".htmlentities($element->node)."</pre>
Tagname: <tt>".$element->tagname."</tt><br />
Attributes: <tt>".$element->attributes."</tt><br />
Omittag: <tt>".($element->omittag ? 'true' : 'false')."</tt><br />
Inner HTML: <pre>".htmlentities($element->inner_html)."</pre></p>";
}
}
?>