Compilers20_Lecture_6-Parser_II_-_19-12-2020
الـ Operands اللي هي الأرقام بقى نفسها أو الـ Identifiers بتاعتي.
الـ Parse Tree الـ Interior nodes فيها هي الـ Non-terminals، 
أسامي الـ Context Free
 Grammar rules والـ Leaves هم الـ Terminals.
 الـ Syntax tree
When representing a program in a tree structure usually use syntax tree، ده بيفضل لأنه أسهل في الـ Representation.
فيه شوية Nodes كتيرة بتتشال لو أنا Parse tree. 
الـ Syntax tree بتبقى أسهل، 
Rarely constructed as a data structure.
 الـ Syntax tree
represent the Abstract syntax tree of a Program، اللي هي الـ Semantics أقدر منها أفهم الـ Semantics؛ لإن أنا لما قريت كدة عرفت بالتالي أـ Serve الـ Phase بتاعت الـ Semantic Analysis، إن أنا هعرف بالترتيب مثلاً لو أنا...
دي Calculation يبقى زي ما قلنا من الشمال لليمين من تحت لفوق. هنا contains 
هنا بيـ Represent الـ Concrete Syntax بتاع الـ Program، الـ Rule نفسها. هنا Contains only meaningful information اللي هي الـ Values نفسها، الـ Terminals. هنا Contains unusable information.
Syntax tree بتاعت الـ مثلاً expression 
E multiplied by E, 
E plus E أو identifier وعندي string A plus B multiplied by C
 هيبقى syntax tree بتاعتها كده، الـ plus نازل منها الـ A،
 followed by الـ multiplication نازل منها الـ B والـ C، يعني أنا بـ evaluate قلنا من الشمال يمين A plus.
بس حاجة، الحاجة دي هـ evaluate ده الأول B times C،
طب هنا نفس الـ tree بس شوفوا كام node زيادة بقى اللي فيها الـ E، يبقى E ببدأ بالـ root بتاعت  الـ rule بتاعتي E,
E plus E والـ E دي اللي هي identifier اللي هي A والـ E دي اللي هي
 E multiplied by E اللي هي B times C.
نفسها تدي نفس الناتج ولكن الـ tree الـ nodes بتاعتها أكتر، 
طيب بنتكلم عن الـ parsing يبقى أول حاجة أو من أهم الحاجات الـ concepts المهمة جداً 
في الـ parsing الـ ambiguity، يعني إيه ambiguity؟ لما أقولك إن ده 
ambiguous grammar.
أو إن الـ sentence اللي أنت قلتها دي ambiguous حتى في الـ natural language دي معناها إن هي بتحمل معنيين أو تلاتة أو أربعة مش مفهومة مش واضحة غامضة. 
طيب لو أنا بتكلم عن natural language مثلاً لو بتكلم على مستوى كلمة، 
قلنا الـ example ده قبل كدة، ذهب.
في اللغة العربية، ذهب لو معليهاش تشكيل عشان ذَهَبَ دي فعل، لو معليهاش تشكيل ذهب دي بمعنى go راح، وممكن ذهب بمعنى دهب gold، فدي تبقى كلمة ambiguous، كلمة تحمل أكتر من معنى، كذلك.
الـ grammar بتاعي ممكن يخلي لي الـ string دي بتيجي بأكتر من طريقة فبالتالي تحمل أكتر من معنى، تعالوا نشوف إزاي،
 Parse trees and syntax trees uniquely express the structure of syntax، 
يعني إيه الكلام ده؟ الـ parse tree أو الـ syntax tree المفروض uniquely يعني يبقى عندي parse tree واحدة أو syntax tree واحدة.
للـ string بتاعي  للـ ... للـ program بتاعي اللي أنا بعمله compiling، 
بس however الـ grammar اللي عندي ممكن يسمح إن الـ string ده يبقى ليه أكتر من parse tree، لو الـ grammar سمح بـ ده وأنا بكون الـ parse tree لقيتني عملت أكتر من parse tree لنفس الـ string.
يبقى الـ grammar ده فيه ambiguity وبالتالي محتاج يتعمل له disambiguating تمام؟ زي إيه؟ تعالوا نشوف، expression الـ grammar اللي إحنا شرحناه أول واحد خالص في 
الـ CFG
expression operation expression أو expression ما بين قوسين أو number، 
والـ operation عبارة عن plus و minus و multiplication.
تمام، طيب تعالوا نشوف الـ string ده 34 minus 
3
multiplied by 42
again again يا باشمهندسين أنا مش بتكلم mathematical wise، أنا مش عايز أعرف هي كام، أنا عايز أعرف هتعامل معاها كـ string إزاي، وبالتالي طبعاً يعني بيبقى
 into consideration إن أنا هرمي دي بعد كدة هديها الـ parse tree دي أو الـ syntax tree دي.
للـ semantic analysis phase فلازم أكون حاطة into consideration
إن أنا لما آجي أحسبها طالما طلعت parse tree صح يبقى هي دي فعلاً كـ semantic wise هتبقى ليها معنى صح، بمعنى إن أقدر أجيب two trees، ممكن يكون في أكتر في بعض
 الـ strings الأخرى.
الـ grammar ده لما أعمل derivation أقدر ألاقي له اتنين derivation لنفس الـ string ده اللي هو 34 
minus 3
 multiplied by 42، الـ two derivations طلعوا لي two trees والاتنين left-most،
