قواعد الفوقية للمحلل PEG

نجعل هذا الأسبوع منشئ محلل "مستقلة" ، أي أنه سيتم إنشاء محلل خاص به.

لذلك ، لدينا بالفعل مولد محلل ، جزء منه هو محلل قواعد اللغة. يمكن أن نسميها المعرب اللغوي. يعمل المحلل اللغوي بطريقة مشابهة لما تم إنشاؤه: يرث GrammarParser من Parser ويستخدم نفس الآلية mark() / reset() / hope() . ومع ذلك ، كان هناك كل شيء مكتوب باليد. لكن هل هذا صحيح؟

عند تصميم برنامج التحويل البرمجي ، من المعتاد أن يتم كتابة برنامج التحويل البرمجي باللغة التي يجمعها. أتذكر بحب أن برنامج التحويل البرمجي Pascal الذي استخدمته عندما تعلمت البرنامج لأول مرة كان مكتوبًا في لغة Pascal نفسها ، ومجلس التعاون الخليجي مكتوبًا بلغة C ، ومترجم Rust مكتوب باللغة Rust.

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

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

فيما يلي نسخة مبسطة من المخطط دون إجراءات:

 start: rules ENDMARKER rules: rule rules | rule rule: NAME ":" alts NEWLINE alts: alt "|" alts | alt alt: items items: item items | item item: NAME | STRING 

سأريكم كيفية إضافة العمل من الأسفل إلى الأعلى. أذكر من الجزء 3 أن هناك كائنات Rule لها name alts . في البداية ، كانت alts مجرد قائمة بقوائم الخطوط (قائمة خارجية للبدائل وقائمة داخلية لكل عنصر من عناصر البديل) ، ولكن لتنفيذ الإجراءات ، قمت بتغييرها بحيث تم تمثيل البدائل items Alt مع items وسمات action . لا تزال العناصر ممثلة كسلاسل بسيطة. بالنسبة item الذي نحصل عليه:

 item: NAME { name.string } | STRING { string.string } 

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

فيما يلي items التي يجب أن تُرجع قائمة بالسلاسل:

 items: item items { [item] + items } | item { [item] } 

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

قاعدة alt لإنشاء كائن Alt :

 alt: items { Alt(items) } 

سوف أغفل الإجراءات الخاصة rules start ، كما هي محددة بهذه الطريقة.

ومع ذلك ، هناك سؤالان مفتوحان. أولاً ، كيف يمكنني العثور على تعريف Rule و Alt ؟ للقيام بذلك ، نحتاج إلى إضافة العديد من عبارات import إلى الشفرة التي تم إنشاؤها. إن أبسط طريقة هي تمرير العلامة إلى المولد ، الذي يقول "هذا هو قواعد التعريف" ، والسماح للمولد بإدراج import إضافي في بداية البرنامج الذي تم إنشاؤه. ولكن الآن بعد أن اتخذنا الإجراءات ، سيرغب العديد من المحللين الآخرين أيضًا في تخصيص الاستيراد الخاص بهم ، فلماذا لا نرى ما إذا كان يمكننا تطبيق نهج أكثر عمومية.

هناك العديد من الطرق لتنفيذه. تتمثل الآلية البسيطة والعامة في إضافة قسم "التعاريف المتغيرة" في الجزء العلوي من قواعد اللغة والسماح للمولد باستخدام هذه المتغيرات للتحكم في جوانب مختلفة من الشفرة التي تم إنشاؤها. قررت استخدام الرمز @ لبدء تحديد المتغير ، متبوعًا باسم المتغير ( NAME ) والقيمة ( STRING ). على سبيل المثال ، يمكننا وضع مقطع التعليمات البرمجية التالي في الجزء العلوي من قواعد التعريف:

 @subheader "from grammar import Rule, Alt" 

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

 @subheader """ from token import OP from grammar import Rule, Alt """ 

هذا سهل الإضافة إلى قواعد التعريف: سنقسم قاعدة start إلى ما يلي:

 start: metas rules ENDMARKER | rules ENDMARKER metas: meta metas | meta meta: "@" NAME STRING NEWLINE 

(لا أستطيع أن أتذكر لماذا سميت "meta" ، لكنني اخترت هذا الاسم عندما كتبت الكود ، وسألتزم به. :-)

يجب أن نضيف هذا إلى metaparser bootstrap. الآن وبعد أن أصبحت قواعد اللغة ليست مجرد قائمة من القواعد ، دعنا نضيف كائنًا metas بخصائص التعريف rules . يمكننا ضبط الإجراءات التالية:

 start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING { (name.string, eval(string.string)) } 

(لاحظ أن meta تُرجع tuple ؛ وأيضًا تستخدم eval() لمعالجة علامات اقتباس السلسلة.)

