الرموز الطرفية وغير الطرفية

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

تحدد القواعد النحوية الرسمية لغة رسمية من خلال مفردات القواعد النحوية.

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

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

على سبيل المثال، لنفترض وجود قواعد نحوية محددة بقاعدتين. في هذه القواعد، Бيُعد الرمز رمزًا نهائيًا، Ψوهو في الوقت نفسه رمز غير نهائي ورمز بداية. قواعد الإنتاج لإنشاء السلاسل النصية هي كما يلي:

1. Ψيمكن أن يصبح الرمزБΨ
2. Ψيمكن أن يصبح الرمزБ

هذا Бرمز نهائي لأنه لا توجد قاعدة لاستبداله برموز أخرى. من ناحية أخرى، Ψيوجد رمز آخر له قاعدتان لتغييره، لذا فهو رمز غير نهائي. تُعرّف هذه القواعد لغة رسمية تحتوي على عدد لا نهائي قابل للعد من الكلمات ذات الطول المحدود، وذلك لأننا نستطيع تطبيق القاعدة الأولى عددًا لا نهائيًا من المرات كما نشاء. يوضح الشكل 1 سلسلة نصية يمكن إنتاجها باستخدام هذه القواعد.

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

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

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

في الصياغة الكلاسيكية للقواعد التوليدية التي اقترحها نعوم تشومسكي لأول مرة في الخمسينيات من القرن العشرين، ^{[ 3 ] [ 4 ]} تتكون القاعدة G من المكونات التالية:

• مجموعة محدودة N من الرموز غير الطرفية .
• مجموعة محدودة Σ من الرموز الطرفية منفصلة عن N.
• مجموعة محدودة P من قواعد الإنتاج ، كل قاعدة منها على الشكل التالي:

${\displaystyle V^{*}NV^{*}\rightarrow V^{*}}$

أين${\displaystyle V^{*}}$يشير إلى مجموعة جميع السلاسل النصية ذات الطول المحدود الممكنة ضمن المفردات${\displaystyle V=\Sigma \cup N}$باستخدام قاعدة كلين ستار . أي أن كل قاعدة إنتاج تستبدل سلسلة من الرموز تحتوي على رمز غير طرفي واحد على الأقل بسلسلة أخرى. في حالة كون النص يتكون فقط من سلسلة فارغة ^{[ ملاحظة 1 ]} ، يمكن الإشارة إليه برمز خاص (غالبًا Λ أو e أو ε ) لتجنب الالتباس.

• رمز مميز${\displaystyle S\in N}$هذا هو رمز البداية .

تُعرَّف القواعد النحوية رسميًا بأنها الرباعية المرتبة${\displaystyle \langle N,\Sigma ,P,S\rangle }$يُطلق على هذا النوع من القواعد النحوية الرسمية في الأدبيات اسم نظام إعادة الكتابة أو قواعد بنية العبارة . ^{[ 5 ] [ 6 ]}

صيغة باكوس-ناور هي طريقة تدوين للتعبير عن قواعد نحوية معينة. على سبيل المثال، تُستخدم قواعد الإنتاج التالية في صيغة باكوس-ناور لتمثيل عدد صحيح (يمكن إشارته):

< رقم > ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' < عدد صحيح > ::= ['-'] < رقم > { < رقم > } 

في هذا المثال، الرموز الطرفية هي${\displaystyle \{-,0,1,2,3,4,5,6,7,8,9\}}$والرموز غير الطرفية هي${\displaystyle \{}$<digit>،<integer>${\displaystyle \}}$[ ^{ملاحظة 2 ]}

مثال آخر هو:

${\displaystyle {\ce {S -> cAd}}}$

${\displaystyle {\ce {A -> a | أب}}}$

في هذا المثال، الرموز الطرفية هي${\displaystyle \{\mathrm {a,b,c,d} \}}$والرموز غير الطرفية هي${\displaystyle \{\mathrm {S,A} \}}$.

• الأبجدية (اللغات الرسمية)
• التسلسل الهرمي لتشومسكي
• القواعد النحوية المتكررة