Comentarios
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
*/
?>
Patrones recursivos
Considere el problema de comparar una cadena entre paréntesis, permitiendo paréntesis anidados ilimitados. Sin el uso de la recursividad, lo mejor que se puede hacer es usar un patrón que compare hasta alguna profundidad fija de anidamiento. No es posible manejar una profundidad de anidamiento arbitraria. Perl 5.6 ha proporcionado una herramienta experimental que permite a las expresiones regulares actuar recursivamente (entre otras cosas). El elemento especial (?R) es proporcionado para el caso específico de la recursividad. Este patrón de PCRE soluciona el problema de los paréntesis (se asume que la opción PCRE_EXTENDED está establecida por lo que los espacios en blanco se ignoran): \( ( (?>[^()]+) | (?R) )* \)
Primero se compara un paréntesis de apertura. Después compara cualquier número de sub-cadenas que pueden ser tanto una secuencia de algo que no sean paréntesis como una comparación recursiva del patrón mismo (esto es, una sub-cadena con los paréntesis correctos). Finalmente hay un paréntesis de cierre.
Este patrón de ejemplo en particular contiene repeticiones anidadas ilimitadas, y así, el uso de un sub-patrón de una sóla aplicación para comparar cadenas que no contengan paréntesis es importante cuando se aplica el patrón a cadenas que no coinciden. Por ejemplo, cuando se aplica a (aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa() produce "no hay conicidencias" rápidamente. Sin embargo, si no se usa un sub-patrón de una sóla aplicación, la comparación se ejecuta realmente durante mucho tiempo ya que hay muchas maneras diferentes de que las repeticiones + y * se puedan repartir el sujeto, y todas tienen que ser comprobadas antes de que se informe del fallo.
El conjunto de valores para cualquier sub-patrón de captura son aquellos del nivel último de la recursión en el cual el valor del sub-patrón es establecido. Si el patrón anterior se compara con (ab(cd)ef) el valor del paréntesis de captura es "ef", el cual es el último valor tomado en el nivel superior. Si se añaden paréntesis adicionales, dando lugar a \( ( ( (?>[^()]+) | (?R) )* ) \) entonces la cadena que capturan es "ab(cd)ef", el contenido de los paréntesis del nivel superior. Si hay más de 15 paréntesis de captura en un patrón, PCRE ha de obtener memoria extra para almacenar la información durante una recursión, lo cual hace usando pcre_malloc, liberándola mediante pcre_free después. Si no se puede obtener memoria, se guarda la información para los primeros 15 paréntesis de captura sólamente, ya que no hay manera de otorgar un error "out-of-memory" desde dentro de una recursión.
Se puede usar también (?1), (?2) y así sucesivamente, para los sub-patrones recursivos. Tamién es posible usar sub-patrones nominados: (?P>nombre) o (?P&nombre).
Si la sintaxis para la referencia de un sub-patrón recursivo (tanto como número o como nombre) se usa fuera de los paréntesis a los que hace referencia, opera como una sub-rutina de un lenguaje de programación. Un ejemplo mostrado anteriormente, tal que el patrón (abraz|apreci)o de un \1ador coincide con "abrazo de un abrazador" y con "aprecio de un apreciador", pero no con "abrazo de un apreciador". Si en su lugar se usa (abraz|apreci)o de un (?1)ador, coincide con "abrazo de un apreciador" así como con las otras dos cadenas. Tales referencias deben, sin embargo, seguir al sub-patrón al que hacen referencia.
La longitud máxima de una cadena objetivo es el número positivo más grande que una variable tipo integer pueda tener. Sin embargo, PCRE usa la recursividad para tratar sub-patrones y repetición indefinida. Esto significa que el espacio de pila disponible puede limitar el tamaño de una cadena objetivo que puede ser procesada por ciertos patrones.
add a note
User Contributed Notes
Patrones recursivos
Onyxagargaryll
03-Mar-2011 04:49
jonah at nucleussystems dot com
21-Dec-2010 06: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
09-Jan-2010 03: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>";
}
}
?>