lexing: comparison progs/ocaml/re.ml

equal deleted inserted replaced

-:c9027db225cc
+:6a43ea9305ba
 type rexp =
-NULL
+ZERO
-| EMPTY
+| ONE
 | CHAR of char
 | ALT of rexp * rexp
 | SEQ of rexp * rexp
 | STAR of rexp
 | RECD of string * rexp;;
 type value =
-Void
+Empty
 | Chr of char
 | Sequ of value * value
 | Left of value
 | Right of value
 | Stars of value list
 | 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 ^ ")"
 | Right(v1) -> "Right(" ^ string_of_val v1 ^ ")"
 | Stars(vs) -> "[" ^ String.concat "," (List.map string_of_val vs) ^ "]"
 let string_repeat s n =
 Array.fold_left (^) "" (Array.make n s);;
 (* some helper functions for rexps *)
 let rec seq s = match s with
-[] -> EMPTY
+[] -> ONE
 | [c] -> CHAR(c)
 | c::cs -> SEQ(CHAR(c), seq cs);;
 let chr c = CHAR(c)
 let (--) r1 r2 = SEQ(r1, r2);;
 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
+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 *)
 let rec nullable r = match r with
-NULL -> false
+ZERO -> false
-| EMPTY -> true
+| ONE -> true
 | CHAR(_) -> false
 | ALT(r1, r2) -> nullable(r1) || nullable(r2)
 | SEQ(r1, r2) -> nullable(r1) && nullable(r2)
 | STAR(_) -> true
 | RECD(_, r) -> nullable(r);;
 (* derivative of a regular expression r w.r.t. a character c *)
 let rec der c r = match r with
-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 *)
 let rec flatten v = match v with
-Void -> ""
+Empty -> ""
 | Chr(c) -> String.make 1 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 *)
 let rec env v = match v with
-Void -> []
+Empty -> []
 | Chr(c) -> []
 | Left(v) -> env v
 | Right(v) -> env v
 | Sequ(v1, v2) -> env v1 @ env v2
 | Stars(vs) -> List.flatten (List.map env vs)
 let string_of_env xs = String.concat "," (List.map string_of_pair xs);;
 (* 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)
 | 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);;
 (* some "rectification" functions for simplification *)
 let f_id v = v;;
 let f_right f = fun v -> Right(f v);;
 let f_alt f1 f2 = fun v -> match v with
 Right(v) -> Right(f2 v)
 | 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_Empty1 f1 f2 = fun v -> Sequ(f1 Empty, f2 v);;
-let f_seq_Void2 f1 f2 = fun v -> Sequ(f1 v, f2 Void);;
+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);;
 exception ShouldNotHappen
 let f_error v = raise ShouldNotHappen
 let rec simp r = match r with
 ALT(r1, r2) ->
 let (r1s, f1s) = simp r1 in
 let (r2s, f2s) = simp r2 in
 (match r1s, r2s with
-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))
 | SEQ(r1, r2) ->
 let (r1s, f1s) = simp r1 in
 let (r2s, f2s) = simp r2 in
 (match r1s, r2s with
-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))
 | RECD(x, r1) ->
 let (r1s, f1s) = simp r1 in
 (RECD(x, r1s), f_rec f1s)
 | r -> (r, f_id)
 ;;
 let rec der_simp c r = match r with
-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 (r1d, f1d) = der_simp c r1 in
 let (r2d, f2d) = der_simp c r2 in
 (match r1d, r2d with
-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))
 | SEQ(r1, r2) ->
 if nullable r1
 then
 let (r1d, f1d) = der_simp c r1 in
 let (r2d, f2d) = der_simp c r2 in
 let (r2s, f2s) = simp r2 in
 (match r1d, r2s, r2d with
-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))
 else
 let (r1d, f1d) = der_simp c r1 in
 let (r2s, f2s) = simp r2 in
 (match r1d, r2s with
-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))
 | STAR(r1) ->
 let (r1d, f1d) = der_simp c r1 in
 (match r1d with
-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))
 | RECD(x, r1) -> der_simp c r1
 (* matcher function *)

changeset 156	6a43ea9305ba
parent 3	94824659f6d7