Les expressions régulières sont-elles un langage de programmation?

Au sens académique, les expressions régulières peuvent-elles être qualifiées de langage de programmation?

La motivation pour ma curiosité est une question SO que je viens de regarder qui a demandé "peut regex faire X?" et cela m'a fait me demander ce qui peut être dit au sens générique des solutions possibles en les utilisant.

_{Je demande essentiellement, "les expressions régulières de Turing sont-elles complètes"?}

Les expressions régulières sont un type particulier de grammaire formelle utilisée pour analyser des chaînes et d'autres informations textuelles connues sous le nom de "langues régulières" dans la théorie du langage formel. Ce n'est pas un langage de programmation en tant que tel. Ils sont plus un raccourci pour le codage qui serait autrement extrêmement fastidieux à mettre en œuvre et encore plus déroutant que le Regex parfois arcanique.

Les langages de programmation sont généralement définis comme des langages Turing Complete . Ces langages doivent pouvoir traiter n'importe quelle fonction calculable . Regex ne rentre pas dans cette catégorie.

Si vous voulez une langue qui ressemble à Regex, essayez J.

Il est difficile de répondre à des questions de type « est X un Y », si les participants de l'utilisation de débat différentes définitions de X et Y . Il se pourrait que pour certaines définitions, la réponse soit «oui», et pour certaines définitions, la réponse soit «non». Surtout si la réponse dépend de détails techniques où les différentes définitions diffèrent. Cette discussion contient également des informations erronées, alors veuillez patienter avec une réponse plus longue.

Qu'entend-on par « langage de programmation »?

Une réponse simple pourrait être "un langage utilisé pour créer des programmes". Bien sûr, mais: quel genre de programmes? Qu'en est-il d'un langage qui pourrait être utilisé pour créer certains types de programmes, mais pas d'autres types de programmes? Voici deux exemples spécifiques pour illustrer les cas extrêmes:

1) Un langage imaginaire appelé M fonctionne comme ceci: Si le programme contient la seule lettre "m", il crée un jeu de Démineur. Tout le reste est une erreur de syntaxe.

Intuitivement, ce n'est pas ce que nous entendons par dire "un langage de programmation". Mais le service marketing de M pourrait faire valoir qu'il répond techniquement à la définition, car il peut être utilisé pour créer un programme. Bien sûr, le compilateur fait certaines parties critiques pour vous, mais c'est ce que font les compilateurs, n'est-ce pas? Un compilateur du langage C traduit également quelques mots simples en dizaines d'instructions de processeur. Le compilateur M va juste plus loin et rend votre travail encore plus simple.

2) Si vous installez la version originale du célèbre Turbo Pascal, vous pouvez écrire de nombreux types de programmes. Mais vous ne pouvez pas écrire un jeu qui s'exécute dans le navigateur Web, car l'API nécessaire n'est tout simplement pas là.

Alors, quelle est exactement la chose qui fait de Turbo Pascal un langage de programmation, mais M ne l'a pas? En termes simples, vous pouvez faire plus en Pascal qu'en M. Mais imaginez que nous avons un M.NET, qui crée un jeu de démineur fonctionnant dans un navigateur Web. Alors maintenant, nous avons quelque chose que Pascal peut faire et M.NET ne peut pas, mais nous avons aussi quelque chose que M.NET peut faire et Pascal ne peut pas. Pourquoi devrions-nous considérer les avantages de Pascal importants et les avantages de M.NET non pertinents?

La réponse est que vous pouvez écrire toutes sortes d' algorithmes en Pascal, mais vous ne pouvez pas écrire d' algorithmes en M ou M.NET. Bien sûr, M compile votre commande "m" et C compile votre commande "strcmp". Mais vous pouvez placer "strcmp" dans un contexte plus large, par exemple comparer deux fichiers ligne par ligne, ou lire des milliers de chaînes et les trier par ordre alphabétique, ou ... enfin, des millions d'autres choses. Et c'est précisément cette capacité à utiliser des commandes données dans n'importe quel algorithme qui fait l'essence d'un langage de programmation.

Qu'est-ce qu'un algorithme et, plus important encore, qu'est-ce qu'un "algorithme"? En informatique, nous utilisons les mots Turing-complete . L'idée est qu'il existe un ensemble de langages informatiques, où chacun est capable de les simuler tous. L'un de ces langages est la machine de Turing, c'est pourquoi ils sont appelés ainsi. Pascal est là, C est là, Java est là, Python est là, Lisp est là, Smalltalk est là, même XSLT est là. Nos hypothétiques M et M.NET ne sont pas là. Vous pouvez en apprendre davantage à ce sujet dans n'importe quelle université offrant un cours d'informatique décent, mais l'idée est qu'un langage complet de Turing peut faire n'importe quoiqu'un autre langage complet de Turing peut faire, si vous leur donnez l'API minimale nécessaire. (Si vous donnez une API de navigateur Web à Pascal, vous pouvez créer toutes sortes de jeux dans le navigateur Web. Si vous donnez l'API de navigateur Web à M, vous ne pouvez toujours créer que Démineur.) On pourrait dire métaphoriquement que si vous supprimez toutes les API d'un langage de programmation, l'essentiel est ce qui reste.

