شجرة بناء الجملة المجردة

يحتوي نموذج شجرة بناء الجملة المجردة (AST) على العديد من الخصائص التي تساعد في الخطوات الإضافية لعملية التجميع:

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

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

غالباً ما يرتبط تصميم شجرة بناء الجملة المجردة (AST) ارتباطاً وثيقاً بتصميم المترجم وخصائصه المتوقعة.

تشمل المتطلبات الأساسية ما يلي:

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

يمكن استخدام هذه المتطلبات لتصميم بنية البيانات الخاصة بشجرة بناء الجملة المجردة (AST).

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

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

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

تُعرف عملية مقارنة شجرة بناء الجملة المجردة (AST)، أو اختصارًا "مقارنة الشجرة"، بحساب قائمة الاختلافات بين شجرتي بناء جملة مجردتين. ^{[ 1 ] [ 2 ]} تُسمى هذه القائمة عادةً "نص التحرير". يشير نص التحرير مباشرةً إلى شجرة بناء الجملة المجردة للبرنامج. على سبيل المثال، قد ينتج عن عملية التحرير إضافة عقدة جديدة في شجرة بناء الجملة المجردة تُمثل دالة.

يُعدّ AST تجريدًا قويًا لإجراء عملية الكشف عن نسخ التعليمات البرمجية . ^{[ 3 ]}

يترك${\displaystyle S}$أن تكون مجموعة من نوع ما ، فإن عدد العناصر هو زوج مرتب${\displaystyle (s_{1},\dots ,s_{n},s)}$، ل${\displaystyle s_{1},\dots ,s_{n},s\in S}$، وتكتب أيضًا على${\displaystyle (s_{1},\dots ,s_{n})s}$وبشكل أدق،${\displaystyle \mathrm {Arity} (S):=\coprod _{n\in \mathbb {N} }S^{n+1}}$.

يترك${\displaystyle {\mathcal {O}}=\{{\mathcal {O_{\alpha }}}\}_{\alpha \in \mathrm {Arity} (S)}}$كن${\displaystyle \mathrm {Arity} (S)}$عائلة مفهرسة من مجموعات منفصلة من المؤثرات . إذا${\displaystyle o}$عدد المعاملات${\displaystyle (s_{1},\dots ,s_{n})s}$نقول ذلك${\displaystyle o}$نوع${\displaystyle s}$وله${\displaystyle n}$نوع من أنواع الجدال${\displaystyle s_{1},\dots ,s_{n}}$.

يصلح${\displaystyle S}$أن تكون مجموعة منتهية من نوع ما، و${\displaystyle {\mathcal {O}}}$أن${\displaystyle \mathrm {Arity} (S)}$عائلة مفهرسة من مجموعات منفصلة من المؤثرات . ليكن${\displaystyle {\mathcal {X}}=\{{\mathcal {X}}_{s}\}_{s\in S}}$كن${\displaystyle S}$عائلة من المتغيرات المنفصلة المفهرسة.${\displaystyle {\mathcal {A}}[{\mathcal {X}}]=\{{\mathcal {A}}[{\mathcal {X}}]_{s}\}_{s\in S}}$أصغر أنواع أشجار بناء الجملة المجردة ، أو AST s${\displaystyle S}$عائلة من المجموعات المنفصلة المفهرسة والمغلقة في ظل الشروط التالية:

1. المتغيرات هي عبارة عن هياكل شجرة بناء الجملة المجردة (ASTs): إذا${\displaystyle x\in {\mathcal {X}}_{s}}$، ثم${\displaystyle x\in {\mathcal {A}}[{\mathcal {X}}]_{s}}$.
2. يقوم المشغلون بدمج أنظمة AST: إذا${\displaystyle o}$هو عامل من نوع${\displaystyle (s_{1},\dots ,s_{n})s}$، و${\displaystyle a_{i}\in {\mathcal {A}}[{\mathcal {X}}]_{s_{i}}}$للجميع${\displaystyle 1\leq i\leq n}$، ثم${\displaystyle o(a_{1};\dots ;a_{n})\in {\mathcal {A}}[{\mathcal {X}}]_{s}}$.