قواعد الإسناد

قواعد السمات هي طريقة رسمية لتكملة القواعد الرسمية بمعالجة المعلومات الدلالية. تُخزَّن المعلومات الدلالية في سمات مرتبطة بالرموز الطرفية وغير الطرفية للقواعد. وتُستمد قيم السمات من قواعد تقييم السمات المرتبطة بقواعد الإنتاج في القواعد. تسمح السمات بنقل المعلومات من أي مكان في شجرة بناء الجملة المجردة إلى أي مكان آخر، بطريقة مُتحكَّم بها ورسمية. ^{[ 1 ]}

تتعامل كل دالة دلالية مع سمات الرموز التي تظهر في قاعدة إنتاج واحدة فقط: فكل من معلمات الدالة الدلالية ونتيجتها تمثل سمات رموز من قاعدة معينة. عندما تُعرّف دالة دلالية قيمة سمة رمز على الجانب الأيسر من القاعدة، تُسمى هذه السمة "مُركّبة" ؛ وإلا تُسمى " موروثة" . ^{[ 2 ]} بالتالي، تُستخدم السمات المُركّبة لنقل المعلومات الدلالية إلى أعلى شجرة التحليل، بينما تسمح السمات الموروثة بنقل القيم من العقد الأصلية إلى أسفل شجرة بناء الجملة وعبرها.

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

ابتكر دونالد كنوث وبيتر فيجنر قواعد السمات . ^{[ 3 ]} وبينما يُنسب الفضل في المفهوم العام إلى دونالد كنوث، فقد ابتكر بيتر فيجنر السمات الموروثة خلال محادثة مع كنوث. وتعود بعض الأفكار الأولية ^{[ 3 ]} إلى عمل إدغار تي. "نيد" آيرونز، ^{[ 4 ]} مؤلف كتاب IMP .

فيما يلي قواعد نحوية بسيطة خالية من السياق يمكنها وصف لغة تتكون من ضرب وجمع الأعداد الصحيحة.

تعبير ← تعبير + حد تعبير ← حد حد ← حد * عامل حد ← عامل عامل ← " (" تعبير ")" عامل ← عدد صحيح

يمكن استخدام قواعد السمات التالية لحساب نتيجة تعبير مكتوب بهذه القواعد. لاحظ أن هذه القواعد تستخدم قيمًا مُصنّعة فقط، ولذلك فهي قواعد سمات من النوع S.

التعبير 1 ← التعبير 2 + الحد [ قيمة التعبير 1 = قيمة التعبير 2 + قيمة الحد ] التعبير ← الحد [ قيمة التعبير = قيمة الحد ] الحد 1 ← الحد 2 * العامل [ قيمة الحد 1 = قيمة الحد 2 * قيمة العامل ] الحد ← العامل [ قيمة الحد = قيمة العامل ] العامل ← "(" التعبير ")" [ قيمة العامل = قيمة التعبير ] العامل ← عدد صحيح [ قيمة العامل = strToInt( العدد الصحيح .str)]

تُحسب السمة المُركّبة من قيم سمات العناصر الفرعية. وبما أنه يجب حساب قيم العناصر الفرعية أولاً، فهذا مثال على الانتشار التصاعدي. ^{[ 5 ]} لتعريف السمة المُركّبة تعريفًا رسميًا، لنفترض${\displaystyle G=\langle V_{n},V_{t},P,S\rangle }$أن تكون قواعد نحوية رسمية، حيث

• ${\displaystyle V_{n}}$هي مجموعة الرموز غير الطرفية
• ${\displaystyle V_{t}}$هي مجموعة الرموز الطرفية
• ${\displaystyle P}$هي مجموعة الإنتاجات
• ${\displaystyle S}$هو الرمز المميز، أو رمز البداية

ثم، بالنظر إلى سلسلة من الرموز غير الطرفية${\displaystyle A}$واسم السمة${\displaystyle a}$،${\displaystyle Aa}$تُعتبر سمة مركبة إذا تحققت الشروط الثلاثة التالية:

