module M = Map.Make(Char)

(* inlocuieste caract. i din s1 cu s2 *)
let replace s1 i s2 =
  let i1 = i + 1 in
  (String.sub s1 0 i) ^ s2 ^ (String.sub s1 i1 (String.length s1 - i1))

(* fold_right pe un sir cu o functie de sir, indice si acumulator *)
let foldi_n f v0 s =
  let rec foldi i acc =
    if i = 0 then acc else let i1 = i - 1 in foldi i1 (f s i1 acc)
  in foldi (String.length s) v0

(* adauga la slist toate sirurile obtinute din s printr-un pas de derivare *)
let expand_once gram =
  let expand_i s i slst =
    let prods = try M.find s.[i] gram with Not_found -> []
    in List.fold_left (fun acc rhs -> replace s i rhs :: acc) slst prods
  in foldi_n expand_i

(* calculeaza toate sirurile obtinute din s dupa n pasi de derivare *)
let expand_n gram s =
  let rec expand1 n =
    if n = 0 then [s]
    else List.fold_left (expand_once gram) [] (expand1 (n-1))
  in expand1
       
let gram = M.add 'S' ["aA";"b"] (M.add 'A' ["Bb";"aA"] (M.singleton 'B' ["Sa"]))

let sls = expand_n gram "S" 3

This document was generated using caml2html