مسند نحوي

يُحدد المسند النحوي صحة تطبيق قاعدة إنتاج في قواعد نحوية رسمية ، وهو مماثل للمسند الدلالي الذي يُحدد صحة تطبيق قاعدة إنتاج دلالية. يُعدّ المسند النحوي وسيلة بسيطة وفعّالة لتحسين قدرة محلل LL على التعرّف بشكل كبير من خلال توفير إمكانية التنبؤ المسبق. في تطبيقها الأصلي، كانت المسندات النحوية تأخذ الشكل "(α)؟"، ولا يمكن أن تظهر إلا على الحافة اليسرى لقاعدة الإنتاج. يمكن أن يكون الشرط النحوي المطلوب α أي جزء صحيح من قواعد نحوية خالية من السياق .

بصورة أدق، يُعدّ المسند النحوي شكلاً من أشكال تقاطع قواعد _{الإنتاج} ، ويُستخدم في مواصفات المحلل اللغوي أو في القواعد النحوية الرسمية _. وبهذا المعنى، يحمل مصطلح "المسند" دلالة دالة مؤشر رياضية . فإذا كانت p1 و p2 قاعدتي إنتاج، فإن _اللغة الناتجة عن كلتيهما هي تقاطع مجموعتيهما _.

بحسب التعريف أو التطبيق المعتاد، تُرتّب المسندات النحوية ضمنيًا قواعد الإنتاج بحيث تكون لقواعد الإنتاج المحددة سابقًا أسبقية أعلى من قواعد الإنتاج المحددة لاحقًا ضمن القرار نفسه. وهذا يُتيح إمكانية إزالة الغموض عن قواعد الإنتاج المُبهمة، إذ يُمكن للمبرمج ببساطة تحديد قاعدة الإنتاج التي يجب أن تُطابق.

تُوسّع قواعد التعبير التحليلية (PEGs)، التي ابتكرها برايان فورد، هذه المسندات البسيطة من خلال السماح باستخدام "مسندات النفي" وإمكانية ظهور المسند في أي مكان ضمن قاعدة الإنتاج. علاوة على ذلك، ابتكر فورد تحليل "باكرات" لمعالجة هذه القواعد في وقت خطي باستخدام التخزين المؤقت ، على حساب مساحة الذاكرة الديناميكية.

من الممكن دعم تحليل المسندات في زمن خطي، حتى تلك العامة التي تسمح بها قواعد PEG، مع تقليل تكلفة الذاكرة المرتبطة بالتخزين المؤقت عن طريق تجنب التراجع حيثما يكفي تطبيق أكثر كفاءة للتنبؤ المسبق. يُطبَّق هذا النهج في الإصدار 3 من ANTLR ، الذي يستخدم آلات الحالة المحدودة الحتمية للتنبؤ المسبق؛ وقد يتطلب ذلك اختبار المسند لاختيار أحد انتقالات آلة الحالة المحدودة الحتمية (يُسمى تحليل "pred-LL(*)"). ^{[ 1 ]}

ملخص

مصطلحات

صاغ بار وكوونغ مصطلح المسند النحوي، وهو يميز هذا النوع من المسند عن المسند الدلالي ( الذي تمت مناقشته أيضاً). ^{[ 2 ]}

تُعرف المسندات النحوية في العديد من المراجع بمصطلحات مختلفة، منها المطابقة متعددة الخطوات ، وقيود التحليل ، والمسندات ببساطة . (انظر قسم المراجع أدناه). يستخدم هذا المقال مصطلح "المسند النحوي" بشكل كامل لضمان الاتساق ولتمييزه عن المسندات الدلالية .

خصائص الإغلاق الرسمي

أظهر بار-هيلل وآخرون ^{[ 3 ]} أن تقاطع لغتين منتظمتين هو أيضًا لغة منتظمة، وهذا يعني أن اللغات المنتظمة مغلقة تحت التقاطع .

إن تقاطع لغة منتظمة ولغة خالية من السياق مغلق أيضًا، ومن المعروف منذ هارتمانيس ^{[ 4 ]} على الأقل أن تقاطع لغتين خاليتين من السياق لا يعني بالضرورة أنهما لغة خالية من السياق (وبالتالي ليس مغلقًا). ويمكن إثبات ذلك بسهولة باستخدام لغة النوع 1 المتعارف عليها . $L=\{a^{n}b^{n}c^{n}:n\geq 1\}$ :

