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 可能会出现多次非终结符(例如 if COND then STMT else STMT)，并且这些出现不需要派生相同的子 -表格。

(3) 一般来说，语法可以生成无限的句子集。

---

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

copy = [x for x in original]

说起来更简单:

copy = original[:]