| Copyright | Copyright (C) 2008 Uwe Schmidt |
|---|---|
| License | MIT |
| Maintainer | Uwe Schmidt (uwe@fh-wedel.de) |
| Stability | experimental |
| Portability | portable |
| Safe Haskell | Safe |
| Language | Haskell98 |
Text.XML.HXT.DTDValidation.RE
Description
A module for regular expression matching based on derivatives of regular expressions.
The code was taken from Joe English (http://www.flightlab.com/~joe/sgml/validate.html). Tested and extended by Martin Schmidt.
Further references for the algorithm:
Janusz A. Brzozowski.
Derivatives of Regular Expressions. Journal of the ACM, Volume 11, Issue 4, 1964.
Mark Hopkins.
Regular Expression Package. Posted to comp.compilers, 1994. Available per FTP at ftp://iecc.com/pub/file/regex.tar.gz.
- data RE a
- re_unit :: RE a
- re_zero :: String -> RE a
- re_sym :: a -> RE a
- re_rep :: RE a -> RE a
- re_plus :: RE a -> RE a
- re_opt :: Ord a => RE a -> RE a
- re_seq :: RE a -> RE a -> RE a
- re_alt :: Ord a => RE a -> RE a -> RE a
- re_dot :: RE a
- checkRE :: (Eq a, Show a) => RE a -> String
- matches :: (Ord a, Show a) => RE a -> [a] -> RE a
- nullable :: RE a -> Bool
- printRE :: (Eq a, Show a) => RE a -> String
Documentation
Data type for regular expressions.
Constructs a regular expression for an empty sequence.
- returns : regular expression for an empty sequence
re_zero :: String -> RE a Source #
Constructs a regular expression for an empty set.
- 1.parameter errMsg : error message
- returns : regular expression for an empty set
Constructs a regular expression for accepting a symbol
- 1.parameter sym : the symbol to be accepted
- returns : regular expression for accepting a symbol
re_rep :: RE a -> RE a Source #
Constructs an optional repetition (*) of a regular expression
- 1.parameter re_a : regular expression to be repeted
- returns : new regular expression
re_plus :: RE a -> RE a Source #
Constructs a repetition (+) of a regular expression
- 1.parameter re_a : regular expression to be repeted
- returns : new regular expression
re_opt :: Ord a => RE a -> RE a Source #
Constructs an option (?) of a regular expression
- 1.parameter re_a : regular expression to be optional
- returns : new regular expression
re_seq :: RE a -> RE a -> RE a Source #
Constructs a sequence (,) of two regular expressions
- 1.parameter re_a : first regular expression in sequence
- 2.parameter re_b : second regular expression in sequence
- returns : new regular expression
re_alt :: Ord a => RE a -> RE a -> RE a Source #
Constructs an alternative (|) of two regular expressions
- 1.parameter re_a : first regular expression of alternative
- 2.parameter re_b : second regular expression of alternative
- returns : new regular expression
Constructs a regular expression for accepting any singel symbol
- returns : regular expression for accepting any singel symbol
checkRE :: (Eq a, Show a) => RE a -> String Source #
Checks if an input matched a regular expression. The function should be called after matches.
Was the sentence used in matches in the language of the regular expression?
-> matches e s == s `in` L(e)?
- 1.parameter re : the derived regular expression
- returns : empty String if input matched the regular expression, otherwise an error message is returned
matches :: (Ord a, Show a) => RE a -> [a] -> RE a Source #
Derives a regular expression with respect to a sentence.
- 1.parameter re : regular expression
- 2.parameter s : sentence to which the regular expression is applied
- returns : the derived regular expression
nullable :: RE a -> Bool Source #
Checks if a regular expression matches the empty sequence.
nullable e == [] `in` L(e)
This check indicates if a regular expression fits to a sentence or not.
- 1.parameter re : regular expression to be checked
- returns : true if regular expression matches the empty sequence, otherwise false