لم أذكر تنفيذ الإجراءات في قواعد alt ! والسبب هو أنهم يخرجون قليلا الفوضى. لكن ليس من المنطقي أن تؤجل أكثر ، لذلك هنا:

 alt: items action { Alt(items, action) } | items { Alt(items, None) } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string } 

سبب الأوساخ في التعريف هو رغبتي في جعل كود Python التعسفي ساري المفعول بين أقواس مجعد ، بما في ذلك متداخلة في أقواس مجعد أخرى. لهذا الغرض ، نستخدم رمز مميز خاصًا يقوم بإنشاء الرمز المميز الخاص بنا لجميع علامات الترقيم المعترف بها من قِبل Python (إرجاع رمز مميز واحد مع نوع OP لمشغلات متعددة الأحرف مثل <= أو ** ). الرموز الأخرى الوحيدة التي يمكن أن تحدث في تعبيرات Python هي الأسماء والأرقام والسلاسل. وبالتالي ، يمكن التعبير عن الكود بين الأقواس الخارجية للعمل ، من خلال تكرار NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP NAME | NUMBER | STRING | OP .

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

باستخدام هذا الاختراق الصغير ، يمكننا أن نجعل المقارنة على OP تقع على قوس مجعد. ثم المقارنة بين stuff action سيكون ممكنا.

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

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

 @subheader """ from grammar import Grammar, Rule, Alt from token import OP """ start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } metas: meta metas { [meta] + metas } | meta { [meta] } meta: "@" NAME STRING NEWLINE { (name.string, eval(string.string)) } rules: rule rules { [rule] + rules } | rule { [rule] } rule: NAME ":" alts NEWLINE { Rule(name.string, alts) } alts: alt "|" alts { [alt] + alts } | alt { [alt] } alt: items action { Alt(items, action) } | items { Alt(items, None) } items: item items { [item] + items } | item { [item] } item: NAME { name.string } | STRING { string.string } action: "{" stuffs "}" { stuffs } stuffs: stuff stuffs { stuff + " " + stuffs } | stuff { stuff } stuff: "{" stuffs "}" { "{" + stuffs + "}" } | NAME { name.string } | NUMBER { number.string } | STRING { string.string } | OP { None if op.string in ("{", "}") else op.string } 

الآن بعد أن أصبح لدينا قاعدة عمل وصفية ، نحن على استعداد تقريبًا لإجراء بعض التحسينات.

لكن عليك أولاً التفكير قليلاً: خطوط فارغة! اتضح أن الوحدة النمطية لرمز stdlib تنشئ رموزًا إضافية لتتبع tokenize غير المهمة (الرمز المميز لـ NL ) والتعليقات (الرمز المميز للتعليق). بدلاً من تضمينها في القواعد (حاولت ، هناك القليل من المرح!) ، هناك جزء بسيط جدًا من التعليمات البرمجية التي يمكننا إضافتها إلى فئة الرموز المميزة لتصفيتها. إليك طريقة peek_token المحسّنة:

  def peek_token(self): if self.pos == len(self.tokens): while True: token = next(self.tokengen) if token.type in (NL, COMMENT): continue break self.tokens.append(token) self.report() return self.tokens[self.pos] 

هذا يزيل تماما الرموز المميزة NL و COMMENT ، لذلك لم نعد بحاجة للقلق بشأنها في القواعد.

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

 start: metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } 

هذا يرجع إلى حقيقة أن الرمز المميز ينشئ رمز مميز لـ NEWLINE في نهاية السطر الأول ، وفي هذه اللحظة سيعتبر المحلل اللغوي هذا هو نهاية القاعدة. علاوة على ذلك ، سوف يتبع هذا NEWLINE الرمز المميز لـ INDENT ، لأن السطر التالي تم وضعه في مسافة بادئة. حتى بداية القاعدة التالية ، سيكون رمز DEDENT أيضًا.

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

 $ python -m tokenize foo bar baz dah dum ^D 

نرى أن هذا ينتج التسلسل التالي من الرموز (لقد قمت بتبسيط الإخراج من الكود أعلاه قليلاً):

 NAME 'foo' NAME 'bar' NEWLINE INDENT NAME 'baz' NEWLINE NAME 'dah' NEWLINE DEDENT NAME 'dum' NEWLINE 

وبالتالي ، تتم الإشارة إلى مجموعة محددة من السلاسل بواسطة DEDENT و DEDENT . الآن يمكننا إعادة كتابة rule النحوية rule كما يلي:

 rule: NAME ":" alts NEWLINE INDENT more_alts DEDENT { Rule(name.string, alts + more_alts) } | NAME ":" alts NEWLINE { Rule(name.string, alts) } | NAME ":" NEWLINE INDENT more_alts DEDENT { Rule(name.string, more_alts) } more_alts: "|" alts NEWLINE more_alts { alts + more_alts } | "|" alts NEWLINE { alts } 

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

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

 start: | metas rules ENDMARKER { Grammar(rules, metas) } | rules ENDMARKER { Grammar(rules, []) } 

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

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

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