بسم الله الرحمن الرحيم السلام عشانكم المسلمين نبدأ
اليوم إن شاء الله نكمل برضه في ال syntax analysis
كنا المحاضرة الماضية حددنا إيش المواضيع اللي بدنا
نغطيها و بدنا .. غطينا .. حددنا إنه نحكي في ال
introduction context free grammars و ال writing
grammar و ال top-down parsing و ال bottom-up
parsing و ناخد introduction ل simple LR parserالان
احنا غطينا سنة و مراتين حتى الان اللي هو section
4142 و صرتنا على web اللي هو 4 3 writing a grammar
ف writing a grammar بنشوف قضيتين أساسيات يجب أن
ناخد .. خدوا في عنوان عطوار عند كتابة كتابة هنا مش
بمعنى كتابة ال code بس بمعنى تصميم ال grammar بعد
هي كبنشوف كيف عمليا بيصمم .. بيشتغل ال parts of
top down و كيف بيشتغل bottom upفبدنا نروح على طول
على section أربع تلاتة كان آخر إشي جابل أربع تلاتة
اللي حكينا فيه اللي هو ال derivation ال derivation
إذا بتذكروا ال derivation و ال .. و building القاس
trees و ربما
هذه النقطة ماوقفناش عندها خلينا نحكيها فيها على
السريع وهي إن كيف أنت تستطيع .. احنا شوفنا قبل هيك
ال regular expression كيف بن ..حولوا الى NFA ثم
بعد ذلك DFA الآن احنا ممكن نعمل الاكس من ال NFA لل
grammar يعني لو عندي انا NFA موجود و مش موجودة ال
grammar بقدر من ال NFA اكتب ال grammar اكتب ال
grammar يعني على سبيل المثال عندي ال
NFA يحتوى على states I1, I2, I3كل state فيه لها
edges بتودع على الأخريات صح ال edges label عليهم
labels ال labels هذه عبارة عن alphabet characters
مظبوط قول مثلا a قول مثلا b قول اي اخر تاني ال M
you can build أو تكتب ل grammar مبين على ال NFA
اللي عندك كل state عمال ال states هنا مرقمين
بأرقامكل state بتعمل إليها non-terminal لإيديك
state 1, state 2, state 3, state 4 إلى آخره فبتعمل
non-terminal لهذه non-terminal لإيديك نعمل non
-terminal لإيديك الأخرى لكل state non-terminal
خلينا زي ما هو هنا ماشي عمل الأسامي ال states
سميهم
ايه1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14
a15 a16 a16 a17 a18 a19 a21
a22
a23 a22 a23 a23 a23 a23 a23 a23 a23 a23 a23 a23
a23 a23 a23 a23 a23 a23 a23 a23 a23 a23 a23 a23
a23 a23 a23 a23 a23
a23 a23 a23 a23 a23 a23 a23 a23 a23 a23 a23 a23
a23 aبتخيل انك تشتغل ك algorithm ال diagram مش
مضرور يبقى موجود اللي موجود هو ال table تبعه مش
موجود بيه أنه ال table ال transition table هنا ال
states صح؟
و هنا ال alphabet symbols فانت لكل state لكل state
دلوقتي for each state we createالانتظار الى if
state i هذا ال transition to state j إذا في من
state i transition بيوديني على state أخرى عبر واحد
من ال alphabet characters افترض هنا هذا مثلا ال c
بيقولي اذا انت على one وجهك c بتروح على تلاتة يبقى
الآن في transition من واحد إلى تلاتة عبر c هذا ال
transition يظهر عنه على شكل ruleif state a has a
transition into state j on input a الrule هي اللي
بتكون هي ال non terminal ai يؤدي إلى او can have
the form بنحط بنحط ال character ثم ال non terminal
تبع ال state اللي يؤدي اليها اللي هي aj okay
هنا هو في المثال هذا جاي small a انا عندي هنا
small c okay يمكن بحط ال .. بحط ال character ال
input symbol كhead لل body تبع ال production و
باقي ال body هو مين اسم ال non terminal تبع ال
state الوجهة ال destination و ال state المصدر اللي
هي ال source state هي ال head تبع ال production
الهيد بتبع ال production الآن
إذا في عندى هنا في ال table إبسلون و بقول من اتنين
ممكن أروح على أربع عبر إبسلون بقول a2 إلى a4 على
طول a2 can have the form a4 ليش
واضح الإبسلونطيب هذه ليه .. مش واضحة هذه .. هذه
تعادل هذه بس انا حاطط C و هو حاطط A في الآخر ايه
ال character اللي عندك ال input character AI اللي
هي واحد من هنا من ال states AI بالظبط تؤدي إلى AJ
عبر ال character هذا تفكر فيها هاي واحد افرض انه
تلاتر هاي تلاترعلى حسب هذا ال diagram لا يوجد شفرة
فانا اعملها من 1 الى 3 عبر ال C فيه edge ماشي الان
ال C التلاتة فاكر انه لسه في باقي لل NFA و states
أخرى و ربما symbols أخرى و بعدين في الأخر ربما هنا
states هذي أربعة و هذي أربعة و هذي خمسة و هذي ستة
و هذي ستة final
الأمر هنا أنت بتقول AI اللي هو هذه can have a form
CAJ لأن لاحظ أن هذه التلاتة هي أسطحات ال body تبع
ال production انت تخيل ال body تبع ال production
عينيه هو ال B و ال D أما تخيل أن هذا النمط يرمز
إلى مجموعة ال input signals اللي ممكن نتوقعها بعد
هذا ال stateفهذا هو عبارة عن مجموعة السيمبولز اللي
جايين بعد ال state هذه وصولها إلى ال f إلى final
وإن هذا هو المقدمة لهذه ال sequence كما نقول إن
وجودنا هنا موهج لإنه يجينا هذا ال input
السؤال ايه؟ طب انا جيت لو كان مثلا من واحد لاتنين
ع طريق ال a من واحد لاتنين ع طريق ال a عادي هعمل
ايش؟ a واحد يودي الى can have the form a اتنين
فجيت منهم اتنين و غرضه هكمل انه يودي الى تلاتة انا
لكل النمط ده بس هعمل لهم productions انا بقول هنا
if said I has a transition فهألف عليهم كله my
statesهذا ال states و اشوف كل واحدة من ال states
ايش ال transitions اللي تبعتها ايش ال edges اللي
بتودي علي مين و اعمل الان اذا عندي if a if
i is an accepting state زي هذه مثلا ايش بس اوي
اعمل
production a6 an accepting stateالنمط التبعها a6
a6 يمكن أن يكون مصمم أبسلون و طبعا ال start state
بعمل ايش بعمل ال start
symbol ال node اللي هي start node النمط التبعها
start symbol
فبتكون معايا مجموعة productions على أساس هذا ال
NFA طيب نهاية أربعة اتنين احنا لان جايين عشان نفضى
في أربعة تلاتة نهاية أربعة اتنين في مجموعة من ال
exercises ضروري تتابع عليها لأنهم ممكن
تيجي منها او مثلها في الامتحان الان موضوعنا الأول
اليوم هو writing a grammarwriting a grammar فيها
على طول بدأ أدخل على مسألة ال ambiguity و how we
eliminate ال ambiguity ال ambiguity هنا لدينا مثال
ال production هذه او ال non terminal هذا statement
ممكن تبقى f statement او غير ذلك بس احنا بدنا نطلع
بس على حالة لما نكون f statement الآن الصيغة هذه
الصيغة هذهفي هذه سيرة then سيرة then معاها else
ماشي ال statement ممكن تجيلها حلقة أخرى F ولا مش F
يعني فالان لما يكون في هن دي input جايب بالشكل هذا
F expression one then فال past three تبع هذا ال ..
هذا
ال statement هتكون على هذا الشكل صح؟هنا في عندي
هذا ال
f و ال e واحد و ال then و ال s واحد و ال else تمام
هدولة هم ال children تمعون statement الشاملة كليا
و بعد يكمل هنا هدولة يعبقوا عن sub statement جوا
جايين جواب ال else وهي ال parsing طبعا
الان في اي مشكلة هنا لأ يعني logically و
syntactically الأمر صحيح لأنه خلاص هذه ال else
مخدة ال F معروف ال F تبعها ومعروف معاها كله هو
جواب ال else اللي هي هذا ال else تبعت ال F يعني
لكن احنا ممكن نبقى في عنا اشي زيك اه
في شي زي هيك اه
بلا احس انه احنا معانا ال grammar هادى معانا ال
grammar هادى ايوة a statement can have the form if
expression then statement و if expression then
statement else statement
طبعا أكبر فانا الآن هذا ال grammar لما يجيني ايش
زي هيك اف expression و بعدين ثاني و اف expression
ثاني و then و اس و statement و else و statement
يعني two if و else واحد ممكن أنظر إلى ال grammar
على أساس أنه كل هذا هو جواب ال then هذهجملة F
مكتملة وهي ال F وهي الذن تبعها وهي ال S تبعها صح
هذا واضح وممكن اقضها على اساس انه ال ال S دي تابعة
هنا وبالتالي هذه هي جواب الذن ال S ال F الأصلية
وال statement S2 جواب ال S هذا الآنهو ال option
الأولى الخيار الأولاني وهذا الخيار التاني اللي هو
أيه فأجه هذا ال if و ال then ال if و ال expression
و ال then و ال statement أجوا جوام ال then و
الباقي تكمل لل statement الأصلي هذي ambiguity ولا
لأ هذي ambiguity ال grammar سمحت بذلك أعطت مسلكين
لنفس ال input string
ال Grammar دي تعديل على الأصلية عشان يمنع ال
ambiguity بنحس أنه اجهز احنا بدنا .. بدنا دايما
نلس مع
ال F اللي وراه كيف؟ هنا في اندي انا match
statement و open statement تفهمهم كتاري open يعني
مفتوحة يعني إيش؟no is افهمها كتر يعنى و ال matched
اللى هى with is ال is معاها طبعا ال ال ال يعنى if
then و else فالان اذا كان عندي انا استيد ال
expression هي ده وينه هيته ده اكتبوا تحت هناif E1
then if E2 then S1 else S2 بناء على هذا الـ
definition الآن بناء على هذا ال grammar
أنا هذه البندورية اللي هي ك statement هتكون إما
matched أو open عشان تكون matched لازم تنطبق على
هذا الصيغة وإلا فهي open عشان تنطبق على هذه الصيغة
لازم يحتوي على else واللي جابني ال else لازم يكون
matched
واللي بعد ال else يبقى أيضا match إيش يعني matched
يعني معاه ال else تبعه ما إحنا إيش ميزنا ال match
في else و ال open مافي شي في else okay فإذا والله
أنا بدي أجرب هذه أخش okay if موجودة expression
موجود then موجود okay لازم يكون express موجودة إذا
بدنا نكمل في هذا الاتجاه لازماللي بعد ال else يجي
statement و تبقى matched و اللي جاب لل else ما بين
ال else و ال then يبقى statement و أيضا يبقى
matched لو
ما حصل هذا الكلام يبقى هذا ال option غير valid
يبقى إلناش إلا مالناش إلا الإحتمال والاخر فتطلع
على هذا هل هذا يلبي ال definition تبعهmatched لا
يلبنى لأن ال match بدها else وهنا fe2 then s1
ومافي else ال else بتاع خلت الخلق صح ولا لأ احنا
هنا اتسكر المسلك اللى كان حامل ambiguity واحد من
المسلكين يعنى وبالتالي ماضلش الا المسلك واحد
وبالتالي مافيش ambiguityأصبح هذا ال rule لا تنطبق
على هذا ال rule ماهو البديل عنها؟ مافيش اللي هم
الثانية دولة ك statement مافي إلا matched أو open
البديل أنه أخدها لو أخشها open هل هذا هينطبق؟ لأ
مش هينطبق لأن في end else يبقى هذا لازم ينطبق
open لأ هو هذا اللي هينطبق عارف ليش هذا اللي
هينطبق لأن هذا اللي هتيجي كلها هاي ال if و هاي ال
expression و هاي ال then و ال statement هذي هتيجي
كلهاشوف ارجع تاني لو هذا مضيش ينطبق ينجح هذا اللي
لازم ينطبق طب هذا عشان ينطبق بده S جيد هي الموجودة
لكن الجامعه ال S لازم يماشي وهذا مش متحقق فاحنا
الآن مابناش لهذا وهذا فعلا حيثبت لسه لأنه هتجهلكم
لهذا ال statement و ال statement هذه هي أبقى match
statement match statement match
statement تحتوي علىتحتوي على F وتحتوي على else صح؟
فأحد هيك بالطريقة هذه ما أغلق أحد المصارمين اللي
دي كان و بالتالي ضال واحد و بالتالي مافيش
ambiguity تمام هذا بالنسبة لل ambiguity فانت الآن
على أحد القضايا اللي انت و مش هتلاقيSoftware tool
اللى تريحك من هذا التحدي انت صياجدك لل rules لل
grammar أسف لل grammar بتبقى خالية من ال ambiguity
بعد ما تصيغر ال grammar بتروح بتدخلها على ال
generator tool عشان ال generator يعمل لك ال parser
نقطة تانية هذه النقطة الأولى كانت ياش ambiguity
النقطة التانية اللي هي left recursion left
recursion انه احنا نلاقي ان يبقى في عندك في ال ..
وهذا .. وهذا كان موجود معانا طول الوقت بس احنا
ماكناش ندجك طول الوقت كان يبقى في كل ال grammar
اللي مرت علينا كان فيها left recursionلما يبجى ال
non terminal نفسه يظهر كهد لل body تبعته ال body
تبعته ال production تبعته هذا اسمه left recursion
حيث ال E هنا يظهر هو نفسه و اللي تحته و اللي تحته
تمام؟ هذا مشكلة ليش مشكلة؟ لأنه اتخيل انت عامل لكل
واحد من ال non terminals هده عاملهم ال recursive
descent function تبعتهrecurse of descent يعني ال
function بتستدعي نفسها بنشوف احنا اي E بروح نستدعي
ال function تبع ال E ال E هذه بتبدأ تاخد ال
children تبعه من ال E هتشوف اول child مين ال E
هتروح تستدعي نفسها بعد ما تستدعي نفسها هتروح على
برضه ال production هي تعمل عليها children وتلاقي
دايما عندي بالغرب ال Eأول و أحد فهذا استداء ذاتي و
infinite مظلوم بتنمية بالمعنى فلازم يزال ال left
recursion هذا okay فالقاعدة العاملة اللي هي أنه
لما يمكن في أندي left recursion زي هيكا هي اتوا a
has the form a مطبوعة بصم .. مطبوعة بصم ايشsome
sequence of symbols الألفة هنا بتتذكروا لما كنا
بنحكي في ال convention كنا بنقول أننا
بنستخدم ال Greek letters small small case أو lower
case Greek letters للإشارة إلى إيش إلى مجموعات ال
symbols أو سلسل ال symbols يعني ال sequenceاللي هو
كيس كريت كلترز Alpha و Beta و Gamma to represent
اللي هو strings of symbols و هاد ال strings of
symbols هاد
ال strings of symbols ممكن تبقى اياش terminals و
non terminals خليط فانا كان انا هنا لما اقول ايه
capitalالفة يقصد بيها أي شيء اي sequence of
symbols صح يعني
هنا تطبق
هذا الصيغة على هذا الكلام E can have the form E
plus T
وهي ايه؟ وين الفة؟ الفة هي plus صح؟ يقصد هي
sequence of أي combination of terminals و non
terminals لو إذا في عندي إيش زي هذا الحالة أستطيع
أن أصلح هذا المشكلة هذا المشكلة ليش؟ لأن ال non
terminal جايفي رأس ال body تبع ال production تبع
الترميلاني تخيل
أيضا أن هو نفسه another production ليس فيها مشكلة
نسميها نرمز لل body تبع ال production الأخرى ب
Beta Beta هو ال body تبع ال production تبع ال
production الأخرى لأ نفس ال non terminal مافيهاش
left recursionاستناد الى وجود هذه ال production
الأخرى أستطيع أن أعالج مشكلة left recursion بإنه
أستحدث نمط من الآخر أسميه A' و أقول ال A ال A أحول
هذه إلى إيش إلى واحدة أخرى بجيب ال beta اللي مافيش
فيها أي مشكلة و بحط A' بعدهابعدين a prime بعرفه
على أنه هو ال alpha مطبوعة ب a prime و
بحط ال production جديدة epsilon يعني
بالزمن
يكون في production أخرى مافيش فيها مشكلة هذه ال
production فيها مشكلة بالزمن يكون في واحدة أخرى
مافيش فيها مشكلة عشان أقدر أقالجطريقتي للمعالجة ان
انا باستحدث non terminal جديد لان ال production
الأصلية اللى بتبدأ بال A بجيب ال A و بجيب ال body
السليم و باتبعه بال non terminal مستحدث هذا و هذا
المستحدث بروح بقرفه على ان هوالـ body الـ
remainder الـ remainder يعني الجزء الباقي من ال
production اللي فيها مشكلة مع هو نفسه ثم في الآخر
بضيف production epsilon يعني قبلت الكلام هذا على
ال E قبلت الكلام هذا على هذه ال E كنبة form E plus
T اتفقنا على انه هذا هو ال A وهذا هو ال Aوهذا هو
ايش ال alpha وين ال beta؟
وين ال beta؟ ال beta لازم يكون فيه production أخر
لل E مافيش فيها left recurrent طب نفترض أنه مافيش
فيها ماقدرش طبعا ماقدرش تمام؟الان هنا في الـ
Grammar الأمامي في اندى production في Beta في الـ
T نعم الـ T هذا الـ T لحالة هي ال Beta خلاص الان
كيف بتعالج بجيب ال E و بقول E بحط ال Beta مطموعة
بالمستحدث اللي هو E Prime المستحدث هذا ياخد Alpha
اللي هي إيش Alphaفهي عندك Z و T ايوة Z و T باتبعه
بال E Prime ثم في الآخر او
بحطه او بحطه هياته عامل الكلمة هذا لأ ال E Prime
فهياته ال
E Prime ال E Primeأه انا حاطط ايه هاد لازم تبقي
اوه اوه اوه اوه اوه اوه اوه اوه اوه اوه اوه اوه
اوه اوه اوه اوه اوه اوه
اوه
اوه او
مش جاهز كبداية ال body كبداية ال body ده أيه بقى
okay كويس okay هذا الأن ال left recursion in
general بقدر أعمم القضية هذه ليه بقدر أعممها يعني
غالبا غالبا بغير أن اني بس مجرد واحد فقط اللي فيها
left recursion ال non terminal يلو خمسة ستة عشرة
productions بعض منهم في left recursionو بعض ..
يعني ممكنش فيه أدى Beta واحدة أكتر من Beta Beta
هدول اللي مافيش فيهم left recursion نفس اللي مات و
بعض أخر فيهم left recursion ف in general لو عندى
أنا non terminal و فيله مجموعة من ال productions
هذه one production another production و هدول ال
productions فيهم left recursion و أخريات مافيش
فيهم بقدر in generalعمّم المعالجة بقول انه بجيب ال
betas كلهم وبالحم بيهم بلصق بيهم المستهدف اي beta
واحد معاها a prime beta اتنين a prime لها اخر beta
ثم a prime هذا المستهدف بجيب الالفز وبحطه حسب ال
وراهم هم طبعا عددهم مختلف نقول عن عدد ال betas صح؟
وهي ال .. okay هذا السلوب معالجة اللي هو ال left
recurge ايوة في الأخر بالظبط في ال .. okay فالان
هذا الكلام لسه جزء من مشكلة ال left recurge هذا
بنسميه immediate left recurgeممكن ال left
recursion يبقى متخبي،
مبطن، مؤجل، كيف يعني؟ يعني مثلا هنا، ال grammar
هذه، في عندي left recursion واضح حياته، هذا
immediate، صح؟ لكن في left recursion أخر مبطن،
اللي هو لو أحنا جينا وقلنا ال Swe derive من S we
derive A capital A plus ثم بعد ذلك هذا non
terminal بنستبدله بواحد من ال production سبعتين
اللي هي هذه شيلنا
ال A و حطينا S D أصبح عندي S D و بعدين ال A small
نزلت هذا lift recursion ولا مش lift recursion
الـ S تستدعي نفسها مرة و مرة و مرة
أنا لازم أخد بالي منه هذا الخفي ال left recursion
الخفي و أعالجه ففي أن هنا ال
algorithm هذه ل eliminating left recursion عموما
بصفة عامة بصفة عامة فإذا كان وجد immediate ولا إذا
وجد
الأيجاروفم هذه بتاخد ال grammar على علّاتها و
بتطلع لنا grammar خالية من left recursion ال
output is an equivalent grammar with no left
recursion الأليه تبعتها أننا بناخد ال non
terminals كلها اللي في ال grammarال grammar تبعتنا
هي ناخد هذه على سبيل المثال هاي ال grammar هذه
نكتبها هنا على جانب هاي ال S S
can have a form ايش A capital A small و
برضه ال S can have a form ايش B بعدين A can have a
form A capital CA can have the form S D و A can
have the form Epsilon نشلها لأن ال algorithm هذه
بتقول لي خد كل ال non terminal اللي عندك و رصهم في
ليستة اكم non terminal عندي انا هنا في هذه ال
grammar خمسة ستة اقل اكتر اقل من خمسة اتنين ال S و
ال A ال S capital و ال A capitalهؤلاء اللي لم
انتهى من عزيزي عندي برصهم من الطبيعي نبدأ بال
start symbol و بعدين ايش اللي بعده فيه غير مفيش
يعنى بتقولي الأن تاخد الأولاني و
تبص على اللي جابله الأولاني هذا مفيش يجابله انسى
الحكاية تكلها خد التاني و بص على اللي جابلهإذا
وجدت التاني هذا اللي أنت واقف عليه هل اللي أنت
واقف عليه بنسميه I واللي جابله قد يكون عندي أربعة،
تلاتة، اتنين، واحد، خمسة، عشر، عشرين، كل واحد منهم
بنسميه J أنا عندي بس هذا هذا J هذا J إذا بدك تطلع
على ال production سبعة Iإذا لجيت واحدة منهم جاي
بهذا الشكل جاي
بهذا الشكل لإنه A لإنه
J جاي head للبقية تبعها أنا قلت له بدك تجه، فيه
عندك مشكلةالـ a, j و ال a, a, a, a, a, a, a, a, a,
a, a, a, a, a, a, a, a, a, a, a, a, a, a, a, a, a,
a, a, a, a, a, a, a, a, a, a, a, a, a, a, a
إذا وجدت واحدة منهم يظهر هذا في على رأسها فهناك
مشكلة وهذا متحقق هنا لأن
هذه مشكلة lift recursion مبطن أو مؤجلبداك تعالجها
كده بداك تعالجها هاي المعالج تبعها بس احنا متفقين
على انه AI هذا يرمز الى اللي نطلق من هنا ونفعل ال
M وAJ هو واحد من اللي جابله واحد من اللي جابله
اللي احنا .. okay؟ و جاي .. هذا اللي جابله جاى
للواس body ل production ل .. من تابونها هذا AI هذا
AI ممكن يكون له زي ما قلت اده من ال productionsو
يبقى هذا جاي في واحد منهم او في اكثر كيف نتعالج
اعتبر الان اعتبر الان انه هاي ال a قولنا و كان هذا
form S و الباقي اعتبروا هذا ايش قولنا جامع جامع
الان ال S نفسه بلّه على ال production سبعونه ال
production سبعونهاعتبارهم كله sigma small 1 sigma
small 2 sigma small 3 دور كل production سبب ال S
هذا انا هنا انا اكل واحد انهيأتهم هذي sigma
small 1 و هذي sigma small 2 صح؟
دعوني اقول ايه ايه
مظبوط الكلام؟ بدك تجيب الآن الـSigmas كلياتهم و
تحط وراهم الـGamma هذه ال production اللي فيها
المشكلة صح؟ هذه ال production اللي فيها المشكلة و
لا هدولة؟ هدولة هي هدولة بدك تروح تستبدلها بعدد
يساوي هدولة بعدد من ال production هي اللي بتلتج و
تستبدل بـA can have the formبتجيب السيجما الأولى و
تلحقها بجرام السيجما الثاني و تلحقها بجرام جرام
خلاص هاللي تروح و تستبدل ب .. بقداش ريالنا
productions لل S فهو
بيقول لك replace each production of the form كذا
كذا هال production إيه؟كامن فيها الخلد replace it
by the productions هدولة حيث ان .. طب ال sigma ..
يقول يحط sigma طب من انا اجيب ال sigma ال gamma
هيتها ال sigma من اين؟ بتجيبها من ال bodies تبعون
AJ AJ هو مين؟ ال S صح؟ خلاص؟ طيب؟فاستبدل هتنطبق
هذا الكلام على هادي مش احنا قلنا هادي ينطبق عليها
الأمر الان هاي ال S و هاي الجامعه ال D لحالها هى
الجامعه جامعه مستوى ال D ليش بقولي بقولي استبدل
هادي بمجموعة عدد جديش عدد اتنين الأولى حط sigma
واحد هي A capital A small ثم اتبعها بD والتانيةالـ
B و اتباعها بالـ D حلو؟ حلو؟ مش حلو على الآخر ليش؟
في هن دي الان immediate left recursion بقول لي
خلاص، ببساطة شديدة eliminate ال immediate بالطريقة
اللي اتوا حكينا فيها قضية ال Alpha و ال Beta خلاص؟
بس الأول لازم أنتبه على ال non immediate left
recursionعلشته نتج عنه immediately خلاص بنعالجه
احنا القلم الذرع اللي تبقى نهار بسيط لأنه مافيش
فيه الا two non-terminals ده كده إذا عندك grammar
كبيرة هتبقى فيها عشرات ال non-terminals و بدك تلف
عليهم بالقالية هذه و مش أنت طبعا ال generator هو
اللي هيسوي هالكلام انت كل اللي عليك تكتب ال
grammar
لأن هو بعد ما هو مسوي الكلام هذا لما أنا أجيب و
أعالج ال left recursion هنا عادة أسجل ال immediate
left recursion هاي خد عندك هذه سليمة هذه okay
مافيش فيها مشكلة هذه أتبعها الآن beta لإن أنا
أعالج ال immediate left recursion هذه الألفة
صح وهذه ال beta كيف نعالجهم؟بنقول a can have the
form beta مطبوعة ب alpha prime a prime بي دي a
prime و بعدين a prime بيساوي بيساوي
ال alpha بيساوي ال beta
صح بعدين Beta A'
A صغير بعدين Epsilon خلّي
بالك انه احنا ال A,C,H,D اصلا موجودة في ال grammar
بيقولها على حياتنا صح بس تخدملها عشان .. اه لأ لأ
اشي اللي بيصيريصير انه لما احنا وين المشكلة كانت؟
كانت في هادي كانت انتيجة من ال a هادي و هادي راحت
هادي محل و محل الاتنين هدوله صح؟ انتظر
شوية كان في اتار ابسلون في الاصل اه كان موجود هيته
صح؟تمام يبقى هم الأصل تلاتة واحد ثاني وجرم ثلاثة
هدول اتنين ويبقى صار عنها المجموعة الآن مجموعة ال
production سمعوني ال A هم هدولة الرابعة هدولة راح
واحد كانوا تلاتة راح واحد وجرم ثلاثة هدول اتنين
صار الرابعة الآن أنا في عندي .. بتطبق ال general
case ال immediate case بتنتهي عنديتنتقم فيهم
immediately فهذا ألف واحد وهذا ألف اتنين وهذا beta
واحد وهذا beta اتنين ايش أسوي هاي ال a أحط ال
alphas و بعدها ال a prime تمام هاي ال alpha الأولى
و بعدها ال a prime صحيح
بعدين ال A' لأ
احنا بقولن ال betas و بعدين ال A' ال betas و بعدين
ال A' ال BD A' بعدين ال beta التاني اللي هو هذا و
بعدين ال A' epsilon بعدين A' A' صح؟ okay
بعدين ال A'ياخد ال form ايش ال alpha بعدهم a prime
ال alpha هي ال alpha الأولى بعدها a prime بعدين ال
alpha التانية ال d a prime بعدين
مع ال a prime بنساش أحق في الآخر الأفصل مصبوط هذا
ال N هو هذا
صح ال production سبعت ال S بلغهم زي ما هم مرة
أخرى ال A جبنا ال betas و حطينا ال beta الأولى و
حطينا بعدها A prime ال beta التانية اللي ال
epsilon و بعدها A prime خلاص ال epsilon لمهيشي في
الأول
الأولى كانت ال ambiguity النقطة
التانية اللي هي lift
recursion مفت التالتة left factoring left
factoringأبسط .. أبسط حاجة في التلات نقطة يقصد بي
أنه لما يكون فيها Indiana statement هي نفسها اللي
شوفناها في الأول اللي هي طبعا ال F statement مافيش
فيها ambiguity ولا فيها left recursion ولا فيها
left recursion عندها يعني هي statement مش جاية
كبداية للهدف إنما فيها left factory
نفس ال prefix هذا ظاهر معاك في ال production
الأخرى في قاسم مشترك ما بين two productions نفس ال
symbols if if expression expression then then
statement statement بقى الهدف المختلف فبناخد قاسم
مشترك factoring لما نعمل factoring ناخد قاسم مشترك
فالسيئة لأنه لو عندي أنا ننطق من الالو two
productions واحد من المشتركين مع بعض في جزء
ومختلفين في جزء الأخر Alpha متكرر في ال two bodies
و ال Beta واحد و بعدها Beta اتنين و مختلفة عن ده
فببساطة شديدة بقول ايه بعيد سيارة بقول ايه بحط
Alpha و بعدين بستحدث non
terminal للشق المختلف A' هذا ال end can have the
formمرة beta واحد ومرة beta جميلة
تمام
فبصوفة اما ال
alpha هذا تصل لمشترك مش لازم يكون epsilon لازم
يكون فيه فعلا symbols اذا
there is
a non-trivial common prefix replace all of the A
productions طبعا ال A كلهم دولة غيرهم طبعا إذا كان
الجامعة كما هذه مافيش فيها أصلا قاصة مشتركة يعني
مختلفة تماما تغير بس ال productions طبعا ال ال
مافيش فيها ألفةبنغيّر بس اللي فيه ألفة بإنه إيش
يعني
هذه ال production ضلت هذه الجهة ضلت بس نغيّر مين
هدولة نحط ألفة في القاس المشترك و نعمل a' و ال a'
بيصير ال waiters كدهش في قد منهم هدولة
Okay هذه نفسها ال F نفسها بس بدل ما نقول F و
expression و then استبدل statement ب S مجددا
استبدلنا statement ب S كان هام ده form ال F
استبدلناها بsmall I و expression بال E و
then بالاش T capital ولا T small اكتبأنا باختصر
يعني بحط اختصارات ال F حطيتها بال I small و
expression حطيتها بال E capital then أحطها capital
T و لا small t لا تفرق احنا ليش وقفنا على ال
convention قولنا ال small letters بيستخدمها لل
terminals و ال capital letters بيستخدمها لل non
terminals فهذه expression non terminal
القسم المشترك هو
الوظائف الوطن
اللي هي ال A ال production أخرة يعني A هذا اختصار
ل other يعني لأي حاجة فهذا في left factoring صح
مستبدله و مستفدله أخذ هذا الكله للقاس المشترك هذا
الكله و أتبعه باش ب S' و نزل ال A زي ما هي ال S'
الآن هو ما تبقى ESأبسلر هذا من أين أتيت و أحظ أنه
أنا عندي هذا هو beta 1 و هذا beta 2 هو ال epsilon
صح ال
E هذه مافيش فيها مشكلة تنزل زمانخلاص احنا هيك
عموما بنكون انهينا اللي حاكيه عن section تلاتة
اربع اربع تلاتة اللي هو القضايا اللي يجب انك انت
تاخد بالك منها عند كتابة writing او grammar ماحدش
مافيش tool اللي تغطي تسد عنك في هذا الأمربعد هيك
الآن في ال 4.4.4.5 بشوف ال top-down 4.4.4.5 بشوف
ال top-down parsing كيف بيتم قاليته يعني احنا شفنا
مقدمة إلها في السابق بشوفها عمليا و بعدين بشوف ال
bottom-up ان شاء الله يعطيكم العافية