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?La "regex" nei linguaggi di programmazione moderni è davvero "grammatica sensibile al contesto"?
risposta
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.
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
-
Tuttemaggior 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).
Lookahead/lookbehind e naming aggiungono sicuramente qualcosa che si trova al di fuori delle espressioni regolari standard - la memoria. Quindi non siamo a livello di PDA? – notnot
In generale non è vero che il linguaggio naturale è sensibile al contesto, vedi http://www.eecs.harvard.edu/~shieber/Biblio/Papers/shieber85.pdf –
ah, questa è la roba buona – notnot
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.
So che va oltre la regex classica, ma mi chiedo quanto più lontano. Il link di Fabian sopra è interessante. – notnot
- 1. Le grammatiche dei linguaggi di programmazione moderni sono prive di contesto o sensibili al contesto?
- 2. Endianness nei linguaggi di programmazione
- 3. Problemi culturali nei linguaggi di programmazione
- 4. Frequenza dei simboli nei linguaggi di programmazione
- 5. Che tipo di linguaggi formali possono analizzare i motori regex moderni?
- 6. Covarianza e controvarianza nei linguaggi di programmazione
- 7. Automobili Linguaggi di programmazione
- 8. Hashing sensibile al contesto con Min Hash
- 9. HTML5 Canvas - Menu sensibile al contesto
- 10. Linguaggi di programmazione SIMD
- 11. Ruolo dei combinatori nei linguaggi di programmazione concatenativo/tacit
- 12. Algoritmo per generare una grammatica senza contesto da qualsiasi regex
- 13. matematiche Linguaggi di programmazione
- 14. Ridenominazione degli oggetti in RStudio sensibile al contesto nell'intero progetto
- 15. La programmazione orientata agli oggetti nei linguaggi interpretati (ad esempio, PHP) è efficiente?
- 16. Quanto è rilevante la programmazione Win32 per i professionisti moderni?
- 17. Che cos'è un elenco di linguaggi di programmazione al curry?
- 18. Linguaggi di programmazione funzionale introspezione
- 19. I linguaggi di programmazione con evidenziazione della sintassi sono possibili utilizzando le espressioni regolari?
- 20. Qual è il significato del concetto di serializzazione nei linguaggi di programmazione?
- 21. Segmentazione della memoria nei moderni sistemi operativi
- 22. JSON Hijacking è ancora un problema nei browser moderni?
- 23. Qual è la differenza tra grammatica lessicale e grammatica sintattica?
- 24. Convergenza di linguaggi matematici e di programmazione
- 25. XML è sensibile al maiuscolo/minuscolo?
- 26. Java è sensibile al maiuscolo/minuscolo?
- 27. La codifica percentuale dell'URL è sensibile al maiuscolo/minuscolo?
- 28. La gestione delle parentesi graffe in regex javascript è la stessa in tutti i browser moderni?
- 29. Dove posso trovare una grammatica formale per il linguaggio di programmazione Perl?
- 30. Linguaggi di programmazione che definiscono il problema anziché la soluzione?
Potrebbe spiegare la differenza tra "linguaggio normale" e "espressione regolare"? –
È davvero più potente di CSG? Potresti fare un esempio? – notnot
Una lingua normale può essere descritta da una grammatica regolare (vedere http://en.wikipedia.org/wiki/Regular_grammar), mentre le espressioni regolari sono un linguaggio di abbinamento di modelli meno ristretto e quindi più complesso da elaborare. –