python - 试图生成一个简单形式语法的所有句子

Question

我是 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 的一个副本，队列中的所有内容也会更改。任何帮助表示赞赏，任何指示，提示都会很棒

这是预期的输出:

       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

Answer 1

I am facing some issue with shallow-deep copy, if I change one copy of sf, everything in queue changes too

是的。在 Python 中，列表是具有自己标识的对象。所以:

Q.enqueue(['Sigma'])

创建一个(单元素)列表并将对它的引用排入队列。

sf = Q.dequeue()

从 Q 弹出该引用并将其分配给变量“sf”。

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

对该列表(“sf”所指的列表)进行更改。

Q.enqueue(sf)

将对同一列表的引用排入队列。

所以只涉及一个列表对象，Q 只包含对它的多个引用。

相反，您可能希望 Q 中的每个条目都是对单独列表(句子形式)的引用，因此您必须为每次调用 Q.enqueue 创建一个新列表。

根据您修复该问题的方式，代码中可能存在也可能不存在其他问题。考虑:

(1) 每个句子都有多个推导，你只需要'找到'一个(例如，最左边的推导)。

(2) 通常，虽然不是在您的示例语法中，但产生式的 RHS 可能不止一次出现非终结符(例如，如果 COND 然后 STMT 否则 STMT)，并且这些出现不需要派生相同的子 -表格。

(3) 一般来说，一个文法可以生成无限多的句子。

---

顺便说一句，在Python中复制一个列表，而不是说

copy = [x for x in original]

说起来更简单:

copy = original[:]