نفتكر left-most derivation إن أنا بعمل replacement من الشمال لليمين،
طيب تعالوا نشوف إزاي، expression عبارة عن expression operation expression، دول parse trees طبعاً.
وهنا اعتبرت الـ operation اللي هي الـ multiplication 
هي اللي فوق followed by الـ number اللي هو 42، والـ expression ده أخدته اللي هو number minus number، اللي هو expression operation expression عبارة عن number minus number، طيب في الـ tree دي mathematical wise اللي هو مش موضوعي في الـ parsing بس mathematical wise.
هيتحسب إيه؟ قلنا من الشمال لليمين من تحت لفوق، 
أنا في الشمال وتحت يبقى هنا هيتحسب 34 
minus 3 لو أنا رحت للـ semantic analysis مش في الـ parsing،
 هيتحسب هنا 34 
minus 3 
then multiplied by 42، طيب تعالوا نشوف الـ tree التانية
 expression operation expression.
هنا الـ number اللي هي 34، هنا الـ minus، 
هنا الـ expression operation expression اللي هي number times number 
اللي هي 3 
times 42، هنا هيتحسب إزاي؟ 34 minus something، 
الـ something دي هبدأ أحسبها من تحت لفوق يعني الـ multiplication بتاع 3 
by 42، اللي هيطلع رقم، الرقم ده هطرحه من 34، ما يهمنيش هيطلع كام.
طيب mathematical wise كـ semantic wise أنا عايزة أنهي أنا عايزة أنهي tree،
 أنهي tree هي اللي صح؟ أنهي tree هي صح؟ يبقى أنا طالما دي mathematical operation، mathematical equation يبقى لازم أرجع للـ rules بتاعت 
الـ mathematics، طيب لو الحاجات دي بتيجي في الـ...
فوازير بقى ويلا حل وشوف الـ value دي هتطلع إيه، طيب
 تعالوا نشوف اللي بيحكم لي هنا الدنيا أنا معنديش أقواس، ا
لأقواس حتى أنا حاطاها هنا يعني just for clarification الـ example ده حتى لو هي موجودة أنا هنا it doesn't represent something لأن هي الـ 3 على الـ outer يعني، فهنا مش بتحكمني الـ precedence، طب الـ precedence عندي هنا 34 
minus 3
 times 42، يا ترى هعمل multiplication الأول ولا هعمل الـ subtraction الأول؟ أنا الطبيعي بمشي من الشمال لليمين.
فالطبيعي المفروض أعمل الـ subtraction، بس أنا عندي لو subtraction
 و subtraction يبقى هبدأ هنا الـ subtraction دي بعد كدة دي، 
أو subtraction و addition ليه لأن هم ليهم نفس الـ precedence نفس الأولوية نفس الأسبقية، لكن الـ multiplication والـ division ليهم أسبقية أعلى،
 يعني أنا لو الاتنين جم ومافيش أقواس.
في addition وفي multiplication ابدأ بالـ multiplication حتى لو
 الـ multiplication هي على اليمين، يعني 34
 minus 3
 times 42 يبقى هبدأ بالـ multiplication الأول اللي هي 42
 times 3، أضربها في 3 واللي هيطلع هطرحه من 34، أنهي tree بقى اللي بتقول لي الصح 
الـ derivation الصح؟
يا ترى ده ولا ده؟ يا ترى أنا هنا عشان عندي multiplication أعلى، في علامة
 الـ multiplication موجودة في level أعلى في الـ tree، هل كدة معناها
 higher precedence؟ لأ العكس تماماً، الـ multiplication هنا كل ما أنا أعلى في الـ tree كل ما أنا أقرب للـ root كل ما ده معناه إن أنا ليا lower precedence، ليه؟ لأن أنا بحسب من تحت لفوق.
يعني أنا هنا هحسب subtraction
 then multiplication، هنا هحسب الـ multiplication واللي هيطلع هعمل له subtraction من الـ number، يبقى هي دي الـ tree التانية هي دي اللي صح. Okay؟
 يبقى أنا عايزة أوصل للـ rule بتاعتي أعمل لها disambiguating الـ context-free grammar بحيث إنها تطلع لي الـ tree دي بس.
مش عايزاها تطلع لي الـ tree دي، ده الـ derivation بتاع الـ tree الأولانية،
left-most derivation أهو expression operation expression، 
وبعد كدة شلت الـ expression حطيت شلت الـ expression ده حطيت expression operation expression تاني.
الـ comma دي زيادة، بعد كدة شلت الـ expression ده حطيت number،
 أهو left-most بقى فببدأ أعمل replace من الشمال لليمين، كل non-terminal على الشمال أبدأ أ replace ـوا
، number minus number، بعد كدة الـ operation دي multiplication أهي بعد كدة number، okay؟
الـ left-most derivation التانية
 expression operation expression
, number operation expression,
 number minus expression
