détermine si l'expression régulière correspond uniquement aux chaînes de longueur fixe

Question

Existe-t-il un moyen de déterminer si l'expression régulière correspond uniquement aux chaînes de longueur fixe? Mon idée serait de scanner *, + et? Ensuite, une logique intelligente serait nécessaire pour rechercher {m, n} où m! = N. Il n'est pas nécessaire de prendre le | l'opérateur en compte.
Petit exemple:^\ d {4} est de longueur fixe;^\ d {4,5} ou^\ d + sont de longueur variable

J'utilise PCRE.

Merci.

Paul Praet

Answer 1

Eh bien, vous pouvez utiliser le fait que le moteur de regex de Python ne permet que des expressions régulières de longueur fixe dans les assertions arrières:

import re 
regexes = [r".x{2}(abc|def)", # fixed 
      r"a|bc",   # variable/finite 
      r"(.)\1",   # fixed 
      r".{0,3}",   # variable/finite 
      r".*"]    # variable/infinite 

for regex in regexes: 
    try: 
     r = re.compile("(?<=" + regex + ")") 
    except: 
     print("Not fixed length: {}".format(regex)) 
    else: 
     print("Fixed length: {}".format(regex)) 

volonté sortie

Fixed length: .x{2}(abc|def) 
Not fixed length: a|bc 
Fixed length: (.)\1 
Not fixed length: .{0,3} 
Not fixed length: .* 

Je suppose que l'expression rationnelle elle-même est valide.

Maintenant, comment Python sait-il si l'expression régulière est de longueur fixe ou non? Il suffit de lire la source - dans sre_parse.py, il existe une méthode appelée getwidth() qui retourne un tuple composé de la longueur la plus basse et la plus longue possible, et si celles-ci ne sont pas égales dans une assertion lookbehind, re.compile() déclenchera une erreur. Le procédé getwidth() guide à travers l'expression rationnelle récursive:

def getwidth(self): 
    # determine the width (min, max) for this subpattern 
    if self.width: 
     return self.width 
    lo = hi = 0 
    UNITCODES = (ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY) 
    REPEATCODES = (MIN_REPEAT, MAX_REPEAT) 
    for op, av in self.data: 
     if op is BRANCH: 
      i = sys.maxsize 
      j = 0 
      for av in av[1]: 
       l, h = av.getwidth() 
       i = min(i, l) 
       j = max(j, h) 
      lo = lo + i 
      hi = hi + j 
     elif op is CALL: 
      i, j = av.getwidth() 
      lo = lo + i 
      hi = hi + j 
     elif op is SUBPATTERN: 
      i, j = av[1].getwidth() 
      lo = lo + i 
      hi = hi + j 
     elif op in REPEATCODES: 
      i, j = av[2].getwidth() 
      lo = lo + int(i) * av[0] 
      hi = hi + int(j) * av[1] 
     elif op in UNITCODES: 
      lo = lo + 1 
      hi = hi + 1 
     elif op == SUCCESS: 
      break 
    self.width = int(min(lo, sys.maxsize)), int(min(hi, sys.maxsize)) 
    return self.width 

Answer 2

Selon regular-expressions.info, le moteur PCRE ne supporte que regexes de longueur fixe et à l'intérieur de l'alternance assertions arrières. Donc, si vous avez une regex valide, entourez-la avec (?<= et ) et voyez si elle compile encore. Vous savez alors qu'il s'agit d'une taille fixe ou d'une alternance de regex de taille fixe.

Je ne suis pas sûr de quelque chose comme a(b|cd)e - ce n'est certainement pas de taille fixe, mais il pourrait encore compiler. Vous devez l'essayer (je n'ai pas installé C/PCRE).

Answer 3

Juste pour le plaisir.

En supposant que le regex nous testons contre le soutien que +, *, ?, {m,n}, {n} et [...] (sauf une syntaxe bizarre comme []] et [^]]). Ensuite, la regex est longueur fixe que si elle suit la grammaire:

REGEX  -> ELEMENT * 
ELEMENT -> CHARACTER ('{' (\d+) (',' \1)? '}')? 
CHARACTER -> [^+*?\\\[] | '\\' . | '[' ('\\' . | [^\\\]])+ ']' 

qui peut être réécrite en PCRE comme:

^(?:(?:[^+*?\\\[{]|\\.|\[(?:\\.|[^\\\]])+\])(?:\{(\d+)(?:,\1)?\})?)*$