Espressività del linguaggio formale dei pattern Perl

Question

Le espressioni regolari classiche sono equivalenti agli automi finiti. La maggior parte delle attuali implementazioni di "espressioni regolari" non sono espressioni regolari, ma sono più potenti. Alcune persone hanno iniziato a usare il termine "modello" piuttosto che "espressione regolare" per essere più precisi.

Qual è la classificazione del linguaggio formale di ciò che può essere descritto con una moderna "espressione regolare", come i modelli supportati in Perl 5?

Aggiornamento: Con "Perl 5" intendo la funzionalità di corrispondenza del modello implementata in Perl 5 e adottata da numerosi altri linguaggi (C#, JavaScript, ecc.) E non qualcosa di specifico per Perl. Non voglio prendere in considerazione, ad esempio, trucchi per incorporare il codice Perl in un pattern.

Answer 1

C'è stata una recente discussione su questo argomento un PerlMonks: Turing completeness and regular expressions

Answer 2

Ho sempre sentito l'implementazione di regex di Perl descritta come un NFA con backtracking. Wikipedia sembra avere una piccola sezione su questo:

Questo è forse un po 'troppo confusa ma è non informativo meno:

From Wikipedia:

Ci sono almeno tre diversi algoritmi che decidono se e il modo in cui un'espressione regolare con corrisponde a una stringa .

Il più antico e più veloce due si basano su un risultato nella teoria dei linguaggi formali che permette ogni deterministico finiti macchina a stati (NFA) per essere trasformato in un stati finiti macchina deterministica (DFA). Il DFA può essere costruito in modo esplicito e quindi eseguito su la stringa di input risultante un simbolo alla volta. La creazione del DFA per un'espressione regolare di dimensione m ha il tempo di memoria di O (2m), ma è possibile eseguire su una stringa di dimensione n in tempo O (n). Un approccio alternativo è per simulare direttamente l'NFA, essenzialmente la creazione di ogni stato DFA sulla richiesta e quindi scartarla nel passaggio successivo , possibilmente con la memorizzazione nella cache. Questo mantiene implicito il DFA ed evita il costo di costruzione esponenziale , ma l'aumento dei costi di esercizio di su O (nm). L'approccio esplicito è chiamato l'algoritmo DFA e l'approccio implicito dell'algoritmo NFA. Poiché entrambi possono essere visti come stesso DFA, si possono anche chiamare l'algoritmo DFA senza fare una distinzione . Questi algoritmi sono veloci, ma usarli per richiamare sottoespressioni raggruppate , quantificazione lenta e caratteristiche simili è difficile. [12] [13]

Il terzo algoritmo consiste nel far corrispondere il pattern alla stringa di input con il backtracking . Questo algoritmo è comunemente chiamato NFA, ma questa terminologia può essere fonte di confusione.La sua tempo di esecuzione può essere esponenziale, che semplici implementazioni mostra quando di corrispondenza contro espressioni come (a | aa) * b che contengono sia alternanza e quantificazione illimitata e forza l'algoritmo di considerare un esponenziale crescente numero di sub -I casi. Le implementazioni più complesse di identificano spesso e accelerano o annullano i casi comuni dove altrimenti verrebbero eseguiti lentamente.

Sebbene backtracking implementazioni danno solo una garanzia esponenziale peggiore dei casi, essi forniscono molto maggiore flessibilità ed espressivo potenza. Ad esempio, qualsiasi implementazione che consente l'utilizzo dei backreferences o implementa le estensioni introdotte da Perl, deve utilizzare un'implementazione di backtracking.

Alcune implementazioni cercano di fornire il meglio dei due algoritmi per primo l'esecuzione di una partita veloce DFA per vedere se la stringa corrisponde all'espressione regolare a tutti, e solo in questo caso eseguono un potenzialmente più lento backtracking partita .

Answer 3

Perl regexps, come quelli di qualsiasi linguaggio di pattern, in cui "backreferences" sono consentiti, non sono in realtà "regolari".

Backreferences è il meccanismo di corrispondente alla stessa stringa abbinata a una sotto-sequenza prima dello. Ad esempio, /^(a*)\1$/ corrisponde solo stringhe con numero pari di a s, perché dopo alcuni a s dovrebbe seguire lo stesso numero di quelli.

È facile dimostrare che, ad esempio, il modello /^((a|b)*)\1$/ corrisponde a parole di un linguaggio non regolare (*), quindi è più espressivo che l'automa finito. Le espressioni regolari non possono "ricordare" una stringa di lunghezza arbitraria e poi ricollegarla (la lunghezza può essere molto lunga, mentre la macchina a stati finiti può solo simulare una quantità finita di "memoria").

Una prova formale userebbe il pumping lemma. (A proposito, questa lingua non può essere descritta da una grammatica senza contesto.)

Per non parlare dello tricks that allow to use perl code in perl regexps (lingua non regolare delle parentesi bilanciate lì).

---

(*) "Lingue normali" sono insiemi di parole che sono abbinate ad automi finiti. Ho già scritto an answer a riguardo.