I admit it's a long time ago I had to parse something as "complex" as a context-free language. But I've done quite a lot of regular expression mojo since.
Even with 5.10 regular expressions, I would not use regular expressions to parse something. I'd use regular expressions to tokenize the stream, but I'd use some kind of state machine for the parsing. I do consider Parse::RecDescent to implement a state machine, with hooks for callbacks, that uses regular expressions to tokenize. (Of course, regular expressions themselves are state machines...)
Of course, I may change my mind halfway the project....