0

I want to parse something like this:

Hi [{tagname:content}] [{tag1:xnkudfdhkfujhkdjki diidfo now nested tag
[{tag2: more data here}] kj udf}]

I am using this PCRE regex to get all the data between \[{(.*?)}\] and it works, but not for nested tags. I am not a PCRE expert.

1
  • This needs recursive feature of the regex. Would you please post the expected result?
    – nhahtdh
    Commented Jul 1, 2012 at 11:41

4 Answers 4

4

PCRE, like Perl can match nested structures to any arbitrary depth. Here is a tested script:

Regex to match nested brackets

<?php // test.php Rev:20120701_0800
$re_nested_double_bracket ='% # Rev:20120701_0800
# Match [{...[{...}]...}] structure with arbitrary nesting.
\[\{                      # Opening literal double bracket.
(                         # $1: Contents of double brackets.
  (?:                     # Group for contents alternatives.
    [^\[\}]++             # Either one or more non-brackets,
  | (?R)                  # or a nested bracket pair,
  | \[                    # or the start of opening bracket
    (?!\{)                # (if not a complete open bracket),
  | \}                    # or the start of closing bracket
    (?!\])                # (if not a complete close bracket).
  )*                      # Zero or more contents alternatives.
)                         # End $1: Contents of double brackets.
\}\]                      # Closing literal double bracket.
%x';

$input = file_get_contents('testdata.txt');
$count = preg_match_all($re_nested_double_bracket, $input, $matches);
printf("There were %d matches found.\n", $count);
for ($i = 0; $i < $count; ++$i) {
    printf("  Match[%d]: %s\n", $i + 1,  $matches[0][$i]);
}
?>

When run against the test data in the original post, here is what the regex matches:

Example Output:

There were 2 matches found.
Match[1]: [{tagname:content}]
Match[2]: [{tag1:xnkudfdhkfujhkdjki diidfo now nested tag
[{tag2: more data here}] kj udf}]

Note that this regex matches the outermost set of possibly nested brackets and captures into group $1 the contents between the brackets. If you wish to parse out any nested brackets, you'll need to re-run the regex on the contents of the outermost brackets recursively until there are no more matches.

Those who claim that modern regex engines (i.e. Perl, PCRE/PHP, .NET) cannot parse nested structures are simply wrong. Regular expressions have not been "REGULAR" for a long, long time...

Edit: 2012-07-01 09:00 Note that this solution matches nested brackets to any "arbitrary depth", but is always limited by system memory, executable stack size and the PHP pcre.backtrack_limit, pcre.recursion_limit and memory_limit configuration variables. Note that it is certainly possible for this regex solution to fail if the subject string is too large and/or the nesting too deep for a given host system. It is even possible for the PHP/PCRE library to cause the running executable to generate a stack overflow, segmentation-fault and program crash! See my answer to a related question for an in-depth discussion on how and why this can occur (and how to avoid it and gracefully handle errors of this sort): RegExp in preg_match function returning browser error and PHP regex: is there anything wrong with this code?.

5
  • No modern regex engine can create a parse tree of arbitrary depth. Commented Jul 1, 2012 at 14:18
  • @Walter Tross - Maybe so... yet the above regex solution works! Commented Jul 1, 2012 at 14:37
  • It depends on what the OP needs. If he needs a parse tree, your solution does not provide one yet. Commented Jul 1, 2012 at 15:10
  • Ok.. but this is fine because i don't need to parse long files.... i just need to parse some html file which will contains fews tags like this... they are also made by me... anyway ridgerunner thanks.. thanks.... Commented Jul 1, 2012 at 18:21
  • I see by your edit that you misunderstood my remark. What I said is that a regex engine cannot create a parse tree of arbitrary depth (this is just to rule out fixed-max-depth cases), not that it cannot recognize nested structures (parse is not the right word here, since it cannot split them into all their parts at once). Commented Jul 1, 2012 at 22:38
3

This is a common problem in REGEX. As buckley says, they weren't designed for this. Nonetheless the question arises a lot.

The fundamental problem is there is no way for the REGEX to know that the closing brackets of a nested tag are not, in fact, the closing brackets of the outer tag.

I decided to do some vandalism and came up with this horror. The concept is to first pull out the tags that do not contain other tags. It then works outwardly until it has all tags.

