Your logic goes astray because you try to parse XML with regexps.

You shouldn't.

Please read On XML parsing for a (n incomplete) list of reasons not to.

Actually the problem seems even worse than that: it looks like you are calling XML something that is not XML: level=2 is not an attribute value in XML, you need to quote the value.

I can't really test much right now due to Antonio keeping me busy, but something like this using XML::Twig would certainly work:

#!/usr/perl -w
use strict;

use XML::Twig;

my $t= XML::Twig->new( twig_roots => { heading => \&heading },
                       twig_print_outside_roots => 1,
                       pretty_print => 'indented'
                     );
$t->parse( \*DATA);

sub heading
  { my( $t, $heading)= @_;
    if( defined $heading->att( 'level'))
      { $heading->set_gi( 'heading' .  $heading->att( 'level'));
        $heading->del_att( 'level');
      }
    elsif( my $pcdata= $heading->first_child( '#PCDATA'))
      { my $text= $pcdata->pcdata;
        if( $text=~ s/^\s*level\s*=\s*(\d+),//s)
          { $pcdata->set_pcdata( $text);
            $heading->set_gi( 'heading' . $1);
          }
      }
    $heading->print;
  }

__DATA__
<doc>
<heading>
  <index/>
  <index/>
  level=3,
  Specifying Rest Arguments in a Procedure Definition</heading>
<heading level="2">
    Introduction to Arguments</heading>
</doc>
[download]

And finally, if you really want to use regexps, you can have a look at XML::Regexp or at XML::Parser::Lite.