بِسْمِ اللهِ الرَّحْمَنِ الرَّحِيمِ السلام عليكم اليوم أن
شاء الله احنا عملياً خلصنا الـ 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 لـ الـ parse 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 في الآخر بيطلع عندي الـ parse 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 لحالة صح؟ وكان فيه and then اه هاي then و
بعدين ايش؟ الـ X الـ X هي عبارة عن identifier X و
أنا حاطي identifier و letter بيطلع X وبعدين ايش؟
فرد وبعدين less than الـ LE وبعدين ايش؟ الرقم
الثلاثة ثلاثة كانت ثلاثة وبعدين الـ ghost اليمين تمام
بعدين identify ايه قولنا then then هي دي عبارة عن
token صح then الـ identifier y بدي يكون assignment
خمسة ولا كانت الخمسة هنا كل واحد كل واحد خلاص
الآن أنا الآن هنا على الـ grammar وهنا على ال
input صح هاي الـ forward pointer وقول لي أنت الآن
على الـ input الآن أنا هنا على الـ grammar على ال
production وهنا على الـ input إذا xi equals the
current input symbol ايه أي current symbol input
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 احنا عملنا على دخل في الإفعال
سابها اللي انا صار على then وهنا على الـ E تمام
الآن لما أنا أجد على الـ E ما جيش topic الـ E مع
الـ then كان يخش على أيوة الـ 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 وبقى مطبوعة بين سلسلة مش مهمة من الـ ash من
الـ 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 هذه هي
محل الاهتمام إذا كان الـ symbol هذا 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
أثر كـ symbol بصفة عامة هذا الـ symbol قد يكون 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 لـ B Follow the B if there is a
production بيظهر فيها الـ B في الـ body تبعها مطبوعة
بسلسلة من الـ symbols فهذه السلسلة من السيمبولز جيب
الـ first تبعها احنا ما مر علينا ان نجيب الـ first
تبع السلسلة من السيمبولز احنا بنعرف كيف نجيب الـ
first تبع non terminal نظبط non terminal بشوف الـ
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 بقول لي و الله وين 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 هذه
بتقول لي إيش آخد من هنا وأحط في الجدول من الجدول
هذا كيف أشكل الجدول الثاني