بسم الله الرحمن الرحيم
المرحلة الثانية الجزء الأول
تعريف اللغة
يمكن تعريف أي لغة باستخدام 4 مجموعات Tuples أساسية
1- الTerminal اختصاراً T و هي مجموعة من الحروف التي لا يمكن تقسيمها (الأبجدية) Alphabet
2- الNon Terminals اختصاراً N و هي مجموعة من الكلمات (المفردات) Vocabulary
3- الProduction Rules اختصاراً P و هي مجموعة القواعد (النحو) Grammar
4- الSubject اختصاراُ S و هو رمز البداية (الفاعل) Subject
1- الTerminal
و هو وحدة البناء الأساسية في اللغة أو كما قلنا هو الأبجدية (Alphabet) التي تتكون منه جميع المجموعات الأخرى و هو مالايمكن تقسيمه إلى أقسام أقل..
2- الnon Treminals
هو مجموعات من الterminals او الnon-terminal المتتالية التي تتبع قاعدة P فيتم تكوين non terminal و تعرف علمياً على الشكل التالي...
non-terminal ::= string of terminals and non-terminals
حيث العلامة =:: تعني "تُعرف على" is defined as
3- الProduction Rule
هي القواعد النحوية التي تُحدد كيف يتكون الnon-terminal من مجموعة terminals أو non-terminals
فالقاعدة السابقة
non-terminal ::= string of terminals and non-terminals
تعتبر Production Rule
4- الStarting Sybmbol
هو non-terminal مميز Distinguished و هو الذي يظهر على الجانب الجانب الأيسر من الProduction Rule التي تعرف من مجموعة من الTerminals فقط.... و هو أول non-terminal يجب أن يبدأ به البرنامج
بالطبع بعد المقدمة المملة السابقة قد لا تُكمل الدرس و لكن اصبر فالتالي أفضل...
ملحوظة: هناك اتفاق على أن الTerminals تكتب بالحروف الكبيرة (Capital Letters) و ال Non-Terminals تكتب بالحروف الصغيرة (Small Letters ) و هذا ما سنستخدمه نحن أيضاً
أنواع الProduction Rules
1- النوع الثالث Regular Production القواعد الاعتيادية
a ::= Av
حيث a هو الnon-terminal المُراد تعريفه
A هو Terminal
v هو sequence من الTerminals أو الnonterminals أو خليط منهم أو empty string (لاشئ)
و في الحالة الخاصة v = empty string يكون ال v = A أي ان الnon-terminal هو أساساً Terminal
2- النوع الثاني Context Free (Context Independent) السياق المستقل أو السياق الحُر
a ::= u
حيث الu هو non empty string من الterminals أو ال non-terminals
و في الحالة الخاصة اذا كانت u = Av يؤول النوع الثاني إلى النوع الثالث
3- النوع الأول Context Dependent أو السياق المُعتمد
xay ::= xuy
حيث ان ال x, y هما مجموعة من الterminals و الnon-terminals أو لاشئ
و في الحالة الخاصة اذا كان x , y كل منهما لاشئ يؤول النوع الأول إلى النوع الثاني
4- النوع صفر Phrase Structure Production
xay ::= z
حيث الz هي أي string حتى الempty string
و يمكن تلخيص علاقة الأنواع السابقة معاً بالشكل التالي
فكما يتضح أن كل نوع هو تعميم للنوع السابق له و هكذا
بعد هذه الأسطر من الملل سنبدأ في جزء أكثر اثارة و هو ال BNF
Formal Description of A Language
الطريقة التي تستخدم في التعبير عن اللغات بشكل عام هي طريقة Backus Naur Form BNF و قد ظهرت لأول مرة في التعبير عن لغة ALGOL 60
و لها قواعد أساسية سنسردها الآن
1- العناصر التي تُكتب بالأحرف الصغير Lower Case تُمثل ال non-terminals
2- العناصر التي تُكتب بالأحرف الكبيرة Higher Case تُمثل ال Terminals
3- الأقواس المربعة [ ] تُمثل عناصر اختيارية
4- العلامة # تُمثل احتمال تكرار العناصر السابقة لها
5- العلامة | تستخدم في التعبير عن الLogical OR
6- الأقواس المعرجة { } تُمثل العناصر الإجبارية و التي يجب وجودها
7- العلامة =:: تمثل أن ال nonterminal على يسار العلامة مُعرف مباشرة من الterminals و الnon-terminals التي على يمين العلامة
8- العلامة <=:: تمثل ان الnon-terminal على يسار العلامة مُعرف بطريقة غير مباشرة عن طريق الterminals و الnon-terminals على يمين العلامة
كمثال على القواعد السابقة مثلاً طريقة كتابة الأمر DEL في الDOS و الذي يُستخدم في حذف الملفات
delete_command ::= DEL [path_descriptor] filename
و هنا يتم تعريف الnon-terminal المسمى delete_command بأنه الTerminal DEL متبوع بnon terminal اختياري و هو الpath متبوعاً بnon-terminal آخر و هو اسم الملف filename
و فيما يلي بعض الأمثلة على الBNF في التعبير عن المتغيرات المختلفة
identifier ::= letter [letter | digit]#
و كما نرى أن تعريف الIdentifier هو حرف متبوع بتكرار اختياري من الحروف و الأرقام
و فيما يلي مثال متقدم يشرح التعبير عن الثوابت المختلفة عن طريق مجموعة قواعد
numeric_constant ::= integer | real integer ::= digit# real ::= digit#.[digit#] | .digit# digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
و للحديث بقية
ملحوظة: هذا الدرس ممل و لكن مهم ....