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.