Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
Regular-expressions extended with fixpoints for context-free powers.
Some examples are in RERE.Examples module.
Synopsis
- data RE a
- ch_ :: Char -> RE a
- (\/) :: Ord a => RE a -> RE a -> RE a
- star_ :: RE a -> RE a
- let_ :: Ord a => Name -> RE a -> RE (Var a) -> RE a
- fix_ :: Ord a => Name -> RE (Var a) -> RE a
- (>>>=) :: Ord b => RE a -> (a -> RE b) -> RE b
- string_ :: Ord a => String -> RE a
- nullable :: RE a -> Bool
- derivative :: Char -> RE Void -> RE Void
- compact :: Ord a => RE a -> RE a
- size :: RE a -> Int
- match :: RE Void -> String -> Bool
- generate :: Int -> Int -> RE Void -> Maybe (Gen String)
- data Var a
- unvar :: r -> (a -> r) -> Var a -> r
- data Name
- type CFG n a = Vec n (CFGBase n a)
- type CFGBase n a = RE (Either (Fin n) a)
- cfgToRE :: (SNatI n, Ord a) => Vec (S n) Name -> CFG (S n) a -> RE a
- data RR s
- matchR :: RE Void -> String -> Bool
- matchDebugR :: RE Void -> String -> IO ()
- data RST s
- matchST :: RE Void -> String -> Bool
- matchDebugST :: RE Void -> String -> IO ()
- type CharClasses = Set Char
- charClasses :: RE a -> CharClasses
- classOfChar :: CharClasses -> Char -> Char
- putLatex :: RE Void -> IO ()
- putLatexTrace :: RE Void -> String -> IO ()
- putLatexCFG :: Vec n Name -> CFG n Void -> IO ()
Regular expressions with fixpoints
Regular expression with fixed point.
Null | |
Full | |
Eps | |
Ch CharSet | |
App (RE a) (RE a) | |
Alt (RE a) (RE a) | |
Star (RE a) | |
Var a | |
Let Name (RE a) (RE (Var a)) | |
Fix Name (RE (Var a)) |
Instances
Monad RE Source # | |
Functor RE Source # | |
Applicative RE Source # | |
Foldable RE Source # | |
Defined in RERE.Type fold :: Monoid m => RE m -> m # foldMap :: Monoid m => (a -> m) -> RE a -> m # foldr :: (a -> b -> b) -> b -> RE a -> b # foldr' :: (a -> b -> b) -> b -> RE a -> b # foldl :: (b -> a -> b) -> b -> RE a -> b # foldl' :: (b -> a -> b) -> b -> RE a -> b # foldr1 :: (a -> a -> a) -> RE a -> a # foldl1 :: (a -> a -> a) -> RE a -> a # elem :: Eq a => a -> RE a -> Bool # maximum :: Ord a => RE a -> a # | |
Traversable RE Source # | |
Eq a => Eq (RE a) Source # | |
Ord a => Ord (RE a) Source # | |
Show a => Show (RE a) Source # | |
Ord a => IsString (RE a) Source # | |
Defined in RERE.Type fromString :: String -> RE a # | |
Ord a => Semigroup (RE a) Source # | |
(Absurd a, Ord a) => Arbitrary (RE a) Source # | |
Smart constructors
Operations
nullable :: RE a -> Bool Source #
Whether the regular expression accepts empty string, or whether the formal language contains empty string.
>>>
nullable Eps
True
>>>
nullable (ch_ 'c')
False
derivative :: Char -> RE Void -> RE Void Source #
Derivative of regular exression to respect of character.
is \(D_c(r)\).derivative
c r
compact :: Ord a => RE a -> RE a Source #
Re-apply smart constructors on RE
structure,
thus potentially making it smaller.
This function is slow.
Matching
match :: RE Void -> String -> Bool Source #
Match string by iteratively differentiating the regular expression.
This version is slow, consider using matchR
.
Generation
Generate strings.
>>>
runGen 42 $ generate 10 10 $ star_ (ch_ 'a')
"aaa"
>>>
runGen 44 $ generate 10 10 $ star_ (ch_ 'a')
"aaaaaaaaaa"
Variables
Instances
Functor Var Source # | |
Foldable Var Source # | |
Defined in RERE.Var fold :: Monoid m => Var m -> m # foldMap :: Monoid m => (a -> m) -> Var a -> m # foldr :: (a -> b -> b) -> b -> Var a -> b # foldr' :: (a -> b -> b) -> b -> Var a -> b # foldl :: (b -> a -> b) -> b -> Var a -> b # foldl' :: (b -> a -> b) -> b -> Var a -> b # foldr1 :: (a -> a -> a) -> Var a -> a # foldl1 :: (a -> a -> a) -> Var a -> a # elem :: Eq a => a -> Var a -> Bool # maximum :: Ord a => Var a -> a # | |
Traversable Var Source # | |
Eq a => Eq (Var a) Source # | |
Ord a => Ord (Var a) Source # | |
Show a => Show (Var a) Source # | |
IsString a => IsString (Var a) Source # | |
Defined in RERE.Var fromString :: String -> Var a # |
Context-free grammars
cfgToRE :: (SNatI n, Ord a) => Vec (S n) Name -> CFG (S n) a -> RE a Source #
Convert CFG
(with names for productions) into RE
.
Note: the start symbol have to be last equation.
>>>
let a = Eps \/ ch_ 'a' <> Var (Left FZ)
>>>
let b = Eps \/ ch_ 'b' <> Var (Left (FS FZ))
>>>
let cfg = b ::: a ::: VNil
[ begin{aligned} {mathit{b}} &= {varepsilon}cupmathtt{b}{mathit{a}} -- {mathit{a}} &= {varepsilon}cupmathtt{a}{mathit{b}} -- end{aligned}
Faster matching
Ref
Knot-tied recursive regular expression.
ST
Knot-tied recursive regular expression.
Character classes
type CharClasses = Set Char Source #
Character classes are represented by partition lower bounds.
charClasses :: RE a -> CharClasses Source #
Character classes.
We can partition Char
so characters in each part,
affect the given regular expression in the same way.
If we do some kind of memoising, we can map all characters
to classOfChar
, making everything smaller.
classOfChar :: CharClasses -> Char -> Char Source #
Map char to the representer of a class.