2
$\begingroup$

I have been considering building a tool that would convert regexes between the various syntaxes (BRE, ERE, PCRE). It is obvious that PCREs are too strong for the is-regular problem to be decidable, which would make the PCRE -> BRE / ERE conversion impossible in the general case, but it is clearly possible to recognise a subclass of regular PCREs via static analysis. I am curious if any research has been conducted and published in this regard and whether the class of languages recognized by PCREs has been formally described in relation to an existing hierarchy (Chomsky od otherwise).

$\endgroup$
  • $\begingroup$ Why would that "make the PCRE -> BRE / ERE conversion impossible in the general case"? ​ (For example, the halting problem is undecidable, but interpreters are such that whenever their input halts, the interpreter will halt with the same output.) ​ ​ ​ ​ $\endgroup$ – user6973 Apr 10 '16 at 16:00
  • $\begingroup$ od -> or ​ ​ ​ ​ ​ $\endgroup$ – user6973 Apr 10 '16 at 16:01
  • $\begingroup$ Well, if the conversion is impossible (halts), I'd like to be able to detect that. That won't be possible in the general case, since it's likely that PCRE >= Context-Sensitive -> Is-Regular is undecidable, but it should be possible to come up with a heuristic Is-Regular', such that Is-Regular'(L) -> Is-Regular(L). I'm curious whether there has been any published research into that. $\endgroup$ – Witiko Apr 10 '16 at 19:50
  • 2
    $\begingroup$ Regular expressions + backreferences (supported by PCRE) are NP-hard (see for example perl.plover.com/NPC). I'm also curious to see if there is a published paper on the subject. $\endgroup$ – Marzio De Biasi Apr 10 '16 at 22:24

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.