, number minus expression operation expression, 
يبقى number minus number multiplied by number، 
دي هي الـ derivation اللي هتديني الـ value صح.
إن number minus expression
, 34 minus حاجة، الحاجة دي هيتعمل لها evaluation الأول بعد كدة إيه أبدأ أعمل لها subtraction من الـ number الأول. الـ syntax tree بتاعتها إزاي؟ 
دي الـ left-most derivation الأولانية، الـ multiplication أهي بقت هي الـ root.
الـ root نازل منها 42 على اليمين ونازل منها 34 
minus 3 يبقى هعمل addition بعد كدة multiplication، التانية left-most derivation التانية الـ tree التانية الـ subtraction أهي نازل منها 34 والناحية التانية نازل منها multiplication of 3 times 42، 
قلنا مين اللي صح؟ هي اللي تحت، التانية دي هي اللي صح.
أوكي، يبقى الـ ambiguous grammar
هو grammar that generates a string with two or more distinct parse trees
, two different parse trees or more، such a grammar represents a serious problem for a parser، 
مش هينفع، مش هينفع أعمل له programming زي فكرة الـ non-determinism في الـ...
في الـ NFA، كان لازم أحولها لـ DFA بالـ subset construction 
علشان أشيل موضوع الـ non-determinism، إن أنا مش عارفة أروح يمين ولا شمال، نفس الكلام هنا، أنا عندي parse tree و parse tree تانية و parse tree تالتة للـ string الواحد، شوف بقى الـ program اللي أنت بتعمل له compilation كام string، فبالتالي لو كل واحد له اتنين تلاتة parse trees فالاحتمالات كتير أوي أـ combine الـ parse tree دي مع
 الـ parse tree التانية.
ولا أـ combine الـ parse tree التانية بتاعت الـ string الأولاني مع الـ parse tree التانية 
بتاعت الـ string التاني وهكذا، فأهم حاجة إن أنا الـ grammar بتاعي يبقى مش ambiguous عشان يبقى سهل عليا إن أنا أبني parser
however الـ ambiguity في الـ grammar مش بسهولة إن أنا أشيله زي ما شلت الـ non-determinism في الـ NFA.
معنديش algorithm محدد عندي شوية techniques،
لكن مفيش algorithm محدد أوصل له أقدر أقول إن أنا ده لو مشيت على steps 1, 2, 3
 الـ grammar ده مش هيبقى ambiguous
okay؟ في بعض الـ helping techniques مش شرط تكون applicable على كل 
الـ grammars ومش شرط إن أنا لما أطبقها تشيل الـ ambiguity من الـ grammar.
أول method ده بمنتهى البساطة إن أنا بقول والله أنا عندي مثلاً two parse trees
 زي مثلاً ما شفنا، أحدد الـ disambiguating rule يعني الـ rule بيقول لي إن أنا
 والله الـ tree الصح هي كذا، الـ advantage of this method it corrects the ambiguity without changing the grammar بمنتهى البساطة.
لكن طبعاً ما هواش applicable ما هواش reliable ما هواش يعني professional
، syntactic structure of the language is no longer given by the grammar alone، يعني أنا مابقتش عارفة أحدد الـ structure بتاع الـ grammar بتاعي طالما أنا مغيرتش الـ grammar، لأ أنا بس مجرد بقول إن الـ string اللي طالع لي آه أنا accepting
 الـ string ده والـ string ده.
الـ Tree دي والـ Tree
Method التانية changing the grammar into a form هي دي الـ method الأصح بس زي ما اتفقنا هي ما هياش easy، بحوله لـ form
 forces the construction of the correct parse tree thus removing the ambiguity. 
Of course in either method we first decide.
Which of the trees in an ambiguous case is the correct one؟ 
لازم أحدد هي إيه، أنهي واحدة اللي صح عشان بناءًا عليه أبدأ أغير في الـ rule بتاعي بحيث مايطلعليش غير الـ parse tree دي، simply state this disambiguating rule that establishes the relative precedence of the operations represented 
مثلاً لو أنا عندي كذا operation بقوم مزودة شوية rules تقولي إن ده أعلى من ده، هنشوف example بعد شوية.
The standard solution is to give addition and subtraction the same precedence and to give multiplication higher precedence
يعني أفرقهم عن بعض، يعني الـ plus والـ minus مع بعض في rule ومحطش معاهم 
الـ multiplication
a further disambiguating rule is the associativity، إيه الـ associativity؟
إن أنا اللي هي الـ recursion 
في left associative و right associative زي left recursive و right recursive
 أنا لو عندي دايماً الـ ambiguity بتيجي لو أنا عندي مثلاً على الـ right hand side
left و right recursive، أخليها حاجة واحدة علشان متبقاش ambiguous.
specify that an operation is non-associative، a sequence of more than one operator in an expression is not allowed، 
ما ينفعش أعمل أكتر من operator في الـ expression الواحد، ده هيسهل لي
 الـ ambiguity
for instance writing simple expression grammar in the following form.
Expression عبارة عن factor operation factor 
أو factor، والـ factor عبارة عن expression ما بين قوسين أو number، 
والـ number عبارة عن plus أو minus أو multiplication، إيه اللي اتغير هنا؟ 
إن أنا شلت الـ recursion، شلت الـ associate، ده مابقاش associative، ليه؟ ده
 non-associative علشان أنا عندي هنا مابقاش فيه على الـ right hand side
expression خالص.
خلاص، الـ rule عندي كانت بتقولي expression عبارة عن 
expression operation expression، 
لأ أنا جبت rule جديد اسمه factor وحطيت هنا الـ factor فده هيشيل لي الـ recursion، 
طيب لو عندي بقى الـ string
such as 34 نفس الـ string بس minus و minus و 34 هو نفس الـ string بس هنا multiplication.
في الحالة دي مش legal، 
أنا في الحالة دي لما عملت الـ rule اللي فاتت أنا  I enforced إن هو يحط أقواس،
 ففي الحالة دي الأقواس هتجبره إن هو يقول له لا احسب كذا أو احسب كذا، ده أحد الحلول، عملت disambiguating rule، لا والله الـ rule بتاعي إن أنا لازم الـ string يكون فيه أقواس ما بين كل اتنين.
