BNFC.Types.Regex

Tools to manipulate regular expressions.

Regular expressions

data Regex

Regular expressions are constructed over character classes.

Use smart constructors to ensure invariants.

Constructors

RChar CharClass

Atomic regular expression.

RAlts (List2 Regex)

Alternative/sum: List free of duplicates and RAlt. We use list instead of set to preserve the order given by the user. Empty list would mean empty language, but this is instead represented by the empty character class.

RMinus Regex Regex

Difference. Most lexer generators do not support difference in general, only at the level of character classes. LBNF has general difference, so it is represented here.

REps

Language of the empty word (empty sequence).

RSeqs (List2 Regex)

Sequence/product. List free of RSeq. Empty list is eps (language of the empty word).

RStar Regex

0 or more repetitions. Regex isn't RStar, RPlus, ROpt, RAlts [] nor REps.

RPlus Regex

1 or more repetitions. Regex isn't RStar, RPlus, ROpt, RAlts [] nor REps.

ROpt Regex

0 or 1 repetitions. Regex isn't RStar, RPlus, ROpt, RAlts [] nor REps.

Instances

Eq Regex

Defined in BNFC.Types.Regex

Methods

(==) :: Regex -> Regex -> Bool

(/=) :: Regex -> Regex -> Bool

Ord Regex

Defined in BNFC.Types.Regex

Methods

compare :: Regex -> Regex -> Ordering

(<) :: Regex -> Regex -> Bool

(<=) :: Regex -> Regex -> Bool

(>) :: Regex -> Regex -> Bool

(>=) :: Regex -> Regex -> Bool

max :: Regex -> Regex -> Regex

min :: Regex -> Regex -> Regex

Show Regex

Defined in BNFC.Types.Regex

Methods

showsPrec :: Int -> Regex -> ShowS

show :: Regex -> String

showList :: [Regex] -> ShowS

Satisfiable Regex

Defined in BNFC.Types.Regex

Methods

satisfiable :: Regex -> Bool

ReifyRegex Regex

Defined in BNFC.Check.Regex

Methods

reifyRegex :: Regex -> Reg

Print Regex

Defined in BNFC.Backend.Txt2Tags.Txt2Tags

Methods

prt :: Int -> Regex -> Doc ()

Print Regex

Defined in BNFC.Backend.Latex.Latex

Methods

prt :: Int -> Regex -> Doc ()

Print Regex

Defined in BNFC.Backend.Haskell.Lexer

Methods

prt :: Int -> Regex -> Doc ()

pattern REmpty :: Regex

pattern RAlt :: Regex -> Regex -> Regex

pattern RSeq :: Regex -> Regex -> Regex

nullable :: Regex -> Bool

Check if a regular expression is nullable (accepts the empty string).

class Satisfiable a where

Check if a regular expression matches at least one word.

For differences, this check may err on the positive side.

Methods

satisfiable :: a -> Bool

Instances

Satisfiable CharClassUnion

Defined in BNFC.Types.Regex

Methods

satisfiable :: CharClassUnion -> Bool

Satisfiable CharClass

Defined in BNFC.Types.Regex

Methods

satisfiable :: CharClass -> Bool

Satisfiable Regex

Defined in BNFC.Types.Regex

Methods

satisfiable :: Regex -> Bool

Character classes

data CharClass

Character classes are regular expressions that recognize character sequences of length exactly one. These are often distinguished from arbitrary regular expressions in lexer generators, e.g. in alex.

We represent character classes as a difference of unions of atomic character classes.

Semantics: ⟦ CMinus ccYes ccNo ⟧ = ⟦ ccYes ⟧ ⟦ ccNo ⟧

Constructors

CMinus

Fields

• ccYes :: CharClassUnion

  Character in question must be in one of these character classes.

• ccNo :: CharClassUnion

  Character in question must not be in one of these character classes. Must be empty if ccYes is empty.

Instances

Eq CharClass

Defined in BNFC.Types.Regex

Methods

(==) :: CharClass -> CharClass -> Bool

(/=) :: CharClass -> CharClass -> Bool

Ord CharClass

Defined in BNFC.Types.Regex

Methods

compare :: CharClass -> CharClass -> Ordering

(<) :: CharClass -> CharClass -> Bool

(<=) :: CharClass -> CharClass -> Bool

(>) :: CharClass -> CharClass -> Bool

(>=) :: CharClass -> CharClass -> Bool

max :: CharClass -> CharClass -> CharClass

min :: CharClass -> CharClass -> CharClass

Show CharClass

Defined in BNFC.Types.Regex

Methods

showsPrec :: Int -> CharClass -> ShowS

show :: CharClass -> String

showList :: [CharClass] -> ShowS

Satisfiable CharClass

Defined in BNFC.Types.Regex

Methods

satisfiable :: CharClass -> Bool

ReifyRegex CharClass

Defined in BNFC.Check.Regex

Methods

reifyRegex :: CharClass -> Reg

pattern CEmpty :: CharClass

pattern CC :: CharClassUnion -> CharClass

data CharClassUnion

Possibly overlapping union of character classes.

Constructors

CAny

Any character, LBNF char.

CAlt [CharClassAtom]

Any of the given (≥0) alternatives. List is free of duplicates.

Instances

Eq CharClassUnion

Defined in BNFC.Types.Regex

Methods

(==) :: CharClassUnion -> CharClassUnion -> Bool

(/=) :: CharClassUnion -> CharClassUnion -> Bool

Ord CharClassUnion

Defined in BNFC.Types.Regex

