2

私はpythonが初めてで、文法で可能なすべての文を生成しようとしています。文法は次のとおりです。

  #set of non terminals
  N = ('<subject>', '<predicate>', '<noun phrase>', '<noun>', '<article>', '<verb>',   '<direct object>')
  #set of teminals

  T = ('the', 'boy', 'dog', 'bit')
  #productions
  P = [ ('Sigma',           ['<subject>', '<predicate>']), \
  ('<subject>',       ['<noun phrase>']),            \
  ('<predicate>',     ['<verb>']),                   \
  ('<predicate>',     ['<verb>','<direct object>']), \
  ('<noun phrase>',   ['<article>','<noun>']),       \
  ('<direct object>', ['<noun phrase>']),            \
  ('<noun>',          ['boy']),                      \
  ('<noun>',          ['dog']),                      \
  ('<article>',       ['the']),                      \
  ('<verb>',          ['bit'])                       ]

これが私の試みです。キュークラスを使用して体系的に実装しています。

# language defined by the previous grammar.
Q = Queue()
Q.enqueue(['Sigma'])
found = 0
while 0 < len(Q):
    print "One while loop done"
    # Get the next sentential form
    sf = Q.dequeue()
    sf1 = [y for y in sf]
    for production in P:
        for i in range(len(sf1)):
                if production[0] == sf1[i]:
                        sf[i:i+1] = [x for x in production[1]]
                        Q.enqueue(sf)
                        Q.printQ()

私は無限ループに陥っています。また、sf の 1 つのコピーを変更すると、キュー内のすべても変更されます。どんな助けでも大歓迎です、どんな方向性、ヒントも素晴らしいでしょう

予想される出力は次のとおりです。

       The dog bit the boy
       The boy bit the dog
       The boy bit the boy
       The dog bit the dog
       The dog bit
       The boy bit
4

2 に答える 2

2

sf の 1 つのコピーを変更すると、キュー内のすべても変更されます。

はい。Python では、リストは独自の ID を持つオブジェクトです。そう：

Q.enqueue(['Sigma'])

(要素が 1 つの) リストを作成し、それへの参照をキューに入れます。

sf = Q.dequeue()

Q からの参照をポップし、変数 'sf' に割り当てます。

sf[i:i+1] = ...

そのリスト ('sf' が参照するリスト) に変更を加えます。

Q.enqueue(sf)

同じリストへの参照をキューに入れます。

したがって、関連するリスト オブジェクトは 1 つだけで、Q にはそれへの複数の参照が含まれているだけです。

代わりに、おそらく Q の各エントリを個別のリスト (文形式) への参照にしたいので、Q.enqueue への呼び出しごとに新しいリストを作成する必要があります。

それを修正する方法に応じて、コードに他の問題がある場合とない場合があります。検討：

(1) 各文には複数の派生語があり、そのうちの 1 つを「見つける」だけで済みます (たとえば、一番左の派生語)。

(2) 一般に、例の文法ではありませんが、プロダクションの RHS には非終端記号が複数回出現する可能性があり (たとえば、COND の場合は STMT、そうでない場合は STMT)、それらの出現は同じサブフォームを派生させる必要はありません。

(3) 一般に、文法は無限の文のセットを生成できます。

ちなみに、Pythonでリストをコピーするには、

copy = [x for x in original]

言うのは簡単です：

copy = original[:]
于 2013-09-24T01:18:30.407 に答える