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]

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]

      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]
[reply]
[d/l]
[select]
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:
    1. Run under ActiveState Perl 5.8.2.808.
    2. Quoted regex narration for clarity.
[reply]
[d/l]
[select]
      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
[reply]

Back to Seekers of Perl Wisdom