1. casa
  2. Domanda e risposta
  3. Analisi dei casi peggiori per le espressioni regolari

Analisi dei casi peggiori per le espressioni regolari

2011-01-19 6 views
48

Esistono strumenti che richiedono una particolare espressione regolare e restituiscono lo scenario peggiore in termini di numero di operazioni richieste per un determinato numero di caratteri con cui viene confrontata l'espressione regolare?Analisi dei casi peggiori per le espressioni regolari

Quindi, ad esempio, dato un (f|a)oo.*[ ]baz, quanti passaggi potrebbero passare il motore attraverso i 100 caratteri?

Sarei anche interessato se c'è uno strumento che può richiedere un mucchio di campioni di testo e mostrare le operazioni medie per ciascuna analisi.

Mi rendo conto che questo dipenderà molto dal motore utilizzato e dall'implementazione, ma sono ignorante su quanto sia comune. Quindi, se è comune a molte lingue (rendendo la mia domanda troppo vaga) sarei particolarmente interessato a Perl e Python.

fonte

2011-01-19 Kyle Brandt

+0

Ottima domanda! Ovviamente dipenderà dalla regex. È risaputo che le regex pure (anche come l'esempio '(x + x +) + y 'di cui sotto) ammettono un automa di macchina allo stato finito puro, ma che le normali librerie regex implementano effettivamente quelle con backtracking, in gran parte per supportare l'immaginazione roba come il contesto. Uno strumento come quello che descriveresti sarebbe bello da cogliere http://en.wikipedia.org/wiki/Regular_expression_Denial_of_Service_-_ReDoS –

risposta

22

Regexbuddy's debugger indica quanti passaggi il motore impiegherebbe per concludere la corrispondenza o meno su un dato campione. Maggiori informazioni su catastrophic backtracking e debugging regular expressions.

catastrophic backtracking shown in RegexBuddy

PS: E non è libero, ma offrono una garanzia di rimborso 3 mesi.

fonte

2011-01-19 02:35:22 Himanshu

+1

Stavo giocando con quello - Jeff è stato un fan di esso: http://www.codinghorror.com /blog/2004/07/my-buddy-regex.html. Ma stavo pensando un po 'più programmatico e orientato all'ottimizzazione - se questo ha senso. –

11

Si noti che dipende dal motore . Mentre la teoria delle regex si basa sulla teoria degli automi, la maggior parte dei motori non sono traduzioni rigorose di quelle teorie. Per questo motivo, ad esempio, alcuni motori sono soggetti a tempi esponenziali mentre l'elaborazione NFA non lo è.

fonte

2011-07-08 23:20:00

 Problemi correlati

  • Nessun problema correlato^_^