Methods

compare :: CharClassUnion -> CharClassUnion -> Ordering

(<) :: CharClassUnion -> CharClassUnion -> Bool

(<=) :: CharClassUnion -> CharClassUnion -> Bool

(>) :: CharClassUnion -> CharClassUnion -> Bool

(>=) :: CharClassUnion -> CharClassUnion -> Bool

max :: CharClassUnion -> CharClassUnion -> CharClassUnion

min :: CharClassUnion -> CharClassUnion -> CharClassUnion

Show CharClassUnion

Defined in BNFC.Types.Regex

Methods

showsPrec :: Int -> CharClassUnion -> ShowS

show :: CharClassUnion -> String

showList :: [CharClassUnion] -> ShowS

Semigroup CharClassUnion

Union of character class unions.

Defined in BNFC.Types.Regex

Methods

(<>) :: CharClassUnion -> CharClassUnion -> CharClassUnion

sconcat :: NonEmpty CharClassUnion -> CharClassUnion

stimes :: Integral b => b -> CharClassUnion -> CharClassUnion

Monoid CharClassUnion

Defined in BNFC.Types.Regex

Methods

mempty :: CharClassUnion

mappend :: CharClassUnion -> CharClassUnion -> CharClassUnion

mconcat :: [CharClassUnion] -> CharClassUnion

Satisfiable CharClassUnion

Defined in BNFC.Types.Regex

Methods

satisfiable :: CharClassUnion -> Bool

ReifyRegex CharClassUnion

Defined in BNFC.Check.Regex

Methods

reifyRegex :: CharClassUnion -> Reg

Print CharClassUnion

Defined in BNFC.Backend.Txt2Tags.Txt2Tags

Methods

prt :: Int -> CharClassUnion -> Doc ()

Print CharClassUnion

Defined in BNFC.Backend.Latex.Latex

Methods

prt :: Int -> CharClassUnion -> Doc ()

Print CharClassUnion

Defined in BNFC.Backend.Haskell.Lexer

Methods

prt :: Int -> CharClassUnion -> Doc ()

pattern CCEmpty :: CharClassUnion

data CharClassAtom

Atomic character class.

Constructors

CChar Char

A single character.

CDigit

0-9, LBNF digit.

CLower

Lower case character, LBNF lower.

CUpper

Upper case character, LBNF upper.

Instances

Eq CharClassAtom

Defined in BNFC.Types.Regex

Methods

(==) :: CharClassAtom -> CharClassAtom -> Bool

(/=) :: CharClassAtom -> CharClassAtom -> Bool

Ord CharClassAtom

Defined in BNFC.Types.Regex

Methods

compare :: CharClassAtom -> CharClassAtom -> Ordering

(<) :: CharClassAtom -> CharClassAtom -> Bool

(<=) :: CharClassAtom -> CharClassAtom -> Bool

(>) :: CharClassAtom -> CharClassAtom -> Bool

(>=) :: CharClassAtom -> CharClassAtom -> Bool

max :: CharClassAtom -> CharClassAtom -> CharClassAtom

min :: CharClassAtom -> CharClassAtom -> CharClassAtom

Show CharClassAtom

Defined in BNFC.Types.Regex

Methods

showsPrec :: Int -> CharClassAtom -> ShowS

show :: CharClassAtom -> String

showList :: [CharClassAtom] -> ShowS

Print CharClassAtom

Defined in BNFC.Backend.Txt2Tags.Txt2Tags

Methods

prt :: Int -> CharClassAtom -> Doc ()

Print CharClassAtom

Defined in BNFC.Backend.Latex.Latex

Methods

prt :: Int -> CharClassAtom -> Doc ()

Print CharClassAtom

Defined in BNFC.Backend.Haskell.Lexer

Methods

prt :: Int -> CharClassAtom -> Doc ()

Smart constructor for regular expressions.

rChar :: Char -> Regex

rSeq :: Regex -> Regex -> Regex

Simplifications included, but no distributivity.

rSeqs :: [Regex] -> Regex

rAlt :: Regex -> Regex -> Regex

rAlts :: [Regex] -> Regex

rMinus :: Regex -> Regex -> Regex

rStar :: Regex -> Regex

rPlus :: Regex -> Regex

rOpt :: Regex -> Regex

cAlt :: CharClass -> CharClass -> Regex

Disjunction of two character classes is either a character class again (RChar) or simply the disjunction (RAlt).

(p1 m1) ∪ (p2 m2) = (p1 ∪ p2) (m1 ∪ m2) if p1 ⊥ m2 and p2 ⊥ m1

cMinus :: CharClass -> CharClass -> Regex

Disjunction of two character classes is either a character class again (RChar) or simply the disjunction (RMinus).

(p1 m1) (0 m2) = p1 m1 (p1 m1) (p2 m2) = p1 (m1 ∪ p2) if p1 m2 = p1

Smart constructors for character classes.

cChar :: Char -> CharClass

Match given characters.

cAlts :: [Char] -> CharClass

Match any of the given characters.

cDigit :: CharClass

cLower :: CharClass

cUpper :: CharClass

cLetter :: CharClass

cAny :: CharClass

cAtom :: CharClassAtom -> CharClass

ccuMinus :: CharClassUnion -> CharClassUnion -> Either CharClass CharClassUnion

Smart constructor for CharClass from difference..

Mutually reduce: (A - B) = (A B) - (B A)

onlyOneChar :: CharClassUnion -> Bool

isEmpty :: CharClassUnion -> Bool