如何使用以下规则和语法生成正则表达式中所有可能的单词？

Question

如何使用以下规则和语法生成正则表达式的所有可能的单词：

• 用户输入字母表
• 用户输入表达式
• 任何不是（）*+或空格的字符都可以是字母表的一部分
• +字符在其左侧的字符或序列或右侧的字符或序列之间进行选择
• *字符允许在其左侧重复一个或多个字符或序列
• 两个按顺序排列的字母字符将被连接起来
• 括号可以改变优先顺序。在

我从用户那里得到了作为字符串的字母表和表达式，并将其转换为python列表。然后，我根据上面的规则对这两种方法进行了一些简单的验证测试。在

之后，目前，我的算法已经正确地生成了无括号表达式的单词。我的问题是：我还没有找到一种方法来正确地管理括号来正确地生成单词。在我看来，我有两个选择：

1）找到一种直接从原始表达式计算可能的单词的方法，或

2）以某种方式消除所有括号，并使用我当前的算法来解决它。在

我想知道是否可以使用某种递归函数来完成第一个选项，尽管我仍然不知道如何实现。有什么想法吗？在

以下是到目前为止的代码（抱歉用葡萄牙语评论，这里是巴西语）：

alphabetInput = input(
    "Informe os caracteres do alfabeto (OBS.: os símbolos '(', ')', '+' e '*' são caracteres reservados):\n")
alphabetInput = alphabetInput.strip()  # remove os espaços em branco da string
alphabetInput = list(alphabetInput)  # transforma a string numa lista

# remove as duplicidades do alfabeto
alphabet = []
for c in alphabetInput:
    if c not in alphabet:
        alphabet.append(c)

for c in alphabet:
    if c in "()*+":
        print("Alfabeto inválido (OBS.: os símbolos '(', ')', '+' e '*' são caracteres reservados).")
        exit()

expression = input("Informe a expressão regular:\n")
expression = expression.strip()  # remove os espaços em branco da string
expression = list(expression)  # converte a string numa lista

counter = 0  # controle dos parênteses abertos e fechados no loop a seguir

for c in (expression):
    if c == "(":
        counter = counter + 1  # +1 significa que um parêntese foi aberto
    elif c == ")":
        counter = counter - 1  # -1 significa que um parêntese foi fechado
    else:
        pass
    if counter < 0:
        print("Expressão inválida. Um parêntese foi fechado sem ter sido aberto antes.")
        exit()

# se o contador for maior do que zero, significa que há mais parênteses abertos do que fechados
# se for menor do que zero, terá caído no 'if' dentro do loop acima
# se for igual a zero, estará ok
if counter > 0:
    print("Expressão inválida: Existem parênteses em aberto.")
    exit()

# testa a validade da expressão com base na existência sequências inválidas de caracteres
if (expression[0] == "+" or expression[len(expression) - 1] == "+"):  # testa a existência de "+" no começo e no fim da expressão
    print("Expressão inválida: Existem adições lógicas (+) sem um dos operandos.")
    exit()
else:
    for i in range(0, len(expression)):
        if (expression[i] == "+"):
            if (expression[i + 1] == "+" or expression[i + 1] == "*" or expression[i + 1] == ""):
                print("Expressão inválida: Existem adições lógicas (+) sem um dos operandos.")
                exit()

#### FIM DA SEÇÃO 1 ####

#### SEÇÃO 2: TESTE DE PERTINÊNCIA DOS SÍMBOLOS INFORMADOS AO ALFABETO INFORMADO ####

# OBS.: 'expression' já é uma lista, o casting é feito para que o conteúdo modificado em uma não o seja na outra
testExpression = list(expression)

# os loops seguintes marcam e removem os espaços em branco e caracteres especiais da expressão,
# e em seguida testam se os símbolos usados pertencem ao dicionário informado
for i in range(len(testExpression)):
    if testExpression[i] in " ()+*":
        testExpression[i] = "marked"

while "marked" in testExpression:
    testExpression.remove("marked")

# testa se os símbolos usados fazem parte do alfabeto informado
for c in testExpression:
    counter = 0
    for cc in alphabet:
        if c == cc:
            counter += 1;
    if counter == 0:
    # se esse contador for igual a zero, significa que não há correspondência entre o símbolo da expressão e o alfabeto
        print("Expressão informada possui símbolos que não pertencem ao alfabeto.")
        exit()

#### FIM DA SEÇÃO 2 ####

#### SEÇÃO 3: GERAÇÃO DAS PALAVRAS ####

possibilities = [[]]  # vetor que receberá os subvetores com cada possiblilidade
possibilitiesCounter = 0  # contador de possibilidades, toda vez que ele é incrementado um novo subvetor é criado

# monta e arranja as palavras geradas no vetor 'possibilities'
for i in range(0, len(expression)):
    if expression[i] in alphabet:
        possibilities[possibilitiesCounter].append(expression[i])
    if expression[i] == "+":
        possibilities.append([])
        possibilitiesCounter += 1

# imprime todas as palavras geradas na tela
yetAnotherCounter = 0
words = []  # lista final das palavras
for l in possibilities:
    words.append("".join(str(x) for x in l))
    print("Palavra ", yetAnotherCounter + 1, ":", words[yetAnotherCounter])
    yetAnotherCounter += 1

Answer 1

所以，我通过使用一个名为exrex:https://github.com/asciimoo/exrex的库来解决这个问题

它有一个函数generate，它正是我想要的。在