Où se situent la plupart des implémentations REGEX sur l'échelle de complexité?

La plupart des implémentations modernes d'expressions régulières, telles que celles en perl ou .NET, vont au-delà de la définition informatique classique des REGEX avec des fonctionnalités comme lookahead et lookbehind. Ces fonctionnalités leur permettent-elles d'analyser des instructions qui ne peuvent pas être décrites avec un automate fini et non pushdown? Dans quelle mesure est-ce plus proche de la réalisation complète si cela est possible?

Je ne pense pas que le vrai problème soit la question de ce que signifie sans limites; ce n'est pas pire que toute autre situation d'analyse.

Le problème réside dans la caractérisation des références arrières, qui sont à la fois très puissantes et très limitées: elles permettent la description de certaines langues sans contexte, sans autoriser certaines langues sans contexte. Par exemple, l'expression régulière (a*)b\1b\1correspond à des chaînes de la forme , et vous pouvez utiliser le lemme de pompage pour montrer que ce n'est pas un langage sans contexte. Cependant, d'un autre côté, les expressions rationnelles avec des références inverses ne semblent pas être suffisantes pour correspondre au langage de parenthèse équilibrée, qui est le langage sans contexte prototypique.$a^n \cdot b \cdot a^n \cdot b \cdot a^n$

Il est assez facile de donner une sémantique dénotationnelle indiquant quelles chaînes sont dans un langage pour les expressions rationnelles, mais donner une bonne caractérisation théorique des automates semble beaucoup plus difficile. C'est quelque chose comme une machine à registres, dans les registres desquels vous pouvez copier les sous-chaînes de votre entrée, et que vous pouvez utiliser pour tester votre chaîne actuelle, mais pour laquelle vous n'avez pas la possibilité de modifier ces registres.

Les gens qui font de la théorie des modèles finis ont un tas de modèles de machines funky, et il serait intéressant de savoir si cela correspond à l'un de leurs modèles.

Le problème avec la réponse à cette question est de capturer la notion de "sans limite" dans une implémentation réelle. Par exemple, l'expression régulière /(.*)\1/capturera la langue , qui n'est pas sans contexte. En pratique, il pourrait y avoir des limites sur la pile utilisée (c'est-à-dire que ne peut pas être plus long qu'un certain grand nombre ), ce qui transformerait effectivement le langage en , qui pour tout fixe est à nouveau une expression régulière.w K L K = { w w | w ∈ Σ ∗ , ∣ w ∣ ≤ K } $L = \{ ww | w \in \Sigma^*\}$$w$$K$$L_K = \{ ww | w \in \Sigma^*, \mid w \mid \le K\}$$K$

Mais en principe, les expressions rationnelles telles que spécifiées sont plus puissantes que les langues normales, comme cette question connexe en discute beaucoup plus en détail (avec un exemple astucieux également).

Un résultat intéressant, tiré de cette autre question , également liée par Suresh Venkat, est que les regexps «pratiques» sont NP-complets, et donc ils devraient être équivalents en puissance à SAT.

Étant un non-expert, bien que je convienne qu'intuitivement "les expressions rationnelles avec des références arrières ne semblent pas être suffisantes pour correspondre au langage de parenthèse équilibrée", il se passe quelque chose d'étrange. L'exhaustivité de NP implique que tout problème de NP peut être réduit polynomialement à une expression rationnelle, donc il y a probablement juste une réduction polynomiale du langage "entre parenthèses équilibrées" à un identifiable avec des expressions régulières. Mais encore une fois, il peut y avoir une expression rationnelle absurde pour analyser une CFL, car ils peuvent même analyser des nombres unaires non premiers!

La leçon est probablement que les classes de complexité et les classes de langue ne sont pas comparables, en général. Ce qui suggère également de reformuler votre question, pour faire référence à la hiérarchie de Chomsky plutôt qu'à «l'échelle de complexité» (même si, pour être honnête, cela ne m'a pas dérouté).

Charles Stewart écrit:

Aho, 1990, «Algorithms for find patterns in strings» montre que le problème d'appartenance pour les langues régulières avec retour en arrière est NP complet.

Un aperçu partiel (au moins de la déclaration) peut être trouvé sur Google Books , à la page 289, et une référence bibliographique à l'article peut être trouvée ici . Notez que dans le document, rewbr signifie Regular Expression With BackReferences.

PCRE, l'implémentation la plus populaire des "expressions régulières" implémente également des modèles récursifs, qui vont au-delà des références arrières. Une question sur leur complexité vient d'être posée sur Stackoverflow. Selon la réponse pratique en profondeur du gourou de Perl, Brian D Foy, cela rend PCRE aussi puissant que les grammaires sans contexte. Cependant, la syntaxe est horrible par rapport à Backus-Naur Form.