-- ------------------------------------------------------------

{- |
   Module     : Text.XML.HXT.DTDValidation.RE
   Copyright  : Copyright (C) 2008 Uwe Schmidt
   License    : MIT

   Maintainer : Uwe Schmidt (uwe@fh-wedel.de)
   Stability  : experimental
   Portability: portable

   A module for regular expression matching based on derivatives of regular expressions.

   The code was taken from Joe English (<http://www.flightlab.com/~joe/sgml/validate.html>).
   Tested and extended by Martin Schmidt.

   Further references for the algorithm:

   Janusz A. Brzozowski.

        Derivatives of Regular Expressions. Journal of the ACM, Volume 11, Issue 4, 1964.

   Mark Hopkins.

        Regular Expression Package. Posted to comp.compilers, 1994.
        Available per FTP at <ftp://iecc.com/pub/file/regex.tar.gz>.
-}

-- ------------------------------------------------------------

module Text.XML.HXT.DTDValidation.RE
    ( RE(..)

    , re_unit
    , re_zero
    , re_sym
    , re_rep
    , re_plus
    , re_opt
    , re_seq
    , re_alt
    , re_dot

    , checkRE
    , matches
    , nullable
    , printRE
  )
where

import           Data.List (foldl')

-- |
-- Data type for regular expressions.

data RE a =
        RE_ZERO String          --' L(0)   = {} (empty set)
        | RE_UNIT               --' L(1)   = { [] } (empty sequence)
        | RE_SYM a              --' L(x)   = { [x] }
        | RE_DOT                --' accept any single symbol
        | RE_REP (RE a)         --' L(e*)  = { [] } `union` L(e+)
        | RE_PLUS (RE a)        --' L(e+)  = { x ++ y | x <- L(e), y <- L(e*) }
        | RE_OPT (RE a)         --' L(e?)  = L(e) `union` { [] }
        | RE_SEQ (RE a) (RE a)  --' L(e,f) = { x ++ y | x <- L(e), y <- L(f) }
        | RE_ALT (RE a) (RE a)  --' L(e|f) = L(e) `union` L(f)
        deriving (Int -> RE a -> ShowS
[RE a] -> ShowS
RE a -> String
(Int -> RE a -> ShowS)
-> (RE a -> String) -> ([RE a] -> ShowS) -> Show (RE a)
forall a. Show a => Int -> RE a -> ShowS
forall a. Show a => [RE a] -> ShowS
forall a. Show a => RE a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [RE a] -> ShowS
$cshowList :: forall a. Show a => [RE a] -> ShowS
show :: RE a -> String
$cshow :: forall a. Show a => RE a -> String
showsPrec :: Int -> RE a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> RE a -> ShowS
Show, RE a -> RE a -> Bool
(RE a -> RE a -> Bool) -> (RE a -> RE a -> Bool) -> Eq (RE a)
forall a. Eq a => RE a -> RE a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: RE a -> RE a -> Bool
$c/= :: forall a. Eq a => RE a -> RE a -> Bool
== :: RE a -> RE a -> Bool
$c== :: forall a. Eq a => RE a -> RE a -> Bool
Eq, Eq (RE a)
Eq (RE a)
-> (RE a -> RE a -> Ordering)
-> (RE a -> RE a -> Bool)
-> (RE a -> RE a -> Bool)
-> (RE a -> RE a -> Bool)
-> (RE a -> RE a -> Bool)
-> (RE a -> RE a -> RE a)
-> (RE a -> RE a -> RE a)
-> Ord (RE a)
RE a -> RE a -> Bool
RE a -> RE a -> Ordering
RE a -> RE a -> RE a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (RE a)
forall a. Ord a => RE a -> RE a -> Bool
forall a. Ord a => RE a -> RE a -> Ordering
forall a. Ord a => RE a -> RE a -> RE a
min :: RE a -> RE a -> RE a
$cmin :: forall a. Ord a => RE a -> RE a -> RE a
max :: RE a -> RE a -> RE a
$cmax :: forall a. Ord a => RE a -> RE a -> RE a
>= :: RE a -> RE a -> Bool
$c>= :: forall a. Ord a => RE a -> RE a -> Bool
> :: RE a -> RE a -> Bool
$c> :: forall a. Ord a => RE a -> RE a -> Bool
<= :: RE a -> RE a -> Bool
$c<= :: forall a. Ord a => RE a -> RE a -> Bool
< :: RE a -> RE a -> Bool
$c< :: forall a. Ord a => RE a -> RE a -> Bool
compare :: RE a -> RE a -> Ordering
$ccompare :: forall a. Ord a => RE a -> RE a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (RE a)
Ord)



-- ------------------------------------------------------------
-- Constructor functions to simplify regular expressions when constructing them.

-- |
-- Constructs a regular expression for an empty set.
--
--    * 1.parameter errMsg :  error message
--
--    - returns : regular expression for an empty set

re_zero                 :: String -> RE a
re_zero :: String -> RE a
re_zero String
m               = String -> RE a
forall a. String -> RE a
RE_ZERO String
m


-- |
-- Constructs a regular expression for an empty sequence.
--
--    - returns : regular expression for an empty sequence

re_unit                 :: RE a
re_unit :: RE a
re_unit                 = RE a
forall a. RE a
RE_UNIT


-- |
-- Constructs a regular expression for accepting a symbol
--
--    * 1.parameter sym :  the symbol to be accepted
--
--    - returns : regular expression for accepting a symbol

re_sym                  :: a -> RE a
re_sym :: a -> RE a
re_sym a
x                = a -> RE a
forall a. a -> RE a
RE_SYM a
x


-- |
-- Constructs a regular expression for accepting any singel symbol
--
--    - returns : regular expression for accepting any singel symbol

re_dot                  :: RE a
re_dot :: RE a
re_dot                  = RE a
forall a. RE a
RE_DOT


-- |
-- Constructs an optional repetition (*) of a regular expression
--
--    * 1.parameter re_a :  regular expression to be repeted
--
--    - returns : new regular expression

re_rep                  :: RE a -> RE a
re_rep :: RE a -> RE a
re_rep RE a
RE_UNIT          = RE a
forall a. RE a
RE_UNIT
re_rep (RE_ZERO String
_)      = RE a
forall a. RE a
RE_UNIT
re_rep e :: RE a
e@(RE_REP RE a
_)     = RE a -> RE a
forall a. RE a -> RE a
RE_REP (RE a -> RE a
forall a. RE a -> RE a
rem_rep RE a
e)            -- remove nested reps
re_rep e :: RE a
e@(RE_ALT RE a
_ RE a
_)   = RE a -> RE a
forall a. RE a -> RE a
RE_REP (RE a -> RE a
forall a. RE a -> RE a
rem_rep RE a
e)            -- remove nested reps in alternatives
re_rep RE a
e                = RE a -> RE a
forall a. RE a -> RE a
RE_REP RE a
e

-- |
-- remove redundant nested *'s in RE
-- theoretically this is unneccessary,
-- but without this simplification the runtime can increase exponentally
-- when computing deltas, e.g. for a** or (a|b*)* which is the same as (a|b)*

rem_rep                     :: RE a -> RE a
rem_rep :: RE a -> RE a
rem_rep (RE_ALT RE a
RE_UNIT RE a
e2) = RE a
e2
rem_rep (RE_ALT RE a
e1 RE a
e2)      = RE a -> RE a -> RE a
forall a. RE a -> RE a -> RE a
RE_ALT (RE a -> RE a
forall a. RE a -> RE a
rem_rep RE a
e1) (RE a -> RE a
forall a. RE a -> RE a
rem_rep RE a
e2)
rem_rep (RE_REP RE a
e1)         = RE a -> RE a
forall a. RE a -> RE a
rem_rep RE a
e1
rem_rep RE a
e1                  = RE a
e1


-- |
-- Constructs a repetition (+) of a regular expression
--
--    * 1.parameter re_a :  regular expression to be repeted
--
--    - returns : new regular expression

re_plus                 :: RE a -> RE a
re_plus :: RE a -> RE a
re_plus RE a
RE_UNIT         = RE a
forall a. RE a
RE_UNIT
re_plus (RE_ZERO String
m)     = String -> RE a
forall a. String -> RE a
RE_ZERO String
m
re_plus RE a
e
    | RE a -> Bool
forall a. RE a -> Bool
nullable RE a
e        = RE a -> RE a
forall a. RE a -> RE a
re_rep RE a
e            -- nullable e => e+ == e*
    | Bool
otherwise         = RE a -> RE a -> RE a
forall a. RE a -> RE a -> RE a
re_seq RE a
e (RE a -> RE a
forall a. RE a -> RE a
re_rep RE a
e)


-- |
-- Constructs an option (?) of a regular expression
--
--    * 1.parameter re_a :  regular expression to be optional
--
--    - returns : new regular expression

re_opt                  :: (Ord a) => RE a -> RE a
re_opt :: RE a -> RE a
re_opt RE a
RE_UNIT          = RE a
forall a. RE a
RE_UNIT
re_opt (RE_ZERO String
_)      = RE a
forall a. RE a
RE_UNIT
re_opt RE a
e                = RE a -> RE a -> RE a
forall a. Ord a => RE a -> RE a -> RE a
re_alt RE a
forall a. RE a
RE_UNIT RE a
e

-- |
-- Constructs a sequence (,) of two regular expressions
--
--    * 1.parameter re_a :  first regular expression in sequence
--
--    - 2.parameter re_b :  second regular expression in sequence
--
--    - returns : new regular expression

re_seq                                 :: RE a -> RE a -> RE a
re_seq :: RE a -> RE a -> RE a
re_seq e1 :: RE a
e1@(RE_ZERO String
_)   RE a
_              = RE a
e1                         -- simplification
re_seq RE a
RE_UNIT          RE a
e2             = RE a
e2                         -- simplification
re_seq RE a
_                e2 :: RE a
e2@(RE_ZERO String
_) = RE a
e2                         -- simplification
re_seq RE a
e1               RE a
RE_UNIT        = RE a
e1                         -- simplification
re_seq (RE_SEQ RE a
e11 RE a
e12) RE a
e2             = RE a -> RE a -> RE a
forall a. RE a -> RE a -> RE a
re_seq RE a
e11 (RE a -> RE a -> RE a
forall a. RE a -> RE a -> RE a
re_seq RE a
e12 RE a
e2) -- right assoc.
re_seq RE a
e1               RE a
e2             = RE a -> RE a -> RE a
forall a. RE a -> RE a -> RE a
RE_SEQ RE a
e1 RE a
e2


-- |
-- Constructs an alternative (|) of two regular expressions
--
--    * 1.parameter re_a :  first regular expression of alternative
--
--    - 2.parameter re_b :  second regular expression of alternative
--
--    - returns : new regular expression

re_alt                                      :: (Ord a) => RE a -> RE a -> RE a
re_alt :: RE a -> RE a -> RE a
re_alt (RE_ZERO String
_)      RE a
e2                  = RE a
e2
re_alt RE a
e1               (RE_ZERO String
_)         = RE a
e1
re_alt (RE_ALT RE a
e11 RE a
e12) RE a
e2                  = RE a -> RE a -> RE a
forall a. Ord a => RE a -> RE a -> RE a
re_alt RE a
e11 (RE a -> RE a -> RE a
forall a. Ord a => RE a -> RE a -> RE a
re_alt RE a
e12 RE a
e2)  -- is right assoc
re_alt RE a
e1               e2 :: RE a
e2@(RE_ALT RE a
e21 RE a
e22)
    | RE a
e1 RE a -> RE a -> Bool
forall a. Eq a => a -> a -> Bool
== RE a
e21                             = RE a
e2             -- duplicates removed, the effective rule
    | RE a
e1 RE a -> RE a -> Bool
forall a. Ord a => a -> a -> Bool
>  RE a
e21                             = RE a -> RE a -> RE a
forall a. Ord a => RE a -> RE a -> RE a
re_alt RE a
e21 (RE a -> RE a -> RE a
forall a. Ord a => RE a -> RE a -> RE a
re_alt RE a
e1 RE a
e22)  -- sort alternatives
    | Bool
otherwise                             = RE a -> RE a -> RE a
forall a. RE a -> RE a -> RE a
RE_ALT RE a
e1 RE a
e2
re_alt RE a
e1               RE a
e2
    | RE a
e1 RE a -> RE a -> Bool
forall a. Eq a => a -> a -> Bool
== RE a
e2                              = RE a
e2             -- simplification, the effective rule
    | RE a
e1 RE a -> RE a -> Bool
forall a. Ord a => a -> a -> Bool
>  RE a
e2                              = RE a -> RE a -> RE a
forall a. Ord a => RE a -> RE a -> RE a
re_alt RE a
e2 RE a
e1   -- sort alts for unique repr.
    | Bool
otherwise                             = RE a -> RE a -> RE a
forall a. RE a -> RE a -> RE a
RE_ALT RE a
e1 RE a
e2



-- ------------------------------------------------------------


-- |
-- Checks if a regular expression matches the empty sequence.
--
-- nullable e == [] `in` L(e)
--
-- This check indicates if a regular expression fits to a sentence or not.
--
--    * 1.parameter re :  regular expression to be checked
--
--    - returns : true if regular expression matches the empty sequence,
--                otherwise false

nullable                ::  RE a -> Bool
nullable :: RE a -> Bool
nullable (RE_ZERO String
_)    = Bool
False
nullable RE a
RE_UNIT        = Bool
True
nullable (RE_SYM a
_)     = Bool
False
nullable (RE_REP RE a
_)     = Bool
True
nullable (RE_PLUS RE a
e)    = RE a -> Bool
forall a. RE a -> Bool
nullable RE a
e
nullable (RE_OPT RE a
_)     = Bool
True
nullable (RE_SEQ RE a
e RE a
f)   = RE a -> Bool
forall a. RE a -> Bool
nullable RE a
e Bool -> Bool -> Bool
&& RE a -> Bool
forall a. RE a -> Bool
nullable RE a
f
nullable (RE_ALT RE a
e RE a
f)   = RE a -> Bool
forall a. RE a -> Bool
nullable RE a
e Bool -> Bool -> Bool
|| RE a -> Bool
forall a. RE a -> Bool
nullable RE a
f
nullable RE a
RE_DOT         = Bool
False


-- |
-- Derives a regular expression with respect to one symbol.
--
-- L(delta e x) = x \ L(e)
--
--    * 1.parameter re :  regular expression to be derived
--
--    - 2.parameter sym :  the symbol on which the regular expression is applied
--
--    - returns : the derived regular expression

delta :: (Ord a, Show a) => RE a -> a -> RE a
delta :: RE a -> a -> RE a
delta RE a
re a
x = case RE a
re of
        RE_ZERO String
_               -> RE a
re                                   -- re_zero m
        RE a
RE_UNIT                 -> String -> RE a
forall a. String -> RE a
re_zero (String
"Symbol " String -> ShowS
forall a. [a] -> [a] -> [a]
++ a -> String
forall a. Show a => a -> String
show a
x String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" unexpected.")
        RE_SYM a
sym
                | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
sym      -> RE a
forall a. RE a
re_unit
                | Bool
otherwise     -> String -> RE a
forall a. String -> RE a
re_zero (String
"Symbol " String -> ShowS
forall a. [a] -> [a] -> [a]
++ a -> String
forall a. Show a => a -> String
show a
sym String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" expected, but symbol " String -> ShowS
forall a. [a] -> [a] -> [a]
++ a -> String
forall a. Show a => a -> String
show a
x String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" found.")
        RE_REP  RE a
e               -> RE a -> RE a -> RE a
forall a. RE a -> RE a -> RE a
re_seq (RE a -> a -> RE a
forall a. (Ord a, Show a) => RE a -> a -> RE a
delta RE a
e a
x) RE a
re                -- (re_rep e)
        RE_PLUS RE a
e               -> RE a -> RE a -> RE a
forall a. RE a -> RE a -> RE a
re_seq (RE a -> a -> RE a
forall a. (Ord a, Show a) => RE a -> a -> RE a
delta RE a
e a
x) (RE a -> RE a
forall a. RE a -> RE a
re_rep RE a
e)
        RE_OPT  RE a
e               -> RE a -> a -> RE a
forall a. (Ord a, Show a) => RE a -> a -> RE a
delta RE a
e a
x
        RE_SEQ  RE a
e RE a
f
                | RE a -> Bool
forall a. RE a -> Bool
nullable RE a
e    -> RE a -> RE a -> RE a
forall a. Ord a => RE a -> RE a -> RE a
re_alt (RE a -> RE a -> RE a
forall a. RE a -> RE a -> RE a
re_seq (RE a -> a -> RE a
forall a. (Ord a, Show a) => RE a -> a -> RE a
delta RE a
e a
x) RE a
f) (RE a -> a -> RE a
forall a. (Ord a, Show a) => RE a -> a -> RE a
delta RE a
f a
x)
                | Bool
otherwise     -> RE a -> RE a -> RE a
forall a. RE a -> RE a -> RE a
re_seq (RE a -> a -> RE a
forall a. (Ord a, Show a) => RE a -> a -> RE a
delta RE a
e a
x) RE a
f
        RE_ALT  RE a
e RE a
f             -> RE a -> RE a -> RE a
forall a. Ord a => RE a -> RE a -> RE a
re_alt (RE a -> a -> RE a
forall a. (Ord a, Show a) => RE a -> a -> RE a
delta RE a
e a
x) (RE a -> a -> RE a
forall a. (Ord a, Show a) => RE a -> a -> RE a
delta RE a
f a
x)
        RE a
RE_DOT                  -> RE a
forall a. RE a
re_unit


-- |
-- Derives a regular expression with respect to a sentence.
--
--    * 1.parameter re :  regular expression
--
--    - 2.parameter s :  sentence to which the regular expression is applied
--
--    - returns : the derived regular expression

matches :: (Ord a, Show a) => RE a -> [a] -> RE a
matches :: RE a -> [a] -> RE a
matches RE a
e = (RE a -> a -> RE a) -> RE a -> [a] -> RE a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' RE a -> a -> RE a
forall a. (Ord a, Show a) => RE a -> a -> RE a
delta RE a
e


-- |
-- Checks if an input matched a regular expression. The function should be
-- called after matches.
--
-- Was the sentence used in @matches@ in the language of the regular expression?
-- -> matches e s == s `in` L(e)?
--
--    * 1.parameter re :  the derived regular expression
--
--    - returns : empty String if input matched the regular expression, otherwise
--               an error message is returned

checkRE :: (Eq a, Show a) => RE a -> String
checkRE :: RE a -> String
checkRE (RE a
RE_UNIT)       = String
""
checkRE (RE_ZERO String
m)     = String
m
checkRE RE a
re
        | RE a -> Bool
forall a. RE a -> Bool
nullable RE a
re   = String
""
        | Bool
otherwise     = String
"Input must match " String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
forall a. (Eq a, Show a) => RE a -> String
printRE RE a
re



-- ------------------------------------------------------------



-- |
-- Constructs a string representation of a regular expression.
--
--    * 1.parameter re :  a regular expression
--
--    - returns : the string representation of the regular expression

printRE :: (Eq a, Show a) => RE a -> String
printRE :: RE a -> String
printRE RE a
re'
    = String
"( " String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
forall a. (Show a, Eq a) => RE a -> String
printRE1 RE a
re' String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" )"
      where
      -- printRE1 :: (Eq a, Show a) => RE a -> String
      printRE1 :: RE a -> String
printRE1 RE a
re = case RE a
re of
          RE_ZERO String
m                             -> String
"ERROR: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
m
          RE a
RE_UNIT                               -> String
""
          RE_SYM a
sym                            -> a -> String
forall a. Show a => a -> String
show a
sym
          RE a
RE_DOT                                -> String
"."
          RE_REP RE a
e
              | RE a -> Bool
forall a. RE a -> Bool
isSingle RE a
e                      -> RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"*"
              | Bool
otherwise                       -> String
"(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")*"
          RE_PLUS RE a
e
              | RE a -> Bool
forall a. RE a -> Bool
isSingle RE a
e                      -> RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"+"
              | Bool
otherwise                       -> String
"(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")+"
          RE_OPT RE a