Operands، 
فيا تحط لي هنا قوس يا تحط لي هنا قوس، يا تحط لي هنا قوس يا تحط لي هنا قوس، 
فبالتالي أنا أجبرت اللي بيكتب الـ string إن هو يقول لي هبدأ بأنهي evaluated الأول،
 not only change the grammar also change the language being recognized، كمان الـ language نفسها اتغيرت ليه؟ لأن مابقيتش أقبل الـ string اللي مفيهوش أقواس.
تمام، الـ expression بقى عندي الـ الحالة التانية اللي أنا كنت بقولها إن أنا فصلت
 الـ precedence عن بعض، يعني الـ add عملت بدل ما أقول operation وحطيت plus و minus و multiplication، لأ عملت add operation لوحدها دول ليهم نفس
 الـ precedence.
Multiplication operation لوحدها وليها نفس الـ precedence، 
هنا زودت الـ rules بقت هنا expression add operation expression
 still لسه فيه هنا recursion
add operation عبارة عن plus و minus، بعد كدة term جبت هنا term خليته قلت له term عبارة عن multiplication operation أو term أو factor.
Factor والـ factor هو expression ما بين قوسين أو number
addition and subtraction will appear higher closer to the root، ليه؟ 
أنا كدة أجبرته I enforced him إن هو الـ plus والـ minus ييجوا أعلى في الـ tree ليه؟ 
لأن هم اللي أقرب للـ first symbol اللي أنا ببدأ بيه الـ tree، فكل ما بعلى في الـ tree 
بالـ operation كل ما ليها أقل في الـ precedence.
فأنا هنا عايزة الـ plus والـ minus يبقوا أعلى في الـ tree عشان هم ليهم أقل precedence
فأنا في الحالة دي بالقانون اللي أنا عملته ده خليت إن هم فعلاً هيبقوا أعلى في الـ tree فبالتالي هيبقى ليهم less precedence فبالتالي هييدوا result 
precedence cascade, grouping operators into different precedence levels.
Cascade is a standard method in syntactic specification using BNF
BNF اللي هي طريقة كتابة الـ Context-Free Grammar
replacing the rule, يعني عندي expression عبارة عن
 expression add operator expression
left and right recursive أو term, يعني أنا عملت أول حاجة الـ precedence, تاني حاجة عايز أشيل بقى إيه...
الـ recursion ده الـ associativity
فممكن أقول أخليها left recursive only فبالتالي أخلي الـ expression دي 
وبعد كدة أ add
 operator وبعد كدة term ليه term؟ لأن أنا عندي هنا الـ expression ممكن يبقى term فأنا بدلت الـ expression دي بالـ term، فبالتالي شلت 
الـ right associativity أو الـ right recursion.
أو أخلي الـ right recursion وأشيل الـ left recursion
okay؟ فبالتالي يبقى أنا كدة أنا شلت مخلتهاش right and left recursive
أو right and left associative فبالتالي لغيت الـ ambiguity، 
يبقى أنا ظبطت الـ precedence وظبطت الـ associativity.
ده هيـ remove الـ ambiguity عندي في حالة الـ mathematical operation
يبقى الـ final grammar أهو
 الـ expression عبارة عن expression add operation expression
sorry expression add operation term or term
 والـ add operation 
plus أو minus، آدي الـ precedence، والـ term عبارة عن term multiplication operation factor أو factor.
و الـ multiplication operation هي times لو عندي division هتتحط هنا. 
والـ factor هي عبارة عن expression ما بين قوسين او number.
 بالتالي I enforce him ده تالت حاجة اللي احنا قلناها في الاول ان هو يحط اقواس
فحاجة زي كده 34
3 minus و multiplied by 42 اللي كانت فيها ambiguity وطلعالي و بـ 2 
parse trees مرة بحسب الـ subtraction الأول وبعد كدة مرة تانية بحسب
 الـ multiplication.
لو جبت ورقة وقلم كدة وكتبت الـ rules اللي في الـ slide اللي فاتت ومشيت عليها في 
الـ derivation هلاقي إن الـ expression عبارة عن
 expression add operation term، والـ expression ده عبارة عن term، 
الـ term اللي هو factor اللي هو number، اللي هو هيكون 34، 
الـ add operation جت الأول أهي  فأجبرت نفسي إن أنا أعمل precedence الأقل فوق اللي هي الـ minus.
term عبارة عن term multiplication operation factor،
 والـ factor اللي هي number اللي هي 42، 
والـ multiplication operation اللي هي multiplication أهي، 
والـ term اللي هي factor اللي هي number اللي هي 3. دي الـ tree الوحيدة اللي هقدر أطلعها، لو عرفت تطلع tree تانية يبقى أنا كدة لسه still فيه ambiguity.
في حالة الـ subtraction أهي نفس الفكرة، expression add operator term 
والـ term ده عبارة عن factor والـ factor ده number اللي هو 42
 الـ minus أهي، هنا ده expression ده بقى left recursive أهو
left recursive يعني هتلاقي الـ tree عمالة أبدل أبدل أبدل في الشمال
 يعني حتى لو في expression تاني هييجي كدة.
Okay ؟ فبالتالي هنا هيعمل 
number minus number followed by minus number
التالتة، طيب، في بقى عندي problem تانية شهيرة غير بقى
 الـ mathematical precedence.
