Moje pytanie dotyczy z jednej strony klas typu Applicative i Monad, az drugiej bezkontekstowej i kontekstowej gramatyki hierarchii Chomsky'ego.Korespondencja między klasami typów a poziomami gramatyki w hierarchii Chomsky'ego
Słyszałem, że istnieje powiązanie między klasami typów i poziomami gramatyki. Jak dokładna jest ta korespondencja?
Czy wszystkie gramatyki bezkontekstowe można analizować za pomocą niczego silniejszego niż kombinatoryka aplika- cyjna, i czy wszystkie gramatyki można analizować za pomocą niczego silniejszego niż kombinatoryki aplikacyjne bez kontekstu? Innymi słowy, czy klasa typu Applicative dokładnie odpowiada gramatykom bezkontekstowym?
To samo pytanie, z wyjątkiem "bezkontekstowy" zastąpiony przez "kontekstowy" i "Wnioskujący" przez Monad.
Bounty wyjaśnienie: zrobić klasę typ (y) odpowiadają gramatyki poziomów? Na przykład: jest zestaw klas typów, które zapewniają wszystkie operacje wymagane do wyrażania zwykłych języków i nic więcej?
Motywacją dla tego pytania jest to, że pracowałem nad parserem i chciałem ustalić, na którym poziomie gramatyki moja implementacja była oparta na kombinatorach, których użyłem. czy to możliwe?
Myślę, że twoje przesłanie tutaj jest niekompletne. Sam "Applicative" nie da ci bardzo daleko, ponieważ nie możesz ani cofać, ani wybierać produkcji na podstawie danych wejściowych. Typowy interfejs API parsera opiera się na 'Alternative' oraz' Applicative'. –
@ C.A.McCann tak, to prawda, dziękuję za wskazanie tego. Czy 'Alternatywa' odpowiada regularnym gramatykom? Chciałem to dodać, ale nie byłem pewien, co zrobić z ograniczeniem "Applicative". Czy są jakieś inne klasy (klasy), które odpowiadają regularnym gramatykom? –
Nie jestem pewien. Nie jestem tak naprawdę przekonany, że związek tutaj idzie głębiej niż ogólna zdolność "Monada" do wyrażania związków przyczynowych, których "Wnioskodawca" nie może, ponieważ nie widzę, jak jakiekolwiek naturalne ograniczenie (tj. Nie jest spreparowane w tym celu) kombinatorów parsera dałoby możliwość definiowania tylko mniej ekspresyjnych gramatyk. –