Is there any paper (or at least technical report / preprint or even thesis) mentioning that regex engines cannot match expressions that contain "left recursion" (explained below)? I am particularly interested in libpcre2; however, references on other regex engines would help as well.

An example of the "left-recursive problem": (?(DEFINE)(?<A>((?=(?&B))(?&B)*|a*)))(?(DEFINE)(?<B>(?=(?&A))a*|b*))^(?&A)*$ is syntactically correct (compiled) while rejected by the engine when matching some input text, e.g., a (when subroutine A is called, B needs to be evaluated within lookahead; to do it, A needs to be evaluated within lookahead, which is rejected as A is recursively called again while there is no advance in the input text (endless recursion)).

This question does not involve behaviour of this particular software. What I need is knowledge whether this behaviour is published (in some academic text). I have found mentions of this problem at this site and at a few blog posts. (No mention at all in official documentation.) All without any more details on "why".



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.