Logica predicatelor - Tema 11

0. Citiți cursul Familiarizați-vă cu automatele și expresiile regulate și cu modul de transformare din NFA în DFA, de a scrie o expresie regulată și câteva șiruri generate de ea.

1. Comentarii Completați automatul dat cu stări și tranziții astfel încât să urmărească ambele tipuri de comentarii din C. Desenați automatul rezultat.

type state = In | Out | Slash  (* de completat cu alte stari *)

let delta = function        (* function: state -> char -> state *)
  | In -> (function
             | '\n' -> Out
             | _ -> In)
  | Out -> (function
             | '/' -> Slash
             | _ -> Out)
  | Slash -> (function
               | '/' -> In
               | _ -> Out)

let fold_in f =         (* similar cu fold_left, dar pe sirul caracterelor citite din intrare *)
  let rec fold1 v =     (* calculeaza f (f (f (v c1) c2) c3 ... *)
    (try let c = input_char stdin in    (* incearca citirea unui nou caracter c *)
         fun () -> fold1 (f v c)        (* reusit: continua cu acumulatorul f v c *)
     with _ -> fun () -> v) ()          (* exceptie la sfarsit: returneaza acumulatorul *)
  in fold1

(* starea acceptoare e Out -- textul se termina afara din comentariu *)
  
let _ = print_endline (if fold_in delta Out = Out then "OK" else "ends in comment")
Starea inițială e Out (automatul nu a citit nimic, deci nu a început niciun comentariu). Funcția de tranziție a automatului e delta. Funcția fold_in e similară cu List.fold_left dar pe o secvență de caractere citite de la intrare (până la sfârșitul acesteia). Ea apelează repetat o funcție f pe o valoare-acumulator v și caracterul citit de la intrare c, continuând cu f v c ca acumulator. O folosim pentru a implementa funcția de tranziție pentru șiruri de caractere δ* pornind de la delta.
Compilați programul din terminal cu comanda ocamlc fisier.ml. Apoi rulați programul cu ./a.out (sub Windows: ./a). După ce ați introdus caracterele dorite, tastați Ctrl-D pentru a semnala încheierea intrării (Ctrl-Z sub Windows). Pentru a prelua textul dintr-un fișier (prin redirectarea intrării) dați comanda ./a.out < fisier .
Alternativ, puteți scrie un program C care face același lucru.


Marius Minea
Last modified: Wed Dec 9 8:00:00 EET 2015