Qualcuno sa se Python (qualsiasi versione) usasse gli NFA (Automatismi finiti non deterministici) per valutare le espressioni regolari o utilizza qualche altro meccanismo? Fornire collegamenti/riferimenti, se disponibili.Python usa NFA per la valutazione delle espressioni regolari nel modulo re?
Questo dovrebbe richiedere meno di un ms su una DFA:
$ time python3 -c 'import re; re.match("a?"*25+"a"*25, "a"*25)'
real 0m7.273s
Change 25 con 100 e non terminerà per tutta la vita.
Ecco come appare su un DFA (grep):
$ time echo "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" |grep "a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?a\?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
real 0m0.063s
c'è una grande discussione del tema in http://swtch.com/~rsc/regexp/regexp1.html
Dal momento che la maggior parte dei motori di RE al giorno d'oggi consentono di lingue non regolari da abbinare Dubito che qualsiasi motore RE moderno usi ancora NFA o DFAs. – Joey
Bene, dal momento che un motore RE può identificare un sottoinsieme di RE che sono regolari, e quelli sono di uso comune, ha senso ottimizzare per quegli scenari. Quindi è del tutto possibile che a volte utilizzino NFA o DFA. – MSalters