Hi All,

I posted a question earlier about this, but now I have narrowed in on the cause of the problem. The code below is a simplified parser of C conditionals. Simply enter a conditional, such as foo && (bar || baz) on the command line, and it will create a tree-like structure. Well, for a simple expression (no parentheses), this works fine. For a complicated expression that causes treeify() to recurse, it still works, but the interpreter crashes afterward, apparently during garbage collection.

Can anyone see what I have done wrong? I have no clue what the problem is. I appreciate all help greatly.

I am running ActiveState v.5.8.3 on Win32.

Thanks, ColonelPanic

#!/usr/bin/perl -w
use strict;

{
   my $exp;
   chomp ($exp = <STDIN>);
   init_regexes();
   my $foo = treeify($exp);
   use Data::Dumper;
   print Dumper($foo);
}


my $TERM = "";
my $FUNCTION_CALL = "";
my $ATOM = "";
my $PAREN_EXP = "";
my $CONDITIONAL = "";
my $PAREN_COND = "";
my $OPERATOR = "";     
my %OPS = ( '&' => 1, '|' => 2, '&&' => 3, '||' => 4, );

#regexes to parse C conditionals (more or less).
sub init_regexes
{
   $TERM = qr/
      (?:
         (?:
            (??{$PAREN_COND})
         )
         |
         (?:
            (??{$FUNCTION_CALL})
         )
         |
         (?:
            (??{$ATOM})
         )
      )
   /x;

   $PAREN_EXP = qr/
      \(
      \s*
      (?:
         (?> [^()&|]+ )
         |               
         (??{$PAREN_EXP})
      )
      \s*            
      \)
   /x;

   $ATOM = qr/
      (?:
         (?:
            (?: [!*&] | \b )
            \w+\b
         )
         |
         (??{$PAREN_EXP})
      )
   /x;

   $FUNCTION_CALL = qr/
      \b\w+\s?
      \(
      \s*(??{$TERM})\s*
      (?:
         ,\s*(??{$TERM})\s*
      )*
      \)
   /x;

   $OPERATOR = qr/
      (?: && | \|\| | & | \| | \^ )
   /x;

   $CONDITIONAL = qr/
      ((??{$TERM}))
      (?:
         \s*
         ( (??{$OPERATOR}) )
         \s*
         (?:
            ((??{$TERM}))
         )
      )+
   /x;

   $PAREN_COND = qr/
      !?
      \(
      (?:
         (??{$CONDITIONAL})
      )
      \)
   /x;
}


#make a tree out of a C expression. 
sub treeify
{
   my $exp = shift;
   my $tree;

   #find the first term in the string; put in $1 and delete.
   while ($exp =~ s/^($TERM)//)
   {
      my $term = $1;
      my $type = 'atom';
      if ($term =~ /\s*($CONDITIONAL)\s*/)
      {
         $term = $1;
         $type = 'cond';
      }
      
      my $new_term = {
         'type'  => $type,
         #if the term itself should be a node, process it.
         'value' => $term,
         'ref' => undef
      };

      if ($type eq 'cond')
      {
         $new_term->{'ref'} = treeify($term);
      }

      push @{ $tree->{'terms'} }, $new_term;

      #now find, put in $1, and delete the next operator.
      if ($exp ne '' and $exp =~ s/^\s*($OPERATOR)\s*//)
      {
         $tree->{'op'} ||= $1;    
      }
      else
      {
         return $tree;
      }
   }
}
[download]

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.