هي الـ dangling else problem، إيه الـ dangling else؟ 
لو افتكر كدة في بداية ما كنت بتتعلم programming
 C++ أو whatever the language، الـ if condition، لو عندي nested if
 if expression أو if condition
 then كذا.
else كذا دي مش nested if 
دي if else عادية طب if condition جواها أو if condition
 then كذا if condition
 then كذا else كذا else واحدة وعندي وقبليها 2 
if nested جوا بعض ال else دي بتتبع الـ inner if ولا الـ  outer if
دي اسمها الـ dangling else problem 
dangling يعني else كدة مالهاش صاحب، يا ترى بتتبع دي ولا بتتبع دي؟ الـ rule عندي في معظم الـ languages إن ماكانش كلهم، إن الـ else دايماً 
follows the nearest if يعني أنا عندي هنا هتبقى it follows the nested if أو
the inner if.
نرجع للـ rule بتاعنا اللي هو الـ Context-Free Grammar 
بتاع الـ if
 if statement other, if expression statement or if expression statement else statement
 This grammar is ambiguous، ليه؟ لو عندي الـ nested if اللي كنا بنتكلم عليها
 if 0 if  1 other, else other.
في كل الـ languages زي ما اتفقنا الـ else المفروض بتتبع 
 الصح إن الـ else دي هتـ follow الـ if دي، إلا لو أنا حاطة braces. طيب
 في حالة الـ grammar بتاعي ده اللي هو يبدو إنه simple وبسيط و straightforward،
 لا أنا عندي ambiguity، ليه؟ عندي statement عبارة عن if statement أهي
 الـ statement بتاعتي if 0 if 1 other, else other.
في الحالة الاولانية عندي statement عبارة عن if statement 
خدت ان الـ if 
expression statement else statement اعتبرت ان الـ else تبع الاولانية. 
okay؟ والstatement اللي جوه الـ if statement الاولانية هي جواها الـ nested if التانية اللي هي من غير else.
 ممكن بنفس الـ Grammar على نفس الـ string اجيب Tree تانية لا 
خدت الـ if expression statement.
يبقى الـ outer if expression
statement واحدة والـ statement دي عبارة عن الـ if else، وده 
 دي المفروض برضو الـ tree التانية دي هي اللي صح semantic-wise
parsing أنا كدة الـ parsing الاتنين صح، الاتنين صح بالـ grammar اللي عندي 
بس أنا لو عندي grammar بيطلع لي two different parse trees.
لنفس الـ string يبقى أنا الـ grammar ده مش مظبوط، 
ده ambiguous ولازم أعدله، طيب، Which tree is correct depends on associating
 the single else part with the first or the second if
حسب الـ rule بتاعي، افرض أنا مثلاً language بتقولي لا أنا الـ else بتاعتي هتتبع الـ if اللي فوق، حسب الـ rule بتاعي.
This ambiguity called dangling else problem, disambiguating rule is the most closely nested rule, implies the second parse tree above is the correct one
يعني إيه؟ for example 
if x not equal 0, if y == 1/x
okay ده boolean variable حطيته بـ true
 else z equal 1/x، الـ else دي المفروض بتتبع ده.
If you wanted, we could associate the else part with the first statement by using brackets، 
ممكن أنا أجبره إنه يحط brackets نفس فكرة إن أنا أجبرته إنه يحط لي brackets ويحدد لي أنا هحسب الـ addition الأول ولا هحسب الـ multiplication. ممكن أحلها إن أنا أغير شوية في 
الـ rule، بقول له عندي statement بدل ما كانت if statement أو other، 
خليتها matched statement أو unmatched.
Matched يعني if else
، unmatched يعني أي حاجة تانية matched statement
if expression ممكن يبقى جواها matched statement else 
matched statement، يعني أنا بجبره إن أنا أي حاجة nested جوا الـ if هتبقى
matched هتبقى if else، أي حاجة بعد الـ else هتبقى matched.
أو Other.
 الـ Unmatched ممكن تبقى If Expression Statement 
خلاص يا If Statement مفيهاش Else لأنها Unmatched. أو If Expression Match
 Statement
Else Unmatched. يا اما مفيهاش Else أصلاً يا اما هنا فيها Matched واـ -Else هي اللي بعدها Unmatched. يبقى أنا اللي Accepted عندي إن أنا بجبره هنا
 All Else Parts Must Be Matched As Soon As Possible.
except آخر واحدة، ممكن ييجي بعدها if statement مفيهاش فيها else مفيش مشكلة إنما أي else كدة هتيجي لي لازم هتكون matched مع أقرب if ليها. 
Now for the statement نفس الـ statement اللي فاتت if 0 if 1 other else other تعالوا نشوف على الـ grammar ده لو مشيت هطلع إيه.
 statement عبارة عن unmatched statement ده parse tree.
if expression statement 
طيب الـ statement اللي هنا عبارة عن matched
 if expression matched statement else statement
 يبقى أنا هنا مقدرتش أطلع برضو غير tree واحدة matching الـ grammar بتاعي و مع
 الـ string بتاعتي الـ derivation في حاجة اسمها بقى unessential ambiguity
إيه الـ unessential يعني ambiguity بس مش فارقة معايا أوي
 كـ semantic. الـ grammar
 may be ambiguous and yet always produce unique abstract tree
 يعني ممكن يبقى ambiguous grammar لكن بيطلع لي abstract syntax tree واحدة، زي مثلاً بتاع الـ semicolon separator ده، either
 الـ right recursive أو الـ left recursive grammar rule.
