Quelles langues les expressions régulières compatibles Perl reconnaissent-elles?

23

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

L={ww|wΛ}
|vXw|p

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.

peppe
la source
2
Veuillez inclure la définition que vous avez choisie de PCRE dans votre question, car elle a changé entre les versions. Les regexes Perl réelles peuvent contenir du code Perl arbitraire, ce qui les rend complètes de Turing.
Gilles 'SO- arrête d'être méchant'
J'ai ajouté une note à la fin, j'espère que cela clarifiera ce point.
peppe

Réponses:

7

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

peppe
la source
2
Lorsque l'auteur dit "NP-complet", il devrait dire "NP-dur". Ils ne fournissent aucune preuve que la classe des langages PCRE est contenue dans NP.
András Salamon
Certes, cela est également noté dans les commentaires.
peppe
5

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.

Xodarap
la source
5
L'argument que vous donnez dans le deuxième paragraphe explique pourquoi PCRE ne peut pas accepter plus que CS, mais pas pourquoi cette inclusion est exacte (ce que vous proposez dans votre premier paragraphe). Il ne semble pas non plus que l'article lié en ait apporté la preuve.
Raphael
Eh bien, vous ne pouvez pas grouper plus que ce qui est dans la chaîne d'entrée, et le nombre de groupes est fixé dans un modèle donné, vous avez donc une limite supérieure (linéaire) à la mémoire qu'un modèle utilise. Pourtant, il me manque une preuve formelle d'une PCRE -> transformation automate linéaire bornée ...
peppe
Oui, vous avez raison. J'ai modifié la réponse.
Xodarap
Voir aussi perlmonks.org/?node_id=406253 pour une discussion antérieure.
András Salamon