Ich habe die Aufgabe, mit OCaml einen (Spielzeug-) Parser für eine (Spielzeug-) Grammatik zu schreiben, und bin mir nicht sicher, wie ich dieses Problem starten soll (und wie ich damit fortfahren soll).

Hier ist eine Beispiel-Awk-Grammatik:

type ('nonterm, 'term) symbol = N of 'nonterm | T of 'term;;

type awksub_nonterminals = Expr | Term | Lvalue | Incrop | Binop | Num;;

let awksub_grammar =
  (Expr,
   function
     | Expr ->
         [[N Term; N Binop; N Expr];
          [N Term]]
     | Term ->
     [[N Num];
      [N Lvalue];
      [N Incrop; N Lvalue];
      [N Lvalue; N Incrop];
      [T"("; N Expr; T")"]]
     | Lvalue ->
     [[T"$"; N Expr]]
     | Incrop ->
     [[T"++"];
      [T"--"]]
     | Binop ->
     [[T"+"];
      [T"-"]]
     | Num ->
     [[T"0"]; [T"1"]; [T"2"]; [T"3"]; [T"4"];
      [T"5"]; [T"6"]; [T"7"]; [T"8"]; [T"9"]]);;

Und hier sind einige Fragmente zum Parsen:

let frag1 = ["4"; "+"; "3"];;
let frag2 = ["9"; "+"; "$"; "1"; "+"];;

Was ich suche, ist eine Regelliste, die das Ergebnis der Analyse eines Fragments ist, wie dieses für frag1 ["4"; "+"; "3"]:

 [(Expr, [N Term; N Binop; N Expr]);
  (Term, [N Num]);
  (Num, [T "3"]);
  (Binop, [T "+"]);
  (Expr, [N Term]);
  (Term, [N Num]);
  (Num, [T "4"])]

Die Einschränkung besteht darin, keine anderen OCaml-Bibliotheken als List ... zu verwenden: /