تنفيذ الميزات المتبقية من PEG

بعد أن جمعت جميع أجزاء مولد PEG-parser معًا في المنشور السابق ، أنا مستعد لإظهار كيفية تنفيذ بعض الأشياء الأخرى المثيرة للاهتمام.

سننظر في الميزات التالية لـ PEG:

• العناصر المسماة: NAME=item (يمكن استخدام الاسم في الإجراء)
• عناصر النظافة: &item (إيجابي) و !item (سلبي)
• تجميع العناصر بين قوسين: ( item item ... )
• العناصر الاختيارية: [item item ...] item?
• العناصر المكررة: item* (صفر أو أكثر) item+ (واحد أو أكثر)

الحجج المسماة

لنبدأ بالعناصر المسماة. هذا مناسب عندما يكون لدينا العديد منهم في بديل واحد لنفس القاعدة ، على سبيل المثال:

 expr: term '+' term 

يمكننا الرجوع إلى term الثاني عن طريق إضافة الرقم 1 إلى اسم المتغير ، بحيث يتضح في الإجراء ما يلي:

 expr: term '+' term { term + term1 } 

لكن لا يحب الجميع ذلك ، وأنا شخصياً أفضل أن أكتب شيئًا مثل هذا:

 expr: left=term '+' right=term { left + right } 

يتم دعم هذا بسهولة في قواعد التعريف عن طريق تغيير قاعدة item كما يلي:

 item: | NAME = atom { NamedItem(name.string, atom) } | atom { atom } atom: | NAME { name.string } | STRING { string.string } 

(حيث atom ليست سوى عنصر قديم)

يتطلب ذلك منا إضافة تعريف الفئة grammar.py إلى grammar.py . إنها إحدى فئات البيانات التي ذكرتها سابقًا - لها أيضًا سمات name والعنصر.

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

Lookahead

تليها lookahead. ربما صادفت هذا المفهوم في تعبيرات منتظمة. أثناء واجهة البحث الأمامية ، يمكن رفض البديل المعرب أو قبوله على الفور ، دون تحريك مؤشر الرمز المميز.

في الواقع ، يمكن استخدام واجهة البحث كوسيلة أكثر أناقة لإزالة الالتباس مع استثناءات المحلل اللغوي ، والتي كتبت عنها في مقالة سابقة. بدلاً من السماح للإجراءات برفض بديل مقبول بالفعل من خلال إرجاع بلا ، يمكننا إضافة تعليمة قبل OP لاستبعاد "}" . القاعدة القديمة تبدو مثل هذا:

  | OP { None if op.string in ("{", "}") else op.string } 

الإصدار الجديد يشبه هذا:

  | !"}" OP { op.string } 

يؤدي هذا إلى نقل معالجة القوس المجعد من الإجراء إلى القواعد النحوية ، حيث ينتمي. لا نحتاج إلى التحقق من "{" ، لأنه يتوافق مع بديل سابق (في الواقع ، هذا صحيح أيضًا بالنسبة للإصدار القديم ، لكني نسيت ذلك :-).

نضيف قواعد النحو ل lookaheads إلى القاعدة item النحو التالي:

 item: | NAME = atom { NamedItem(name.string, atom) } | atom { atom } | "&" atom { Lookahead(atom, True) } | "!" atom { Lookahead(atom, False) } 

مرة أخرى ، نحتاج إلى إضافة قاعدة بيانات Lookahead إلى grammar.py (واستيرادها إلى @subheader !) وتعديل المولد قليلاً بإضافة طريقة المساعد التالية:

  def lookahead(self, positive, func, *args): mark = self.mark() ok = func(*args) is not None self.reset(mark) return ok == positive 

في حالتنا ، يبدو الرمز الذي تم إنشاؤه لهذا البديل كما يلي:

  if (True and self.lookahead(False, self.expect, "}") and (op := self.expect(OP)) ): return op . string 

كما ترون من جزء القواعد أعلاه ، لا يمكن أن تحصل lookahead على أسماء مناسبة. هذا سهل الإصلاح ، لكن لا يزال لدي فكرة عن مدى فائدة ذلك. بالإضافة إلى ذلك ، بالنسبة للتوقعات السلبية ، ستكون القيمة دائمًا بلا.

التجمع بين قوسين

الآن لننفذ مجموعات ذات أقواس. أفضل مكان لإضافتها إلى المخطط هو قاعدة atom :

 atom: | NAME { name.string } | STRING { string.string } | "(" alts ")" { self.synthetic_rule(alts) } 

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

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

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

  | !("{" | "}") OP { op.string } 

علاوة على ذلك ، يمكن أن تحتوي المجموعات أيضًا على إجراءات! هذا لن يساعد في حل المشكلة مع الإجراءات ، ولكن في حالات أخرى قد يكون مفيدًا. ونظرًا لأننا في أي حال نقوم بإنشاء قاعدة تركيبية ، فإنه لا يتطلب أي عمل إضافي لتنفيذه (باستثناء تطبيق synthetic_rule :-).

العناصر الاختيارية

