<p>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).</p>

CC BY-SA 3.0
2016-04-10T19:50:55.217Z
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.
Witiko
CC BY-SA 3.0
2016-04-10T22:24:22.720Z
Regular expressions + backreferences (supported by PCRE) are  NP-hard (see for example http://perl.plover.com/NPC/). I'm also curious to see if there is a published paper on the subject.
Marzio De Biasi
<fl.formal-languages><automata-theory>
What is the class of the languages recognized by PCREs?
Witiko
# What is the class of the languages recognized by PCREs?

(Asked by: username_0 on 2016-04-10)

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

**Tags:** fl.formal-languages, automata-theory

> **Comments:**
> **username_0**: 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.  
> **username_1**: Regular expressions + backreferences (supported by PCRE) are  NP-hard (see for example http://perl.plover.com/NPC/). I'm also curious to see if there is a published paper on the subject.  

---

## 0 answers