e
              | RE a -> Bool
forall a. RE a -> Bool
isSingle RE a
e                      -> RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"?"
              | Bool
otherwise                       -> String
"(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")?"
          RE_SEQ RE a
e1 (RE_REP RE a
e2)
              | RE a
e1 RE a -> RE a -> Bool
forall a. Eq a => a -> a -> Bool
== RE a
e2                        -> RE a -> String
printRE1 (RE a -> RE a
forall a. RE a -> RE a
RE_PLUS RE a
e1)
          RE_SEQ RE a
e1 (RE_SEQ (RE_REP RE a
e2) RE a
e3)
              | RE a
e1 RE a -> RE a -> Bool
forall a. Eq a => a -> a -> Bool
== RE a
e2                        -> RE a -> String
printRE1 (RE a -> RE a -> RE a
forall a. RE a -> RE a -> RE a
RE_SEQ (RE a -> RE a
forall a. RE a -> RE a
RE_PLUS RE a
e1) RE a
e3)
          RE_SEQ RE a
e RE a
f
              | RE a -> Bool
forall a. RE a -> Bool
isAlt RE a
e  Bool -> Bool -> Bool
&& Bool -> Bool
not (RE a -> Bool
forall a. RE a -> Bool
isAlt RE a
f)       -> String
"(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
") , " String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
f
              | Bool -> Bool
