مستوحاة فقط من فهم جزئي لبرنامج PEG ، قررت أن أحاول تنفيذه. قد لا تكون النتيجة الأفضل بين موزعي PEG للأغراض العامة - يوجد بالفعل الكثير منهم (على سبيل المثال ، TatSu مكتوب في Python ويقوم بإنشاء كود Python) - لكن هذه طريقة جيدة لفهم PEG. في المستقبل ، أريد استبداله بالتطبيق الحالي للمحلل في CPython.
بيثون PEG محلل سلسلة المحتوى في هذا القسم ، أضع الأسس لفهم عمل المحلل اللغوي ، وذلك باستخدام مثال للتطبيق البسيط المكتوب ذاتيًا لقواعد اللعبة من مقال سابق.
(بالمناسبة ، كتجربة ، لا أضع روابط في النص الخاص بي. إذا كنت لا تفهم شيئًا ما ، فيمكنك فقط google. :-)
عادةً ما يستخدم PEG محلل نزول عودي مع مخزن مؤقت غير محدود للعودة. فيما يلي قواعد لعبة من مقال سابق:
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
سيحدد المحلل اللغوي الفائق التجريد للنسب العودية لهذه اللغة وظيفته لكل قاعدة يتم فيها فهم البدائل. على سبيل المثال ، statement ، سيكون لدينا هذه الوظيفة:
def statement(): if assignment(): return True if expr(): return True if if_statement(): return True return False
بالطبع ، هذا مثال بسيط للغاية: فهو يحذف التفاصيل المهمة ، على سبيل المثال ، ما يتم تغذية مدخلات هذه الوظيفة وما سيكون نتيجة تنفيذها.
لنبدأ بالحجج. يستخدم المحللون الكلاسيكيون رمز مميز منفصل ، يقوم بتقسيم الإدخال (ملف نصي أو سطر) إلى سلسلة من الرموز المميزة ، مثل الكلمات الأساسية ، والمعرفات (الأسماء) ، والأرقام ، والمشغلين. غالبًا ما يجمع محللو PEG (مثل غيرهم من المحللون المعاصرون مثل ANTLR) بين الرمز المميز والتحليل ، لكن بالنسبة لمشروعي ، قررت ترك رمز مميز منفصل.
رمزية Python معقدة للغاية ، لذلك لا أريد تنفيذها على قواعد PEG. على سبيل المثال ، يجب عليك تتبع المسافة البادئة (وهذا يتطلب مكدس داخل الرمز المميز) ؛ تعد معالجة الخطوط الجديدة في بيثون مهمة أيضًا (فهي مهمة ، باستثناء تلك الموجودة في الأقواس المقابلة). أنواع كثيرة من السلاسل تسبب أيضًا بعض التعقيد. باختصار ، ليس لدي أي شكاوى حول الرمز المميز لـ Python ، لذلك أريد أن أتركه كما هو. بالمناسبة ، يحتوي CPython على رمزين: الأول الداخلي ، والذي يستخدمه المحلل اللغوي ، وهو مكتوب بلغة C ، والمكتبة القياسية ، وهي نسخة طبق الأصل مطبقة بيثون النقي. هذا سوف يأتي في متناول يدي في مشروعي.
يحتوي get_token() الكلاسيكي عادةً على واجهة بسيطة تتكون من get_token() واحدة. في كل مرة ، تقوم بإرجاع الرمز التالي في تسلسل الإدخال ، مع تحليل مجموعة من الأحرف. الوحدة النمطية tokenize CPython ليست استثناء: API الأساسي الخاص به هو مولد يصدر رمزًا واحدًا في كل مرة. كل رمز مميز هو كائن من النوع TypeInfo ، الذي يحتوي على عدة حقول ، أهمها هو نوع الرمز المميز (على سبيل المثال ، NAME ، NUMBER ، STRING ) وقيمة السلسلة هي مجموعة الأحرف التي يتكون منها (على سبيل المثال ، abc ، 42 أو "Hello, world" ). هناك أيضا حقول إضافية. على سبيل المثال ، لفهرس الرمز المميز في دفق الإدخال ، وهو أمر مفيد في رسائل الخطأ.
نوع خاص من الرمز المميز هو ENDMARKER ، مما يشير إلى أنه تم الوصول إلى نهاية ملف الإدخال. سوف يسقط المولد إذا تجاهله وحاول الحصول على الرمز التالي.
ولكن كنت مشتتا. كيف ندرك عوائد غير محدودة؟ استرجاع القائمة المميزة يتطلب منك أن تكون قادرًا على تذكر الموضع في الكود المصدري وإعادة التحليل من تلك النقطة. لا تسمح لنا أداة الرمز المميز بنقل مؤشرها ، ولكن يمكنك التقاط دفق الرموز في صفيف وتشغيله من هناك ، وهو ما سنفعله. يمكنك أيضًا تكرار ذلك مع itertools.tee() ، ولكن هذا ربما يكون أقل فعالية في حالتنا ، إذا نظرت إلى التحذيرات في الوثائق.
أفترض أنه يمكنك فقط الرمز المميز لجميع المدخلات إلى القائمة أولاً ، ثم استخدامها كمدخل للمحلل اللغوي. ولكن إذا كان هناك رمز مميز غير صالح في نهاية الملف (على سبيل المثال ، سطر به اقتباس إغلاق مفقود) وكان هناك أيضًا خطأ في بناء الجملة في الملف ، فستتلقى أولاً رسالة خطأ من الرمز المميز. أعتقد أن هذا أمر سيء للمستخدم ، لأن خطأ في بناء الجملة يمكن أن يكون السبب الرئيسي لخط غير صالح. لذلك لدي متطلبات مختلفة قليلاً عن الرمز المميز ، على وجه الخصوص ، يجب تنفيذها كقائمة كسول.
واجهة برمجة تطبيقات API بسيطة للغاية. يقوم كائن Tokenizer بتغليف صفيف من الرموز المميزة والموضع في هذه الصفيف. لديه ثلاث طرق رئيسية:
- إرجاع
get_token() الرمز المميز التالي ، تحريك المؤشر (أو قراءة الرمز المميز التالي من المصدر ، إذا كنا في نهاية المخزن المؤقت الرمز المميز)؛ mark() بإرجاع الموضع الحالي في المخزن المؤقت ؛reset(pos) الموضع في المخزن المؤقت (يجب الحصول على الوسيطة من mark() ).
أضفنا وظيفة المساعد peek_token() ، والتي تُرجع الرمز التالي دون تغيير الموضع في المخزن المؤقت.
هذا ما تبدو عليه قاعدة فئة Tokenizer :
class Tokenizer: def __init__(self, tokengen): """Call with tokenize.generate_tokens(...).""" self.tokengen = tokengen self.tokens = [] self.pos = 0 def mark(self): return self.pos def reset(self, pos): self.pos = pos def get_token(self): token = self.peek_token() self.pos += 1 return token def peek_token(self): if self.pos == len(self.tokens): self.tokens.append(next(self.tokengen)) return self.tokens[self.pos]
هنا ، تم حذف شيء ما للبساطة (على سبيل المثال ، يجب أن تبدأ أسماء الطرق ومتغيرات المثيل بتسطير أسفل السطر) ، ولكن هذا مجرد نموذج أولي Tokenizer برمجة تطبيقات Tokenizer .
يجب أن يصبح المحلل أيضًا صنفًا بحيث statement() ، expr() ، إلخ. يمكن تنفيذها كطرق. سيصبح الرمز get_token() متغير مثيل ، لكنني لا أريد أن تقوم أساليب المحلل اللغوي بالاتصال مباشرة بـ get_token() - بدلاً من ذلك ، نطبق طريقة wait() في فئة Parser ، والتي يمكن أن تنجح أو تفشل تمامًا مثل طريقة المحلل اللغوي. الوسيطة إلى الدالة wait() هي الرمز المميز المتوقع: إما سلسلة (على سبيل المثال ، + ) أو نوع الرمز المميز (على سبيل المثال ، NAME ). نوع القيمة المرجعة ليس مهمًا بعد ، سأعود إليه بعد مناقشة نتيجة عمل المحلل اللغوي.
دع وظائف القواعد النحوية ترجع فقط True أو False . هذا جيد بالنسبة لعلوم الكمبيوتر النظرية (هناك المحلل اللغوي يجيب على السؤال "هل هذه سلسلة صحيحة في اللغة؟") ، ولكن ليس بالنسبة لنا. مهمتنا هي إنشاء AST. لذلك ، دعنا نعيد كتابة هذا الكود حتى تعيد كل طريقة تحليل كائن Node عند النجاح أو None عند الفشل.
يمكن أن تكون فئة Node بسيطة للغاية:
class Node: def __init__(self, type, children): self.type = type self.children = children
هنا ، يحدد النوع نوع العقدة AST (على سبيل المثال ، add أو if ) ، وأحفاد هي قائمة العقد والرموز (مثيلات TokenInfo ). هذا يكفي للمترجم لإنشاء رمز أو إجراء تحليلات أخرى ، مثل فحص النوع أو الفحص الثابت. على الرغم من أنني في المستقبل أود تغيير طريقة عرض AST.
لتتوافق مع هذا المخطط ، يجب أن ترجع طريقة expect() كائن TokenInfo عند النجاح ولا None على الفشل. لتتمكن من التراجع إلى الرموز السابقة ، ألغيت المكالمات إلى أساليب mark() و reset() الخاصة بالرمز المميز (هنا لا يتغير API). إليك ما حدث:
class Parser: def __init__(self, tokenizer): self.tokenizer = tokenizer def mark(self): return self.tokenizer.mark() def reset(self, pos): self.tokenizer.reset(pos) def expect(self, arg): token = self.tokenizer.peek_token() if token.type == arg or token.string == arg: return self.tokenizer.get_token() return None
مرة أخرى: لقد حذفت بعض التفاصيل ، لكن هذا يعمل رمزًا بالفعل.
أحتاج الآن إلى تقديم شرط مهم لطرق المحلل اللغوي. يجب على كل شخص إما إرجاع Node ، ووضع الرمز المميز بعد الرمز المميز الأخير لقاعدة القواعد التي تعرف عليها ؛ إما None وترك موقف رمزية دون تغيير. إذا قرأت طريقة المحلل اللغوي عدة رموز ثم سقطت ، فيجب أن تستعيد موضع الرمز المميز. للقيام بذلك ، يتم وضع mark() وإعادة reset() . لاحظ أن expect() أيضًا إطاعة هذه القاعدة.
لذلك ، إليك رسم للمحلل الفعلي. أنا هنا استخدم عامل تشغيل الفظ من Python 3.8 ( := ):
class ToyParser(Parser): def statement(self): if a := self.assignment(): return a if e := self.expr(): return e if i := self.if_statement(): return i return None def expr(self): if t := self.term(): pos = self.mark() if op := self.expect("+"): if e := self.expr(): return Node("add", [t, e]) self.reset(pos) if op := self.expect("-"): if e := self.expr(): return Node("sub", [t, e]) self.reset(pos) return t return None def term(self):
لقد حذفت تنفيذ بعض الأساليب بحيث أتيحت للقارئ الفرصة لممارسة أنفسهم. هذا أفضل من مجرد قراءة كيفية تنفيذ هذا المحلل اللغوي. في النهاية ، سنقوم بإنشاء هذا الرمز تلقائيًا من القواعد. يتم استيراد الثوابت مثل NAME و NUMBER من وحدة token للمكتبة القياسية. هذا يربطنا أكثر بالتطبيق الحالي لرمز بيثون. إذا كنا نريد إنشاء محلل PEG المعمم ، فيجب علينا إيجاد طرق لتجنب ذلك.
لاحظ أيضًا أنني غش قليلاً. يجب أن تترك طريقة expr متكررة ، لكنني جعلت المحلل اللغوي متكررًا لأن محلل النسب المتكرر لا يعمل مع قواعد النحو النحوية العودية اليسرى. يمكن إصلاح ذلك ، لكنه لا يزال موضوع بعض الأبحاث العلمية ، وأود أن أتحدث عنه بشكل منفصل. فقط ضع في اعتبارك أن هذا التطبيق لا يتوافق بنسبة 100٪ مع قواعدنا المبسطة.
الأشياء الرئيسية التي أريدك أن تفهمها حتى الآن:
- تتوافق قواعد القواعد النحوية مع أساليب المحلل اللغوي ، وعندما تشير قاعدة القواعد النحوية إلى قاعدة أخرى ، فسوف تستدعي طريقة قاعدة أخرى.
- عندما يمكن تفسير سلسلة من الرموز بطريقة مختلفة ، يتم استدعاء أساليب المحلل اللغوي المقابلة واحدة تلو الأخرى.
- عندما تشير قاعدة القواعد إلى رمز مميز ، فإن الطريقة تستدعي الدالة
expect() . - إذا تعترف المحلل اللغوي بنجاح بقواعد النحو في الموضع الحالي ، فسوف يُرجع العقدة AST المقابلة ؛ إذا لم يستطع التعرف على قواعده النحوية ، فإنه لن يعود.
- يجب على أساليب المحلل اللغوي إعادة تعيين موضع الرمز المميز بشكل صريح عند إيقاف التحليل بعد استخدام واحد أو أكثر من الرموز المميزة (بشكل مباشر أو غير مباشر ، استدعاء طريقة تحليل ناجحة أخرى). ينطبق هذا ليس فقط عند رفض أحد الخيارات من أجل المتابعة إلى التالي ، ولكن أيضًا عند رفض التحليل ككل.
إذا كانت جميع أساليب التحليل تطيع هذه القواعد ، فلا داعٍ للالتفاف على كل من المكالمات mark() وإعادة reset() . يمكن إثبات ذلك عن طريق الحث.
بالإضافة إلى ذلك ، من المغري محاولة التخلص من المكالمات الصريحة لوضع mark() وإعادة reset() باستخدام مدير السياق والعبارة " with ، لكنها لن تنجح: يجب عليك عدم استدعاء reset() إذا نجحت! كإصلاح إضافي ، يمكنك محاولة استخدام استثناءات لتدفق التحكم بحيث يعرف مدير السياق ما إذا كان يجب إعادة تعيين الرمز المميز (أعتقد أن TatSu يقوم بعمل مشابه). على سبيل المثال ، شيء مثل هذا:
def statement(self): with self.alt(): return self.assignment() with self.alt(): return self.expr() with self.alt(): return self.if_statement() raise ParsingFailure
على وجه الخصوص ، يمكن كتابة سلم صغير if في atom() للاعتراف بتعبير بين قوسين كما يلي:
with self.alt(): self.expect("(") e = self.expr() self.expect(")") return e
ولكن يبدو لي أيضًا "سحريًا" - عند قراءة هذا الرمز ، يجب أن تتذكر أن كل طريقة للتحليل (بما في ذلك wait() ) يمكن أن تضع استثناءً. وأن هذا الاستثناء يتم اكتشافه وتجاهله بواسطة مدير السياق في العبارة with . هذا غير عادي إلى حد ما ، على الرغم من إمكانية تحقيقه (عن طريق إرجاع True من __exit__ ). ومع ذلك ، فإن هدفي النهائي هو إنشاء رمز في C ، وليس Python ، وفي C لا يوجد عبارة with عبارة لتغيير تدفق التحكم.
على أي حال ، إليك بعض المواضيع للأجزاء التالية:
- توليد طرق المحلل اللغوي من قواعد اللغة ؛
- packrat تحليل (المذكرة) ؛
- ميزات EBNF مثل
(x | y) ، [xy ...] ، x* ، x+ ؛ - تتبع (لتصحيح الأخطاء أو محلل نحوي) ؛
- ميزات PEG مثل lookahead وقطع.
- كيفية التعامل مع قواعد العودية اليسرى.
- جيم رمز الجيل
ترخيص لهذه المقالة ورمز استشهد: CC BY-NC-SA 4.0