Meine Frage betrifft einerseits die Klassen Applicative und Monad und andererseits die kontextfreien und kontextsensitiven Grammatikebenen der Chomsky-Hierarchie.Korrespondenz zwischen Typklassen und Grammatikstufen in der Chomsky-Hierarchie
Ich habe gehört, dass es eine Übereinstimmung zwischen den Typklassen und den Grammatikebenen gibt. Wie genau ist diese Korrespondenz?
Das heißt, können alle kontextfreien Grammatiken mit nichts stärker als Applicative Kombinatoren geparst werden, und tun alle Grammatiken, die mit nichts stärker als Applicative Kombinatoren kontextfrei geparst werden können? Mit anderen Worten: Entspricht die Klasse des Applicative-Typs genau kontextfreien Grammatiken?
Und die gleiche Frage, außer mit 'kontextfrei' durch 'kontextsensitiv' und Applicative durch Monad ersetzt.
Bounty Klarstellung: Typklasse tun (n) entsprechen Ebenen der Grammatik? Zum Beispiel gibt es eine Reihe von Typklassen, die alle Operationen bieten, die für Ausdruck reguläre Sprachen und nichts mehr benötigt werden?
Die Motivation für die Frage ist, dass ich an einem Parser arbeitete und anhand der von mir verwendeten Kombinatoren feststellen wollte, auf welcher Grammatikebene meine Implementierung war. Ist das möglich?
Ich denke, Ihre Prämisse hier ist unvollständig. 'Applicative' allein wird Sie nicht sehr weit bringen, da Sie Produktionen weder auf der Grundlage von Inputs zurückverfolgen noch auswählen können. Die typische Parser-Kombinator-API stützt sich auf "Alternative" zusammen mit "Applicative". –
@C.A.McCann Ja, das stimmt, danke, dass du das herausgibst. Entspricht 'Alternative' regulären Grammatiken? Ich wollte das hinzufügen, war mir aber nicht sicher, was ich mit der 'Applicative'-Einschränkung machen sollte. Gibt es andere Klassen, die regulären Grammatiken entsprechen? –
Ich bin mir nicht sicher. Ich bin nicht wirklich davon überzeugt, dass die Verbindung hier tiefer geht als die allgemeine Fähigkeit von "Monad", kausale Beziehungen auszudrücken, die "Applicative" nicht kann, weil ich nicht sehe, wie irgendeine Art von natürlicher Einschränkung (dh nicht erfunden zu diesem Zweck) von Parser-Kombinatoren würde die Möglichkeit ergeben, nur weniger expressive Grammatiken zu definieren. –