Language.HaLex.RegExp

Regular Expressions in Haskell.

Code Included in the Lecture Notes on Language Processing (with a functional flavour).

Data type with recursion pattern

data RegExp sy

Type of regular expressions.

Constructors

Empty

Empty Language

Epsilon

Empty String

Literal sy

Literals

Or (RegExp sy) (RegExp sy)

Disjuncion

Then (RegExp sy) (RegExp sy)

Sequence

Star (RegExp sy)

Repetition, possibly zero time

OneOrMore (RegExp sy)

One or more times (extended RegExp)

Optional (RegExp sy)

Optional (extended RegExp)

RESet [sy]

Set (extended RegExp)

Instances

Eq sy => Eq (RegExp sy)

Methods

(==) :: RegExp sy -> RegExp sy -> Bool

(/=) :: RegExp sy -> RegExp sy -> Bool

Read sy => Read (RegExp sy)

Methods

readsPrec :: Int -> ReadS (RegExp sy)

readList :: ReadS [RegExp sy]

readPrec :: ReadPrec (RegExp sy)

readListPrec :: ReadPrec [RegExp sy]

Show sy => Show (RegExp sy)

Pretty print of regular expressions.

Methods

showsPrec :: Int -> RegExp sy -> ShowS

show :: RegExp sy -> String

showList :: [RegExp sy] -> ShowS

cataRegExp :: (re, re, re -> re -> re, re -> re, sy -> re, re -> re -> re, re -> re, re -> re, [sy] -> re) -> RegExp sy -> re

Catamorphism induced by the RegExp inductive data type

Matching

matchesRE

Arguments

:: Eq sy

=> RegExp sy

(canonical) Regular Expression

-> [sy]

Input Symbols

-> Bool

Test whether a match can be found for the given regular expression in the given sequence of characters. The regular expression is assumed not to contain OneOrMore or Optional. See also matches'.

matches'

Arguments

:: Eq sy

=> RegExp sy

Regular Expression

-> [sy]

Input Symbols

-> Bool

Test whether a match can be found for the given regular expression in the given sequence of characters. The regular expression is allowed to contain OneOrMore or Optional.

Size

sizeRegExp

Arguments

:: RegExp sy

Regular Expression

-> Int

Size

Compute the size of a regular expression. We define the size of a regular expression as the number of occurrences of symbols of the alfabeth

Printing

showRE

Arguments

:: Show sy

=> RegExp sy

Regular Expression

-> [Char]

String-based Regular Expression

Print regular expression to String as a catamorphism. A straightforward (catamorphic) show function.

(it produces too many brackets, making it difficult to read or understand the expression)

Simplification

simplifyRegExp :: Eq sy => RegExp sy -> RegExp sy

Simplify regular expressions according to the algebra of regular expressions.

Normalization

extREtoRE :: RegExp sy -> RegExp sy

Rewrite extended regular expressions to plain regular expression. This means that the OneOrMore Optional and RESet constructors are normalized away.