بسم الله الرحمن الرحيم الصلاة والسلام عليكم ورحمة
الله ورحمة الله ورحمة الله ورحمة الله ورحمة الله
ورحمة الله ورحمة الله ورحمة الله ورحمة الله ورحمة
الله ورحمة الله ورحمة الله ورحمة الله ورحمة الله
ورحمة الله ورحمة الله ورحمة الله ورحمة الله ورحمة
الله ورحمة الله ورحمة الله ورحمة الله ورحمة الله
ورحمة الله ورحمة الله ورحمة الله ورحمة الله ورحمة
الله ورحمة الله ورحمة الله ورحمة الله ورحمة الله
ورحمة الله ورحمة الله ورحمة الله ورحمة الله ورحمة
الله ورحمة الله ورحمة الله ورحمة الله ورحمة الله
وموضوع الـ parse trees كيف أننا نشكل parse tree من
خلال بعض الـ derivation وأيضا نشوف المفهوم الـ
ambiguity اللي هو اللبس يعني بمعنى أن نفس الـ input
ممكن يتعمل أكتر من الـ derivation وكل derivation
تفضي إلى parse tree مختلفة وكيف أن هذا الكلام ينتج
عنه semantics مختلفة، يفسرّه إذا فُسّر هيك بينتج
value تبعه شيء مختلف عن لو تم تفسيره بشكل آخر بعد
ذلك برضه كمان اتناولنا الموضوع الـ associativity of
operators و الـ precedence of operators فعملية احنا
انتهينا من section 2.2 يعني الشيء بدنا نتجه الآن
إلى section 2.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 اللي تلقائي اللي حيعطيه
infix 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.T هنا بضع one عشان أميز ما بين الـ
parent و ما بين الـ child ده بقول expression one
expression
one و .T والحمّ وراها إيش هذا الـ double bar
concatenation يعني الحمّ وراها إيش النقص ولا الخمسة
الـ term.T والحمّ بعدها نقص النقص كما هو على شكل
الـ string أو الـ character نفس الشيء هنا
بس بدل النقص الزائد برضه هنا بحط expression one
تمييز إن أنا بحكي عن الـ child
خطوة ممتازة الآن نأخذ هذا الكلام و نضعه مع الـ
production بحيث إن الـ parser يقوم بترجمة ويقوم
بترجمة في أنهي المعاهد نفس الواجهة اللي هو الكتل
أمسح هذا الكلام خلاص واضح هدول
productions تمام هدول شغل الـ parser اللي بيسويه
بتناولهم عشان يعمل parsing في نفس الوقت اللي بيصير
في الـ parsing بدنا برضه كمان يصير translation
هدول productions هدول إيش اسمهم semantic rules
rules إن هذا الـ rule تعني إن الـ نادش للـ
translation بدي يكون هيك ماشي .. امتى بيتطبق هذه ..
هذه بدأت تتنفس امتى بتتنفس .. لما يكتمل الـ parsing
تبع هذا الـ non-terminal بناء على هذه الـ production
هذا الـ non-terminal بناء على هذه الـ production لما
يكتملها وجدت بتتنفس هذه الـ rule تتنفس .. بمعنى إنه
بنعطي الـ top T attribute تبع الـ expression لأي
expression اللي هو هذا الـ non-terminal نعطيه قيمة
الـ .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 scheme Translation
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 ما لهوش بس الـ
.T attribute لأ ممكن يجيله الـ .T يعني
translate والـ .T is the type والـ .T واحدة
تانية يعني الـ value الـ value طبعا إذا هو
expression ممكن الـ value النهائي يعني تسعة ناقص
خمسة يساوي أربعة زائد اثنين يساوي ستة الستة هذه بتاخذها
في attribute اسمها الـ .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 تبع الـ .
T هذا ما بحصل عليه إلا من بعد ما اتحدى الـ value تبع
اللي تحتها وهذه الكاميرا كحالة الـ tree الـ
traversal لازم يتم depth 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 إنه وأنا وقعدت على node 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 form plus يتبعها term يتبعها rest واحد هذه
مثال على production production هذه الـ production
هذه أنا ممكن أسقّ بها code هذا code هذا اللي بين
الـ curly braces دول code أسقته بنفس الـ
production فيها نفسها مش إن عملت rule مصاحبة مش إن
أنا عملت 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 و بعدين نقص
و بعدين term إيش بدي أعمله بنفذ الـ 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 of How 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 أنا
شايف هذا هل هذا .. هل هذا يطابق ال .. ال .. يعني
ممكن أتجاوزه إذا هذا كان terminal له 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-down descent يعني هبوط 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 procedure is 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