Compilers20_Lecture_6-Parser_II_-_19-12-2020
السلام عليكم، بنتكلم النهاردة عن المحاضرة السابعة Syntax Analysis
الـ Parsing Part 2. إحنا اتكلمنا في المحاضرة اللي فاتت بداية الـ Parser
 الـ Parser هي الـ Phase التانية بتاعة الـ Compiler.
 طيب، إحنا اتكلمنا المرة اللي فاتت على الـ Parse Tree وعلى الـ Context Free Grammar.
النهاردة هنتكلم عن إيه؟ أولاً دي الـ Quote of the day
 Smile, it's free therapy.
 يعني Smile، يعني متوتروش نفسكم الفترة اللي إحنا فيها، طبعاً توتر على الكل، من جميع الجهات وجميع المستويات، علينا وعليكم، ربنا يوفقنا ويوفقكم، بس يعني..
ربنا قادر إن.. يزيح الغمة دي، وإن شاء الله كل حاجة تبقى تمام. 
النهاردة هنتكلم عن الـ Abstract Syntax Tree والـ Ambiguous Grammar. لو نفتكر مع بعض الـ Parse Tree 
لو عندي مثلاً String زي ده 3 في 4.
الـ Parse Tree بيبقى شكلها عامل كدة 
بكتب هنا الـ Start symbol في الـ Context Free Grammar،
 وبعد كدة ابدأ أكتب الـ Derivation بتاع الـ String لغاية ما أوصل للـ Leaves، 
اللي هي الـ Leaf nodes، دي اللي هي الـ Terminals بتاعتي. تمام؟
 الـ Parse Tree بكتب في الـ Nodes اللي هي Interior nodes بتاعت الـ Tree،
 بكتب فيها الـ Rules أو اللي هي Terminals.
الـ Non-terminals، وفي الـ Leaves بكتب الـ Terminals. تمام؟ 
فالـ Parse Tree بـ Contains 
more information than it is absolutely necessary للـ Compiler. إحنا اتفقنا إن الهدف من الـ Parser، الـ Phase التانية للـ Compiler، إن أنا أطلع.. آخد الـ Tokens من
 الـ Lexical Analyzer اللي هو الـ Scanner..
أطلع بـ Parse tree أو Syntax tree. طيب، For simplicity إحنا هنطلع الـ Syntax tree، وفيه حاجة كمان اسمها Abstract syntax tree. 
الـ Abstract syntax tree اللي هو بمنتهى البساطة هي Tree عبارة عن الـ Terminals فقط. يعني أنا لو عايز 3 في 4، هحط الـ Operation هنا..
وانزل 3 في الـ left و 4 في الـ right بشيل كل details بتاعت rules وبتاعت derivation دي بتبقى اسهل و abstract يعني حاجة مجردة من التفاصيل مش محتاجة اعرف انا rules طالما انا مشيت على derivation صح وعملت verification
مش محتاجة أحط الـ Rule عندي في الـ Tree فدي بتسهل في الـ Compiler يعني. 
فدي مثلاً الـ Tree بتاعت الـ Expression
(34-3)
multiplied by 42 . هنا أنا حاطة Bracket فبـ Enforce إن أنا أعمل الـ Subtraction الأول لو مفيش Brackets زي ما هنشوف كمان شوية...
يبقى المفروض إن أنا منتظرة إن أنا أعمل Multiplication الأول لأن ليها
 Higher precedence، ليها أسبقية، ليها أولوية. فأنا هنا ناخد بالي من حاجة
 إن أنا كل ما أبقى أعلى في الـ Tree فوق، أقرب للـ Root، كل ما أنا يبقى ليا
 Lower precedence. يعني أنا هنا اللي تحت هو اللي بيتحسب الأول.
فهنا الـ Higher precedence يعني أنا بديله أولوية في الحسبة بتاعته وبعد كدة ده. طيب،
 أنا ده ماليش دعوة بالـ Calculations خالص في الـ Parser 
الـ Parser هدفه إن أنا أشوف هل الـ Tree ماشية على الـ String ده ماشي على الـ Tree ولا لا. طيب خلينا نشوف..
الـ Parentheses token هنا مش بنحطها علشان هي مـ.. يعني مش محتاجة تتحط لأن أنا Already الـ Tree ده بيـ Enforce إن أنا أعمل الـ Subtraction الأول. لو نفتكر الـ Grammar بتاع
 الـ If statement..
أنا بسميه الـ Simplified
f statement، اللي هو Straightforward. الـ Statement عبارة عن If statement 
أو Other
If expression statement، اللي هي الـ If statement أو If expression statement else statement، بمنتهى البساطة Straightforward. والـ Expression ده يا 0 يا 1. طيب، عايزة مثلاً أعمل الـ Tree بتاعت if 0
 other else other.
