Mi sono divertito ultimamente ad esplorare lo sviluppo dei parser di lingua nel contesto di come si inseriscono nella gerarchia di Chomsky.
Che cos'è un buon esempio del mondo reale (cioè non teorico) di una grammatica sensibile al contesto?
Mi sono divertito ultimamente ad esplorare lo sviluppo dei parser di lingua nel contesto di come si inseriscono nella gerarchia di Chomsky.
Che cos'è un buon esempio del mondo reale (cioè non teorico) di una grammatica sensibile al contesto?
Buona domanda. Sebbene come menzionato nei commenti molti linguaggi di programmazione siano sensibili al contesto, la sensibilità al contesto spesso non viene risolta nella fase di analisi ma in fasi successive, ovvero un superset della lingua viene analizzato utilizzando una grammatica context-free, e alcuni di questi alberi di analisi vengono successivamente filtrati.
Tuttavia, ciò non significa che quelle lingue non siano sensibili al contesto , quindi ecco alcuni esempi:
Haskell consente di definire le funzioni utilizzate come operatori e di definire anche la precedenza e l'associatività di tali operatori. In altre parole, non è possibile creare l'albero di analisi corretto per un'espressione di operatore come:
a @@ b @@ c ## d ## e
a meno che tu abbia già analizzato le dichiarazioni di precedenza / associatività per @@ e ## :
infixr 8 @@
infixr 6 ##
Un secondo esempio è Bencode , un linguaggio dati che prefigura il contenuto con la sua lunghezza:
<length>:<contents>
Il problema con questo formato è che è praticamente impossibile analizzare senza qualcosa di sensibile al contesto, perché l'unico modo per capire le dimensioni del "campo" è ... analizzare la stringa.
Un terzo esempio è XML, assumendo che siano consentiti nomi di tag arbitrari: i nomi di tag aperti devono avere tag di chiusura corrispondenti:
<hi>
<bye>
the closing tag has to match bye
</bye>
</hi> <!-- has to match "hi" -->
Finché so, le grammatiche sensibili al contesto sono usate nell'elaborazione del linguaggio naturale, solo . Gli interpreti ei compilatori dei linguaggi di programmazione non tentano di analizzare una grammatica senza contesto a causa della complessità (anche se alcuni tentativi sono stati fatti in passato).
Forse, puoi trovare qualche esempio di reale utilizzo in una di queste librerie:
Le grammatiche sensibili al contesto sono talvolta utilizzate nelle descrizioni della semantica del linguaggio di programmazione. Forse l'uso più completo di grammatiche sensibili al contesto era la definizione della lingua Algol68. Ha usato un grammofono free-level a due livelli (vedi link ) per descrivere sia la sintassi che la semantica dei programmi Algol68.
Un paio di miei colleghi hanno usato la grammatica di van Wijngaarden per dirigere la loro implementazione di Algol68 (vedi link ).
Leggi altre domande sui tag language-design grammar parsing