Qu'entendons-nous par « expressions régulières »?

Différents langages de programmation les implémentent légèrement différemment. Mais l'idée originale était que les expressions régulières expriment des langues dites régulières . Notez que nous ne parlons pas ici de langages de programmation, mais de langages (pseudo-) humains. Imaginez que vous trouviez une tribu exotique parlant une langue composée uniquement de mots "ba", "baba", "bababa" et ainsi de suite. Vous pouvez décrire cette langue verbalement comme "une syllabe 'ba' répétée une ou plusieurs fois" ou en utilisant une expression régulière comme "(ba) +".

Les expressions régulières sont censées exprimer: "rien", "cette lettre", "ceci, suivi de cela", "ceci ou cela", "ceci, répété une ou plusieurs fois", et "pas ceci". - Telle est la définition mathématique . Tout le reste n'est qu'un raccourci pratique construit à partir des composants précédents. Par exemple, "ceci, répété deux ou trois fois" peut être traduit par "ceci, suivi de ceci, suivi de (ceci ou rien)", mais il pourrait être plus pratique d'écrire "ba {2,3}" que "baba (ba)? ".

Dans la vie réelle, une implémentation typique des "expressions régulières" implémente plus que cela. Par exemple, en utilisant la définition mathématique, une langue de "aba", "aabaa", "aaabaaa" et ainsi de suite - n'importe quel nombre de "a" s, suivi d'un "b", suivi du même nombre de "a "s - n'est pas une langue régulière. Cependant, de nombreuses "expressions régulières" utilisées aujourd'hui pourraient le détecter, en utilisant le concept supplémentaire de "la même chose que nous avons trouvée auparavant", écrit "(a +) b \ 1". En utilisant ce concept supplémentaire, nous pouvons faire des choses intéressantes, par exemple détecter des mots composés d' un nombre premier de lettres. Pourtant, nous ne pouvons faire aucun algorithme ... pour une explication pourquoi,

Donc, revenons au sujet d'origine: les expressions régulières (définies soit comme: des expressions décrivant des langages réguliers dans la hiérarchie Chomsky; soit comme: l'ancien, plus l'opération \ 1) un langage de programmation (défini comme: Turing-complete)? La réponse est non . Non, vous ne pouvez implémenter aucun algorithme à l' aide d'expressions régulières, et la capacité d'implémenter n'importe quel algorithme est ce que les personnes qui étudient en informatique comprennent généralement comme l'essence du langage de programmation.

Bien sûr, n'importe qui peut changer la réponse en insistant sur une définition différente . Comme je l'ai écrit au début, les détails techniques sont importants ici. Si vous vous trompez, vous obtenez une mauvaise réponse.

Et si vous n'êtes pas intéressé par les détails techniques, la réponse pourrait être: pouvez-vous utiliser des expressions régulières (et rien d'autre) pour créer un programme? Alors pourquoi l'appeler un langage de programmation? (Cependant, une réponse comme celle-ci a été téléchargée et supprimée ici, c'est pourquoi j'ai écrit cette version plus longue.)

EDIT: En outre, n'importe qui peut créer une bibliothèque implémentant sa propre nouvelle variante d '"expressions régulières" avec de nouvelles fonctionnalités ajoutées. À un certain moment, les nouvelles fonctionnalités peuvent être suffisantes pour que l'ensemble du système devienne Turing-complete. Un exemple trivial serait d'incorporer un langage complet de Turing en utilisant une nouvelle syntaxe; mais cela peut aussi arriver moins évidemment. Peut-être que c'est déjà arrivé.

Dans .Net, non seulement Regex peut gérer plusieurs formes de conditions, en utilisant différentes combinaisons d'alternance et de contournements, mais il peut également manipuler sa propre pile.

(?xm)
    (?>
        <(?<Tagname>table)[^>]*>
    )
(?(Tagname)
    (
        </(?(?!\k'Tagname')(?<-Tagname>))*\k'Tagname'>(?<-Tagname>)
    |
        (?>
            <(?<Tagname>[a-z][^\s>]*)[^>]*>
        )
    |
        [^<]+
    )+?
    (?(Tagname)(?!))
)

Ceci, par exemple, est un petit extrait que j'ai écrit pour récupérer un tableau HTML. Contrairement aux autres moteurs d'expression régulière, cela contrôle la pile des collections de capture (push, peek et pop) et peut gérer les objets imbriqués. J'en ai un plus complexe, mais c'est en quelque sorte propriétaire.

