La mia domanda riguarda le classi di tipo applicativo e Monade, da un lato, e le e sensibile al contesto context-free livelli grammaticali della gerarchia di Chomsky, dall'altro.Corrispondenza tra le classi di tipo ei livelli di grammatica nella gerarchia di Chomsky
Ho sentito dire che ci sia una corrispondenza tra le classi di tipo ei livelli di grammatica. Quanto è esatta questa corrispondenza?
Cioè, tutte le grammatiche context-free possono essere analizzate utilizzando niente di più forte dei combinatori Applicativi e tutte le grammatiche possono essere analizzate utilizzando niente di più forte dei combinatori Applicativi senza contesto? In altre parole, la classe di tipo Applicativo corrisponde esattamente a grammatiche senza contesto?
E la stessa domanda, se non con 'al contesto libero' sostituito da 'sensibile al contesto' e applicativo per Monade.
Bounty precisazione: fare classe del tipo (es) corrispondono alla grammatica livelli? Ad esempio, esiste un set di classi di tipi che forniscono tutte le operazioni richieste per le lingue regolari delle espressioni e niente di più?
La motivazione per la questione è che stavo lavorando a un parser, e ha voluto determinare quale livello di grammatica mia implementazione era basata sulle combinatori che ho usato. È possibile?
Penso che il tuo premessa è incompleta. 'Applicativo' da solo non ti porterà molto lontano, poiché non puoi né tornare indietro né selezionare produzioni basate sull'input. L'API del combinatore di parser tipico si basa su 'Alternative' insieme a' Applicative'. –
@ C.A.McCann sì, è vero, grazie per averlo indicato. 'Alternative' corrisponde alle grammatiche regolari? Volevo aggiungere questo, ma non ero sicuro di cosa fare con il vincolo 'Applicativo'. Esistono altre classi di tipi che corrispondono a grammatiche regolari? –
Non ne sono sicuro. Non sono in realtà convinto che la connessione qui sia più profonda della capacità generale di 'Monad' di esprimere relazioni causali che non possono essere 'Applicative', perché non vedo come alcun tipo di restrizione naturale (cioè, non forzata a questo scopo) di combinatori di parser risulterebbe nella capacità di definire solo grammatiche meno espressive. –