اليسار عودي PEG النحوي

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

النظر في هذه القاعدة النحوية القاعدة:

expr: expr '+' term | term 

إذا قمنا بتطبيق هذه القطعة من القواعد في طريقة المحلل اللغوي العودية اليسرى ، فسنحصل على شيء مثل التالي:

 def expr(): if expr() and expect('+') and term(): return True if term(): return True return False 

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

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

 expr: term '+' expr | term 

ومع ذلك ، في خطوة بناء شجرة التحليل ، سيكون شكلها مختلفًا. قد يؤدي ذلك إلى تدمير الموقف إذا أضفنا عامل التشغيل '-' إلى القواعد (نظرًا لأن a - (b - c) ليست a - (b - c) نفسها (a - b) - c ). يتم حل هذا عادةً مع وظائف PEG أكثر قوة ، مثل التجميع والتكرار ، ويمكننا إعادة كتابة القاعدة أعلاه على النحو التالي:

 expr: term ('+' term)* 

في الواقع ، هذه هي الطريقة التي يتم بها كتابة قواعد Python النحوية الحالية لمحلل pgen (الذي لديه نفس المشكلات مع القواعد العودية اليسرى).

ومع ذلك ، هناك مشكلة صغيرة: نظرًا لأن المشغلين مثل '+' و '-' (في بيثون) يكونون في الغالب ثنائيون ، عندما نحلل شيئًا مثل a + b + c ، يتعين علينا أن ننتقل إلى نتيجة التحليل (الذي بشكل أساسي قائمة بـ ['a', '+', 'b', '+', 'c'] ) لإنشاء شجرة تحليل متكررة يسارية (والتي تبدو مثل هذا [['a', '+', 'b'] , '+', 'c'] ).

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

دعونا نلقي نظرة على مثال المدخلات foo + bar + baz . تتوافق شجرة التحليل التي نود الحصول عليها من هذا (foo + bar) + baz . يتطلب هذا ثلاثة مكالمات عودية اليسار إلى الدالة expr() : واحد يتوافق مع المشغل المستوى الأعلى '+' (أي ، الثاني) ؛ واحد إضافي - إلى المشغل الداخلي '+' (أي الأول) ؛ والثالث هو اختيار البديل الثاني (على سبيل المثال ، term ).

نظرًا لأنني لست جيدًا في رسم مخططات حقيقية باستخدام أدوات خاصة ، فسأعرض ذلك هنا باستخدام فن ASCII:

 expr------------+------+ | \ \ expr--+------+ '+' term | \ \ | expr '+' term | | | | term | | | | | 'foo' 'bar' 'baz' 

تتمثل الفكرة في أننا في دالة expr() ، نحتاج إلى "oracle" تخبرنا ما إذا كان يجب اختيار البديل الأول (أي ، الدعوة العودية إلى expr() ) أو الثانية (أي ، term() call call))). في أول استدعاء expr() يجب أن تخبرنا أوراكل باتباع البديل الأول ( expr() ) ؛ في المكالمة الثانية (العودية) - بالمثل ، لكن في المكالمة الثالثة يجب أن تطالبنا بالاتصال term() . في الكود ، سيبدو كما يلي:

 def expr(): if oracle() and expr() and expect('+') and term(): return True if term(): return True return False 

كيف تكتب أوراكل؟ دعونا نرى ... يمكن أن نحاول تتبع عدد (يسار العودية) المكالمات إلى expr() في مكدس المكالمات ومقارنتها مع عدد من '+' المشغلين في التعبير التالي. إذا كانت رصة المكالمة أعمق من عدد البيانات ، فيجب أن تعيد أوراكل خطأ (إجبارنا على اختيار term() ). لا يمكنني الانتظار لتنفيذ ذلك باستخدام sys._getframe() ، ولكن هناك طريقة أفضل: sys._getframe() مكدس المكالمة!

