4

Preciso criar uma expressão regular que seja equivalente à seguinte BNF:

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

Tentei criar um código em Python com a biblioteca regex:

import re

reg = r'[0-2]'

print(reg)

Era um teste, mas não consegui criar de fato uma regex que seja equivalente à BNF.

8
  • E você tá usando qual string pra tentar procurar por ocorrências usando a expressão regular em questão? Commented 19/10/2020 às 16:14
  • A regex teria que ser [0-2], mas dependendo do que vc precisa pode não ser o suficiente. Sem contar que você só criou uma string mas não está usando regex de fato. Se puder editar a pergunta e colocar mais detalhes (por exemplo, de qual texto vc quer extrair os números, etc)
    – hkotsubo
    Commented 19/10/2020 às 16:15
  • Não cheguei a incluir string, na verdade estou com muita dúvida nesse tema em questão. Se puder me ajudar. Commented 19/10/2020 às 16:15
  • "mas não consegui fazer exibir a sequência numérica", que sequência?
    – Woss
    Commented 19/10/2020 às 16:16
  • 1
    Para conhecer o verdadeiro funcionamento das expressões regulares Leia isto.
    – Solkarped
    Commented 19/10/2020 às 17:25

1 Resposta 1

2

Se a ideia é gerar uma regex equivalente a esta BNF, então seria algo assim:

import re

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

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

A regex usa os marcadores ^ e $ que indicam respectivamente o início e fim da string.

Depois temos a classe de caracteres [01] que significa "um dígito 0 ou 1" e o quantificador + que indica uma ou mais ocorrências. Assim, a regex reconhece uma sequência de zeros e uns, de tamanho mínimo 1 e sem limite máximo (exatamente o mesmo que a BNF representa).

No exemplo acima, podemos ver que se a string só tem zeros e uns, é encontrado um match, e se tiver qualquer caractere diferente, não encontra nada.

Obs: eu até poderia usar [0-1] em vez de [01], mas neste caso dá na mesma ("um digito de 0 a 1" e "o dígito 0 ou 1" é basicamente a mesma coisa).


Antes da edição e dos comentários, não estava claro que o objetivo era gerar a regex acima. De qualquer forma, vou manter a versão que tentava responder à pergunta original.

Se dada uma BNF, você quer criar uma sequência que corresponda à definição, então regex não é a ferramenta certa para a tarefa.

No caso, você teria que implementar na mão, ou usar alguma lib pronta. Uma alternativa é usar o NLTK. Como eu não uso muito esse tipo de coisa, acabei pegando um exemplo daqui e adaptando para o seu caso:

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))

No caso acima, a saída foi:

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

A partir daí você pode ler a documentação (aqui e aqui) para gerar exatamente o que você precisa.

Pois a gramática em questão gera uma sequência potencialmente infinita de zeros e uns (e não "uma sequência de 0 a 2", como originalmente dito), então não está claro se você precisa gerar alguma sequência qualquer que seja válida, ou alguma específica, ou todas de determinado tamanho, etc.

Mas a ideia geral provavelmente é essa...

7
  • Muito obrigada, pela ajuda. Eu precisaria no caso criar uma sequência com a biblioteca regex de forma que representasse a BNF que mostrei acima, não exatamente resolvesse ela, entendeu? Mas já me ajudou bastante. Commented 19/10/2020 às 17:53
  • @CamillaMarques Atualizei a resposta
    – hkotsubo
    Commented 19/10/2020 às 18:04
  • Muito obrigada! Agora consegui entender melhor. Commented 19/10/2020 às 18:09
  • 1
    @CamillaMarques Então é o caso de abrir outra pergunta. A ideia do site é ter uma pergunta por problema específico - e além disso, uma nova pergunta fica visível na página principal para todos verem (aqui nos comentários menos gente vai ver, provavelmente só eu, o que diminui as chances de ter uma resposta) e assim o site também fica mais organizado :-)
    – hkotsubo
    Commented 15/11/2020 às 0:00
  • 1
    Feito : pt.stackoverflow.com/questions/482315/… Commented 15/11/2020 às 0:05

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .