使用语法/规则在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"，您将求1中的a，而不是其他的(也不是B，因为它没有非终结符选项)。然后你会在另一条路径上计算另一个A——你最终会把两个东西推到堆栈上。

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