The contents of {..} in your regex aren't interpolated. You actually need them to be (re)interpolated at the time of a possible match. You can do this with (??{ code }), which is a bit of an ugly hack... I have no idea if Parse::RecDescent will like these, presumably it just evals the regex so it may work.

my $regex = qr/\[(\d{1,20})(??{  " {" . (20 - length $1) . "}"  })\]/;

while (<DATA>) {
  print /$regex/ ? "yes\n" : "no\n";
}

__DATA__
[12345678901234567890]
[123                 ]
[234223423      ]
[23409234329c        ]
[download]

I don't know of a good way to do this without extended regex features (or multiple regexes). If there were some way to do this in general, I'd have to get to work on some regex abuse a la Abigail. There have been a few times when something like this would have been handy!