주어진 수의 터미널로 문법에서 문장을 생성합니다.

Question

장난감 문법이 있다고 가정 해 봅시다. (출력이 더 자연스럽게 보이도록 업데이트되었습니다)

S -> ${NP} ${VP} | ${S} and ${S} | ${S}, after which ${S}

NP -> the ${N} | the ${A} ${N} | the ${A} ${A} ${N}

VP -> ${V} ${NP}

N -> dog | fish | bird | wizard

V -> kicks | meets | marries

A -> red | striped | spotted

예를 들어, "개가 붉은 마법사를 걷어 차다", "새가 발견 된 물고기를 만나거나 마법사가 줄무늬 개와 결혼한다"

이 문법에서 총액을 포함해야한다는 제약에 따라 어떻게 문장을 생성 할 수 있습니까? N vs + as + ns. 정수가 주어지면 문장에는 많은 터미널이 포함되어야합니다. (물론이 문법에서 가능한 최소값 N 3).

Answer 1

다음 파이썬 코드는 주어진 수의 터미널과 함께 임의의 문장을 생성합니다. 주어진 길이의 문장을 생성하는 방법의 수를 계산하고, 많은 임의의 숫자를 생성하고, 표시된 문장을 계산합니다. 카운트는 메모 화를 통해 재귀 적으로 이루어집니다. 빈 오른쪽은 n이 0과 0 문장 인 경우 1 문장을 생성합니다. 비어 있지 않은 오른쪽에 의해 생성 된 문장의 수를 계산하려면 오른쪽의 첫 번째 기호에 의해 사용되는 터미널 수를 i에 합산하십시오. 각각의 경우, 오른쪽의 나머지 가능성에 첫 번째 기호에 대한 가능성 수를 곱하십시오. 첫 번째 기호가 터미널 인 경우, 그렇지 않으면 1과 0이면 1 가능성이 있습니다. 첫 번째 기호가 비 터미널 인 경우 각 대안의 가능성을 합산하십시오. 무한 루프를 피하기 위해, 우리는 수량이 0 일 때 재귀 호출을 가지 치기 위해주의해야합니다. 문법에 한 문장의 많은 파생물이 무한히 많은 경우에도 여전히 무한히 루프가 될 수 있습니다. 예를 들어, 문법에서

S -> S S
S ->

빈 문장의 무한히 많은 파생물이 있습니다 : s =>, s => ss =>, s => ss => sss => 등. 특정 문장을 찾는 코드는 코드를 간단히 수정하는 것입니다. . 이 코드는 합리적으로 효율적이며 각각 100 개의 단자가있는 100 개의 문장을 1 초 이내에 생성합니다.

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))

Answer 2

아마도 최선의 해결책은 아니지만 제약을 초과 할 때까지 문법의 각 규칙을 통해 재귀 적으로 작업을 수행 한 다음, 뒤로 물러서서 문법을 따라 다른 길을 탐색합니다. 제약 조건을 충족시키는 모든 문장을 유지하고 그렇지 않은 모든 문장을 버리십시오.

예를 들어, n = 3 :

s-> ($ {np} $ {vp}) -> ((($ {n}) $ {vp}) -> (((dog) $ {vp}) -> ...-> (( The (dog) ((kicks) ($ {np})))) -> ((Dog) ((kicks) (The (dog)))))

그리고 뒤로 튀어 나옵니다

((the (dog) ((킥) ($ {n})))) -> ((Dog) ((kicks) (wish)))))

그리고 잠시 후 ...

((The (dog) ($ {v} $ {n}))) -> ((The (Dog) ((Meets) $) $ {n})))) -> ((Dog) ((Meets) The (개) ) ) )

등.

본질적으로 깊이 우선 그래프 검색으로, 그래프를 검색 할 때 그래프를 구축하고 있습니다 (제약 조건을 초과하는 부품 구축을 중단합니다).

Answer 3

이 질문에는 범주 오류가 포함되어 있습니다. 당신이 지정한 문법에는 컨텍스트가없는 문법의 모양이 있지만 특정 수의 터미널 노드가 있어야한다는 요구 사항에는 재귀 적으로 열거 가능한 문법이 필요합니다.