بسم الله الرحمن الرحيم اليوم إن شاء الله بدنا
نستكمل في chapter 4 chapter 4 تقريبا معظم الأشياء
اللي فيه أخذناها قبل هيك لكن هنركز فقط على
الإضافات اللي ما أخدناش قبل هيك chapter 4 بتكلم
بالتفصيل عن ال syntax analysis اللي هو عملية ال
parsing بالتفصيل وعملية ال grammar طبعا أحنا أخدنا
العملية هذه قبل هيك في الشباتر السابقة لكن
بالتأكيد في أشياء يمكن ما حكيناهاش ب more details
خلال هذا الشبطن إن شاء الله بدنا نعرج عليها و
نحاول أن نعرفها أنا إن شاء الله خلال الشرح هحاول
أنّ الأشياء اللي أخدناها قبل هيك أتجوز عنها و أركز
فقط على الأشياء اللي ما أخدناش قبل هيك طبعا هنا زي
ما أنتم شايفين في البداية الرسمة الأساسية اللي
بتحطلنا الخارطة احنا وين موجودين اللي دائما بنتكلم
عنها من بداية الفصل أنا عندي lexical analyzer ال
lexical analyzer بيقرأ من ال source program و
بيروح بيطلع لي ال tokens ال tokens هدول بيبعثهم لل
parser و ال parser بيحاول من خلال ال grammar يعمل
عملية parsing tree و هي هذا اللي احنا نركز عليه ال
stage هاي أن كيف عملية ال parsing بتتم طبعا احنا
قلنا قبل هيك أن عملية ال parsing بتعتمد بشكل
أساسي على وجود ال grammar بيوصف ال language لأنّه من
خلال هذا ال grammar أنا بحاول أعمل عملية parsing
لل sentence اللي موجودة عندي فإذا هذه ال sentence
طلعت معناها هذه ال sentence سليمة و مكتوبة ضمن
النطاق تبع ال language أو ضمن ال syntax السليم و
الصحيح تبع ال language و طبعا زي ما احنا شايفين و
قلنا قبل هيك أن جميع ال stages بتعاملوا باستمرار
مع ال symbol table طيب، الآن في section 412 ببدأ
يتكلم عن ال grammar و كأنه احنا مش عارفين ولا إيش
عن ال grammar ببدأ يوريني كيف ال grammar بتكون من
ال non-terminal و ال non-terminal بتكون من ال
productions اللي موجودة عندي و مجموعة ال
productions كيف بتطلع ال grammar و كل التفاصيل
اللي احنا أخدناها قبل هيك و يمكن زي ما تشايفين هنا
هذا المثال اللي أزهقنا به احنا أنّه دائما بناخده اللي
هو ال expression expression زي ال term أو term أو
expression والterm عبارة عن term في factor أو
factor وال factor هو عبارة عن expression أو ID
وهذا طبعا احنا كثير أخدناه المثال قبل هيك أنا همشي
عنه بسرعة لأنّ احنا already اتعرفنا أن ال grammar
عبارة عن مجموعة من ال productions وأن كل
production بتكون من non-terminal بعدها سهم بعدها
مجموعة من ال terminals و ال non-terminals فهذا كله
إن شاء الله هنمشي عنه لأنه أخدناه في السابق طبعا
بالنسبة لموضوع الأخطاء أيضًا تكلمنا فيها قبل هيك
أين يتم كشف الأخطاء وما هي الأخطاء التي يتم كشفها
يمكن هنا احنا حابين نركز على النقاط التالية في أنا
عندي زي ما شايفين ال lexical errors وأيام أخذنا
الشبتر السابق تكلمنا فيها أن يكون عندي خطأ في
حرف، في عندي حرف زيادة، حرف ناقص، حرفين، أنا محتاج
أبدلهم مكان بعض أو أشيل حرف و أحط حرف كانت هذه
الأخطاء اللي موجودة عن طاق ال lexical طبعا في
أخطاء بيكشفها ال syntax analyzer زي إيش مثلا زي
لما بنسى الفصلة المنقوطة، بنسى السهم، بنسى عفوا
فتحة القوس، تسكيرة القوس، إلى آخره يعني أي أخطاء
موجودة من ناحية ال syntax هذه بنسميها على طول
syntactic errors بعد هيك في أخطاء من نوع ال
semantic برضه تكلمنا عنها قبل هيك يعني مثلا لما
أنا أقول x زائد y ويكون ال x مثلا اسم array و ال y
مثلا integer أو ال x float و ال y مثلا integer
فلازم يكون في حد يتأكد من ال types و يتأكد أنها
مظبوطة و م compatible مع بعض عشان تمشي الأمور بدون
أخطاء غير هيك بيجي ال semantic بيعلق و بيقول في
عندي أخطاء مثال ثاني حكيناه في semantic errors لما
بكتب بين ال array و بين جثتين number هي ك syntax
مظبوطة لكن إذا هذا ال number قيمته float بيصير في
عندي مشكلة فعشان هي كبير يجي ال syntax بتحقق أو ال
semantic عفوا بتحقق من ال semantic errors و آخر
نوع من الأخطاء اللي موجودة عندي اللي هي ال logical
errors زي إيش مثلا يعني واحد كاتب if x تساوي y طبعا
هو بيقصد هنا يعمل مقارنة بين x و y لكن هو نسي يكتب
ال double equals فراح كتب x تساوي y فعليا هي ك
syntax مظبوطة فعليا أيش اللي هيصير؟ في الـ language
هتنحط قيمة الـ Y في X أو إذا كانت هذه القيمة مش
صفر هيعتبرها true وينفذ لكن إذا كانت صفر هيعتبرها
false وينفذ فهيك لما تحط X تساوي Y لكن لما نحط X
تساوي تساوي Y هيقارن قيمة X بقيمة Y فإذا كانوا
متساويين بيروح على طول بفوت جوا ال if مش متساويين
بفوتش وبالتالي لو أنا كمبرمج نسيت المساواة للأسف
البرنامج هيقول لي ما فيش أخطاء ما في أي خطأ أو هي
بالفعل syntactically مظبوطة أو semantically سليمة
وما فيش مشاكل في ال lexical وبالتالي هيقول لي هي صح
مع أنها مش أنا اللي بديها أو مش أنا اللي كان
يقصدها المبرمج عشان هي قاعدة بنسميها logical errors
تمام طيب الآن برضه بالنسبة لموضوع الأخطاء احنا
إيش مطلوب من ال compiler مطلوب من ال compiler تلت
نقاط رئيسية أنّه يحاول يعرف لي إيش هو ال error بوضوح
و بدقة ومش بسيك وأنّه بعد ما يعرف ال error ويديني
رسالة عنه مش يوقف ويطلع برا لأ المفروض أنّه يقدر
يرجع للمكان اللي بدأ منه ويكمل ويحص بقية الأخطاء
يعني لازم يكون فيه قدرة على ال recover أنّه يرجع من
مكانه بسرعة ويكمل طيب إيش في نقطة ثالثة مهمة أنّه
ضروري جدا أن عملية كشف الأخطاء هذه بوضوح أنها ما
تستغرقش وقت كبير أنها ما يروحش يخل ال system ال
overall ال system تبعي يصير بطيء أو مش فعال عشان
هيك ألاحظ أنّه أنا بطلب هنا حاجتين عكس بعض أنّه
لازم يكشف الأخطاء بوضوح وبدقة وفي نفس الوقت
ما يديعش وقت كبير وهذا عبارة عن challenge لازم
دائما ناخد بالنا منها في عملية أن كيف ال compiler
بيشتغل و بيكشف الأخطاء و بيقدر يكمل بدون أي مشاكل
طبعا زي برضه ما حكينا قبل شوية كيف الـ compiler
يقدر يرجع من الخطأ و يكمل طبعا فيه استراتيجيات
error recovery strategies يعني فيه أكثر من
استراتيجية أن كيف بنخلي ال compiler يقدر يكشف أي
خطأ معين عنده القدرة يكمل في ال code و يكشف بقية
الأخطاء في عندنا تقريبا أربع استراتيجيات
الاستراتيجية الأولى اللي هي panic mood recovery
وهنا إيش بيصير أول ما بيلاقي أول خطأ بيصير يرمي كل
ال characters بالترتيب لغاية ما يلاقي نقطة أو
character بيقدر يبدأ من عنده يعني على سبيل المثال
تنتهي ال sentence مثلا بفاصلة منقوطة الآن قبل
الفاصلة المنقوطة بفترة لاجى مثلا error إيش بيسوي؟
خلاص بيصير يرمي .. بيرمي كل ال characters بالترتيب
مالهاش فحص لغاية ما يوصل لنقطة بداية جديدة مثل
فاصلة منقوطة و بيرجع من بعد الفاصلة المنقوطة يعيد
و يفحص من جديد و خلاص بيكون سجل رسالة error على
الخطأ اللي قبل شوية و هيك بيقدر يكمل بدون مشاكل
لأنّ عشان يقدر يكمل لازم يمسك نقطة بداية جديدة عشان
يعيد الفحص تبعه و يشوف فيه خطأ ولا فيش خطأ فهذه
بنسميها الطريقة panic mood recovery طبعا في طريقة
ثانية اللي هي ال phrase level recovery هنا لما
بيلاقي خطأ بيسيرش يرمي ال characters و يدور على
نقطة بداية جديدة، لأ بيحاول على المطرح يعرف شو هذا
الخطأ اللي موجود عندي، إيش الفكرة، هل الناس يجوز،
هل هو لأ ضايف جوز، فبحاول يعمل correction، بيحاول
يعمل تصحيح و يعرف نوع الخطأ، ليش؟ عشان ما يرميش إشي
و كل ال characters البجيان يتفحصوا يعني كانت في
الطريقة الأولى برمي كل ال characters لغاية ما يوصل
لنقطة بداية جديدة لكن في الاستراتيجية الثانية
بيرمي شيء بيحاول على طول ما بيلاقي الغلط
بيحاول يكتشف شو هو الغلط بيحاول يفهم أه كان ناقص
جوز لأ زيت جوز فبيحاول يصلح الخطأ في المكان
تبعه و يعرفّه عشان يكون عنده القدرة يكمل من نفس
المكان وما يرميش أي حاجة طبعا هذه بتاخد process
أكثر اللي بنسميها هذه الطريقة phrase level
recovery الاستراتيجية الثالثة بنسميها error
productions ال error productions نفس فكرة ال
grammar احنا ليش كنا بنحط ال grammar؟ احنا كنا
بنحط ال grammar ليش؟ علشان نقدر نوصف ال syntax تبع
ال language وبالتالي ال sentence لو نعملها parsing
بتصير في ال syntax تبع ال language وهنا نفس ال
idea ونفس الفكرة هنستخدمها لكن لوصف الأخطاء الشائعة
يعني في الأول طبعا بنعمل كتير تجارب كتير أكواد
بتنكتب بيحاولوا يعرفوا الأخطاء الشائعة وبعد هيك
بيصيروا يعملوا grammar يوصف هذه الأخطاء الشائعة
هذا ال grammar بنسميه error reductions وبالتالي
لما بيصير أنتي خطأ معين بنشوف هذا ال grammar اللي هو
error productions بيطلع ال tree ولا بيطلعش ال tree
والله إن طلع ال tree خلاص بعرف نوع الخطأ بقوله
أنت النوع الفلاني وبصير عملية التصحيح يعني الفكرة
تمامًا زي ما بنوصف ال syntax صرنا نوصف الأخطاء
الشائعة والجملة اللي فيها خطأ بشوف مين اللي
هتعملها parsing في ال grammar اللي بيوصف الأخطاء
والله والله مثلًا ال grammar الخامس مثلًا وصف لي ..
عمل لي tree لهذه ال sentence إذا أنا على طول بعرف
أن الخطأ هذا نوع الخامس وهكذا يعني الفكرة مش صعبة
مجرد وصف للأخطاء وبشوف ال sentence بعملها parsing
tree طلع parsing tree معناه في خطأ طب ما طلعش
parsing tree معناه هذه مش من الأخطاء اللي موجودة
عندي معناها بعتبرهاش خطأ مثلًا من الأخطاء اللي عندي
طيب آخر نقطة هنا اللي هي ال global corrections إيش
بقصد في ال global corrections؟ طبعًا لما بكون في
عندي sentence غلط بحاول أنه يحولها، يعمل عليها
تحويلات علشان تصير sentence صحيحة فهو بيروح بيجرب
على ال system اللي موجود عنده، بكون عارف إيش الطرق
للكتابة السليمة والصحيحة فالآن ال sentence اللي
فيها غلط بتطلق، بقول أه لو غيرنا مثلًا أربعاربع
characters بتصير صح، هذا حل، بعدين بيجرب كمان مرة
قال والله لو غيرنا عشرة بتصير برضه صح، هذا حل
ثاني، اه والله لو غيرنا اثنين characters بتصير
صح، فبيقدر يحدد كم صح بيقدر يطلع من هذه ال
sentence، في الآخر مين بيعتمد؟ صاحبة التحويل الأقل
يعني لو جاء حال أن أنت اثنين characters بتحصل على
حاجة صح خلاص بيقول لك بفترض أن هي هذه اللي كان
المفروض تنكتب ويقول لك في خطأ في المكان الفلان والمكان
الفلان لكن طبعًا إيش عيب المشكلة هذه إنه مش
بالضرورة تعطيك الشيء اللي كان في بال المبرمج يعني
يمكن اللي كان في بال المبرمج أنه لو عملت الأربع
أخطاء بتوصل لنتيجة المبرمج هو مش هيعمل زيّه هو لو
لجأ أنها خطأين بيطلعها صح في التحويل خلاص بيقول لك
على طول هذه بقصد فيها الثانية وهنا المشكلة يعني
باختصار لو أنا عندي sentence X تمام مكتوبة هذه ال
X غلط الـ X هذه بتتحول لواحدة من الصح تعتبر هدول
صح الـ Y صح والـ W صح والـ Z صح تمام؟ الـ X عشان تصير
Y المطلوب أغير حرفين مثلًا الـ X عشان تصير W
مفروض أغير عشرة characters مثلًا الـ X عشان تصير Z
يعني الـ Z اللي هي الصحيحة مفروض أغير خمسة
characters مثلًا إذا مين هيعتمد؟ هيعتمد اللي فيها
أقل عدد من التغييرات فهو هيفترض أن المبرمج كان في
باله يكتب الـ Y ويصير يقول لك خلاص هذه الجملة
الصحيحة ويذكر الأخطاء اللي موجودة هنا اللي بتطلع
لي لهذه لكن زي ما قلنا المشكلة أن المبرمج كان قصده
في Z وغلط كثير فهو ال computer بيفهمش بدور على
الأقل عدد من الأخطاء وبيروح بيقول له هذه الحل سواء
صح ولا غلط فطبعًا هذه المشكلة في الطريقة هذه بتأخذ
وقت كبير وللأسف في النهاية ما بتعطينيش نتائج دقيقة
عشان هي كبتلاقي في الغالب باعتمدوا على أول اثنين
strategies اللي هم ال panic mode و ال phrase level
recovery طيب الآن بالنسبة ل section 4.2 4.2 ما فيش
فيه أي شيء مش هشرح فيه حاجة ليش؟ لأنه بيتكلم عن ال
grammar ال context free grammar بفترض إنك مش عارف
أي حاجة على ال grammar فبيصير يشرح شو هو ال grammar
إيش مكونات ال grammar إيش ال production إيش ال
terminal إيش ال non terminal وهذا كله إحنا أخذناه
في الشباتر القديمة فأنا همشي عنه بس وأركز فقط على
الجديد فهذا همشي عنه تمام؟
طبعًا إيش بقصد هنا ملاحظة بال notational
conventions هنا الكتاب بيحاول يكتب بطريقة تساعد
القارئ يفهم القصة تابعة ال grammar يعني مثلًا لما
بكتب لك الكتاب bold غامق أي شيء فمعناه بيقصد أن هو
هذا ال terminal لما مثلًا بكتب Italic مائل معناه
بيفهمك أن هذا بيقصد فيه في الكتاب أن هذا non
terminal بعمل شوية notations وشوية رموز عشان نفهم
إيش الـ .. الـ .. المكتوب في الكتاب يعني مرات مثلًا
بيقول ال start symbol هو عبارة عن S فلو أنت شفت
مثلًا في ال grammar S معناه بدك تفهم أنه بيقصد فيها
start symbol وهكذا طيب أنا همشي عن ال notations
لأن هذه بس مجرد شغلة أنه كيف نقرأ ونفهم الـ ..
الرموز اللي موجودة في الكتاب على سبيل المثال لو
عندي مثلًا Alpha إيش يعني ال alpha؟ ال alpha هذه
عبارة عن خليط من ال grammar symbol يعني خليط من ال
terminals والـ non terminals فوقت ما بده يقول إنه
أنا عندي خليط من ال terminals والـ non terminals
بحط إشارة مثلًا alpha وهنا في ال notation بشرح هذا
الكلام بيقول ال alpha معناها كذا مثلًا لما يجي
مثلًا يحط لك A capital بيقصد فيها مثلًا non terminal
وهو هذا ذاكره شرحه في ال notations فهذه مش حفظ
الشغلة لكن كيف إحنا نتعامل مع الرموز في الكتاب عشان
نستوعب الأمثلة بتاعته بشكل سليم طيب نيجي على موضوع
ال derivations بالنسبة لل derivations برضه شبيه
جداً بموضوع عملية ال parsing وأن أطلع ال tree لكن
بطريقة شوية مش بطريقة رسم بطريقة رياضية خليني أشوف
كيف يعني مثلًا لو أنا عندي هذا ال grammar خليني
أكبرهتمام؟ تمام وبدنا نعمل مثلًا إيه؟ وبدنا نعمل
مثلًا ID زائد ID مثلًا زمان كنا بال tree نقول خلاص
ال E عبارة عن E زائد ال E والـ E ID والـ E ID فكنا
نعمل derive لـ letter E اليوم لا في صيغة ثانية إيش
بقول صيغة بنكتبها بدون رسم باجي بقول الـ E derives
السهم زي هيك derives E زائد E فهنا إيش بنقول هذا
derives طبعًا طيب الآن بدي أكمل وبعدين إيش بسوي
بعمل كمان سهم ورا مثلًا الآن مين أغير؟ أغير اللي على
الشمال ولا أغير اللي على اليمين؟ جال على حسب ال
derivations إحنا إيش شغالين؟ لو إحنا شغالين
leftmost derivations بيصير أغير في الأول مين؟ اللي
على الشمال لو إحنا شغالين rightmost derivations
بيصير أغير مين؟ اللي على اليمين، الآن نفترض أننا
شغالين leftmost عشانك إيش هنصير نقول؟ ال E
هتمستبدل بـ ID زائد E، لاحظوا خطوة خطوة جايت باش
تتغلو بعدك إيش هنقول؟ ID زائد ID طب أنا إيش سويت في
المكان هذا؟ أنا عملت derivations لل sentence من ال
start symbol E من خلال عملية derivations طب إيش
يختلف عن هذا؟ ما يختلفش شيء الاثنين واحد ال tree وال
derivations equivalent واحد هنا بس على شكل
graph إنه كيف ال E طلع ID هنا ال E في الأول تستبدل
بـ E زائد E بعدين ال E تديني ID بعدين ال E تديني ID
هنا على شكل ال graph بينما هنا شغال على شكل معادلة
أن ال E derives لمن؟ derives لمن؟ derives لمن؟
لغاية ما أوصل لل sentence طالما طلعت ال sentence
معناها هذه موجودة في ال language على طول زي هيك
بس هي كل قصة ال derivations ما بدها شيء يعني فاللي
عارف ال tree على طول ال derivations تحصيل حاصل طيب
الآن همشي عن ال derivations أنا ما فيش في شيء أكمل
طبعًا هذه وبيشرح هنا ال parse tree وال
derivations هذه بديكم مثال زي اللي شرحناه قبل
شوية لو بدنا نعمل مثلًا ناقص id زائد id هنا اشتغل
عليها على شكل إيش؟ على شكل ال tree ما بدها شيء لو
بدنا نعمل derivation سهل جدًا في ال derivation
هنقول ال E بتعطيني ناقص E بعدين derives ال E بتصير
تتحولها وبنسيب نمشي من الشمال لليمين زي ما قلت
قبل شوية وهيها هنا بورينيشايفين كيف مع بعض؟ هي
شايفين؟ قال ال E أول شيء بتطلع ناقص E طبعًا لاحظوا
أنه ممكن أرسم رسمها ممكن أكتبها زي هيك خلاص E
derives ناقص E الاثنين صح سواء بدي أكتبها هيك أو
أرسمها هيك الاثنين صح لأن زي ما قلنا ال tree وال
derivations equivalent بس هذا شكل ال graph وهذا
شكل المعادلة طبعًا لاحظوا أن طب كيف بدي أكمل ال
derivations أكيد ال E هذه بدي أستبدلها بإيش
أستبدلها عشان أطلع ال sentence اللي جابني شوية بدي
أستبدلها بين جثتين E فشايفين كيف عملها؟ خلاص هو فضل
هنا في المثال أنه يخلط الاثنين مع بعض أنه يعمل ال
derivations مع الـ tree لكن أنا زي ما قلت مش ملزم
أعمل زي هيك يعني إذا أنا بدي أعمل هذا المثال اللي
هو جاله هاي مثلاً خليني امسح
يعني لو بدنا نعمل هذا اللي هو ناقص ID زائد ID خلاص
إيش بسوي بقول الـ E بتعطيني إيش minus E بعدين بكمل
بغير الـ E إيش بتعطيني هيها طبعاً أنا بشتغل من ال
grammar اللي شوفته قبل شوية بقول عبارة عن بين جثين
E بعدين إيش بسوي E زائد E بعدين إيش بسوي هي الناقص
زي ما هو هذه الـ ID بغيرها بعدين آخر شيء إيش بسوي ناقص
ID زائد ID هيك أنا عملت إيش derivations بس هناك هو
فضل إيش يعملها خطوة خطوة على شكل Tree عمل Tree لهذه
عمل Tree لهذه عمل Tree لهذه عمل Tree لهذه لما طلع
النتيجة كله صح سواء عملنا هيك سواء عملنا هيك أو
سواء رسمنا الـ tree زي زمان كله صح ومافيش فيه
مشاكل لأنهم زي ما قلنا equivalent والمعلومة اللي
بتديها الأساسية أن الـ sentence بتطلع من الـ non
terminal ولا لأ سواء عملت parsing ولا derivation
خلصت القصة إذا طلعت الـ sentence من الـ non terminal
سواء بالـ tree أو بالـ derivation معناه هي في ال
language معناه مافيش مشاكل ما طلعت معناه فيها
مشاكل، هاي باختصار طيب الـ ambiguity .. إيش تعرف ال
ambiguity؟ الـ ambiguity أخدناها زمان إيش كنا نقول
لو عندي اثنين tree لنفس الـ sentence معناه
ambiguous طيب بلغة الـ derivations إيش ال
ambiguous؟ بلغة الـ derivation لو عندي اثنين
leftmost derivation لنفس الـ sentence معناه
ambiguous أو إذا عندك اثنين rightmost derivation
لنفس الـ sentence معناه ambiguous لكن غلط أقول
اثنين derivation لنفس الـ sentence أنت كل sentence
لها اثنين derivation مرة بستبدل من الشمال اللي هو
leftmost ومرة بستخدم من اليمين اللي هو rightmost
إذا غلط أقول اثنين derivation لكن لازم الكلام يكون
واضح بتكون ambiguous إذا إلها اثنين leftmost
derivation لنفس الـ sentence أو اثنين rightmost
derivation لازم نحدد زي هذا المثال هنا أشتغل على
rightmost من الـ grammar اللي قبل شوية قال لي الـ ID
زائد الـ ID ضرب الـ ID كيف بدنا نطلعها؟ لاحظوا أنها
حلّين الحل الأول E drive E زائد E استبدل الـ E لأنه
بشتغل leftmost استبدل الـ E بـ ID بعدين الـ E الثاني
استبدلها بـ E ضرب E طبعاً ما استبدلش من جيبته رجع
على الـ grammar اللي موجود قبل شوية وشرح فبعدين
استبدل الـ E بـ ID واستبدل الـ E هد بـ ID فطلعت الـ ID
زائد ID ضرب ID الآن عمل most leftmost derivation
ثانية استبدل الـ E بـ E ضارب E، بعدين خلّى ..
شايفين؟ الـ E هاد استبدالها الأولى بـ E زائد E
وخلّى الـ E هادي، بعدين استبدل بـ ID، استبدل بـ
ID، واستبدل بـ ID، إذا التنتين sentence هدول طلعوا
من اثنين leftmost derivation مختلفين، إذا هذا
ambiguous تمام طيب
خلّيني .. هذا الـ section مش مشكلة أربعة اثنين ستة
بناشي إياه خلّيني أدخل على أربعة اثنين سبعة أربعة
اثنين سبعة إيش بقول فيه؟ بقول context-free grammar
versus regular expression وهنا في معلومة مهمة لازم
نعرفها أن كل regular expression بقدر أعمله
بالـ grammar لكن مش كل الـ grammar بقدر أعمله بال
regular expression ليش؟ لأن الـ grammar أعم وأشمل
من الـ regular expression الـ regular expression
شوية ضيق خلينا نقول محدود بينما الـ grammar
powerful أكثر وأكبر وبالتالي كل شيء بنعمل بال
regular expression بنعمل بالـ grammar لكن العكس مش
صحيح طب ندي مثال ونشوف كيف الآن احنا بنعرف أن كل
regular expression ما لها .. زي هذه مثلاً طبعاً .. هذه
طبعاً اللي هي regular expression بتوريني .. طبعاً
إيش الـ language بتوصفها هاي؟ كل الكلمات اللي من A
أو B لكن تنتهي بـ ABB هذا regular expression، الآن
كيف أنا بقدر أسويها كـ grammar؟ قال الخطوة الأولى لازم
تجيب الـ NFA تبعته احنا أخذنا الشبطر السابق كيف
نحول من regular expression لـ NFA إذا الخطوة الأولى
لازم نجيب الـ NFA طبعاً تعلمنا قبل هيك أن كل
regular expression له NFA وبالتالي هذه هنحولها
لإنقاف A من باب التذكير احنا أخذنا أول إنقاف A
لهذا المثال في بداية الشابط السابق كانت أظن إنك لو
zero كانت A هنا لف و B هنا لف وأظن إن هنا كانت A
بتروح لـ 1 تمام؟ وعندنا بعدين كانت B وإننا كمان
لاثنين وإننا آخر شيء كانت بتروح لتلاتة طبعاً هذه يا
بنات أخذناها قبل هيك اللي هي NFA لـ regular هذا
يعني أنا عشان أحول regular لـ grammar أول خطوة بدي
أحول الـ regular لـ NFA طيب حولت لـ NFA الآن إيش
أعمل؟ قال الموضوع simple خالص قال كل دائرة في هدول
تمثل non terminal الدائرة zero هي non terminal A
zero الدائرة واحد non terminal A واحد الدائرة
اثنين non terminal A اثنين الدائرة تلاتة A تلاتة
طيب إيش هسوي في كل واحدة فيهم؟ تعالي تطلع الدائرة
الأولى الدارة الأولى عند A1 بتروح بتبقى على نفسها صح
ولا لأ فكيف عمل هذا الـ edge في الرسمة تطلعوا إيش
قال قال a في a node يعني عند الـ input بيبقى ضال في
a node طيب هل في input ثاني في الدويرة الأولى اه
في input ثاني اللي هو b طب إيش عمل وبتروح عند b
بتروح على نفسها فراح يسوي بي a node شايفين كيف طب
هل في input اه في كمان input a بيروح على واحد عشان
ايه إيش سوى قال a a واحد وبهيك عمل إيش ل
production الأولاني تحت الدائرة الأولى الآن بنفس
الفكرة الدائرة اللي وراها اللي اسمها A1 إيش فيها
اسم إنبوت مافيش غير الـ B وبتروح على A2 مظبوطة لا
لأ فراح يسوي قال خلاص عند الـ B بتروح على A2 ما كملش
ليش؟ لأن مافيش إنبوت ثاني لو في إنبوت ثاني كان سجله
زي ما سجل في الـ A node طيب الآن تعالي A2 إيش فيها
برضه فيها إنبوت وحيد إيش هو؟ إنه لو أجه B بيروح على
تلاتة فإيش بيقول لي BA3 باختصار طيب A تلاتة مافيش
فيها ولا link مافيش فيها ولا N بتروح عليها مكان
فإيش سوى A تلاتة؟ Epsilon الآن إيش اللي اِطلع
معايا هذا؟ هذا عبارة عن Grammar الـ language تبعته
كل الكلمات اللي من A وB وتختم بـ ABB اللي هي نفس
الوصف تاع Regular Expression وبهيك أنا حولت من
Regular Expression لمين؟ للـ Grammar على طول ببساطة
بس لازم أروح لمين؟ للـ NFA في الطريق تمام؟ طيب
نكمل طبعاً هنا بيشرح الـ rules اللي قلتها قبل شوية
في الرسمة ندخل
على الـ section اللي ورا أربعة تلاتة اللي هو
writing a grammar طبعاً هنا بيسأل سؤال مهم lexical
vs syntax analysis طبعاً هنا بقول في هذا subsection
ليش احنا فصلنا الـ lexical عن الـ syntax طالما أن كل
regular expression أنا بعمله بالـ grammar يعني واحد
بسأل بقول طالما أنت regular بنعمل بالـ grammar طب
ما خلاص كده أنا عملت الـ grammar لكله وخليته م stage
واحدة وما نفصلش طبعاً لأ احنا ليش فصلنا احنا قلنا
زمان أن عملية الفصل بتخلّي الـ code تبقى more
efficient ليش؟ لأن لما بقسم الـ problem لـ sub
problems بيصير أسهل عملية الـ coding أسهل عملية
البرمجة بيصير more efficient فالآن أنا ضروري يكون
في عندي شغل للـ lexical كمان قلنا المرة اللي فاتت
أو زمان قلنا عشان كمان الـ portability على أساس أنا
كل الـ languages تقريباً الـ tokens تبعتهم واحدة
وبالتالي أنا بقدر أعمل Lexical للغة معينة أستفيد
منه في الـ languages الأخرى لكن لو أنا سيرت خالطه
كله مع الـ grammar بدي أسير في كل language أعيد كل
الشغل وهذا الكلام تكلمنا عنه مسبقاً لكن كمان في
فوائد ثانية الآن احنا قلنا قبل شوية أن الـ grammar
powerful أكثر من الـ lexical وبالتالي أنا مش محتاج
أستخدم هذه القدرة الكبيرة عشان أقدر أنا أوصف ال
regular expression ولا أوصف الـ tokens يعني بفعل
بسيط أفرض أنا بدي أطلع مشوار خارج الجامعة أو اتصلت
على شركة السيارات أطلع خارج الجامعة اروحوا مثلاً
يبعثوا لي bus اللي هو powerful وأكبر وأكثر طب إيش
بدي في الـ bus أنا في النهاية صح بيوصلني لكن أنا بدي
الشيء اللي على الجد علشان يكون أسرع ويكون أفضل ويكون
أحسن عشان هيك احنا بنقول لأ خلاص الـ grammar
يستخدم للـ language وللـ syntax تبع الـ language ول
الوصف تبع الـ language بينما الـ regular expression
خلاص مناسب جدا لطبيعة ال token وعشان أقدر أعمله
بشكل efficient وعشان أقدر أبرمج بشكل systematic
زي ما اتعلمنا و عملنا ال tool في ال chapter السابق
طبعا في كتير زي ما قلنا، ذاكر هنا أسباب عديدة أنه
ليش أنا أفصل؟ ليش أعمل regular و أعمل expression
هذه مجرد قراءة، ممكن إيش نقرأها و نشوفها هنا، و أنا
طبعا توأ أجملتهم و أتكلمت عنهم، طيب
بالنسبة لاربع تلاتة eliminating ambiguous، هذه مش
مشكلة، خلينا نسيبها الآن
خلّيني أشرحها، مش مشية، خلّيني أشرحها، مش مشية، الأهم
في، أنا عندي هنا
grammar، فبيسألني هذا ال grammar ambiguous ولا مش
ambiguous، احنا من شغل زمان بنعرف اذا في عندى tree
لنفس ال two trees لنفس ال sentence هتقوله على طول
انها ambiguous، الان هذه ambiguous grammar، الاثبات
وينه؟ ان أنا اللي عندى ال two trees، هايهم، هايهم
هايهم للـ F للsentence هذه، if expression then if
expression then if statement is statement، في عندى
اتنين trees مختلفات لنفس ال sentence، يعني من ال
grammar بتطلع هذه، ومن ال grammar بتطلع هذه، طبعا
احنا أخدنا قبل هيك هذا الكلام بشكل مفصل، عشان هيك
أنا مستعجل فيه، المهم أنه هاد الآن طالما إلها اتنين
trees لنفس ال sentence، على طول ال grammar اللي
جابلي شوية ambiguous، طيب إيش بيطلب مننا الكتاب؟
بيقول طب كيف نصلح هذا ال grammar و نخليه بطل
ambiguous؟ طبعا عشان نقرر و نصلح، بدي أنتبه لشغلة
مهمة مين؟ الرسم اللي في التنتين أصح؟ طبعا الرسمة
الأصح في التنتين اللي هي الرسمة هذه، ليش؟ احنا
بنعرف من زمان دائما ان القلص بتتبع لآخر F بتشوفها
في البرمجة وبالتالي هذه القلص لو جينا نسأل لمين
بتتبع للـ F هاي ولا للـ F هاي؟ هتقوللي في ال tree
هاي القلص هذه بتتبع للـ F هذه، يبقى مافيش عندي
مشاكل، لكن لو جينا نتطلع على الرسمة اللي تحتو جينا
نسألك القلص الليهانبتتبع للـ F هاي ولا للـ F هاي؟
طبعا الكل هيجاوب ويقول الإلس بتتبع للـ F هاي لأنها
يبقى في الشجرة هذه لحالة بتطلع من ال statement، طيب
هنا في مشكلة، أنت مكتوب عندك F وموجود عند الإلس
الإلس ماتبعتش الأقرب، تبعت الأبعد، طيب و هذا خطأ و
بالتالي هذه letter غلط، غلط أني أعمل grammar يطلعها
فلازم ال grammar تبعي يطلقلي حاجة زي هيك، لازم
نتقيد دائماإن ال else تتبع أقرب F عليها مش ال F
البعيدة، وبالتالي لازم نصلح هذا ال grammar، طبعا
الفكرة كانت في عملية التصحيح تبع هذا ال grammar
كيف؟ عمل حاجة اسمها matched statement، إيش ال
matched statement؟ خلي بس نكبر شوية، طيب
ال match statement ماتش بقول if expression then
match statement else عندي statement، انتبهوا الشرط
انه ال else هاي و ال if هاي، عشان هذه تتبع هاي لازم
جوا يكون ال if مع ال else معانا عشان تصير هذه صح
عارفين لو هذه ماكنتش F else وكانت F صارت الجملة
غلط، ليش؟ لأن في الحالة هذه ال else بتتبع للـ F هي،
مابتتبعش ده الـ F هي، طب عشان هذه المشكلة ما تصيرش،
إيش المطلوب؟ المطلوب إنه مايجيش بين ال F و ال else
إلا F مع else تبعتها، الان انا عندى F وعندى L ممنوع
في النص يجى F لحال، لأن لو اجت F لحال للأسف ال L
هذه مش هتتبع إلها وهذا غلط، طب إيش الحال؟ قال ضروري
جدا أنه إذا أجى في النص إشي بين ال F و ال L
الرئيسيات تيجي ال F مع ال L تبعتها و بهيك مكون
مافيش مشاكل، ليش؟ لأن ال L هذه تبعت لل F هذه و
بيصير منطقيا ال L الكبيرة تبعت لل F الكبيرة، فهذا
الشرط الرئيسي أنه ممنوعبين ال if وال else ييجي if
لحاله، لازم ييجي if else عشان هيك سماها matched، طيب
السؤال طب بعد ال else، ماذا هو الشرط بعد ال else؟
قال مش مشكلة، بعد ال else، بعد ال else تيجي if لحال
بمشي الحال، تيجي if else بمشي الحال، وعشان مايصيرش
ambiguous عملها مرتين، قال هنا match statement
بينما هنا تطلعوا في اللي تحت في ال open، نفس الجملة
هي اللي فوق هي موجودة تحت، لكن في الآخر ايش عمل؟
open statement، شايفين؟ لأنه لو عمل هذه match زيها
و هذه match زيها هتصير ambiguous، هتصير هذه و هذه
مرتين بقدر أجيبهم، ولو عمل هذه open و هذه open
بتصير برضه ambiguous، اللي بتصير بقدر أخد الحل هذا
و الحل هذا عشان مايصيرش ambiguous جالك خلاص واحدة
في النهاية match و واحدة في النهاية open، يعني مش
فارقة معاه بعد ال else إيش يجي يجي كده ولا يجي كده
مش فارقة معاه، لكن اللي فارق معاه في الحالتينطلعوا
بين ال F و ال S ممنوع يجي إلا matched، بين ال F و
ال S ممنوع يجي إلا matched، هذه باختصار، طيب واحد
هيقول طب أنا يمكن مايجيش F else بالمرة، بنقوله صحيح
كلامك معناه أنت ال statement هي open و ال open
خلاص F expression ده ال statement و خلصنا مافيش
مشاكل، لكن احنا المشكلة تبعتنا لو كان في else هنا
لازم واحد ياخد باله ان ال if و ال else عشان يصيروا
صح في النص ماتيجيش if لحالها و لازم يجي ال else مع
بعض عشان تصير العملية كلها صح، لكن بعد ال else مش
فارقة معايا ييجي matched ولا ييجي open مش فارقة
معايا و لو من البداية مابدي if و else خلاص بدي if
لحالها مافيش مشكلة، فالاهم ال statement هي نوعين
open عادية بدون if else و ال match اللي هي ال if
else ضمن الشروط اللي اتكلمنا عنها، طيب آخر section
بدنا نشرحه اليوم اللي هو eliminating لل lift
recursion، طبعا البعض هيقول لي طب احنا أخدنا كيف
نشيل ال lift recursion قبل هيك، طبعا
أخدناها قبل هيك وهي بس بدي أكتب .. أورجيكوا
القانون
لو أنا عندي ال a بالصورة هذه a alpha أو beta، قلنا
زمان إيش هنسوي، خلاص هناخد ال beta اللي مافيش فيها
المشكلة a عبارة عن beta في a bar وبعدين نسيب نقول
ال a bar هذه عبارة عن إيش، نخب اللي فيها المشكلة و
نقول alpha في a bar أو epsilon، فهذا already احنا
خدناها، طب هو ليش مذكور الدرس هذا هنا كمان مرة؟ لأن
أحيانا ممكن يكون ال left recursion مخبأ، كيف يعني
مخبأ؟ يعني أجي أقول مثلا ال A بتعطيني B زائد L، و
أجي أقول مثلا ال B بتعطيني
مثلا a زائد w، لاحظوا في left recursion مخبأ، ليش؟
لأن لو أنا شيلت ال b و عوضت عنه بقيمة ال a هيصير
ال a في الأول و ال a في الأول فبصير في عندي مشكلة
بصير في عندي left recursion، طب شو الحل؟ كيف نشتغل؟
كيف نحل؟ جال بدنا نصير انعوض، طب اعوض مين مكان مين و
لا .. و لا .. بصدفة اشتغل و لا كيف نسوي، تعالي ناخد
مثال و نشوف كيف عملت التعويض بالظبط، بدها تصير على
هذا المثال، طالع
معاك و هل دائما اعود و لا مش دائما اعود و لا كيف
القصة بدها تصير بالظبط، جالك أول حاجة بالنسبة
للتعويضممنوع اتعود اللي فوق تحت، ايش بتعود؟ يعني
مثلا أنا بادي في ال S، ال S فيها A صح؟ طب ال A
متجاية، ال A جاية لسه بعد شوية، جاية في المستقبل مش
هعود، خلاص غلط، تيجي من تحت تتعود فوق خلاص تشتغل S
بتتطلع فيها عادي زي ما كنا نتطلع زمان مافيش lift
recursion، خلاص بقوله مافيش lift recursion انتهتلكن
تعالى لما تجى تشتغل على A، ال A فيها S اه، طب ال S
بينت معاى قبل شوية فوق هنا، إجبارى لازم ال S تعوض
فيها، طالما ظهرت قبلي لازم أخدها أعوض فيها، لكن إش
بيجينى بعدى بعوضش فيه، فعشان هيك أنا ماعوضتش ال A
في ال S لأن ال A جاية بعد ال S لكن هنا عوضت ال S
في ال A لأن ال S كانت قبلى، أنا بهمنى موضوع الترتيب
إذا كيف هنشتغل هان؟ طبعا هنا لاحظوا ان ال lift
recursion مخبأ، ليش مخبأ؟ لأنه لو اتعودت ال S جوا
هيظهر كمان A في البداية فبدك تنتبه للقصة هذه، طب
كيف هنعوض؟ كيف هتصير الجملة؟ هتصير زي هيك، A A C أو
تمام؟ الآن عوض عن ال S، هناعندي عبارة عن ايش؟ ا ا
شايفين أو بيه دي كلها الاس يعني جيبتها كلها و بدى
اضربها في مين؟ في دي و اضيف ال epsilon، الان هد ايش
بتصير هد؟ فاكفكوها عبارة عن a a c أو a a d شايفين؟
أو B,D أو Epsilon، الان خلاص صارت بالنسبة لنا سهل ان
نشيل ال left recursion زي ما كنا نعمل زمان، واضح ال
production هي ايه، هنا left recursion و هنا فيه
left recursion و هنا مافيش و هنا مافيش، فخلاص الان
هتشتغلوها ضمن القوانين اللي اتعلمناها قبل هيك، بس
كانت ال trick الجديدة أو كانت الإضافة الجديدة في
هذا الدارس مين أعوض مكان مين بس كانت ال trick
الجديدة أو الشيء الغائب زمان أنه ممكن يكون ال left
recursion مخبأ زي هذا المثال أنا لما تعوضت اكتشفت
أنه في left recursion زمان ما كنتش أعوض عشان هيك
بدك تنتبهي أنه كيف عملية التعويض بتتم عشان أنا
أقول في left recursion ولا لأ؟ طبعًا في ناس شاطرين
مرات بيقولوا ما فيش داعي للتعويض يعني كيف شاطرين
يعني مثلًا خليني أمسح اللي كتبته أنا يعني لو فرضنا
جدلًا أنه أنا كاتب هنا زائد A A زائد ففي ناس
بيقولوا طب أنا ليش أعوض عن ال S طالما هي بتبدأ
بزائد وبتبدأش ب A يعني الفاضي صح؟ لو عوضت مش غلط
لكن التعويض مش هيجيب لي left recursion يعني هيجيب لي
جملة عادية فالشاطرين إيش بيقولوا؟ بيقولوا ما فيش داعي
للتعويض لأنه لو حتى عوضت ال A مش هتظهر في الأول لأن
هي مش في الأول في ناس شاطرين قبل ما يعوضوا بيفكروا
هل التعويض ممكن يجيب ال left recursion ولا مش ممكن؟
إذا كان التعويض بيجيب ال left recursion لازم أعوض
ولازم أشيله لو كان التعويض بيجيبش ال left
recursion أنت مخيّر عوضتي صح ما عوضتيش صح لكن ليش
تضيعي وقت طالما بيجيبش ال left recursion بس
والنقطة الثانية الرئيسية اللي قلنا عنها قبل شوية
ممنوع أعوض اللي تحت فوق لازم اللي فوق بتعود تحت
يعني مثلًا لو أنا عندي في ال A في عندي X و ال X
كانت ورايا وبتبدأ ب A ممنوع أعوض في ال X طب إذا ال
X كانت فوق وبتبدأ بال A آه بعوض بال X فانتبهوا
للترتيب زي ما بدأنا ال S ما كانتش شايفة ال A فما عوضتش
لكن لما كنت في ال A كنت already شايف ال S فروح
اتعوضت فالصح دائمًا أنه لما يكون في اشتباه ل left
recursion مخبأ بنعوض وبعد ما نخلص التعويض إذا في
left recursion بنشيله زي ما تعلمنا في الشابتر
السابقة من ال left recursion وبهيك يعطيكم الصحة
والعافية هيك خلصنا إن شاء الله والمرة القادمة إن
شاء الله نستكمل في ال lift factoring والسكاشن
القادم إن شاء الله يعطيكم الصحة والعافية السلام
عليكم