Следующий код Python сгенерирует случайное предложение с заданным количеством терминалов.
Он работает путем подсчета количества способов создания предложения заданной длины, генерации большого случайного числа и вычисления указанного предложения.
Подсчет делается рекурсивно, с запоминанием.
Пустая правая часть выдает 1 предложение, если n равно 0 и 0 предложений в противном случае.
Чтобы посчитать количество предложений, произведенных непустой правой частью, суммируйте по i количество терминалов, используемых первым символом в правой части.
Для каждого i умножьте количество возможностей для остальной правой части на количество возможностей для первого символа.
Если первый символ является терминалом, существует 1 возможность, если i равно 1 и 0 в противном случае.
Если первый символ нетерминальный, суммируйте возможности по каждой альтернативе.
Чтобы избежать бесконечных циклов, мы должны быть осторожны, чтобы сократить рекурсивные вызовы, когда количество равно 0.
Это может продолжаться бесконечно, если грамматика имеет бесконечно много производных одного предложения.
Например, в грамматике
S -> S S
S ->
существует бесконечно много производных пустого предложения: S =>, S => S S =>, S => S S => S S S => и т. Д.
Код для поиска конкретного предложения представляет собой простую модификацию кода для их подсчета.
Этот код достаточно эффективен, он генерирует 100 предложений со 100 терминалами каждое менее чем за секунду.
import collections
import random
class Grammar:
def __init__(self):
self.prods = collections.defaultdict(list)
self.numsent = {}
self.weight = {}
def prod(self, lhs, *rhs):
self.prods[lhs].append(rhs)
self.numsent.clear()
def countsent(self, rhs, n):
if n < 0:
return 0
elif not rhs:
return 1 if n == 0 else 0
args = (rhs, n)
if args not in self.numsent:
sym = rhs[0]
rest = rhs[1:]
total = 0
if sym in self.prods:
for i in xrange(1, n + 1):
numrest = self.countsent(rest, n - i)
if numrest > 0:
for rhs1 in self.prods[sym]:
total += self.countsent(rhs1, i) * numrest
else:
total += self.countsent(rest, n - self.weight.get(sym, 1))
self.numsent[args] = total
return self.numsent[args]
def getsent(self, rhs, n, j):
assert 0 <= j < self.countsent(rhs, n)
if not rhs:
return ()
sym = rhs[0]
rest = rhs[1:]
if sym in self.prods:
for i in xrange(1, n + 1):
numrest = self.countsent(rest, n - i)
if numrest > 0:
for rhs1 in self.prods[sym]:
dj = self.countsent(rhs1, i) * numrest
if dj > j:
j1, j2 = divmod(j, numrest)
return self.getsent(rhs1, i, j1) + self.getsent(rest, n - i, j2)
j -= dj
assert False
else:
return (sym,) + self.getsent(rest, n - self.weight.get(sym, 1), j)
def randsent(self, sym, n):
return self.getsent((sym,), n, random.randrange(self.countsent((sym,), n)))
if __name__ == '__main__':
g = Grammar()
g.prod('S', 'NP', 'VP')
g.prod('S', 'S', 'and', 'S')
g.prod('S', 'S', 'after', 'which', 'S')
g.prod('NP', 'the', 'N')
g.prod('NP', 'the', 'A', 'N')
g.prod('NP', 'the', 'A', 'A', 'N')
g.prod('VP', 'V', 'NP')
g.prod('N', 'dog')
g.prod('N', 'fish')
g.prod('N', 'bird')
g.prod('N', 'wizard')
g.prod('V', 'kicks')
g.prod('V', 'meets')
g.prod('V', 'marries')
g.prod('A', 'red')
g.prod('A', 'striped')
g.prod('A', 'spotted')
g.weight.update({'and': 0, 'after': 0, 'which': 0, 'the': 0})
for i in xrange(100):
print ' '.join(g.randsent('S', 3))