0
$\begingroup$

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".

$\endgroup$

0

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.