اسم الخوارزمية - مطابقة الأشجار الفرعية في ASTs

Question

لدي مجموعة S من الأشجار "الصغيرة". S[i] والتي أحتاج إلى العثور على مواقعهم لداخل أكبر والتي يتم استخدامها كأنماط للعثور على الأشجار الفرعية المطابقة في نطاق أكبر شجرة T.أنا أعرف S قبل أن أبدأ في البناء T (وهي شجرة تحليل)، لذلك أفكر في استخدام ملف طريقة قطع الطائرة لمطابقة العقد أثناء تقدمي (حيث يقوم المحلل اللغوي بإنشاء CST).

الأشجار في S ليست هي نفس ASTs T - فكر في XPath مقابل XPath.إكس إم إل - S يحمل التمثيل الشجري لـ XPaths، بينما T هو AST الفعلي للكود المصدري - أحتاج إلى خرائط بينهما i ومتجه للعقد المطابقة لـ T.

لكنني لست متأكدًا من أسماء الخوارزميات التي سأستخدمها.

في الأساس، أعرف ما أريد أن أفعله، يبدو الأمر وكأنه "تقسيم وآخرون للأشجار" مع مكدس حيث أحتفظ بالمرشحين المحتملين للمطابقة، في كل نوبة من محلل LALR أقوم بتكرار الجزء العلوي من المكدس وإزالة المرشحين i من S[i] والتي لن تتطابق على أي حال، وبعد التخفيض أخرجت من المكدس.في البداية جميع الأعضاء من S هم المرشحين المحتملين.

يرجى الملاحظة:هذا يتعلق فقط بـ AST، وASG قصة أخرى...

إضافة

هنا تكون شجرة التحليل T.

ستكون وظيفة التحليل على دراية بقائمة ما أسميه "مسارات الأشجار"، في شكل أساسي، ويتم تمثيلها أيضًا على شكل أشجار، مخزنة في S.لكنها لن تبدو مثل شجرة البارسيتري، بل لديها لغتها الخاصة التي سيتم تمثيلها بها، على غرار XPath.

مثال على مسار الشجرة للحصول على جميع الوظائف التي لها قيمة إرجاع متغيرة:

function[body[return[expr[@type="variable"]]]]]

1. إذن ما الذي يجب أن أبحث عنه في الأدبيات الموجودة؟
2. أي نصائح أخرى؟
3. هل توجد بالفعل لغات يمكنها الاستعلام عن الأشجار ذات التعليقات التوضيحية مثل هذا؟ستكون مكتبة C مفتوحة المصدر (وليس C++) مثالية.

Answer 1

1) تتوافق أشجار S الخاصة بك مثل XPath مع بعض أشجار T.لماذا لا يتم إنشاء أشجار T مسبقًا، ومن ثم مطابقة الأنماط بينها؟

2) إذا كنت تريد مطابقة نمط ما مع هيكل ما، يمكنك أن تتخيل تجميع النمط إلى نوع ما من أجهزة الحالة، والتي تنتقل عند مطابقة أجزاء معينة من الشجرة.إذا دخلت آلة الحالة في حالة قبول، فقد وجدت تطابقًا.إذا كان لديك أكثر من نمط واحد، فيمكن التعامل مع كل واحد منهم كآلة حالة ويمكنك تشغيلهم "بالتوازي" (عن طريق المحاكاة).ولجعل هذا فعالا، قم بحساب المنتج المتقاطع لجميع أجهزة الدولة؛الآن هناك انتقال واحد فقط، ويحدث انتقال واحد فقط لكل إدخال.هذه الفكرة أسميها "منتجات النمط" وترى شيئًا من هذا القبيل في مجموعة متنوعة من المطابقات الفعالة.واحد قريب مما تريد القيام به هو خوارزمية ريت, ، الذي يتتبع "الأنماط" الحية مع تغير البيانات التي يتم تغذيتها بها.

Answer 2

قد يكون من المفيد النظر في JXPath: http://commons.Apache.org/jxpath/لست متأكدًا من اللغة التي تستهدفها، ولكن قد يكون الأمر يستحق التجربة.

على أي حال، إن دافعي الأول إذا اضطررت إلى محاولة تنفيذ شيء كهذا سيكون إيجاد طريقة "لإجراء تسلسل" لكلتا الشجرتين، وتقليل المشكلة إلى مشكلة مطابقة سلسلة بسيطة.