كما هو الحال في pgen القديم ، أستخدم الأقواس المربعة للإشارة إلى مجموعة من الرموز المميزة. هذا هو المكان الذي اتضح أنه مفيد. على سبيل المثال ، يمكن لقاعدة النحو التي تصف Python for loop استخدامها للإشارة إلى أن امتدادًا else يمكن أن يوجد. ومرة أخرى يمكننا توسيع قواعد اللغة atom كما يلي:

 atom: | NAME { name.string } | STRING { string.string } | "(" alts ")" { self.synthetic_rule(alts) } | "[" alts "]" { Maybe(self.synthetic_rule(alts)) } 

هنا Maybe هناك فئة بيانات أخرى ، مع سمة item واحد. نقوم بتعديل مولد الشفرة بحيث لا تفشل نتيجة الوظيفة التركيبية إذا كانت هذه القيمة بلا. للقيام بذلك ، يمكنك إضافة or True في التنفيذ. على سبيل المثال ، من أجل [term] :

 if (True and ((term := self.term()) or True) ): return term 

العناصر المكررة

التبديل إلى التكرار هو وظيفة PEG مفيدة أخرى (يتم استعار الترميز من التعبيرات العادية ويستخدم أيضًا في pgen). هناك نموذجان: تعني إضافة * إلى ذرة "صفر أو أكثر من التكرار" ، بينما تعني إضافة + "تكرار واحد أو أكثر". لأسباب أخرى ، اضطررت إلى إعادة كتابة القواعد النحوية item atom ، مع إضافة قاعدة وسيطة ، والتي molecule :

 item: | NAME '=' molecule { NamedItem(name.string, molecule) } | "&" atom { Lookahead(atom) } | "!" atom { Lookahead(atom, False) } | molecule { molecule } molecule: | atom "?" { Maybe(atom) } | atom "*" { Loop(atom, False) } | atom "+" { Loop(atom, True) } | atom { atom } | "[" alts "]" { Maybe(self.synthetic_rule(alts)) } atom: | NAME { name.string } | STRING {string.string } | "(" alts ")" { self.synthetic_rule(alts) } 

لاحظ أن هذا يقدم بناء جملة بديل للعناصر الاختيارية ( atom? ). لا يتطلب الأمر جهودًا إضافية للتنفيذ ، لأن هذه مجرد طريقة أخرى لإنشاء عقدة Maybe .

كانت إعادة تفعيل هذه القواعد ضرورية لأنني لا أرغب في جعل بعض المواقف صالحة:

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

ومع ذلك ، لا يزال هذا الحل غير مثالي ، حيث يمكنك كتابة شيء مثل (foo?)* . سيكون من الضروري إضافة فحص لهذا الموقف في منشئ المحلل اللغوي ، لكنني سأفعل ذلك خارج المقالة.

تحتوي فئة بيانات Loop على سمتين: item وغير nonempty . سيستخدم الرمز الذي تم إنشاؤه طريقة محلل مساعد loop() . إنه مشابه جدًا lookahead() الموضحة مسبقًا:

  def loop(self, nonempty, func, *args): mark = self.mark() nodes = [] while node := func(*args) is not None: nodes.append(node) if len(nodes) >= nonempty: return nodes self.reset(mark) return None 

إذا كانت قيمة nonempty False (بمعنى أن القواعد كانت * ) ، فلن يؤدي ذلك إلى حدوث خطأ. لن يتم العثور على إدخالات ، وسيتم إرجاع قائمة فارغة. لتحقيق ذلك ، نقوم بتطبيق مولد المحلل اللغوي بحيث is not None إضافة بلا. سيؤدي الاختيار الأكثر نعومة من منشور سابق إلى إرجاع False في حالة وجود قائمة فارغة.

هذا كل شيء لهذا اليوم! كنت سأناقش عامل التشغيل "cut" ( ~ ) الموجود في TatSu ، لكن حتى الآن لم تتح لي الفرصة لمواجهته. لست مستعدًا حتى الآن لمناقشته - فوثائق TatSu لا تقدم سوى مثال بسيط يهتم بي قليلاً. لم أجدها في مولدات أخرى من PEG-parsers ، لذلك ، ربما ، هذه الميزة هي TatSu فقط. ربما يوما ما سأقول عنه. (وفي الوقت نفسه ، قمت بتنفيذها فقط في حالة ، أنت لا تعرف أبدا. :-)

أعتقد أن المقالة التالية ستكون عن تجربتي في كتابة قواعد PEG التي يمكنها تحليل قواعد Python. سوف أخبركم كيف حدث سباق مطوري Python kernel ، الذي كان في لندن هذا الأسبوع بدعم لوجيستي من بلومبرج ودعم مالي من PSF وبعض الشركات الأخرى (على سبيل المثال ، دفعت Dropbox لي الفندق والطيران). شكر خاص لإميلي مورهاوس وبابلو غاليندو سالغادو ، الذين ساعدوا كثيرا في تنفيذ الأدوات والاختبارات. بعد ذلك ، سنكتب اختبارات الأداء ، ومن ثم سنقوم بإضافة إجراءات إلى هذا النحو حتى تتمكن من إنشاء أشجار AST التي يمكن تجميعها بواسطة برنامج التحويل البرمجي لرمز بايت CPython. هناك أشياء أكثر إثارة للاهتمام في المستقبل!

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