BNF.md

BNF Grammar of Regular Expressions

Following the precedence rules given previously, a BNF grammar for Perl-style regular expressions can be constructed as follows.

• <RE> ::= <union> | <simple-RE>
• <union> ::= <RE> "|" <simple-RE>
• <simple-RE> ::= <concatenation> | <basic-RE>
• <concatenation> ::= <simple-RE> <basic-RE>
• <basic-RE> ::= <star> | <plus> | <elementary-RE>
• <star> ::= <elementary-RE> "*"
• <plus> ::= <elementary-RE> "+"
• <elementary-RE> ::= <group> | <any> | <eos> | <char> | <set>
• <group> ::= "(" <RE> ")"
• <any> ::= "."
• <eos> ::= "$"
• <char> ::= any non metacharacter | "\" metacharacter
• <set> ::= <positive-set> | <negative-set>
• <positive-set> ::= "[" <set-items> "]"
• <negative-set> ::= "[^" <set-items> "]"
• <set-items> ::= <set-item> | <set-item> <set-items>
• <set-items> ::= <range> | <char>
• <range> ::= <char> "-" <char>

regex.hs

data RegexTop

data Regex
  = Term RegexTerm
  | StartAnchor Regex
  | EndAnchor Regex
  | Repeat Int (Maybe Int) Bool Regex
  | Or Regex Regex
  | FollowedBy Regex Regex
  deriving(Show, Eq)

data RegexTerm
  = OneOf [Choose]
  | NotOneOf [Choose]
  | Literal RegexLiteral

data RegexLiteral
  = RegexChar Char
  | RegexSpecialChar SpecialChar
  | Wildcard

data Choose
 = ChooseLiteral RegexLiteral
 | ChooseCharRange Char Char
  deriving(Show, Eq)

data SpecialChar
 = Whitespace
 | Number
 | AlphaNumeric
 | OctalEscape Char
 | HexadecimalEscape Char
  deriving(Show, Eq)