--- a/progs/ocaml/re.ml Fri Mar 18 15:03:54 2016 +0000
+++ b/progs/ocaml/re.ml Sat Mar 19 23:27:29 2016 +0000
@@ -1,7 +1,7 @@
type rexp =
- NULL
- | EMPTY
+ ZERO
+ | ONE
| CHAR of char
| ALT of rexp * rexp
| SEQ of rexp * rexp
@@ -9,7 +9,7 @@
| RECD of string * rexp;;
type value =
- Void
+ Empty
| Chr of char
| Sequ of value * value
| Left of value
@@ -18,7 +18,7 @@
| Rec of string * value;;
let rec string_of_val v = match v with
- Void -> "Void"
+ Empty -> "Empty"
| Chr(c) -> String.make 1 c
| Sequ(v1, v2) -> "Seq(" ^ string_of_val v1 ^ "," ^ string_of_val v2 ^ ")"
| Left(v1) -> "Left(" ^ string_of_val v1 ^ ")"
@@ -38,7 +38,7 @@
(* some helper functions for rexps *)
let rec seq s = match s with
- [] -> EMPTY
+ [] -> ONE
| [c] -> CHAR(c)
| c::cs -> SEQ(CHAR(c), seq cs);;
@@ -55,15 +55,15 @@
let ($) x r = RECD(x, r);;
let alts rs = match rs with
- [] -> NULL
+ [] -> ZERO
| [r] -> r
| r::rs -> List.fold_left (++) r rs;;
(* size of a regular expressions - for testing purposes *)
let rec size r = match r with
- NULL -> 1
- | EMPTY -> 1
+ ZERO -> 1
+ | ONE -> 1
| CHAR(_) -> 1
| ALT(r1, r2) -> 1 + (size r1) + (size r2)
| SEQ(r1, r2) -> 1 + (size r1) + (size r2)
@@ -73,8 +73,8 @@
(* nullable function: tests whether the regular
expression can recognise the empty string *)
let rec nullable r = match r with
- NULL -> false
- | EMPTY -> true
+ ZERO -> false
+ | ONE -> true
| CHAR(_) -> false
| ALT(r1, r2) -> nullable(r1) || nullable(r2)
| SEQ(r1, r2) -> nullable(r1) && nullable(r2)
@@ -83,9 +83,9 @@
(* derivative of a regular expression r w.r.t. a character c *)
let rec der c r = match r with
- NULL -> NULL
- | EMPTY -> NULL
- | CHAR(d) -> if c = d then EMPTY else NULL
+ ZERO -> ZERO
+ | ONE -> ZERO
+ | CHAR(d) -> if c = d then ONE else ZERO
| ALT(r1, r2) -> ALT(der c r1, der c r2)
| SEQ(r1, r2) ->
if nullable r1 then ALT(SEQ(der c r1, r2), der c r2)
@@ -100,7 +100,7 @@
(* extracts a string from value *)
let rec flatten v = match v with
- Void -> ""
+ Empty -> ""
| Chr(c) -> String.make 1 c
| Left(v) -> flatten v
| Right(v) -> flatten v
@@ -111,7 +111,7 @@
(* extracts an environment from a value *)
let rec env v = match v with
- Void -> []
+ Empty -> []
| Chr(c) -> []
| Left(v) -> env v
| Right(v) -> env v
@@ -125,7 +125,7 @@
(* the value for a nullable rexp *)
let rec mkeps r = match r with
- EMPTY -> Void
+ ONE -> Empty
| ALT(r1, r2) ->
if nullable r1 then Left(mkeps r1) else Right(mkeps r2)
| SEQ(r1, r2) -> Sequ(mkeps r1, mkeps r2)
@@ -141,7 +141,7 @@
| SEQ(r1, r2), Right(v2) -> Sequ(mkeps r1, inj r2 c v2)
| ALT(r1, r2), Left(v1) -> Left(inj r1 c v1)
| ALT(r1, r2), Right(v2) -> Right(inj r2 c v2)
- | CHAR(d), Void -> Chr(d)
+ | CHAR(d), Empty -> Chr(d)
| RECD(x, r1), _ -> Rec(x, inj r1 c v);;
(* some "rectification" functions for simplification *)
@@ -153,8 +153,8 @@
| Left(v) -> Left(f1 v);;
let f_seq f1 f2 = fun v -> match v with
Sequ(v1, v2) -> Sequ(f1 v1, f2 v2);;
-let f_seq_Void1 f1 f2 = fun v -> Sequ(f1 Void, f2 v);;
-let f_seq_Void2 f1 f2 = fun v -> Sequ(f1 v, f2 Void);;
+let f_seq_Empty1 f1 f2 = fun v -> Sequ(f1 Empty, f2 v);;
+let f_seq_Empty2 f1 f2 = fun v -> Sequ(f1 v, f2 Empty);;
let f_rec f = fun v -> match v with
Rec(x, v) -> Rec(x, f v);;
@@ -168,18 +168,18 @@
let (r1s, f1s) = simp r1 in
let (r2s, f2s) = simp r2 in
(match r1s, r2s with
- NULL, _ -> (r2s, f_right f2s)
- | _, NULL -> (r1s, f_left f1s)
+ ZERO, _ -> (r2s, f_right f2s)
+ | _, ZERO -> (r1s, f_left f1s)
| _, _ -> if r1s = r2s then (r1s, f_left f1s)
else (ALT (r1s, r2s), f_alt f1s f2s))
| SEQ(r1, r2) ->
let (r1s, f1s) = simp r1 in
let (r2s, f2s) = simp r2 in
(match r1s, r2s with
- NULL, _ -> (NULL, f_error)
- | _, NULL -> (NULL, f_error)
- | EMPTY, _ -> (r2s, f_seq_Void1 f1s f2s)
- | _, EMPTY -> (r1s, f_seq_Void2 f1s f2s)
+ ZERO, _ -> (ZERO, f_error)
+ | _, ZERO -> (ZERO, f_error)
+ | ONE, _ -> (r2s, f_seq_Empty1 f1s f2s)
+ | _, ONE -> (r1s, f_seq_Empty2 f1s f2s)
| _, _ -> (SEQ(r1s, r2s), f_seq f1s f2s))
| RECD(x, r1) ->
let (r1s, f1s) = simp r1 in
@@ -188,15 +188,15 @@
;;
let rec der_simp c r = match r with
- NULL -> (NULL, f_id)
- | EMPTY -> (NULL, f_id)
- | CHAR(d) -> ((if c = d then EMPTY else NULL), f_id)
+ ZERO -> (ZERO, f_id)
+ | ONE -> (ZERO, f_id)
+ | CHAR(d) -> ((if c = d then ONE else ZERO), f_id)
| ALT(r1, r2) ->
let (r1d, f1d) = der_simp c r1 in
let (r2d, f2d) = der_simp c r2 in
(match r1d, r2d with
- NULL, _ -> (r2d, f_right f2d)
- | _, NULL -> (r1d, f_left f1d)
+ ZERO, _ -> (r2d, f_right f2d)
+ | _, ZERO -> (r1d, f_left f1d)
| _, _ -> if r1d = r2d then (r1d, f_left f1d)
else (ALT (r1d, r2d), f_alt f1d f2d))
| SEQ(r1, r2) ->
@@ -206,26 +206,26 @@
let (r2d, f2d) = der_simp c r2 in
let (r2s, f2s) = simp r2 in
(match r1d, r2s, r2d with
- NULL, _, _ -> (r2d, f_right f2d)
- | _, NULL, _ -> (r2d, f_right f2d)
- | _, _, NULL -> (SEQ(r1d, r2s), f_left (f_seq f1d f2s))
- | EMPTY, _, _ -> (ALT(r2s, r2d), f_alt (f_seq_Void1 f1d f2s) f2d)
- | _, EMPTY, _ -> (ALT(r1d, r2d), f_alt (f_seq_Void2 f1d f2s) f2d)
+ ZERO, _, _ -> (r2d, f_right f2d)
+ | _, ZERO, _ -> (r2d, f_right f2d)
+ | _, _, ZERO -> (SEQ(r1d, r2s), f_left (f_seq f1d f2s))
+ | ONE, _, _ -> (ALT(r2s, r2d), f_alt (f_seq_Empty1 f1d f2s) f2d)
+ | _, ONE, _ -> (ALT(r1d, r2d), f_alt (f_seq_Empty2 f1d f2s) f2d)
| _, _, _ -> (ALT(SEQ(r1d, r2s), r2d), f_alt (f_seq f1d f2s) f2d))
else
let (r1d, f1d) = der_simp c r1 in
let (r2s, f2s) = simp r2 in
(match r1d, r2s with
- NULL, _ -> (NULL, f_error)
- | _, NULL -> (NULL, f_error)
- | EMPTY, _ -> (r2s, f_seq_Void1 f1d f2s)
- | _, EMPTY -> (r1d, f_seq_Void2 f1d f2s)
+ ZERO, _ -> (ZERO, f_error)
+ | _, ZERO -> (ZERO, f_error)
+ | ONE, _ -> (r2s, f_seq_Empty1 f1d f2s)
+ | _, ONE -> (r1d, f_seq_Empty2 f1d f2s)
| _, _ -> (SEQ(r1d, r2s), f_seq f1d f2s))
| STAR(r1) ->
let (r1d, f1d) = der_simp c r1 in
(match r1d with
- NULL -> (NULL, f_error)
- | EMPTY -> (STAR r1, f_seq_Void1 f1d f_id)
+ ZERO -> (ZERO, f_error)
+ | ONE -> (STAR r1, f_seq_Empty1 f1d f_id)
| _ -> (SEQ(r1d, STAR(r1)), f_seq f1d f_id))
| RECD(x, r1) -> der_simp c r1