not (RE a -> Bool
forall a. RE a -> Bool
isAlt RE a
e) Bool -> Bool -> Bool
&& RE a -> Bool
forall a. RE a -> Bool
isAlt RE a
f        -> RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" , (" String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
f String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"
              | RE a -> Bool
forall a. RE a -> Bool
isAlt RE a
e  Bool -> Bool -> Bool
&& RE a -> Bool
forall a. RE a -> Bool
isAlt RE a
f             -> String
"(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
") , (" String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
f String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"
              | Bool
otherwise                       -> RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" , " String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
f
          RE_ALT RE a
RE_UNIT RE a
f                      -> RE a -> String
printRE1 (RE a -> RE a
forall a. RE a -> RE a
RE_OPT RE a
f)
          RE_ALT RE a
e RE a
f
              | RE a -> Bool
forall a. Eq a => RE a -> Bool
isSeq RE a
e  Bool -> Bool -> Bool
&& Bool -> Bool
not (RE a -> Bool
forall a. Eq a => RE a -> Bool
isSeq RE a
f)       -> String
"(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
") | " String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
f
              | Bool -> Bool
not (RE a -> Bool
forall a. Eq a => RE a -> Bool
isSeq RE a
e) Bool -> Bool -> Bool
&& RE a -> Bool
forall a. Eq a => RE a -> Bool
isSeq RE a
f        -> RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" | (" String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
f String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"
              | RE a -> Bool
