بسم الله الرحمن الرحيم اليوم ان شاء الله سنستكمل
الدارس السابق ان شاء الله اليوم بدنا نبدأ في موضوع
ال lift factoring طبعا احنا قلنا قبل هيك لو بدي
اعمل predictive parser لازم في شروط تكون متوفرة في
هذا ال grammar حتى استطيع ان اعمل predictive
parserطبعا ال predictive parser ليش أنا مهتم فيه
لأنه more efficient parser فكان الشروط إيش الشروط
اللي كانت؟ ممكن تتذكريه؟ مايكونش فيه left
recursion ومايكونش فيه بداية مكررة ومايكونش
ambiguous كمان طبعا بالنسبة لل left recursion
حالها كان سهل بالنسبة لنا بنعمل إعادةصياغة لل
grammar استخدام القوانين اللي اتعلمناها علشان أشيل
ال left recursion بنفس الطريقة لما بكون في عندي
بداية مكررة في algorithm بيعلمني كيف أعيد شكله
صياغة ليس مضمونة صياغة بحيث أني أحصل على grammar
بشكل آخر لا يوجد فيه بداية مكررة وبالتالي بيصير
فيها اندي إمكانية ان اش أعمل predictive parser
فهنا بديكي مثال زي ما انت شايفها if expression
then statement else statement if expression then
statement هنا بتقدر تعمل predictive parser حسب
معلوماتك السابقة لأ ليش لأنه في F هنا و في F هناو
انت ال look ahead واقف على F طب مين اختار؟فكنا
بنقول زمان انت مضطرة لل backtracking كنا بنقول
زمان بدك تاخد الجربي الأولى match .. match ..
match .. match .. match .. match .. match .. match
.. match .. match .. match .. match .. match ..
match .. match .. match .. match .. match .. match
.. match .. match .. match .. match .. match ..
match .. match .. match .. match .. match .. match
.. match .. match .. match .. match .. match ..
match .. match .. match
.. match .. match .. match .. match .. match ..
match .. match .. match .. match .. match .. match
.. match .. match .. match .. match .. match ..
match .. match .. match .. match .. match .. match
.. match ..
خلاص بتقول Erot إلا إذا كان فيه خيار تالت بيبدأ ب
F تجاربيه هذا اللي كنا نقوله زمان لكن زي ما انت
شايف هبضيع وقته ليش؟ لأنه صار ماشي و راجع و ماشي و
راجع صار لأ الحل التاني اللي هو بنصح فيه أنه أعيد
صياغةال algorithm او اعيد صياغة ال grammar نفسه
بحيث ما اشوفش البداية المكررة يعني انغيره شكلا مش
مضمونا يعني ايش equivalent له لكن مافيش فيه بداية
مكررة وبالتالي بعمله ايش a predictive parser طبعا
كيف ال algorithm او كيف القوانين اللي بتغيره شكلا
و بتشيل البداية المكررة هي نرقم نشوفها اشي simple
خالص مش صعببقولك على فرض أن هذا الشكل اللي عندي
إيه بتعطيني alpha beta one و هذا production تاني
alpha beta two لو جيت تتطلع هتقولي ال alpha هان
وال alpha هان ما لهم بيعملوا نفس البداية صح ولا لأ
هتقوليني أنا مابقدرش أعمل left recursion لأ
مابقدرش أعمل predicted parser لهذا ليش لأنه نفس
البداية هان و هان صح ولا لأ اتطلعي كيف أعاد
الصياغةالقانون ماذا يقول؟ بيقول ببساطة خُدي A خُدي
المشترك مش هاد ال alpha هي المشترك بين الإتنين مش
هاد البداية المشتركة أكتبيها زي ما هي و ضربيها في
A bar خلاص أخدت المشترك و ضربته في إيش؟ في A bar
عارفين يا بنات لو في هنا gamma oneGamma 2 هكمل
ايش؟ Gamma 1 عادي مش هيتأثروا البقية انا بس
المعالجة تبعتي كانت وين؟ في اللي فيها البداية
المكررة فانا سحبت ال alpha اللي هي المشتركة وضربت
في A bar الان شو ال A bar؟ قالك ارجعيلهم خبي ال
alpha ايش ضال؟ Beta 1 او Beta 2يعني بالعربي كأنه
أخدهم عامل مشترك، كأنه أخد ال alpha عامل مشترك
لبرا، إيش ضال جوا؟Beta 1 أو Beta 2 التي هي الـ A
bar هكذا احنا غيرنا شكله لكن ليس مضمونه لأن لو جيت
تطلع على ال grammar الجديد مافيش فيه بداية مكررة
خلاص بتعمل فانكشن A بتعمل فانكشن A bar وبتشتغل
وبتعمل ال predicted bar تبعك هذه القصة باختصار
يعني الموضوع simple خالص مافيش فيه اشي تعالوا ناخد
مثال تعالوا
ناخد مثالطبعاً قبل المثال برضه in general اعمل
القانون in
general زي ما تشايفها ايش بقول في القانون ان ال a
على هذا الشكل alpha beta one alpha beta two alpha
beta n يعني كتير متكررةوفي غيرها مش متكرر مافيش
فيها مشاكل قال القانون التابعي الجديد الـA عبارة
عن خد المشترك وضربه في A bar خلصنا or مين اللي
مافيش فيهم مشاكل الآن عشان تحسب الـA bar ارجع للي
كان فيهم مشاكل خبيهم و اكتب باقية ال instructions
هاي باختصار قانون simple خالص سهل خالص طيب تعالوا
نطبقوا على هذا المثالونشوف كيف نحل الآن
هل بقدر أعمل predictive parser لهذا؟ لأن فيه بداية
مكررة IETS IETS عشان هي كيف شهر القانون بيقول؟
بيقول عادي A عبارة عن أو بلاش ايه، خلّيني أسميها
أيش زي ما نفس الاسم، إيش الاسم؟ S S عبارة عن أيش؟
أول إيش بتاخد؟ مين العامل المشترك؟ اللي هم مين؟ IE
,T,S ونضربهم في مين؟ في أسبار أو اللي مافيه مشاكل
إذا الأسبار عبارة عن إيش؟ خدي خبي هذا أشدل منه
إبسلون خبي هذا أشدل منه خلاص يعني ES إبسلون مش
مشكلة الترتيبيعني واحدة خب منهما دول وضلت ال
epsilon وواحدة خب منهما دول المشترك وضلت ال yes
الآن إيش صار عندي؟ صار عندي grammar جديد مافيش فيه
بداية مكررة بالتالي بنقدر نعمل اللي هو ال
predictive parser okay ليه المشاكل؟ طبعا مرة في
الامتحانات سألنا سؤال شوية يعنيخطوة .. هذا هتحلوه
في ال exercises المطلوب كتبنا عظمي I E كيف
تتسوي؟ هل ناخد ال I E لحال؟ و لا ناخد ال I ETS في
الأول و بعدين نعمل ال I E؟
العموم الحالين .. الحالين صح .. خلينا نشوف حال
منهموانت جربت تاني في البيت واحد أسهل من التاني
على كل حوال خلينا ناخد الأطول خلينا نجرب ناخد
الأطول لو أخدنا الأطول إيش بيصير I E T S مظبوط
مضرب فيه .. هنوصل ل conclusion للأسهل I E T S
هتضربي في إيش أسبار أسبار أسبار مظبوط او ايه او
ايش عندك لسه اما انت أخدت هذههذه اسمها يخد الـS
الجارب أيش؟ جارب الـI اسهل، جارب الـI، مش مشكلة
على أساس ما تضطريش اللي فوق تعمليها، هو ننصح، ننصح
سنحاول نوصل لـS، خد الـIE تمام، الـIE هتدور بيها،
في أسبار or A الأسبار عبارة عن أيش؟ تشيلينها، TS
أو
TS VS TS أو إبسلون إبسلون مش هيك؟ خلاص الآن هتيجي
تعيدي نفس الفكرة همش هحلو كامل exercise هو سؤال
هتيجي تعتبريه كأنه سؤال جديد وفي TS بداية مكررة و
بتبدأ تعيدي بتصير الأسبار هتطلعلك أسبار بار و
بتحليه أسبار عبارة عن TS في أسبار بارأو إبسلون و
ال أس بار بار عبارة عن إيش؟ إيش ضال؟ إبسلون أو بي
أس بي أس، خلصنا، خلصنا، عادي دائما خدي من باب
السهولة الأقصر و شوية شوية حتتعاد أكتر من ال
iteration عملها تخلصي المهم في كل أحوال أنت صيرتي
تكتبي ال grammar تاني بدون ما يكون فيه بداية مكرمة
تمام لحد هنا؟كمل؟ في أي مشاكل؟
طبعا خلاص، دلوقت بقال subsection اتكلم عنه على
السريع انا مستهل، مش مشكلة طيب،
الان اش بقول هنا في هذا ال subsection الأخير، بقول
في شغلاتnon-context-free grammar إيش يعني؟ يعني في
شغلات موجودة في ال language لا يمكن وصفها بال
grammar اللي أنا أعرفه عشان أتعلمنا ال context
-free grammar اللي هو عبارة عن productions و non
-terminal و اللي أخدناها هذا الكلام فهل السؤال هل
كل الأشكال الموجودة في ال language نستطيع وصفها
بال grammar اللي احنا عارفينه؟جال لأ مش الكل في
أحيانا بعض الشغلات اللي مابنقدرش نصفها بال context
-free grammar وتحتاج إلى معالجة خاصة من خلال ال
rules و ال semantic أو translators زي إيش مثلا
أديكي مثال ال function ال function كيف بنعملها
استدعاء في المين؟مش عبارة عن ID فاصلة ال
parameters اللي هي list فاصلة ID لما تخلصي ID
فاصلة أجد ما بدك، صح؟ طيب، أيش يعرفني إن اللي أنا
عملته هان مطابق لل declaration اللي في البداية؟ مش
أنا أعمل declaration لهذه ال function اللي اسمها
كذاتاخد خمسة parameters مثلا افرض في الكل حتى تلتة
parameters هي ك semantic .. ك syntactic صح .. ك
syntax مظبوط ID فتحت جوس list of identifiers أو
list of parameters سكر جوس خلصنا سؤال لأ لكن كيف
نعرف أن عددهم مطابق للعدد اللي فوق للأسف لا نستطيع
ذلك بال grammar لوحدهطب إيش الحل؟ لازم يكون فيه
action لازم يكون فيه rules اللي تشيك و تشوف ال ..
مش قولنا مش تشوف ال .. بتيجي من رحلة ال rules اللي
بيشوف ال types و بيشوف النوع اسم array اسم
function إيش معرف قدرة براميتراته يعني بده يصير
إشي أكتر لكن ك grammar لحال مابيجيبهاش واضحة؟ مثال
تاني غير ال functions ال identifiersأنا ممكن أقول
x تساوي y زائد z كسينتاكس هيطلعلي id تساوي id ساعد
id مش هيك كسينتاكس هتطلعليه و هيقوللي كسينتاكس
سليمة لكن يمكن أنا ال y هذا ماله مش عامله
declaration مش معرفه ال grammar بيقدرش يعرف طب كيف
بنعرف من خلال ال semantic rulesهل هذه الـ Y موجودة
في الـ Symbol Table؟ مش موجودة، طبعاش معرفة، مش ..
مش قولنا زي هيك، بيصير يبحث، لكن ك grammar لحال
مابيجيبش تطابق بين ال declaration سواء ال
identifiers مع ال identifiers المستخدمات أو في
مثال آخر، عدد ال parameters في ال functions مع ال
parameters اللي انت كتبتيهم في الاستدعاء مافيش
grammar بيقدر تطلعلي هذا الكلام عشان هيك إيش بنقول
non context free grammar بده معالجة تانية، هاي
باختصارماشي الحال اكتر من المثالين هدول مابدناش
okay اكتر من المثالين هدول مابدناش فاك انت ممكن
ييجي على بالك اكتر من المثال نفس الفكرة حاجة اتعرف
في مكان و بديها في مكان تاني و ك syntax سليمة و
هناك كsyntax سليمة كيف بدي اعرف؟ ال grammar لحاله
مفيدنيش okay طيب
خلونا هنكمل ال subsection الجديد
طيب طبعا بالنسبة للsubsection الجديد هذا المفروض
أنه أنا ماشرحش فيه إش كتير ليش؟ ليش؟ ليش؟ لأنكوا
أخدتوه أخدتوه و خلصوه بدون .. أركز على الأشي المهم
أنا بس بدي أحاول ع السريع أمشي عنه طبعا
يا بنات عملية ال bar sinkالها شكلين احنا اتعلمنا و
بنشتغل على شكل لكن سيبنا الشكل التاني مش هنشتغل
عليه الشكل اللي اتعلمناه اللي هو ال top-down يعني
ببدأ انا من ال road بسيرأعمل الشجرة لغاية ما أوصل
مثلا خمسة زائد اتنين و هكذا فهذه الطريقة ما نسميها
top-down لكن بالتأكيد في طريقة عكسية بتبدأ من ال
sentence المكتوبة يعني ببدأ من واحد زائد اتنين
زائد تلاتة و بعدين من وين طلعت هذي طلعت من factor
هذي من وين طلعت .. و تصير ايش؟من تحت تمشي لغاية ما
تخلص عند ال route نسميها بوتوبأب لكن البوتوبأب مش
داخل المعنى مش هنشرحه احنا بس مركزين على طريقة ال
top-down طبعا في طريقة ال top-down شايفين هذا ال
grammar هذا ال grammar أخدتوه ولا لا قبل هيك؟
أخدناها هذا كان بصورته السليمة اللي هي E عبارة عن
E زائد termأو E لأقصر تهرب تهرب تهرب في factor على
factor فاكترو ID وده خير ايه لكن ايش عمل فيه هو
هنا شال ال lift recursion عشان يهيئه لل predictive
process بس مش اكتر و هاد الكلام زيجنا منه واخدناه
تمام بس انا بدأ امشي عنه بسرعة طبعا هاد عبارة عن
ايش بالنسبة ل ID زائد ID ضرب ID كيف نطلعها من هذا
ال grammar معقول اليوم مابتقدروش تطلعوليمن هذا ال
grammar كيف نعمل id زائد id ضرب id انتوا الأصل لو
أنا بجيبلكوا grammar لأول مرة زي ما في الامتحانات
صار و بجيبلكوا sentence و بقولوا طلعيلي parsing
المفروض انتوا تعرفوا فمبالغ هذا اللي ازهجنا منه
لكن مش مشكلة يمكن احنا ماعملنهاش قبل هيك لكن كليني
أبدحيها كيف
نطلع id زائد id ضرب idأيش هتقوليلي؟ هتقوليلي ببدأ
من ال root E صح؟ الحرف ال E مالها .. مالهاش إلا
production واحد يعني، مافيش شيء فهتقوليلي هذا
عبارة عن إيش؟ T E bar طيب ال T هاي باش نستبدلها؟
أنا بدي أطلع ال ID ال T مش هتستبدليها انتي
هتقوليلي F T bar F T barالـ F عشان هتستبدل إيها؟
اجري ID عشان أخلص من الأول ID الـ I نخلصت هاي بس
لكن لسه ضالة ليها زائد اما نشوف هذا كله term هو،
تنسيش أن هذا term اتضارب وال expression زائد تعالي
لل T bar ال T bar عبارة عن إيش؟ عبارة عنإبسلون و
لا ضرب أف تي بار؟ إبسلون إبسلون
إبسلون إبسلون إبسلون إبسلون إبسلون إبسلون
إبسلون
لكن هي مش ضاربة، إذا الآن نرجع لمين نكمل؟ E bar بس
قبل ما أروح أكمل كلغة ال derivations إحنا إيش
سوينا؟ هتقوليلي أول إيش استبدالت ال E بإيش؟ ب T E
bar، صح؟ أول step عشان هي
استبدلنا ال E بـ F T E Bar بعدين إيش عملنا؟
استبدلنا من اليمين للي شمال، من الشمال للييمين،
from left to most استبدلنا ال T بإيش؟ F T Bar
شايفة؟ F T Bar المهم إن هو أنا قاعد أعملك الشجرة
step by step أنا مهم ليش هذا، المهم بس عشان تفهم و
تدوس إيش اللي صار إنه قاعد step by step أعملك
الشجرة أنا قاعد يشغلي عليها إيش أنا؟ مرة واحدة،
تمام؟ خلاص خليني رجع نكمل، الآن ال E برعن إيش؟
plus T E bar الآن ال plus هيه الآن يا شجاق ال T ال
T بتطلق اللي المفروض F T bar فلنشوف اين ال T F T
bar F
F T bar فش هذا و ال F بتطلق I D و ال T bar ضرب F
الـ T bar والـ F ID والـ T bar إبسلون والـ E bar
إبسلون وخلصت يعني سهل أن نطلع الشجرة تبعتنا بدون
مشاكلوزي ما تشايفين الكتاب بس عمل .. عملها على شكل
derivation steps مش هناخدها المرة فات derivation
ان كل step بورجينيها فالكتاب هيومشي كل خطوات
شايفين خطوة step by step كيف تطلع لما وصل في
النهاية لمين الشجرة الأخيرة تبعي
في أي سؤال حد هتكمل؟
طبعا الدارس هذا برضه ال recursion ماله أخدناه اللي
هو recursive descent parsing احنا اتفقنا زمان انه
ممكن اعمل عملية ال parsing من خلال استخدام
functions تستدئي نفسها وهي كلها نشتغلها حتى الآن
متعلمنها شغل طريقة ال recursionالصحونة لأ عشان هيك
بتذكرني بطريقة ال recursion الأن لو أنا عملت طريقة
ال recursion بدون ال backtracking أصبح predictive
parsing أصبح more efficient لكن اللي بال
backtracking و اللي بدون backtracking اللي
أتعلمناهم هم إيش recursive decent parsing هنتعلم
خلال هذا ال chapter المحاضرة الجاية non recursive
decent parsing يعني حاجة بتشتغل بدون recursion
المرة الجاية أما اليوم بدي أشرجها شوية شغلاتالمهم
طريقة ال recursion كلنا عارفينها إيش .. إيش .. إيش
هي عبارة عن إيش أن كل non-terminal إيه و إيهاش،
function، مظبوط أو لأ؟ بتضيف عليهم ال matchوفي كل
function إيش بتسوي؟ if else أو switch فبس قاعد
بقولك هذا الكلام كيف أنتي بتعمليه إن كلنا تمأله
function وكل function عبارة عن إيش؟ if else حسب ال
productions اللي عندك قالوا بيشرحوا في ال
recursion وهذا شرحناه زمان مابدوش إعادة بالنسبالنا
بنكمل وهنا أعطى مثال أعطى مثال وهذا المثال أعطانا
إياهو لحظة طب قولولي في هذا ال grammar الموجود
بقدر أعمله predictive parser؟ بقدر او لأ؟
predictive parser طبعا هتقولولي لا يمكن أعمله
predictive parser ليش؟ لأن البداية هنا مالها مكررة
إذا أنا بدي أحول ال grammar سيما خدنا بالقانون
بظبطبس هو هنا في المثال هذا جال ماتحاوليش كيف نعمل
كودنا وقعد يشرح عملية ال code كيف جال على فرض انه
مكتوب ال sentence CAD وعلى فرض ال look ahead واقف
على ال C وعلى فرض ان انت بدأتي من S ايش هيصير؟
طبعا عملية ال tree كيف هتصير؟ اكيد ال C عبارة عن
ايش؟ ايش هتعمل ال C؟ match .. match ايش؟مش أنت ال
function S عبارة عن match C؟ إيش match C بتسوي؟
بيخلي أنا يمشي وين؟ على A و بيخلينا نستدعي مين؟ ال
A ال function A، الآن المفروض أنت كنت تعمل .. كنت
متوقع زمان أن مايكونش فيه بداية مكررة و if A خلاص
كنت تخلصي، صح أو لأ؟ اليوم ال look هيتواجف على A و
فيه خيارين ببدو في A إيش هتسوي عاد أنت في الحالة
هذه؟ هتمسكي الخيار الأول و تمشي عليه، خلاصهتقولي
خلاص بدنا نستبدل ال a كشجرة ب what ب a b يعني
match a match b هيك هتسوي بس هتحفظ المكان اللي كان
في ال lookahead ليش؟ لأنه في خيار تاني يمكن هو
اللي يكون صح أي تغييرات بسيطة بتعملها في ال codec
عشان هيك إيش هنقول match a هيصير هذا وين يمشي على
دي وهذا وين راح يعني ما اللي match b
مختلفين إذا بيعرف إنه الخيار اللي اختاره إيش مش
مظبوط عشان هيك إيش هيصير؟ هيرجعله كhead تاني ومش
هيختار الآن هادي هيريد إيش يختار ال إيه؟ a small
الحالة التالية الآن إيش هيقول؟ match A إيش بيصير؟
وين بيروح هذا؟ عادي، الآن بعد ما بيخلص ال function
A وين بيرجع؟ على match Dمش طبعا بصدق ايه؟ بروح و
بعد ما بخلص برجع ع دى؟ إيش برجع ع دى بقوله ماشي؟
بقوله ماتش دى؟ هلّك هدى؟ أه خلاص خلصت و ماشي مافيش
مشاكل لإنه أنا كاتب كد في ال language بس إيش اللي
اتغير معاكي؟ إنه إنت لما شفت فيها أكتر من خيار صار
في عندك شوية احتياط إنه بتجرب الأولى إذا زبطت
هينظلنا ماشيين و خلصنا مازبطتش بقولش error زي
الزمانبجرب التاني إذا زبطت ما زبطتش خلاص error
لاني جربت الخيارات فهذا
with backtracking طيب انت في غناء ان ذلك يعني لو
انت بدك تحلي من الأساس كويس ايش هتسوي بتشيلي ال
left recursion بتاعة a يعني فيش بتقولي a عبارة عن
ايش a a bar مظبوط و ال a bar
B خد ال A عامل مشترك خد ال A .. بحكي ال function A
حد ما فيش فيها مشاكل فوق A A bar B خلاص و بتعمل
هذه ال function و هذه ال function تشتغل عادي خلاص
بيصير سهلة عادي اشيلنا lift trick اي lift .. عملنا
lift fact اشيلنا lift ده المقاررة صار في و عندي
شكل grammar جديد و عملت predict بارزر بظبط بدل ما
أروح و أرجعماشي الحال طيب
لحد هل في أي أحد مش فاهم؟ هذا كل مراجعة لحد تقامي
اشرحتش اشي جديد هذا مراجعة هذا
.. هذا .. هذا درس تمام خليني أشوفه تفاصيل
ال first و ال follow طبعا ال first و ال follow درس
كتير أنا بسأل عنه في الانتحانات دايما مافيش انتحان
يخلو من درس ال first و ال follow و لو كنتوا
ملاحقينه كمان في ال med لأ أخدتهوا من ال med بس
للأسف ماكناش ملاحقينه في النصفين فأكيد هذا جاي جاي
في النهاية ان شاء الله و مش صعب بس بتكونوا تبهوله
مار علينا ال first قبل هيك؟ حد متذكر مار علينا ال
first قبل هيك؟
بداية حد متذكر بالزمان حكينا عن ال first و لا
ماحكيناش بالمرة حكينا كويس هاي في ناس يقولوا حكينا
متذكرين متى حكينا و إيش حكينا و وين حكينا؟ ايوة
أيام ما كنا نختار في ال predictive parser مش كنا
نختار احناال production؟ على أي أساس كنت تختار ال
production؟ على البدايات لما كنا زمان نقول ال
statement ساهم for ال statement ساهم if ال
statement ساهم while ليش كنت تختار ال for؟ لأنه
كان ال look ahead four و كنت تطلع على بدايات ال
productions صح ولا لأ؟ و أياميها كنت أقولك
البدايات هذه مهمة جدا بس زمان كانت البدايات واضحة،
باينةلكن مش بالضرورة في الإجرامارات اللي بدك
تشتغلي لها بدك تبارثر أن تكون البداية مبينة يعني
أديكي مثال يعني مثلا لو أجينا عملنا زمان كنا نقول
حاجة ا سائد افتح post أو ضربS لما أجي أسألك إيش
بدايات الـA إيش هتقوليلي أنت بدايات الـA يا زائد
يا ضرب فكنت تعملي if else يعني إذا ال look ahead
على زائد كنت إيش بتسوي انت بتختاري لهذا ال
production إذا ال look ahead ضرب كنت تختاري هذا ال
production فكانت البدايات تتطلعيلها عشان تعرفي مين
ال production بتختاريه مش كان ال look ahead واقف
على fourليش اخترت ال production التالت تاع four؟
لأن هو اللي بيبدأ ب four مكان F كنت بتختار أي
production اللي بيبدأ ب F يعني دي دايما تتطلع على
بدايات ال production عشان تعرفي مين البداية
المتطابقة مع ال look ahead و تختاريها مش هيك؟ طيب
افترض ال A كانت زي هيك S بال S عبارة عن زائد L
الآن هنا، معاك خبر إن الزائد هو من بدايات الـA،
ليش؟ لأن الـS ممكن تستبدليها بزائد وتصير الزائد،
لكن هذا ماكانش واضح وصريح زي فوق، زي زمان، عشان
هيك أنا مطلوب مني أعرف بدايات هذا، ليش؟ عشان لما
يكون look at زائدأقول آه والله الزائد من بدايات ال
production high معناه لازم أختار ال a تجلب لمين لل
production high طب افترضي كان look ahead ضرب آه
والله الضرب مش من بدايات ال production high يبقى
مستحيل أستبدل ال a في هذا ال production إذا مافيش
production تاني بتطلب في بداياته ضرب أنا هقرر
مابقدرش من a أجيب الضربشوفت كيف؟ فأصبحت البدايات
مهمة جدا أن تكون عارفة بدايات ال production زمان
كانت واضحة وصريحة فماكنتش تتعبى خلاص فتطلع على طول
الذائب موجود أو مش موجود الدرب موجود أو مش موجود
اليوم صار مخبأ يعني بلزمك حسابات كيف أحسب ال first
كيف أحسب ال follow عشان أقدر أعمل كودي بدون مشاكل
ووضعت أهمية ال first الآن بده يبدأ الكتاب يعلمككيف
نحسبهم؟ كيف بالظبط ال first بنحسب؟ بس قبل يعرفته
أهمية حساباته عشان يساعدني في كتابة أي quote طيب
تعالى نشوف قوانين ال first طبعا
في عندي first وفي عندي follow ال first هو البداية
ال follow هو الذي يتبع كل من terminal إله first
وإله followيعني هذا ال non-terminal بمين بيبدأ؟
مين ومين ومين؟ وهذا ال non-terminal مين بيجي وراه؟
مين ومين ومين؟ فبيهمني القراءتين هدول أني أعرف ال
first و أعرف ال follow تمام؟ تعالوا نشوف كيف ال
first من حسب هذه
أول قانون إيش بقولك؟if .. إيش مركزين؟ و الله تمام؟
حاسسكوا شويه مبسوطين؟ طيب
if x is a terminal then first ال x هو x يعني first
الزائد
إيش يساوي؟ firstالـ four ايش يساوي؟ four مش
تقوليلي اف .. four ما .. مية المية إذا كان
terminal هو بداية نفسه على طول ال terminal هو
بداية نفسه مش في مشاكل ال terminal خليني في
التالتة قبل التانية if xتعطيني epsilon then add
epsilon to the first x أيش معناها؟ يعني لو ال a
بتعطيني مثلا زائد ال أو epsilon و جيت سألتك شو
بدايات a هتقوليلي بدايات a الزائد وال epsilon لأن
أش بقولك القانون الأخير إذا ال x بتطلع epsilonالـ
Epsilon في الـ First على طول بس برضه انتبهي أيضا
لو الـ A بتعطيني الـ M و الـ L بتعطيني Epsilon و
الـ M بتعطيني Epsilon هذه نفسها A بتعطيني Epsilon
مش هذه الـ L قد تكون Epsilonوهذا ال M قد تكون
إبسلون يعني التنتين فراغ يعني برضه ال A بتعطيني
إبسلون فمش بالضرورة تشوفيها بشكل مباشر ممكن
تشوفيها indirect يعني بيجي يقولك ال A بتعطيني XYZ
و ال X فيها إبسلون و ال Y فيها إبسلون و ال Z فيها
إبسلون يعني خلاص صارت الإبسلون تضعف لل A يعني
فاهمت؟ سواء بشكل مباشر أو بدون شكل مباشرهذه
قانونين اللي حتى الآن في ال first تعالوا الأهم
واحد و بتحاولوا أنتوا تفسوليا هذا اجرولي الكلام
اجرولي point two و قولولي شو معناها اجرولي
point two و قولولي شو معناها النقطة
اتنين ايش معناها
أه مين فين معناها؟ نقطة 2 يعني
كيف؟ عشان كيف؟ يعني إيش بالظبط؟ يعني الآن لو هذه
Y1 إيش .. إيش .. إيش دخلها في ال first؟ما هو بداية
ال X هتكون نفس بداية ال Y1 يعني أنت بتحسب بداية ال
Y1 عشان تعرفي بداية ال X طيب كويس بس ولا في معلومة
تانية؟
إذا كان إيش؟ إذا كان فيها إبسلون ننقل عالي وراها
كيف ننقل عالي وراها؟ يعني لو كان Y1 إبسلون هنجيب
بداية Y2 طيب واش في كمان معلومة أخرى؟ إذا كلهم
عادل Y1 وY2 وY3 وYK كلهم فيهم إبسلونات هضيف إبسلون
في المجموعة طيب تعالوا الممتازين تعالوا نشوف إيش
اللي جالوا هنا جال عشان أحسب first X ببساطة بدي
أجيب first Y1إذا حسبت first y1 هو هحطه كل وين في
first x يعني افترض ال y1 كانت زائد هتقول إيه ليه؟
first ال x هي ال first z هي زائد و خلصنا و وقفنا
انتهت لكن هو ايش بقول كمان كقانون بقول افترض ال y
كان من بدايتها يعني كانت non terminal ال yوكان
فيها زائد وكان فيها ناقص طبعا هضيف الزائد والناقص
على ال X وكام من بداية يعني ايه؟ عشان تستخدمي
First Y1 افترضي كانت زائد ناقص Epsilon على طول
حضرتك هتيجي تقولي First ال X تساوي الزائد والناقص
ال Epsilon بتعوض عنها ايش هم بتعوض عنها؟ يعني ممكن
Y1 تكون فراغةصح؟ في الحالة دي إيش حضرتك هتسوي؟
هتحسبي فرستات ال Y2 واضفيهم على مين؟ على المجموعة
بتاعة X طب إفض ال Y2 كان فيها إبسلون، هضيفي على ال
X فرستات Y3، فيها إبسلون، هضلي ماشية، طب كلهم
صاروا فيهم إبسلون، بتضيفي في الآخر خالص إبسلون
اختصاري طيب افترضي كان فيه في النص زائد هل وارد
يكون في ال first X, Y؟ لأ مستحيل ليش؟ لأن لو هذه
فيها إبسه و هذه فيها إبسه و هذه فيها إبسه في الآخر
هيوصل لزائد خلاص تضاف الزائد و بتجفف مافيش مجال
تتكمل لأن هتطلب شكل صريح terminal لكن لو كان non
terminal و ممكن يكون إبسه و بيصير يكملتنتبهي للقصة
هذه بعدين القصة يا بنات منطقية جدا انا بدايات ال X
شوفهم ما بدايات ال Y إذا ال Y ممكن تكون فراغ
بدايات ال Y2 كمان إذا ممكن تكون فراغ بدايات ال Y3
كمان طب مافيش فيها فراغ خلاص وقفنا كيف بدي أروح
لللي ورايا لأنه مابنفعش لما أقول X عبارة عن زائد
ضرب مابنفعش أقول بدايات ال X زائد وضرب بس بدايات
ال X زائد بس ممنوع أروح للضربشوفتي كيف؟ لكن لو كان
حاطط ليه هنا S و الـ S عبارة عن زائد أو إبسلون أه
إيش بدايات ال S؟ زائد أو إبسلون؟ وبالتالي بدايات
ال X هو الزائد و عوضة عن الإبسلون و هو الضرب بيصير
في الحالة هذه لأن أنت اشتغلت على بداية ال S فبداية
ال S زائد و إبسلون فنحط الزائد لمين؟ لل X و عوضنا
عن إبسلون هنا و نضعف عليه لمين؟الضرب فانت تنتبي
طبيعة السؤال واضحة كماشي و احنا هناخد أنثى على ده
الكلام بس انا بيهمن ال rules طيب أي
سؤال لحد الآن طيب
خلونا نشوف ال follow إيش
بقصد بال follow
والفولو له تلات قوانين اول
قانون طبعا هي واحد اتنين تلاتة نشوف شو هم بالظبط
اول قانون جال عشان احسبالـ follow تبع ال start
symbol أول إشي بديك تحطيه في المجموعة ال dollar
sign إيش بال dollar sign؟ ال end marker كيف يعني؟
يعني الآن يا بنات لما أنا بدي أفحص أي جملة، أي
sentenceفي الـ language .. أصلا مش في الـ language
مش مرات بحط أنا إشارة نهاية للإشي اللي بده فحص
عشان أقول إنه أنا خلاص بدي تفحصلي هذا ال code اللي
نهايته عنده file أو تفحصلي هذا ال sentence اللي
نهاية دولار sign مش هيكله لأ فالآن افترض ال start
symbol S مش ال S هو اللي بيطلع كل الشجرة هاي إيش
بيتبع ال S دائما؟ إيش بيجي ورا ال S دائما؟
الـ End Marker علمت النهاية و خلصنا فجالي لما الحد
يطلب منك ال follow تاع ال start symbol بدون تفكير
هذا الرمز تاع النهاية بتحطه في مجموعة ال follow
تاع ال start symbol وبعدين تبدأ تشتغل واضحيت؟ طب
ليش هو بيحطه؟كمان مرة ..كمان مرة ..الان انا لما
بتعمل عملية parsing ل sentence او ل code او ل جملة
مش فيه لها نهاية عشان اقول انه خلصت ففي رمز يعبر
عن النهاية سواء نهاية جملة نهاية code و هذا رمز مش
بالضرورة يكون دولار ممكن يكون in the file ..المهم
اي رمز دي هي فانا في مثليجال اعتبر رمز النهاية
بتاع ال sentence اللي بتعملها ال parsing هي dollar
sign يعني اذا كنت كاتب واحد زائد اتنين زائد تلاتة
بتفحصها وراها ال dollar sign انت الان من اين هتبدأ
تشتغل عشان تشجري هذا؟ من ال root من ال start
symbol شو ال root هو؟ S صح؟ مش هاد هي S في النهاية
اللي بتتشجر و تطلع لنا ده الكلام؟ ايش بيجي بعد S
دايما؟Follow، ايش بيجي وراها؟ رمز النهاية دائما
بيكون بعد ال route اللي أنا فحصته صح ولا لا، دائما
و أبدا عشان ذلك قال كقانون أول كقانون أول حطوا ال
dollar sign في ال follow تبع ال start symbol ليش؟
لأنهم عارفين أن هذا ال start symbol يعمل الشجر
الكبير عشان يطلع ال sentence وعارفين أن ورا ال
sentence على طول يعني ورا ال route على طولالـ end
marker اللي هو في المثال هذا دولار فقال لي خلاص
هذا بتنحط في ال follow طب شو معنى ال follow يا
بنات ال follow S معناها ماذا يأتي بعد ال S شوف
انتبه يختلف عن ال first first S بماذا تبدأ Sfollow
S ما يتبع الـ S، إيش بيجي بعد الـ S، مين وراها الـ
S، لشو بتفيدني المعلومة بتفيدني، بعدين هنشوف هذا
الكلام، مش اليوم، أما بتفيدني ال follow، واضحة؟
طيب، فأول ملاحظة إنه دائما رمز النهاية بينحط في ال
follow بتاع ال start سمه، دائما، لازم يكون في رمز
نهاية في نهاية ال sentence أو في نهاية ال code
عشان يعرف إن أنا خلصته
طيب إيش رأيكوا في نقطة 2؟ و هي بتطلعها هيك و
أكبرها إيش رأيكم في نقطة 2؟ إيش
يعني نقطة 2؟ مين يشرحلنا إياها؟ هذه نقطة 2 إيش
معناها؟
في كل بداية ال action يعني راح تكون عند ال person
كلهم قاعدة فيكويس كويس تعالى نشوف انا بده احسب ال
follow بي انا بده احسب ال follow بي انا بده احسب
ال follow بي المنطق ايش بيقول ال follow بي هو نفسه
ال first beta فانت احسب ال first beta طبعا كل اللي
في ال first beta بيصير وين؟ في follow بي بس
باختصار لأنه بدايات ال beta هي اللي تأتي بعدالـ B
طيب إلا إبسلون يعني لو ال beta فيها إبسلون ممنوعة
تفريها في ال follow ها إيش هنسويه؟ عوض عنه تمام
عوض عن ال beta وبدأ افترض أن في ورا ال beta gamma
كام ليش هتسوي؟ و هتجيب فرصة الجامعة و تحطيها في ال
follow؟ ال betaوفترضي كمان فيها إيسرون وخلصت أيش
يعني خلصت يعني صارت ال B في الآخر جال كمان إذا ال
B في الآخر كل ال follow A بدي ينحط في ال follow B
هقول ليش كمان شوية بس خد ياها قانون إذا كانت ال B
في آخر ال A في الآخرأو مش في الآخر لكن هدول فيهم
كلهم إبسلونات يعني كائنها في الآخر بشكل غير مباشر
هضيف على مجموعة الـ follow B كل الـ follow A هقولك
ليش الآن هقولك ليش الآن وهذا هو القانون 3 اجري
القانون 3 الآن عشان نشرحه كيف أجاهر اجري قانون 3
اجري
قانون 3
إذا كانت الـ B بالآخر أو وراها شغلات كلهم فيهم
إبسلونات يعني بشكل مباشر في الآخر أو indirect في
الآخر كل الـ follow A بيصير في ال follow B أقولك
عاد ليش، تعالي أقولك ليش أقولك ليش القانون التالت
هذا موجود الآن
افترض الـ S في الشجرة طلعت A و وراها زائد في
الشجرة وجيت سألتك إيش بيجي بعد الـA؟ إيش هتجاوبي؟
هتقولي زائد، صح؟ لأنه بعد الـA بيجي زائد، الموضوع
لأ طب افترض الـA عبارة عن شغلات كتير، آخر الـA بيه
بيصير الزائد مش بس بعد الـA و ورا الـB عشان كل إشي
يتبع الـAيتبع الـ B بس هذا ما يحدث إلا إذا كانت
الـ B في آخر الـ A بس طبعا تكون أخرها بشكل صريح أو
أخرها بشكل مش صريح يعني إذا ال beta هذه فيها
epsilon بتعوض عن أسالة في الآخر عادل لو ال beta
مافيش فيها epsilon خلاص لأ ماعملش القانون ده أنا
بطلت مش في الآخر E مضحكت؟ في حد يسأل؟ الآن هناخد
أمثلة
هذه الثلاث قوانين تبعون ال follow خلونا
الآن نرجع ناخد مثال السؤال
اللي في الأول السؤال
إيش بيقولبنحسب ال first و ال follow لكل هدول، لل
grammar يلا
بدنا نشتغل ماشي السؤال احسب ال first و ال follow
لمين بنحسب ال first و ال follow هنا؟ لمن؟ لل E و
ال E bar و ال T و ال T bar و ال F نحسبلهم ال first
أتا و نحسبلهم ال follow بالدور لنبدأ بال firstيلا
first مين؟ ال E إيش هتساوي؟ الشطرين هيقولوا هي
first ال T يعني لازم حضرتك تحزمي في الأول لازم
تحزمي في الأول ال T عشان تعرفي تجاوبي طيب بأجل
الجواب بروح لمين؟ first ال T إيش تساوي؟ first ال F
مش هقدر أعرف إلا أحلعشان أقدر أجاوز، صح؟ الـ
F هتقوللي
فتح القوس او ID انت بوادي يا بنات ان لازم حضرتك
تكون يعرف فتح القوس أجا من أي production من هاد
ولا من هاد؟ من هادو لازم تكون عارفة ال ID هذا اللي
في ال verse أجد من أي production ليش؟ احنا بيقول
هذا الكلام افرض ال look-ahead واقف على فتحة جوس
معناها بديك تستبدل ال F من أي واحدة بهاي لو ال
look-ahead واقف على I دي بديك تستبدل بإيش؟ طب ال
look-ahead لا واقف على جوس ولا I دي مناقرة فاهمتي؟
هذا ال verse مهم لازم تكون عارفة كل واحدة من أي
production أجدشوفتي ليش؟ عشان تقدر في ال code
تشتغلي صح طيب، الآن طالما عرفت هذه إيش هتسوي انت؟
هزبوت،
وهذه إيش كمان؟ تمام؟ طيب، الآن خلصنا من الفرستات،
الان بتلاحظي في الفنات ال follow أول ما هنبدأ نقول
ال follow لمين؟ لإيه؟ قبل ما تفكري هتضيفي
ال dollar sign قبل أي تفكير ليش؟ لأن ال dollar
sign هي نهاية ال sentence أو الجملة أو ال marker
افترضناها طيب الآن كيبنا نشتغل كيبنا نعرف الفلو
إيه عشان تعرف الفلو إيه بدك تدوري وين في إيه هنا
هيا إيش بيجي براها على طول بقوله هذا إيشبدور كل إي
موجودة و إيش بيجي وراها طب جدلا خلاص هيك خلاص
مافيش غير إي واحدة صح؟ لكن افترضي كان ورا الإي N
ساعتها فرستات ال N بدوا يسيروا فلو الإي طب افترضي
كان في إبسلون في فرستات ال N و وراها في L هتكملي
المهم القوانين بتضل تكملي و تنتبه هذا مثال simple
لسههذه القصة طيب افترضي كان كله أبسلونات الـ
follow up هتصبح الـ E و لا تنسى القوانين الثلاثة
دعوني أكمل الآن الـ I الـ follow مين بدنا الـ E
bar كيف نشتغلها؟ وين في E bar؟ في الآخر، ايش
هنعمل؟فى الـ follow إي بار إذا هنحط هدول في الـ
follow إي بار إذا قلنا كده في الآخر فى قانون ماشي
بيقول ان كل الـ follow تعالى فى الـ follow إي بار
مش تقعد اثبتناها قبل شوية طب دوري وين فى إي بار
كمان follow إي بار follow إي بار نفسها فى نفسها
مافيش مشكلة مافيش إي بار تانية الامن فين نشتغل
follow
مين؟ تي، ايش الفلو تي؟ بتدور وين في تي؟ ايوة،
هتقولي فرس الإيبار تعالي ناخد فرس .. فرس الإيبار،
وينها؟ ماحليناهاش .. ماحليناهاش، ليش؟ طالعينا ليش؟
طيب، يلّا فرس الإيبار زائد أو أبسل إيبار؟ إيش فرس
الإيبار يا بنات؟ زائد أو ضرب أو إبسل فرس الإيبار
زائد .. لأ أو إبسل، ليش ضرب؟
و هذه كانت first الـ T bar ضرب نصينه هذولا كنا اه
اه اه اه اه اه اه اه اه اه اه اه اه اه اه اه اه اه
اه اه اه اه اه اه اه اه اه اه اه اه اه
اه اه
افي الـ follow T الـ follow E اللي هو الدولار
تسكيرة الcourse هل في T تالية؟ أه هيها إذا ال
first E bar كمان مرة في ال follow T ال first E bar
مين هم؟ الزائر حطيتها و ال epsilon بعوض عنها صارت
ال T في الآخر إذا كمان هضيف ال follow E barفى ال
follow T هى اللى حصلت فى الآخر follow E bar فى ال
T وين follow E bar الدولار هى المحتوطين خلاص هل فى
كمان T مافيش كمان T الأمنى من الحسب follow T bar
وين ال T bar فى الآخرfollow ال T في ال follow T
bar follow T زائد دولار goes هل في كمان T؟ T bar
أنا شغال؟ اه هي هي follow T bar في follow T bar
مافيش اشي جديد خلصنا اخر واحدة follow مين؟ F دوري
وين في F؟ هي هي first T bar ايش ال first T bar؟هذه
ضرب إبسلون عوض عنها صارت follow T في follow F
follow T زائد دولار تسكيب ال cost هل في كمان F؟ أه
هذه ال first T bar ايش هما؟ الضرب حطناه والإبسلون
عوض عنه إيش بيصير؟ في الآخر إذا ال follow كمان تاع
ال T bar في follow تاع ال Fوين ال flow بتاع ال T
bar؟ ال Z محتوط و ال ضرم هو لأ ممكن تكون تتغير عن
بعض بس لأنهم شبه بعض محتوطين لكن انت تنتبهي ممكن
هذا يكون في حد زيادة عن هذا فبديك تضيف كلهم
محتوطين خلصنا هل في كمان F؟ و هيك خلصنا تمام؟
واضحة الأمور؟ مش حسب ال flow E barدش حسبت إيش؟
كله بدنا نحسب .. كله ال .. كله بدنا نحسب السؤال
أحسب كل ال follows و كل ال first تام؟ كله طيب
واضحة ال first و ال follow؟ خدوا break دقيقتين
الآن في عندنا مصطلح ضروري نحاول نفهمه كويس اللي هو
الالونو كتير أسئلة في الامتحانات بتيجي على الالوان
.. هنيجي نقول أشيان الالألوان
هو .. بنات هدولة لو سمحتوا هو ال grammar اللي
بيكون جاهز حتى نقدر نعمل predictive parser يعني
ببساطة من كلمتين اللي حكيتهم أنا الشاطرة هتقول
معناها مايكونش ambiguas الشاطرة هتقول معناها
مايكونش philipter kirginالشهادة يا عزيزي مايكونش
فيه بداية مكررة، هي باختصار علشان هيك إذا لجأتي
التلت شغلات هدول، طبعا فيه rules، هيتكلم من خلال
rules، مش بس بالبرامج اللي أنا قلته، فيه rules
نشوفهم، نتطلع فيهم شكل دقيق، المهم أنه لو أنا
قلتلك هذا ال grammar افحصي ليه الألوان و لا مش
الألوان، اللعنة لجأتي فيه left recursion، على طول
قولي not الألوان because left recursion لجأتي فيه
بداية مكررة not الألوان لأنه فيه بداية مكررةعلى
طول ما تستنيش لجيتي شجرتين لنفس ال sentence يعني
ambiguous قوليلي مش قلق الألوان لأنه ambiguous
باختصار لكن للأسف أحيانا ممكن تطلع عليه مش مبين
فيه refrigerant مش مبين فيه بداية مكررة مش مبين
انه ambiguous لكن بيكونش قلق الألوان طب كيف أقدر
أعرف القوانين اللي بتعلمها الآن واحد اتنين تلاتة
هي اللي هتعرفكالقوانين بتتمد على حسابات ال first و
ال full اللي اتعلمناهم قبل شوية كيف تعالوا نشوف
التفاصيل و ناخد أمثلة على ده الكلام في الأول خلينا
نشوف ال rules هاي ال rules جال عشان أقول هذا ال
grammar الألوان والله مش الألوان في عندي تلاتة
rules واحد اتين تلاتة بدنا نشوف معناهه الأول ايش
معناه يا بنات؟إيش رايكوا بالأول إيش معناه؟
أه إيش معناه الأول؟
بالظبط طبعا التابع هو أنه هنا هو بيقولك على فرضية
أنه أنا عندي reproduction على هذا الشكل A بتعطيني
Alpha و بتعطيني Beta فإيش بيقولك الشقر أولاني أن
ال Alpha ماتطلعش كبداية A و ال Beta ماتطلعش كبداية
نفس ال A لأن إذا هذه طلعت و هذه طلعت نفس البداية
في مشكلةيعني طب أنا كيف أعرف؟ Galaxy احسب ال first
لهذا ال production زي ما اتعلمتي و احسب ال first
لهذا ال production زي ما اتعلمتي إذا كان في بينهم
تقاطع مانها مش الألوان، إيش يعني تقاطع؟ يعني موجود
مرتين، يعني البداية مرة هنا و مرة هنا، هذا مايكونش
الألوان، إذا مش متقطعين الألوان، يعني هذه أنا كيف
ممكن أعبر عنها بالمثال صغير، خليني أمسح هذا الكلام
يعني لو أنا كتبت مثلا A بتعطيني B, C أو D و ال B
بتعطيني A و ال D بتعطيني ضرب مفتاح و سكر ghost أو
A وسألتك هذا ال grammar الألوان ولا لا؟الشطرين
هيقولوا مش الألوان، ليش؟ لأن first ال
BC يساوي ايش first هدول؟ A و first ال D يساوي طب
انا هساوي حاجات تانية، فيها ضر و فيها ايه؟طالما
الـ A موجود هنا وهنا يعني انا هيك بقول first بي سي
تقاطع first دي
لا يساوي A لا يساوي five إذا it is not الألوان
لأنه لازم يكون التقاطع معله five مافيش تقاطع بنات
افهم أنا إيش اللي سويتهfirst بي سي يعني حسبة
بدايات مين طلع ايه و بدايات دي طلع فيها ايش ايه دي
ايه هي مش ايه ضارب الان تقاطع بدايات هي مع تقاطع
بدايات هي فيها ايه معناه ال a ممكن تطلع من هنا او
ممكن تطلع من هنا اذا مش الالوان لازم البدايات و
البدايات يكونوا مش زي بعضفهمتي كيف؟ يعني لو أنا
سألتك هذا الألوان ولا لأ، الموضوع تقولي مش
الألوان، ليش؟ يا بتجاوب بشكل Mathematical رياضي
أنه بداية هذا تقاطع بداية هذا يساوي something لا
يساوي five، it's not الألوان ما بدك تكتبي هذا
الشكل الرياضي، بدك تشرحي تقولي ال A بتطلع من
بدايات ال B وC وبتطلع كمان من بدايات ال D وC وC وC
وC وC وC وC وC وC وC وC وC وC وC وC وC وC وC وC وC
وC وC وCلكن هذا أسهل خلاص فريستات هدول و فريستات
هدول و فريستات هدول كلهم لازم يكونوا مش متقاطعين
لقيت تقاطع مش ال ال one وضحت؟ طيب خلوني أكمل
الأولش بقوللي at most one of alpha and beta can
derive the empty string أيش بقصود؟ يعني هل يجوز
نكتب A بتعطيني B, C أو إبسلون و ال B بتعطيني A أو
إبسلون و ال C بتعطيني ضرب جواس أو إبسلون هذا ال
grammar ال ال one و مش ال ال one مش ال ال one ليش؟
لأن ال ال إبسلون طلعت مرتين مرة مباشرو مرة بال بي
سي إيه؟ هاي ال بي ممكن تكون إبسلون و هاي ال سي
ممكن تكون إبسلون يعني ممكن إبسلون يكون طالع من هذا
ال production أو ممكن يكون طالع من هذا ال
production طالع من الإبسلون طلع مرتين ambiguous
معناها صاراش مش الألوان طبعا بنات ممكن يكون أنا
كاتب هنا NL و ال N حاطط فيها إبسلون و ال L حاطط
فيها إبسلون برضه الإبسلون بطلع من هنا و بطلع من
هنافي النهاية ممنوع الانسان يطلع أكتر من مرة سواء
بمباشر ولا غير مباشر وهذا اللي هو بيقوله في
القانون هنا at most one of alpha and beta واحد
منهم بس ليش اللي بيطلع ال empty string الأنش
بيقولك ركزي معايا ركزي لو ال a بتعطيني alpha
أو إبسلون هنا
إيش بقولك؟ ممنوع .. و هنشوف حاليش كمان شوية طالما
في إبسلون ممنوع ال follow تاع ال a و ال first تاع
ال a يتقاطع، ممنوع يعني لما بتلاقي إبسلون هنابتحسب
الـ first للـ A وبتحسب الـ follow للـ A اللي جاتي
عنصر موجود في الإتنين مش الألوان هذا اللي بقول
القانون التالت بس هذا ماتبتطلعيلهم إذا كان ال
epsilon موجود في A يعني لو ماكانش في epsilon
مابفحثش ال follow و ال first يعني أنا بفحث ال
follow و ال first مع بعض لهذا ال A بشرط أن تكون ال
epsilon طالعة من أحدهموهذا اللي هو بيقوله بشكل
واضح تقول إذا ال beta بتطلع ال epsilon مش هو هيك
كان عامل السؤال alpha or beta إذا ال beta بتطلع ال
epsilon بشكل مباشر أو بشكل غير مباشر المهم تطلع ال
epsilon من التنتين من واحدة طبعا لأنه لو ال
epsilon تطلع مرتين ما لأ ambiguous لكن إذا ال
epsilon تطلع مرة واحدة في فحص زيادة بدك تعمليه شو
هو follow و first ممنوع يتقطعاتقاطعوا .. هيك
القانون التالت بيقول اتقاطعوا مش على الألوان طب
السؤال ليش يعني الحركة هذه عاملها؟ الحين للي بدوا
يفهم راكزي معايا، لو مفهوحاش مش مشكلة، بس كويس
اللي بتفهميها الآن ده أسألك سؤال افترض ال look
-ahead عشان تستوعب القصة واقفة على فتحة جوس خلاص
ال look-ahead واقف على فتحة جوس و ال a هذه اللي
بدت تستبدلالـ first تبعها في فتح الجوس والـ follow
تبعها في فتح الجوس والـ a ممكن تستخدميها في
epsilon الآن لما اوصل لهذه الحالة فاندي خيارين،
صح؟ الخيار الأول ان افترض ان هذا هو البداية مش ال
بيجي بعدو استبدل ال A بال production لأن هو في
بداية ال A اللي بيطلعه مش هذا خيار الخيار التاني
طالما هو بيظهر في ال follow بيظهر في اللي ورايا ان
افترض ان هذا هو اللي جاي ورايا و بيستبدل ال A في
epsilon فهنا بيصير عمل ايه التحيير؟بيعرفش من الصح
في التنين هو السهق الجوس موجود مرتين مرة كبداية و
مرة كواحد بيجي ورايا طب أنا مش يعرفني يمكن يكون
بداية فالمفروض أستبدل ال production باللي طلعه لكن
إذا كان من اللي بيجي ورايا هذا الجوس معناه لازم
أستبدل ال A ماشي من ال epsilon لأن ال epsilon ممكن
تكون فراغ في الحالة هذه جال فقط في الحالة هذه ممكن
تكون في مشكلة و الحالة هذه لا تحدث إلا في حال وجود
الإبسلون، لأنه إذا لم يكن هناك إبسلون يجب أن يكون
هناك إبسلون وليس هناك إبسلون وليس هناك إبسلون وليس
هناك إبسلون
وليس هناك إبسل
فهمت كيف؟ في هذه القصة طيب مثال و نختم طيب
خلّيني في هذا المثال و نختم هل
ال
grammar اللي على اللوح الألوان
والله مش الألوان
طبعا لو جينا نتطلع على القوانين الأساسية مافيش
بداية مكررة، مافيش left recursion، مافيش أمبريغوس،
هيك في النظرة الأولى، فقوانين القديمة بتعرفنيش،
صح؟ الآن تعالوا نستخدم القوانين الجديدة أول واحدة،
أيش ديك تعمل يا حضرتك؟ بديك تجيبي first high
وfirst high ولازم مايتقطعوش، صح؟ first هذي كلها
إيش؟ I وfirst هذي كلها إيش؟ A، بتقطعوش، if granted
مافيش فيكي مشاكل في ناحية first hatتعالى فرستاتها
دى فرستها دى E و فرستها دى Epsilon مافيش فيه مشاكل
مافيش بداية مكررة و first high B فالفرستات مافيها
مشاكل الآن القانون التانى هل في Epsilon بطلع مرتين
هن لأ ولا واحد بطلع بطلع مرتين هن لأ بس واحد بطلع
لأن هذا terminal مش ننطلع ان انا اخاف فهمتك ايه؟
يبقى قانون الـ Epsilon إنه يطلع مرتين مش موجود،
ضال أخر قانون اللي هو مين ال production اللي يحتوي
على Epsilon، بدّى أحسبله ال first و ال follow،
أشوف هل متخطأ ولا لأ، هذا أحسبله ال first و ال
follow، لأنه مافيش شيء يطلع، بس التاني، المرشح
يكون فيه مشكلة، عشانك إيش دي تحسبيه؟ first مين
أسبار، إيش هي؟ E و Epsilon، وتحسبي مين؟follow
اسبار ايش ال follow اسبار؟ هي في الآخر يعني follow
الاس طب ايش follow الاس؟ هتحط ال dollar sign و ايش
follow الاس؟ الاسبار
اللي هم ال E و ال Epsilon بتعود عنها مش هيك؟ و ال
follow اس في ال follow اس، مظبوط؟ خلصت، في اس
تانية؟في الآخر follow أسبار جواتها مافي يا بنات مش
عايزة تحسب ال first و ال follow؟ طيب كيف حسبت ال
first و ال follow؟ ثاني بدي أحسنكوا كله و بعدين
نقارن تبعنا، خلاص؟ اعتبروه مثال على ال first و ال
follow يللا أزاي بقى بنشتغل first أس إيش first ال
أس؟ I و ال A ايش بقى بنشتغل في الأول؟ first مين؟
أسبار إيش هي؟
first بي الان بده مين؟ follow ابدي في ال follow
تبعت مين؟ ال S ال dollar sign فاصلة طبعا نحسب
تلاتة follow مين هم؟ أسبع أسبع تمام و مين الأخيرة؟
ايه؟ بتدور تعالي إيش بقولك يلّا ابدي في follow S
dollar sign ال S first الأسبار مين first الأسبار؟
ايه؟ اعوضيالـ Epsilon يعني صارت في الآخر فلو أس في
فلو أس ماتغيرتش في أس تاني هيرم ايش بتقول الفلو أس
بار لسه ماحسبتهاش في الفلو أس يعني أكيد أي حاجة
زيادة في الأس بار هترجع وين؟ على الأس لو حسبتها
كمان شوية في أس تانية مافيش شيء الأن نحسب مين؟ فلو
أس بار عشان أحسب الفلو أس بار هي في الآخر إذا
الفلو أس جوتها هي نفس الفلو أسطيب وين كمان الأسبار
موجودة؟ خلاص مافيش اللي هيعنى، مظبوط؟ هيك الفلو
أسبار خلصت و الفلو أس خلصت، إيش الفلو إيه؟ أس إيش؟
T الآن عشان أعرف أل ألوان و مش أل ألوان، أول شيء
الفيرستات هيهم، مافيش فيهم مشاكلكفرستات مايوجد
مشاكل .. كفرستات مايوجد مشاكل الأقل لأنه في إبسلون
هلاش نعمل؟ نطلع على first أسبار و follow أسبار شو
فيهم؟ فيهم تقاطع؟ follow أسبار و first أسبار
هتقولي تقاطع في ال E إذا نطق الألوان طب لو كانت
هذه زائدخلاص مش هفحص ال .. ال first و ال follow و
التقاطع هي بس بفحصها في عالة واحدة أنه بطلع
epsilon و هذا المشكلة أنه بيعمل ليه؟ أنه أخد هو
اللي ورايا و أنا اللي معاه، بس واضحة يا بنات؟
يعطيكوا العافية