You can do away with a lot of the punctuation by putting the dereference inside rand_elt() which avoids having it most everywhere else. By predeclaring generate(), you can avoid the need for parens on most of the function calls which cleans it up further.

The final thing of using nested ternaries rather than if / then / else is probably a step too far and will be seen as golfing, but I think it actualy comes closer to the Lisp cond operator (function?).

#! perl -slw
use strict;

my %dict = (
  sentence     => [ [ qw/ noun_phrase verb_phrase / ] ],
  noun_phrase  => [ [ qw/ Article Noun / ] ],
  verb_phrase  => [ [ qw/ Verb noun_phrase / ] ],
  Article      => [ qw/ the a /],
  Noun         => [ qw/ man ball woman table/ ],
  Verb         => [ qw/ hit took saw liked / ]
);


sub rand_elt {
    return @{ $_[ 0 ] }[ rand @{ $_[ 0 ] } ];
}

sub listp {
    return ref $_[0] eq "ARRAY";
}

sub generate;
sub generate {
    my $phrase = shift;
    return listp( $phrase )      ? map{ generate $_  } @{ $phrase }   
        :exists $dict{ $phrase } ? generate rand_elt $dict{ $phrase } 
+: $phrase;
}

print join ' ', generate "sentence";
[download]