$str = "Hi [{tagname:content}] [{tag1:xnkudfdhkfujhkdjki diidfo now nested tag [{tag2: more data here}] kj udf}]";
$matches = array();
function replace_cb($this_match) {
    global $matches;
    $this_match = $this_match[0];
    foreach($matches as $index => $match) $this_match = str_replace('**'.($index + 1).'**', $match, $this_match);
    array_push($matches, $this_match);
    return '**'.count($matches).'**';
}
while(preg_match('/\[\{[^\[]*?\}\]/', $str)) $str = preg_replace_callback('/\[\{[^\[]*?\}\]/', 'replace_cb', $str);
print_r($matches);

Outputs:

Array
(
    [0] => [{tagname:content}]
    [1] => [{tag2: more data here}]
    [2] => [{tag1:xnkudfdhkfujhkdjki diidfo now nested tag [{tag2: more data here}] kj udf}]
)

...hence you end up with all three tags, separated.

One weakness is it currently decides a tag contains nested tags if it contains a [. This should be [{ together, but that is tough because you can't negate sub-strings in REGEX, only characters or ranges of characters.

So, so horrible. But it works :)

0
2

There is no general solution when using a regex to allow for unlimited nesting. They were not made for that.

The following matches a comment delimited by [{ and }] allowing one level of nested comments inside. The negative lookahead is used instead of .*? to prevent catastrophic backtracking if the subject string contains unbalanced [{ characters.

\[{(?:(?!}]|\[{).)*+(?:\[{(?:(?!}]|\[{).)*+}](?:(?!}]|\[{).)*+)*+.*?}]
2
  • i am getting this error with php Warning: preg_match_all(): Unknown modifier '\' in C:\wamp\www\project1\~test.php on line 28 Call Stack: 0.0008 322672 1. {main}() C:\wamp\www\project1\~test.php:0 0.0008 323176 2. preg_match_all() C:\wamp\www\project1\~test.php:28 Commented Jul 1, 2012 at 11:52
  • but it still working in regexBuddy .... i am using i and s as modifiers $p=preg_match_all('|\[{(?:(?!}]|\[{).)*+(?:\[{(?:(?!}]|\[{).)*+}](?:(?!}]|\[{).)*+)*+.*?}]|is',$m,$mat,PREG_OFFSET_CAPTURE ); Commented Jul 1, 2012 at 11:54
2

Regular expressions are not parsers.

For a lightweight solution I suggest you use the JSON parser, e.g., like this:

$tree = json_decode('["root","'.
                    preg_replace('/\[\{(\w+):/',
                                 '",["\1","',
                                 str_replace(array('\\',   "\n", '"',  '}]'),
                                             array('\\\\', '\n', '\"', '"],"'),
                                             $str).
                    '"]'));

For this input (your example):

$str = 'Hi [{tagname:content}] [{tag1:xnkudfdhkfujhkdjki diidfo now nested tag
[{tag2: more data here}] kj udf}]';

you get this output:

$tree = array(
   0 => "root",
   1 => "Hi ",
   2 => array(
      0 => "tagname",
      1 => "content"
   ),
   3 => " ",
   4 => array(
      0 => "tag1",
      1 => "xnkudfdhkfujhkdjki diidfo now nested tag\n",
      2 => array(
         0 => "tag2",
         1 => " more data here"
      ),
      3 => " kj udf"
   ),
   5 => ""
);

The tag name is element 0 of each subtree (I added an arbitrary "root" tag). I assumed tag names to be a simple \w+. That should be changed to reflect allowed tag names. As you see there may be extra empty strings in the parse tree, but you can easily get rid of them.

I know, your question was about PCREs, but it was a bit like asking for the right hammer to turn a screw.

BTW, parsers built on recursive regex engines have one theoretical disadvantage that can become quite real: since they must rescan every input element as many times as its depth in the tree, their worst case time complexity, assuming no backtracking, is O(n2).

2
  • good solution but sounds like crack... anyway thanks walter.. i am beginner and i learn from you that we can do anything with little help of mind and tricks...... thanks Commented Jul 1, 2012 at 18:24
  • @MeghrajChoudhary: I guess you mean a hack. I would call it a trick, at most. Commented Jul 4, 2012 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.