It's recursive, I don't know if all cases can be covered¹ but most cases are much easier then one might think:

> perl -e'use re 'debug'; qr/(x{100}.*y{100})*/' 
Compiling REx "(x{100}.*y{100})*"
Final program:
   1: CURLYX[0] {0,32767} (18)
   3:   OPEN1 (5)
   5:     CURLY {100,100} (9)
   7:       EXACT <x> (0)
   9:     STAR (11)
  10:       REG_ANY (0)
  11:     CURLY {100,100} (15)
  13:       EXACT <y> (0)
  15:   CLOSE1 (17)
  17: WHILEM[1/1] (0)
  18: NOTHING (19)
  19: END (0)
minlen 0 
Freeing REx: "(x{100}.*y{100})*"
[download]

> But all this is really speculation so long as the OP does not tell us which kind of regexes she or he wants to use.

Yes the monastery has the tendency to answer kindergarten questions with a PHD thesis.

I certainly won't start to implement it, just showing the theoretical approach.

update

¹) with an opcode interpreter