Stability | experimental |
---|---|

Maintainer | Sebastian Fischer <mailto:sebf@informatik.uni-kiel.de> |

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.

- newtype RegExp c = RegExp (forall w. Semiring w => RegW w c)
- data RegW w c = RegW {}
- final :: Semiring w => RegW w c -> w
- data Reg w c
- class Semiring w => Weight a b w where
- symWeight :: (a -> w) -> b -> w

- defaultSymWeight :: (a -> w) -> a -> w
- weighted :: Weight a b w => RegW w a -> RegW w b
- eps :: RegExp c
- epsW :: Semiring w => RegW w c
- char :: Char -> RegExp Char
- sym :: (Eq c, Show c) => c -> RegExp c
- quote :: Char -> String
- psym :: String -> (c -> Bool) -> RegExp c
- symW :: Semiring w => String -> (c -> w) -> RegW w c
- anySym :: RegExp c
- noMatch :: RegExp c
- alt :: RegExp c -> RegExp c -> RegExp c
- altW :: Semiring w => RegW w c -> RegW w c -> RegW w c
- seq_ :: RegExp c -> RegExp c -> RegExp c
- seqW :: Semiring w => RegW w c -> RegW w c -> RegW w c
- rep :: RegExp c -> RegExp c
- repW :: Semiring w => RegW w c -> RegW w c
- rep1 :: RegExp c -> RegExp c
- opt :: RegExp c -> RegExp c
- brep :: (Int, Int) -> RegExp c -> RegExp c
- regW :: Semiring w => RegExp c -> RegW w c
- acceptFull :: RegExp c -> [c] -> Bool
- acceptPartial :: RegExp c -> [c] -> Bool
- matchingCount :: Num a => RegExp c -> [c] -> a
- fullMatch :: Weight a b w => RegExp a -> [b] -> w
- partialMatch :: Weight a b w => RegExp a -> [b] -> w
- 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

# Documentation

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

.

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

Matches the empty word. `eps`

has no direct string representation
but is used to implement other constructs such as optional
components like `a?`

.

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

Matches either of two regular expressions. For example `a+b`

matches either the character `a`

or the character `b`

.

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

Matches the sequence of two regular expressions. For example the
regular expressions `ab`

matches the word `ab`

.

rep :: RegExp c -> RegExp cSource

Matches zero or more occurrences of the given regular
expression. For example `a*`

matches the character `a`

zero or
more times.

rep1 :: RegExp c -> RegExp cSource

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 cSource

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 cSource

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

.

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

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

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

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

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

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

ping the word with positions.

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