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