How to create a regex equivalent to a BNF?

Question

I need to create a regular expression that is equivalent to the following BNF:

<SEQ> ::= <DIG><SEQ> | <DIG>
<DIG> ::= 0|1

I tried to create a Python code with the regex library:

import re

reg = r'[0-2]'

print(reg)

It was a test, but I couldn’t actually create a regex that was equivalent to BNF.

Answer 1

If the idea is to generate a regex equivalent to this BNF, then it would be something like this:

import re

r = re.compile('^[01]+$')

print(r.match('010100111')) # retorna um objeto Match
print(r.match('010120111')) # None

The regex uses the markers ^ and $ which indicate respectively the start and end of the string.

Then we have the character class [01] which means "one digit 0 or 1" and the quantifier + which indicates one or more occurrences. Thus, regex recognizes a sequence of zeros and ones of minimum size 1 and no maximum limit (exactly the same as BNF represents).

In the example above, we can see that if the string only has zeros and ones, a match, and if you have any different character, you find nothing.

Note: I could even use [0-1] instead of [01], but in this case it is the same ("a digit from 0 to 1" and "the digit 0 or 1" is basically the same thing).

---

Before the editing and the comments, it was not clear that the goal was to generate the above regex. Anyway, I will keep the version that tried to respond to original question.

If given a BNF, you want to create a sequence that matches the definition, then regex nay is the right tool for the task.

In case, you would have to implement at hand, or use some ready lib. An alternative is to use the NLTK. As I don’t use this kind of thing much, I ended up taking an example from here and adapting to your case:

from nltk import CFG
from nltk.parse.generate import generate

# cria a gramática a partir da BNF
grammar = CFG.fromstring(""" SEQ -> DIG SEQ | DIG
    DIG -> "0" | "1" """)

# gera várias "palavras" válidas da gramática
for production in generate(grammar, depth=5):
    print(' '.join(production))

In the above case, the exit was:

0 0 0
0 0 1
0 1 0
0 1 1
0 0
0 1
1 0 0
1 0 1
1 1 0
1 1 1
1 0
1 1
0
1

From there you can read the documentation (here and here) to generate exactly what you need.

For the grammar in question generates a sequence potentially infinite of zeros and ones (and not "a sequence from 0 to 2", as originally said), so it is unclear whether you need to generate any sequence whatever is valid, or some specific, or all of certain size, etc.

But the general idea is probably this...