دي Parse tree اللي أنا رسماها دي Parse tree ولا Syntax tree؟
دي Parse tree ليه؟ لأن أنا كاتبة في الـ Nodes، الـ Interior nodes كاتبة اسم الـ Non-terminals أو أسامي الـ Rules بتاعت الـ Context Free Grammar. فأنا هنا بقول Statement عبارة عن If statement، والـ If statement عبارة عن if expression statement else statement وهنا الـ Expression ده بـ 0 لأن الـ String مكتوب لي فيه 0، وهنا دي Other ودي Other..
Other.. ده الـ Parse tree بتاعت الـ Statement دي. طيب، Again هكرر
أنا في الـ Parser أنا بعمل الـ Parse tree ماليش دعوة بالـ Meaning أو.. 
أنا مرحلة الـ Meaning إن أنا أحسب مثلاً زي 34 - 3 * 42....
أنا ماليش دعوة هي هتدي كام في الـ Parser أعرف هتدي كام في الـ Semantic Analysis. هي الـ Semantics دي أو الـ Phase اللي هي التالتة هي دي اللي مسؤولة عن تفهم بقى
 If statement دي معناها إيه، الـ Calculation دي يعني أحسب كام كده. 
لكن أنا هنا اللي يخصني الـ String اللي جايلي، بتعامل معاه على إنه String.
بعامله على إنه String وأحطه في الـ Parse tree أو الـ Syntax tree.
 فيه Another grammar للـ If statement برضو كان If statement أو Other، if expression statement else-part
والـ else-part عبارة عن else statement أو Epsilon. برضه خدناها من المحاضرة اللي فاتت، هنا بقول إن أنا الـ else-part دي حطيت لها Rule جديدة الـ Rule الجديدة بتقولي يا يجيلي else statement...
Else بعد كدة Statement يجيلي Epsilon، يعني معنديش Else statement.
 طيب، نفس الـ Statement دي if 0 other else other 
بالـ Rule الجديدة تبقى عاملة كدة Statement if-statement ودي عبارة عن if expression statement else-part، والـ else-part عبارة عن else
 followed بـ statement اللي هي other. الـ Grammar ده برضو خدناه Lecture اللي فاتت بتاع الـ Semicolon separator...
إحنا خدنا اتنين واحد كان Semicolon separator والتاني كان الـ Semicolon terminator. الـ Separator ده معناه إن الـ Language اللي كانت Accepted لو نفتكر هو الـ S لوحدها، أو S
 followed by semicolon followed by S
يعني أي Two or Three statements يبقوا Separated في النص بـ Semicolon.
عايزة أشوف الـ Statement دي أعمل لها الـ Parse tree بتاعتها 
S ; S ; S. فهمشي على الـ Rule همشي على الـ Rule
 Statement Sequence دي الـ Parse tree بتاعتها عبارة عن Statement Semicolon Statement Sequence. الـ Statement دي اللي هي عبارة عن S، والـ Semicolon دي خلاص Terminal. طالما اللي بالأزرق دول، اللي أنا كاتباهم بالأزرق دول Terminals اللي هم الـ Leaves بتوع الـ Tree يعني مش هنزل بيهم..
بفرع جديد من الـ Tree. 
Statement Sequence عبارة عن Statement Semicolon 
followed by Statement Sequence،
اللي هي Statement وS، وهنا الـ Statement اللي هي S. يبقى S ; S ; S، بتتقري كدة 
From left to right، from down to up
S semicolon S semicolon S، تاني From left to right.
From down to up
S semicolon S semicolon S. 
ممكن أعمل لها Syntax tree إن أنا أشيل الـ Statement sequence والـ Statement، وأحط بس.. أشوف هنا أعلى واحدة فين في الـ Terminals
 أهي الـ Semicolon، يبقى أحطها فوق، هي دي الـ Root بتاعت الـ Tree بتاعتي
Left بتاعها S، والـ Left بتاعها Semicolon برضو، Followed by S شمال وS يمين. يبقى أهي S Semicolon 
وبعدين هنزل هنا S Semicolon S.
 ليه ماخدتش الـ Semicolon.. يعني دي مش معناها Semicolon followed by Semicolon، لأ.
S semicolon 
وبعد كدة الفرع ده بيـ Evaluate من تحت لفوق، اللي هي عبارة عن S semicolon S، 
Okay؟ نيجي بقى نعمل Differentiation
 between الـ Syntax tree والـ Parse tree. 
الـ Syntax tree بتتسمى Abstract 
Abstract يعني مجردة، مجردة من التفاصيل.
الـ Parse Tree بتتسمى Concrete Concrete يعني إيه؟ يعني حاجة قوية، ماسكة نفسها، فيها التفاصيل، فيها القوانين، فيها الـ Verification، الـ Evidence إن أنا الـ Derivation ده جاي من الـ Grammar. الـ Syntax Tree إيه الـ Properties بتاعتها؟
 الـ Interior nodes هم Operators
plus, minus, multiplication, semicolon. 
الـ Leaves هي الـ Operands.