باشى باسم الله الرحمن الرحيم السلام عليكم اليوم ان
شاء الله احنا عمليا خلصنا ال section أربعة تلاتة
اللي هو writing grammar وشوفنا المشاكل ال left
factoring و ال left recursion ووقفنا
على اللي هو بداية section أربعة أربعة اللي هو top
down parsing ال top down parsing اللي احنا شوفنا
أخدنا فكرة عنه قبل هيكة في الكلام اللي هنا في
section اتنينوالان احنا بنشوفه ان شاء الله بشكل
اكتر تفصيلا في بداية section 4.4 بيغطي الموضوع
التالي اللي هو recursive descent parsing recursive
descent parsing هو بالتحديد اللي شوفناه قبل
الحكاية اللي ماشوفناه هو predictive parsing و non
predictive parsing و error recovery during parsing
وهذا هو اللي ان شاء الله بتشوفه في المحاضرة هذه و
اللي بعدها احنا لو بدنا نيجي نعمل parsing
هو عنده string و ال string هذا يحتوي على
identifier مطموعة من الزائد مطموعة من identifier
مطموعة من الضارب مطموعة من identifier احنا لازم
نبدأ من ال start symbol و ال start symbol هو ال E
فبنيجي على ال E اذا انا انا بدأ اعمل derivation او
انا بدأ اعمل building ل ال parts tree انا بدأ
استبدل ال E بال body ال body production له ال E
وحدة بس ليه هذه من اللي فيها سواء لو انا بتعمل
derivation احط T E prime او بتعمل building tree و
اجي زي ما هو عامل اقول E و هاتي E prime صح هاي ال
first derivation ال second derivation باخد واحد من
ال ال non terminals باخد ال left most non terminal
left most هو Tو باستبدل و باستبدل و باستبدل و
باستبدل و باستبدل
و باستبدل و باستبدل و باستبدل و باستبدل و باستبدل
و باستبدل و باستبدل و بشايفين انتوا هنا ال T
استفدلها او يفرع منها FT prime فاما بنعمل افرح to
build ال tree او بس مجرد بنستبدل ال symbols ب
symbols في الآخر بطلع عندى ال path tree ال leaf
nodes تبعونها هم مطابقين لل inputهذا المقصود بالـ
parsing إما أنه derivation أو بناء الـ parse tree
ال parser هو اللي بده يعمل هذا الأمر سواء
derivation أو بناء ال parse tree فاحنا بنشوف كيف
هو بيتناول الأمر هذا okay at each step of a top
-down parse the key problem is of is that of
determining مين هي ال production يعني هنا عندي
الأمر سهل بسيط جدافي كل الأحوال كانت عندي كل non
terminal ال production واحدة فما كان عندي إشكالية
الإختيار ربما هنا ال F في عندي تنتين بس برضه مش ..
لكن في واقع ال grammar بيبقى في عندي الإختيار
إشكالية كبيرة فهي هذه ال main problem at each step
of the top down path لإن ماعندي مشكلة في أختار مين
ال non terminal اللي هستبدله وعروفة وانا مغمض ال
left mostبس هذا الـ non-terminal اللي بدى استبدله
بأي واحدة من ال production اللي استبعت وهو هذا
السؤال اه determining the production to be applied
for a non-terminal say ايه بدى استبدله once a
production is chosen the rest of the processing
consist of matching بعد هيك بيصير matching
بنسترجع اللي هو .. استذكر اللي شوفناها قبلها كان
في ال .. في ال .. في ال .. في ال recursive descent
عندي إيش؟ عندي لكل واحد من ال non-terminals فيه
إليه إيش procedure ال procedure هي دي recursive
يعني ممكن تستخدمي نفسك أو تستخدمي other procedures
تبع other non-terminals مظبوط؟ ببساطة شديدة أول
شغلاللي هي انه احنا اللي هي انه بده لل a تقلل ال a
بده يختار احدى ال productions تبعه منه choose an a
production هذه هي المشكلة الأساسية بس احنا ..لو
يعني كان اكثر من ال production من اي جوجل احنا
الان بدنا نتجهل هذه المشكلة بس عشان نفهم القالية
بعدين هنركز على المشكلة هذه how to deal with عملية
الاختيار هذهبس الآن عشان انا بس اذكركم بالقاليه
القاليه انه احنا اختار واحدة الواحدة هذه من ال
production تبعون ال a ال body تبعها هيحتوي على
مجموع من ال symbols اذا افترض ان ال a هذه هي عبارة
عن statement و ال form تبعها if expression then
هي بتحطها هنا افترض ان statement can have the form
if expression then statement else statement صح؟
اذا x1 هو هذا x2 x3 x4 x5 x6 تمام؟ بالننيجي بتقول
لي خد ال x هذي واحد و بعد تانيمن I بسوة واحد إلى
K، K اللي هي يجهد D صح؟ واحد، اتنين، تلاتة، اربع،
خمسة، ستة If XI زي ال X اللي أنت واقف عليه، X
واحدة لان إذا non-terminal، هل هو non-terminal I؟
ال I هنا يرمز لإيش؟ لل F statement، لل F keyword
صح؟ non-terminal، non-terminal؟ Terminal و نص
كمان، صح ولا لا؟و ال E دي there is expression يعني
انا بتعطيكوا مثلها العمل هي المبرمج مدخل زيك هذي
بتعملها less than عشان من اللحظة بتقولوا ان هذي
assignment هذي ايه يعني هذا
ال I ترمز لل F كلها ال I هنا ترمز لل token تبع ال
F تبع ال F keyword فإذا اللي أنا ماجف عليه هو
عبارة عن ال non-terminal هو مش تق non-terminal
يبقى بداجي else لأن إذا ال I equals the current
input symbol أنا عندي هاي ال input هذا هو ال input
و بدي أحللك ال input symbol by symbol كيف ده
أحللهمهي F لحالة صح؟ و كان فيه اندجوس اه هاي جوس و
بعدين ايش؟ ال X ال X هي عبارة عن identifier X و
انا حاطي identifier و letter بيطول X و بعدين ايش؟
فرد و بعدين less than ال L E و بعدين ايش؟ الرقم
التلاتةتلاتة كانت تلاتة بعدين ال ghost اليمين تمام
بعدين identify ايه قولنا then then هي ده عبارة عن
token صح then ال identifier y بدي يكون assignment
خمسة و لا كانت الخمسة هنا كل واحد كل واحد خلاص
الان انا الان هنا على ال grammar و هنا على ال
input صح هاي ال forward pointer و قولي انت الان
على ال input الان انا هنا على ال grammar على ال
production و هنا على ال input اذا xi equals the
current input symbol ايه اي current symbolinput
symbol هل هذا مطابق هذا أي نعم لأن هذه في ال
grammar هتكون مكتوبة على شكل ال token مظبوط اللي
هو هذا فمطابق ايش بسوي advance the input advance
the input صح advance the input وبعدين اطلع من ال
current iteration ورجع تاني على I بساوة اتنين I
بساوة اتنين يبقى انا الآنهي بشار هنا هى x2 انا
الآن هى I بالساوية اتنين انا الان هنا الان هو non
terminal اللى مجيهش يسوي باستدعي كل procedure xi
x2 اللى هى ال procedure تبع E فهيكون في عندي زى
هذه هى مجيهش مفروض هروحها كرشسأختار اشكال E
production سأختار اشكال E production هجيب ال
production تبع ال expression ايش اشكاله ان والله X
اكبر من وش عارف شو كان يعني identifier و
relational operator و number هجيب اشكال و هقعد
ايه؟ هحلل فيه بنفس القالية مظبوط؟ الان لو ماكنش
non terminalلو هذا لأ و هذا لأ يبقى إيش يبقى else
يبقى فيه error مظبوط يعني لأ هو يعني هو هو هو هو
مش non terminal هو terminal ولكن لم يكن مساوي يعني
كان اللي كان اللي عطيني دكتور أرجعت لما أحنا قلنا
إنهم terminal أحنا عملنا على دخل في الإفعال
سابها اللي انا صار على الجوس و هنا على ال E تمام
الان لما انا اجد على ال E ماجليش topic ال E مع
الجوس كان يخش على ايوة ال E ايش أشكاله قد يكون
واحد من الأشكال تبع ال E اللي بيبدأ نحن على X2
فالان لفنا اللف وصلنا على X3 هنا هدا كان مجرد
مطابقنا احنا جدّمنا بقى لا تنساشجدّمنا الفرق الان
انا على هذا انا على دي دي terminal اين احد ال
terminal هل يقابق ال current اين عن مقابق خلصنا هل
في ضايق اشي مش ضايق اشي الجهد خلصت و هذا خلص ال
input يبقى كل شي سليم بس ايش المشكلة اللي هي مشكلة
التجربة و الخطأ هذه فاحنا we want to find a way to
eliminate the trial and errorتجربة الخطأ هذه بدنا
نلغيها نشطبها ف ..
لو في عندي جدول زي هذا الجدول اللي يقولي والله يا
سيدي لو أنت موجود على ال terminal فلاني ال non
terminal فلاني و ال input اللي أمامك في الهالة هو
كذا إذا أنت وارف على ال terminal كذاإذا انت واقف
على terminal كده خلاص مافيش فيه ال matching لكن
إذا انت واقف على non terminal بص على ال .. ليش؟ لأ
بص على ال input اللي جاي ال input اللي جاي ال
input اللي قدامك ليش .. هقولها عايش بدك تبص انت
دلوقتي ع ال non terminal ع ال non terminal ماشي؟
أيش المعلومة الوحيدة اللي ممكن توجهك اللي هو ال
input اللي داخل عليك إذا أنت على ال non terminal
فلاني وعلى ال input فلاني استخدم ال rule فلانية
هذا ال table بالظبط بيقولك كذا بيقولك إذا أنت على
ال non terminal كذا و أمامك في ال input identifier
فاستخدم ال rule هذه أمامك boss استخدم ال rule هذه
غير هيك أنت هنا وجدت إشي تانيمعناته في error هدولة
فعلا error يعني هذا إنه لو أجاني ال a هيعطيه error
صح أو لا؟ لو أنا واقف على ال e و أجاني حاجة تانية
غير هذا و غير هذا معناته في error هنا السؤال اللي
تتذكر انت ال a كنا مطابق ال input اه بس ال a أنهي
a اطلعنا من ال a احنا هنا هنا هنا هنا مافيش a في e
لأ انا كتبت منه كده؟ اه كنت لما قولني انا جاني ايه
كتبت عنه اللي هو non-terminal صح ولا لأ؟ نعم مش
انت قولتلي هانا غير طابق فيه قولتلي انك جد وانت
يعني لما هو جد وانت يعني
non-terminal اه طيب بدي اشوف ايه هو ال non
-terminal بدي اشوف اي واحد من ال non-terminal اللي
عندى اي واحدو اشوف ايش ال input اللي انا ماجف عليه
و اشوف هذا ال input ايه اسمه مع هذا ال non
terminal هل موجود في الجدول ايش بيجمعهم اه فيه اذا
فيه هذا هتكون rule بروح بهي اللي باختارها الجدول
هذا بقولي ايش ال rule اللي اختارها اذا كنت انا
واقفعلى ال term ال non term الفلاني و دخل عليا و
في ال input واقف على ال input الفلاني السؤال الآن
كيف ابني الجدول هذا كيف بنبنى الجدول هذا جدول هذا
هو عبارة عن جدول بيريحني من عملية التجربة والخطأ
قاعد بقول لي بشكل محدد اذا انت على ال non term
الفلاني و في ال input على ال character على ال
input الفلانيعندي هذه ال rule اللي تستخدمها وانت
مغلط مافي اختيار و مافي backtracking مظبوط انه
الاختيار هو سبب ال backtracking إذا بختار و بغلط،
بعدها تقعد أتراجع okay فالان هذا ال table بقدر
أبنيه باستخدام algorithm بس ال algorithm هذه تعتمد
على مفهوم ال first و ال followالمفهوم ال first و
ال follow المفهوم المفهوم ال first و ال follow
المفهوم المفهوم المفهوم المفهوم المفهوم المفهوم
المفهوم المفهوم المف
S can have the form كذا و اي كذا الان ال alpha هذه
ترمز الى اي تشكيلة من ال symbols ال
A هذا ال non terminal هذا اللي هو productions
واحدة منهم هذه هذه ال productions بتبدأ بال
terminal Cوبقى مطبوعة بين سلسلة مش مهمة من الاش من
ال symbols ال C هذا يظهر في بداية ال A يظهر في
بداية ال production دمات ال A وانا
مغمط بقول ان ال first of A يحتوي
على C قلت يحتوي علىis a member of a first law of A
لأنه
قد يكون في حاجات أخرى بس بصفة عامة أي terminal
بيظهر في بداية ال body تبع non terminal ال body
تبع production ل non terminal هذا ال terminal اللي
ظهر في البدايةبكون موجود في ال .. في ال first تبع
هدف ال non terminal فأنا مهمتي قبل ما أبني عشان
أقدر أبني ال table أعمل جرد لكل ال non terminals
عندي و أشوف لكل non terminal ال firsts تبعه منه
نرجع كمثال لهذه ال grammar بناء
على الفرنة التوية ال E
الـ E' لو انا بدأ اسأل عن ال first تبع ال E' ايش
ال symbols طبعا كلها هتكون terminus اللي داخلة في
ال first تبع ال E' ال E' مالوش الا two productions
واحدة إبسلون والتانية فيها symbols ايش العصر
هذه هذه terminal او non-terminal Terminal صح فهذا
من الطبيعي ان يكون ياشهر الجمع الذاتي ال E بقى
مالهاش غيرهم خلاص بسكر ال F ال
first تبعها ال
ghost الشمال و ايش كمانهذه production وهذه
production اخرى هل ال production هذه بتبدأ ايضا
بتبدأ بتبدأ بتبدأ بتبدأ بتبدأ بتبدأ بتبدأ بتبدأ
بتبدأ بتبدأ بتبدأ بتبد
Terminal فنحط هذا ال terminal في ال first ضمن
مجموعة ال first لأن ال first بقى هذا عبارة عن
مجموعة ممكن تحتوي على واحد ممكن تحتوي على أكتر حسب
ال productions بظبط طبعته هذا كان له production
واحدة فقط فال non terminal اللي ظهر في بدايتها كان
هو لحانه إذا كان له عدة productions فناخده
بصفحة عامة مايش نسويه بصفحة عامة ال first تبع اي
symbol اذا
هذا ال
symbol terminal فال
first تبع اي terminal هو نفسهيعني لو قلت لك ايش ال
first تبع ال ghost هو ال ghost ولا شيء سوى ال
ghost شوفوا فيه اصلا هو terminal لا يتفرح منه اي
حاجة اذا هو اذا انا فيه عندي ال first هذا ال
symbol هذا فيه ال production زي هيكا can I have
the form of epsilonبينما إذا هو non-terminal فابد
أبص على إيش Productions
تبعهم صح؟ إذا في عندي production ل X بقول إيه
لإبسلون Can have a form epsilon يمكن لازم أحط
إبسلون في
المجموعة
صح هدول الحالتين اللي هو بسيطات غير هيك انه هو non
terminal
هو non-terminal ويله productions تحتوي على عادية
سلسلة من السيمبولز زي مثلا اللي هو statement can
have a form if expression then statement else
statement هذا عبارة عن
هذا عبارة عن non-terminal له production تحتوي على
مجموعة من ليش بس symbols بعض منها terminals و بعض
منها non-terminals ففي مثل هذه الحالة ال first تبع
S I
لأنها terminal ماشي بس يه production واحدةبس لأ هو
ممكن يكون يكون له production أخرى من هذه ال
production باخد بس ال I لو في أسئلة production
أخرى بدي أبص عليها واحد و واحد تاني و أشوف ايش ال
.. الآن قد تكون ال production بتبدأ ب non terminal
إذا بدأت ب non terminal معناه بدي أخد ال first تبع
هذا ال non terminal
لأ لأ احنا خلصنا ال epsilon احنا قاعدين بنقول احنا
بنقول بنشوف اذا جينا non terminal صح او لا ايوة
احنا خلصنا ان هو non terminal خلصناها خلصناها و
خلصنا ان هو non non terminal لكن في ال production
مباشرة epsilon ايش حديثة بنحط بنحط epsilon الارجال
هنا في هذه الحالة تعتبر ان هو non terminal و ال
productions مش epsilon يعني فيها symbolsفكانوا
يقولوا إذا كان والله لازم نطلع على كل ال
productions اللي زي ذلك نطلع على أول أنصار في كل
production إذا أول أنصار عبارة عن terminal إذا
أول أنصار عبارة عن terminal نخده هو لحاله من هذا
ال production إذا Y1 عبارة عن terminal خلاص لان
جينا ل production الأخرىلجينا Y واحد non terminal
افترض انه زي ذلك بدي اشوف ال E ايش ال first تبعها
وكل عناصر ال first تبعونها اضيفهم كfirst ل S
منطقي؟ صح؟ يعني بما ان انا بحكي على اول عناصر ممكن
يبينوني في S وبما ان S هذه ممكن اول تصريف لها يبدأ
بEيبقى كل ال first one ايه هم ال first ال X حلو
كتير احنا الآن بنركز
على هذه الحالة ان X is a non terminal و ال
productions بتحتوي على symbols ال symbols هذه هي
محل الاهتمامإذا كان السيمبول هذا Y1 باختصار
بدي أجيب ال first تبعه و
أحط عناصر ال first تبعه members في عناصر ال first
تبع X أنا الأن أشغل على Xولاقيت انه ال productions
و ال productions هذه فيها symbols و ال symbols هذه
فيها دي y1 ال symbol هذا y1 بتجيب ال first تبعه و
حطهم عناصر في ال first تبع ال x هذا الان ال y1
والله هو terminal خلاص هو لحاله إذا هو non
terminal و يقول إلى epsilon خلاص ال epsilonإذا هو
non-terminal وإله production بتخش عيد الكرر فهي
تولد تلات rows هم بتلخصوا الحكاية كلها بس العملية
recursive عملية جرد ال first تبع أي non-terminal
هي في حالتها عامة مليئة recursive لأن هذا ال non
-terminal
أثر كسمبل بصفة عامة هذا السمبل قد يكون terminal و
تنتهي الجلسة أو قد يكون non-terminal و يلو إبسلون
و تنتهي الجلسة أو قد يكون يلو إبسلون و يلو أبسلون
و تنتهي الجلسة أو قد يكون يلو إبسلودخلت وعملت جرد
لل first تبعونه وجدت فيه بينهم ال epsilon يعني
لحظة من ال productions تبعت y واحد تقول إلى
epsilon فدخل ال epsilon في ال first تبع y واحد دخل
في ال first تبع y واحد يبقى هدخل في ال first تبع x
كونه في لل y واحدالـ first تبعه في إبسلون لازم
أروح أعمل برضه ل Y2 طوال ما بيظهر معايا Y و إبسلون
في ال first بتعمل ل Y2 إذا طلع معايا إبسلون في ال
first تبع Y2 بتعمل ل Y2 صح ولا مش صح؟ ليش؟ لأن إذا
إبسلون موجود في ال first تبع Y1 يمكن في احتمال أن
Y1 مش موجود في ال input يعني لما دخل ال inputمحدود
في ال Y1 هو إيش يعني إبسلون؟ يعني مش موجود يبقى ..
مين اللي حاجة في الصدر الرحني؟ Y2 يبقى لازم أشوف
ال first تبع Y2 كذلك الحالة ل Y2 إذا إبسلون موجود
في ال first تبعها فالعملية هذه بيقول لي for
example جيبنا Y1 ال first تبعهاكُل ال first تبع y1
is in .. in ال first تبع x لأن if y1 does not
derive epsilon إذا ال first تبع y1 لاح تبع ال
epsilon خلاص we add nothing more مابنضيفش شيء وإلا
but if y1 derives epsilon .. derives epsilon يعني
ال epsilon موجود في ال first تبعه then we add ال
first تبع y2يعني نروح ال Y2 و نجيب ال first تبع ال
Y نعم و and so on يعني إذا برضه ال Y2 ال first
تبعها يحتوي على إبسلون بدي ألف على Y تلاتة يبقى
هذا العملية الجرد هذه فيها عمق يعني أنا ببدأ على X
بدي أجيب أنا ال first تبع X راجحها و دخلت على ال
first تبع Y ال Y هذا هو واحدة من ال production
تبتدى ب Wكـ Non Terminal و Non Terminal هي
Productions دخلني على Z و Z دخلني على مش هشور فانا
هضلني اغوص اتعمق و كذا كالحالة Depth و Breadth لو
طلع معايا ال Y واحد و مش تقاتها طلع منهم Epsilon
هبدأ اروح على Y اتنين صح فالعملية متشعبة عمقا و
عرضا بس احنا طبعا ايشخلّيني أشوف مثال بسيط على ذلك
و .. مش
هيبقى مثل المعقدة .. بقى بس شغل .. اخي .. خلاص اه
بنعمل ال first و بعدين بنرجع تاني لل follow هاي ال
example هي ده consider ال grammar هي نفسها بيه تبت
ال E prime ده ده ده ده ده ده ده ده ده ده ده ده ده
طبعا الجانب can have the form FTE' و بعدين ال E'
can have the form plus TE' or ε ال T can have the
form F T'
و ال T' can have the form F T' or ε
الـ first of F و ال first of T و ال first of E
خلّيني أخد ال first of E هاي ال E ساوي
هاي ال production
تبعت ال E في غيرها مش غيرها أول symbol Y1 إلها
عبارة عن non-terminal إيش أسوق فيه؟ أحطه في ..
أحطه في ليه ده؟ لأ طبعا لأ أقول لك كونه non
-terminal استحالة non-terminal ييجي كده بدي أشوف
ال productions تبعته هاي وين هايها مش غيرها انا
الآن قاعد ببوص العبق الآن ال Fبرضه non terminal
هاي production و هاي production تمام هاي ال
production هادي هاي Y واحد تبعها ال ghost ال ghost
هدا non terminal ايش ال first تبع non terminal هو
نفسه فبحطه يعني هو بالاصل احنا اليوم بنحكي عن ال
first تبع ال Fاللي هو بده ييجي جوا ال first تبع ال
T و بعدين ال E اللي هو بده ييجي جوا ال first تبع
ال E فاحنا على طول بنحط في ال E الان مين كمان
خلصنا من هذه ال production ال Y واحد تبعها هيبقى
on terminal و حطناه و خلاص مافيش شي نطلع التانية
هي production أخرى هي ال Y واحد مافيش شي غيره أصلا
برضه terminalفى ابسلون عندى هنا ال F لها علاقة
بالأبسلون لأ هسكر فى عندى بس عنصر يعنى ال goes و
ال identify هدول الآن بيخشوا لل E لل T و بيخشوا لل
E فبس هم لل F هيته الفرصة تبع F يسوى الفرصة تبع T
يسوى الفرصة تبع E مافيش شي غيره هل ال E الآن أنا
بعد ما خلصت هي Y واحد تبع ال Eأيش يساوي؟ الـ goals
و الـ identifier من داخل بالي من إيش؟ من الإبسلون
هل الإبسلون موجود هنا؟ لأ، خلصت، لو الإبسلون موجود
هنا، معناه أنك تريد أن تذهب و تحسب Y2 اللي هي الـ
E prime و تحسب ال first و تجيبهم كلهم برضه كمان و
تضيفهم على ال first ده، صح؟ لكن لو حصلنا على حد
مافيش، فخلصنا لأن ال goals و ال identifier، الآن
لل E primeالـ E' هيالها two productions واحدة منهم
فعلى طول الـ first تبع E' بده أحط الـ Epsilon من
أولها فاهم؟ كمان، بس أنا بده أحطه من أولها و أرايح
حاجة منه ليش حطيته؟ لأن القاعدة بتقول لي إذا X
derives Epsilon وهو كذلك E'
حط الـ Epsilon في فرصة X الـ X اللي عندي اللي هو
هذا الـ E' يصبح و
إيش كمان أحط .. إيش هذه .. هاي ال E' فعندي الزائد
ال production التانية Y واحد فيها الزائد خلاص هذه
الزائد لأنه الـ Epsilon موجود في .. هو Y2لأ احنا
قاعدين نحسب ده E' طيب طبعا لو E' جاي اقول مثلا هيك
هنا لو E' جاي بدل ال T و انا قاعد بحسب ال first
تبع ال E و طلع مع ال epsilon يبقى لازم اروح حاسب
ده اللي بعد دكتور اكيد انا ب E' اول ما دخلنا ال
first تبعه مثلا ال Z لو ما انتظرنا نحطهحطنا ال
gate لجينا ال production تانية اللي هو ال epsilon
لجينا ال gate نسينا أن نروح على Y2 اللي هو ال T ال
capital صح ولا لأ؟ ايه و بنروح على ال T بالظبط
لأنه ال epsilon ظهر لأ نشره على ال T احنا هنا Y1
اش هو زاد لو لو كانت هذه non terminal و لجينا ال E
في ال first تبعها هي تبقى على ال Tأحنا بيقولنا
بنروح على ال T بنزيد Y زيادة Y لإيش اذا انا وجهنا
ال Epsilon Epsilon وين؟ في ال first تبع مين؟ ال A
لأ تبع ال Y واحد ايش اللي بيخليني أسحب على Y تنين
و Y تلاتة ان انا ألاقي Epsilon في ال first تبع Y
واحد و Y واحد خلاص و Y واحد خلاص قبل يه ال T اللي
هي ال plus مش رايح انك ماروحتش على اللي بعد فانا
الآن جفلتالفرس تبع ال E' بالإبسلوم والزائد أو ال Z
والإبسلوم مش فارق احنا
الآن عمليا ال F والT والE خلصناها في الهروبية
واحدة و الآن ال E' ايش رضاه؟ رضاه ال T و
ال T صح؟ هاخد ال T و ال T ال T خلصناها يا عزيزي هي
ال T مخلصة رضاه بس ال E' ال T' ال E' خلصتT prime
نفس قصة E prime النجمة و اللبس العاطف صح ماشي
الان هذا الكلام سنسجله في table نيجي و نقول ال E و
ال firstبعدين ال follow كمان شويه بنعمل ال follow
ال E ايش ال first تبعها اللي هو اول احنا حسبناه
اللي هو ال ghost و ال ID ال E ال E prime ال T ال T
prime و ال F صح ال E prime اللي هو الزائد و ال
ghost و ال و ال epsilon ال T ال T اللي هو زي ال E
الـ T' هو النجمة والأبسلان والـ F هو الـ ID والجوث
والأبسلان هانيش نعمل الآن ال follow نشوف ال follow
كيف الفولو فكرته انه هاي ال non terminal عادة بيجي
بعدهالأول هو ما كان فكرته والثاني هو ما هي ال
terminals التي تأتي بداية production سبعته بالنسبة
ل ال follow إذا كنا نحكي عن start symbolبنحسبله بس
start simple كحالة خاصة لازم احط ال dollar sign في
ال follow تبعه ال dollar sign كمان شويه قدام بنفهم
ايش وظيفته ال follow تبع S مفتاح جواز و اول انصر
في الجواز اللي هو ال dollar sign وبعدين بقالف ..
بطلع ال productions تبع .. مش ال productions تبع
تبع ال productions اللي هو بيظهر في ال body تبعها
ليش؟ لأن انا الآن ال rule تبعتي بتقول لي إذا عندك
non terminal Bظاهر في body تبع production بغض نظر
الـ A ده ولا إيش المهم هو و جاي بعده مجموع من ال
symbols Beta هنا ترمز إلى مجموع من ال symbols جيب
ال first تبع Beta ال first تبع Beta هو follow ل A
هو follow ل A capital صح ولا لأ اش طبيعي ال first
تبع Beta هو follow ل BFollow the B if there is a
production بيظهر فيها ال B في ال body تبعها مطبوعة
بسلسلة من ال symbols فهذه السلسلة من السيمبولز جيب
ال first تبعها احنا ما مارش علينا ان نجيب ال first
تبع السلسلة من السيمبولز احنا بنعرف كيف نجيب ال
first تبع نون ترمينال نظبط نون ترمينال بشوف ال
productions تبعته ببحث فيهfirst تبع beta و بسيطة
عادى مش beta سلسلة من ال symbols قول مثلا عندي I
expression
then statement else statement افترض بي هي هذا مش
beta
صح وماش Alpha صح فانا الان قاعد بقى اسأل ايش ال
follow تبع S ال ruler بتقوللي ال first تبع Beta هو
ال follow تبعه طيب هاي ال Beta E S ايش ال first
تبع هذا الكلام خدوه على اساس ان هو body يبتد ب E
ياليها S إيش ال E هذي ال terminal؟ اه terminal هي
ال else صح؟ إيش ال first تبع terminal؟ ال E طيب E
هتكون ال follow يعني .. أروح .. مصمم شوية أروح
أكمل؟ لأ لأ خلاص لجدك يا عزيزي يمكن ال first تبع
هركب كله هو ال E لحالها هذا كان هو ال follow تبع B
ك first ك first تبع data هو ال follow تبع Bهذه كل
القصة فإذا أنا بحكي عن الـ non-terminal و الـ non
-terminal هذا بيظهر في body في productions أول non
-terminal بوجهي هذي لأ لأ احنا بدنا نعمل عملية
حصائية لكلهم لكلهم بدنا نحسب ال follows تبعتهم
كلهم كلهم بدنا نحسب .. زي ما حسبنا ال first بدنا
نحسب ال follows فلعندي هنا مثلا أخد ال T بدني ال
follow تبع ال Tبقول لي و الله وين تي ظاهرة هي
ظاهرة في هذا ال production وظاهرة في خلاص هي هذه
ال production اتطلع عليها هنا و اتطلع عليها هنا
طيب هنا ايش في وراها وراها symbol واحد هذا ال
symbol هو beta هنا من حظنا ال beta تحتها symbol
واحد اجيب ال first تبع E' ما هو محسوبه خالص ال
first تبع E' هو followبس مش لحاله ربما .. ربما
ألاج ال T ألاج
ال T في ال production أخر جايب عليها beta أخر لازم
ألف مش لحاله بس هنا ال first تبع E prime اللي هي
هذه هتتجفونه ل T وين T؟ هاي T فبتحطهم اللي هم ال
plus و ال epsilonلا بقولي استفنى ال epsilon except
ال epsilon شيل ال epsilon مابحطهاش okay بس ماخلصتش
انا لإن انا شايف ال T في هذه ال production هي في
production أخرى هذه ال production أخرى أختها
بالظبط ايه نفسها اذا اعيد نفس الكلام مابحاجيبش
جديد خلاص طيب بدي أجيب ال follow تبع F
الـ F أظهر هنا و أظهر هنا و في الحالتين مطبوعة
بالـ H بالـ T' نفس الأيدي يرجع ال first تبع T'
يضرب و يستفن الأبسلون طيب بدي أجيب ال follow تبع
E' E' هنا أظهر و مافيش وراها Beta و هنا كذلك مافيش
وراها Betaهل القاعدة لك انطبق اللي هنا لإنه انا هل
بتقولي انه في في الأول يعني هو لما قولنا انه نجيب
لل F صح ولا لأ انت ركنك حقرت لل T' ماكناش نحكي عن
ال F ال follow ال follow ماكناش نحكي عن ال F ليش
مش قولنا ال F بعدية T برا نجيبنا ال first بعد T
برا اه اه اه صح الصح ال Fالـ F أهل باعه أهل أبوه
أهل أبوه أبوه أبوه أبوه أبوه أبوه أبوه أبوه أبوه
أبوه أبوه أبوه أبوه أبوه أبوه أبوه أبوه أبوه أبوه
أبوه
أبوه أبنطبق عليها رقم تلاتة اذا B جاي في الآخر او
خلّي بالك جاي في الآخر وراها beta و ال beta هي ال
first of حيحتها على epsilon طب هذا الكلمة مر علينا
مر علينا وين هنا و هنا لما كنا بنحط ال epsilon و
بعدين بنشيلها انا هذه ال rule تلاتة هي اللي بتنطبق
على كمان برضه عشان على T ايش بيقوللي
السمبل اللى بتحسب الـ follow تبعه الـ non-terminal
اللى بتحسب الـ follow تبعه جاي في ال .. بيجي في
آخر production أو بيجي وراء إشي و الإشي هذا ال
first تبعه يحتوى على إبسلون يبقى عشان .. أيه بدك
تسوي بدك تجيب ال first تبع ال issue هذا اللي هو ال
beta و أيضا بدك تحط ال follow تبعه ال
follow تبع ايه؟بنضع follow بيكتر بيكتر بيكتر بيكتر
بيكتر بيكتر بيكتر بيكتر بيكتر بيكتر بيكتر بيكتر
بيكتر بيكتر بيكتر بيكتر بيكتر بيكتر بيكتر بيكت
إذا الحالتين هذوله بيه مفيش وراها beta او بيه
وراها beta و ال beta هذه يظهر ال epsilon فيها
فمعنى ذلك ايش هنسوي ان everything in follow a is
in follow b كل شيء في ال follow تبعي ايه ال a دي
ده هي رأس ال production ال answer لازم اطلع ال
follow تبع ايهو ال follow تبع ال E prime و احطهم
في ال follow تبع ال E prime فانا الآن بحكي عن ال E
prime بتروح على ال E هاجيب ال follow تبعها عشان
احطه في ال follow تبع ال E prime صح؟ خلينا نطلع
على الكلام هذا هنا هيته ال follow تبع ال E هو
مااخدهم مش زي ما انا اخدهم اخدهم واحد واحد من ال E
الـ follow تبع E بيساوي الـ follow تبع E' نفس
السبب اللي تبقى قولناها ويساوي ايش جوس ودرسين ليش
جوس ودرسين؟ ايش ال follow تبع E؟ وين ال E تظهر؟
وين ال E تظهر في ال productions؟ هنا الوحيد المكان
الوحيد تظهر فيه ايش البيت اللي وراها؟ جوس جوس ايش
ال first تبع هذا الجوس؟ هو الجوس نفسه صح؟ يبقى هذا
الجوس اللي هو firstاللي هو beta هو first and
foremost هو follow ال E تمام؟ تتبعه بال$$$$$$$$$$$
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
$
$$$طبع الرأس الـ production هو الـ follow إلها من
الرأس هنا E ماهو ال follow تبعه الـ ghost درسان من
الحاطط طب هنا ماهو الرأس E نفسها ماهو ال follow
خلاص ماضيفش إش جديد يبقى follow of E يساوي follow
of E prime يساوي ال ghost اليمين مع درسان
بعدين رايح على ال T رايح على ال T follow of ال T
وين ال T يظهر علينا هى و هى صح ايش حسبنا احنا ال
follow تبع ال T ال follow
تبع ال T هو ال first تبع ال E prime ال first تبع
ال E prime تشوف ال E prime اللي هو ايش ازاي صلت
شويةالـ follow تبع ال .. ال .. ال .. ال first تبع
ال E prime ال first تبع ال E prime اللي هو الزائد
اللي هو الزائد والإبسلون لأ بس لإنه .. اه هذه اللي
قال بيتا و ال first تبع هذه ال beta اه ال first
تبع يحتوي على الزائد على الزائد والإبسلون يبقى أنا
دلوقتي انا خشيت في روح رقم تلاتة روح رقم تلاتة إيش
بتقولبتقولي جيب ال follow لأن
ال beta تحتوي على إبسلون صح؟
أنا الآن بقى أحسب لل T صح؟ طيب بيدا جيب ال first
تبع E prime جبت ال first تبع E prime ال first تبع
E prime تحتوي على إبسلون
صح في هذا الحل ايش هسوي رقم تلاتة اش بتقول اذا
كان هناك production او
جاني ورا beta و ال beta هادى ال first بحر هيحتوى
علشان ان كل شيء في ال follow تبع a و ال follow تبع
b من ال follow تبع a هي ال a من ال follow تبعها
الجوز والدولار الثاني اعطيه لمن؟ اعطيه لل T الجوز
والدولار الثاني صح؟ والزاد والزاد ايوة ايوة الزاد
لأنه اصلا الزاد موجود في ال first بمعنى ان ال
first هذه بحطهم و بروح بجيب الفرق بس ده شيء ما
بحطش ال epsilon صراحة كاتب ال ZN
is in follow everything في الهدى is in follow يعني
إضافة إلى إنه انا حطيت ال first تبع beta برضه كمان
بده اضيه بده احط ال follow تبع a و انا احنا هنا
احط الزائد احط الزائد اللي جاي من ال first تبع
beta احط الجوز و ال dollar sign اللي جايين من ال
follow تبع E primeلأ تبعين تبع ال E و I هو تبع ال
E' لاحظ ان هنا T برضه الظاهرة هنا و نفس الشيء يعني
انا لما اجيب ال first تبع ال E' هرجع في نفس القضية
اللي هو إيش ال epsilon و روح اجيب تمام
الآن ال T' نفس الشيء ليش ال T' نفس الشيء
مش Beta تمام؟ اللي جبّبك عليها انه في Beta كأنها
زيها زيه اللي في Beta و ال first تبع Beta إبسلو و
فيه إبسلو okay فإيش يسوي الأن ال T prime ال T
prime اللي هو plus و plus و plus يعني ال F إيش ال
.. إيش ال follow تبع ال F و
ال F جاية
يعني ال T Prime و T Prime لكي تجيب ال first تبع ال
T Prime ال first تبع ال T Prime هيته اللي هو اللي
اتضارب اللي هو اللي اتضارب صح؟ صح يا عزيزي لأن في
إبسلون لأنه بيجيب ال follow تبع ال T لأن ال first
تبع ال T Prime محتوى للإبسلون لكي تجيب ال follow
تبع ال T اللي هو هذا لكي تجيب ال follow لل T Prime
خلّي بالك انا بجيب ال follow تبع ال F بطلع على ال
first تبع T' ال first تبع T' يحتوي على ال star و
ال epsilon هحطه ال star ال epsilon خلّاله دي اش
هسوي اجيبه ال follow تبع رأس ال .. طيب ليه؟ عشان
جدي .. بزي ما توه عملنا اتوه لما مش جيبنا ال
follow تبع ال ..مرة و أخرى مرة و أخرى أنا الآن على
ال F بدي ال follow تبع ال F بطلع ال first تبع اللي
بعدها اللي بعدها ال T prime وين ال first تبعه؟
حياته صحيح بس لأني بيحط .. حطيت النجمة لأنه احتجت
على ال epsilon إيش ال rule بتقوللي؟ ال follow تبع
ال T هاي ال T هاي ال follow تبعها صح
ولا لا؟ مظبوط؟
مظبوط؟ جثة طويلة و عريضة بس ال rules بتاعتها واضحة
يعني ربما بدها انتباه شديد في انك انت تتأكد انك
بتنجل ال symbols الصح من ال non-terminal الصح انما
ال rules واضحة و محددة و مافيش فيها laps هذا
الجدول الآن اللي هاندي علان عليهبقدر اعمل الجدول
اللي هو هذا هذا اللي انا بدي انه يقول لي لكل واحد
من ال non-terminants دولة اذا انا واقف عليه و واقف
على 100 اي واحد من ال input سلولة
هل هي role أستخدمها؟ خلاص و احنا لاقينا عملية بناء
ال table شبه جربنا على نهايتها ال algorithm هذه
بتقولي ايش اخد من هنا و احط في الجدول من الجدول
هذا كيف اشكل الجدول التاني