Comme le titre l'indique, j'ai passé quelques heures le week-end dernier à essayer de résumer la classe de langages correspondant aux expressions régulières compatibles Perl, à l' exclusion de tout opérateur de correspondance qui permet d'exécuter du code arbitraire à l'intérieur du modèle .
Si vous ne savez pas ce que sont les PCRE, veuillez lire ceci et ceci .
Le problème est que les ressources disponibles sur Internet s'arrêtent à peu près aux langages sans contexte, et les PCRE peuvent correspondre plus que ceux (voir ci-dessous); mais je ne sais vraiment pas où trouver plus de théorèmes ou d'articles sur ce genre de choses.
En particulier: les PCRE sont évidemment un surensemble de langages normaux (car la syntaxe PCRE a tous les opérateurs de langage normaux).
Tout CFG peut être mis sous la forme normale de Greibach, ce qui supprime la récursivité gauche. Je pense que cela peut être utilisé au moyen de (?(DEFINE)...)groupes pour "traduire" la grammaire en sous-programmes correspondants, en évitant d'étouffer la récursion gauche, en traduisant:
- le non-terminal en tête de chaque production devient un sous-programme
(?<HEAD>...) - le corps de chaque production est mis dans le sous-programme; les terminaux sont laissés tels quels, les non-terminaux deviennent des invocations de procédure (ie
(?&NONTERMINAL)); - toutes les productions avec le même non terminal que la tête sont assemblées par l'
|opérateur (plus un groupement supplémentaire avec(?:...), si nécessaire) - le motif devient alors un
(?(DEFINE)...)groupe contenant toutes les productions "traduites", et une invocation pour la procédure du symbole de départ, pour correspondre à la chaîne entière, ie^(?(DEFINE)...)(?&START)$
Cela devrait concerner tout CFG. Par conséquent, les PCRE devraient pouvoir correspondre à n'importe quelle LFC.
Il y a plus: prenons le langage simple c'est-à-dire la langue des chaînes répétées deux fois. Ce langage n'est pas une LFC - le lemme de pompage des LFC échoue. (Faites particulièrement attention à ce que doit tenir, vous ne pouvez donc pas simplement pomper le début ou la fin des deux chaînes répétées.)
Cependant, cette langue est facilement compensée par une PCRE: ^(.*)\1$. Par conséquent, nous sommes strictement au-dessus des LFC.
Combien au-dessus? Eh bien, comme je l'ai dit, je n'en ai aucune idée. Je n'ai trouvé aucune ressource sur les CSL ou toutes les autres classes entre les deux pour me faire une idée. Un expert est-il disposé à en discuter?
Addendum: on m'a demandé de spécifier exactement quel sous-ensemble de la syntaxe PCRE doit être autorisé. Comme je l'ai écrit au début de l'article, je voulais exclure tout opérateur qui permet d'exécuter du code arbitraire à l'intérieur du modèle, comme ??{}.
Pour les besoins de l'argument, je pense que nous pouvons nous en tenir à la syntaxe définie par la page de manuel pcresyntax (3) , qui est un sous-ensemble raisonnable de ce que Perl 5.10-5.12 offre, moins les légendes (car elles ne sont pas à l'intérieur du modèle). Je ne suis pas sûr que l'ajout ou la suppression de verbes de contrôle de retour en arrière modifient le langage que nous pouvons reconnaître; si c'est le cas, ce serait bien de savoir quelles classes nous avons avec et sans celles-ci.
Réponses:
J'ai également trouvé cet article de blog extrêmement intéressant http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html . Il fournit la même preuve que j'ai donnée auparavant sur le fait que les expressions régulières reconnaissent les CFL (en réécrivant la grammaire à travers des
DEFINEblocs), et même certaines CSL (comme le langage des chaînes répétées); il s'appuie sur cela et continue, donnant une preuve que les expressions rationnelles avec des références arrières sont NP-dures (en réduisant 3-SAT à une expression rationnelle).la source
Ils décident tout au plus des langages contextuels (qui, comme vous le signalez, sont un sur-ensemble des langages sans contexte). Voir ce post de moines perl .
L'idée de base est que la "mémoire" de la machine est le nombre de groupes de capture, qui est délimité linéairement.
la source