• Searching and matching text

• Formally describing strings

• Defining the symbols (lexemes or tokens) that make up a language

• RE: A pure OCaml regular expression library that supports multiple formats (glob, POSIX, Str, etc.). In this lecture, we will use the POSIX format of the RE library.

• Str: The standard OCaml Str module. This module is generally not recommended because it is relatively slow and does not support Unicode.

OCaml REPL

#require "re";; (* only needed in utop *) 
 let str2re t = Re.Posix.compile (Re.Posix.re t);; 
 
 let r = str2re "[a-z][0-9]+";; 
 (* The pattern r matches substrings that start with a letter 
 followed by one or more digits *) 
 Re.matches r "a12#b22abcd";;

[Output]
val str2re : string -> Re__.Core.re = <fun>
val r : Re__.Core.re = <abstr>
- : string list = ["a12"; "b22"]

OCaml REPL

#require "re";; (* only needed in utop *) 
 let str2re t = Re.Posix.compile (Re.Posix.re t);; 
 let pattern = str2re "([0-9]{4})-([0-9]{2})-([0-9]{2})";; 
 let text = "The date is 2026-02-23.";; 
 let t = Re.exec pattern text;; 
 Re.Group.get t 1;; (* year *) 
 Re.Group.get t 2;; (* month *) 
 Re.Group.get t 3;; (* day *)

[Output]
val str2re : string -> Re__.Core.re = <fun>
val pattern : Re__.Core.re = <abstr>
val text : string = "The date is 2026-02-23."
val t : Re.Group.t = <abstr>
- : string = "2026"
- : string = "02"
- : string = "23"

In-class Example Code (regex.zip)

regex/bin/main.ml

let () =
  if Array.length Sys.argv <> 2 then (
    Printf.eprintf "Usage: %s <pattern>\n" Sys.argv.(0);
    exit 1);
  let pattern = Sys.argv.(1) in
  match Regex.match_words pattern with
  | words -> Regex.WordSet.iter (Printf.printf "%s\n") words
  | exception Re.Posix.Parse_error ->
    Printf.eprintf "Error: invalid pattern %S\n" pattern;
    exit 1
  | exception Re.Posix.Not_supported ->
    Printf.eprintf "Error: pattern %S uses unsupported POSIX syntax\n" pattern;
    exit 1

regex/lib/regex.ml

(*
  Lists all words from "war and peace" that match the pattern

  More documentation about the Re library:
  https://ocaml.org/p/re/latest/doc/Re/index.html
*)

module WordSet = Set.Make (String)

(* The corpus lives at the project root, but this may run from any
   subdirectory (e.g. under [dune test] or [dune exec]), so search upward
   from the current directory rather than assuming cwd is the root. *)
let find_file name =
  let rec search dir =
    let candidate = Filename.concat dir name in
    if Sys.file_exists candidate then candidate
    else
      let parent = Filename.dirname dir in
      if parent = dir then failwith (Printf.sprintf "Could not locate %s" name)
      else search parent
  in
  search (Sys.getcwd ())

(* Read a file line by line*)
let read_lines file =
  let contents =
    In_channel.with_open_bin (find_file file) In_channel.input_all
  in
  String.split_on_char '\n' contents

let str2re t = Re.Posix.compile (Re.Posix.re t)

let word_delimiter = str2re "[<>/,?!. '-()\":;*]"

let split_into_words delimiter lines =
  List.concat_map
    (fun line -> Re.split delimiter line |> List.map String.lowercase_ascii)
    lines

(* Lowercased words are read and split once per process and reused across
   calls, rather than re-reading and re-splitting the corpus every time. *)
let corpus_words =
  lazy (split_into_words word_delimiter (read_lines "war_peace.txt"))

(* Pure matching logic, independent of the corpus file, so it can be tested
   against a small in-memory word list instead of the full book. *)
let words_matching pattern words =
  let re = str2re pattern in
  List.fold_left
    (fun acc word -> if Re.execp re word then WordSet.add word acc else acc)
    WordSet.empty words

(* Return all unique, lowercased words from "war_peace.txt" matching [pattern] *)
let match_words pattern = words_matching pattern (Lazy.force corpus_words)