بسم الله الرحمن الرحيم اليوم إن شاء الله سنستكمل
الدرس السابق إن شاء الله اليوم بدنا نبدأ في موضوع
الـ 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 ..
خلاص بتقول Error إلا إذا كان فيه خيار ثالث بيبدأ ب
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 one gamma 2 هكمل
إيش؟ gamma 1 عادي مش هيتأثروا البقية أنا بس
المعالجة تبعتي كانت وين؟ في اللي فيها البداية
المكررة فأنا سحبت الـ alpha اللي هي المشتركة وضربت
في A bar الآن شو الـ A bar؟ قال لك ارجع إليهم خبي الـ
alpha إيش ضال؟ beta 1 أو beta 2 يعني بالعربي كأنه
أخدهم عامل مشترك، كأنه أخد الـ alpha عامل مشترك
لبرا، إيش ضال جوا؟ beta 1 أو beta 2 التي هي الـ A
bar هكذا احنا غيرنا شكله لكن ليس مضمونه لأن لو جئت
تطلع على الـ grammar الجديد ما فيش فيه بداية مكررة
خلاص بتعمل function A بتعمل function 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 ونضربهم في مين؟ في S bar أو اللي ما فيه مشاكل
إذا الـS bar عبارة عن إيش؟ خذي خبي هذا ايش دخل منه
إبسيلون خبي هذا ايش دخل منه خلاص يعني 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 bar S bar S bar مظبوط أو ايه أو
إيش عندك لسه أما أنت أخذت هذه هذه اسمها ياخد الـS
الجارب إيش؟ جارب الـI أسهل، جارب الـI، مش مشكلة
على أساس ما تضطريش اللي فوق تعمليها، هو ننصح، ننصح
سنحاول نوصل لـS، خذ الـIE تمام، الـIE هتدور بيها،
في S bar or A الـS bar عبارة عن إيش؟ تشيلينها، TS
أو
TS VS TS أو إبسيلون إبسيلون مش هيك؟ خلاص الآن هتيجي
تعيدي نفس الفكرة همش هأحل كامل exercise هو سؤال
هتيجي تعتبريه كأنه سؤال جديد و في TS بداية مكررة و
بتبدأ تعيدي بتصير الـS bar هتطلع لك S bar bar و
بتحليه S bar عبارة عن TS في S bar bar أو إبسيلون و
الـS bar bar عبارة عن إيش؟ إيش ضال؟ إبسيلون أو بي
أس بي أس، خلصنا، خلصنا، عادي دائما خذي من باب
السهولة الأقصر و شوية شوية حتتعاد أكثر من الـ
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 كيف بنعملها
استدعاء في الـ main؟ مش عبارة عن 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 إيش معرف قدرة parameters يعني بده يصير
إشي أكتر لكن ك 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 الجديد هذا المفروض
أنه أنا ما شرحتش فيه إشي كثير ليش؟ ليش؟ ليش؟ لأنكوا
أخدتوه أخدتوه و خلصتوه بدون .. أركز على الأشي المهم
أنا بس بدي أحاول ع السريع أمشي عنه طبعا
يا بنات عملية الـ parse tree لها شكلين احنا اتعلمنا و
بنشتغل على شكل لكن سيبنا الشكل الثاني مش هنشتغل
عليه الشكل اللي اتعلمناه اللي هو الـ top-down يعني
ببدأ أنا من الـ root بسيرأعمل الشجرة لغاية ما أوصل
مثلا خمسة زائد اثنين و هكذا فهذه الطريقة ما نسميها
top-down لكن بالتأكيد في طريقة عكسية بتبدأ من الـ
sentence المكتوبة يعني ببدأ من واحد زائد اثنين
زائد ثلاثة و بعدين من وين طلعت هذي؟ طلعت من factor
هذي من وين طلعت .. و تصير إيش؟ من تحت تمشي لغاية ما
تخلص عند الـ root نسميها bottom-up لكن الـ bottom-up مش
داخل المعنى مش هنشرحه احنا بس مركزين على طريقة الـ
top-down طبعا في طريقة الـ top-down شايفين هذا الـ
grammar هذا الـ grammar أخدتوه ولا لا قبل هيك؟
أخدناه هذا كان بصورتة السليمة اللي هي E عبارة عن
E زائد term أو E لأقصر تهرب تهرب تهرب في factor على
factor فاكتورو ID وده خير إيه لكن إيش عمل فيه هو
هنا شال الـ left 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 عبارة عن إيش؟ عبارة عن إبسلون و
لا ضرب F T bar؟ إبسلون إبسلون
إبسلون إبسلون إبسلون إبسلون إبسلون إبسلون
إبسلون
لكن هي مش ضاربة، إذا الآن نرجع لمين نكمل؟ E bar بس
قبل ما أروح أكمل كلغة الـ derivations إحنا إيش
سوينا؟ هتقوليلي أول إيش استبدلت الـ E بإيش؟ بـ T E
bar، صح؟ أول step عشان هي
استبدلنا الـ E بـ F T E Bar بعدين إيش عملنا؟
استبدلنا من اليمين للي شمال، من الشمال للييمين،
from left to right استبدلنا الـ T بإيش؟ F T Bar
شايفة؟ F T Bar المهم إن هو أنا قاعد أعملك الشجرة
step by step أنا مهم ليش هذا، المهم بس عشان تفهم و
تدوس إيش اللي صار إنه قاعد step by step أعملك
الشجرة أنا قاعد أشغلي عليها إيش أنا؟ مرة واحدة،
تمام؟ خلاص خليني أرجع نكمل، الآن الـ E barعن إيش؟
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 كيف تطلع لما وصل في
النهاية لمين الشجرة الأخيرة تبعتي
في أي سؤال حد هتكمل؟
طبعا الـ parser هذا برضه الـ 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 ahead هيتوقف على A و
فيه خيارين بيبداوا في A إيش هتسوي عاد أنت في الحالة
هذه؟ هتمسكي الخيار الأول و تمشي عليه، خلاص هتقولي
خلاص بدنا نستبدل الـ a كشجرة بـ what بـ a b يعني
match a match b هيك هتسوي بس هتحفظ المكان اللي كان
في الـ lookahead ليش؟ لأنه في خيار ثاني يمكن هو
اللي يكون صح أي تغييرات بسيطة بتعملها في الـ codec
عشان هيك إيش هنقول match a هيصير هذا وين يمشي على
دي وهذا وين راح يعني ما اللي match b
مختلفين إذا بيعرف إنه الخيار اللي اختاره إيش مش
مظبوط عشان هيك إيش هيصير؟ هيرجعله كـ head ثاني ومش
هيختار الآن هادي هيريد إيش يختار الـ a؟ 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 parser بظبط بدل ما
أروح و أرجع ماشي الحال طيب
لحد هلأ في أي أحد مش فاهم؟ هذا كل مراجعة لحد تقريبًا
ما شرحتش شيء جديد هذا مراجعة هذا
.. هذا .. هذا درس تمام خليني أشوفه تفاصيل
الـ 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 صح ولا لأ؟ و أياميها كنت أقولك
البدايات هذه مهمة جدًا بس زمان كانت البدايات واضحة،
باينة لكن مش بالضرورة في الجرامر اللي بدك
تشتغلي لها بدك تضمن إن تكون البداية مبينة يعني
أديكي مثال يعني مثلًا لو أجينا عملنا زمان كنا نقول
حاجة A سائد افتح 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 بنحسب؟ بس قبل يعرفك
أهمية حساباته عشان يساعدني في كتابة أي code طيب
تعالوا نشوف قوانين الـ 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 قد تكون
epsilon يعني التنتين فراغ يعني برضه الـ A بتعطيني
epsilon فمش بالضرورة تشوفيها بشكل مباشر ممكن
تشوفيها indirect يعني بيجي يقول لك الـ A بتعطيني XYZ
و الـ X فيها epsilon و الـ Y فيها epsilon و الـ Z فيها
epsilon يعني خلاص صارت الـ epsilon تضعف للـ A يعني
فاهمة؟ سواء بشكل مباشر أو بدون شكل مباشر هذه
قانونين اللي حتى الآن في الـ first تعالوا الأهم
واحد و بتحاولوا أنتو تفسوليا هذا اجرولي الكلام
اجرولي point two و قولوا لي شو معناها اجرولي
point two و قولولي شو معناها النقطة
اثنين إيش معناها
آه مين فين معناها؟ نقطة 2 يعني
كيف؟ عشان كيف؟ يعني إيش بالضبط؟ يعني الآن لو هذه
Y1 إيش .. إيش .. إيش دخلها في الـ first؟ ما هو بداية
الـ X هتكون نفس بداية الـ Y1 يعني أنت بتحسب بداية الـ
Y1 عشان تعرفي بداية الـ X طيب كويس بس ولا في معلومة
ثانية؟
إذا كان إيش؟ إذا كان فيها epsilon ننقل على اللي وراها
كيف ننقل على اللي وراها؟ يعني لو كان Y1 epsilon هنجيب
بداية Y2 طيب وإيش في كمان معلومة أخرى؟ إذا كلهم
عادل Y1 وY2 وY3 وYK كلهم فيهم epsilonات هضيف epsilon
في المجموعة طيب تعالوا الممتازين تعالوا نشوف إيش
اللي جالوا هنا جال عشان أحسب 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 بماذا تبدأ S follow
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
مين؟ T، إيش الفلو T؟ بتدور وين في T؟ أيوة،
هتقولي فرست الإي بار، تعالي ناخد فرست .. فرست الإي بار،
وينها؟ ما حليناهاش .. ما حليناهاش، ليش؟ طلعناها ليش؟
طيب، يلّا فرست الإي بار زائد أو إبسل إي بار؟ إيش فرست
الإي بار يا بنات؟ زائد أو ضرب أو إبسل فرست الإي بار
زائد .. لأ، أو إبسل، ليش ضرب؟
و هذه كانت 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 ممكن تستخدميها في
إبسلون الآن لما أوصل لهذه الحالة ف عندي خيارين،
صح؟ الخيار الأول إن افترض إن هذا هو البداية مش الـ
بيجي بعده استبدل الـ A بالـ production لأن هو في
بداية الـ A اللي بيطلعه مش هذا خيار الخيار الثاني
طالما هو بيظهر في الـ follow بيظهر في اللي ورايا إن
افترض إن هذا هو اللي جاي ورايا و بيستبدل الـ A في
إبسلون فهنا بيصير عمل إيه التحيير؟ بيعرفش من الصح
في الاثنين هو السهق الجوس موجود مرتين مرة كبداية و
مرة كواحد بيجي ورايا طب أنا مش عارفني يمكن يكون
بداية فالمفروض أستبدل الـ production باللي طلعه لكن
إذا كان من اللي بيجي ورايا هذا الجوس معناه لازم
أستبدل الـ A ماشي من الـ epsilon لأن الـ epsilon ممكن
تكون فراغ في الحالة هذه جال فقط في الحالة هذه ممكن
تكون في مشكلة و الحالة هذه لا تحدث إلا في حال وجود
الإبسلون، لأنه إذا لم يكن هناك إبسلون يجب أن يكون
هناك إبسلون وليس هناك إبسلون وليس هناك إبسلون وليس
هناك إبسلون
وليس هناك إبسل
فهمت كيف؟ في هذه القصة طيب مثال و نختم طيب
خلّيني في هذا المثال و نختم هل
الـ
grammar اللي على اللوح الألوان
والله مش الألوان
طبعا لو جينا نتطلع على القوانين الأساسية مافيش
بداية مكررة، مافيش left recursion، مافيش ambiguous،
هيك في النظرة الأولى، فقوانين القديمة بتعرفنيش،
صح؟ الآن تعالوا نستخدم القوانين الجديدة أول واحدة،
إيش بدك تعملي يا حضرتك؟ بدك تجيبي 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
الـ S طب إيش follow الـ S؟ هتحطي الـ dollar sign و إيش
follow الـ S؟ الـ أسبار
اللي هم الـ E و الـ Epsilon بتعود عنها مش هيك؟ و الـ
follow S في الـ follow S، مظبوط؟ خلصت، في S
ثانية؟ في الآخر 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 و هذا المشكلة أنه بيعمل ليه؟ أنه أخذ هو
اللي ورايا و أنا اللي معاه، بس واضحة يا بنات؟
يعطيكم العافية