• ${\displaystyle (A\rightarrow \alpha )\in P}$(أي${\displaystyle A\rightarrow \alpha }$(وهي إحدى قواعد النحو)
• ${\displaystyle \alpha =\alpha _{1}\ldots \alpha _{n},\forall i,1\leq i\leq n:\alpha _{i}\in (V_{n}\cup V_{t})}$(أي أن كل رمز في متن القاعدة إما غير طرفي أو طرفي)
• ${\displaystyle Aa=f(\alpha _{j_{1}}.a_{1},\ldots ,\alpha _{j_{m}}.a_{m})}$، أين${\displaystyle \{\alpha _{j_{1}},\ldots ,\alpha _{j_{m}}\}\subseteq \{\alpha _{1},\ldots ,\alpha _{n}\}}$(أي أن قيمة السمة هي دالة)${\displaystyle f}$(مطبق على بعض القيم من الرموز الموجودة في متن القاعدة)

تُعرَّف السمة الموروثة في عقدةٍ ما في شجرة التحليل باستخدام قيم السمات في العقدة الأب أو العقد الشقيقة. تُعدّ السمات الموروثة ملائمةً للتعبير عن اعتماد بنية لغة البرمجة على السياق الذي تظهر فيه. على سبيل المثال، يُمكننا استخدام سمة موروثة لتتبُّع ما إذا كان مُعرِّفٌ ما يظهر على الجانب الأيسر أو الأيمن من عملية إسناد، وذلك لتحديد ما إذا كان عنوان المُعرِّف أو قيمته هو المطلوب. على عكس السمات المُصنَّعة، يُمكن للسمات الموروثة أن تأخذ قيمًا من العقدة الأب و/أو العقد الشقيقة. كما في المثال التالي،

S → ABC

حيث يمكن لـ A أن تحصل على قيم من S و B و C. ويمكن لـ B أن تأخذ قيمًا من S و A و C. وبالمثل، يمكن لـ C أن تأخذ قيمًا من S و A و B.

• القواعد النحوية ذات السمات L : يمكن تقييم السمات الموروثة في عملية اجتياز واحدة من اليسار إلى اليمين لشجرة بناء الجملة المجردة
• القواعد النحوية المنسوبة إلى LR : قواعد نحوية منسوبة إلى L يمكن أيضًا تقييم سماتها الموروثة في التحليل النحوي من الأسفل إلى الأعلى .
• القواعد النحوية المنسوبة إلى ECLR : مجموعة فرعية من القواعد النحوية المنسوبة إلى LR حيث يمكن استخدام فئات التكافؤ لتحسين تقييم السمات الموروثة.
• قواعد النحو المنسوبة إلى S : نوع بسيط من قواعد النحو المنسوبة، يستخدم فقط السمات المُصنّعة ، ولكن لا يستخدم أي سمات موروثة.

• قواعد الإلصاق
• قواعد فان وينجاردن
• الترجمة الموجهة بالبنية النحوية

• الورقة الأصلية التي تُعرّف بالقواعد النحوية المنسوبة: كنوت، دونالد إي. (1968). "دلالات اللغات الخالية من السياق" (ملف PDF) . نظرية الأنظمة الرياضية . 2 (2): 127-145 . doi : 10.1007/BF01692511 . S2CID 5182310. مؤرشفة من الأصل بتاريخ 19 مايو 2020. تم الاطلاع عليها بتاريخ 23 مارس 2018 . {{cite journal}}: CS1 maint: bot: حالة عنوان URL الأصلي غير معروفة ( رابط ) ,

• لماذا تُعدّ قواعد السمات مهمة ؟، مجلة موناد ريدر، العدد 4، 5 يوليو 2005. (تتناول هذه المقالة كيف يُسهم الشكل الرسمي لقواعد السمات في دمج البرمجة الموجهة نحو الجوانب مع البرمجة الوظيفية من خلال المساعدة في كتابة التحويلات التركيبية . وتشير إلى قاعدة سمات جامعة أوتريخت المؤرشفة في 5 يونيو 2013 على نظام Wayback Machine (انظر أيضًا : Lrc: نظام وظيفي بحت قائم على قواعد السمات من الرتبة العليا ) باعتبارها التطبيق المستخدم في الأمثلة.)
• قواعد السمات في علاقتها بلغة هاسكل والبرمجة الوظيفية .
• جوكا باكي: نماذج قواعد السمات - منهجية عالية المستوى في تنفيذ اللغة . مجلة ACM Computing Surveys 27 :2 (يونيو 1995)، 196-255.
• أوكس هو نظام تجميع لقواعد السمات، يُضيف إلى مواصفات ليكس وياك تعريفات للسمات المُصنّعة والموروثة، مكتوبة بمزيج من صيغ أوكس و C / C++ . انطلاقًا من هذه المواصفات، يُولّد أوكس مواصفات ليكس وياك عادية، تُستخدم لبناء شجرة تحليل مُنسّقة وتزيينها . يعمل أوكس مع إصدارات ليكس وياك المُوزّعة في أنظمة التشغيل يونكس وسولاريس ، بالإضافة إلى فليكس ، وRE/flex، وبايسون ، وBYacc ، و BtYacc ، و MSTA (في مستودع DINO على جيت هاب) . (انظر مستودع سورس فورج ).
• Silver هي لغة ونظام لتحديد قواعد النحو الوصفية القابلة للتوسيع من جامعة مينيسوتا. (انظر أيضًا مستودع GitHub .)