Introduction aux expressions régulières

Les expressions régulières sont souvent considérées comme incapables de parser les langages HTML en raison de leur irrégularité. Cependant, cette affirmation est trompeuse car les expressions régulières modernes sont beaucoup plus puissantes que ce que leur nom suggère.

Qu'est-ce qu'un langage régulier ?

Un langage régulier est défini par une grammaire où toutes les règles de production ont l'une des formes suivantes : B -> a, B -> aC ou B -> ε. Les caractères majuscules représentent des non-terminaux, qui peuvent être décomposés, tandis que les caractères minuscules représentent des terminaux, qui ne peuvent pas être décomposés.

B -> a
B -> aC
B -> ε

Par exemple, la grammaire définissant les nombres naturels est régulière car elle peut être exprimée sous la forme d'une expression régulière : [0-9]+.

Les expressions régulières et la hiérarchie de Chomsky

La hiérarchie de Chomsky divise les langages formels en quatre types : les langages récursivement énumérables (Type 0), les langages sensibles au contexte (Type 1), les langages libres de contexte (Type 2) et les langages réguliers (Type 3). Les expressions régulières peuvent matcher les langages réguliers, mais également certains langages libres de contexte.

Exemple de matching d'un langage libre de contexte

Le langage {a^n b^n, n>0} peut être matché par l'expression régulière PCRE : 

^(a(?1)?b)$
. Cette expression utilise une référence récursive pour matcher les chaînes de caractères avec le même nombre de 'a' et 'b'.

Les expressions régulières sont donc capables de matcher des langages non réguliers, mais leur puissance dépend de l'implémentation spécifique utilisée.