يترك $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$ (النوع 2) يترك $L_{2}=\{a^{n}b^{n}c^{m}:m,n\geq 1\}$ (النوع 2) يترك $L_{3}=L_{1}\cap L_{2}$

بالنظر إلى السلاسل abcc و aabbc و aaabbbccc ، من الواضح أن السلسلة الوحيدة التي تنتمي إلى كل من L ₁و L ₂ (أي السلسلة الوحيدة التي تنتج تقاطعًا غير فارغ ) هي aaabbbccc .

اعتبارات أخرى

في معظم الصيغ الرسمية التي تستخدم المسندات النحوية، يكون بناء جملة المسند غير تبادلي ، أي أن عملية الإسناد مرتبة. على سبيل المثال، باستخدام المثال السابق، لننظر إلى القواعد النحوية الزائفة التالية، حيث يُفهم من X ::= Y PRED Z ما يلي: " ينتج Y قيمة X إذا وفقط إذا كانت Y تحقق المسند Z أيضًا ".

S ::= a X X ::= Y PRED Z Y ::= a+ BNCN Z ::= ANBN c+ BNCN ::= b [BNCN] c ANBN ::= a [ANBN] b

بالنظر إلى السلسلة aaaabbbccc ، في حالة وجوب تحقق الشرط Y أولًا (وبافتراض تطبيق جشع)، ستُنتج S السلسلة aX ، والتي بدورها ستُنتج aaabbbccc ، وبالتالي تُنتج aaaabbbccc . أما في حالة وجوب تحقق الشرط Z أولًا ، فلن يتمكن ANBN من إنتاج aaaabbb ، وبالتالي لن تُنتج القواعد النحوية aaaabbbccc . علاوة على ذلك، إذا حدد أي من Y أو Z (أو كلاهما) إجراءً يُتخذ عند الاختزال (كما هو الحال في العديد من المحللات النحوية)، فإن ترتيب تطابق هذه القواعد يُحدد ترتيب حدوث تلك الآثار الجانبية. وقد تعتمد الصيغ التي تتغير بمرور الوقت (مثل القواعد النحوية التكيفية ) على هذه الآثار الجانبية .

أمثلة على الاستخدام

ANTLR

يقدم بار وكوونغ ^{[ 5 ]} هذا المثال على مسند نحوي:

stat : ( declaration ) ? declaration | expression ;

والذي يهدف إلى تلبية القيود التالية غير الرسمية ^{[ 6 ]} للغة C++ :

إذا بدا الأمر وكأنه إعلان، فهو كذلك؛ وإلا
إذا بدت كأنها تعبير، فهي كذلك؛ وإلا
هذا خطأ في بناء الجملة.

في أول عملية إنتاج لقاعدة stat، يشير المسند النحوي (declaration)؟ إلى أن التصريح هو السياق النحوي الذي يجب أن يكون موجودًا لنجاح بقية عملية الإنتاج. يمكننا تفسير استخدام (declaration)؟ على أنه "لست متأكدًا مما إذا كان التصريح سيتطابق؛ دعني أجربه، وإذا لم يتطابق، فسأجرب البديل التالي". وبالتالي، عند مصادفة تصريح صحيح، سيتم التعرف على تصريح القاعدة مرتين - مرة كمسند نحوي ومرة أخرى أثناء التحليل الفعلي لتنفيذ الإجراءات الدلالية.

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

أمثلة قانونية

اللغة $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ يمكن تمثيلها في قواعد نحوية وصيغ شكلية مختلفة على النحو التالي:

تحليل قواعد التعبير

S ← & ( A ! b ) a + B ! c A ← a A ? b B ← b B ? c

حساب التفاضل والتكامل

استخدام المسند المقيد :

S → {A} ^B

أ → س 'ج+' X → 'a' [X] 'b' ب → 'أ+' ص Y → 'b' [Y] 'c'

باستخدام مسندين حرين :

أ → <'a+'> _أ <'ب+'> _ب Ψ( أ ب ) ^X <'ج+'> _ج Ψ( ب ج ) ^ص

