Accueil  / Semaine 5 / Présentation de la semaine

Présentation de la semaine

Présentation de la semaine

Cette semaine, nous allons aborder l’aspect formel des expressions régulières. Nous compléterons l’introduction aux expressions régulières de la leçon 4 et nous verrons comment implémenter des moteurs d’expressions régulières avec des automates finis. À la fin de la semaine, vous serez en mesure de reconnaître ou de comprendre les difficultés associées au traitement des expressions régulières.

Nous allons terminer la semaine avec quelques exemples d’utilisation des expressions régulières en Java. À la fin de cette semaine, vous pourrez programmer les expressions régulières en Java.

Évidemment, les expressions régulières sont supportées par pratiquement tous les langages, incluant C++ (voir Boost), Python (paquetage « re »), etc. Mais nous ne pourrons pas couvrir tous les types de langage dans ce cours.

Hiérarchie de Chomsky

Les expressions régulières font partie de la hiérarchie de Chomsky. La hiérarchie de Chomsky est une façon de classifier différents types de langage à l’aide de grammaires formelles élaborées selon le degré de sophistication nécessaire pour les traiter.

Commençons d’abord par un peu de terminologie. La plupart des langages informatiques que vous connaissez (Java, C++, C#, Visual Basic, etc.) sont équivalents à une machine de Turing. Sur le plan théorique, tous ces langages peuvent être comparés à une machine (ou à un humain) qui utiliserait un ruban comprenant des caractères (provenant d’un alphabet) qu’on peut faire avancer ou reculer, et sur lequel on peut lire et écrire.

Nous allons voir qu’un moteur d’expressions régulières est conçu à l’aide d’un automate fini (déterministe ou non). Un automate est un type de programme informatique simple. Si on devait programmer en n’utilisant que des automates, on ne pourrait pas faire tout ce qu’on peut faire avec Java, C++ ou C#, etc. Les automates finis ne sont pas équivalents à une machine de Turing : si la machine de Turing peut faire tout ce que l’automate peut faire, le contraire n’est pas vrai.

Il manque plusieurs éléments à un automate fini. Par exemple, un automate fini n’a pas de « pile » : une pile est une unité de stockage où on empile (ou dépile) des éléments l’un par-dessus l’autre, de telle manière qu’on ne puisse voir que le dessus de la pile (voir java.util.Stack).
À plus forte raison, un automate n’a pas de « liste » : une liste est tout simplement une chaîne d’éléments qu’on peut visiter en séquence et dans laquelle on peut ajouter de nouveaux éléments à n’importe quel endroit (voir java.util.List).

Une expression est donc régulière si elle peut être traitée avec un « automate fini ». Toutes les expressions régulières utilisées en pratique ne sont pas, pour autant, « régulières » : on triche, parfois, en introduisant des notations qui ne sont pas régulières.

Voici un résumé de la syntaxe des expressions « vraiment » régulières :

  1. « . » n’importe quel caractère ;
  2. « [ ] » tout caractère qui est dans la liste (« [abc] » correspond à « a » ou « b » ou « c ») ; on peut utiliser le caractère « - » pour omettre les caractères intermédiaires comme dans « [a-z] ». La syntaxe « [^] » permet d’identifier tous les caractères qui ne font pas partie de la liste (« [^abc] » signifie ni « a », ni « b », ni « c ») ;
  3. « ^ » (hors des crochets) signifie le début d’une ligne ;
  4. « $ » signifie la fin d’une ligne ;
  5. « * » ou « ? » ou « + » signifient « répéter zéro, une ou plusieurs fois », « répéter zéro ou une fois », et « répéter une ou plusieurs fois » ;
  6. « 1,4 » signifie « répéter entre 1 et 4 fois ».

Par exemple, une expression n’est pas vraiment régulière si elle comporte une parenthèse capturante.

Supposons maintenant qu’on veuille traiter une grammaire. Cela pourrait être la grammaire de la langue française, ou la grammaire de Java. Plus la grammaire sera sophistiquée, plus il faudra un logiciel sophistiqué pour la traiter. Chomsky a proposé de classer les grammaires en 4 catégories, de la plus complexe (niveau 0) à la plus simple (niveau 3).

niveau sophistication
3 On peut écrire la grammaire en utilisant simplement un moteur d’expressions régulières.
2 On peut écrire la grammaire en utilisant un moteur d’expressions régulières qui a, de plus, accès à une pile.
1 On peut écrire la grammaire en utilisant simplement un moteur d’expressions régulières qui a, de plus, accès à une liste.
0 Il faut toute la puissance d’une machine de Turing pour traiter la grammaire.

En somme, les belles grammaires « simples » sont les grammaires de langages dits réguliers. Avant de traiter un langage donné, il est utile de savoir où il se trouve dans la hiérarchie de Chomsky. La grande majorité des langages (comme Java et le français) n’ont pas une grammaire de niveau 3.

En pratique, les expressions régulières sophistiquées que Java supporte, par exemple, ne sont pas des expressions régulières « pures » (de niveau 3), mais sont plutôt de niveau 1. Seules les expressions régulières « de base » sont de niveau 3.