كيف يمكنني توليد الجمل من رسمي قواعد اللغة ؟

Question

ما هي طريقة شائعة توليد جمل من قواعد اللغة ؟

أريد خوارزمية هذا النوع الآخر من محلل.هذا هو إعطاء الرسمية الخالية من السياق النحوي (أقول ليرة لبنانية) ، أريد أن تولد التعسفي الجملة التي تتوافق مع تلك القواعد.يمكنني استخدام الجملة هنا يعني أي صحيح الجسم من النص ، لذلك يمكن أن يكون في الواقع برنامج كامل (حتى لو كان لا يجعل من أي معنى طالما انها syntactially الصحيح).

المثال النحوي:

program   : <imports> NEWLINE? <namespace>
imports   : ("import" <identifier> NEWLINE)* 
namespace : "namespace " <identifier> NEWLINE "{" <classes> "}" 
identifier: (A-Za-z_) (A-Za-z0-9_)*
...

على سبيل المثال ولدت البرنامج:

import jkhbhhuob
import aaaaa888_

namespace u8nFGubgykb
{ class ui0op_np { ... }
}

Answer 1

أنا لا أعرف أن هناك "المشتركة" خوارزمية من أجل القيام بذلك.عشوائي برنامج جيل يستخدم في البرمجة الجينية لذلك يمكن أن ننظر القائمة على قواعد اللغة GP النظام ومعرفة كيفية التعامل مع برنامج جيل.وأود أن تفعل العودية القاعدة خوارزمية توليد مثل الزائفة رمز:

void GenerateRule(someRule)
{
  foreach (part in someRule.Parts)
  {
    if (part.IsLiteral) OutputLiteral(part);
    if (part.IsIdentifier) Output(GenerateIdentifier(part)));
    if (part.IsRule) GenerateRule(part.Rule);
  }
}

هذا يفترض أن كنت قد قرأت في جميع الأجزاء إلى بعض بنية البيانات.سوف تحتاج أيضا إلى التعامل مع التكرار(تولد عشوائيا عدد مرات حدوثها) و القواعد الاختيارية (الوجه عملة لمعرفة ما إذا كانت هناك أم لا).

---

تحرير:و إذا حكم على أكثر من خيار واحد ، كنت مجرد اختيار واحد من الخيارات للذهاب مع العملية بنفس الطريقة.حتى إن بعض حكم (حرفية|متغير) ، وكنت اختيار عشوائيا بين البلدين.

Answer 2

هنا هو بيثون سبيل المثال باستخدام NLTK:

from nltk import parse_cfg, ChartParser
from random import choice

def produce(grammar, symbol):
    words = []
    productions = grammar.productions(lhs = symbol)
    production = choice(productions)
    for sym in production.rhs():
        if isinstance(sym, str):
            words.append(sym)
        else:
            words.extend(produce(grammar, sym))
    return words

grammar = parse_cfg('''
S -> NP VP
PP -> P NP
NP -> Det N | Det N PP | 'I'
VP -> V NP | VP PP
V -> 'shot' | 'killed' | 'wounded'
Det -> 'an' | 'my' 
N -> 'elephant' | 'pajamas' | 'cat' | 'dog'
P -> 'in' | 'outside'
''')

parser = ChartParser(grammar)

gr = parser.grammar()
print ' '.join(produce(gr, gr.start()))

المثال هو مقتبس من الكتاب.الجمل ولدت هي عبارة صحيحة ولكن لا يزال إجمالي رطانة.

Answer 3

الحل الخاص بك ينبغي أن تتبع الاستقرائي بنية اللغة.كيف يمكنك توليد عشوائي الكلام لكل من التالي ؟

• محطة الرمز
• رمز رمز غير خطي
• تسلسل اليمنى الجانبين
• اختيار اليمنى الجانبين
• نجوم إغلاق اليمنى الجانبين

كل هذا سيكون أكثر وضوحا إذا كنت أكتب بنية البيانات تستخدم لتمثيل النحوي.هيكل من مجموعة متبادلة متكررة مولد وظائف المرآة التي بنية البيانات عن كثب.

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

Answer 4

من على قمة رأسي:

أود العمل بشكل متكرر (في الأساس عكس العودية الكريم محلل) باستخدام بعض الاستدلال حول ما يجب القيام به مع نطاقات ((...):ربما اختيار عشوائيا) اخليارات (?:انظر [] أدناه) ، التكرار(''توزيع بواسون?).حرفية ("...") بسيطة مكتوبة إلى الإخراج ، subtokens (`<...>') تولد العودية.

هذا لا ينبغي أن يكون من الصعب جدا إلا إذا كنت تريد أن تضمن نوعا من تغطية كاملة.حتى ذلك الحين توليد مجموعة البيانات من شأنه أن يساعد...

---

[*] عليك أن تشمل اخليارات أقل من 50% من الوقت لمنع لانهائية التراجع عند معالجة القواعد مثل

 nonterm:  otherstuff <nonterm>?

جيدة الصيد طيدة.

وبالمثل مع التكرار ، رمي التوزيعات التي يتقاطع بقوة.

---

سوف تحتاج إلى تحليل المدخلات اللغة أولا إذا قدم عليه في BNF شكل كما هنا.أبسط شيء نفعله استخدام الخرائط (name, string), ثم تبدأ مع أعلى مستوى مميز (التي قد تفترض يعني أول واحد...).

هذا يتيح لك:

("البرنامج"،"<imports> السطر?<namespace>")

("الواردات" ، ("استيراد" <identifier> السطر)*)

...

فإن عليك أن تبدأ مع "البرنامج" ضرب "<imports>"لذلك كنت تتكرر...على العودة ، hist "السطر?", حتى رمي النرد والكتابة أو لا ضرب "<namespace>"وهكذا تتكرر...على العودة الانتهاء من ذلك.

---

أجد نفسي الشك أن هذا حدث من قبل.إذا كنت بحاجة فقط الإخراج ، أود البحث في الويب...ربما http://portal.acm.org/citation.cfm?doid=966137.966142, على الرغم من العدد الهائل من محلل مولدات هناك فوضى حتى البحث الفضاء...محاولة هذه الورقة, أيضا.

BTW ... أنت الجامعات المحلية ربما لديه اشتراكات الانترنت إلى هذه المجلات ، حيث يمكنك الحصول عليها مجانا عن طريق تركيب في المكتبة.

Answer 5

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

Answer 6

اقتراحي الأول سيكون اتساع أول البحث.فقط إعداد الرسم البياني قواعد البحث من خلالها.عليك أن تبدأ بصق البرامج بدءا من أصغر ممكن منها ببطء الحصول على أكبر.سوف تجد على الأرجح ، على الرغم من أن قواعد اللغة الخاصة بك سوف يبصقون أكثر أضعافا مضاعفة البرامج على عدد معين من القواعد و سوف يرجح أن لا تحصل على مدى 30 أو حتى الرموز في برنامج باستخدام DFS.

المشكلة مع عمق البحث الأول هو أن الثانية لديك اليسار العودية القاعدة ، البحث الخاص بك سوف تتعثر في حلقة لا نهائية.

مشكلة كبيرة أخرى هي أن عبارة صحيحة برامج شوطا طويلا من الصحيحة لغويا البرامج.توليد هذا النوع الأخير هو المرجح تماما unfeasable في جميع ولكن معظم الحالات الأساسية.

Answer 7

كالعادة, انا ذاهب الى تقديم المشورة ضد إعادة اختراع العجلة.لقد كتبت من الذراع المجمع ، ولكن أنا على الاطلاق كما الندم (البرنامج:الممارسة والخبرة نيسان / أبريل 2007):

"في وقت لاحق ، الجاهزة التعبير مولد ينبغي أن تستخدم في توليد عشوائي الذراع تعليمات التجميع للمقارنة.بدلا من ذلك Perl بنيت تدريجيا ، مع كل ذراع التعليمات تعريف توليد الحالات.ميزة, ومع ذلك ، الإضافية في المنزل النهج بسيطة بدائل بسيطة الكشف عن الأخطاء و الشوائب الصيد يمكن أن تنتقل تدريجيا."

أخشى أنني لا أذكر ما جعلني أغير رأيي وأنا أشك أن تكون ذات صلة إلى الاحتياجات المحددة الخاصة بك, ولكن أنا لا أقترح النظر أصعب سابقة الحل.فإنه يتطلب أقل الانضباط لكتابة مثل هذه الاشياء بنفسك ، ولكن دائما ما تستغرق وقتا أطول مما كنت تتوقع.

Answer 8

لا إجابة, ولكن تحقق من ويكيبيديا الدخول على قواعد اللغة الجيل:http://en.wikipedia.org/wiki/Context-free_grammar_generation_algorithms

ووصف بعض الخوارزميات المستخدمة.

Answer 9

في حين أن فكرة لطيفة (لقد فكرت عدة مرات من قبل) ، فإن الواقع هو أنه من دون بعض نماذج البيانات و/أو طن من مولد القيود/الجهد حدود, هو جدا مهمة كبيرة.

واحد قد تجد نماذج الكتابة باليد أسهل.:)