ما هو محلل الشجرة في ANTLR وهل أنا مجبر على كتابته؟

https://stackoverflow.com/questions/697755

22-08-2019
|

سؤال

أنا أكتب معجمًا/محللًا لمجموعة فرعية صغيرة من لغة C في ANTLR والتي سيتم تشغيلها في بيئة Java.أنا جديد في عالم قواعد اللغة وفي العديد من دروس ANTLR، يقومون بإنشاء AST - شجرة تركيب مجردة، هل أنا مجبر على إنشاء واحدة ولماذا؟

المحلول 2

وجدت هذه الإجابة على السؤال الموجود على jGuru الذي كتبه Terence Parr، الذي أنشأ ANTLR.لقد نسخت هذا الشرح من الموقع المرتبط هنا:

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

تخيل مشكلة ترجمة بسيطة حيث تريد طباعة صفحة html عنوانها "يوجد n عناصر" حيث n هو عدد المعرفات التي وجدتها في دفق الإدخال.يجب طباعة المعرفات بعد العنوان مثل هذا:

<html>
<head>
<title>There are 3 items</title>
</head>
<body>
<ol>
<li>Dog</li>
<li>Cat</li>
<li>Velociraptor</li>
</body>
</html>

من الإدخال

Dog
Cat
Velociraptor

لذا، باستخدام الإجراءات البسيطة في قواعدك، كيف يمكنك حساب العنوان؟لا يمكنك ذلك دون قراءة المدخلات بأكملها.حسنًا، نعلم الآن أننا بحاجة إلى نموذج وسيط.الأفضل عادة هو AST الذي وجدته لأنه يسجل بنية الإدخال.في هذه الحالة، إنها مجرد قائمة ولكنها توضح وجهة نظري.

حسنًا، أنت تعلم الآن أن الشجرة مفيدة لأي شيء باستثناء الترجمات البسيطة.بالنظر إلى AST، كيف تحصل على الناتج منه؟تخيل أشجار التعبير البسيطة.إحدى الطرق هي إنشاء فئات محددة للعقد في الشجرة مثل PlusNode وIntegerNode وما إلى ذلك.ثم تطلب فقط من كل عقدة أن تطبع نفسها.للمدخلات، 3+4 سيكون لديك شجرة:

+ | 3 -- 4

والطبقات

class PlusNode extends CommonAST {
  public String toString() {
    AST left = getFirstChild();
    AST right = left.getNextSibling();
    return left + " + " + right;
  }
}

class IntNode extends CommonAST {
  public String toString() {
    return getText();
  }
}

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

expr returns [String r]
{
    String left=null, right=null;
}

: #("+" left=expr right=expr) {r=left + " + " + right;}
| i:INT                       {r=i.getText();}
;

لاحظ أن أسلوب الفئة المحددة ("AST غير المتجانسة") يقوم فعليًا بتشفير محلل أصل عودي كامل لـ #(+ INT INT) يدويًا في toString().باعتبارك أحد مولدات المحلل اللغوي، فإن هذا من شأنه أن يجعلك تشعر بالإحباط.;)

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

باختصار، تعمل إضافة الإجراءات إلى محلل الإدخال الخاص بك على الحصول على ترجمات واضحة جدًا حيث:

ترتيب بنيات الإخراج هو نفس ترتيب الإدخال
يمكن إنشاء جميع التركيبات من المعلومات التي تم تحليلها إلى النقطة التي تحتاج فيها إلى بصقها

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

نصائح أخرى

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

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

وهناك الكثير لANTLR. إذا كنت لم تقم بذلك بالفعل، وأود أن أوصي الحصول الكتاب .

أعتقد أن إنشاء أست هو اختياري.ال شجرة بناء الجملة مجردة مفيد للمعالجة اللاحقة مثل التحليل الدلالي للبرنامج الذي تم تحليله.

أنت وحدك من يستطيع أن يقرر ما إذا كنت بحاجة إلى إنشاء واحدة.إذا كان هدفك الوحيد هو التحقق من صحة النحو، فلن تحتاج إلى إنشاء واحد.في javacc (على غرار ANTLR) هناك جدوى مُسَمًّى JJTree الذي يسمح بتوليد AST.لذلك أتصور أن هذا اختياري في ANTLR أيضًا.

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow