بسم الله الرحمن الرحيم الصلاة والسلام عليكم ورحمة
الله ورحمة الله ورحمة الله ورحمة الله ورحمة الله
ورحمة الله ورحمة الله ورحمة الله ورحمة الله ورحمة
الله ورحمة الله ورحمة الله ورحمة الله ورحمة الله
ورحمة الله ورحمة الله ورحمة الله ورحمة الله ورحمة
الله ورحمة الله ورحمة الله ورحمة الله ورحمة الله
ورحمة الله ورحمة الله ورحمة الله ورحمة الله ورحمة
الله ورحمة الله ورحمة الله ورحمة الله ورحمة الله
ورحمة الله ورحمة الله ورحمة الله ورحمة الله ورحمة
الله ورحمة الله ورحمة الله ورحمة الله ورحمة الله
ورموضوع ال parse trees كيف أننا نشكل parse tree من
خلال بعض ال derivation وأيضا نشوف المفهوم ال
ambiguity اللي هو اللبس يعني بمعنى أن نفس ال input
ممكن يتعمل أكتر من ال derivation وكل derivation
تفضي إلى parse tree مختلفة وكيف أن هذا الكلام ينتج
عنه semantics مختلفةيفسّه إذا فُسّر هيك بينتج
value تبعه شيء مختلف عن لو تم تفسيره بشكل آخر بعد
ذلك برضه كمان اتناولنا الموضوع ال associativity of
operators و ال precedence of operators فعملية احنا
انتهينا من section 2.2 يعني الشيء بدنا نتجل الان
إلى section2.3 هو syntax-directed translation
syntax-directed translation بنشوف مثال مبسط جدا
على كيف بعد ال syntax analysis بيتم أو أثناء برضه
ال syntax analysis ممكن ينعمل شكل من أشكال
translation translation بمعنى تحويل ال input إلى
ال output المضلوبماشي بس هذا اشي مبسط جدا بس عشان
يوضحك الفكرة انما عملية ال compilation فيها
تعقيدات اكتر من هيك فانا الآن بدي امر على اللي هو
بدي انتقل الى section 2.3 اللي كله مرمين عليه
المحاضر الماضي في نهاية ال section 2.2 في
exercises انا هنا بس حاطت بس اتنين منها two two
one و two two twoفي لغاية الـ 2.2.6 بنصحكم تطلعوا
عليها في وقتكم على سبب انه تمارنوا على مسائل ممكن
يجي مثلها في الابتحانات الان ال section 2.3 اللي
هو syntax directed translation نشوف مثلا زي ما قلت
على translation بيكون syntax directed بمعنى انه
موجه او based على ال syntax analysis حنشوف مثلها
على درجةلو انا عندى هنا هدى ايش production صح ال
production بتقول انه ال expression can have the
form expression زي ال term صح okay الان هدا ال ..
هدا ال expression احنا .. او هدا ال translator
اللى بدى يترجم عاملا ايش بتسوي؟ بت .. بت .. اذا
بتعرف حاليا اسمها post-fixed notation هي كل واحدة
انا مش عارف أسألكموفي انفكس نظروا انفكس لو انا جيت
عندي اشي زي .. زي
هيك دي اضغطه في الصلاة دالي في عندي expression زي
هذا و بدى احاوله هلاقاش انفكس و لا postfixهذا a
fixed من أين جاء المصطلح هذا ان ال operator اللي
هو الناقص والزائد جاء inside ما بين ال operands
اللي هم التسعة من ناحية والخمسة من ناحية واضح لو
بدي احاول ل post fixed بحط ال operator بعد ال
operands يعني بتجيب التسعة و بحط ورا ال خمسة و
بعدين ايش الناقص زيك عمليا هذا ال expression كله
بتحول إلى تسعة و خمسة ناقص اتنين زائد تمام تسعة و
خمسة ناقص هدولة الناتج تبقى هون بيصير هو ال over
end التاني مع الاتنين لعملية الجمع okay فالان
فاكري بدنا نعمل translator اللي تلقائي اللي هعطيه
انفيكس expression بديش يحسبلي كده قيمته انه تسعة و
ناقص و خمسة زائد لأ بدي احولليه الى postfix ليش؟لأ
يعنينا لأ ربما نعطيها stack ماشيين علشان تحسبوا
اللي لأ المهم ان احنا بظيفة ال translator اللي
بدنا نحكي عنه هي انه يحول من ايش الى postfix
بالظبط فالان انا برجع جوا في ال slides ال slide
الأولى اللي كنا فيها الان expression نفسهالـ
Definition تبعه هو عبارة عن expression زي ال term
أو expression ناقص term مظبوط فلو كان عندي ال rule
هذه ال production هذه expression زي ال term لو كان
عندي expression و كان فعلا اشي زيك مثلا فهو
expression زي ال term صح التسعة اللي بتتاخد عليها
term و ال term بتتاخد عليها تسعة التسعة هي ال
expressionو ال expression هي ال term و ال term هي
ال digit و ال digit هي التسعة و ال خمسة هي ال
digit و ال digit هي الخمسة فال rule هذه او ال
production هذه بتطابق هذا ال input إذا عندي هذا ال
input يريد أن يترجم كيف؟ يريد أن يترجم إلى تسعة
خمسة ذات إيش معناه هذا؟ معناه أننا نحط ال
expression الأولاني ال expressionبنحط ال term ثم
بعد كده بنحط الزائد مظبوط؟ هذه الأن هذه
ال expression هذه قد يكون شيء بسيط زي تسعة و قد
يكون شيء مركب يعني ممكن يجي تسعة ناقص اتنين و
بعدين زائد و بعدين الخمسة في هذا الحالةفي هذه
الحالة ال expression لازم ارجع احلله او ال
translator لسه في الأول يحلله و يطلع الترجمة تبعته
و ناتج الترجمة تبعته ييجي ثم بعدين ناتج الترجمة
تبعة ال term ييجي وراه ثم بعدين الإشارة تزارك تيجي
في هذه الحالة كلمة translate expression هنا
معناتها إذا عندي هذه ال ruleمطبقات ايش هذا الشق
اللي expression one عالجه بشكل recursive او بشكل
nested يعني عالجه ال output تبعه للترجمة تبعت هذا
تنحط ثم خش على هذا عالجه الترجمة تبعته تنحطها
بعدين و بعدين هحط ال .. واضح من ال recursion الان؟
okay فهذا الأمر احنا الان بدنا نصيبه بشكلاللي يقدر
ال system هذا ال translator هذا انفظه برضه ال
attributes هترجعلها كمان شوية و ال slide هترجعلها
فاحنا الآن عملية الترجمة هذه بتخيلها عملية الترجمة
من infix ل postfix تخيلها كالتالي ان انا جينا لل
expression اللي هو تسعة ناقص خمس زائد اتنين و
عملنا له parsing سيبينا من ال tree هذهأنا بدي أكتر
.. بدي أعمل طريقة أبسط منها اللي هي انه ال .. ال
.. ال .. ال .. كله هذا ك expression اتحلل إلى إيش
إلى expression ناقص زائد term مظبوط ال expression
الأولى يعني اللي هو هلأ تسعة ناقص خمسة اتحلل إلى
إيش expression ناقص ناقص و term مظبوط ال
expression هذا اتحلل إلى termأنا من وين جامي بجيب
الكلام هذا مش من مخي من ال definition هذا اللي هو
احنا مر علينا محاضرة ماضية اللي هو وين كان وين راح
بعيد اتعنى كتير جبل
جبل صح هي اتولاد هذا مظبوط هي rules هذي انا مش
جامي من مخي بس انا تقريبا يعني ذاكرها special is a
term special is not a termو ال term هي عبارة عن
term ده و ال factor term هنا ماقلناش احنا في
الحالت وقتنا مش هنتقلب الى اي من هذا ال term is a
factor و ال factor can be a digit هنا ال term is a
factor و ال factor is a digit و ال digit is 9 هنا
برضه factor is a digit و ال digit is 5 و هنا ايش
برضه factor is a digit 2الان برجع ل slide اللى كنا
فيها نفس
الشيء بس اللهم ال term على طول مختصر هو ال term
ومعطيها digital يعني كأنه تجاوز عن التحليل هذا
بسيط بسيط زى ما هو بسيط و term على طولها
لأ تبسيط هذا الكلام مش .. تسعة .. مش انه يعني تسعة
خمسة اتنين .. تسعة خمسة اتنين .. تسعة خمسة اتنين
.. تسعة خمسة اتنين .. تسعة خمسة اتنين .. تسعة خمسة
اتنين .. تسعة خمسة اتنين .. تسعة خمسة اتنين ..
تسعة خمسة اتنين .. تسعة خمسة اتنين .. تسعة خمسة
اتنين .. تسعة خمسة اتنين .. تسعة خمسة اتنين ..
تسعة خمسة اتنين .. تسعة خمسة اتنين .. تسعة خمسة
اتنين .. تسعة خمسة اتنattributes وmethods اعتبر
عندك attribute اسمها T T هذا اختصار للترجمة كل
node عندك كل node لـ non-terminal اعتبرها object و
ال object هذا ايه له dot T attribute dot
T attribute هذه بتحملقيمة لـ Translation تبع ما
تحتها يعني الترم هذا اللي هو الخمسة إيش ال
translation تبع الخمسة لحالها هي الخمسة نفسها إيش
ال translation تبع التسعة
نفسها مافي translation للتسعة إلا هي نفسها بتتزن
زي ما هي هذا الآن ال expressionالـ T تبعه هي ال
translation تبع ما تحتها طب إيش ما تحتها هو بس هذا
يبقى هى نفسها بينما هذا ال T الترانسليشن تبع اللى
تحتها عبارة عن الترانسليشن تبع هذا مطبوعة بالإشعة
النقص مطبوعة بالإشعة النقص مظبوط يبقى ال T بتساوي
ال expression dot Tهنا بضع one عشان اميز ما بين ال
parent و ما بين ال child ده بقول expression one
expression
one و dot T و الحم وراها ايش هذا ال double bar
concatenation يعني الحم وراها ايش النقص ولا الخمسة
ال term dot T و الحم بعدها نقصالنقص كما هو على شكل
ال string أو ال character نفس الأشي هنا
بس بدل النقص الزائد برضه هنا بحط expression one
تمييز ان انا بحكي عن ال child
خطوة ممتازة الان ناخد هذا الكلام و نضعه مع ال
production بحيث ان ال parser يقوم بترجمة و يقوم
بترجمة في أنهي المعاهد نفس الواجهة اللي هو الكتل
أمسح هذا الكلام خلاص واضح هدولة
productions تمام هدولة شغل ال parser اللي بيسويه
بتناولهم عشان يعمل parsing في نفس الوقت اللي بيصير
في ال parsing بدنا برضه كمان يصير translation
هدولة productions هدولة إيش اسمهم rules semantic
rules ان هذا ال rule تعني ان ال نادش لل
translation بدي يكون هيكماشي .. امتى بيتطبق هذه ..
هذه بدأت تتنفس امتى بتتنفس .. لما يكتمل ال parsing
تبع هذا ال non-terminal بناء على هذه ال production
هذا ال non-terminal بناء على هذه ال production لما
يكتملها وجدت بتتنفس هذه ال rule تتنفس .. بمعنى انه
بنعطي ال top T attribute تبعة ال expression لأي
expression اللي هو هذا ال non-terminalنعطيه قيمة
الـ dot T مطبوعة
بالإشارة الزائدة
بالـ syntax-directed translation Translation على
أساس الـ syntax analysis هذا لما أنا بجيب ال
productions و بحط مقابل كل production ال rule
المصاحبة لها لتتنفس عند اجتمال تطبيقة هذا بيصير
syntax-directed definition هو بالاصل definition ده
ال grammarأسهل الآن هي عبارة عن syntax directed
definition لجرمه وللترجمة syntax
directed definition for infix to postfix
translation للتحويل من infix to postfix الان راحزي
ان هي ال rules او ال production سبعة ال term كان
في الأول يوم على سطر واحد وفصلهم الان كل واحد على
سطر لحاله و جاء إنه إذا هو zero فعلى طول طلّع ال
zero زي ما هي إضافة T لتأخد شكله ال zero ال
character فاحنا الآن بدنا نرجع شوية بس عشان نتبع
الحاجة اللي سقناها اللي الأول أصبحت المفهوم ألنا
هاي بداية ال section اتنين تلاتة مفهوم ال
attribute ومفهوم ال translation schemeTranslation
Scheme Translation Scheme هو عبارة عن الجدول هذا
اللي شوفناه هو عبارة عن Translation Scheme هو
عبارة عن Rules مصاحبة لإيش لProductions ال
Attributes Attributes is any quantity associated
with a programming construct Programming Construct
إن هنا هو ال non terminal و أيضا كمان على فكرة
اللي هو ال terminals ال one و ال zero الترانسليشن
تبعهم هو اللي هو الترانسليشنبس أم الـ 1 و الـ 0
هؤلاء معبّر عنهم بـ non-terminal اسمه term صح؟ non
-terminal اسمه term an attribute is any quantity
associated with a programming construct هذا
التعريف العامل للattribute عندنا في الحلقة .. في
ال example هذا شوفنا attribute اللي هي الخاصة بالـ
translation في attributes تانية قدام نحكي عن ال
parsing بشكل مفصل هنشوف أنواع attribute اللي هي
وظائف أخرى غير أنها تحملالقيمة الـ Translation ان
هي فيها attributes لل data type هذا الـ non
terminal يمثل متغير و لا يمثل identifier بلزمني
اعرف ال data type هو انتجر او float او كده فبيكون
فيه attribute خاصة لانها تحمل ال data type تبع ال
construct هذافانت تتخذن ال object ما لهوش بس ال
dot T attribute لأ ممكن يجيله ال dot T يعني
translate و ال dot T is the type و ال dot T واحدة
تانية يعني ال value ال value طبعا إذا هو
expression ممكن ال value النهائي يعني تسعة ناقص
خمس يسوى أربع زائد اتنين يسوى ستة الستة هذه تتخذن
في attribute اسمها ال dot value فهذا كل كلام جدا
بنشوفه بشكل مفصلهذا هو مفهوم الـ Attribute وهذا هو
مفهوم الـ Translation Scheme Translation Scheme هو
مفهوم لـ Attaching Program fragments Program
fragments يعني جزء من الـ code برمجي مع من؟ مع ال
production هذا الآن كأنه
code fragment لأنه بقى يقول لي ال attribute هي هذه
ال value تبقى هيك هذه كأنه سطر في برنامج بيعطي
قيمة ل attribute تمام
فإرفاق
أو attaching program fragments مع productions
بيشكل لي الاش الtranslation scheme و آخر شيء ان ال
production واحدة ممكن يصحبها rule يعني fragment
سطر واحد او اكتر ممكن تبقى مجموعة من ال fragments
اللي تتنفذ عند اكتمال اللي هو ال parsing
بعرفك ايش هي post-extension و تحويلها وهي example
وهي ال tree وهي ال syntax directed definition الان
ال tree هذه زي ما انتوا شايفين ال value تبع ال dot
T هذا مابحصل عليه الا من بعد ما اتحدى ال value تبع
اللي تحتها وهذه الكامرة كحالةالـ tree الـ
traversal لازم يتم dip first صح؟ لأن لازم انا أخش
هيك أطلع ال value تبع ال T هذه أرحله إلى هنا علينا
أخش هيك هذه مافيش إلها T أخش هيك مظبوط؟ اه بعد كده
أجمع ال value تبع ال T هذه من ال T هذه من ال T هذه
من هذا مظبوط؟ اهكلمة أجمع الـ value بالـ
concatenation بالإنجليزي synthesize بجمع أو بركّب
.. أه .. synthesize عشان هيك هذا ال attribute
بنعتبرها synthesized attribute طيب ما هي كل ال
attributes synthesized تيجي ال value تبعها من
التحت؟ مظبوط؟ لأ مش كلهم، في أنواع من ال
attributes قدامها نشوف اسمهم inherited attributes
بيجي ال value تبعها من siblingأو من parent بس اللي
بيجي ال value تبعها من تحت هي اللي بيقول عنها
synthesized غير هي اللي بيقول عنها inherited المهم
أحنا بقال لإن بس يعني لو أجي واحد قال طيب هي
attribute ليش سيقوموها ال synthesized هي attribute
فبس إذا حد عنده هذا التسارع حابب يعلن عنه okay
الآن هذا simple syntax directed definitionوهي الـ
tree traversal الـ tree traversal كنا ندل في ال
first انه وانا وقعدت على note N هي procedure اسمها
visit visit يعني من أزورها و أزور كل ما اتفرج عنها
for each child C of N هاي N هذا child وهذا child
from left to right visit C
أو recursive call إلى نفسها طب الآن أنا كنت على
هذه صرت الآن هنا visit هذه معناته شوف ال children
تبعها و visit اللي هم من left to right و جفت عليا
child إذا إله لسه children بده أضمني ألان لما خلاص
مافيش شيء لما أخلص visiting اللي أنا موجود على ال
node و مالهاش ال children ف evaluate ال semantic
rules at node nاللي انا عارف عليها evaluate وبعطي
قيمة وبأطلع منها على اللي بعدها واللي بعدها لإن
لما أرجع لفوق بقاش القيم تبعت اللي تحت بيجمعولي
القيم تبعت النوض اللي من فوق ال translation
schemes اللي ممكن تيجي على شكل إيش أنه ال rule
نفسها هي عندي rule rest can
have a formplus يتبعها term يتبعها rest واحد هذه
مثال على production production هذه ال production
هذه انا ممكن السق بها code هذا code هذا اللي بين
ال curly braces دولة code أوسقته بنفس ال
production فيها نفسها مش ان عملت ruleمصاحبة مش ان
انا عملت مور مصاحبة لأ السكتر ابهب و حطيت ال code
هذا في المص هنا مابين term و مابين rest اصفح ال
parser لو دخل على هذا ال production هشوف ال plus
هشوف ال term يعمله analysis لما يطلع جبل ما يشوف
ال rest راح ينفذ هذا هذا اشي بتنفذ اللي هو print
plusهروح يطبع ال plus ثم يكمل الحلل ال rest فجاعت
بترجم في نص ما هو بيحلل فهذه الآن لما احنا بنعمل
code fragment هذه code fragment والسقناها
بال production ممكن تيجي في وسط ال body ممكن تيجي
في بدايته ممكن تيجي في آخرهفي حالات مختلفة المهم
أننا نلتقطها
مع ال body تبع ال production إيش
بيترتب على هذا الكلام لو أنا عندي ال productions
زي هيكة هعندي ب grammar بالاصل expression كنا
ندفعه expression زي ال term هذا جديد علينا لأ
expression كنا ندفعه expression ناقص termالـ
expression is a term و ال term واحد من ال digits
الان عندي expression زي هذا تسعة نقص خمس زي
الإتنين و بدي أعمله parsing باستخدام ل translation
scheme هذا جاي لل print مراسقة لل body تبع ال
production و جاي دايما في الآخر مافيش حاجة في
الوسط أو في البدايةتخيل ايش اللي هيحصل الان انا
عملت دخلت على ال input اخدت ال input وحللته على
اساس انهياش expression زائد term هي expression وهي
زائد وهي term خلصت من تحليل ال expression هذا لأ
لسه دخلت على تحليل ال expression هذا اللي هي 9
ناقص الخمسة صح اخدت على اساس انهياش rule رقم اتنين
صح
Okay فأخدتها على أساس أنها هذه التسعة expressions
والخمسة إيش term لأن هذا ال expression هذه اللي هي
ال expression أخدتها على أساس أنها term يعني
expressions is a term عندنا نروح رقم تلاتة okay
الان خلصت term لأ مخلصتش ال term هي اللي بدي أخدها
على أساس أنها إيش تسعة على أساس أنها تسعة صح يجب
نروح رقم هاي عشرةتلاتة و تلاتة و تلاتة و تلاتة و
تلاتة و تلاتة و تلاتة و تلاتة و تلاتة و تلاتة و
تلاتة و
تلاتة و تلاتة و تلاتة و تلاتة و تلاتة و تلاتة و
تلاتة و تلاتة و تلاتة و
تلاتة
الان رجعت على الناقص و بدى اشوف هذه الخمسة اخدتها
على اساس انها term تمام هاي term و ال term هو
عبارة عن مين بالان على ال rule اللى هتكون هنا ال
term can have four terms صح لان هذه برضو هيوجه
فيهاcode fragment بيقولي أتباع خمسة فانا هي اتنين
خلصته درجة قبل ما اتجه بأتباع خمسة بنفذ الهدا الان
اكتمل تحليل ال production هذه اللي هي رقم اتنين
بعد ما اكتملت جزء هدا ك expression one و بعدين نقص
و بعدين تام ايش بدي اعمله بنفذ ال fragment اللي
بيقولي نقص اكتمل هذا الكلام الان انا اكتمل هذالأن
أنا برجع راجع على رقم واحد اكمل اه هذا خلص خلص
الزايد ضايل هذا هذا ايش بس اول اشي بروح على اتنين
صحيح انا هذا ماعنوش اي نوع من ال analysis ان خلص
الزايد انا بروح على ال term ال term باخد على اساس
ان اتنين اتنين هيقولي اطبع فهطبع اتنين صح بعد ما
اطبع اتنين برجع تاني الآن خلصت انا الآن من هذاالان
وصلت هنا فبقول اطبع ازاي اطبع ازاي صحيح لأ فهدولة
أسلوبين في التعامل مع عملية الترجمة السلوب الأول
كان ان انا باجمع ال translation تراكميا بواسطة ال
attributes والترجمة النهائية بتكون التجمعت لدي في
ال root node في ال dot T attribute تبع ال root
node بعد هيك بس خلاص بروح مرة واحدة باطبعهاأو
بصدرها يعني للاستدعام بينما في ال .. في
translation schemes أنا بطلع output أثناء عملية ال
parsing لأن ال actions مدمجة بداخل ال body بداخل
ال productions واضحة بتهيألي هدول أسلوبين مختلفين
في عملية ال translationو كلا هما .. كلا هما إيش؟
syntax directed لأنه كلا هما أنا أدمجت عملية ال
translation أثناء عملية ال parsing بس واحدة من
خلال ال attributes و واحدة من خلال اللي هي ال code
fragments
هذا الرسم يتعبر عن ما هو مفروض ال code fragments
اللي بتيجي في وسط ال code هذه الخطة المتقطة معناته
انه مش عملية passing هي عملية action بتتنفس اللي
هو ال printing وهنا هي طبعا نفس الكلمة اللي
سويناها معبرك انه بعد ما انتهى ال analysis هذاأخذت
تسعة وانتهينا من هذا الكلام تم تنفيذ الطباعة بعد
تسعة ثم طباعة خمسة ثم اتنين ثم اتنين ثم اتنين ثم
اتنين ثم اتنين ثم اتنين ثم اتنين ثم اتنين ثم اتنين
ثم اتنين ثم اتنين ثم اتنين ثم اتنين ثم اتنين ثم
اتنين ثم اتنين ثم اتنين ثم اتنين ثم اتنين ثم اتنين
ثم اتنين ثم اتنين ثم اتنين ثم اتنين ثم اتنين ثم
اتنين ثم اتنين ثم اتنين ثم اتنين ثم اتنين ثم ات
العملية الـ syntax-directed translation شوفنا ال
post-augmentation فيها الـ syntax الـ synthesizer
attribute بتعرفنا عليها الـ simple syntax-directed
definition بتعرفنا عليها الـ tree traversal هو ال
.. ال .. ال button في ال .. ال depth first و ال
translation schemes اللي هي بيكون فيها ال code
fragments مدمجة مع ال .. ال .. okay مع الاش .. مع
ال productionsخلّي بالك ان هنا تبدأ هذا و هذا
بيصيب و يكون في عندي table يحتوي على عمودين عمود
ال productions و عمود ال rules و ال rules بينما
هنا عمود واحد بتكون ال fragments ال semantic
actions اسمها اذا لاحظته في ال slide تكون مدمجة
بداخل
ال productions
صح؟مدمجة إما في نص ال body أو على آخره أو حتى ممكن
تيجي في بدايته في بعض الحلقات يعني خلصنا احنا الآن
على باب اللي هو مشارف ال parsing ال parsing اللي
هي إيش برضه كمان syntax analysis فيها ال top-down
parsing و واحد منهما اللي هو predictive parsing
وبعدين كده بيشوف بيكمل designing a predictive
parserوبعدها ننظر إلى أسئلة ال recursion هناك نوع
من ال recursion اسمه left recursion هذا في ال
grammar ممكن يمر عليكم لماذا؟ في المبادئ؟ لأ عموما
إذا دلت معانا وجهة نحن نجيلها وبتشوف أيش ضرر تبعها
وكيف ممكن أن نعالجه بتغيير ال grammar بحيث أنها
تصبح مش left recursion لإن احنا بنروح على 2.4 اللي
هو
الـ Top-Down Parsing 2.4 و2.4.1 هل
يوجد أحد عنده سؤال في الفاتر؟ نتفقن
على أن الـ Parsing هو الprocess ofHow the input
string can be generated by a grammar؟ ال grammar
شو هي؟ المجموعات اللي إيش؟ هي ال definition اللي
يتكون من مجموعات ال productions كيف أنا بستخدم هذه
ال definitions to generate ال input؟ كيف أنا هو
أنا أصلا مظيفتي أنا أطلع ال input؟ لأ ال input
هيدخلي بس إذا أنا اللي دخليها لأ I could generate
itإذا انا اقدرت ان اعمل مطابق له مع أن دالك هذا
اللي دخل سليم قواعديا Gramatically يعني في ال
parsing هو وظيفته التأكد من سلامة صحة ال input
عشان يتأكد من صحته و يشوف هل استطيع انه ت
regenerate it بناء على rules بناء على productions
ببدا من الاش من ال star symbol و من خلال عملية
الاستبدالبشوف هل يمكن وصول إلى form مطابق للform
تبعين okay ف how a string of terminals ال input هو
عبارة عن string of terminals لو تسعة نقص كمس زي
اتنين هدولة symbols هي عبارة عن terminals لو if
statement if goes expression كده يوجوه مش حاجة ان
مغارة مش كاتبلي كلمة expression صح هيمكن تحططلي
expression فعلي
هذا وهذا ال expression الفعل هو عبارة عن symbols و
ال symbols هدى terminals فهو الهدف في ال parsing
is the process of determining how a string of
terminals can be generated by a grammar أو
regenerated by a grammar طيب الآن احنا هي مثلا
مثال بسيطة عندنا اللي هو وهذا اللي كان أسمع مش
يديد علينا هذا definition a grammar for some
statements in C and Java a statement is an
expressionأو if أو for أو some other شكل آخر من
أشكال ال statements وعندي هنا ال for مثلا الاسم ال
if تحتوي على أقص و expression و statement إذا
أتحقق هذا ال expression تتنفذ هذا ال statement
طبعا ال for ال if لها شكل آخر اللي هو ال else ال
if else بس هنا أحنا هذا تبسيط مش داخلالـ four
عبارة عن بُس فيه هدي ال initialization فيه هدي ال
condition وفيه هدي ال action اللي يتنفس في كل دورة
دورته وفيه هدي اللي هو ال statement أيضا اللي
بتنفس هذا اللي بيكون implementation او decrement
وهدول
ال expressions اللي هنا بسميهم او عاملهم non
-terminal اسمه optional expression optional
expression optional expression optional expression
الأعضاء هذه حاططها بس يعني عشان كناية عن كل ال
other forms of the statement لأن هذا ال optional
expression ممكن يبقى إبسلون إبسلون يعني إيش ولا إش
ولا شيء بالظبط أو يبقى expression فهي هذه الوسيلة
تبعتنا يعني راحنا بنحط الإبسلون بنحطه كوسيلة
للكناية عن أو للتخصيص أنه هذا الشيء optionalيا
المفاض يا اما كده يبقى هذا الشيء يكون او هذا
المنتج يكون optional الان انا بكون فيها expression
input داخل زيك طبعا انا قولت مرة اخرى بقول مرة
اخرى ان ال programmer مش هيكتب كلمة expression
expr هيبقى حاضر ال expression بس احنا تجاوزا عشان
نوضح الفكرة فكرة ال top-down parsing بإننا نعتبر
انهالأحرف هذه فعلا هي اللي داخلة في ال input EXPR
EXPR وكلمة other وإيه اللي لازم أضعه؟ أي حاجة زي
ذلك هيفشل عملية ال parsing لأن ال grammar لها تدعم
سواء هلأ كده ال parser
should be able to build a parse tree parse tree
التي تتكوّن من نوت و أطفال هداية من الـ star
symbol الى ال .. فال
process هذه تبعد building ال tree تبدأ
أنه ال node in نعمل
node نرمز عليها بينبنعطيها label ال label تبعها
بيكون اسم ال non terminal اللي واقفين عليه واقفين
عليه في ال input و اللي واقفين عليه في ال rule هو
ال input مش هيجيني بداخله اسم ال non terminal مش
هتيجي كلمة statement ولا كده أنا عندي ال inputمن
ناحية و عند ال rules من ناحية اول ما بدأ ببدأ بمين
بال start symbol فانا الان ال start symbol انا
واقف عليه فهو ال current node تبعتي فلازم ينعمله
node لازم ينعمله ال statement لازم ينعمله node فهي
انعملت node ال
node in labelled with non terminal aننترنال A الان
في البداية هو ال start symbol STMT تمام يعني
select one of the productions تبعت هذا النترنال
ايه ال production الان هنا اربعة مش تلاتة هم
اربع صح سنة بتنتهي صح صح هم اربع هي واحد هي تنتين
هي تلاتة هي اربعOkay Select one كلمة select one
هذا حُط تحتها عشرين ألف خط Okay لأنها هذه قضية
محور مفرقية لأنه بتأثر على أداء ال parser إذا
اختار واحدة ومشي في التحليل وطلعت مش شيء صحيحة بدي
يرد ويرجع يختار اللي بعدها عملت الاختيار هذا الخطأ
أو الصحبتاخد budget المفروض يكون فيه شيء يقوله
اروح على هذا ال production على طول بدون ما يجربوا
يختاروا المهم select one of the productions for A
اللي هو ايه اللي هو ال symbol الحالي and construct
children عند ال node اللي انت عملتها لا ال node
اللي انت عملتها دي construct children for the
symbols اللي في ال production bodyاختفنا هذه
القوية معناه ذلك ايش؟ مدى ايش اول statement؟ اللى
هى ال carrot node و اعمل اكم node اكم child؟ اتنين
او تلاتة؟
اتنين واحدة لأ هذا ال symbol و هذا لايوجد هنا ال
production هذا كم symbol فيها؟ واحد اتنين تلاتة
اربعة خمسة واحد اتنين تلاتة اربعةخمسة .. ستة ..
سبعة .. تمانية .. تسعة .. صح؟ هدول ال symbols بعض
منهم terminals و بعض منهم non-terminals بس كل واحد
منهم ال symbols اللي قلناه عمال يشهد child عملنا
الآن خلصنا الان find the next node at which a sub
-tree is to be constructed مين الآن؟ هي عملنا sub
-tree .. عملنا ال node هذه sub-tree اللي هي ال ..
ال children الدول بيجي على مين؟ نبدأ من الشمالهذه
الان بدنا نعملها sub tree فبنروح هذا ال non
terminal إذا والله كان زي ال F زي هذه كان عبارة عن
terminal مالوش sub tree بروح على اللي بعده الآن
صح؟ يعني نفترض إن هذه كانت F وكانت هذه course
وكانت هذه expression و .. لأن هذا ده قال الدور ال
Fبطلع لها sub-tree؟ ماطلعش لأنها terminal ليش
اسمها .. سمنها terminal؟ لأنه مافي بتفرع منها أي
شيء هذا احنا الأن ماخدين اللي هي ال production
أولى expression و الأن بدي أجف هنا ال end تبعتي
الأن بيصير هذي هي ال pointer اسمه M بيصير أشراه
هذي هذا الأن بدي أعملها sub-treeبالدرجة بنفس
القليل اشوف ايش ال production تبعتها دا non
terminal و اختار واحدة منهم و اعمل nodes children
بعندمين مقابل ال symbols تبعتها ال production اي
expression وان expression فشي صح لو فيه بيبقوا
عاملوا نفس الشيء الان احنا هنيجي نعمل build الان
اذا كان
find the next which subtree is to be constructed
typically the leftmost unexplained none terminal
of the tree هذا الكلام الحكيمي اللي هو انه ناخد
الشمال الان هذا الكلام expression لو فيه بن ايش؟
بن مصدر الان انا لازم اجف انت بعدين اجي الاقي
terminal Fإذا أنا جيت في Terminal F و لا 4 و لا
كذا بدي أشوف هل ال Terminal هي ده يطابق ال
Terminal اللي أنا عارف عليه حاليا في ال input إذا
فيه مطابقة يعني أنا لغاية مافيش مجال لأكمل فلأ
سالب يقول dead end إذا هذا ال dead end أو leaf
note إذا هذا ال leaf note يطابق ال input اللي
معايا يمكن أن أقدم خطوة أخرى في عملية ال matching
Matching صح؟ وإلامعناته انا وصلت الى error error
اه error معناه ده اللي جيش بدي اعمل backtracking و
اتراجع بدي ابدل ال production أخرى مش بالضرورة
مضربوه ممكن من هنا المشكلة كانت يعني هذا ال
expression المهم انا اخترت ال production البداية
تبعته لات مطابق فمدي اجيب ال production أخرى و
اجرب لو اجيت كل ال production سبعت هذا فاشلتإذا هو
فاشل إذا ال production اللي هو أجا منها بدي أبدلها
و أجيب production أخرى ففي النهاية حصل إلى بعضك إن
والله statement هذه بعد
ما حاولت هذه و فشلت و حاولت هذه و فشلت هقعدش على
هذه هيقول لي أن هي top ممكن أرسمها من جديد هي four
و بص و expression و هذا ذلكمطابقة if that I can
move في ال matching و هذه مطابقة يا حلو طيب هذه ال
semi colon انا شايف هنا ال semi colon صحيح لكن
عندي في ال parsing لسه مش شايف ال semi colon انا
شايف هذا هل هذا .. هل هذا يطابق ال .. ال .. يعني
ممكن اتجاوزهإذا هذا كنان ترنالد إله production
إمتي معناه ده أنا مقدر أتجاوزه وهو فعلا إله إمتي
يعني أنا هنا يا إما بقابق هذا مع اللي أنا ماعرف
عليه يا إما بلاقي إله إمتي بمعناه إنه أتجاوزه وهو
فعلا إله ال epsilon production فهو فعلا أتجاوزه
بصير أنا واقف هنا على السيم كورن السيم كورن على
السيم كورن يبقى بجدّم واحظ إذا مافيه matching إيش
بسوي بجدّمفي ال .. في ال two tracks في المسارين
باجدّم صح؟ اجدّمت، الآن أنا صرت هنا وصرت هنا لأن
هذه optional expression وهنا عندي terminal
expression هل في لل optional expression شكل او ..
او production يعني، ايش production سبب؟ في ال
epsilon وفي ال expression ال epsilon لأ ال
expression اهفطابق هذا مع هذا الآن بعدى عن هذا و
بعدى عن هذا صح هنا بنتقل هنا طيب هذا لما أسيبه و
انا أروح مافيش sibling برجع لل parent و بكمل ال
sibling تبع ال parent صح؟ بلاقي فيه match بكمل نفس
العملية era and era هنا صار .. تكون تمت عملية ال
parsing و بشكل top-down من فوق إلىمن أعلى إلى أسفل
يعني إحنا بنمشي من هناك و بندخل على ال children و
ال children تبعد ال children إلى أن نصل ل leaf
node و نعمل matching هذه هي استراتيجية ال top-down
parsing عمليا و هذه التوضيح خطوة لخطوة يعني نفس
الكلام اللي قلته أنا شرحته message هو اعملكي خطوة
لخطوة اول شيء اول شيء عمل node واحدةلل statement
non terminal و ال pointer عليها و في ال input ال
pointer علي ال non terminal تبع ال four صح؟ في
الخطوة التانية طبعا هو بعد ما جرّر خلينا نقول أو
نصره ان هو عمل selection لها من البداية دون ..
الآن four مع صار ال pointer متجر من هنا إلى ال
four تبع ال three و على ال input على ال four هو
هاي ال input صح؟يعني هذه مرحلة وهذه مرحلة وهذه
مرحلة و هذا زي ما انا حكيته طبعا يعني مافيش داعي
نفيده مني الان الامر
هذا بيطبق عمليا من خلال من خلال إيش اللي هو ال
recursive descent parsing ال recursive descent
parsing إذا top down خلي ال predictive parsing
بحكي إيشيعني ليش ال recursive descent قاسي من
أنواع من أنواع ال predictive بس recursive descent
إيش عن ال descent يعني هبوت قنزول و recursive يعني
باستخدام قلية ال recursion قلية ال recursion هي
استدعاء ذاتي يعني على طول بحط في دماغي أنه في
function بدأ تقوم بالشغل و بدأ تقوم في هذا الشغل
من خلال استدعاء ذاتي لنفسها و descent بمعنى إنه م
top-downdescent يعني هبوط and top-down هي is a top
-down method of syntax analysis in which لسه
analysis مافيش translation عامة a set of recursive
procedures مختلفة
كل واحد لديها دورها وحتى لو بدأت نفس دورها ممكن
تستدعي نفسها أكتر من مرة is used to process the
input one procedureis associated with each non
-terminal يعني كل non-terminal في الgrammar
بنبناله procedure إذا عندي non-terminal يسمه
expression حيكون عندي procedure أو function اسمها
expression هذا
non-terminal في هذه method أو procedure هذا
statement non-terminal في تمام؟
one procedure is associated with each non-terminal
of a grammar هاي statement a procedure to mean a
statement non-terminal إيش بيستوي الان
هدول ال cases عندك فكرة إيش هم؟ هدول
هم children of one statementهذه ال gossip الأول
هدول
القيم
أسف هدول عبارة عن ال .. ال .. ال .. ال .. ال
symbols اللي بيجوا في بداية ال productions تبع ال
statement الحين صعب أن نطلع و ننزل بس إذا بتذكروا
ال statement كان لدي عدة productions
و واحدة منهم F و بعدين كده كده و بعد تاني four و
كده كده و بعد تاني other صح هدولة other و four و F
و expression هم بدايات ال bodies تبعت ال
productions تبعت ال statement فكأنه بيقول لي إنه
إذا أنا .. إذا أنت الآن واقف على ال statement فال
children تبعونهااحتمال يكون اول واحد فيهم اما
expression او اول واحد منهم if او other او for او
other فاذا كان if معناه ذلك سوي كده كده اذا كان
expression معناه ذلك بدك تستدعي ال expression
recursive procedure عشان تشوف ال subtree تبع ال
expression اذا
الـ Lookahead هو عبارة عن الـ pointer تبع ال node
.. آسف مش تبع ال node .. تبع ال input ال pointer
تبع ال input اسم ال lookahead هذا بيشير إلى ال
token اللي واقفين عليه في ال input ما احنا ال
input تبعنا tokens مش characters احنا ماخدين a
sequence of tokens من مين؟من الـ Lexical Analyzer
Lexical Analyzer بشوف characters و بسلمنا مين
بسلمنا مين ال tokens فانا واقف على .. امامي في
sequence of tokens و ال pointer اسمه ال lookahead
بشاور واحد ورا التاني طبعا فإذا اللي أمامي اللي
داخل .. اللي أنا واقف عليه في ال input هو
expression هذه expression مهم ترمنا فبدأ أستدعي
طبعا أستدعيهذا expression بناء على ال grammar
keyword لأن الذاكتين احنا مالوش productions ومعناه
المكتوب اصلا كان بال bold مش Italic ف expression
بناء على ال grammar هو terminal فterminal معناته
match expression ايش يعني match expression عشان
تشوف هل ال look a hit هل ال look
a hitيطابق ال current node في ال tree إذا ال
lookahead يطابق ال current node معناته انتقل وعمل
match لل semicolon هل ال next token في ال input
يطابق ال next child في ال tree فالمatch هذه
وظيفتها أنها تشوف إذا في مطابق ولا لا إذا في
مطابقة بتقدمإذا مافيش مطابقة بتعطيلي error error
معناه ذلك ال case اللي فشلت معناه ذلك بتتحول على
.. على حاجة تانية okay فالان هنا هتلاقي انه في
حالات هاي زي مثلا وين هنا
هتلاقي انه زي في ال four لإن ال four في عندي انا
four كذا four or كذا option و بعدين هنا في
statement صح اللي بتتنفس بكلهفبيجي انه ال input
اللي داخل بعد ال ghost بنعالجه باستخدام استدعاء
ذاتي آخر لاستخدام نفسها عشان نشوف ايش ال statement
اللي بعد ال ghost كيف ممكن تتعامل معاه فهذا
recursive و descent وفكرته انه لكل واحدة من ال non
-terminants في procedure و ال procedure هذه بتشتمل
على code ال code هذا هو ترجمةلأيش لل productions
تبعت ال non terminal ده بمعنى محدد و هو انه كل
production تبعت لهذا ال non terminal بنشوف راسها
او ال first element تبعها و نعمل check له و لكل ما
يتبعه بعد هيك اذا نجح اذا هو اللي فعلا موجود في ال
input فبدنا نعمل matching لل input على اساسال rule
تبقى وهذا راس ل role او ل body فإذا صار في
matching بينه و بين ال input يبقى لازم اللي يتبعه
في ال input يكون زي هيك كله هدا يعطيه true true
true true بتكون اكتمل ال task واحدة منهم تعطيني
false و بطلع و بجرب واحدة تانية لأن كل واحدة من
هدولة ممكن تشتمل على استدعاء ذاتي لنفسهاأو أيضا ل
.. ل .. ل .. ل .. ل .. ل .. ل .. ل .. ل .. ل .. ل
.. ل .. ل .. ل .. ل .. ل .. ل .. ل .. ل ..
ل .. ل .. ل .. ل .. ل .. ل .. ل .. ل .. ل .. ل ..
ل .. ل .. ل .. ل .. ل .. ل .. ل .. ل .. ل ..
ل .. ل
الان انا بنكمل من انديان لان هذه قضية مهمة جدا ان
انا يكون في هندي قالية لتحديد منهم ال firsts تمهات
ال productions تمهات كل واحد من ال non-terminal
يعني على اساس هذا ال first انا بقدر ابني ال
recursive function