"Regex" nei moderni linguaggi di programmazione è davvero "grammatica sensibile al contesto"?

Question

Nel corso degli anni, "regex" la corrispondenza dei modelli sta diventando sempre più potente al punto in cui mi chiedo: è davvero solo una corrispondenza grammaticale sensibile al contesto? È una variazione / estensione della corrispondenza grammaticale senza contesto? Dov'è adesso e perché non lo chiamiamo semplicemente così invece della vecchia, restrittiva "espressione regolare"?

Answer 1

In particolare i riferimenti alle catture tra parentesi rendono le espressioni regolari più complesse delle grammatiche regolari, senza contesto o sensibili al contesto. Il nome è semplicemente cresciuto storicamente (come molte parole). Vedi anche questa sezione in Wikipedia e questa spiegazione con un esempio da Perl.

Answer 2

Per come la vedo io:

• Lingue regolari:
  • Corrisponde a macchine a stati. È possibile utilizzare solo una variabile per rappresentare la corrente & Quot; posizione " nella grammatica da abbinare: la ricorsione non può essere implementata
• Lingue senza contesto:
  • Corrisponde a una macchina stack. La posizione corrente "quotata" nella grammatica è rappresentato da una pila in una o in un'altra forma. Impossibile "ricordare" tutto ciò che è accaduto prima
• Lingue sensibili al contesto:
  • La maggior parte dei linguaggi di programmazione
  • Tutte La maggior parte delle lingue umane

Conosco parser di espressioni regolari che ti permettono di confrontarti con qualcosa che il parser ha già incontrato, ottenendo qualcosa come una grammatica sensibile al contesto.

Tuttavia, i parser di espressioni regolari, per quanto sofisticati possano essere, non consentono l'applicazione ricorsiva delle regole, che è un requisito definito per le grammatiche libere dal contesto.

Il termine regex , a mio avviso, si riferisce principalmente alla sintassi utilizzata per esprimere quelle grammatiche regolari (le stelle e i punti interrogativi).

Answer 3

Esistono funzionalità nelle moderne implementazioni delle espressioni regolari che infrangono le regole della espressione regolare classica definizione .

Ad esempio Microsoft & # 8217; s .NET Balancing Group < ? code> (< nome1 - nome2 > & # 8230;) :

^(?:0(?<L>)|1(?<-L>))*(?(L)(?!))$

Questo corrisponde alla lingua L & # 8320; & # 8321; = { & # 949; , 01, 0011, 000111, & # 8230; }. Ma questa lingua non è regolare secondo il Pumping Lemma .