Che tipo di linguaggi formali possono analizzare i motori regex moderni?

Question

Qui su SO le persone a volte dicono qualcosa come "non puoi analizzare X con espressioni regolari, perché X non è un linguaggio normale". Tuttavia, dalla mia comprensione, i moderni motori di espressioni regolari possono corrispondere a più di semplici lingue in Chomsky's sense. Le mie domande:

dato un motore di espressioni regolari che supporta

• backreference
• affermazioni Lookaround di larghezza illimitata
• ricorsione, come (?R)

che tipo di lingue può esso analizzare? Può analizzare qualsiasi linguaggio privo di contesto e, in caso contrario, quale sarebbe il controesempio?

(Per essere precisi, con "parse" intendo "creare una singola espressione regolare che accetta tutte le stringhe generate dalla grammatica X e rifiuta tutte le altre stringhe").

Aggiungi: Sono particolarmente interessato a vedere un esempio di un linguaggio privo di contesto che i moduli regex moderni (Perl, Net, modulo regex di Python) non sarebbero in grado di analizzare.

Answer 1

Recentemente ho scritto un tempo piuttosto lungo articolo su questo argomento : The true power of regular expressions.

In sintesi:

• espressioni regolari con il supporto per i riferimenti sotto-regola ricorsivi può corrispondere tutte linguaggi context-free (per esempio a^n b^n).
• espressioni regolari con affermazioni Lookaround e riferimenti sotto-regola può corrispondere almeno alcune lingue sensibile al contesto (ad esempio ww e a^n b^n c^n).
• Se le asserzioni hanno larghezza illimitata (come dici tu), poi tutti grammatiche sensibili al contesto può essere abbinato. Non conosco alcun sapore regex anche se questo non ha limitazioni a larghezza fissa su lookbehind (e allo stesso tempo supporta i riferimenti sotto-regola).
• Le espressioni regolari con i riferimenti secondari sono completate NP, quindi qualsiasi altro problema NP può essere risolto utilizzando le espressioni regolari (dopo l'applicazione di una trasformazione del tempo polinomiale).

Alcuni esempi:

• Adattamento del linguaggio context-free {a^n b^n, n>0}:

  /^(a(?1)?b)$/ 
  # or 
  /^ (?: a (?= a* (\1?+ b)))+ \1 $/x 
  

• corrispondenza della lingua sensibile al contesto {a^n b^n c^n, n>0}:

  /^ 
      (?=(a(?-1)?b)c) 
      a+(b(?-1)?c) 
  $/x 
  # or 
  /^ (?: a (?= a* (\1?+ b) b* (\2?+ c)))+ \1 \2 $/x 
  

Answer 2

I motori regex moderni possono sicuramente analizzare un insieme più grande di lingue rispetto alle normali lingue impostate. Così detto, nessuno dei quattro classici set di Chomsky è esattamente riconosciuto dalle regex. Tutte le lingue regolari sono chiaramente riconosciute dalle regex. Esistono alcuni classici linguaggi context-free che non possono essere riconosciuti dalle espressioni regolari, ad esempio la lingua parentesi bilanciata a^n b^n, a meno che non siano disponibili back-referenze con conteggio. Tuttavia, un'espressione regolare può analizzare la lingua ww che è sensibile al contesto.

In realtà, le espressioni regolari nella teoria del linguaggio formale sono solo leggermente correlate alle regex. Il regex di corrispondenza con backreference illimitato è NP-Complete nel caso più generale, quindi tutti gli algoritmi di pattern matching per regex sufficientemente potenti sono esponenziali, almeno nel caso generale. Tuttavia la maggior parte delle volte per la maggior parte degli input sono abbastanza veloci. È noto che l'abbinamento di lingue senza contesto è al massimo qualcosa più veloce di n^3, quindi ci sono alcune lingue in espressioni regolari che non sono context-free (come ww) ma non tutte le lingue context-free possono essere analizzate dalle espressioni regolari. Le lingue di tipo 0 non sono decidibili in generale, le regex del figlio non arrivano lì.

Quindi, come conclusione non molto conclusiva, le regex possono analizzare un ampio set di linguaggi che includono tutti i linguaggi regolari e alcuni context-free e context-sensitive, ma non è esattamente uguale a nessuno di questi set. Esistono altre categorie di linguaggi e altre tassonomie in cui è possibile trovare una risposta più precisa, ma nessuna tassonomia che includa linguaggi privi di contesto come sottoinsieme appropriato in una gerarchia di lingue può fornire una singola lingua esattamente riconosciuta dalle espressioni regex, poiché le espressioni regolari solo intersecare in qualche parte con i linguaggi context-free, e nessuno dei due è un sottoinsieme appropriato dell'altro.

Answer 3

Si può leggere su espressioni regolari in An Introduction to Language And Linguistics By Ralph W. Fasold, Jeff Connor-Linton P.477

Chomsky Gerarchia:

Type0> = Type1> = Tipo2> = Tipo3

Linguistica Computazionale dispone principalmente di tipo 2 & 3 Grammatiche

• tipo 3 grammatiche:

-include espressioni regolari e automi a stati finiti (aka, macchine a stati finiti)

-Il punto focale di tutto il resto di questo discorso

• tipo 2 grammatiche:

- Utilizzato comunemente per parser di linguaggio naturale

-Utilizzato per modellare la struttura sintattica in molti teorici linguistici i (spesso integrati da altri meccanismi)

-Abbiamo giocherà un ruolo chiave nel prossimo discorso sul parsing.

---

maggior parte XMLs come Microsoft DGML (Directed Graph Markup Language) che ha collegamenti inter-relazionali sono campioni che Regex sono inutili.

---

e questo tre risposte potrebbero essere utili:

1 - does-lookaround-affect-which-languages-can-be-matched-by-regular-expressions

2 - regular-expressions-arent

3 - where-do-most-regex-implementations-fall-on-the-complexity-scale