Je pense que dans cet exemple, Regex peut être considéré comme ayant toutes les exigences de base d'un langage de programmation. Il a des variables, une mémoire en ligne, des conditions, des entrées et des sorties, il se compile en utilisant l'un des multiples moteurs de compilation regex (.Net dans ce cas).

En réponse au squawking sur-utilisé pour (JAMAIS) analyser HTML avec Regex, je suis allé de l'avant et j'ai publié une réponse pré-tapée que je peux publier: Analyse HTML

Un exemple d'anoter (juste une démonstration) est le suivant:

Function Regex("<(td>)((?:[^<]*(?(?!</\1)<))*)</\1")
    Group(0) = "<"
    Group(1) = "td>"
    Group(0) += Group(1)
    Group(2) = LoopMethod()
    Group(0) += Group(2)
    Group(0) += "</" & Group(1)
    Return Group()
End Function

Function LoopMethod()
    retGroup = ""
    Do
        tmpGroup = Everything that is NOT an Opening HTML Delimeter
        If the Text following tmpGroup Does NOT Equal "</" & Group(1) Then
            tmpGroup += "<"
            retGroup += tmpGroup
        Else
            Exit Do
        End If
    Loop
    Return retGroup
End Function

Encore une fois, pour les perroquets HTML: analyse HTML

Cela montre une expression rationnelle plus simple effectuant des boucles et des conditions (algorithmes?). La seule chose qui manque est le calcul mathématique réel. Il s'agit d'une expression régulière plus détaillée qui tire simplement une cellule TD plus efficacement que la méthode "(. *?)" Typique.

Mais même en tant que passionné de Regex et maître autoproclamé, je ne dirais pas à quiconque que Regex est un langage de programmation. Mon propre argument contre moi-même est qu'il ne peut pas être autonome, il doit être exécuté via son propre moteur tout en étant pris en charge par un autre moteur de langage de programmation.

Bien qu'une recherche / remplacement dans une expression régulière ne soit pas un langage de programmation complet de Turing, comme expliqué par les réponses précédentes, si vous autorisez à utiliser des actions répétées de remplacement par des expressions régulières, alors oui, vous pouvez coder n'importe quelle machine Turing à l'aide d'une expression régulière:

La recherche / remplacement répété par des expressions régulières est un langage de programmation complet de Turing

Par conséquent, vous pouvez calculer n'importe quelle fonction calculable en utilisant la même recherche et remplacer encore et encore l'expression régulière javascript.

Pour prouver l'exhaustivité de Turing, il suffit de coder une machine de Turing en recherche / remplacement d'expressions régulières. Supposons que l'état de l'éditeur soit:

0000#12345:01-5:0#0000000

qui peut être lu comme une bande de symboles avec un lecteur dessus:

[left symbols]#[set of states]:[set of symbols]-[current state]:[current symbol]#[right symbols]

Pour la règle lisant 0 dans l'état 5, écrivant 1 et changeant son état en 3 et se déplaçant vers la gauche, nous l'abstractionons en utilisant la notation suivante:

5:0 => 1, 3:[left]

Nous encodons la notation précédente dans une expression régulière de recherche:

(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#

et son expression de remplacement (de type javascript)

#12345:01-$4:$1#$8

Ok, maintenant comment encoder de nombreuses règles? Nous utilisons la concaténation avec l' oropérateur |pour la recherche d'expressions régulières et nous combinons les résultats en remplaçant les numéros de groupe par des décalages. Par exemple, considérons l'ensemble des quatre règles.

5:0 => 1, 3:left
3:0 => 1, 5:right
5:1 => 1, 5:right
3:1 => 1: 3:stop

Nous les encodons dans une expression de recherche et de remplacement:

Search:
(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#|#(1)(2)(3)(4)(5):(0)(1)-3:0#(\d)|#(1)(2)(3)(4)(5):(0)(1)-5:1#(\d)|#(1)(2)(3)(4)(5):(0)(1)-3:1#

Replace by:
$15$23#12345:01-$4$13$21$27:$1$16$24$31#$8

Essayez-le dans votre moteur javascript préféré:

function turingstep(s) {
  return s.replace(/(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#|#(1)(2)(3)(4)(5):(0)(1)-3:0#(\d)|#(1)(2)(3)(4)(5):(0)(1)-5:1#(\d)|#(1)(2)(3)(4)(5):(0)(1)-3:1#/g,"$15$23#12345:01-$4$13$21$27:$1$16$24$31#$8");
}

var tape = "0000#12345:01-5:0#0000000"
for(var i = 0; i < 6; i++) {
  console.log(tape)
  tape = turingstep(tape)
}