anchor.diff:  
   open System.Diagnostics
   open LanguagePrimitives
  +open ExtCore
  +open ExtCore.Collections
  +open ExtCore.Control
  +open ExtCore.Control.Collections
   open SpecializedCollections
   
   (*  Turn off warning about uppercase variable identifiers;
  
positive.code:         Regex.IsNullableImpl regex id
  
      /// Implementation of the canonicalization function.
      static member private CanonicalizeImpl (regex : Regex) (cont : Regex -> Regex) =
          match regex with
          | Epsilon
          | Any as regex ->
              cont regex
  
          | CharacterSet _ as charSetRegex ->
              charSetRegex
              |> cont
  
          | Negate Empty ->
              cont Any
          | Negate Any ->
              cont Regex.empty
          | Negate Epsilon ->
              cont Regex.empty
          | Negate (Negate regex) ->
              Regex.CanonicalizeImpl regex cont
          | Negate r ->
              Regex.CanonicalizeImpl r <| fun r' ->
                  Negate r'
                  |> cont
  
          | Star (Star _ as ``r*``) ->
              Regex.CanonicalizeImpl ``r*`` cont
          | Star Epsilon
          | Star Empty ->
              cont Epsilon
          | Star (Or (Epsilon, r))
          | Star (Or (r, Epsilon)) ->
              Regex.CanonicalizeImpl r <| fun r' ->
                  Star r'
                  |> cont
          | Star r ->
              Regex.CanonicalizeImpl r <| fun r' ->
                  Star r'
                  |> cont
  
          | Concat (Empty, _)
          | Concat (_, Empty) ->
              cont Regex.empty
          | Concat (Epsilon, r)
          | Concat (r, Epsilon) ->
              Regex.CanonicalizeImpl r cont
          | Concat (r, Concat (s, t)) ->
              // Rewrite the expression so it's left-associative.
              let regex = Concat (Concat (r, s), t)
              Regex.CanonicalizeImpl regex cont        
          | Concat (r, s) ->
              Regex.CanonicalizeImpl r <| fun r' ->
              Regex.CanonicalizeImpl s <| fun s' ->
                  // Try to simplify the expression, using the canonicalized components.
                  match r', s' with
                  | Empty, _
                  | _, Empty ->
                      cont Regex.empty
                  | Epsilon, r'
                  | r', Epsilon ->
                      Regex.CanonicalizeImpl r' cont
                  | r', s' ->
                      Concat (r', s')
                      |> cont
  
          | Or (Any, _)
          | Or (_, Any) ->
              cont Any
          | Or (Empty, r)
          | Or (r, Empty) ->
              Regex.CanonicalizeImpl r cont
          | Or (CharacterSet charSet1, CharacterSet charSet2) ->
              // 'Or' is the disjunction (union) of two Regexes.
              let charSetUnion = CharSet.union charSet1 charSet2
  
              // Return the simplest Regex for the union set.
              CharacterSet charSetUnion
              |> cont
  
          | Or (r, Or (s, t)) ->
              // Rewrite the expression so it's left-associative.
              let regex = Or (Or (r, s), t)
              Regex.CanonicalizeImpl regex cont
          | Or (r, s) ->
              Regex.CanonicalizeImpl r <| fun r' ->
              Regex.CanonicalizeImpl s <| fun s' ->
                  // Try to simplify the expression, using the canonicalized components.
                  match r', s' with
                  | r', s' when r' = s' ->
                      cont r'
  
                  | Empty, r
                  | r, Empty ->
                      Regex.CanonicalizeImpl r cont
  
                  | Any, _
                  | _, Any ->
                      cont Any
  
                  | CharacterSet charSet1, CharacterSet charSet2 ->
                      // 'Or' is the disjunction (union) of two Regexes.
                      let charSetUnion = CharSet.union charSet1 charSet2
  
                      // Return the simplest Regex for the union set.
                      CharacterSet charSetUnion
                      |> cont
  
                  | r', s' ->
                      // Sort the components before returning; this takes care
                      // of the symmetry rule (r | s) = (s | r) so the
                      // "approximately equal" relation is simply handled by
                      // F#'s structural equality.
                      if r' < s'
                      then Or (r', s')
                      else Or (s', r')
                      |> cont
          
          | And (Any, r)
          | And (r, Any) ->
              Regex.CanonicalizeImpl r cont
          | And (Empty, _)
          | And (_, Empty) ->
              cont Regex.empty
          | And (CharacterSet charSet1, CharacterSet charSet2) ->
              // 'And' is the conjunction (intersection) of two Regexes.
              let charSetIntersection = CharSet.intersect charSet1 charSet2
  
              // Return the simplest Regex for the intersection set.
              CharacterSet charSetIntersection
              |> cont
          | And (r, And (s, t)) ->
              // Rewrite the expression so it's left-associative.
              let regex = And (And (r, s), t)
              Regex.CanonicalizeImpl regex cont
          | And (r, s) ->
              Regex.CanonicalizeImpl r <| fun r' ->
              Regex.CanonicalizeImpl s <| fun s' ->
                  // Try to simplify the expression, using the canonicalized components.
                  match r', s' with
                  | r', s' when r' = s' ->
                      cont r'
  
                  | Empty, _
                  | _, Empty ->
                      cont Regex.empty
  
                  | Any, r
                  | r, Any ->
                      Regex.CanonicalizeImpl r cont
  
                  | CharacterSet charSet1, CharacterSet charSet2 ->
                      // 'And' is the conjunction (intersection) of two Regexes.
                      let charSetIntersection = CharSet.intersect charSet1 charSet2
  
                      // Return the simplest Regex for the intersection set.
                      CharacterSet charSetIntersection
                      |> cont
  
                  | r', s' ->
                      // Sort the components before returning; this takes care
                      // of the symmetry rule (r & s) = (s & r) so the
                      // "approximately equal" relation is simply handled by
                      // F#'s structural equality.
                      if r' < s'
                      then And (r', s')
                      else And (s', r')
                      |> cont
  
      /// Creates a new Regex in canonical form from the given Regex.
      static member Canonicalize (regex : Regex) : Regex =
          Regex.CanonicalizeImpl regex id
  
      //
      static member private DerivativeImpl wrtSymbol regex cont =
          match regex with
          | Epsilon ->
              cont Regex.empty
          | Star r as ``r*`` ->
              Regex.DerivativeImpl wrtSymbol r <| fun r' ->
                  Concat (r', ``r*``)
                  |> cont
          | Concat (r, s) ->
              let ``nu(r)`` = if Regex.IsNullable r then Epsilon else Regex.empty
              Regex.DerivativeImpl wrtSymbol r <| fun r' ->
              Regex.DerivativeImpl wrtSymbol s <| fun s' ->
                  Or (Concat (r', s),
                      Concat (``nu(r)``, s'))
                  |> cont
          | Or (r, s) ->
              Regex.DerivativeImpl wrtSymbol r <| fun r' ->
              Regex.DerivativeImpl wrtSymbol s <| fun s' ->
                  Or (r', s')
                  |> cont
          | And (r, s) ->
              Regex.DerivativeImpl wrtSymbol r <| fun r' ->
              Regex.DerivativeImpl wrtSymbol s <| fun s' ->
                  And (r', s')
                  |> cont
  
          | Any ->
              cont Epsilon
          | Negate r ->
              Regex.DerivativeImpl wrtSymbol r <| fun r' ->
                  Negate r'
                  |> cont
          | CharacterSet charSet ->
              if CharSet.contains wrtSymbol charSet
              then Epsilon
              else Regex.empty
              |> cont
  
      /// Computes the derivative of a Regex with respect to a specified symbol.
      static member Derivative symbol regex =
  
negative.code: // Add more members to Regex
  type Regex with
      //
      static member private DerivativeClassesImpl regex =
          Cps.cont {
          match regex with
          | Epsilon ->
              return DerivativeClasses.Universe
          | Any ->
              return
                  { DerivativeClasses.Universe
                      with HasEmptySet = true; }
          | CharacterSet charSet ->
              return
                  { HasEmptySet = false;
                    Elements = charSet;
                    Negated = charSet; }
          | Negate r
          | Star r ->
              return! Regex.DerivativeClassesImpl r
          | Concat (r, s) ->
              if not <| Regex.IsNullable r then
                  return! Regex.DerivativeClassesImpl r
              else
                  let! ``C(r)`` = Regex.DerivativeClassesImpl r
                  let! ``C(s)`` = Regex.DerivativeClassesImpl s
                  return DerivativeClasses.Intersect (``C(r)``, ``C(s)``)
          | Or (r, s)
          | And (r, s) ->
              let! ``C(r)`` = Regex.DerivativeClassesImpl r
              let! ``C(s)`` = Regex.DerivativeClassesImpl s
              return DerivativeClasses.Intersect (``C(r)``, ``C(s)``)
          }
  
      /// Computes an approximate set of derivative classes for the specified Regex.
      static member DerivativeClasses (regex : Regex) =
  