Text.RegExp.Internal

This module exports internal data types and matching functions. You do not need to import it unless you want to write your own matching algorithms.

Documentation

newtype RegExp c

Regular expressions are represented as values of type RegExp c where c is the character type of the underlying alphabet. Values of type RegExp c can be matched against lists of type [c].

Constructors

RegExp (forall w. Semiring w => RegW w c)

Instances

Eq (RegExp Char)

Show (RegExp Char)

IsString (RegExp Char)

data RegW w c

Constructors

RegW

Fields

active :: !Bool

empty :: !w

final_ :: !w

reg :: !(Reg w c)

Instances

Eq (RegW Bool Char)

Show (RegW Bool Char)

final :: Semiring w => RegW w c -> w

data Reg w c

Constructors

Eps

Sym String (c -> w)

Alt (RegW w c) (RegW w c)

Seq (RegW w c) (RegW w c)

Rep (RegW w c)

Instances

Eq (Reg Bool Char)

Show (Reg Bool Char)

class Semiring w => Weight a b w where

Methods

symWeight :: (a -> w) -> b -> w

Instances

Weight c c Bool

Weight c c Longest

Num a => Weight c c (Numeric a)

Weight c (Int, c) Leftmost

Weight c (Int, c) LeftLong

defaultSymWeight :: (a -> w) -> a -> w

weighted :: Weight a b w => RegW w a -> RegW w b

eps :: RegExp c

Matches the empty word. eps has no direct string representation but is used to implement other constructs such as optional components like a?.

epsW :: Semiring w => RegW w c

char :: Char -> RegExp Char

Matches the given character.

sym :: (Eq c, Show c) => c -> RegExp c

Matches the given symbol.

quote :: Char -> String

psym :: String -> (c -> Bool) -> RegExp c

Matches a symbol that satisfies the given predicate.

symW :: Semiring w => String -> (c -> w) -> RegW w c

anySym :: RegExp c

Matches an arbitrary symbol.

noMatch :: RegExp c

Does not match anything. noMatch is an identity for alt.

alt :: RegExp c -> RegExp c -> RegExp c

Matches either of two regular expressions. For example a+b matches either the character a or the character b.

altW :: Semiring w => RegW w c -> RegW w c -> RegW w c

seq_ :: RegExp c -> RegExp c -> RegExp c

Matches the sequence of two regular expressions. For example the regular expressions ab matches the word ab.

seqW :: Semiring w => RegW w c -> RegW w c -> RegW w c

rep :: RegExp c -> RegExp c

Matches zero or more occurrences of the given regular expression. For example a* matches the character a zero or more times.

repW :: Semiring w => RegW w c -> RegW w c

rep1 :: RegExp c -> RegExp c

Matches one or more occurrences of the given regular expression. For example a+ matches the character a one or more times.

opt :: RegExp c -> RegExp c

Matches the given regular expression or the empty word. Optional expressions are usually written a? but could also be written (|a), that is, as alternative between eps and a.

brep :: (Int, Int) -> RegExp c -> RegExp c

Matches a regular expression a given number of times. For example, the regular expression a{4,7} matches the character a four to seven times. If the minimal and maximal occurences are identical, one can be left out, that is, a{2} matches two occurrences of the character a.

Numerical bounds are implemented via translation into ordinary regular expressions. For example, a{4,7} is translated into aaaa(a(a(a)?)?)?.

regW :: Semiring w => RegExp c -> RegW w c

acceptFull :: RegExp c -> [c] -> Bool

Checks whether a regular expression matches the given word. For example, acceptFull (fromString "b|abc") "b" yields True because the first alternative of b|abc matches the string "b".

acceptPartial :: RegExp c -> [c] -> Bool

Checks whether a regular expression matches a subword of the given word. For example, acceptPartial (fromString "b") "abc" yields True because "abc" contains the substring "b".

matchingCount :: Num a => RegExp c -> [c] -> a

Computes in how many ways a word can be matched against a regular expression.

fullMatch :: Weight a b w => RegExp a -> [b] -> w

Matches a regular expression against a word computing a weight in an arbitrary semiring.

The symbols can have associated weights associated by the symWeight function of the Weight class. This function also allows to adjust the type of the used alphabet such that, for example, positional information can be taken into account by zipping the word with positions.

partialMatch :: Weight a b w => RegExp a -> [b] -> w

Matches a regular expression against substrings of a word computing a weight in an arbitrary semiring. Similar to fullMatch the Weight class is used to associate weights to the symbols of the regular expression.

matchW :: Semiring w => RegW w c -> [c] -> w

shiftW :: Semiring w => w -> RegW w c -> c -> RegW w c

shift :: Semiring w => w -> Reg w c -> c -> RegW w c