balanced parens regexp hangs

grizzley has asked for the wisdom of the Perl Monks concerning the following question:

Hi!

I am writing a script to parse IDL file and to generate graphviz file from it. I encountered following problem, which I isolated below:

Regexp tries to find 'module <module_name> { content };' text globally (//g) and if found, content is parsed recursively to create nested 'subgraph {}' sequences. Code below hangs. And if I remove innemost parens - it works good. Can anyone enlighten me what can be wrong? I am using this regexp (nested parens) for more than year in several scripts and it works (uhm, worked) perfectly since now.

With 'use warnings;' it prints 'Use of uninitialized value in pattern match (m//)', but it doesn't help me in any way to understand the problem.

Thank for any help.

#!perl

$_=join"",<DATA>;

sub parse
{
    my ($text) = @_;
    $nw++;
    
    my $parens = qr{(?:[^{}]+?|\{(??{$parens})\})*}x;
    
    while($text =~ /module (\w+) \{ ($parens) \};?/gx)
    {
        ($name, $content)=($1, $2);
#         print "[$&]";
        print '  'x$nw, "subgraph $name\n";
        print '  'x$nw, "{\n";
        parse($content);
        print '  'x$nw, "}\n";
    }
    $nw--;
}

print "digraph G\n{\n";

parse($_);

print "}\n";

__DATA__
module abc
{
    module def
    {
        module ghi
        {
        };
    };
};
[download]

Comment on balanced parens regexp hangs - solved Download Code

Replies are listed 'Best First'.
Re: balanced parens regexp hangs by moritz (Cardinal) on Mar 26, 2009 at 22:31 UTC
Your code does not hang on my machine, with perl-5.10.0. `(?:[^{}]+?\|\{(??{$parens})\})` Such a regex with nested quantifiers is potentially dangerous, because the outer quantifier can force the inner quantifier to backtrack. Use a non-backtracking group `(?>...)` instead. (Oh, and why are you using non-greed `+?` on the `[^{}]` group? I see no reason for that).	[reply] [d/l] [select]
Re^2: balanced parens regexp hangs by grizzley (Chaplain) on Mar 27, 2009 at 08:32 UTC
I run it on WinXP with ActiveState Perl v5.10.0. (build 1004). Localizing helped solving my problem, but I removed non-greed and tried to use `(?>...)` but I must admit I don't fully understand documentation of this construct yet. Did you think about something like this? `local $parens = qr{(?:(?>[^{}])\|\{(??{$parens})\})*}x;` [download]	[reply] [d/l] [select]
Re^3: balanced parens regexp hangs by moritz (Cardinal) on Mar 27, 2009 at 09:07 UTC
Actually I meant `(?>(?>[^{}])\|\{(??{$parens})\})`, since I don't see a reason why any of these groups should ever give up something that they successfully matched. For an explanation of `(?>...)` see How backtracking works in regular expressions and Avoiding regex backtracking.	[reply] [d/l] [select]
Re^4: balanced parens regexp hangs by grizzley (Chaplain) on Mar 27, 2009 at 10:10 UTC
Re: balanced parens regexp hangs by AnomalousMonk (Archbishop) on Mar 27, 2009 at 00:47 UTC
In addition to moritz's comment, be aware that the `//x` modifier used in your posted code with the `/module (\w+) \{ ($parens) \};?/gx` regex means that whitespace is a comment, so you are looking for "the substring `'module'`, followed immediately by one or more `\w` characters, followed immediately by a `'{'` character, etc..." As moritz said, lexical variables do not play well with the `(??{ code })` Extended Patterns variant; it is really intended to work with package variables. The following works for me (note that `$parens` is a fully local-ized package variable): use warnings; use strict; use constant DENT => ' '; our $parens; my $text = do { local $/; <DATA> }; sub parse { my ($text, $indent) = @_; $indent = 0 unless defined $indent; local $parens = qr{ (?: [^{}]+? \| \{ (??{$parens}) \} )* }xms; while ($text =~ /module \s+ (\w+) \s* \{ ($parens) \} ;? /gx) { my ($name, $content) = ($1, $2); print DENT x $indent, qq(subgraph $name { \n); ++$indent; parse($content, $indent); print DENT x $indent, qq(} \n); --$indent; } } # print $text; # FOR DEBUG print "digraph G\n{\n"; parse($text); print "}\n"; __DATA__ module abc { module def { module ghi { module jkl {} }; }; }; [download] Output: `digraph G { subgraph abc { subgraph def { subgraph ghi { subgraph jkl { } } } } }` [download] Updates: Run under ActiveState Perl 5.8.2.808. Quoted regex narration for clarity.	[reply] [d/l] [select]
Re^2: balanced parens regexp hangs by ikegami (Patriarch) on Mar 27, 2009 at 01:01 UTC
There's no reason to have the `our` where it is. Use the following instead: `local our $parens = qr{ ... }xms;` [download]	[reply] [d/l] [select]
Re: balanced parens regexp hangs by Anonymous Monk on Mar 27, 2009 at 03:19 UTC
http://search.cpan.org/~perrad/CORBA-IDL-2.63/bin/idl	[reply]


Pathologically Eclectic Rubbish Lister
	PerlMonks

balanced parens regexp hangs - solved