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

Question

Nel corso degli anni, il pattern matching "regex" è diventato sempre più potente fino al punto in cui mi chiedo: è davvero solo la corrispondenza grammaticale sensibile al contesto? È una variazione/estensione della corrispondenza grammatica libera dal contesto? Dov'è adesso e perché non lo chiamiamo semplicemente al posto della vecchia "espressione regolare" restrittiva?

Answer 1

In particolare i riferimenti secondari per l'acquisizione di parentesi rendono le espressioni regolari più complesse rispetto alle grammatiche regolari, contestuali o sensibili al contesto. Il nome è semplicemente storicamente cresciuto (come molte parole). Vedi anche this section in Wikipedia e questo explanation with an example da Perl.

Answer 2

Il mio modo di vedere:

• linguaggi regolari:
  • di pari passo con macchine a stati. Solo una variabile può essere usato per rappresentare l'attuale "location" nella grammatica da abbinare: ricorsione non può essere attuato
• context-free lingue:
  • Abbinato da una macchina stack. L'attuale "posizione" nella grammatica è rappresentata da una pila in una o in un'altra forma. Non può "ricordare" tutto ciò che si è verificato prima
• sensibili al contesto lingue:
  • maggior parte dei linguaggi di programmazione
  • Tutte maggior parte dei linguaggi umani

so di regolare parser di espressioni che ti permettono di confrontare con qualcosa che il parser ha già incontrato, ottenendo qualcosa come un contesto grammatica intuitiva.

Ancora, i parser di espressioni regolari, per quanto sofisticati possano essere, non consentono un'applicazione ricorsiva delle regole, che è un requisito preciso per le grammatiche context-free.

Il termine regex, a mio parere, si riferisce principalmente al sintassi utilizzato per esprimere quelle grammatiche regolari (le stelle e punti interrogativi).

Answer 3

Ci sono funzionalità nelle moderne implementazioni di espressioni regolari che infrangono le regole dello classic regular expression definition.

Per esempio Microsoft’s .NET Balancing Group(?<name1-name2> …):

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

Questo fa corrisponde alla lingua L ₀₁ = {ε, 01, 0011, 000111, ...}. Ma questa lingua non è regolare secondo lo Pumping Lemma.