diff -r c9027db225cc -r 6a43ea9305ba progs/sml/re.ML --- 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