forall a. Eq a => RE a -> Bool
isSeq RE a
e  Bool -> Bool -> Bool
&& RE a -> Bool
forall a. Eq a => RE a -> Bool
isSeq RE a
f             -> String
"(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
") | (" String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
f String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"
              | Bool
otherwise                       -> RE a -> String
printRE1 RE a
e String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" | " String -> ShowS
forall a. [a] -> [a] -> [a]
++ RE a -> String
printRE1 RE a
f


      isSingle :: RE a -> Bool
      isSingle :: RE a -> Bool
isSingle (RE_ZERO String
_)    = Bool
True
      isSingle RE a
RE_UNIT        = Bool
True
      isSingle (RE_SYM a
_)     = Bool
True
      isSingle RE a
_              = Bool
False


      isSeq :: (Eq a) => RE a -> Bool
      isSeq :: RE a -> Bool
isSeq (RE_SEQ RE a
e1 (RE_REP RE a
e2))
          | RE a
e1 RE a -> RE a -> Bool
forall a. Eq a => a -> a -> Bool
== RE a
e2          = Bool
False  -- is transformed back into RE_PLUS
      isSeq (RE_SEQ RE a
_ RE a
_)      = Bool
True
      isSeq RE a
_                 = Bool
False


      isAlt :: RE a -> Bool
      isAlt :: RE a -> Bool
isAlt (RE_ALT RE a
RE_UNIT RE a
_)= Bool
False  -- is transformed back into a RE_OPT
      isAlt (RE_ALT RE a
_ RE a
_)      = Bool
True
      isAlt RE a
_                 = Bool
False