Ich habe eine Aufgabe, einen (Spielzeug-) Parser für eine (Spielzeug-) Grammatik mit OCaml zu schreiben und bin mir nicht sicher, wie ich dieses Problem lösen (und fortfahren) kann.
Hier ist eine Beispiel-Awk-Grammatik:
%Vor%Und hier sind ein paar Fragmente zum parsen:
%Vor%Was ich suche, ist eine Regelliste, die das Ergebnis der Analyse eines Fragments ist, wie dieses für frag1 ["4"; "+"; "3"]:
%Vor%Die Einschränkung besteht darin, keine anderen OCaml-Bibliotheken als List ...: /
zu verwenden Ok, also denken Sie zuerst, Sie sollten einen lexikalischen Analysator schreiben. Das ist das
Funktion, die den 'rohen' Input übernimmt, wie ["3"; "-"; "("; "4"; "+"; "2"; ")"] ,
und teilt es in eine Liste von Tokens auf (dh Darstellungen von Terminalsymbolen).
Sie können ein Token als
definieren %Vor% Der Typ der Funktion lexer wäre string list -> token list und der Ausgang von
wäre etwas wie
%Vor%Dies erleichtert Ihnen das Schreiben des Parsers, weil Sie dies nicht tun müssen Sorgen Sie sich darum, was eine Ganzzahl ist, was ein Operator ist, usw.
Dies ist ein erster, nicht zu schwieriger Schritt, da die Token bereits getrennt sind. Der Lexer muss sie nur identifizieren.
Wenn Sie damit fertig sind, können Sie einen realistischeren lexikalischen Analysator vom Typ string -> token list schreiben, der eine tatsächliche rohe Eingabe wie "3-(4+2)" benötigt und diese in eine Token-Liste verwandelt.
Ich bin mir nicht sicher, ob Sie den Ableitungsbaum speziell benötigen oder ob dies nur ein erster Schritt beim Parsen ist. Ich nehme das letztere an.
Sie könnten damit beginnen, die Struktur des resultierenden abstrakten Syntaxbaums zu definieren, indem Sie Typen definieren. Es könnte so etwas sein:
%Vor% Dann würde ich einen rekursiven Descent-Parser implementieren. Natürlich wäre es viel schöner, wenn Sie streams kombiniert mit dem Präprozessor camlp4of ...
Übrigens gibt es ein kleines Beispiel für arithmetische Ausdrücke in der OCaml-Dokumentation hier .