Nur zur Klarstellung, das sind keine Hausaufgaben. Ich wurde um Hilfe gebeten und bin dazu nicht in der Lage, also wurde es zu einer persönlichen Aufgabe, um es zu lösen.
Stellen Sie sich vor, Sie haben eine Grammatik für einen englischen Satz wie folgt:
%Vor%Ich habe mehrere Stunden gesucht und habe wirklich keine Ideen mehr. Ich habe Artikel gefunden, die über oberflächliches Parsing, Tiefen-Backtracking und ähnliche Dinge sprechen, und obwohl ich mit den meisten davon vertraut bin, kann ich sie immer noch nicht auf dieses Problem anwenden. Ich habe Lisp und Haskell markiert, weil dies die Sprachen sind, in denen ich dies implementieren möchte, aber es macht mir nichts aus, wenn Sie in Ihren Antworten andere Sprachen verwenden.
Ich würde gerne Hinweise, gute Artikel und alles im Allgemeinen schätzen.
Hier ist ein funktionierendes Haskell-Beispiel. Es stellt sich heraus, dass es ein paar Tricks zu lernen gibt, bevor Sie es zum Laufen bringen können! Die nullte Sache zu tun ist boilerplate: Schalte die gefürchtete Monomorphismusbeschränkung ab, importiere einige Bibliotheken und definiere einige Funktionen, die nicht in den Bibliotheken sind (aber sein sollten):
%Vor%Nun, da die nullte Sache erledigt ist ... definieren wir zuerst einen Datentyp für unsere abstrakten Syntaxbäume. Wir können hier einfach der Form der Grammatik folgen. Um es jedoch bequemer zu machen, habe ich ein paar Grammatikregeln berücksichtigt; insbesondere die beiden Regeln
%Vor%sind so bequemer geschrieben, wenn es darum geht, einen Parser tatsächlich zu schreiben:
%Vor%Jedes gute Buch über das Parsen wird ein Kapitel darüber haben, warum diese Art von Faktorisierung eine gute Idee ist. Also, der AST-Typ:
%Vor%Dann können wir unseren Parser machen. Dieser folgt der (faktorisierten) Grammatik noch genauer! Die eine Falte hier ist, dass wir immer wollen, dass unser Parser einen ganzen Satz konsumiert, also müssen wir explizit darum bitten, dass er das tut, indem er ein "eof" - oder ein Ende von "file" verlangt.
%Vor% Das letzte Stück ist der Tokenizer. Für diese einfache Anwendung werden wir nur anhand von Leerzeichen token, so dass die integrierte words -Funktion problemlos funktioniert. Lass es uns ausprobieren! Laden Sie die gesamte Datei in ghci:
Hier zeigt Right eine erfolgreiche Analyse und Left einen Fehler an. Die "column" -Nummer, die in dem Fehler gemeldet wird, ist tatsächlich die Wortnummer, an der der Fehler aufgetreten ist, aufgrund der Art, wie wir Quellpositionen in singleToken berechnen.
Es gibt verschiedene Ansätze für das syntaktische Parsen unter Verwendung einer kontextfreien Grammatik.
Wenn Sie das selbst implementieren möchten, können Sie sich zunächst mit Parsing-Algorithmen vertraut machen: Sie können hier und hier , oder wenn Sie etwas auf Papier bevorzugen, das Kapitel Syntactic Parsing in Jurafsky und Martin könnte ein guter Anfang sein.
Ich weiß, dass es nicht zu schwierig ist, einen einfachen syntaktischen Parser in der Programmiersprache Prolog zu implementieren. Googeln Sie einfach nach 'Prolog Shift Reduce Parser' oder 'Prolog Scan Predict Parser'. Ich kenne Haskell oder Lisp nicht, aber es könnte Ähnlichkeiten mit Prolog geben, also können Sie vielleicht ein paar Ideen von dort bekommen.
Wenn Sie nicht den kompletten Parser selbst implementieren müssen, würde ich mir die Python NLTK ansehen, die Tools für CFG-Parsing bietet. Es gibt ein Kapitel darüber im NLTK-Buch .
Okay, es gibt eine Reihe von Algorithmen, die Sie verwenden könnten. Im Folgenden finden Sie einige beliebte dynamische Programmieralgorithmen: 1) CKY-Algorithmus: Die Grammatik sollte in CNF-Form vorliegen 2) Earley-Algorithmus 3) Diagrammanalyse.
Bitte google, um die Implementierung dieser zu finden. Bei einem gegebenen Satz können Sie mit diesen Algorithmen einen kontextfreien Baum zuweisen.
Sie haben ein Beispiel für nicht propabalistische Grammatik geliefert. Sie können also die Tools ANTLR, JFlex, Scala Parser Combinators, Parsers python library verwenden, um Parser mit dieser Grammatik in sehr ähnlichem Code zu implementieren, den Sie bereitgestellt haben.
Ich denke, das Problem für Sie könnte sein, dass die Art und Weise, wie Sie eine Computersprache parsen, viel anders ist als die natürliche Sprache.
Computersprachen sind so konzipiert, dass sie eindeutig und relativ einfach sind, um die genaue Bedeutung von einem Computer zu erhalten.
Natürliche Sprachen entwickelten sich, um kompakt und ausdrucksstark zu sein und normalerweise von Menschen verstanden zu werden. Sie könnten es schaffen, deterministisches Parsen zu machen, dass Compiler Arbeit für eine sehr einfache Teilmenge der englischen Grammatik verwenden, aber es ist nichts wie das, was verwendet wird, um echte natürliche Sprache zu analysieren.