Regex BNF Grammar

Question

Is there any BNF grammar for regular expression?

Ablation

Answer 1

You can see one for Perl regexp (displayed a little more in detail here, as posted by edg)

Galloon

This answer has been mentioned here #69197182 – Bolus

@XaviMontero 13 years later, I will follow your post (referencing Robert Cameron's study) with interest. Does Wiktor Stribiżew's comment adequately address your question? – Galloon

It did! (specially after Wiktor converted the comment to a fully-documented answer) – Bolus

Answer 2

To post them on-site:

CMPT 384 Lecture Notes Robert D. Cameron November 29 - December 1, 1999

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>

via VonC.

--- Knud van Eeden --- 21 October 2003 - 03:22 am --------------------

PERL:Search/Replace:Regular Expression:Backus Naur Form:What is possible BNF for regular expression?

expression = term

             term | expression

term = factor

       factor term

factor = atom

         atom metacharacter

atom = character

       .

       ( expression )

       [ characterclass ]

       [ ^ characterclass ]

       { min }

       { min ,  }

       { min , max }

characterclass = characterrange

                 characterrange characterclass

characterrange = begincharacter

                 begincharacter - endcharacter

begincharacter = character

endcharacter = character

character =

            anycharacterexceptmetacharacters

            \ anycharacterexceptspecialcharacters

metacharacter = ?

                * {=0 or more, greedy}

                *? {=0 or more, non-greedy}

                + {=1 or more, greedy}

                +? {=1 or more, non-greedy}

                ^ {=begin of line character}

                $ {=end of line character}

                $` {=the characters to the left of the match}

                $' {=the characters to the right of the match}

                $& {=the characters that are matched}

                \t {=tab character}

                \n {=newline character}

                \r {=carriage return character}

                \f {=form feed character}

                \cX {=control character CTRL-X}

                \N {=the characters in Nth tag (if on match side)}

                $N{=the characters in Nth tag (if not on match side)}

                \NNN {=octal code for character NNN}

                \b {=match a 'word' boundary}

                \B {=match not a 'word' boundary}

                \d {=a digit, [0-9]}

                \D {=not a digit, [^0-9]}

                \s {=whitespace, [ \t\n\r\f]}

                \S {=not a whitespace, [^ \t\n\r\f]}

                \w {='word' character, [a-zA-Z0-9_]}

                \W {=not a 'word' character, [^a-zA-Z0-9_]}

                \Q {=put a quote (de-meta) on characters, until \E}

                \U {=change characters to uppercase, until \E}

                \L {=change characters to uppercase, until \E}

min = integer

max = integer

integer = digit

          digit integer

anycharacter = ! " # $ % & ' ( ) * + , - . / :
               ; < = > ? @ [ \ ] ^ _ ` { | } ~
               0 1 2 3 4 5 6 7 8 9
               A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
               a b c d e f g h i j k l m n o p q r s t u v w x y z

---

[book: see also: Bucknall, Julian - the Tomes of Delphi: Algorithms 
and Datastructures - p. 37 - 'Using regular expressions' - 
http://www.amazon.com/exec/obidos/tg/detail/-
/1556227361/qid=1065748783/sr=1-1/ref=sr_1_1/002-0122962-7851254?
v=glance&s=books]

---
---

Internet: see also:

---

Compiler: Grammar: Expression: Regular: Which grammar defines set of 
all regular expressions? [BNF]
http://www.faqts.com/knowledge_base/view.phtml/aid/25950/fid/1263

---

Perl Regular Expression: Quick Reference 1.05
http://www.erudil.com/preqr.pdf

---

Top: Computers: Programming: Languages: Regular Expressions: Perl
http://dmoz.org/Computers/Programming/Languages/Regular_Expressions/Per
l/

---

TSE: Search/Replace:Regular Expression:Backus Naur Form:What is 
possible BNF for regular expression?
http://www.faqts.com/knowledge_base/view.phtml/aid/25714/fid/1236

---

Delphi: Search: Regular expression: Create: How to create a regular 
expression parser in Delphi?
http://www.faqts.com/knowledge_base/view.phtml/aid/25645/fid/175

---

Delphi: Search: Regular expression: How to add regular expression 
searching to Delphi? [Systools]
http://www.faqts.com/knowledge_base/view.phtml/aid/25295/fid/175

----------------------------------------------------------------------

via Ed Guinness.

Sweepstakes

I'm not sure this works. It looks like it would allow {0,} as a regex. You should only be allowed to add {m, n} to an expression, not as an atom on its own. (Unfortunately, fixing that makes the grammar left-recursive.) – Fieldstone

Answer 3

http://web.archive.org/web/20090129224504/http://faqts.com/knowledge_base/view.phtml/aid/25718/fid/200

Housewifery