X → 'a' [X] 'b' Y → 'b' [Y] 'c'

قواعد الربط

(ملاحظة: المثال التالي يُولّد فعليًا $L=\{a^{n}b^{n}c^{n}|n\geq 0\}$ ، ولكنها مدرجة هنا لأنها المثال الذي قدمه مخترع قواعد الربط. ^{[ 7 ]} ):

S → AB&DC A → aA | ε B → bBc | ε C → cC | ε D → aDb | ε

قواعد راكو

القاعدة S { <قبل <A> <!قبل b>> a+ <B> <!قبل c> } القاعدة A { a <A>? b } القاعدة B { b <B>? c }

المحللات/الصيغ التي تستخدم شكلاً من أشكال المسند النحوي

على الرغم من أنها ليست قائمة شاملة بأي حال من الأحوال، فإن المحللات النحوية والصيغ النحوية التالية تستخدم المسندات النحوية :

ANTLR (بار وكوونغ): كما طُبِّقَت في الأصل، ^{[ 2 ]} تقع المسندات النحوية على الحافة اليسرى لقاعدة الإنتاج، بحيث تُجرَى محاولة بناء قاعدة الإنتاج على يمين المسند إذا وفقط إذا قبل المسند النحوي الجزء التالي من سلسلة الإدخال. على الرغم من الترتيب، تُفحص المسندات أولًا، ويستمر تحليل الجملة إذا وفقط إذا تحقق المسند، وتحدث الإجراءات الدلالية فقط في غير المسندات. ^{[ 5 ]}
برنامج مطابقة الأنماط المعزز (بالماس): تشير بالماس إلى المسندات النحوية باسم "المطابقة متعددة الخطوات" في ورقتها البحثية حول تحليل APM. ^{[ 8 ]} أثناء قيام محلل APM بالتحليل، يمكنه ربط السلاسل الفرعية بمتغير، ثم التحقق من هذا المتغير مقابل قواعد أخرى، ويستمر في التحليل إذا وفقط إذا كانت تلك السلسلة الفرعية مقبولة لقواعد أخرى.
قواعد تحليل التعبيرات (فورد): تحتوي قواعد فورد النحوية على مسندات نحوية معبر عنها كمسند " و " ومسند "ليس" . ^{[ 9 ]}
حساب التفاضل والتكامل (جاكسون): في حساب التفاضل والتكامل §، تُسمى المسندات النحوية في الأصل ببساطة بالمسندات ، ولكنها تُقسم لاحقًا إلى أشكال مقيدة وأشكال حرة ، ولكل منها خصائص إدخال مختلفة. ^{[ 10 ]}
قواعد راكو: يُقدّم راكو أداةً عامةً لوصف القواعد النحوية تُسمى القواعد ، وهي امتدادٌ لصيغة التعبيرات النمطية في بيرل 5. ^[¹¹^] تُعرَض المسندات عبر آلية استباقية تُسمى قبل ، إما باستخدام " " أو " " (أي: " ليس قبل"". يحتوي بيرل 5 أيضًا على آلية استباقية مماثلة، لكنها لا تستطيع سوى تغليف ميزات التعبيرات النمطية المحدودة في بيرل 5.<before ...><!before ...>
قواعد اللغة (تقنيات نوركين): تستخدم لغة تعريف القواعد (GDL) الخاصة ببرنامج ProGrammar المسندات النحوية في شكل يُسمى قيود التحليل . ^{[ 12 ]} تنبيه: هذا الرابط لم يعد صالحًا!
قواعد الاقتران والقواعد البولية (أوخوتين): تُقدّم قواعد الاقتران، التي قدّمها أوخوتين لأول مرة ^{[ 13 ]} ، المفهوم الصريح للاقتران كإسناد . ويُعدّ تناول قواعد الاقتران والقواعد المنطقية ^{[ 14 ]} لاحقًا أكثر الدراسات شمولًا لهذا الشكل حتى الآن.

مراجع

↑ بار، تيرينس (2007). المرجع الشامل للغة ANTLR: بناء لغات خاصة بالمجال . المبرمجون العمليون . ص 328. ISBN 978-3-540-63293-1.
1 2 بار، تيرينس جيه ؛ كوونغ، راسل (أكتوبر 1993). "إضافة مسندات دلالية ونحوية إلى LL(k): Pred-LL(k)" . إضافة مسندات دلالية ونحوية إلى تحليل LL(k): pred-LL(k) . سلسلة محاضرات في علوم الحاسوب. المجلد 786. منشور مسبق رقم 93-096، مركز أبحاث الحوسبة عالية الأداء التابع للجيش. الصفحات 263-277 . CiteSeerX 10.1.1.26.427 . doi : 10.1007/3-540-57877-3_18 . ISBN 978-3-540-57877-2تم الاطلاع عليه بتاريخ 26 أغسطس 2023 .
↑ بار هليل، ي .؛ بيرلز، م. شامير، إي. (1961). “حول الخصائص الرسمية لقواعد بنية العبارة البسيطة”. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung . 14 (2): 143- 172..
↑ هارتمانيس، جوريس (1967). "اللغات الخالية من السياق وحسابات آلة تورينج" . الجوانب الرياضية لعلوم الحاسوب . وقائع ندوات في الرياضيات التطبيقية. المجلد 19. الجمعية الأمريكية للرياضيات. الصفحات 42-51 . doi : 10.1090/psapm/019/0235938 . ISBN 9780821867280.
1 2 بار، تيرينس؛ كوونغ، راسل (يوليو 1995). "ANTLR: مولد محلل LL(k) المسند" (ملف PDF) . البرمجيات: الممارسة والخبرة . 25 (7): 789-810 . doi : 10.1002/spe.4380250705 . S2CID 13453016 .
↑ ستروستروب، بيارن؛ إليس، مارغريت أ. (1990). دليل مرجعي مشروح للغة سي++ . أديسون-ويسلي. ISBN 9780201514599.
↑ أوخوتين، ألكسندر (2001). "القواعد النحوية الاقترانية" (ملف PDF) . مجلة الأوتوماتا واللغات والتوافقية . 6 (4): 519-535 . doi : 10.25596/jalc-2001-519 . S2CID 18009960. مؤرشف من الأصل (ملف PDF) في 26 يونيو 2019.
↑ بالماس، فرانسواز (20-23 سبتمبر 1994). "مُطابقة الأنماط المُعززة كأداة لتوليف الأوصاف المفاهيمية للبرامج". وقائع مؤتمر هندسة البرمجيات القائمة على المعرفة التاسع KBSE '94. وقائع المؤتمر التاسع لهندسة البرمجيات القائمة على المعرفة. مونتيري، كاليفورنيا. ص 150-157 . doi : 10.1109/KBSE.1994.342667 . ISBN 0-8186-6380-4.
↑ فورد، برايان (سبتمبر 2002). تحليل Packrat: خوارزمية عملية خطية الوقت مع التراجع (رسالة ماجستير). معهد ماساتشوستس للتكنولوجيا.
↑ جاكسون، كوين تايلر (مارس 2006). التكيف مع بابل: التكيف والحساسية للسياق في التحليل النحوي . بليموث، ماساتشوستس: دار نشر إيبيس. CiteSeerX 10.1.1.403.8977 .
↑ وول، لاري (2002-2006). "ملخص 5: التعبيرات النمطية والقواعد" .
↑ "لغة تعريف القواعد النحوية" . شركة نوركين للتكنولوجيا.
↑ أوخوتين، ألكسندر (2000). "حول تعزيز الشكلية لقواعد اللغة الخالية من السياق بعملية التقاطع". وقائع المؤتمر الدولي الرابع "النماذج المنفصلة في نظرية أنظمة التحكم" (باللغة الروسية): 106-109 .
↑ أوخوتين، ألكسندر (أغسطس 2004). قواعد اللغة البولية: القدرة التعبيرية والخوارزميات (أطروحة دكتوراه). كينغستون، أونتاريو: كلية الحوسبة، جامعة كوينز.

روابط خارجية

[1] بار، تيرينس (2007). المرجع الشامل للغة ANTLR: بناء لغات خاصة بالمجال . المبرمجون العمليون . ص 328. ISBN 978-3-540-63293-1.

[Parr&Quong1993-2] 1 2 بار، تيرينس جيه ؛ كوونغ، راسل (أكتوبر 1993). "إضافة مسندات دلالية ونحوية إلى LL(k): Pred-LL(k)" . إضافة مسندات دلالية ونحوية إلى تحليل LL(k): pred-LL(k) . سلسلة محاضرات في علوم الحاسوب. المجلد 786. منشور مسبق رقم 93-096، مركز أبحاث الحوسبة عالية الأداء التابع للجيش. الصفحات 263-277 . CiteSeerX 10.1.1.26.427 . doi : 10.1007/3-540-57877-3_18 . ISBN 978-3-540-57877-2تم الاطلاع عليه بتاريخ 26 أغسطس 2023 .

[3] بار هليل، ي .؛ بيرلز، م. شامير، إي. (1961). “حول الخصائص الرسمية لقواعد بنية العبارة البسيطة”. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung . 14 (2): 143- 172..

[4] هارتمانيس، جوريس (1967). "اللغات الخالية من السياق وحسابات آلة تورينج" . الجوانب الرياضية لعلوم الحاسوب . وقائع ندوات في الرياضيات التطبيقية. المجلد 19. الجمعية الأمريكية للرياضيات. الصفحات 42-51 . doi : 10.1090/psapm/019/0235938 . ISBN 9780821867280.

[Parr&Quong1995-5] 1 2 بار، تيرينس؛ كوونغ، راسل (يوليو 1995). "ANTLR: مولد محلل LL(k) المسند" (ملف PDF) . البرمجيات: الممارسة والخبرة . 25 (7): 789-810 . doi : 10.1002/spe.4380250705 . S2CID 13453016 .

[Stroustrup&Ellis1990-6] ستروستروب، بيارن؛ إليس، مارغريت أ. (1990). دليل مرجعي مشروح للغة سي++ . أديسون-ويسلي. ISBN 9780201514599.

[Okhotin2001-7] أوخوتين، ألكسندر (2001). "القواعد النحوية الاقترانية" (ملف PDF) . مجلة الأوتوماتا واللغات والتوافقية . 6 (4): 519-535 . doi : 10.25596/jalc-2001-519 . S2CID 18009960. مؤرشف من الأصل (ملف PDF) في 26 يونيو 2019.

[Balmas1994-8] بالماس، فرانسواز (20-23 سبتمبر 1994). "مُطابقة الأنماط المُعززة كأداة لتوليف الأوصاف المفاهيمية للبرامج". وقائع مؤتمر هندسة البرمجيات القائمة على المعرفة التاسع KBSE '94. وقائع المؤتمر التاسع لهندسة البرمجيات القائمة على المعرفة. مونتيري، كاليفورنيا. ص 150-157 . doi : 10.1109/KBSE.1994.342667 . ISBN 0-8186-6380-4.

[Ford2002-9] فورد، برايان (سبتمبر 2002). تحليل Packrat: خوارزمية عملية خطية الوقت مع التراجع (رسالة ماجستير). معهد ماساتشوستس للتكنولوجيا.

[Jackson2006-10] جاكسون، كوين تايلر (مارس 2006). التكيف مع بابل: التكيف والحساسية للسياق في التحليل النحوي . بليموث، ماساتشوستس: دار نشر إيبيس. CiteSeerX 10.1.1.403.8977 .

[Wall2002-11] وول، لاري (2002-2006). "ملخص 5: التعبيرات النمطية والقواعد" .

[NorKen-12] "لغة تعريف القواعد النحوية" . شركة نوركين للتكنولوجيا.

[Okhotin2000-13] أوخوتين، ألكسندر (2000). "حول تعزيز الشكلية لقواعد اللغة الخالية من السياق بعملية التقاطع". وقائع المؤتمر الدولي الرابع "النماذج المنفصلة في نظرية أنظمة التحكم" (باللغة الروسية): 106-109 .

[Okhotin2004-14] أوخوتين، ألكسندر (أغسطس 2004). قواعد اللغة البولية: القدرة التعبيرية والخوارزميات (أطروحة دكتوراه). كينغستون، أونتاريو: كلية الحوسبة، جامعة كوينز.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[

[ 12 ]

[ 13 ]

[ 14 ]