بسم الله الرحمن الرحيم اليوم إن شاء الله بدنا
نستكمل في 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 زي إيش مثلا يعني واحد كاتب ifx تساوي y طبعا
هو بيقصد هنا يعمل مقارنة بين x و y لكن هو نسي يكتب
ال double equals فراح كتب x تساوي y فعليا هي ك
syntax مظبوطة فعليا أيش اللي هيصير؟في الـ language
هتنحط قيمة الـ Y في X أو إذا كانت هذه القيمة مش
صفر هيعتبرها true وينفذ لكن إذا كانت صفر هيعتبرها
false وينفذ فهيك لما تحط X تساوي Y لكن لما نحط X
تساوي تساوي Yهيقارن قيمة X بقيمة Y فإذا كانوا
متساويين بيروح على طول بفوت جوا ال F مش متساويين
بفوتش وبالتالي لو أنا كمبرمج انسيت المساواة للأسف
البرنامج هيقوللي مافيش أخطاء مافي أي خطأ أو هي
بالفعل 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 لغاية ما يوصل
لنقطة بداية جديدة لكن في الستراتيجية التانية
بيرميش ولا إشي بيحاول على طول ما بيلاقي الغلط
بيحاول يكتشف شو هو الغلط بيحاول يفهم أه كان ناقص
ghost لأ زيت ghost فبيحاول يصلح الخطأ في المكان
تبعه ويعرفه عشان يكون عنده القدرة يكمل من نفس
المكان ومايرميش أي حاجة طبعا هذه بتاخد 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 المطلوب أغير characterين مثلاالـ 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 والـ EID والـ EID فكنا
نعمل 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 طب إيش
أختلف عن هذا؟ مختلفش إشي الاتنين واحد ال three و
ال 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 على طول ببساطة
بس لازم أروح لمين؟ للأن أف إيه في الطريق تمام؟ طيب
نكمل طبعا هنا بيشرح ال 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 والسكاشن
القادم ان شاء الله يعطيكوا الصحة والعافية السلام
عليكم