والفكرة هي أننا نبدأ بمكالمة حيث إرجاع أوراكل كاذبة ، وحفظ النتيجة. هذا يعطينا تسلسل expr() -> term() -> 'foo' . (يجب أن تُرجع شجرة التحليل term الأولي ، أي 'foo' . التعليمة البرمجية أعلاه تُرجع " True فقط ، ولكن في الجزء الثاني من سلسلة المقالات التي سبق لي أن أوضحت كيفية إرجاع شجرة التحليل بدلاً من ذلك.) ما False سوى إرجاع False على المكالمة الأولى - لا يلزم التحقق من المكدس أو التحديق في المستقبل.

ثم ندعو expr() مرة أخرى ، وهذه المرة تعيد oracle إرجاع True ، ولكن بدلاً من استدعاء العودية اليسرى إلى expr() النتيجة المحفوظة من المكالمة السابقة. ونظرًا لوجود عامل التشغيل المتوقع '+' والرمز المناسب التالي موجودان ، فسوف يعطينا هذا شجرة تحليل لـ foo + bar .

مرة أخرى نكرر الخوارزمية ، ومرة ​​أخرى يتحول كل شيء: هذه المرة نحصل على شجرة تحليل للتعبير الكامل ، وهي حقًا تكرارية العودية ( (foo + bar) + baz ).

ثم نكرر الخوارزمية مرة أخرى. ولكن هذه المرة ، على الرغم من إرجاع Oracle لقيمة True ، وكانت النتيجة المحفوظة للمكالمة السابقة متاحة أيضًا ، إلا أنه لم يعد هناك عامل '+' ، وفشل البديل الأول. وبالتالي ، نجرب الخيار الثاني ، الذي نجح ، ونجد المصطلح الأولي فقط ( 'foo' ). هذه النتيجة أسوأ من النتيجة التي تم الحصول عليها من البديل الأول ، لذلك في هذه المرحلة نتوقف ونوفر أطول تحليل (على سبيل المثال (foo + bar) + baz ).

لتحويل هذا إلى رمز عمل ، قمت أولاً بتعديل الخوارزمية قليلاً لدمج استدعاء oracle() مع استدعاء العودية اليسرى إلى expr() . دعنا نسميها oracle_expr() . كود:

 def expr(): if oracle_expr() and expect('+') and term(): return True if term(): return True return False 

بعد ذلك ، سوف نكتب غلافًا يطبق المنطق الموصوف أعلاه. يستخدم متغير عمومي (لا تقلق ، سوف أتخلص منه لاحقًا). oracle_expr() دالة oracle_expr() بقراءة المتغير العام ، وسوف يتحكم المجمع في:

 saved_result = None def oracle_expr(): if saved_result is None: return False return saved_result def expr_wrapper(): global saved_result saved_result = None parsed_length = 0 while True: new_result = expr() if not new_result: break new_parsed_length = <calculate size of new_result> if new_parsed_length <= parsed_length: break saved_result = new_result parsed_length = new_parsed_length return saved_result 

الكود ، بالطبع ، فظيع ، لكنه على الأقل ينقل جوهر الخوارزمية. دعنا نصلحها حتى نفتخر بها.

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

لذلك ، نحن بحاجة إلى @memoize_left_rec ديكور منفصل ، والذي يستخدم فقط للقواعد العودية اليسرى. يستدعي الدالة oracle_expr() ، وسحب القيمة المخزنة من ذاكرة التخزين المؤقت للتذكير ، ويحتوي على حلقة تستدعي الدالة expr() عدة مرات ، حتى تكون كل نتيجة جديدة قابلة للمقارنة مع جزء أطول من بيانات الإدخال من السابقة. وبالطبع ، نظرًا لأن كل موضع إدخال وكل طريقة تحليل يتم تخزينها بشكل منفصل ، فإنها لا تشعر بالقلق إزاء التراجع أو بعض القواعد العودية (على سبيل المثال ، في قواعد اللعبة التي استخدمتها ، يتم ترك كلٍّ من expr و term كلمتين متكررة).

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

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

دعنا نكتب رمز المعركة.

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

 def is_left_recursive(rule): for alt in rule.alts: if alt[0] == rule.name: return True return False 

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

كمرجع ، إليك نسخة @memoize decorator الأصلية @memoize ، والتي تم نسخها من الجزء 3. تذكر أن self عبارة عن مثيل Parser له سمة memo (تمت تهيئته بقاموس فارغ) mark() و reset() التي تحصل على الوضع الحالي وتعيينه tokenizer:

 def memoize(func): def memoize_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else: res = func(self, *args) endpos = self.mark() memo[key] = res, endpos return res return memoize_wrapper 

يتذكر @memoize الدعوات السابقة لكل موضع في دفق الإدخال - لكل موقع في مجموعة (كسول) من الرموز المميزة للإدخال يوجد قاموس memo منفصل. الأسطر الأربعة الأولى من memoize_wrapper مخصصة للحصول على قاموس memo الصحيح.

وهنا @memoize_left_rec . فقط الفرع else يختلف قليلاً عن التنفيذ في @memoize أعلاه:

 def memoize_left_rec(func): def memoize_left_rec_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else: # Prime the cache with a failure. memo[key] = lastres, lastpos = None, pos # Loop until no longer parse is obtained. while True: self.reset(pos) res = func(self, *args) endpos = self.mark() if endpos <= lastpos: break memo[key] = lastres, lastpos = res, endpos res = lastres self.reset(lastpos) return res return memoize_left_rec_wrapper 

من المثير للاهتمام كيف يعمل هذا مع طريقة expr() . دعونا نرى كيف سيتم تنفيذ التعليمات البرمجية التالية:

  @memoize_left_rec def expr(self): pos = self.mark() if ((expr := self.expr()) and self.expect('+') and (term := self.term())): return Node('expr', [expr, term]) self.reset(pos) if term := self.term(): return Node('term', [term]) self.reset(pos) return None 

على سبيل المثال تحليل foo + bar + baz .

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

ماذا يحدث بعد ذلك؟ يتم احتساب قيمة ذاكرة التخزين المؤقت الأولية في هذا السطر:

  # Prime the cache with a failure. memo[key] = lastres, lastpos = None, pos 

يؤدي هذا إلى حقيقة أن expr() المُزخرفة None تُرجع إلى None ، وبعدها يقع أول if في expr() (عند expr: = self.expr() ). وهذا هو ، ننتقل إلى الثاني if ، الذي يتعرف بنجاح على term (في مثالنا ، 'foo' ) ويعيد expr مثيل Node . من أين نعود؟ إلى while في الديكور. نقوم بتحديث ذاكرة التخزين المؤقت للمذكرة مع نتيجة جديدة (مثيل Node ) ، ثم نقوم بتشغيل التكرار التالي.

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

لذا ، فإن expr() ، بعد أن تم التعرف بالفعل على foo + bar ، يعود إلى while ، التي تقوم بتنفيذ نفس الإجراءات: تقوم بتحديث ذاكرة التخزين المؤقت للتذكير بنتيجة جديدة (أطول) وتبدأ التكرار التالي.

تتكرر هذه اللعبة مرة أخرى. مرة أخرى ، يسترجع expr() نداء foo + bar المعترضة نتيجة جديدة (هذه المرة foo + bar ) من ذاكرة التخزين المؤقت ، ونتوقع رؤية '+' (ثانيًا) term آخر ( 'baz' ). نقوم بإنشاء Node تمثل (foo + bar) + baz ، (foo + bar) + baz إلى while ، والتي تضعها في ذاكرة التخزين المؤقت وتتكرر مرة أخرى.

ولكن الآن سنذهب إلى جانب فرع آخر من الخوارزمية. نتوقع مقابلة '+' ، لكن لا تجدها! وبالتالي ، هذه الدعوة إلى expr() ترجع إلى البديل الثاني ، وتُرجع term فقط. عندما ينبثق هذا قبل while ، يتبين أن هذه النتيجة أقصر من الأخيرة. لذلك تقاطع وترجع نتيجة أطول ( (foo + bar) + baz ) إلى الشخص الذي بدأ استدعاء expr() (على سبيل المثال ، لا يتم استدعاء المكالمة statement() هنا).

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

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

ترخيص لهذه المقالة ورمز استشهد: CC BY-NC-SA 4.0