would still result in the same syntax tree structure 
 لو شلته وخليته left recursive بس أو right recursive بس هيطلع لي نفس
 الـ syntax tree دي بتتسمى unessential ليه؟ لأن أنا لو s semicolon s 
بادية من الشمال لليمين أو s semicolon s بادية من اليمين للشمال مش هتفرق معايا زي ما بعمل addition خمسة plus أربعة plus تلاتة أجمع خمسة وأربعة الأول وبعد كدة تلاتة هي هي لو جمعت أربعة وتلاتة الأول وبعد كدة خمسة.
الـ associated semantics
 do not depend on what disambiguating rule is used
arithmetic addition مثلاً أو string concatenation، الـ addition أو إن أنا بلزق two strings في بعض مش فارقة معايا الـ associativity، هبدأ من الشمال ليمين ولا من اليمين للشمال
 الـ dot product.
Binary operator لو أنا عندي الـ rule بتاعت if a dot b dot c
 equal هي a dot b dot c وهنا سواء حسبت ده الأول أو ده الأول
 الـ dot دي ممكن تكون plus ممكن تبقى concatenation ممكن تبقى ORing أي حاجة، يبقى الـ operation دي مش فارقة معايا الـ ambiguity بتاعتها لأنها نفس الـ meaning زي ما قلنا خمسة plus أربعة plus تلاتة.
لو جمعت 5 و 4 اللي هي الـ 9 الأول بعد كدة حطيتها على الـ 3 بقت الـ 12 هي هي لو جمعت الـ 4 و 3 الأول اللي هي الـ 7 بعد كدة حطيتها على الـ 5 اللي هي بقت 12
 in this case the syntax trees are still distinct but represent the same semantic value عندي أكتر من syntax tree في الحالة دي ولكن
ليهم semantic value واحدة في الآخر، 
بس however طبعاً يفضل إن الـ parsing algorithm يكون برضو معمول لها disambiguating، لكن لو معملتهاش مش هتأثر أوي في الـ semantic analysis لكن هتبقى يعني تستهلك more processing
okay؟
يبقى الـ challenges in parsing تاني، 
لو عندي int multiplied by int plus int مثلاً، 
فعندي في الـ grammar الشهير بتاعي ده، E عبارة عن E operation E، 
طيب، الـ operation دي ممكن أخدها هي الـ multiplication والـ E تبقى اللي هي الـ int، والـ E التانية تبقى E operation E اللي هي int plus.
في الحالة دي إن أنا عملت إيه، الـ تحت الأول، أنا بحسب الـ تحت الأول، 
عملت الـ addition بعد كدة multiplication، ده الصح؟ لا الصح هي التانية دي
 right most derivation، جيت هنا لأ أخدت الـ E هي E operation E اللي هي int multiplied by int plus int.
في الحالة دي عملت الـ multiplication الأول، 
أنا في الـ rule ده الـ multiplication طبعاً هتبقى الأول لأن هي جاية الأول وهي
 الـ higher precedence، فهي الـ multiplication نزلت تحت في الـ tree يبقى هي ليها
 الـ higher precedence يبقى أنا كدة الـ tree دي هي اللي صح، يبقى
 الـ Context-Free 
Grammar ambiguous if there is at least one string with two or more parse trees.
Note that ambiguity is a property of grammars, not language،
 يعني أنا مش هقول إن الـ language ambiguous،
 أنا أقول إن الـ grammar rule هي اللي ambiguous، هي الـ grammar rule هي اللي ambiguous مش الـ strings اللي جوه الـ language هم اللي ambiguous،
 طريقة إن أنا أعملهم derivation هي اللي ambiguous أقدر أجيبها بكذا طريقة
 there is no algorithm for converting an arbitrary ambiguous grammar into an unambiguous one.
in some grammars inherently ambiguous meaning that no unambiguous grammar exist for them
في grammars ما ينفعش إن أنا أعمل لها disambiguation خلاص هيفضلوا ambiguous
there is no algorithm for detecting whether aribtrary grammar is ambiguous
برضو مفيش طريقة بنقعد نجرب strings
ونشوف والله لو لقيت string ليه أكتر من parse tree 
يبقى أنا كدة ده ambiguous grammar
is ambiguity a problem؟ depending on semantics، يعني لو عندي الـ role ده int و E plus E، ممكن أقول خمسة plus تلاتة plus سبعة أهي.
بالطريقة دي E plus E و E دي خمسة و E دي عبارة عن تلاتة plus سبعة
في الحالة دي هجمع التلاتة والسبعة الأول اللي هي عشرة وبعدين أجمعها على الخمسة، 
وممكن أقول إن أنا هجمع الخمسة والتلاتة الأول وبعد كدة أجمعها على السبعة، في الحالتين semantically the same فساعتها ambiguity مش problem مش هتأثر على 
الـ semantic analysis.
However هتأثر في الـ processing 
هيطلع لي أكتر من tree فبالتالي الـ processing هيبقى أكتر شوية
طب لو جالي بقى subtraction في الحالة دي هتأثر آه، يعني خمسة ناقص تلاتة زائد سبعة 
غير خمسة ناقص تلاتة لوحدها زائد سبعة.
If a grammar can be made unambiguous at all it is usually made unambiguous through layering 
حاجة اسمها layering بعملها layers layers بزود rules الـ rules دي تفصل
 الـ associativity وتفصل الـ precedence
