lexing: comparison progs/sml/re.ML

equal deleted inserted replaced

-:c9027db225cc
+:6a43ea9305ba
 datatype rexp =
-NULL
+ZERO
-| EMPTY
+| ONE
 | CHAR of char
 | ALT of rexp * rexp
 | SEQ of rexp * rexp
 | STAR of rexp
 | RECD of string * rexp
 datatype value =
-Void
+Empty
 | Chr of char
 | Sequ of value * value
 | Left of value
 | Right of value
 | Stars of value list
 (* some helper functions for strings *)
 fun string_repeat s n = String.concat (List.tabulate (n, fn _ => s))
 (* some helper functions for rexps *)
 fun seq s = case s of
-[] => EMPTY
+[] => ONE
 | [c] => CHAR(c)
 | c::cs => SEQ(CHAR(c), seq cs)
 fun chr c = CHAR(c)
 fun op -- (r1, r2) = SEQ(r1, r2)
 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
+ZERO => 1
-| EMPTY => 1
+| ONE => 1
 | CHAR(_) => 1
 | ALT(r1, r2) => 1 + (size r1) + (size r2)
 | SEQ(r1, r2) => 1 + (size r1) + (size r2)
 | STAR(r) => 1 + (size r)
 | RECD(_, r) => 1 + (size r)
 (* nullable function: tests whether the regular
 expression can recognise the empty string *)
 fun nullable r = case r of
-NULL => false
+ZERO => false
-| EMPTY => true
+| ONE => true
 | CHAR(_) => false
 | ALT(r1, r2) => nullable(r1) orelse nullable(r2)
 | SEQ(r1, r2) => nullable(r1) andalso nullable(r2)
 | STAR(_) => true
 | RECD(_, r) => nullable(r)
 (* derivative of a regular expression r w.r.t. a character c *)
 fun der c r = case r of
-NULL => NULL
+ZERO => ZERO
-| EMPTY => NULL
+| ONE => ZERO
-| CHAR(d) => if c = d then EMPTY else NULL
+| 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)
 else SEQ(der c r1, r2)
 | STAR(r) => SEQ(der c r, STAR(r))
 [] => r
 | c::s => ders s (der c r)
 (* 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
 | Sequ(v1, v2) => flatten v1 ^ flatten v2
 | Stars(vs) => String.concat (List.map flatten vs)
 | Rec(_, v) => flatten v
 (* extracts an environment from a value *)
 fun env v = case v of
-Void => []
+Empty => []
 | Chr(c) => []
 | Left(v) => env v
 | Right(v) => env v
 | Sequ(v1, v2) => env v1 @ env v2
 | Stars(vs) => List.foldr (op @) [] (List.map env vs)
 fun string_of_env xs = String.concatWith "," (List.map string_of_pair xs)
 (* 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)
 | STAR(r) => Stars([])
 | RECD(x, r) => Rec(x, mkeps r)
 | (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj r1 c v1, v2)
 | (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj r1 c v1, v2)
 | (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");
 raise Error)
 fun f_alt f1 f2 = fn v => case v of
 Right(v) => Right(f2 v)
 | 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_Empty1 f1 f2 = fn v => Sequ(f1 Empty, f2 v)
-fun f_seq_Void2 f1 f2 = fn v => Sequ(f1 v, f2 Void)
+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)
 exception ShouldNotHappen
 fun simp r = case r of
 ALT(r1, r2) =>
 let val (r1s, f1s) = simp r1
 val (r2s, f2s) = simp r2 in
 (case (r1s, r2s) of
-(NULL, _) => (r2s, f_right f2s)
+(ZERO, _) => (r2s, f_right f2s)
-| (_, NULL) => (r1s, f_left f1s)
+| (_, ZERO) => (r1s, f_left f1s)
 | (_, _)    => if r1s = r2s then (r1s, f_left f1s)
 else (ALT (r1s, r2s), f_alt f1s f2s))
 end
 | SEQ(r1, r2) =>
 let val (r1s, f1s) = simp r1
 val (r2s, f2s) = simp r2 in
 (case (r1s, r2s) of
-(NULL, _)  => (NULL, f_error)
+(ZERO, _)  => (ZERO, f_error)
-| (_, NULL)  => (NULL, f_error)
+| (_, ZERO)  => (ZERO, f_error)
-| (EMPTY, _) => (r2s, f_seq_Void1 f1s f2s)
+| (ONE, _) => (r2s, f_seq_Empty1 f1s f2s)
-| (_, EMPTY) => (r1s, f_seq_Void2 f1s f2s)
+| (_, ONE) => (r1s, f_seq_Empty2 f1s f2s)
 | (_, _)     => (SEQ(r1s, r2s), f_seq f1s f2s))
 end
 | RECD(x, r1) =>
 let val (r1s, f1s) = simp r1 in
 (RECD(x, r1s), f_rec f1s)
 end
 | r => (r, f_id)
 fun der_simp c r = case r of
