--- a/progs/sml/re.ML Fri Mar 18 15:03:54 2016 +0000
+++ b/progs/sml/re.ML Sat Mar 19 23:27:29 2016 +0000
@@ -1,7 +1,7 @@
datatype rexp =
- NULL
- | EMPTY
+ ZERO
+ | ONE
| CHAR of char
| ALT of rexp * rexp
| SEQ of rexp * rexp
@@ -9,7 +9,7 @@
| RECD of string * rexp
datatype value =
- Void
+ Empty
| Chr of char
| Sequ of value * value
| Left of value
@@ -22,7 +22,7 @@
(* some helper functions for rexps *)
fun seq s = case s of
- [] => EMPTY
+ [] => ONE
| [c] => CHAR(c)
| c::cs => SEQ(CHAR(c), seq cs)
@@ -43,15 +43,15 @@
fun op $ (x, r) = RECD(x, r)
fun alts rs = case rs of
- [] => NULL
+ [] => ZERO
| [r] => r
| r::rs => List.foldl (op ++) r rs
(* size of a regular expressions - for testing purposes *)
fun size r = case r of
- 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)
@@ -61,8 +61,8 @@
(* nullable function: tests whether the regular
expression can recognise the empty string *)
fun nullable r = case r of
- NULL => false
- | EMPTY => true
+ ZERO => false
+ | ONE => true
| CHAR(_) => false
| ALT(r1, r2) => nullable(r1) orelse nullable(r2)
| SEQ(r1, r2) => nullable(r1) andalso nullable(r2)
@@ -71,9 +71,9 @@
(* derivative of a regular expression r w.r.t. a character c *)
fun der c r = case r of
- 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)
@@ -88,7 +88,7 @@
(* extracts a string from value *)
fun flatten v = case v of
- Void => ""
+ Empty => ""
| Chr(c) => Char.toString c
| Left(v) => flatten v
| Right(v) => flatten v
@@ -99,7 +99,7 @@
(* extracts an environment from a value *)
fun env v = case v of
- Void => []
+ Empty => []
| Chr(c) => []
| Left(v) => env v
| Right(v) => env v
@@ -113,7 +113,7 @@
(* the value for a nullable rexp *)
fun mkeps r = case r of
- 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)
@@ -130,7 +130,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)
| _ => (print ("\nr: " ^ PolyML.makestring r ^ "\n");
print ("v: " ^ PolyML.makestring v ^ "\n");
@@ -145,8 +145,8 @@
| Left(v) => Left(f1 v)
fun f_seq f1 f2 = fn v => case v of
Sequ(v1, v2) => Sequ(f1 v1, f2 v2)
-fun f_seq_Void1 f1 f2 = fn v => Sequ(f1 Void, f2 v)
-fun f_seq_Void2 f1 f2 = fn v => Sequ(f1 v, f2 Void)
+fun f_seq_Empty1 f1 f2 = fn v => Sequ(f1 Empty, f2 v)
+fun f_seq_Empty2 f1 f2 = fn v => Sequ(f1 v, f2 Empty)
fun f_rec f = fn v => case v of
Rec(x, v) => Rec(x, f v)
@@ -161,8 +161,8 @@
let val (r1s, f1s) = simp r1
val (r2s, f2s) = simp r2 in
(case (r1s, r2s) of
- (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))
end
@@ -170,10 +170,10 @@
let val (r1s, f1s) = simp r1
val (r2s, f2s) = simp r2 in
(case (r1s, r2s) of
- (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))
end
| RECD(x, r1) =>
@@ -183,17 +183,17 @@
| r => (r, f_id)
fun der_simp c r = case r of
- 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
val (r1d, f1d) = der_simp c r1
val (r2d, f2d) = der_simp c r2
in
case (r1d, r2d) of
- (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)
end
@@ -206,11 +206,11 @@
val (r2s, f2s) = simp r2
in
case (r1d, r2s, r2d) of
- (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)
end
else
@@ -219,10 +219,10 @@
val (r2s, f2s) = simp r2
in
case (r1d, r2s) of
- (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)
end
| STAR(r1) =>
@@ -230,8 +230,8 @@
val (r1d, f1d) = der_simp c r1
in
case r1d of
- 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)
end
| RECD(x, r1) => der_simp c r1