have exactly one way to build each piece of the string, have exactly one way of combining those pieces back.
ناخده من ورا لقدام يعني نشوف الـ string جاي إزاي ونبدأ منه أ build
 up a rule تعملي layers توصلني للـ إيه؟ إن أنا أ handle الـ precedence وأ handle 
الـ recursion يعني، فاكرين balanced parentheses
epsilon.
أو left 
right bracket إن كل left bracket يتقفل، طيب 
ممكن ده grammar يـ generate الـ balanced parentheses دي، 
P عبارة عن epsilon أو PP أو P ما بين قوسين. 
عايزين نـ generate الـ string ده من الـ grammar ده، أول حاجة أنا عندي
 surrounding brackets يبقى هاخد الـ rule ده، P ما بين قوسين يبقى هم دول
 الـ terminals دول.
وعندي بقى اللي في النص هبدأ أجيبهم، اللي هي عبارة عن PP 
والـ P دي اللي هي P ما بين قوسين و P بقت empty والـ P التانية نفس القصة
 والـ P بقت empty. طيب، وممكن لقيت لها parse tree تانية unexpectedly.
ممكن أخد الأول الـ concatenation rule اللي هو PP والـ P دي بقت epsilon وبعد كدة 
الـ P دي similarly زي الـ slide اللي فاتت، اللي هي عبارة عن P ما بين قوسين والـ P دي عبارة عن PP والـ P دي عبارة عن قوسين جواهم epsilon وهكذا، فعرفت إن أنا برضو بالـ rule إن أنا أجيب...
Tree تانية unexpectedly يعني اللي فاتت دي أقرب للتفكير، 
لكن لأ حد قعد بقى يفكر زيادة لأ أنا عندي Tree تانية فده كدة ambiguous grammar String of balanced parentheses is a sequence of strings that are themselves balanced parentheses
To Avoid ambiguity و can build a string in two steps 
decide how many different substrings we will glue together.
أشوف كام substring هلزقهم مع بعض concatenated 
وبـ build
each substring independently. يعني 
spread a string of parentheses across  the string، there is exactly one way to do this for any number of parentheses, expand out each substring،
 إيه الكلام ده؟ يعني الـ rule اللي فاتت بدل ما كانت rule واحدة.
عبارة عن P
S  ما بين قوسين- P ما بين قوسين أو PP أو كدة، لا فصلتهم، خليت الـ concatenation الأول، الـ S عبارة عن PS or epsilon، 
وبعد كدة الـ P هي عبارة عن S ما بين قوسين، يبقى الـ concatenation هتيجي لي الأول.
followed by الأقواس يعني لو عايزة أجيب الـ string ده derive الـ string ده، 
أهو S عبارة عن PS، PS بقت PPS، الـ S دي بقت empty بقت PP وهكذا، 
ده كدة unambiguous grammar لو جربت كذا يعني نفس الـ string ده أجيبه بكذا طريقة مش هعرف.
طيب الـ a more trickier grammar
، grammar يوصف لي regular expression، ينفع كدة؟
 آه ينفع، ما هو الـ regular expression دي حاجة ليها طريقة كتابة،
 ليها syntax، طيب الـ syntax بتاعها إزاي أوصفه بـ Context-Free Grammar؟
والله نفتكر مع بعض الـ regular expression عبارة عن any letter أو epsilon 
يا إما concatenation يا إما union اللي هي الـ choice يا إما closure 
يا إما parentheses، دول الـ possible things
 that come in regular expression تعالوا نكتبها كـ rule
 الـ regular expression can be any letter: a, b, c.
Regular expression can be epsilon
 epsilon ما بين double quotes معناها إيه؟ معناها إن الـ string ده معايا في الـ rule
ده terminal، ما هواش meta character الـ epsilon اللي هو الـ empty character، طيب الـ R هنا عبارة عن concatenation
 RR، والـ R ممكن تيجي R or R، طب الـ or هنا برضو.
Differentiated عن الـ or دي، الـ or هنا أقصد الـ or بتاعت الـ Context-Free Grammar، الـ or هنا علامة الـ or علامة الـ bar دي اللي هي ما بين two Rs
 in double quotes 
كـ string إن العلامة دي بتجيلي في الـ grammar في الـ regular expression يعني، علامة الـ asterisk اللي هي الـ closure.
وبعد كدة الـ R اللي ما بين قوسين، لو عايزة أ derive
A or B closure، الـ R دي ممكن تديني الـ concatenation أهي RR، 
الـ R دي اللي هي الـ A، مش الـ concatenation
 sorry ده الـ choice.
بدأت بالـ choice
R or R لأن أنا عايزة A or B closure
، R or R، الـ R دي اللي هي ايه؟، الـ R دي اللي هي R اللي هي B
R closure والـ closure أهي جت لي تحت، يبقى تاني عشان ما نتلخبطش، 
أول طريقة أجيب A or B closure إن أنا R عبارة عن R or R.
والـ R دي هي الـ A، 
والـ R دي عبارة عن R closure اللي هي B closure، 
في الحالة دي أنا أعني A or B closure، الـ closure على الـ B. 
طب أنا لو خدتها R closure، وبعد كدة الـ R closure دي سيبت الـ closure تحت، 
وخدت الـ R دي عملتها R or R، ودي A ودي B، دي معناها A or B
 closure.
