使用语法/规则在Python中生成所有终端字符串？

Question

我正在尝试从给定文件生成一定长度的所有终端字符串。例如，如果你有类似的东西

A = A B
A = B
B = 0
B = 1

那么你会得到类似的东西

0
1
0 0
0 1
1 0
1 1

这是我认为不会太困难的东西，但我陷入了困境。我目前可以读取这些值并将它们附加到字典中，并将规则存储为列表，如下所示：

{'B': [['0'], ['1']], 'A': [['A', 'B'], ['B']]}

看起来您想要做的是从非终结符之一（例如 A 或 B）开始），然后迭代每个规则。如果规则中的符号不​​是非终结符，您将打印或保存它，如果它是非终结符，您将用规则替换它，然后再次检查。我对如何用 Python 来做这件事感到困惑——我在这方面没有做太多事情。任何帮助将不胜感激！

Answer 1

伪代码：（

for each symbol:
    push that symbol onto the stack

while an item X can be popped off the stack:
    if X contains a non-terminal
        calculate each possible result with variation of the leftmost nonterminal
        if that variation is lower than the max length
             push it to the stack
    else
        add the popped X to a set Q of results (for de-duping)

print out the contents of Q (sorted, if so desired)

注意：“非终端单评估变体”意味着如果字符串是“AAB”，您将评估 A 中的 1，但不会评估另一个（也不会评估 B，因为它没有非终端选项）。然后您将在单独的路径中评估另一个 A - 您最终会将两个东西推入堆栈。）

请注意，在 Python 中您可以简单地使用从末尾添加/删除。堆栈的列表，和一个集合的 set() 。