بسم الله الرحمن الرحيم السلام عليكم أيها المسلمون نبدأ
اليوم إن شاء الله نكمل برضه في ال 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 الـ parse
trees و ربما
هذه النقطة ما وقفناش عندها خلينا نحكي فيها على
السريع وهي إن كيف أنت تستطيع .. احنا شوفنا قبل هيك
الـ regular expression كيف بن .. حولوا الى NFA ثم
بعد ذلك DFA الآن احنا ممكن نعمل الـ convert من الـ NFA للـ
grammar يعني لو عندي أنا NFA موجود و مش موجودة الـ
grammar بقدر من الـ NFA اكتب الـ grammar اكتب الـ
grammar يعني على سبيل المثال عندي الـ
NFA يحتوي على states I1, I2, I3 كل state فيه لها
edges بتودع على الأخريات صح الـ edges label عليها
labels الـ labels هذه عبارة عن alphabet characters
مظبوط قول مثلا a قول مثلا b قول أي شيء آخر تاني الـ
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
سميهم
a1 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 يظهر عنه على شكل rule if 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
الـ head بتبع الـ 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 فهذا هو عبارة عن مجموعة الـ symbols اللي
جاين بعد الـ 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 grammar writing 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 لما يجيني إيش
زي هيك if expression وبعدين ثاني و if expression
ثاني و then و S و statement و else و statement
يعني two if و else واحد ممكن أنظر إلى الـ grammar
على أساس أنه كل هذا هو جواب الـ then هذه جملة if
مكتملة وهي الـ if وهي الـ then تبعها وهي الـ S تبعها صح
هذا واضح وممكن أقضّيها على أساس أنه الـ S دي تابعة
هنا وبالتالي هذه هي جواب الـ then الـ S الـ if الأصلية
والـ statement S2 جواب الـ S هذا الآن هو الـ option
الأولى الخيار الأولاني وهذا الخيار الثاني اللي هو
أيّه فأجّه هذا الـ if والـ then الـ if والـ expression
والـ then والـ statement أجوا جوامع الـ then و
الباقي يكمل للـ statement الأصلي هذي ambiguity ولا
لأ هذي ambiguity الـ grammar سمحت بذلك أعطت مسلكين
لنفس الـ input string
الـ Grammar دي تعديل على الأصلية عشان يمنع الـ
ambiguity بنحس أنه أجهز إحنا بدنا.. بدنا دائمًا
نلس مع
الـ if اللي وراه كيف؟ هنا في اندي أنا 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 لازم يكون expression موجودة إذا
بدنا نكمل في هذا الاتجاه لازم اللي بعد الـ else يجي
statement وتبقى matched واللي جاب للـ else ما بين
الـ else والـ then يبقى statement وأيضًا يبقى
matched لو
ما حصل هذا الكلام يبقى هذا الـ option غير valid
يبقى إللناش إلا مالناش إلا الاحتمال الآخر فتطلع
على هذا هل هذا يلبي الـ definition تبعه matched لا
يلبّي لأن الـ match بدها else وهنا if E2 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 تحتوي على تحتوي على if وتحتوي على 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 ان شاء الله يعطيكم العافية