قبل بضع سنوات ، سألني شخص ما إذا كان من المنطقي تحويل Python إلى محلل PEG (أو إلى PEG النحو ؛ لا أتذكر بالضبط من ومتى كان ذلك). ثم نظرت إليه قليلاً ، لكنني لم أتوصل إلى أي استنتاج ، وبالتالي أسقطت هذا الموضوع. لقد تعلمت مؤخرًا المزيد عن PEG (Parsing Expression Grammars و Parsing Expression Grammar) ، والآن أعتقد أن هذا بديل مثير للاهتمام لمولد المحلل اللغوي المكتوب ذاتيًا والذي تم تطويره قبل 30 عامًا عندما بدأت العمل في Python. لقد أطلق عليها "pgen" ، وربما كان هذا الجزء الأول من الكود الذي كتبته لبيثون.
بيثون PEG محلل سلسلة المحتوى السبب في أنني مهتم حاليًا بمحلل PEG هو أنني أشعر بالانزعاج إلى حد ما بسبب قيود pgen. إنه مبني على تطبيق LL (1) الخاص به ، والذي يحتوي على عدد من الافتراضات. على سبيل المثال ، لم يعجبني قواعد القواعد التي يمكن أن تنشئ سطور فارغة ، لذا فقد حظرتها. وبالتالي تبسيط الخوارزمية لإنشاء تحليل الجداول. اخترعت أيضًا تدوين القواعد الخاصة بي ، مثل IBNF ، والتي ما زلت أحبها حقًا.
وهنا بعض المشاكل مع بابوا نيو غينيا التي تزعجني. يشير "1" في الاسم LL (1) إلى أنه يحلل الرمز المميز التالي فقط ، وهذا يحد من قدرتنا على إنشاء قواعد نحوية جيدة. على سبيل المثال ، قد تكون عبارة Python تعبيرًا أو مهمة (أو أي شيء آخر ، ولكنها تبدأ جميعًا بكلمة رئيسية مميزة ، مثل if أو def ). أود وصف بناء الجملة باستخدام تدوين pgen. لاحظ أن هذا مجرد مثال مبسط ، وهو مجموعة فرعية من بيثون ، كما يحدث عادة عند وصف تصميم اللغة. سيكون هذا قواعد لعبة سوف تكون مفيدة لمزيد من التوضيح.
statement: assignment | expr | if_statement expr: expr '+' term | expr '-' term | term term: term '*' atom | term '/' atom | atom atom: NAME | NUMBER | '(' expr ')' assignment: target '=' expr target: NAME if_statement: 'if' expr ':' statement
بضع كلمات حول التدوين: NAME و NUMBER من الرموز المميزة ويتم تحديدهما مسبقًا خارج القواعد. السلاسل المقتبسة من النوع '+' أو 'if' هي أيضًا رموز. (لنؤجل الحديث عنهم في المرة القادمة) تبدأ قواعد القواعد باسم القاعدة ، متبوعة بـ : ثم واحد أو أكثر من البدائل ، مفصولة بـ | .
المشكلة هي أنه إذا وصفت القواعد بهذه الطريقة ، فلن يعمل pgen. هذا يرجع إلى حقيقة أن بعض القواعد ( expr و term ) تُركت متكررة ، وهو غير ذكي بما يكفي للتعامل مع مثل هذه المواقف بشكل صحيح. عادة ما يتم حل هذا عن طريق إعادة كتابة هذه القواعد فقط ، مع ترك القواعد الأخرى دون تغيير. على سبيل المثال:
expr: term ('+' term | '-' term)* term: atom ('*' atom | '/' atom)*
يكشف هذا العديد من إمكانيات EBNF في pgen: يمكنك تداخل البدائل بين قوسين وإنشاء التكرارات عن طريق وضع * بعد العنصر. لذا فإن قاعدة التعبير expr هنا تعني "إنه مصطلح متبوعًا بتكرار صفري أو أكثر من التسلسل <مصطلح زائد أو ناقص ، متبوعًا بكلمة">. تأخذ هذه القواعد نفس لغة الإصدار الأول ، لكنها مرة أخرى لا تعكس القصد من تصميم اللغة. على وجه الخصوص ، لا يُظهر أن عوامل التشغيل مقيدة على اليسار ، وهذا أمر مهم عندما تحاول إنشاء رمز.
ولكن هناك مشكلة مزعجة أخرى في هذا المثال (وفي بيثون أيضًا). بسبب تحليل رمز مميز واحد فقط ، لا يمكن للمحلل تحديد ما ينظر إليه - بداية تعبير أو مهمة. في بداية معالجة المشغل ، يجب أن يقرر المحلل اللغوي الرمز المميز الأول فقط ، وهو البديل الذي يوزعه. (لماذا؟ هذه هي الطريقة التي يعمل بها تنفيذ تحليل pgen). دعنا نقول برنامجنا كما يلي:
answer = 42
يتم تمثيل هذا البرنامج بثلاثة رموز: NAME (مع قيمة answer ) ، = و NUMBER (بقيمة 42 ). الشيء الوحيد الذي نعرفه في بداية التحليل هو أول رمز مميز لـ NAME . القاعدة التي نحاول تحليلها في هذه المرحلة هي statement (الحرف الأولي للقواعد). يتم تحديد ثلاثة بدائل له: expr ، assignment و if_statement . يمكننا استبعاد if_statement الفور ، لأن الرمز السابق ليس if . ولكن يمكن أن يبدأ كل من expr assignment برمز NAME ، ولهذا السبب ، يرفض pgen قواعدنا النحوية باعتبارها غامضة.
هذا ليس صحيحًا تمامًا ، نظرًا لأن القواعد الفنية نفسها ليست كذلك ؛ لا يمكنني العثور على صيغة أكثر دقة ، لذلك دعونا نتحدث عن هذه الصيغة. وكيف يحل pgen هذا؟ إنه يحسب شيئًا ما يسمى مجموعة FIRST لكل قاعدة قواعد نحوية ، وإذا تقاطعها ، فسيكون ذلك استثناءً.
لذلك ، لا يمكننا حل هذه المشكلة من خلال توفير محلل مع عرض عازلة أكبر؟ على سبيل المثال لدينا ، الرمز المميز للمعاينة الثاني يكفي ، لأنه في هذا النحو يجب أن يكون الرمز المميز للواجهة الثانية = . ولكن بلغة أكثر واقعية مثل Python ، قد تحتاج إلى مخزن مؤقت غير محدود ، لأن المحتوى على يسار = token = يمكن أن يكون معقدًا بشكل تعسفي ، على سبيل المثال:
table[index + 1].name.first = 'Steven'
في هذه الحالة ، سيتعين عليك تحليل عشرة رموز قبل أن نلتقي = . ولكني أؤكد لكم أنه قد يكون هناك تعبيرات أطول. لحل هذه المشكلة في pgen ، قمنا بتغيير محلل القواعد لقبول بعض التعبيرات غير الصحيحة ، بإضافة فحص إضافي في مسار لاحق. سوف يلقي خطأ SyntaxError إذا كان لا يمكن أن يطابق الجانبين الأيسر والأيمن. بالنسبة إلى لعبتنا اللغوية ، يتعلق الأمر بكتابة ما يلي:
statement: assignment_or_expr | if_statement assignment_or_expr: expr ['=' expr]
تشير الأقواس المربعة إلى جزء اختياري. وبعد ذلك في المرحلة التالية من برنامج التحويل البرمجي (على سبيل المثال ، عند إنشاء رمز bytecode) نتحقق مما إذا كانت = أو لا ، وإذا تحقق ذلك ، فإننا نتحقق من تطابق الجانب الأيسر مع بناء الجملة target .
هناك مشكلة مماثلة للوسائط استدعاء دالة. نود كتابة شيء مثل هذا (مرة أخرى ، في نسخة مبسطة من بناء جملة Python):
call: atom '(' arguments ')' arguments: arg (',' arg) * arg: posarg | kwarg posarg: expr kwarg: NAME '=' expr
لكن خوارزمية التحليل ، التي ستأخذ بعين الاعتبار الرمز التالي فقط ، لا يمكنها إخبار المحلل ما إذا كان NAME في بداية الوسيطات هو بداية posarg (حيث يمكن أن تبدأ expr بـ NAME ) أو بداية kwarg . مرة أخرى ، يحل محلل Python الحالي هذه المشكلة عن طريق تحديد:
arg: expr ['=' expr]
ثم يكمل البديل في تمرير مترجم لاحق. (لقد ارتكبنا خطأً بسيطًا foo((a) = 1) تمامًا مثل foo(a = 1) . تم إصلاح ذلك فقط في Python 3.8)
فكيف يحل محلل PEG هذه المشكلات؟ باستخدام المخزن المؤقت النسخ الاحتياطي لانهائية! يستخدم تطبيقه النموذجي ما يسمى محلل packrat ، الذي لا يقوم فقط بتحميل البرنامج بأكمله في الذاكرة قبل تحليله ، ولكنه يسمح أيضًا بإعادة المحلل إلى عدد تعسفي من الرموز المميزة. على الرغم من أن مصطلح PEG يشير في المقام الأول إلى التدوين النحوي ، إلا أن المحللون المولدين من قواعد PEG هم عادةً محللون ذو أصل متكرر وعائد غير محدود. يعمل محلل packrat على جعل الأنا فعالة من خلال تذكر القواعد التي تم تحليلها بالفعل لمواقع محددة.
هذا يبسط الخوارزمية ، ولكن بالطبع هناك ثمن: الذاكرة. قبل ثلاثين عامًا ، كان لدي سبب وجيه لاستخدام LL (1): كانت الذاكرة باهظة الثمن. إنه (مثل التقنيات الأخرى مثل LALR (1) ، والتي اشتهرت بها YACC) يستخدم آلة الدولة والمكدس لبناء شجرة التحليل بكفاءة.
لحسن الحظ ، تتمتع أجهزة الكمبيوتر التي تستخدم CPython بذاكرة أكبر بكثير مما كانت عليه قبل 30 عامًا ، ولم يعد تخزين الملف بالكامل في الذاكرة يمثل مشكلة. على سبيل المثال ، أكبر ملف غير اختبار في stdlib يمكنني العثور عليه هو _pydecimal.py ، والذي يستغرق حوالي 223 كيلو بايت. في عالم الجيجابايت ، هذا ليس شيئًا أساسيًا ، الأمر الذي جعلني ألقي نظرة مختلفة على المحللون.
ولكن هناك شيء آخر في محلل CPython الحالي الذي يزعجني. المجمعون عبارة عن أشياء معقدة ، وتنفيذ CPython ليس استثناءً. على الرغم من أن نتيجة محلل pgen هي شجرة تحليل ، لا يتم استخدامها مباشرة كمدخلات لمولد bytecode: يتم تحويله أولاً إلى شجرة بناء جملة مجردة (AST) ، وعندها فقط يتم تجميع AST في رمز bytecode. (في الواقع ، الأمر أكثر تعقيدًا هناك ، لكن في الوقت الحالي لن ندخل في التفاصيل)
لماذا لا تترجم على الفور من شجرة التحليل؟ هذا هو بالضبط ما كان عليه ، ولكن قبل حوالي 15 عامًا اكتشفنا أن المجمع كان معقدًا للغاية. لذلك نحن عزل AST ومرحلة التحول من AST من شجرة التحليل بشكل منفصل. مع تطور Python ، ظلت AST أكثر استقرارًا من التحليل ، مما قلل من احتمال حدوث أخطاء في المجمع.
AST أسهل أيضًا في العمل مع مكتبات الجهات الخارجية التي ترغب في اختبار رمز Python. يمكن الحصول عليها باستخدام وحدة ast الشعبية. كما يسمح لك بإنشاء العقد من نقطة الصفر وتعديل تلك الموجودة ، وكذلك ترجمة الأجزاء إلى bytecode. هذا الأخير سمح بإنشاء صناعة كاملة من ملحقات اللغة لبيثون. (يمكن أيضًا الوصول إلى شجرة التحليل لمستخدمي Python من خلال وحدة التحليل ، ولكن العمل معها أكثر صعوبة ، وبالتالي فهي ليست شائعة جدًا)
الآن أريد الجمع بين هذه الأشياء ومعرفة ما إذا كان يمكننا إنشاء محلل جديد لـ CPython ، والذي يستخدم PEG و packrat لإنشاء AST مباشرة أثناء التحليل. وبالتالي ، سيكون من الممكن حذف توليد الشجرة الوسيطة للتحليل ، والذي يمكن أن ينقذنا من الذاكرة ، على الرغم من استخدام مخزن مؤقت لانهائي للرموز. ما زلت في طور التنفيذ ، لكن لديّ بالفعل نموذج أولي يمكنه تجميع مجموعة فرعية من بيثون إلى AST بنفس السرعة نفسها التي يستخدمها محلل CPython الحالي. ومع ذلك ، فإنه يستخدم ذاكرة أكبر ، ويبدو لي أن توسيع المجموعة الفرعية إلى اللغة الكاملة سيؤدي إلى إبطاء محلل PEG. لكن حتى الآن لم أفكر في أي تحسينات ، لذلك سأواصل العمل.
الميزة الأخيرة للتحول إلى PEG هي أنها توفر مرونة أكبر للتطور الإضافي للغة. في الماضي ، قيل إن قيود LL (1) في pgen أبقت قواعد لغة Python بسيطة. قد يكون هذا صحيحًا تمامًا ، ولكن لدينا العديد من العمليات الأخرى لمنع نمو اللغة غير المنضبط (بشكل أساسي عملية PEP ، والتي يتم دعمها بمتطلبات التوافق مع الإصدارات الصارمة للغاية وهيكل إدارة جديد). لذلك أنا لست قلقا بشأن ذلك.
أود أن أخبر الكثير عن PEG وتنفيذي ، ولكن سيكون في المنشورات التالية بعد تنظيف الكود.
ترخيص لهذه المقالة ورمز استشهد: CC BY-NC-SA 4.0