-1

Preciso criar um programa com Regex que represente as seguintes BNF's:

<list> ::= <element><list> | <element>
<element> ::= <letter><digit>
<letter> ::= A | B 
<digit> ::= 1|2

Para a BNF acima tentei gerar um programa mas acredito que não esteja tão correto assim:

import re

r = re.compile('^[A-B-1-2]+$')

print(r.match('A1'))
print(r.match('A2B1'))

<exp> ::= <exp> + <exp> | <term>
<term> ::= <term> * <term> | <factor>
<factor> ::= ( <exp> ) | <digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 

E preciso implementar também um programa com Regex representando a BNF acima.

3
  • 3
    Como o site é um repositório para público amplo, é importante sempre explicar de maneira objetiva a dificuldade encontrada para avançar na solução, para que as respostas possam focar num problema bem específico, em vez de fornecerem "solução pronta completa", mesmo que não tenha sido intencional. Para aproveitar melhor o site, entender e evitar fechamentos e negativações vale a pena entender O que é o Stack Overflow e ler o Guia de sobrevivência (resumido) do Stack Overflow em Português.
    – Largato
    Commented 15/11/2020 às 0:44
  • 2
    O trivial é usar um gerador de analisadores como o PyBison ou Lark ao invés da biblioteca nativa de expressões regulares. Commented 15/11/2020 às 0:57
  • 1
    Uma linguagem regular pode ser expressa por uma expressão regular. Sua BNF é de uma gramática livre do contexto e portanto não pode ser representada por uma expressão regular.
    – anonimo
    Commented 15/11/2020 às 13:30

1 Resposta 1

2

Conforme informado nos comentários, regex não é a ferramenta ideal para isso (lá são sugeridas opções mais adequadas), e sobre este assunto, também sugiro que leia aqui e aqui. Dito isso, vamos à regex.


A primeira BNF diz que "element" se repete uma ou mais vezes. Por sua vez, um "element" é uma sequência de uma letra A ou B, seguido de um dígito 1 ou 2.

O problema é que você usou [A-B-1-2], que significa "letra A ou B, ou hífen, ou 1 ou 2". Ou seja, ela até pega casos válidos como "A1" e "A2B1" mas também pega casos inválidos como "---" e "1212A". Se a ideia é fazer sempre uma letra e um dígito alternados, e esta sequência pode se repetir várias vezes, a regex deveria ser:

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

Assim, eu tenho [AB] (letra A ou B), seguido de [12] (dígito 1 ou 2), e esta sequência se repete uma ou mais vezes.


A segunda é um pouco mais complicada e acho que não é possível com regex, pois a definição dela é recursiva (e sem um caso base):

  • "factor" pode ser um "exp" entre parênteses
  • "exp" pode ser um "term"
  • "term" pode ser um "factor"
  • "factor" pode ser um "exp" entre parênteses
  • ...

Claro que existe regex recursiva, mas o Python não suporta nativamente (e sinceramente, é um negócio tão complicado que questiono se valeria a pena usar).

Mas apenas para deixar registrado, usei o módulo regex (que possui suporte à regex recursiva) e tentei implementar este pequeno "monstrinho":

import regex

r = regex.compile(r"""(?(DEFINE)
       (?<digit>     (?: [0-9] ) )
       (?<factor>    (?: \( (?&exp) \) | (?&digit) ) )
       (?<term>      (?: (?&term) \* (?&term) | (?&factor) ) )
       (?<exp>       (?: (?&exp) \+ (?&exp) | (?&term)  ) )
    )
    ^ (?&exp) $
""", regex.VERBOSE)

Basicamente ela tenta usar sub-rotinas, que permite que se use a mesma sub-expressão recursivamente.

Mas ao rodar, deu um MemoryError. Testei essa mesma regex no site regex101.com e ocorreu um "engine error" (veja aqui):

The match was halted because your expression contains a recursive loop. This means either that the whole pattern, or a subpattern, has been called recursively for the second time at the same position in the subject string.

Ou seja, eu acho que não é possível, justamente por ter uma definição recursiva (uma expressão que pode ter termos, que podem ter fatores, que podem ser outras expressões, etc) e sem um caso base no qual ela pode se encerrar.

8
  • Muito obrigada, já me ajudou bastante! Como sempre! Commented 15/11/2020 às 0:52
  • Parece que o módulo regex aceita recursividade. Vale a pena testar. Retirado da documentação Recursive and repeated patterns are supported. Commented 15/11/2020 às 21:38
  • @PauloMarques O último exemplo usa o módulo regex e a expressão tem sub-rotinas (que é um dos tipos de recursão de regex). Mas ela não funcionou porque a definição não tem um caso base e acaba virando uma recursão infinita (pelo que entendi). Mas depois eu vejo se tem outro jeito - embora eu ache que com regex não dá mesmo...
    – hkotsubo
    Commented 16/11/2020 às 0:19
  • 1
    Pelo visto teria que ser construído um parser... Commented 16/11/2020 às 2:44
  • 1
    @PauloMarques Sim, inclusive foram sugeridas opções nos comentários - atualizei a resposta para deixar mais claro que regex não é a ferramenta ideal, obrigado!
    – hkotsubo
    Commented 16/11/2020 às 12:10

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