-NULL => (NULL, f_id)
+ZERO => (ZERO, f_id)
-| EMPTY => (NULL, f_id)
+| ONE => (ZERO, f_id)
-| CHAR(d) => ((if c = d then EMPTY else NULL), 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)
+(ZERO, _) => (r2d, f_right f2d)
-| (_, NULL) => (r1d, f_left f1d)
+| (_, ZERO) => (r1d, f_left f1d)
 | (_, _)    => if r1d = r2d then (r1d, f_left f1d)
 else (ALT (r1d, r2d), f_alt f1d f2d)
 end
 | SEQ(r1, r2) =>
 if nullable r1
 val (r1d, f1d) = der_simp c r1
 val (r2d, f2d) = der_simp c r2
 val (r2s, f2s) = simp r2
 in
 case (r1d, r2s, r2d) of
-(NULL, _, _)  => (r2d, f_right f2d)
+(ZERO, _, _)  => (r2d, f_right f2d)
-| (_, NULL, _)  => (r2d, f_right f2d)
+| (_, ZERO, _)  => (r2d, f_right f2d)
-| (_, _, NULL)  => (SEQ(r1d, r2s), f_left (f_seq f1d f2s))
+| (_, _, ZERO)  => (SEQ(r1d, r2s), f_left (f_seq f1d f2s))
-| (EMPTY, _, _) => (ALT(r2s, r2d), f_alt (f_seq_Void1 f1d f2s) f2d)
+| (ONE, _, _) => (ALT(r2s, r2d), f_alt (f_seq_Empty1 f1d f2s) f2d)
-| (_, EMPTY, _) => (ALT(r1d, r2d), f_alt (f_seq_Void2 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
 let
 val (r1d, f1d) = der_simp c r1
 val (r2s, f2s) = simp r2
 in
 case (r1d, r2s) of
-(NULL, _) => (NULL, f_error)
+(ZERO, _) => (ZERO, f_error)
-| (_, NULL) => (NULL, f_error)
+| (_, ZERO) => (ZERO, f_error)
-| (EMPTY, _) => (r2s, f_seq_Void1 f1d f2s)
+| (ONE, _) => (r2s, f_seq_Empty1 f1d f2s)
-| (_, EMPTY) => (r1d, f_seq_Void2 f1d f2s)
+| (_, ONE) => (r1d, f_seq_Empty2 f1d f2s)
 | (_, _) => (SEQ(r1d, r2s), f_seq f1d f2s)
 	end
 | STAR(r1) =>
 let
 val (r1d, f1d) = der_simp c r1
 in
 case r1d of
-NULL => (NULL, f_error)
+ZERO => (ZERO, f_error)
-| EMPTY => (STAR r1, f_seq_Void1 f1d f_id)
+| 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

changeset 156	6a43ea9305ba
parent 3	94824659f6d7
child 317	db0ff630bbb7