如何用语法/规则在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，但不会评估另一个A和B，因为B没有其他选择。然后你会在不同的路径中评估另一个A - 这样你就会把两个东西放到栈里。）

注意，在Python中，你可以简单地通过在列表的末尾添加或删除元素来实现栈的功能，而用set()可以实现集合的功能。