RERE · rere-0.2.0.2 · horizon-platform

Regular expressions with fixpoints

1 declaration

datadata RE a

#

Regular expression with fixed point.

Constructors

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))

Instances11Monad, Functor, Applicative, Foldable, Traversable, Eq, …

Monad REDefined in rere-0.2.0.2 · RERE.Type
Functor REDefined in rere-0.2.0.2 · RERE.Type
Applicative REDefined in rere-0.2.0.2 · RERE.Type
Foldable REDefined in rere-0.2.0.2 · RERE.Type
Traversable REDefined in rere-0.2.0.2 · RERE.Type
Eq a => Eq (RE a)Defined in rere-0.2.0.2 · RERE.Type
Ord a => Ord (RE a)Defined in rere-0.2.0.2 · RERE.Type
Show a => Show (RE a)Defined in rere-0.2.0.2 · RERE.Type
Ord a => IsString (RE a)Defined in rere-0.2.0.2 · RERE.Type
Ord a => Semigroup (RE a)Defined in rere-0.2.0.2 · RERE.Type
(Absurd a, Ord a) => Arbitrary (RE a)Defined in rere-0.2.0.2 · RERE.Type

Smart constructors

valuech_ :: Char -> RE a

#

Smart Ch, as it takes Char argument.

value(\/) :: Ord a => RE a -> RE a -> RE a

#

Smart Alt.

valuestar_ :: RE a -> RE a

#

Smart Star.

valuelet_ :: Ord a => Name -> RE a -> RE (Var a) -> RE a

#

Smart Let

valuefix_ :: Ord a => Name -> RE (Var a) -> RE a

#

Smart Fix.

value(>>>=) :: Ord b => RE a -> (a -> RE b) -> RE b

#

Variable substitution.

valuestring_ :: Ord a => String -> RE a

#

Construct literal String regex.

Operations

valuenullable :: RE a -> Bool

#

Whether the regular expression accepts empty string, or whether the formal language contains empty string.

Example1 expression

>>> nullable EpsTrue

Example1 expression

>>> nullable (ch_ 'c')False

valuederivative :: Char -> RE Void -> RE Void

#

Derivative of regular exression to respect of character. derivative c r is D_c(r).

valuecompact :: Ord a => RE a -> RE a

#

Re-apply smart constructors on RE structure, thus potentially making it smaller.

This function is slow.

valuesize :: RE a -> Int

#

Size of RE. Counts constructors.

Matching

valuematch :: RE Void -> String -> Bool

#

Match string by iteratively differentiating the regular expression.

This version is slow, consider using RERE.matchR.

Generation

valuegenerate

:: Int
star upper size
-> Int
fix unroll
-> RE Void
-> Maybe (Gen String)

#

Generate strings.

Example1 expression

>>> runGen 43 $ generate 10 10 $ star_ (ch_ 'a')"aaaaaaaaaa"

Example1 expression

>>> runGen 44 $ generate 10 10 $ star_ (ch_ 'a')"aaa"

Variables

3 declarations

datadata Var a

#

Var is essentially Maybe.

Constructors

B
bound
F a
free variable.

Instances7Functor, Foldable, Traversable, Eq, Ord, Show, …

Functor VarDefined in rere-0.2.0.2 · RERE.Var
Foldable VarDefined in rere-0.2.0.2 · RERE.Var
Traversable VarDefined in rere-0.2.0.2 · RERE.Var
Eq a => Eq (Var a)Defined in rere-0.2.0.2 · RERE.Var
Ord a => Ord (Var a)Defined in rere-0.2.0.2 · RERE.Var
Show a => Show (Var a)Defined in rere-0.2.0.2 · RERE.Var
IsString a => IsString (Var a)Defined in rere-0.2.0.2 · RERE.Var

valueunvar :: r -> (a -> r) -> Var a -> r

#

Analogue of maybe for Var.

datadata Name

#

Names carry information used in pretty-printing, but otherwise they all compare EQual.

Instances4Eq, Ord, Show, IsString

Eq NameDefined in rere-0.2.0.2 · RERE.Var
Ord NameDefined in rere-0.2.0.2 · RERE.Var
Show NameDefined in rere-0.2.0.2 · RERE.Var
IsString NameDefined in rere-0.2.0.2 · RERE.Var

Context-free grammars

3 declarations

typetype CFG (n :: Nat) a = Vec n (CFGBase n a)

#

Context-free grammar represented as n equations of RE (CFGBase) with n variables.

typetype CFGBase (n :: Nat) a = RE (Either (Fin n) a)

#

Single equation in context-free-grammar equation.

valuecfgToRE :: (SNatI n, Ord a) => Vec ('S n) Name -> CFG ('S n) a -> RE a

#

Convert CFG (with names for productions) into RE. Note: the start symbol have to be last equation.

Example3 expressions

>>> 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

0 declarations

Ref

datadata RR s

#

Knot-tied recursive regular expression.

Instances1Show

Show (RR s)Defined in rere-0.2.0.2 · RERE.Ref

valuematchR :: RE Void -> String -> Bool

#

Convert RE to RR and then match.

Significantly faster than match.

valuematchDebugR :: RE Void -> String -> IO ()

#

Match and print final RR + stats.

ST

datadata RST s

#

Knot-tied recursive regular expression.

Instances1Show

Show (RST s)Defined in rere-0.2.0.2 · RERE.ST

valuematchST :: RE Void -> String -> Bool

#

Convert RE to RST and then match.

Significantly faster than match.

valuematchDebugST :: RE Void -> String -> IO ()

#

Match and print final RR + stats.

Character classes

3 declarations

typetype CharClasses = Set Char

#

Character classes are represented by partition lower bounds.

valuecharClasses :: RE a -> CharClasses

#

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.

valueclassOfChar :: CharClasses -> Char -> Char

#

Map char to the representer of a class.

Pretty printing (as LaTeX)

3 declarations

valueputLatex :: RE Void -> IO ()

#

Pretty-print RE as LaTeX code.

valueputLatexTrace :: RE Void -> String -> IO ()

#

Run match variant, collect intermediate steps, and pretty-print that trace.

valueputLatexCFG :: Vec n Name -> CFG n Void -> IO ()

#

Pretty-print CFG given the names.