문제

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

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

도움이 되었습니까?

해결책

다음 파이썬 코드는 주어진 수의 터미널과 함께 임의의 문장을 생성합니다. 주어진 길이의 문장을 생성하는 방법의 수를 계산하고, 많은 임의의 숫자를 생성하고, 표시된 문장을 계산합니다. 카운트는 메모 화를 통해 재귀 적으로 이루어집니다. 빈 오른쪽은 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))

다른 팁

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

예를 들어, 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 (개) ) ) )

등.

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

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

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top