29

Is there any BNF grammar for regular expression?

3 Answers 3

23

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

3
  • This answer has been mentioned here stackoverflow.com/questions/69196682/… Sep 15, 2021 at 16:24
  • 1
    @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?
    – VonC
    Sep 15, 2021 at 18:50
  • It did! (specially after Wiktor converted the comment to a fully-documented answer) Sep 16, 2021 at 18:26
12

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.

1
  • 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.) Jun 12, 2023 at 16:59
7

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.