إنتاج جملة من قواعد النحوية مع عدد معين من المحطات

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

على سبيل المثال، "الكلب يركب المعالج الأحمر"، "الطائر يلتقي الأسماك المرقط أو المعالج يتزوج الكلب المخطط"

كيف يمكنك إنتاج جملة من هذه القواعد وفقا للقيد يجب أن تحتوي على ما مجموعه ن vs + as + ns. بالنظر إلى عدد صحيح يجب أن تحتوي الجملة على العديد من المحطات. (ملاحظة بالطبع في هذه القواعد الحد الأدنى ممكن ن هو 3).

Answer 1

سيقوم رمز Python التالي بإنشاء جملة عشوائية مع عدد معين من المحطات. إنه يعمل عن طريق حساب عدد الطرق لإنتاج جملة من طول معين، وتوليد عدد عشوائي كبير، والحوسبة الجملة المشار إليها. يتم العدد بشكل متكرر، مع memoization. ينتج الجانب الأيمن الأيمن فارغا جملة واحدة إذا كانت N هي 0 و 0 جمل خلاف ذلك. لحساب عدد الجمل التي تنتجها الجانب الأيمن غير المؤثر، مبلغ أكثر مني، عدد المحطات المستخدمة من قبل الرمز الأول في الجانب الأيمن. بالنسبة لكل ط، اضرب عدد إمكانيات بقية الجانب الأيمن من خلال عدد إمكانيات الرموز الأولى. إذا كان الرمز الأول محطما، فهناك احتمال واحد إذا كنت 1 و 0 خلاف ذلك. إذا كان الرمز الأول غير عاملا، فمن مجموع الاحتمالات على كل بديل. لتجنب الحلقات اللانهائية، يجب أن نكون حريصين على تقليل المكالمات العودية عند الكمية 0. قد لا تزال هذه الحلقة بلا حدود إذا كان قواعد القواعد له العديد من اشتقاق العديد من الجملة. على سبيل المثال، في القواعد

S -> S S
S ->

هناك العديد من مشتقات العديد من المشتقات من الجملة الفارغة: S =>، S => SS =>، S => SS => SSS =>،، إلخ. التعليم الكود للعثور على جملة معينة هو تعديل مباشر للتعليم وبعد هذا الرمز هو فعال بشكل معقول، وتوليد 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))

Answer 2

ربما ليس أفضل حل، لكنني أعمل بشكل متكرر طريقي من خلال كل قاعدة من قواعد القواعد حتى تجاوزت القيد، ثم ظهر الباب واستكشاف مسار آخر على طول القواعد. الحفاظ على كل الجمل التي تلبي القيد ورمي كل الجمل التي لا تفعل ذلك.

على سبيل المثال، مع n = 3:

S -> ($ {np} $ {vp}) -> ((($ {n}) $ {vp}) -> (((الكلب) $ {vp}) -> ... -> (الكلب) ((الركلات) ($ {np}))) -> (((الكلب) ((الركلات) ((الكلب)))))

ثم مرة أخرى

((الكلب (الكلب) ((الركلات) ($ {n}))) -> ((الكلب (الكلب) ((الركلات) ((الأسماك))))

وبعضها البعض في وقت لاحق ...

(((الكلب) ($ {v} $ {n}))) -> ((الكلب (الكلب) ((يجتمع) $ {n})) -> (((الكلب) ((يلتقي) (كلب) ) ) )

إلخ.

في الأساس بحث الرسم البياني العميق الأول، أنت فقط تقوم ببناء الرسم البياني كما تبحث عنه (وأنت تتوقف عن إنتاج الأجزاء التي تتجاوز القيود).

Answer 3

يحتوي هذا السؤال على خطأ في الفئة. يحتوي Grammar الذي حددته بمظهر قواعد اللغة الحرة للسياق، ولكن متطلبات أن هناك عددا محددا من العقد الطرفية يتطلب قواعد قواعد شديدة.