Amélioration et correction d'une expression rationnelle pour les commentaires de blocs de style C

Question

J'écris (en C#) un simple parseur pour traiter un langage de script qui ressemble beaucoup au C classique.

Sur un fichier script que j'ai, l'expression régulière que j'utilise pour reconnaître /* block comments */ entre dans une sorte de boucle infinie, prenant 100% du CPU pendant des lustres.

La Regex que j'utilise est la suivante :

/\*([^*]|[\r\n]|(\*+([^*/]|[\r\n])))*\*+/

Des suggestions sur les raisons de ce blocage ?

Sinon, quelle autre Regex pourrais-je utiliser à la place ?

Plus d'informations :

• Travailler en C# 3.0 en visant .NET 3.5 ;
• J'utilise la méthode Regex.Match(string,int) pour commencer la recherche à un index particulier de la chaîne ;
• J'ai laissé le programme fonctionner pendant plus d'une heure, mais le match n'est pas terminé ;
• Les options transmises au constructeur Regex sont les suivantes RegexOptions.Multiline y RegexOptions.IgnorePatternWhitespace ;
• La regex fonctionne correctement pour 452 de mes 453 fichiers de test.

Answer 1

Je vois quelques problèmes avec votre regex :

Il n'est pas nécessaire que le |[\r\n] dans votre regex ; une classe de caractères annulés comme [^*] correspond à tout sauf à * y compris les séparateurs de lignes. Ce n'est que le . (point) qui ne correspond pas à ces métacaractères.

Une fois que vous êtes dans le commentaire, le seul caractère que vous devez rechercher est un astérisque ; tant que vous n'en voyez pas un, vous pouvez engloutir autant de caractères que vous le souhaitez. Cela signifie qu'il est absurde d'utiliser [^*] alors que vous pouvez utiliser [^*]+ au lieu de cela. En fait, vous pourriez aussi bien mettre cela dans un groupe atomique -- (?>[^*]+) -- parce que vous n'aurez plus aucune raison de renoncer à l'un ou l'autre de ces "nonasterisks" une fois que vous les aurez appariés.

En éliminant les éléments superflus, la dernière alternative à l'intérieur de vos parenthèses extérieures est la suivante \*+[^*/] ce qui signifie "un ou plusieurs astérisques, suivis d'un caractère qui n'est ni un astérisque ni une barre oblique". Cela correspondra toujours à l'astérisque à la fin du commentaire, et il faudra toujours l'abandonner à nouveau parce que le caractère suivant est une barre oblique. En fait, s'il y a vingt astérisques jusqu'à la barre oblique finale, cette partie de votre regex les fera tous correspondre, puis elle les abandonnera tous, un par un. Puis la partie finale \*+/ -- les fera correspondre à ce qu'il faut pour qu'ils soient conservés.

Pour une performance maximale, j'utiliserais cette expression rationnelle :

/\*(?>(?:(?>[^*]+)|\*(?!/))*)\*/

Cela permettra de faire correspondre un commentaire bien formé très rapidement, mais plus important encore, si cela commence à correspondre à quelque chose qui ne correspond pas à la définition du n'est pas un commentaire valide, il échouera le plus rapidement possible.

---

Avec l'aimable autorisation de David Voici une version qui fait correspondre les commentaires imbriqués à n'importe quel niveau d'imbrication :

(?s)/\*(?>/\*(?<LEVEL>)|\*/(?<-LEVEL>)|(?!/\*|\*/).)+(?(LEVEL)(?!))\*/

Il utilise les groupes d'équilibrage de .NET, et ne fonctionnera donc pas dans une autre version. Par souci d'exhaustivité, voici une autre version (issue de la bibliothèque de RegexBuddy) qui utilise la syntaxe des groupes récursifs supportée par Perl, PCRE et Oniguruma/Onigmo :

/\*(?>[^*/]+|\*[^/]|/[^*])*(?>(?R)(?>[^*/]+|\*[^/]|/[^*])*)*\*/

Answer 2

Non, non, non ! Personne d'autre n'a lu Mastering Regular Expressions (3e édition) ? Dans cet ouvrage, Jeffrey Friedl examine précisément ce problème et l'utilise comme exemple (pages 272-276) pour illustrer sa technique de "déroulement de la boucle". Sa solution pour la plupart des moteurs d'expressions régulières est la suivante :

/\*[^*]*\*+(?:[^*/][^*]*\*+)*/

Cependant, si le moteur de regex est optimisé pour gérer les quantificateurs paresseux (comme l'est celui de Perl), l'expression la plus efficace est beaucoup plus simple (comme suggéré ci-dessus) :

/\*.*?\*/

(Avec le modificateur équivalent "s" "le point correspond à tout", bien sûr). Notez que je n'utilise pas .NET et que je ne peux donc pas dire quelle version est la plus rapide pour ce moteur.

Answer 3

Vous pouvez essayer l'option Singleline plutôt que Multiline, vous n'aurez alors pas à vous préoccuper de l'option \r\n. Une fois cette option activée, la procédure suivante a fonctionné pour moi dans le cadre d'un test simple comprenant des commentaires s'étendant sur plus d'une ligne :

/\*.*?\*/

Answer 4

Je pense que votre expression est beaucoup trop compliquée. Appliquées à une grande chaîne de caractères, les nombreuses alternatives impliquent un grand nombre de retours en arrière. Je suppose que c'est la source de la baisse de performance que vous constatez.

Si l'hypothèse de base est de faire correspondre tout ce qui est de l'ordre du "/*" jusqu'à la première "*/" (comme d'habitude, les expressions rationnelles ne sont pas adaptées aux structures imbriquées, de sorte que l'imbrication des commentaires de bloc ne fonctionne pas) :

/\*(.(?!\*/))*.?\*/             // run this in single line (dotall) mode

En substance, cela signifie que "/*" suivi de tout ce qui n'est pas lui-même suivi de "*/" , suivi de "*/" .

Vous pouvez également utiliser la méthode la plus simple :

/\*.*?\*/                       // run this in single line (dotall) mode

Un tel appariement sans recherche a le potentiel de se tromper dans un cas limite - pour l'instant, je ne vois pas de cas où cette expression pourrait échouer, mais je n'en suis pas tout à fait sûr.

Answer 5

J'utilise actuellement ceci

\/\*[\s\S]*?\*\/