Pythonですべての端末文字列を文法/ルールで生成する？

Question

私は、特定のファイルから特定の長さまでのすべてのターミナル文字列を生成しようとしています。だから、例えば、あなたが

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

のようなものを持っているなら、あなたは

0 
1 
0 0 
0 1 
1 0 
1 1 

のようなものになるだろうこれは私が過度に難しいことではないだろうが、私は立ち往生だと思ったものです。非の1で始まる

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

それはあなたがしたいと思いますどのように見えるでしょうです：私は現在の値を読み、ルールがそうのようなリストとして保存された状態で、辞書にそれらを追加することができます（ex 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さんのを評価するが、他のではないだろうということを意味（それは非終端のオプションを持たないので、Bではなく）別のパスで別のAを評価すると、2つのものをスタックにプッシュします。

Pythonではスタックのリストの最後から追加/削除を使用し、セットの場合はset()を使用することができます。