Not an answer but you're treading well into "very hard problem" territory. See Cloudflare blames PCRE for outage and the post referenced here Cloudflare uses Regexp::Debugger in explaining the outage for a similar real world occurrence.

Update: dittos on the halting problem mention below; I almost said as much myself rather than just "very hard".