بسم الله الرحمن الرحيم الصلاة والسلام على أشرف
نفسي اليوم ان شاء الله احنا بنكمل المحاضرة اللي
بدناها اللقاء الماضي كان الحكي كله لسه في ال
introduction كانت المواضيع اللي أمامنا اللي هي ال
structure of a compiler واتعرفنا في ال structure
بتتبع بكم بره على المكونات التبعه ال lexical
analysis و ال syntax analysis و ال semantic
analysis و ال intermediate code generation و مثلا
ال optimization اللى بتحصل فى ال code ال
intermediate و فى ال code برضه اللى بيطلع فى الآخر
ممكن نعمله optimization اللى هى machine dependent
بيكون ال optimization و اتعرفنا على مفهوم ال
symbol tableو ايش الأمور اللى بتنعمل على ال symbol
table بداية من ال lexical analysis و لاحقا هنشوف
كيف برضه كمان أثناء ال syntax analysis و semantic
analysis بيصير فيه تعامل مع ال symbol table وقفنا
تقريبا عند هذا النقطة اللى هى ال grouping of
phases into passes و ال construction tools برضه
كمان هدولة الأن من النقطتين اللى بنذكرهم و بننتفل
بعدين على الشابتر التانى الشابتر التانى نشوف
example بسيط جدا اللى يوضحالكلام هذا كيف بيقوم بيه
ال compiler المرحلة المختلفة كيف بيسويها ال
compiler بشكل مفصل الآن ننتقل على طول على
المفتوحين الأخرونيات اللي هم ال grouping of phases
into passes وبعدين نتعرف على بعض ال tools اللي
بيستخدم في بناء ال compilers بدي أروح مباشرة كمان
احنا ال file اللي بتوضح اللي هو ال structureكل
واحد من الانصار هذه نسميها
phase مرحلة في هذا الإطار عندما نحكي عن groupingof
phases into passes معناه ذلك المقصود هنا ان بعض ال
phases هذه مثلا ال lexical analysis ال syntax
analysis ال semantic analysis و ايضا معاها ال
intermediate code generation هدول الفيزز الأربعة
نعتبرهم one path و هذه ال path بيسميها ال front
end
الـ front-end و الباقي اللى هو اللى من عند ال
intermediate code للأخر اللى نسميه back-end okay
فاحنا الآن عمليا
for example ال front-end phases اللى هي ال lexical
analysis ال syntax analysis و ال semantic analysis
و معاهم مين كمان قلتلنا ال code generation بس ال
intermediate code generation مش التواضعهدولة مع
بعض الأربعة might be grouped together ممكن ننظر
اللي هم عليهم مجموعة واحدة و واحدة مجموعة is a
path path يعني short بتقدر تقولي او دفعة واحدة
might be grouped together into one path والباقين
code optimization و code generation might beبمعنى
optional path بمعنى
إذا أنا ما بدى أعمل optimization ممكن أستغنى عن ال
optimization فإذا
هذول الأربعة one path و بناسميهم front end path
يمكن بيجيني أسمهم ال back end then there could be
a back end path consisting of ال code generation
ومعها أيضا ال optimization ال machine dependent
optimization وبأصبح أنا ممكن أنظر لعملية ال
compiler ال compiler structure على أن هذه front
end وهذه ال back end
هذا الـ front-end path وهذا الـ back-end path الـ
front-end path قلنا طبعا اللي هو ايش ال lexical
analysis ال semantic analysis ال syntax analysis
وكمان و ايضا ال intermediate code generation
الاخيرة اللي هي ال intermediate code generation
هي اللي بتبعتيني اللي هو إيش ال intermediate code
هذا ال intermediate code ممكن تيجي بعدين ال
backend تاخده تعمله ربما optimization تعمل target
و تعمل optimization
لل target هذا optimization one وهذا generation
وهذا optimization twoوالله عشان المقصود فيهم صح؟
وهذه ممكن تبقى optional زي ما قال هنا optional
ماعملهاش وهذه كمان يا ربي ال optimization بتاعي
ماعملهاش حسب الحاجة يعني الله إذا ال code صغير
برنامج صغير هتجده إذا ما ال system كبير و ألاف ال
instructions و الألاف ال lines بستاهل أنه يعمل ال
optimization طب إيش استفدنا من هذا الكلام؟ ال
grouping هنا ال grouping of phases into passes إيش
استفدنا؟سفرنا ان عملية البناء او عملية الترجمة اسف
عملية الترجمة اصبحت مجزة إلى جزئين انا لان لما
يكون عندى مثلا ال code انا كاتبه بال C او كاتبه
بال Java و بدى اعمله exe على different machinesده
نفترض ان في هذه different machines machine one,
machine two, machine تلاتة لان ال executable تبع
هذه هيكون مختلف عن ال executable تبع هذه عن هذه
يعني عملية ال code generation ده تختلف لهذه عن ال
generation تبع هذه عن ال generation تبع هذه انما
ال intermediate اللي بدورها واحد يبقى انا عمليا
محتاج اعمل هذا short مرة واحدة فقطبطلع ال
intermediate code بعد هيك باجيب back end خاصة ب M1
تاخد ال intermediate و تطلع ال target الخاص ب M1
back end أخرى خاصة ب M2 تاخد نفس ال intermediate
core و تطلع target خاص ب M2 و back end تالت طبعا
هذا ال back end غير هتكون غيره لأن هذا ال code
generator اللي هنا M1أه لإن واحد هيختلف عن ال code
generator تبقى هذا صح انما انا محتجت اكرر هذه
العملية تلت مرات خلاص هو one intermediate code
بعمله مرة واحدة في ال shot اللي هو في ال pass ال
front end و بعدين بعمل backend passes على حسب
جدّايش فيه machines هذه هي الغرض الأساسي من ال
grouping تمامنقطة تانية و الأخيرة في هذا ال
chapter أو في هذا ال section عاملين ان احنا من
chapter one اخدنا ال introduction way 1.2 اللي هي
ال compiler construction tools وهذا مهم جدا نجف
عنها لان انا عاملين يوم باجي و بدي اطلع على ال
structure تبع ال compiler و اقول انا بدي اعمل
compiler يعمل ترجمة من لغة إلى لغةشغل كتير كتير
كتير كل واحد من هدول ال phases في حد ذاته مشروع
project فاحنا عادة ما بنكتب هذا ال .. ما بنكتب ال
lexical analyzer من الصفر ولا بنكتب ال syntax
analyzer من الصفر هدول برامج برامج احنا بتتنعمل بس
احنا مابنعملها احنا نستخدم حاجة اسمها compiler
generation tools يعني أدوات لبناء ال compilerالـ
generation tools هذه هي اللي بتعمل لـ lexical
analyzer وهي اللي بتعمل لـ syntax analyzer وغيره
وغيرته بمعنى انه ايش في يدي مثلا حاجة اسمها parser
generator ال parser شو هو ال parser ال syntax
analyzer مش عارف اذا حكيتكوا جميلة او لا ال syntax
analyzer نسميه parser
فلما يوجهني اندي tool اسمه parser generator معناته
هي tool تستخدم في بناء ال parser بناء على ال rules
اللي انا هي اصلا اهم حاجة في ال constructing او في
بناء ال compiler ان انا اكتب ال rules اللي على
اساسها ال compiler هتحول هتعمل ترجمة هذه ال rules
متوفرة و كانت صياغتها سليمةهناك أدوات تقرأ أدوات و
تكتب للبرنامج اللي تريد ان تكتبه ك بارسر أو syntax
analyzer وهناك ايضا scanner generators scanner
اللي هو lexical analyzer او
احدهم يسمونه Lexar Lexar او Lexical Analyzer او
scanner تمام that produce lexical analyzers from a
regular expression a regular expression
description
قواعد الlexical analysis اذا احنا محددين القواعد
هذه مصممينها كويس و صح نسلمها للlexical analyzer
generator او ال scanner generator وهو اللي واحد
بيطلعلي برنامج مكتوب بلغة ال C او بلغة كده اعمله
compilation وهذا البرنامج خلاص بيصير اعطيله ال
source وهو يعطيلي ال tokensمش ال lexical analyzer
اللي بيسوي بياخد ال source code و بيعطي ال token
stream بياخد ال character stream و بيعطي ال token
stream كذلك لها قيسة على بقية ال tools الأخرى كل
tool يعني هذا مثلا code generator generator أداء
لبناء ال code generator all right و ال syntax
directed translation engines هذا برضه يبقى عنTools
اللي بيستخدمها to produce collections of routines
يعني روتينز يعني code برامج اللي بتستخدم في ال
translation Data Flow Analysis Engines هذي ال
tools اللي استخدمها في تحديد ال data flow بس هذي
ما بيعمل generation ل code انما هذا ال tool kit
هذي ال tool kit هذي هي عبارة عن تشكيلة من ال other
tools بيسميه tool kit خاصة tools خاصة بالبناء ال
compilers
السابقين المثال في حاجة اسمها flex flex هذا طول
بيستخدم في generating lexical analyzers بناء على
ال rules اللي .. هنشوف كل يعني محور أساسي و حول
المثقفة ده اللي هو كيف صياغة ال rules تبع ال
languageالـ Source Language طبعا اللى على أساسها
ال rules هذه على أساسها ال rules هذه بيتم تحليل ال
source code من ناحية ال lexical و من ناحية ال
syntax و من ناحية ال semantic فإذا ال rules هذه
مقمومة و موجودة نستطيع بناء عليها نبني ال
analyzers تمام فالان نقطة برضه أخيه وضلتههذه
التقنيات اللي هنتعلمها في ما يتعلق بشغل ال
compiler و كيف يعمل ال compiler ممكن تستخدم في
تطبيقات غير تطبيق ترجمة اللغات من source ل target
على سبيل المثال في حاجة اسمها ال text mining يمكن
تذكرت ان هذا الكلام قبل هيك ال text mining كل
بيعمل نوع من ال data mining على ال text sources
يعني ال input تبعه مش database ال input تبعه كلام
زيكا كلام مرسد كلام مقالات ولا حزيكا فجزء أساسي من
عمل ال text mining انه ناخد الكلام هذا و نعمله
analysis عشان نطلع المفردات كل مفردة ربما بدنا
نعرف جديش اتكررها كمرةلان انا بعرف الفعل الاصلي
تبعها اذا هي verbal اي اه فالتحليل هذا بلزم ادوات
مشابهة يعني بلزم ال lexical analyzer و بلزم ال
syntax analyzer عشان بس نستخلص المفردات اللي
موجودة في هذا النص عشان نقدر بعد هيك ربما نصنف
النص هل هو تابع لهذا topic او تابع لهذا topic او
نقدر نستشف اللي كتب هذا النص ايش توجهاتهأو قراءه
في ال .. هل هو مع هذه القضية ولا ضد هذه القضية ال
software يقدر يعطيني حكم على الكلام اللي مكتوب ..
الكلام اللي كتب بس عشان نصل لهذا الكلام يبدو شوية
AI بس عشان نبدأ فيه لازم يكون فيه أدوات لتحليل
النص مثل ال lexical analysis و ال syntax analysis
طيب احنا هيك بنكون .. يعني أخدنا المقدمةأو ميزمنا
من ال chapter المقدمة أو ال chapter one ال chapter
التاني اللي هنبدأ فيه الأن ان شاء الله برضه هو
chapter تمهيدي بس خلاص بنبدأ ندخل على level أعمق
شوية يتعلق بالمفاهيم
و الأساليب
اللي عمل في ال phases المختلفةهذا الكلام في الكتاب
جاي من خلال example مثال صغير ل translator
translator بترجم expressions مش برامج كبيرة
expressions صغيرة من أسلوب إلى أسلوب أخر خلال
استعراضنا لهذا ال exampleالـ example هيجي لسه قدام
شوية بس من خلال استعراضنا لل example بنقول أخدنا
فكرة كويسة عن ال phases هذه اللي احنا الآن عارفين
ايش بيستوي بس كيف بيستوي لسه مش واضحة للناس بتوضح
من خلال هذا ال example ان شاء الله فاحنا الآن في
chapter اتنين فيه انا اربع succession مدرسية بدنا
ناخدهمintroduction two two اللي هو syntax
definitions لنتعرف على إيش يعني syntax definition
syntax definition هي ال rules اللي تستخدم في صياغة
اللي هو .. او في التعبير عن ال syntax و ال syntax
directed a translation و بعد كده قضية ال parsing
كل هذا هنطلع عليه كمفهيم و نطلع عليه ك example
لعملية .. لل translator هذا اللي بيحول من
expression إلى expression بصيغة أخرىطيب مافي احنا
نبدأ الان على ال introduction بنطلع
على انه لو انا عندي .. طبعا هذا لسه مش ال example
بس هذا موضح مفهوم اللي هو ال .. ال .. كيف ال .. ال
.. ال text بتتحول من لغة إلى .. من .. من لغة إلى
لغة أو من instruction إلى instructions تانية هذا
.. هذا ال code هذا جزء من code مكتوبةالـ C صح يوجد
هنا مجموعة من التغييرات الـ I و الـ J و ال array
هذه و بعد ذلك يوجد wild loop ال wild loop هذه
بتستمر على طول الى ان بعد ذلك في هذا الشرط اللي
اتحقق ان يعمل break نطلع من ال loop لأن هي بضررة
مستمرة المخرجة اللي هو هذه فهذا
ال code الآنلو بده يترجم الى .. الى مش target الى
intermediate format هذا ال format زي اللي شفناه و
احنا بنحكي عن ال phases صح؟ مش عارف اذا كان .. انا
ذكرتلكوا ان هذا النمط من ال instructions بيسميه
three address code يعني كل واحدة منهم is a code او
instructionfree address code التسمية
جاية من ان كل instruction تحتوي على تلات ادرس ادرس
يعني identifier هذا ادرس و هذا ادرس كل واحد من ال
identifiers في الآخر هو memory address ال constant
هو قيمة ال address هو المكان لقيمة لقيمة موجودة في
هذا المكان المهم ان هذا three address code فورمات
هو نمط من الألماط ال intermediate الوسيطة هدفنا
الان ان نطلع على هذا ال example عشان نشوف كيف هذا
ال example اترجم الى هذا ال example كيف هذا ال
code اترجم الى هذا ال code صح هاي هذولة في الآخر
int i و int jهنا فيه ايش فيه انا assignment ل ال
values تبعتهم ال I بتاخد I plus واحد وال J بساخد J
ناقص واحد هذا الكلام لو بدنا نطلع على ال code هناك
وين بيجي هاي ال I بساوي I plus واحد okay بس بعد
هيك بدرجع نرجوها هنا ايش ال Iأخدت الكلمة هذه و
بعدين قلت عملنا while عشان do هذا
while و لا هذا الكلام يعني هيعمل هذه طالب ان هذا
الشرط متحقق صح؟ يبقى هذا الكلام كيف يتفسر؟ يتفسر
ان في عندي ال a صفقة خلينا أكتب ال line هذا كذا
حاجة بس عشان
باختصار شديد هحط ال a sub i في متغير T1 ثم يقارن
T1 بHV إذا T1 أقل من Vو احد اللي هي هذه لضابط كل
هذا الكلام الى ان هذا الشرط يصبح خلاص هنا تنتقل
الى البعد اللي بعدها برضه يعني عبارة شبيهة شبيهة ج
مستويه ج نقص واحد لضابط ينقصني ج واحد كل مرة طالما
ان انا انا كنت باش هنا تمام فهذا ال block هي في
هنا block اخر شبيه الواحد نظيف؟ لأن بعد ذلكعليش
بتقول go to أربعة فهذا جاء go to واحد بعد ذلك فيه
لما بيخلص هذا الشق بيجي بعد ذلك ال F طلع ال I و ال
J بيقارن مع بعض إذا ال I أكبر من أو سوى ال J بيطلع
فهذا الأمر سطر واحد فوصفانها الولادة سطر واحد سطر
واحد إذا I أكبر من أو سوى J go to تسعة تسعة اللي
هي هنا خلاص هنا حدود ال while
هي ال break بتطلع من ال current iteration صح عشان
تكمل على اللي بعدها ايش اللي بعدها بيجي I gotta go
to تسعة تسعة ال X بيساوي A of I بعدين نكمل مظبوط
هذا اللي هو السطر اللي بعد سطر واحد هو صحهذا الصفر
X لأ هو ثلاث statements X بسوء AI و AI بسوء AJ و
AJ بسوء X بعدها كان هذا الكلام يتكرر طالما انه
true يعني اللي بيطلعنا هو
الكلام الأربعة عشرلأن مكتوب false اه اه اه صح if
false بالظبط اذا false بنستمر مظموم بنروح هنا اذا
true بتطلع بيجي هنا هذه بتطلع .. okay ماعندي اقول
خلاص تمام هذي بتطلع برا ايه ايش برا ال loop كلها
صح تمام فاحنا عمليا الآن صارواضحة عنا أن شغل ال
code generation أنه أصل من هذا إلى إشي زاهد .. إشي
زاهد .. إشي اللي هو intermediate هذا ال
intermediate إذا وصلتله بقدر الآن بتنفس الصعوداء و
بقدر أقول إيه حلو كتير أن هذا الكلام أصلا أسهل أن
أترجم هذا إلى target من أن أترجم الدوشة هذهيعني
أصبح شغل ال translation بالتجزئة يعني أصل إلى
intermediate وبعدين من ال intermediate إلى target
okay فالكلام
هذا بتيم من خلال التعامل ما بين ما بين التلاتة
المكونات اللي هي في ال front end الأساسي اللي هو
indexical analyzerالـ parser و أيضًا كمان بيجي ال
semantic بس الدور الأساسي جاي مابين التلاتة دولة
ال lexical analyzer في ال parser و ال intermediate
code generation بتطلعلي ال three address code اللي
هو ال intermediate code representation وهذه بعد
هيك بنستخدمها في ال phase في ال class ال backend
عشان نحولها إلى ال target كل هذا الكلام بتبقى
التعاون معأو بتبادل البيانات مع الـ single tail
هذا عبارة عن model of the compiler front-end دخلنا
شوية على مستوى أعمق من ال .. هذا ال representation
هذا ال code 300 عبارة عن intermediate code
representation بسميها يعني تمثيل لل intermediate
code ممكن ال intermediate code بيجي على شكل tree
يعني ممكن انا بدل ما اطلع tree هذا code اطلع
intermediate و هذ ال intermediate اطلع tree و هذ
ال tree هي اللي يستلمها من ال backend عشان يطلع
منها يطلع منها ايش يطلع منها ال target code بس
احنا هنا ال slide هذا الهدف منها يتوضح لك انهالـ
three address code ليس هي الوحيدة للإنترميدية
للإنترميدية ليس هي الوحيدة للإنترميدية للإنترميدية
للإنترميدية للإنترميدية للإنترميدية للإنترميدية
للإنترميدية
وهي ال body وهي ال condition هذه
ال sentence تم ترجمتها إلى هيك وممكن ترجم إلى هيك
هذول تلين ترجمة ولكن مش ترجمة نهائية ترجمة وسيطرة
موجودة هذه الترجمة three address code وهذه syntax
tree مش بتقوللي ان انت في عندك عملية أساسية اللي
هي ال Dubai عشمالها ال body تبعها وعلى يمينهاالـ
condition اللي بده الان ال code generator راح
يستطيع نمسك هذه و منها يطلع ال target الان
في
ال section
2.2 بنطلع على المفاهيم التالية انا برجع في ال
slideسكتشن 2.2 يطلع على قضية how do we define ال
syntax يعني
كيف
انا بدي اعبر عن صيغة الجمل جملة ال do while ولا
جملة ال for ولا اي assignment statement ولا اي
expression كيف بدي اعبر عنها على شكل rule او قواعد
علشان هذا ال rule ييجي ال lexical syntax analyzer
يفحص ال code عشان يتأكد أنها سليمة عشان يتأكد أن
ال code هذا سليم مطابق لل rule لازم انا اعرف كيف
اصيغ rules تمام فأول حاجة في أن ال grammar و ال
definitions تبعتها يعني ال syntaxعشان اعمل
definition لل syntax عشان اعمل grammar عمليا لان
ال syntax دفعش لجرامر فبتنشوف كيف how do we define
grammar بعدين في مفاهيم تابعة لقضية defining
الجرامر لان الجرامر ممكن تبقى ambiguous ممكن احتاج
ل parse tree او اشوف كيف انه هل الجرامر ال
definition اللي انا حطيتهبيولد تري واحدة و لا ممكن
توليد اكتر من تري اذا اكتر من تري من نفس ال
definition هذا معناته ambiguity ال derivation
مفهوم ال derivation كله هذا الكلام بيجيه و ال
associated كله تابعا لكيف احنا بنصيغ ال grammar
وهذا هو موضوع ال section 2.2 خلينا نطلع عليه ناخده
على نثال بسيط جدا احنا كنا لتو بنحكي عن ال do
while statement صح هذا ال do whileعشان تترجم اليك
او ليك اول خطوة ان احنا اول ايش نسلمها لل syntax
analyzer عشان في الأول يتأكد اللي انا سليم و لا مش
سليم و مظبوط و بعدين نبدأ نحكي في ال code
intermediate code generation فال syntax analyzer
بده grammar ال grammar هذا عبارة عن definitions
فيها سيارة ال definitions تبعات الجملة المختلفة
اللي في اللغة اللي منها ال do واللي منها ال F
واللي من غير ال F فعندك انت الآن Fع سبيل المثال ال
F بيجي بعدها جوس و جوه ال جوس فى expression و
بعدها ك statement و بعدها كلمة else و بعدها
statement صح؟ okay الان هذا ال F is a statement و
ال Y is a statement و ال assignment is also a
statement فانا عندي مفروض statement اختصر هذا
اختصر بس مفروض statement ممكن يبدأ صيرته Fممكن
تبقى while وممكن تبقى غير وغير او انماط متعددة من
الاش هذا واحد منها فانتي عندك هذه ال definition
بيعدر
عن ال syntax تبع جبلة ال F لان هذه ال definition
بتكون من اولا اللي هو ال symbol هذا statement
والسهم يعبر عن أن ال statement can have the form
ممكن يتجه شكلها كالتالي ال if و ال goes و
expression و ال goes و statement و else و
statement statement هذه و statement هذه و
statement هذه يقصد بيهم نفس الشيء بمعنى كأنه أنا
بعمل إيش nested definition يعني بقعد بقول أن ال if
statement ممكن أيضا تحتوي على statement و ال
statement دي ربما تكون أيضا ifالمهم انه انا لو
طلعت اول اشي ملاحظه ان في يدي عناصر مكتوبة
بالitalic وعناصر مكتوبة بالbold اخدي بالك ايش
الفرق هذه ال F ايوه هدولة و ال S Keywords و هدولة
اللي بالمالي ال XPR و STMT Statement هدولة نسميهم
non terminals ال non terminalهي شيء لسه إله إمتداد
non-terminal terminal يعني شيء خلاص نهائي non
-terminal يعني شيء لسه إله ما يتفرع منه واضح فهذه
statement هذا ال symbol تفرع منه هذا statement لو
أنا بدرسمها على شكل تفارقه بقول يتكون من عدة عناصر
ال F يعني هوممكن يأتي على صيغة عدة عناصر فأي
شيء لسه يتفرع إلى عدة مكونات هذا non-terminal لكن
ال F ما بتتفرعش إلى أي شيء ال F هي في حتة ذاتها
keyword الجسم هدول ال terminals هذا و هذا و هذا و
ال rest هدول ال terminals صح؟ فاحنا الصياغة تبع
السيارة أو ال definition تبع أي مكون
من مكونات اللغة مكون construct أي مكون قد يكون
statement و قد يكون مش statement صح؟ مديش أقول ال
definition تبع أي statement مدي أقول ال definition
تبع أي مكون من مكونات اللغة هيجي
بعناصر .. هيحتوي على العناصر التالية ال terminal و
ال non terminal هنا
هذا عبارة عن .. بحكي عن ال grammar كله ال grammar
كله اللي هي عدة definitions عشان كده بقول a set of
terminals .. a set of كده .. a set of كده فاحنا
الآن نبقى فيها العدة definitions كل definition
بيبقى شبيه بال .. بهذا الادة ال definitions مع بعض
هم بشكل ايش ال grammar okay ف context free grammar
وبعدين بنفهم ليش هي اسمها context free بس الآن
بقولي a grammar has four components a set of
terminal symbols شوفي كل هدولة بنتفق هذا is a
symbol is a symbol symbol symbol symbol كل هدىرموز
ترمز كل واحد يرمز إلى شيء هذا يرمز إلى keyword
وهذا يرمز إلى terminal a set of terminal symbols
sometimes referred to as tokens بعدين نفهم ليش ال
symbol بينجل عن ال token a set of non terminals
هنا في ال example هذا واحد اتنين تلاتة اربعة non
terminals and a set of productionsكل سطر is a
production كل سهم كل
سطر يحتوي على سهم السهم فيه على شماله وعلى يمينه
is a production كلمة production بتمر معانا لما
بدرس ال AI ال production تيجي مرادفة ل ruleفي ال
AI اللي بيدرس ال rules و ال rule based systems
بسميها برضه productions فهي ال production يعني
rule و ال rule معروف في أي rule أنه في ال AI في ال
computer science أنه شرط إذا تحقق يؤدي إلى
condition بس هنا احنا مابنقولش rules لأنه ماهياش
شروطه و ده بس يعني هنا القضية أنه نجرى نجرى ال
production كالتالي a statementcan have the form
ممكن أن تأتي على شكل كذا كذا كذا كذا كذا كذا كذا
كذا كذا كذا كذا كذا كذا كذا كذا كذا كذا كذا كذا
كذا
كذا كأو ال production هتعتبر ال left hand side
تبعه a start symbol يعني هنا هنا statement ربما
أجي بعد هكذا بدي أعرف expression can have the form
كذا كذا ربما و أنا بأعرف ال expression يظهر معايا
non-terminal جديدة فبأجي أحتاج إلى تعريفه لأن
التكون عندى ليش؟هدول ال definitions أو هدول ال
productions بيكونوا لجرامة لأن meaning هدوله هو
ال start ليش بدى start؟ واحد منهم لازم يكون start
ال syntax analyzer اللي بيجي ياخد ال input بدي
يبدأ من ال start وشوف هل ال input يطابق ال
structureطبع أي شكل من أشكال هذا ال start ال start
قد يكون له قدت أشكال يعني statement مثلا دي على
فرض أنها start فيها هذا الشكل و ال F و في ال while
و في assignment و في كذا و في كذا فهو هيقعد يشوف
مين من هدولة الأشكال تبعت هذا ال start قد إذا ال
statement هي start قد تكون expression هي start
المهم أنه ال lexical analyzer لازم يتحدد له مين ال
start symbol اللي يبدأ من عندهعملية التحليل و
المطابق أو حاول يطابق واضح فهذه الأربع أناصر بتكون
منها أي grammar ال grammar إذا أحنا كتبنا ال
grammar تبع ال language معينة و نستطيع نسلم هذا ال
grammar لأ ال generator إذا أنا بكتب grammar
syntax grammar بيعني أنه بدي أسلم لل أحسن
generatorأو الـ syntax analyzer generator عشان
يطلّعلي syntax analyzer بقيت ال syntax analyzer
اللي طلّاليه بعطيله source بيقول ليه هاي ال tree
أو هاي التحليل نفس الاشي بينعمل برضه لل lexical
بينعمل definition للمفردات المختلفة بس هذا الكلام
هنشوفه في الشأة التالتة ان شاء الله زي ما في عندي
rules أو definitionsللـ syntax لازم يكون عندى برضه
definitions لل tokens نفسه لكسيم نفسه يعنى ال F
كيف .. كيف ده عمل definition لل F عشان يتعرف عليها
ال lexical analyzer كيف ده عمل definition
للمتغيرات مش ان احنا بنقول ال identifiable يعني
متغير طب المتغير كيف اسميها عادة الشرط الوحيد ان
تبدأ ب characterوتمد كده ما بدها المهم ما تبدأش ب
إيش ب digit أو special character صح؟ هذه ال rule
هذه الشروط اللي أنا قبلها حكيتها لازم تصاغ على شكل
rules بس اللي قال مش إيش مش context free grammar
في حاجة اسمها اللي هي ال ال ال regular expressions
ال regular expressions هي اللي بستخدمها فيصياغة
البنيا تبع المتغيرات وغير المتغيرات من المفروضات
المختلفة على مستوى المفروضات طيب الآن هنا هاي
example لكلام هذا اللي توحى هنا هاي several
examples ها في عندي مثلا أنا مفهوم list list زي
هيك مثلا هذه هذا الكلام اعتبره زي list و list
البنيا تبع ال listis a list plus digit و ال list
ممكن ناقص digit و ال list ممكن تبقى digit بس لحالك
و ال digit هو فقط اي واحد من هدولة ال .. ال .. ال
.. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال ..
ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال
.. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال ..
ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال
.. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال ..
ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال
.. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال ..
ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال
.. ال ..
Input ممكن تشكل منه Tree Syntax
Tree ممكن
تشكل منه Tree Syntax Tree ممكن تشكل منه Tree
Syntax Tree ممكن تشكل منه Tree Syntax Tree ممكن
تشكل منه Tree Syntax Tree ممكن تشكل منه Tree
Syntax Tree ممكن تشكل منه Tree Syntax Tree ممكن
تشكل منه Tree Syntax Tree ممكن تشكل منه Tree
Syntax Tree ممكن تشكل منه Tree Syntax Tree ممكن
تشكل منه Tree Syntax Tree ممكن تشكل منه Tree
Syntax Tree ممكن تشكل منه Tree Syntax Tree ممكن
Syntax Tree ممكن تشكل منأولشي الأولى و بعدين ال
list يبقى عنى تانية التاني ممكن تصبغش لأن التاني
بدها بعده نقص فقط digit وهذا أكثر من digit بعدين
ال list اللى طلعت من الأولى يعني نعمل أولى تطبق
الأولى على أساس أنه تسعة و النقص خمسة دول مع بعض
is a list و بعدين جاي الزائد و بعدين هذا جاي على
أنه digitطبعا طبعا طبعا طبعا طبعا طبعا طبعا طبعا
طبعا طبعا طبعا طبعا
هذا الكلام متوافق مع القول أنهي هذا الانهالة إبراع
ال digital تمام؟
تلت تسعة جدّمنا
الخطوة اللي قدامنا بس احنا القصد بس يوريكي example
ل definitions بس احنا تجاوزنا عن الأمر وشوفنا كيف
هذه ال definitionهو لو أخدها ال parser هتطبقها
لتأكد من أي واحدة من هدولة كلهم هدولة سالمات
يعني من ناحية من ناحية ال grammar okay الآن ايش
قلنا احنا انه متى نصرها دي definition وفهمنا ايش
يعني ال context free grammar definition في
المفاهيم اللي برجع نرجوها جاعدمفاهيم التابعة الـ
Derivation, Sparsing trees و Ambiguity كلها تتبع
.. خلّيني أن أخدهم واحد واحد اللي هو المفهوم الـ
Derivation الـ Derivation to derive .. إيش يعني
نشتق؟ derive مش drive .. derive ف grammar derives
strings by beginning with a start symbol and
repeatedly replacing a non terminalreplacing a non
terminal by the body of a production for that non
terminal يعني مثلا اللي احنا أول سونا هذا تسعة
مقص خمس زائر اتنين انا ال syntax analyzer مظيفته
انه يبدأ من start simple
بعدد خطوات في كل خطوة يحول ال start إلى شكل من
أشكاله بعدين ياخد واحد من ال non terminals يحوله
إلى شكل من أشكاله بالتدريج إلى أن يصل إلى ال
string اللي هو ال source فهذا ال source اللي
اعطيته ال ويان وظيفة ال syntax المراجعة انه يشوف
اذا في طبيقه تؤديمن ال start إلى ال input من ال
start إلى ال input اللي يدخله عبر إيش؟ عبر .. في
كل نقلة في هذا الطريق يحول non terminal إلى شكل من
أشكاله إيش يعني non terminal إلى شكل من أشكاله؟
هذا non terminal وهي شكل أشكاله هذا ال body of the
production ال body تمام؟ كل هدولة ال bodiesلحظة ان
الخط العمود هذا هو ال digit لها عشر أشكال بس
حطناهم في سطر واحد فصلناهم بالعمود يعني كان
المفروض انا اكتب digit can have a form 0 digit can
have a form 1، digit can have a form 2، بس ايش
فرطناهم على سطر واحد ال derivation ايش قلنا
معناته؟ معناته ان ال syntax analyzerبدو يبدأ من ال
start symbol تبعات ال grammar ال grammar هي ال
start symbol واحد و يصل إلى ال input و يصل من خلال
نقلات كل نقلة هي عبارة عن تبديلة واحدة تبديلة
بيبدل فيها a non terminal بال body تبعه بال body
تبعه بأحد ال bodies تبعته او بال body تبع أحد ال
productions تبعته مش ال non terminal ممكن يكون له
عدة productionsالـ syntax analyzer بيبدل الـ non
-terminal بالـ body تبع أحدى ال production إيه كذا
بيكون الكلام أدق بال body تبع هيته فهذا
هو ال derivation a grammar derives strings by
beginning with a star symbol and repeatedly
replacing a non-terminal by the body of a
production for that non-terminal أحدى ال
productionsالباقي تبع احد احدى productions تبعت
هذا term تمام فانا
هتبري ان هدا ال productions هدولة اللي هي اكتر من
احد اتنين اكتر من احد اتنين انواع هي ال grammar
اللي عندك و هتبري ان ال start symbol تبعك هو list
كلمة list أو السمبل list هو ال start symbol فاحنا
الآن عملية ال derivation عدة خطوات nine
is a list nine
is a list by production اتنين تلاتة بمعنى انه احنا
بنا نيجي نقول
اش
هذه تسعة نقص خمسة زائد اتنين ناخد هذه nine
is a list bioproduction اتنين تلاتة سنتين تسعة is
a digit
Digit can have a form of 9 فبالتالي بقدر اشتغل
التسعة ب digit و بالdigit ب list ساندي list فهذا
الكلام تسعة نقص خمسة is a list تسعة نقص خمسة is a
list لأنه تسعة
نقص خمسة is a listلأن list can have a form غير
list ناقص digit list التسعة اليوز already list
والناقص والخمسة هي ال digit بعد هي كان كله
مع بعضه is a list لأنه
9-5 is a list من الناحية و 2 is a digit من الناحية
و فعين دي rule الأولى 2.1 بتقول لي list زائد digit
is a list ال
parse tree هي الشيء متصل بال derivation متصل بال
derivationأنا قلت أننا نقوم بعمل derivation نبدأ
نحولها إلى list ذات digit ناخد هذا الـ form بعدين
ال list هذه نحولها إلى digit او لأ إلى list
بعدين list هذه شوفين اللي ساويت start list
حولتها ل list زاق ال digit من وين جيبت هذا الكلام
من
ال rule ال rule واحد بعدين list هذه حولتها ل list
نقص digit وخلت بلجي زي ما هو هذا ال rule ربط دولت
نهيلان لست حولت هذه إلى digit نقول
لقم تلاتة لان ال list is a digit زائد
بعدين
ال digital حولتها إلى تسعة و
استمرت لان بحول ال digitalالخمسة ال digit هذه
الاتنين انتقلت من ال start symbol الى هذا الأمر
هذا الأمر انا ممكن اعبر عنه شكل tree يعني هي list
و list تاخد الشكل list زائد و digit تمام خلاص هذا
ال tree تمثل هذا لأن هذا list هذهفاربعه تقل إيه؟
List ناقص List ناقص ال digit ثم
هذا فاربعه تقل ال digit ثم هذا تقل ال تسعة هذا تقل
الخمسة وهذا تقل الاتنين هذا ال syntax tree مقابل
لل derivation
مفهوم ال syntax tree أصبح يعني أن ال root بتبع أي
tree أو أي subtree هو عبارة عن ال left hand side و
ال children هم ال body أو ال symbols اللي بتظهر في
ال body كل symbol لحاله is a child a parse tree
pictorially يعني على شكل صورة shows how أصبحت
symbol of a grammarderives a string يعني على سبيل
المثال إذا non terminal a has ال production هذه قد
يكون له أدت productions نفترض هذه واحدة منها أن a
can have a form x,y,z then a parse tree may have
an interior node interior node يعني أنا لتوجه to
root اللي هي a with three children one labeled x,y
,z from left to rightThe root is labeled by the
start symbol الروت تبع ال tree هو ال start symbol
each leaf is labeled by a terminal or by epsilon
ابسلون ابسلون يعني ده شيء تمام اذا كان حسب قد يكون
في عندي rules تحتوي على ده شيء بس انا بدي اشوفه
each interior plant is labeled by a non terminal
non terminal هذي بعد كده اذا في production طبقناها
بنفرع ال children اللي طبقناها
هذا اللي انا بتابعه سويته بس انا سبقته بشوية هذا
ال part 3 for deriving ال expression مش ال
expression نفسه for deriving ال expression عملية
deriving هذا ال expression اللي هي عملية تحليله
بمعنى انه نبدأ من start symbol و نصل إلى ال string
هناaccording to the grammar according to the
grammar مش على هواية عسب إيش ال grammar هي ال
grammar الرؤوسية اللي بتقولي إيش أشيل و إيش أحط
إيش اللي ممكن أشيله و إيش اللي ممكن أحطه طيب فأصبح
أنا بقدر كنتج عملية ال parsing أو كنتج عملية ال
lexical analysis أصلأخد ال string .. ال info
string و أطلع ال syntax tree ال syntax tree قد
ممكن نعتبرها intermediate representation اللي يجي
ال generator .. ال code generator يطلع منها ال
code الان مصمم ال ambiguity ببساطة شديدة إذا كان
في عندي anagramma الروح استبعتهاالـ productions
تسمح
بأن ال string الواحد أقدر أعمله derivation ب two
different parse trees هذا ال L expression هو نفسه
أنا أخدته هنا على أساس أن ال string زي ال string
بعدين هذه ال grammar غير عن الأولانية صح؟الجرامة
بتقولي a string can have the form of string زي ال
string أو ال bar هذا يعني او a string can have the
form of string not a string او a string can have
the form of zero مافيش مفهوم ال digit مش موجود
فانا بناء على الجرامة هذه لازده أستطيع ان اشتغل ال
analysis لهارسن يعني لهذا ال expression هده هي كده
حاله هدول لحالهم strings يعني بينهم زائدهذا لحاله
يبقى two strings بينهم ناطس من وين جيبته من الكلام
هيا فيه rule بتقول هيه بعد ك string لحاله على طول
هو الخمسة .. الخمسة لحالة ال string و التسعة لحالة
ال string من وين جيبته من الكلام من أنه على طول
بيقوللي string و لسه هذا معناته أنه بينما في
العالم .. و أيضا بقدر
و هد لحجة string هد لحجة string نعم تسعة بتيجي
string و هد بيجي string زي string هذا rule number
one two parse trees two valid parse trees for the
same input for the same string معناته ambiguous
grammar ambiguous grammar مش المشكلة
قد يكون في مشكلة و قد لا يكون في مشكلة بعتمد انه
انا هذا ال explanation اللي انا انكف ده اعمله
evaluation فانا بدي اجمع هل اجمع التسة عملاقات
كامسة فان هي كده مافيش خطورة لو انا جمعت ولا عملت
تسة عملاقات كامسة و بعدين جمعت مع اتنين ولا جمعت
خمسة مع اتنينبس في expressions مافيش اي خطورة يعني
ال semantics هي هي ال semantics تبقى هذه و ال
semantics تبقى هذه نفس الشيء بس في expressions
أخرى ممكن يطلع اذا ضرب و قصف مثلا او مختلط مع
جامعة و طرح ممكن يطلع لي two هذا ال part تعطيني
value لل expression وهذا تعطيني value تاني فاحنا
بصفة عامة بدنا ن .. ن .. ن .. ن .. ن .. ن .. ن ..
ن .. ن .. ن .. ن .. ن .. ن .. ن .. ن .. ن .. ن ..
ن .. ن .. ن .. ن .. ن ..لما بنصيغ ال grammar نعمل
حسابي أنه أنا أصيغها بحيث أنها تبدأ unambiguous
مفهوم ال ambiguity مرة أخرى هو إنه إمكانية
deriving the same expression by two different
derivations two different derivations has two
different syntax trees طيب الأهم قضية ال
associativity of operatorsاللي هي ممكن تيجي كمخرج
من مخرج ال ambiguity يعني أنا ألغي ال ambiguity من
خلال أنه أنا أصيغي ال associativity بشكل بشكل محدد
ايش يعني associativity يعني مين ال operator اللي
يأخد ال operators سبعته قبل انا
هنا بديالناقص تاخد ال upper hand في الأول ولا
الزائد اللي تاخد في الأول؟ هي عادة left و right
اللي بيجي في الأول و باخد upper hand طبعا منهم
يعني الناقص تاخد التسعة و الخمسة و بتشتغل عليهم و
الناقص تبحث في upper hand للزائد هذا كلام بتحدد في
الجرامة
أنا أصلي في ال grammar كتابة هنا إيش هذا expr
expression term term term الحد من حدود عملية عملية
حسابية العملية الحسابية الحدود تبع ال operands
نسميهم terms وال factor اللي هو شيء ورق عالي عملية
ضرب أو عملية قسمة تمام ف expression can have a
form expression زي ال termأو expression on this
term أو term فقط وال term قد يكون term مضروف في
factor أو term على factor أو قد يكون factor لحاله
وال factor هو digit أو expression جوا ghost هيك
انا بقدر اقول ان ال syntax analyzer بيستطيه انه
لما نشوف الان لما نشوف عمليات بالان على هذا الهول
هيأخد .. هيتحدد العملية اللي .. اللي بتتاخد في
الأول ولا لأ؟ واضح؟ كيف يعني؟ يعني لو عندي إيش زي
هيك تسعة زائد خمسة ضارة اتنين لأن ال grammar مرة
أخيرة و يعني للأبد أن ال grammar هي اللي بتحكم ال
parserالparser بيشتغلش على عشوائي ال parser بيمشي
على ال grammar بيعمل derivation من أن ما يتيحله من
role of productions في ال grammar صح أو لا؟ لا
يمكن ييجي يخد هدي مع هدي أو هدي مع هدي من عنده من
أن على أيش ال grammar بتنصف إذا ال grammar بتقول
ال execution اللي ممكن ييجي expression زي ال term
أو منقص term أو ييجي ضرب و قسمة بيخد على أساس اللي
عندهفهنا عنده اما تكون زائد و جابليها expression و
بعدها term او نقص و جابليها expression و بعدها
term فلان هو بيطلع على .. فيه عنده زائد يبقى okay
يبقى هل هذا ترى expression و هذا هيك term لأ مش
هيظبط عشان يجوز اه طيب ايش العملات تسعة
expressions كيف تسعة expressions لأن هياخد هياخد
هذا كله على اساس من ال factor اه صحال factor it
can be an expression ال factor can be an
expression جوا بواس اقول هذا كله على أساس انه
factor factor مضموط في term صح؟ طيب في اي شيء يدعم
ذلك؟ عنده هذا كله باعتبره term ال term is a factor
term مضروب في factor expression
term
ضرب factor ال
factor can be a digit و ال digit الرقم 2 ال term
can be a factorوال factor can be an expression
ماحطيتش
جواز حوالين expression لأ كل واحد من دول is a
child وال expression هذا is إيش is an expression و
plus و term وهي plus وهي expression وهي term وال
term هذا is a factor و ال factor is a digitو ال
digit هي خمسة expression هنا is a term و ال term
is a factor و ال factor is a digit اللي
هي تسعة واضح؟ الغرب من هذا المثال انه يوريكي كيف
انت ممكن تضبطي عملية ال precedence شوفي هناحكمنا
ان 9 زي 5 هيتاخدوا في الاول و بعدين .. okay ..
بعدين يضرب الناتج في الدنيا okay
.. اه ..هذا ال precedence of operators بالنسبة
للمثال اللى بعدك اللى هو انه احنا ال ال keywords
ال f و ال y و ال do هى ال keywords ولا لأ لاحظ انه
لما بتيجى هذه ال keywords فى بداية ال production
بتسهل على ال syntax analyzer شغله ليش؟لأنه على طول
بيعمل مطابقة بأن ال input اللي دخل مفترض ان ال
input كان F5I أكبر من خمسة كده كده is هذا ال input
اللي دخل ماشي وجود ال F في قراس ال input على طول
هو عنده edit productions هيبحث يشوف إذا في واحد
منهم مطابق هي .. هيبس يحترم من هدول اتين اتين فقط
لكن لوالبرودكشن .. ال .. ال .. ال .. ال .. ال ..
ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال
.. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال ..
ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال
.. ال .. ال .. ال .. ال ..
ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال
.. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال ..
ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال
.. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال ..
ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال
ال .. ال .. ال .. ال ..
ال .. الالـ assignment statements الان ممكن انا
تبقى في الأول في identifier عندي مثلا V متساوي كده
كده فهد أشوف ال identifier أخش هنا okay بعد ك أاخد
expression ال expression هد يطلع
.. مش .. يطلع الhead دي مش مبادر هدور على إيش صيغة
أخرى identifierو .. او حاجة تانية ال identifiers و
ال non-terminants بتساعدش كتير في .. بتساعدش ال
syntax analyzer زي ال keywords ال keywords على طول
بتوجهه في احتمال واحد او احتمالين اللي يختبرهم
محاضرة جاية بنشوف كيف الكلام الآن بدنا نبني عليه
نبني عليه عشان نصل ل ال .. الورحة اللي بعد اللي هى
ال translation بما انه اناصار في عندي فكرة عن كيف
عملية تحويل ال input إلى syntax tree لنشوف okay
هذا ال syntax tree كيف أستفيد منها في إنتاج ال
intermediate code مش لسه ال code النهائي ال
intermediate code بمعنى أعمل ال translation على كل
هو كلام يعني زي ما تقولي أولي لأنه التفاصيل اللي
هنشوفها قدام كثيرة بس احنا الأن بناخدالفكرة العامة
لقليلة الشغل في ال syntax analysis و المحاضرة اللي
جاي ان شاء الله بنكمل