(أشجار بناء الجملة) تكرار متكرر على الأشجار من أسفل إلى أعلى مع مسار من أعلى إلى أسفل الحالي

Question

انا لدي مجردة شجرة بناء الجملة الذي أحتاجه للتكرار. يتم إنشاء AST بواسطة منفذ الليمون إلى PHP.

الآن "عادة" ، سأفعل ذلك مع فصول SPL الجديدة واللامعة (PHP 5.3.1) ، وسيبدو هكذا:

$it = new \RecursiveIteratorIterator(
  new \RecursiveArrayIterator($ast['rule']),
  \RecursiveIteratorIterator::SELF_FIRST);

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

بالعودة إلى مشكلتي ، أحتاج إلى تكرار AST من أسفل إلى أعلى ، أي شيء مثل RecursiveIratoriterator :: child_first ، من أجل القيام ببعض البدائل والتحسينات في الشجرة.

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

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

الآن هذه كلمة رئيسية: التخزين المؤقت. هذا هو السبب في أنني أظن أنه يجب أن يكون ذلك ممكنًا مع فئة أخرى من SPL: RecursivecachingIterator.

والسؤال هو: هل هو ممكن حقا؟ إذا كانت الإجابة بنعم ، كيف؟

لقد كنت أحاول اللغز مع بعض التعليمات البرمجية ، دون نجاح ، والوثائق نادرة. حقا ، نادرة حقا.

كل من يجد الحل الأكثر أناقة لهذا باستخدام SPL ، قبالة القبعات! أنت معلم PHP!

ملاحظة: في حال لم يكن الأمر واضحًا ، فأنا أبحث عنه بقدر SPL (إعادة) الاستخدام قدر الإمكان. أعلم أنه يمكنني كتابة وظائف متكررة خاصة بي مع مكدس مخصص ، لا حاجة لتذكيرني بذلك.

Answer 1

لقد تمكنت من تشغيلها من خلال وراثة RecursiveIratoritorator وإدارة المكدس في :: endchildren () و :: Caregthildren على التوالي. ربما هذا سوف يساعد شخص ما. القبعات بنفسي :-)