Best way to sort these strings ? recursive way ? use Parse::RecDescent?

I don't see anything recursive about it and this is certainly not a job for Parse::RecDescent.

Have you actually tried anything here? Got code?

I'd approach this by building a data structure from all the input before outputting it. Knowing nothing more about your input than the sample you've provided, I'd use a structure that looked like this when complete:

{
  'EX1J' => { 
    'desc' => 'JOB1' 
    'pred' => [],
  },
  'EX2J' => { 
    'desc' => 'JOB2'
    'pred' => [], 
   },
  'EX3J' => { 
    'desc' => 'JOB3'
    'pred' => ['EX1J'], 
   },
  'EX4J' => { 
    'desc' => 'JOB3'
    'pred' => ['EX1J', 'EX2J'], 
   },
}
[download]

-sauoq
"My two cents aren't worth a dime.";

my %data;

while (<DATA>) {
   chomp;

   if (/^JOB ID=(\S+) DESC='(\S+)'/) {
      my $id   = $1;
      my $desc = $2;
      $data{$id} = {
         desc => $desc,
         pred => [],
      };
   } else {
      my ($id, $pred) = (split(/\s+/))[0, 2];
      push(@{$data{$id}{pred}}, $pred);
   }
}

require Data::Dumper;
print(Data::Dumper::Dumper(\%data));

__DATA__
JOB ID=EX1J DESC='JOB1'
JOB ID=EX2J DESC='JOB2'
JOB ID=EX3J DESC='JOB3'
JOB ID=EX4J DESC='JOB3'
EX4J PRED EX2J
EX3J PRED EX1J
EX4J PRED EX1J
[download]

use warnings;
use strict;
use Parse::RecDescent;
use Data::Dumper;

my $string = <<END;
JOB ID=EX1J DESC='JOB1'
JOB ID=EX2J DESC='JOB2'
JOB ID=EX3J DESC='JOB3'
JOB ID=EX4J DESC='JOB3'
EX4J PRED EX2J
EX3J PRED EX1J
EX4J PRED EX1J
END

our %data;
my $parser = Parse::RecDescent->new (q{
    startrule  : jobphrase(s) exphrase(s) 
    jobphrase  : "JOB ID=" ex "DESC=" jobquote  
                {
                    $::data{$item[2]}{'desc'} = $item[4]; 
                    $::data{$item[2]}{'pred'} ||=[]
                }
    exphrase   : ex "PRED" ex 
                {
                    push @{$::data{$item[1]}{'pred'}}, @item[3] 
                } 
    jobquote   : "'" job "'" {$return = $item[2]}
    ex         : /EX\dJ/
    job        : /JOB\d/
    });

$parser->startrule($string);

print Dumper \%data;
[download]

for ( sort keys %data ) {
    my $pred = join( ', ', @{$data{$_}{pred}} );
    print "$_    desc $data{$_}{desc}   PRED $pred\n";
}
[download]