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 副本，队列中的所有内容也会发生变化。任何帮助表示赞赏，任何方向，提示都会很棒

这是预期的输出：

       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 副本，队列中的所有内容也会更改

是的。在 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[:]
于 2013-09-24T01:18:30.407 回答
1

我创建了一个简单的语法，允许根据备选方案和选项指定不同的句子。可以解析用该语法描述的句子。属性语法是使用 Coco/R 描述的，它有一个 python 版本（http://www.ssw.uni-linz.ac.at/Coco/#Others）。我对 C# 比较熟悉，所以我在这里创建了一个 C# 项目，可以作为示例：https ://github.com/abeham/Sentence-Generator 。

例如，用那个简单语法的解析器解析“(This | That) is a [nice] sentence”会产生四个句子：* This is a sentence * This is a nice sentence * That is a sentence * That is a nice sentence

由于没有重复符号，因此只能使用该语法创建有限的句子。

我知道已经存在一个公认的答案，但我希望这个答案对像我这样来到这里寻找通用解决方案的人也有价值。至少我在网上没有找到类似的东西，这就是我创建 github 项目的原因。

于 2015-06-16T18:00:52.233 回答