Regex backtracking su pattern semplice

2

Ho questo codice in Mathematica che recupera il lato destro o sinistro di un'equazione trasformandolo in testo puro e poi liberando l'altro lato del testo tramite regex. Ho isolato il modello difettoso e non riesco a capire perché stia producendo un backtracking "infinito":

(\S+\s*)+(==|>=|<=|>|<)\s*

testo di esempio:

x <= func[abcde,1]

Ho quasi pensato che fosse a causa delle parentesi che descrivevano alcuni set di caratteri strani e indesiderati, ma qualsiasi carattere sostituivo con le parentesi:

x <= func:abcde,1:

Ritorna ancora all'infinito. L'unica via d'uscita è se "abcde" viene abbreviato in soli 4 caratteri "bcde", "abcd", "cbde" ...

Non capisco. Cos'altro è tornare indietro? <= corrisponde e praticamente risolve tutto a quel punto ...

    
posta Dehbop 02.08.2015 - 12:05
fonte

1 risposta

1

Con l'avvertenza che il comportamento può variare a seconda del motore regex (che stai usando?), un pensiero:

(\S+\s*)+ (la prima metà) corrisponde anche alle stringhe corrispondenti a (==|>=|<=|>|<)\s* (la seconda metà). La corrispondenza è ingorda per impostazione predefinita, quindi la prima metà ingoierà l'operatore, quindi la seconda metà fallirà, quindi inizierà il backtracking. Se puoi utilizzare una corrispondenza non avara o stringere \S per escludere gli operatori, le cose dovrebbero funzionare in modo più affidabile.

Per quanto riguarda i cinque contro quattro personaggi, non lo so, ma penso che abbia a che fare con il modo in cui il tuo motore regex costruisce o ottimizza i suoi automi.

    
risposta data 02.08.2015 - 12:36
fonte

Leggi altre domande sui tag