use Algorithm::Loops qw( NestedLoops );

my $pat = '{a|b}cd{f|g|h}';

my @loops;
for ($pat) {
   if (/\G ( [^{]+ ) /xgc) {
      push @loops, [ $1 ];
      redo;
   }

   if (/\G \{ ([^}]*) \} /xgc) {
      push @loops, [ split /\|/, $1, -1 ];
      redo;
   }
}

NestedLoops(\@loops, sub { print(@_, "\n"); });
[download]

acdf
acdg
acdh
bcdf
bcdg
bcdh
[download]

Algorithm::Loops