يبقى أنا A or B closure ممكن أجيب لها two parse trees 
من الـ grammar ده يبقى ده ambiguous، طبعاً هو ambiguous ليه؟ 
الـ two rules دول أكيد ambiguous
left and right recursive و left and right recursive، فأنا عرفت أجيب نفس الـ string أجيب له two parse trees، ده له معنى وده له معنى تاني، دي A or B closure في
 الـ regular expression كان ليها معنى.
هنا A or B 
all closure كان ليها معنى، طيب أ resolve الـ ambiguity دي إزاي؟ 
أخدها بالعكس، أشوف الـ string هو أنا إديت precedence لإيه الأول، 
لو عندي A A
 or B closure، طيب مين الأول؟ الـ B closure
نفتكرها في الـ grammar في الـ rules بتاعت الـ regular expression، 
الـ closure كان ليها higher precedence ثم الـ concatenation ثم الـ choice
يبقى أنا هي دي المقصود بيها الـ layering، يبقى أنا هعمل الـ closure الأول،
 الـ concatenation تاني.
حاجة الـ choice تالت حاجة، واتفقنا إن اللي ليها higher precedence بتبقى تحت في 
الـ tree واللي ليها lower precedence بتبقى فوق في الـ tree، فبالتالي ده أما أجيبه أحوله
 لـ rule ده الـ ambiguous grammar حولته لـ rule
 unambiguous إزاي؟ حطيت إحنا اتفقنا عايزين الأقرب للـ rule.
هي الأقل في الـ precedence اللي هي الـ choice، يبقى الـ R عبارة عن S أو 
R or S، ثم الـ concatenation الـ S دي بعمل لها rule جديدة عبارة عن T أي 
notation جديدة أو ST، أنا محطتيش SS هنا محطتيش R هنا عشان ميبقاش فيه 
الـ ambiguity بتاعت الـ recursion والـ associativity.
طيب الـ ST أهي، الـ T بقى هبدأ أعرفها عبارة عن U أو T closure اللي هي أعلى واحدة في 
الـ precedence، الـ U أبدأ أحط بقى الحاجات الـ terminals
A or B or C
epsilon، أو الـ R اللي ما بين قوسين.
Only generate atomic expression put stars onto atomic expression, 
بعد كدة بـ concatenate الـ starred expression، بعد كدة بعمل الـ union
 كأقل ايه precedence، لما أجي بقى أجيب AB or C or A closure من الـ grammar اللي أنا عملته واللي أنا بقول إنه unambiguous تعالوا نشوف.
ببدأ الـ R أهي دي regular expression عبارة عن إيه، هبدأ بمين في دول، 
الـ R أنا عندي أقل precedence اللي هي الـ choice، يبقى R or S 
أهي جبت الـ choice ده، ثم هاخد الـ R دي أنا عندي choice تاني فـ R or S أهي.
ثم هاخد الـ R دي أنا left left recursion أهو leftmost derivation،
أجيب مين، الـ R عبارة عن S بقى معنديش choice تاني، الـ S فيها concatenation أنا عندي هنا concatenation أهي اللي هي ST، طيب الـ ST طب الـ S عبارة عن T.
والـ T عبارة عن U والـ U عبارة عن A، والـ T عبارة عن U والـ U عبارة عن B، 
طيب يبقى أنا جبت ايه ؟ B or ففاضل الـ C، الـ C أنا هنا واقفة عند الـ S هتبقى T والـ T عبارة عن U والـ U عبارة عن C، طب دي عايزة أجيب الـ closure بقى.
أقل واحدة في الـ rule، اقل واحدة يعني آخر واحدة مكتوبة في الـ rule عشان هي ليها 
الـ highest precedence، فـ هعمل إيه؟ الـ S دي عبارة عن T ولا ST؟ لا ST  
T قصدي، والـ T هي عبارة عن T closure.
الـ T closure، الـ closure خلاص ده terminal، فاضل الـ T عبارة عن U والـ U عبارة عن A، يبقى أنا بالـ layering كدة عرفت إن ده الأول ثم ده ثم ده ثم ده، فبالتالي عرفت
 أ reformulate الـ grammar بتاعي، اتفقنا إنه مالوش قاعدة، الحل الكتير وأشوف مسائل كتير محلولة ده هيسهل لي إن أنا.
أتعود عليه، الخلاصة الـ Parse tree
 is a Concrete syntax it shows exactly how the text is was derived
 concrete عشان فيها الـ rule، الـ more useful structure is an Abstract Syntax Tree
which retain only the essential structure of the language
Syntax analysis أو اللي هو الـ parsing 
extracts the structure from the tokens produced by the scanner. 
الـ languages
 are usually specified by context-free grammars.
 الـ parse tree
 shows how a string can be derived from a grammar
. الـ grammar
 is ambiguous if it can derive the same string in multiple ways 
there is no algorithm for eliminating ambiguity it must be done by hand
abstract syntax trees contain an abstract representation of a program syntax ده reference video عن الـ ambiguity وإزاي عمل 
disambiguity with context-free grammar اللي interested الموضوع ده بيبقى hot topic في natural language processing أي حاجة أي research أي projects مستخدمة NLP اللي هو
تتكلم على أي language عموماً سواء أي حاجة زي compiler بتتكلم على 
الـ programming languages أو حاجة شغالة في natural language الـ ambiguity ده من topics المهمة جداً فممكن تبقوا تقروا فيه وتتعلموا فيه يعني techniques تانية كتير thank you و أشوفكم المحاضرة الجاية
و شكرًا