Comment puis-je normaliser/canoniser un modèle d'expression régulière?

Question

J'ai une expression régulière complexe que j'ai construite avec du code. Je veux le normaliser à la forme la plus simple (canonique) qui sera une expression régulière équivalente mais sans les parenthèses supplémentaires et ainsi de suite.

Je veux que ce soit normalisé afin que je puisse comprendre si c'est correct et y trouver des bugs.

Voici un exemple pour une expression régulière que je veux normaliser:

^(?:(?:(?:\r\n(?:[ \t]+))*)(<transfer-coding>(?:chunked|(?:(?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)(?:(?:;(?:(?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)=(?:(?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)|(?:"(?:(?:(?:|[^\x00-\x31\x127\"])|(?:\\[\x00-\x127]))*)))))*))))(?:(?:(?:\r\n(?:[ \t]+))*),(?:(?:\r\n(?:[ \t]+))*)(<transfer-coding>(?:chunked|(?:(?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)(?:(?:;(?:(?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)=(?:(?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+)|(?:"(?:(?:(?:|[^\x00-\x31\x127\"])|(?:\\[\x00-\x127]))*)))))*))))*))$ 

Answer 1

Je suis avec les autres réponses et commentaires jusqu'à présent. Même si vous pouviez définir une forme réduite, il est peu probable que la forme réduite soit plus compréhensible que cette chose, qui ressemble au bruit de ligne sur un modem à 1200 bauds.

Si vous avez voulez trouver une forme canonique pour les expressions régulières, je voudrais commencer par définir précisément ce que vous entendez par « forme canonique ». Par exemple, supposons que vous avez l'expression régulière [ABCDEF-I]. Est la forme canonique (1) [ABCDEF-I], (2) [ABCDEFGHI] ou (3) [A-I]? C'est-à-dire, pour les besoins de la canonisation, voulez-vous (1) ignorer ce sous-ensemble d'expressions régulières à des fins de canonisation, (2) éliminer tous les opérateurs "-", simplifiant ainsi l'expression, ou (3) le rendre plus court? Le moyen le plus simple serait de parcourir chaque partie de la spécification d'expression régulière et de déterminer quelles sous-expressions sont logiquement équivalentes à une autre forme, et de décider lequel des deux est "plus canonique". Ensuite, écrivez un analyseur d'expressions régulières récursif qui passe par une expression régulière et remplace chaque sous-expression par sa forme canonique. Continuez à faire cela en boucle jusqu'à ce que vous trouviez le "point fixe", l'expression régulière qui ne change pas quand vous le mettez sous forme canonique.

Cela, cependant, ne fera pas nécessairement ce que vous voulez. Si ce que vous voulez est de réorganiser l'expression régulière pour minimiser la complexité du groupement ou quelque chose de ce genre alors ce que vous pourriez vouloir faire est de canoniser l'expression régulière de sorte qu'elle soit dans une forme telle qu'elle n'a que groupement, union et Kleene opérateurs étoiles. Une fois qu'il est dans cette forme, vous pouvez facilement le traduire en un automate fini déterministe, et une fois qu'il est sous forme DFA, vous pouvez exécuter un algorithme de simplification de graphique sur le DFA pour former un DFA plus simple équivalent. Vous pouvez ensuite retourner le DFA simplifié résultant dans une expression régulière.

Bien que ce serait fascinant, comme je l'ai dit, je ne pense pas que cela résoudrait réellement votre problème. Si je comprends bien, votre problème est pratique. Vous avez ce bordel, et vous voulez comprendre que c'est juste.

Je voudrais aborder ce problème par un point d'ancrage complètement différent. Si le problème est que la chaîne littérale est difficile à lire, ne l'écrivez pas comme une chaîne littérale. Je commence à « simplifier » l'expression régulière en en faisant lire comme un langage de programmation au lieu de lire comme ligne de bruit:

Func<string, string> group = s=>"(?:"+s+")"; 
Func<string, string> capture = s=>"("+s+")"; 
Func<string, string> anynumberof = s=>s+"*"; 
Func<string, string> oneormoreof = s=>s+"+"; 
var beginning = "^"; 
var end = "$"; 
var newline = @"\r\n"; 
var tab = @"\t"; 
var space = " "; 
var semi = ";"; 
var comma = ","; 
var equal = "="; 
var chunked = "chunked"; 
var transfer = "<transfer-coding>"; 
var backslash = @"\\"; 
var escape = group(backslash + @"[\x00-\x7f]"); 
var or = "|"; 
var whitespace = 
    group(
     anynumberof(
      group(
       newline + 
       group(
        oneormoreof(@"[ \t]"))))); 
var legalchars = 
    group(
     oneormoreof(@"[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]")); 

var re = 
    beginning + 
    group(
     whitespace + 
     capture(
      transfer + 
      group(
       chunked + 
       or + 
       group(
        legalchars + 
        group(
         group(
          semi + 
          anynumberof(
           group(
            legalchars + 
            equal + 

...Une fois qu'il semble que ce sera beaucoup plus facile à comprendre et à optimiser.

Answer 2

Je ne suis pas au courant d'aucun outil qui peut le faire. Je doute même fortement qu'il existe quelque chose comme une forme canonique pour les expressions régulières - elles sont suffisamment complexes pour qu'il y ait généralement plusieurs solutions très différentes.

Si cette expression est la sortie d'un générateur, il me semble beaucoup plus prometteur de tester (unitaire) le générateur de code.

Answer 3

Je venais de l'écrire sous une forme élargie:

^ 
(?: 
    (?: (?: \r\n (?:[ \t]+))*) 
    (<transfer-coding> 
    (?: chunked 
    | (?: 
      (?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+) 
      (?: 
      (?: 
       ; 
       (?: 
       (?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+) 
       = 
       (?: (?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+) 
       | (?: 
         " 
         (?: 
         (?: 
          (?: 
          | [^\x00-\x31\x127\"] 
          ) 
         | (?:\\[\x00-\x127]) 
         )* 
        ) 
        ) 
       ) 
      ) 
      )* 
     ) 
     ) 
    ) 
) 
    (?: 
    (?: (?: \r\n (?:[ \t]+))*) 
    , 
    (?: (?: \r\n (?:[ \t]+))*) 
    (<transfer-coding> 
     (?: chunked 
     | (?: 
      (?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+) 
      (?: 
       (?: 
       ; 
       (?: 
        (?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+) 
        = 
        (?: (?:[\x21\x23-\x27\x2A\x2B\x2D\x2E0-9A-Z\x5E\x7A\x7C\x7E-\xFE]+) 
        | (?: 
         " 
         (?: 
          (?: 
          (?: 
          | [^\x00-\x31\x127\"] 
          ) 
          | (?:\\[\x00-\x127]) 
          )* 
         ) 
        ) 
       ) 
       ) 
      )* 
      ) 
     ) 
    ) 
    ) 
) 
) 
$ 

Vous pouvez localiser rapidement le regroupement inutile, et localiser des erreurs. Quelques erreurs que j'ai vu:

• Manquant ? pour les groupes nommés. Il devrait être (?<name>).
• Pas de guillemets doubles (").

Vous pouvez même utiliser la regex sous cette forme. Si vous fournissez l'indicateur RegexOptions.IgnorePatternWhitespace lors de la construction de l'objet Regex, les espaces ou les commentaires (#) dans le modèle seront ignorés.

Answer 4

Je pense que vous êtes en avance sur vous-même; les problèmes avec cette regex ne sont pas seulement cosmétiques. Beaucoup de parenthèses peuvent simplement être supprimées, comme dans (?:[ \t]+), mais je soupçonne que certaines d'entre elles changent la signification de l'expression rationnelle d'une manière que vous n'aviez pas l'intention. Par exemple, que veut dire (?:|[^\x00-\x31\x127\"])? Avec ce tuyau au début, c'est équivalent à [^\x00-\x31\x127\"]?? - zéro ou un, à contrecœur, de ce que la classe de caractères correspond. Est-ce vraiment ce que vous vouliez?

La classe de caractères elle-même est également hautement suspecte. Il est évidemment destiné à correspondre à autre chose qu'un caractère de contrôle ASCII ou un guillemet, mais les nombres sont décimaux où ils devraient être hexadécimaux: [^\x00-\x1E\x7F\"]