بسم الله الرحمن الرحيم الصلاة والسلام علي أشرف
المسلمين اليوم إن شاء الله نبدأ موضوع جديد اللي
هو الـ code generation بس الـ code generation اللي
احنا فاهمين إنه بيتم على مستويين فيه في الأول الـ
intermediate code generation و بعدين الـ target
code generation فاحنا في الـ chapter 6 الحكي
بيتمحور
في نطاق اللي هو الـ intermediate code generation ف
الـ topics في هذا الـ chapter هناخد منها لغاية ستة
ستة الستة topics الأولاني اليوم إن شاء الله إذا
بيكفي الوقت بإننا بنغطي الـ section الأول والتاني
وبعد ذلك بنكمل في كيف بيتم .. بنتعرف على كيف
بينعمل intermediate code لـ type declarations و لـ
الـ simple expressions إنما في البداية بدنا نشوف الـ
syntax trees كيف هي شكل من أشكالهالـ Intermediate
Representation و بعدها كنا نتعرف على
Representation أخرى اللي هي الـ Free Address Code
الـ Free Address Code okay فبداية احنا عارفين إنه
الـ code generation زي ما أخبرتكم قبل إن أنا بتتم
على مستويات مستوى الـ intermediate code و مستوى الـ
target code الـ intermediate code generation بنى
على الـ output تبع الـ parserالـ parser و يليه الـ
static checker اللي هو بيفحص الـ semantic level
يعني بعد الـ syntax level بيجي دور اللي هو الـ code
generation المستوى الأول اللي هو الـ intermediate
code الـ intermediate code هذا بيدخل كـ cash كـ input
لـ target code generator الـ target code generator
بياخد الـ intermediate code و بطلع منه اللي هو الـ
machine dependent target codeالـ Intermediate code
هاد عبارة عن Universal Representation بعد هيك بيجي
الـ target code generator تبع machine X أو machine
Y أو machine Z بياخد الـ representation هادي الـ
intermediate و بطلع منها الـ target code تبع الـ
machine تبعته وهذا نهاية الـ front end
تصميم الـ compiler جاي على شكل phases الفيز
الأولاني هو الـ front-end والفيز التالي اللي هو الـ
back-end عشان يعطيني المهونة هذه إنه أنا عمل شغل
الأساسي لغاية مرحلة الـ intermediate code بعدها
كهذا الـ intermediate code
هذه الموقع من الإعراب في إطار المنظومة الكاملة
موقع الـ intermediate code generation
المراحلة الأخرى هي أن الـ Intermediate
Representation نفسها ممكن ننظرلها إلى إنها في حد
ذاتها مستوية في high level representation و high
level intermediate representation و في low level
intermediate representation low level أو high
level على أساس قربها من الـ target أو قربها من الـ
source إذا الـ representation لسه قريبة من الـ
source التارجت لا تشبه كثير التارجت لو كانت تشبه
كثير التارجت فهي low level فيها احنا الـ three
address code و الـ syntax trees احنا لسه ماشوفناش
الـ three address code بس شوفنا الـ syntax trees الـ
syntax trees are high level representation بعيدة
شوية بعيدة هذه الـ syntax tree اللي بتذكره هي عبارة
عن الـ tree الـ notes اللي فيها عبارة عن operations
و بتفرع منهم أو بتاخد الـ children more operations
أو operands مظبوط هذه الـ syntax tree غير عن الـ
parse tree الـ parts tree الـ notes تبعونها ايش
terminals و non-terminals non-terminals بالأساس و
بتفرع منهم الـ children عبارة عن
الثلاث أدرسات ممكن تعتبرها حسب على حسب الصياغة
الخاصة بها قد تكون الصياغة الخاصة بها شديدة الشبهة
أو شديدة القرب من الـ target وبالتالي بتكون low
level وقد تكون الصياغة الخاصة بها الـ free address
code لسه بدها تعديل أو بدها شغل وبالتالي بتبقى
شوية higher level الآن الـ free address code
طبعا كل ما كانت low level الـ representation فاكر
في الـ free address code كل ما كانت low level كل ما
كانت more suitable for الـ machine dependent code
يعني الـ code اللي بده يكون مخصص لـ machine محددة
عشانك بيقول machine dependent أما إذا هي high
level معناته لسه بدنا نعمل عليها عمليات عشان
نقربها من المن الـ target عشان نقدر نحوّل الـ target
الآن الـ three address code و الـ syntax trees و الـ
syntax trees هما two representations two
intermediate representations الآن مين أنسب باعتمد
على الـ .. الـ اش اللي أمامنا إذا كان احنا بنحكي عن
expressions
كلا هما نفس
المستوى يعني سواء كان أنا عندي يعني خلينا ناخد هذا
expression صح أنا أقول expression عادة نقصد
mathematical expression يعني معادلة فيها جامع وطرح
وكلام فلمثل هذا الـ expression هذه ايش syntax tree
هي مش tree بالظبط هي graph
بس سواء كان أنا بحكي عن syntax tree أو بحكي عن
three address code representation للـ expressions
للـ expressions يعني هذا الـ expression هي الـ ايش
خليني أعطيكوا بقى سريع بس لمحة عن كيف الـ
translation تبعته هيئته نفس الـ expression اللي
توشتناهذه تمثيله على شكل 3 address code وهذه
تمثيله على شكل syntax 3 مرة أخرى هذه ليست syntax 3
بالظبط هذه graph كما شويه بقى بحط الـ difference ما
بينهم بس هذه الـ representation وهذه الـ
representation للـ target code generator اللي بده
يعمل target code لإثنين efficient لإثنين على نفس
الدرجة من الكفاية هيجي ممكن يجي جيمسكت هذه اللي
بيحولهم إلى machine أو assembly وممكن يمشي يمسك هذا
ويحولها إلى assembly مافارقةش كتير بس هذا عدم وجود
الفارق هذا صحيح فقط في حالة الـ expressions لكن مش
دايما يعني مثلا لو أنا بأحكي عن .. أنا برجع لجوة
تاني لو أنا بأحكي عن ..
قلنا لإن الـ expressions كلا هما سيان لكن لو بحكي
عن loop statement زي مثلا الـ wild statement لو أنا
عندي while statement وفيها condition وفيها sub
statement هذا الـ while statement أنا لما بدي أترجم
أطلع منها three address code هطلع three address
code جزء يغطي الـ code الـ condition و جزء آخر يغطي
الـ statement و أحط label هنا و label هنا هذا
intermediate code representation ولو بدي أعمل هذه
syntax tree بقدر أعملها syntax tree مش الـ syntax
tree كلنا بتعتمد على operations و operands طب وين
الـ operations و الـ operands هنا مش بقدرش بقدر بقدر
أعتبر الـ while هي operation و الـ condition هو left
hand side و الـ statement هو الـ right hand side
ماشي الـ condition هذا قد يكون expression زي هيك X
أكبر من خمسة فبالتالي الـ operation أكبر من
relational operator وهي X وهي الخمسة الـ statement
قد تكون يش Y بساوي Y plus واحد مظبوط فبالتالي الـ
statement دي عبارة عن assignment الـ assignment ع
الشمالها Y وعلى يمينها إيش زائد ع شمالها Y وعلى
يمينها واحد هذا is a representation برضه
intermediate code representation وهذا مجرد مجرد
مجرد مجرد مجرد مجرد مجرد مجرد مجرد مجرد مجرد مجرد
مجرد مجرد
مجرد م
الـ looping بتتم كيف الـ flow control يعني هذا الـ
condition لما نينفحص وين أروح بالظاهر؟ أروح على
يساوي أو على الزائد؟ وين؟ مافي شيء هنا في الـ tree
يشير إلى إنه بعد الـ condition ما بين عمل لازم أبدأ
من هنا فإنما هنا فيه صح؟ هنا الـ labels اللي بتنحط
وظيفتها وظيفتها تقول لي وين أبدأ condition هذا كان
true وين أنتقل وإذا خلصت من هنا وين أروح ثاني مش
بدرجة أفحص الـ condition صح فهذا الـ representation
تحتوي على الـ components و الـ flow بينما هذا تحتوي
على الـ components بدون إيش الـ flow يبقى for
looping statements a syntax tree represents ال
components of a statement لكن لا يمكن تمثيل الـ
Flow of control المظبوط بينما الـ three address
code يحتوي على labels التي تمكن من إيش من تساعد من
اللي هو من بنية من التعرف على أو بتحديد ال flow of
control طبعا هذا الكلام كله قدر عن مقدمة بس عشان
نحن نميز أن في عندنا أكثر من على مستوى الانترنت
سوف نجد اثنين منهم syntax tree و three address code وعشان
نتميز أن ليس كلهم دائما متساويين أو مناسبين
للوظيفة التي سوف تقوم بها ال target code generator
لهذه الأسباب نحن بدنا ندرس الآن ال three
address code لأن ال three address code is more
efficient أو effective representation التي تقدر
يستند عليها ال target code generator في إنشاء ال
target code okay الآن قبل ال three address code بس
بدنا نوقف عند النقطة هذه وهي التمييز بين ال syntax
tree وما بين هذا الكائن الجديد الذي اسمه إيش
directed acyclic graph
الجزء هذا يتعرف على الفرق ما بين ال graph وما
بين ال syntax tree ال syntax tree من اسمها فهي
tree بينما ال graph لأنها tree ففي بنيتها بيكون
فيه nodes وال nodes هذه أو leaf nodesالـ leaf
node الواحدة ما لها أكثر من one parent بينما في
الشكل الذي لدي هنا في عندي two nodes التي لها more
than one parent الـ A هذه لها parent واحد و parent
آخر ال node هذه لها parent واحد و parent
آخر هو التالي هذا graph وهذا هو الفرق
الأساسي ما بين ال tree وال graphالـ tree حالة
خاصة من ال graph الـ tree هي حالة خاصة هي graph
ولكن ما في شيء لل node الواحدة إلا parent واحد
طبعا ال parent له أكثر من children ليس مشكلة بس
ال child الواحد أو ال node الواحد يعملها children
الآن لماذا نحن ممكن نحتاج graph أولا شيء هو اسمه
directed واسمه acyclic أولا شيء أيه ال directed ال
directed بيقول عنه أن ال edges هذه معروف اتجاهها
ولا اتجاه واحد يعني ما في انتقال من النجمة إلى
الزائد صح بس من هذا الاتجاه هذا a directed
basically بمعنى أنه ما في شيء cycle no cycles ال
cycle متى بتيجي لو أن أنا في يدي اتجه في هذا
الاتجاه ثم اتجه في هذا الاتجاه ثم اتجه في هذا
الاتجاه ورجعت على الزائد والآن بقدر أكمل هذه
cycle تمام هي نحن acyclic يعني no cycle يعني وهذا
وهذا هو الوضع الذي عندي الوضع الذي عندي صح في
انتقال في هذا الاتجاه وانتقال في هذا الاتجاه بس ما في
انتقال في هذا الاتجاه لأن ال link جاي في هيك فما في
cycle صح فهو acyclic directed acyclic graph
اختصارا DAG أو داغ ناشي فالآن لل expressionsللـ
expressions أنا ممكن أعمل ال expression شيء زي كده
أعمله representation على شكل ال tree أو على شكل ال
DAG ال tree هتبقى نفس ال DAG اللهم اللهم اللهم
اللهم اللهم اللهم اللهم اللهم اللهم اللهم اللهم
اللهم اللهم
اللهم اللهم اللهم اللهم اللهم اللهم اللهم اللهم
اللهم اللهم اللهم كمان واحد زي هوية هنا لو
راجعت ال expression صح هنا عندي النجمة هذه تمام
بعدين من يقوم عن مين الزائد هذا في عندي في ناحية
ال a وفي ناحية الضرب والضرب على شماله ال a
للثاني وعلى يمينه ال b نصية التي يعني ال DAG أفضل
من ال tree لأنها وفّرت عليّ الـ duplication هذا
هذه مكررة لما
أكررها كذلك الحالة ال a هذه مكررة لما أكررها لا
يجب أن أكررها لا يوجد اختلاف هذا ال b هو نفسه هذا
المتغير هو نفسه وال c هو نفسه والفرق ما بينهم هو
نفسه فأنا ال DAG عبارة عن
concise representation ميزته على ال tree أنه
تمثيل
مختصر لنفس المعلومة أو نفس المواضيع في ال DAG
node N in DAG has more than one parent إذا ال N
هذه تمثل a common sub expression يعني ال B
ناقص ال C ال B-C هذا sub expression متكرر كمان
يعني مشترك يعني متكرر في مكان وال A كده كحالة is
a sub expression فهذا ال sub expression وهذا ال
sub expression عمل
له more than one parent واشار إلى
هذا ال .. هنا ال D وهذا بتشير هنا صح؟ صح؟ هذه أخذت
ال two parents وهذه أخذت ال two parents علشان أن
هذول متكررين ف .. ف in a syntax tree ال tree for
the common sub expression would be replicated
مكررة في ال tree الآن على هذا الأساس ال DAG أعطاني
representation more conciseهذا يعني ميزة ال
DAG على ال tree أولا بيختصر عليها في ال memory وفي
الذاكرة ثانيا بيساعد ال code generator ال target
code generator في عملية ال optimization لماذا؟ لأنه
أنا لو عملتها tree وفي عندي ال common sub
expression المكرر هنا وهنا ال compiler ال target
code generator لما يشوف ال sub expression المكرر
هذا مرة واحدة ولما يعرف أنه موجود في أماكن أخرى،
تمام؟ فح .. لما يعرف أنه موجود في مكان آخر، سيقول
okay طب لماذا أنا أترجمه مرتين، سأترجمه مرة واحدة وأعمل
reference، أنا في ال DAG وفّرت عليه هذه القضية
ومعطيه يا مرة واحدة فقط ومشار إليه من two parents
وبالتالي ال code generator ال target code
generator لما يجيء في مسألة ال optimization في
مسألة تقليل حجم ال target instructions بيقدر يسوي
هذا الكلام المعلومة جاهزة له وبيعرف على طول أنه مش
محتاج يكرر
فائدة ال DAG على ال tree في الناحيتين هذول اللي
هو اختصار مساحة ومساعدة ال code generation في ال
optimization فأنه يطلع efficient code okay الآن
نحن ال tree ال syntax tree شفنا كيف بتنعمل
باستخدام syntax derivative definition عبارة عن
rules مع ال productionشفنا كيف مثال زي هذا لـ
expression بسيط نفس ال definition يصلح لإنتاج إيش
ولبناء DAG شغل صغيرة بس بتنعمل وهي أنه إيش لما ال
function هذه التي هي leaf وال function الثاني
التي هي node يجوا يعملوا nodeينتبهوا إلى أنه إذا
ال node هذه موجودة مسبقا ما يروحش يعملها مرة ثانية
okay صح فهو الآن تخيل ال leaf هذه تبدأ تعمل leaf
node ومعها identifier ال
B مثلا لازم تبحث في ال data structure التي مخزنة
فيها ال nodes ال nodes هذه نحن .. نحن كنا
نرسمها بشكل nodes مختلفة صح؟ وشاملة مع بعض ال
pointers تمام؟ هذه ال nodes عمليا ممكن تبقى مفروجة
وممكن تبقى محطوطة مع بعض في array يعني كل واحد من
هذول عبارة عن record في array هذه ال node الأولى
تكون مثلا الزائد وكذا وبتشير إلى من؟ إلى node
أخرى في نفس ال array إلى item آخر في نفس ال array
يعني هذول ال nodes عبارة عن records في ال array ف
ال leaf أو ال node التي تعمل ال interior nodes
لازم تتدور في ال array في الأول هل يا ترى أنا جاي
ببدأ أعمل identifier ببدأ أعمل node لل P هل فيه
already موجود؟ إذا موجودة بأخذ إيش؟ ال reference
تكون ما أعملهاش جديد كذلك لو بدأت تعمل node ل
operation interior node ل operation ناقص بال
pointer الأولاني وال pointer الثاني هل هذا نسميه
signature هل هذا ال signature already موجودة في ال
.. إذا موجودة ما أعملهاش بأخذ reference هي بس
التغيير الوحيد الذي بدنا نعمله في ال node وفي ال
leaf علشان ما ينعملش duplication ويصبح
الآن هذا ال grammar أولا نضيف عليه rule أخرى لماذا؟ ليش
لضرب لأن
فيه فقط الجمع والطرح بدنا لضرب عشان نستخدمها في
معالجة expression هذا فهنا في ضرب، مصمم؟ تعني أن
نحن ال expression هذا ما بدنا نخش نعمله parsingهو
ل tree هذه أو ال DAG هذا كيف يتبنى أنه أثناء ال
parsing لل expression تتنفذ من ال rules وال rules
هذه بعض منها سيجيء ينشئ ال nodes فهو الآن مختصر علي
هنا ومقام تسلسل العمليات التي أنتجت تسلسل ال
القواعد اللي نفذت وأنتجت الجراف إيه؟ الجراف اللي هو
هذا اللي وراه اللي هو هذا. فلو أنا بس بس بس بس بس بس
بس بس بس بس بس بس بس بس بس بس بس بس بس بس بس بس
بس بس بس بس بس بس
بس ب
لإيه؟ خلّيني أعملها مربع صغير ومشارق
له بيه P1 هي هتروح على الـ data structure على الـ
array تلاقيها لسه فاضية في الشيء، هتروح تعمل وتاخد
من الـ index تبع هذا الـ record اللي عملته وترجع
ليه؟ أنا هتزنه في P1، فـ P1 يشير إلى من؟ الـ record
اللي عمل في الـ array للمتغير A، بعد ذلك ستستخدم مرة
أخرى في الـ rule لكي تعمل لمن؟ لـ A برضه صح؟ لما
تشوف ماذا تعمله ستذهب و تبحث وستجد P1 والـ
pointer هو P1 فلن تعمل واحد جديد، ستأخذ P1 وتخزنه
في pointer جديد بس P1 هو نفسه يساوي P2 هو نفسه يساوي
P1 فهو نفس الـ record اللي هو هو الآن، بعد ذلك هدفك
تعمل الـ P طبعًا الـ P مش موجود هتروح في الأول تدور
في الرقم في الـ hash هتلاقيه هتعمل واحد جديد وتشير
إليه بـ H بـ PH3
صح؟ بعدين هتروح تعمل للـ C بنفس الشيء، ليس موجود الـ
C وهتشيل الـ A لـ B عشان P4 P4
الآن بيجي دور node تبع الـ minus الـ minus تبع من؟
هذا تبع الـ B مع الـ C صح؟ هذه فهتروح تعمل node
أول شيء معناه الـ pointer P3 ومعنا الـ pointer P4
أو أصلًا مافيش nodes للـ minus ولا لزاد ولا إشي nodes
يعني interior nodes فهتروح تعمل واحد جديدة صح؟
هتعمل واحد جديدة وتشاور عليها بـ P5 و
طبعًا هتعملها مربوطة الآن على على
مين؟ على P3 و P4 لأن بعد هيك ستعمل نقطة أخرى لنجمة
تانية نجمة اللي هي اللي تضرب هذه مع هذا، محطة هنا
ستعمل واحدة تشير إلى P1 هاي P1 و P5 هاي P5 وهذه
نفسها مشارقة إلى P6
بعد ذلك ستقوم بالزائد
أنا هذه الكلام أنا جعت بس بأقسم فيه Russell أحنا
واثقين أن هذا الـ order الصحيح اللي هيتم لما تتنفس
عملية الـ parsing أثناء الـ parsing كل واحد من هدولة
جاية من الـ rule المقابلة للـ production اللي
بتستخدم، و الله بينتهي الموضوع على في الآخر يعني بس
أنا اللي بدأ أقوله أنه هاي هنا لما نيجي يعمل الآن
لما نشوف الـ P مرة ثانية ويجي يعمل لها leave
هلاقيها موجودة already فهياخد الـ pointer تبعها
okay الآن بـ share بـ P هيعمل pointer جديد صحيح بس
مش node جديد okay وكده عادة حالي لما نشوف الـ C في
المرة الثانية هلاقيها موجودة فهشاور إليها بـ P 9
اللي هو يساوي P 4 صح؟ وبعد كده لما يجي يعمل night
أسئل بم هلاقيها موجودة بخمسة فمش هيعمل واحد جديد
إنما هي share إليها بالـ point of P عشرة الآن
الباقي كله فيها الـ D لازم تنعمل الـ D نعملها node بـ
share إليها بإيش؟ P11 بعدين كبدي أعمل الزائد الضرب
والزائد الضرب اللي بتاخد الـ D مع الناقص صح؟ الزائد
الكبيرة اللي بتاخد الزائد هادي مع الضغط
خلاص واضح إنه في الآخر مش اللي وصلنا له في الآخر
إنه بنفس الكيفية اللي هي كيفية الـ SDD اللي هي إن
أنا أحط rules نعم rules مع الـ productions بقدر
أعمل زي ما كنت بعمل trees بقدر أعمل graph طالما إن
الـ rules مكتوبة صح فتبنيلي اللي هو الـ graph كل ما
بيستجد هو إن أخلي الـ functions ليه في node إنهم
يعملوا check قبل ما يبنوا أو ينشروا الـ nodes جديدة
okay هذا الكلام احنا مرينا عليه صرنا خلاص بس بدي
أقول إنه عندما يجي يستدعي ليه في step number two
يعني في المرة الثانية هو مش هيعمل node جديد إن أنا
بس هياخد عمل pointer جديد وشير إلى نفس الـ pointer
الأولاني وكذلك في المخطوطين
هدولة الآن هذه الرصدة عبارة عن أمر إيه؟ ممكن
تتخيلها اللي مخزن فيها الـ notes سواء الـ leaf notes
وأيضًا الـ operation notes أو الـ interior notes
هدولة التنتين عبارة عن leaf notes بس لناس مش لنفس
البصغير هذا الـ graph يمثل الـ expression هذا الـ
statement مش expression I ساوي I زائد عشرة في هذه
العملية الأساسية الزائد تفرع منها الـ I ع شمالها كـ
left hand side الـ يساوي أنا قلت زائد ع شمالها
عيمينها اللي هو الزائد اللي هي الـ I نفسها اللي
بتاخد الـ I نفسه و 10 أنا جمت بالشكل هذا وهو
راسمها بالشكل هذا حتى الـ 12 الآن
هذا عبارة عن array تمثل الـ notes تبعد هذا الـ graph
أو بتخزن الـ notes تبعد هذا الـ graph هي دول الـ two
notes واحدة للـ identifier I طبعًا هنا القيمة
المخزنة هنا هي مش الـ I نفسه إنما الـ pointer يشير
إلى مكانه في الـ .. في الـ .. في الـ .. في الـ .. في
الـ .. في الـ .. في الـ .. في الـ .. في الـ .. في الـ
في الـ .. في الـ .. في الـ .. في الـ .. في الـ .. في
.. في الـ .. في الـ .. في الـ .. في الـ .. في الـ .. في
الـ .. في الـ .. في الـ .. في الـ .. في الـ .. في الـ
في الـ .. في الـ .. في الـ .. في الـ .. في الـ .. في
.. في الـ .. في الـ .. في الـ .. في الـ .. في الـ .. في
الـ .. في الـ .. في الـ .. في الـ .. في الـ .. في الـ ..
.. في الـ .. في الـ .. في الـ ..
في
ال
أو two arrays لأن nodes واحد يساوي واحد الزائد لأن
الزائد بتاخد
الـ I وبتاخد ناتج الجمع لأ هذا زائد بتاخد الـ I و
بتاخد العشرة فإحنا الآن هنا ما حطيناش الـ I نفسه ولا
حطينا العشرة نفسه، حطينا number يمثله، دول القيمتين قيمة
الـ I وقيمة العشرة هنا، هذا اسمه value number
method يعني أنا ما بحطش في الـ .. في الـ .. في الـ
note في الـ note ما بحط قيم سواء قيم زي عشرة
constants يعني ولا variables A, B, C لأ بحط
number you share أو index you share إليها واضحة
قضية مافيش فيها أي شيء تمام؟ وهنا نفس الشيء لأن
يساوي تاخد على شمالها الـ I التي هي record number
one وتلاتة التي هي نتيجة لها بالظبط هذه هي الـ
method value number for constructing DAGs أنا ببني
الـ DAG على شكل array أنا بخزن الـ DAG في array وهذا
الـ algorithm بقى شغل بسيط إنه يبحث أولًا زي ما قلنا
لازم أعمل search search for search the array for a
node M
node جديد يعني with label up و left child L و right
child R يعني أنا معايا operation و left child و
right child وبدي أضيفهم هذه هي كانت التلات عناصر
هدولة نسميهم signature التلات عناصر هدولة بدي أشوف
إذا كان موجود في أي إشي في الـ array ولا لأ فـ search
if if there is such a note return الـ value number
تبعها الـ value number له الـ index يعني تبعها صح؟
إذا لأ خلق نوع جديد نوع نوع نوع نوع نوع نوع نوع
نوع نوع نوع نوع نوع نوع نوع نوع
نوع
سواء أنا جديدة ولا مش جديدة، بدي أعمل search في
الأول، صحيح؟ لأ، حتى لأ، جديدة ولا مش جديدة، أنا
معايا note، شوفت .. شوفت .. جريت في الـ input إنه
كذا كذا، بدأت .. قررت إن أعمل note لهذا الكلام،
هذا الـ note بدأ في أول شيء أبحث إن كانت موجودة ولا
لا مش موجودة، إذا موجودة ولا مش موجودة، عملية
البحث هذه، خاصة إنها بحث فيقرري، فهي مضنية و .. و
.. و .. و .. لأنها sequence، يعني ممكن ألاقيه في
الآخر فبدل هذا الأمر بروح أعمل الـ more efficient
way إنه نعمل hash صح نعمل array of values وبعدها
الـ hash function تاخد الـ operator والـ left والـ
right وبتحسب من هدولة تلت pieces of information
تحسب hash value فبتروح على الـ hash value إذا تحسبه
كمان مرة نعم، أول إشي عند الإدخال إحنا
وراح تقرر على هذا الموضوع تمام، الآن هذا الموضوع
بتروح تبحث هل هو موجود سابق هل اللي هي جاي بدها
تتخزن، إذا راح هذا الموضوع هذا الموضوع هو عبارة عن
بداية لـ linked list بدها تبحث الآن في linked list
إذا موجود هذا اللي هي جاي تتخزنه في linked list
خلاص بناخد pointer عليه إذا مش موجود بتروح بتضيفه
لأنه ال link list هذه هي كل ال nodes اللي متساوين
في ال hash value صح، ال hash function مابتضنش
unique value بمعنى أنه ممكن يبقى فيه two nodes على
الرغم من اختلاف ال operand يعني يبقى واحد plus
واحد minus لكن ال hash value تبعهم نفس الشيء
ال hash value تبعهم نفس الشيء فبيجوا على ال link list
نفس ال link list اللي رأسها هو ال hash value يعني
ممكن أنا إيه بفيها آندي plus ويبقى
عندي pointer واحد و pointer سبعين وكمان واحد plus
pointer أحداش و pointer سبعين دول مختلفين على بعض
لكن ال hash تبع هذه و ال hash تبع هذه يطلع متساوية
مش مشكلة بيتخزنوا على نفس ال hash value بس two
separate
items مظبوط لأن أنا لما بدي ابحث أنا في الأول
بخزّن لأن بدي ابحث حسبت ال hash value طلع ل 20 بقف
على 20 وببدأ أدور هل هذه اللي أنا ببحث عنها
موجودة أو مش موجودة أيوة بس اختصرت على الحالة
عملية البحث إن أول شيء عملت one jump بعدين عملتش
عدة traversals أهو من إن أعمل traversal على القرية
كلها يبقى عندي مئات مثلًا ال records طبعًا احنا
الأمثلة تبعتنا كلها أمثلة صغيرة نحكي عنها دايمًا
صغيرة لكن عمليًا في ال compiler الحقيقي بدي تكون
يعنيش مئات ربما فال search بيبقى بطيء وهذا كله بدي
يتم أثناء ال compilation تخيّل تكتب برنامج يبقى مائة
سطر ولا متين سطر وال compiler يقعد يحسب الكلام
هذا ويقعد يبحث .. المهم فهذا ال hash is a more
efficient approach than أن نستخدم ال array مباشرة
هذا الأمر يوضح الكلام اللي قلته وقلت أنا الآن كل
حكي ما ذكر عن ال three ال syntax trees و ال graphs
نحكي الآن عن ال three address code بناء ال three
address code لقّوا قدام شوية بس الآن بنا ناخد شوية
ملاحظات على أو نتعرف على ال three address code
بشكل مفسر أكثر ال three address code أول شيء من وين
الاسم جاي جاي من أنه الطرق الاستيعابية لل
instruction مش أكثر من تلاتة addresses وين ال
addresses هي هي هي هي هي هي هي هي هي هي هي هي هي
هي هي هي هي هي هي هي هي هي هي هي هي هي هي هي
هي هي هي هي هي هي هي هي هي هي هي هي هي هي
الإستركشن الواحدة فيها تلات أدرسات ممكن يبقى أقل
بس أكثر ما بيبقى مفيش مجال ممكن يبقى أدرس واحد أو
اتنين إنما أكثر من تلات الأدرسات الأخرى الآن ال
two instructions اللي أمامنا هنا هم عبارة عن ترجمة
لهذا ال expression أنا عندي x زائد y مضروبة في h
في z ترجمة هذا ال expression إلى two instructions
الinstruction الأولى وال section الثانية بتروح تنافس
الجمع صح؟ هذا الآن عبارة عن temporary variable
وهذا temporary variable هأدقّلها عبارة عن إيش؟
identifier صح؟ ال temporary variables و ال
identifiers هم addresses هم يمثلوا addresses يعني
هذا في الآخر ال identifier هيكون قيمة قيمة ال Y
موجودة في ال memory و ال Y هي تشير إلى هذا الموضوع
صح؟ وكذلك حالة T أحنا الآن نفكّر
على من أين ستبقى التسمية الآن الـ DAG هذا الـ graph
هذا هذا الـ three address code المقابل له يعني أنا
بقدر أعمل representation لهذا الـ graph بهذا
المجموع من ال instructions
ال course هذا تبع ال B ناقص ال C بينحسب ال
construction بتحسبه في T1 بتخزّن في T1 بعد ذلك
بينحسب حاصل الضرب بتخزن في T2 أمامك؟ لأن احنا أخذنا
ال T الواحدة اللي هو ناتج الطرح وضربنا في ال A بعد
ذلك T3 بتاخد جمع الناتج هذا مع ال A نفسه مع T2
بتخزن في T3 فأنا الآن عمليًا أنا ممكن أفكر إن لو آندي
أنا graph بشكل systematic أستطيع أني أستنبط منه أو
أستخرج منه أو أبني منه اللي هو إيش سلسلة ال three
address instructions صح؟ يعني ممكن أعمل algorithm
صغيرة اللي لو أعطيتها DAG تعطيني three address code
وأنا مش محتاج عمليًا أنا ممكن أبني ال three address
code مباشرة من ال high level language أو من ال
definition بس
الشغل اللي بدنا نحكيه الآن اللي هي ال addresses
اللي احنا قلناه هذا temporary address هذا
identifier هذه تلاتة ألوان من الأدرسات التي يمكن أن
تظهر في الـ Free Address Instructions فيها الـ
Name الـ Name هي الـ Identifiers اللي هي الأسامي
المتغيرات اللي حطها المبرمج أصلاً في البرنامج ممكن
يظهروا في الـ Free Address Instructions زي ما هم
احنا هنا نقول A و B و C لكن لو ال programmer كاتب
أي حاجة كاتب مثلًا rate كاتب position كاتب ششوة
ممكن يظهروا معانا في الـ Free Address Code مش مشكلة
يعني هو بس مجرد تسمية ل .. ل الاسم ممكن تبقى
constants بدل ما address يُنْحَط بدل ما identifier
تحط قيمة عشرة تحط address لو location في ال memory
يعني constants صح؟ وممكن تبقى temporary name ال
compiler generated temporary ال identifier عمله ال
compiler هذا بالنسبة للإدارات التي يمكن تظهر في الـ
Free Address Code Instructions الآن، ما هي بعد ذلك
الـ Instructions أو الـ Operations التي يمكن تظهر
فيها؟ فيها ممكن تظهر Assignment Instructions
Assignment
Instructions فيه منها نوعين فيه Assignment
Operator وفيه Assignment Binary Operator وفيه
Assignment Binary Operator وفيه Assignment من غير
Operator ماذا يُسمّى الـ Unary Operator الأول؟ اللي
هو ال operator اللي بياخد operand واحد زي ال
logical negation أو التحويل إشارة positive و
negative صح؟ معظم ال operators بتاخد two operands
okay
فهي عندي تلت حالات هذه الحالة الأخرى اسمها copy
لأنه مافيش operator وبالتالي اللي بيستم هو نسخ
قيمة ال Y إلى ال X صح؟ في عندي بعد هيكة بقى كمان
jump instructions في ال jump في منها conditional و
في منها unconditional ال unconditional اللي أنا
عادةً وأقوله go to L بدون أي فحص لأي condition ممكن
تكون لديك T واحد ساوي X زائد Y وبعد كده على طول
تروح من تلك الكتب وتقول go to L L هنا عبارة عن
label أو عبارة عن رقم رقم ال instruction اللي
بتكتب في السؤال هذه إيش اسمه يقولنا unconditional
ال conditional ممكن تيجي ب if أو ب if false و
نعطيها X و X هذا يكون true أو false بيناري أو
Boolean Variable وهنا نبحث إذا هو true وهنا نبحث
إذا هو false وممكن تيجي F و Relational Operator
بمعنى X وقيمة أو Variable يعني تبحث ليه علاقة هذا
بهذا إذا هي أكبر أو أقل أو يساوي فهذه حالات ال
conditional jumps في غير هيكة high conditional jump
اللي هي relation من الoperator في ال procedure
call إن أنا واحد من ال instructions أقول call و P
P هذه برعن pointer ل instruction سابقة أو لاحقة
بدي أنا أروح أنتقل إليها طب إيش الفرق هذا ما بينه
وبين ال jump الفرق إنه هذه ال P تشير إلى بداية
function والـ function هذه احتمال بدها parameters
بدها تشتغل عليهم فبكون أنا قبل ما أستدعيها قبل ما
أنتقل إليها أعطيت
عدة instructions تبدأ بكلمة param param وأعطيتها
المتغيرات فالآن الصيبة هذه إيش معناها معناها
اقفز إلى هذا ال location وخد كذا متغير كذا اقرأ كذا
parameter instruction بقول مثلًا هنا تلاتة اقرأ آخر
تلاتة parameter instructions فدول أخدهم معاك وأنت
رايح تنتقل على هذا ال location لو هذه ال function
بتاخد واحد فبعمل parameter واحد وبقوله هنا one لو
بتاخد اتنين بعمل two parameter instructions و
بقوله اتنين طبعًا بعطيله إيش المتغيرات اللي هو
هيستخدمهم الـ function هذا اسمه procedure code
instructions three address code instructions قمار
عن procedure code في هنا برضه حاجة اسمها ال
indexed copy تذكروا ال copy لما جابوا ال X بساوي Y
بس هنا indexed copy بمعنى إنه ممكن أنا أحكي عن X
of I اللي هو قمار عنصر في ال array بتعطيله قيمة أو
متغير بتعطيله قيمة من عنصر في ال array صح؟
هذا اسمه index copy هو copy ما فيش أي operation نسخ
من variable ل variable الحالة الأخيرة اللي هي ال
addresses والـ pointers أنه أنا بعمل copy بس ايش X
هنا بساوي ال address تبعه X هنا بساوي ال pointer
طبعًا X بساوي ال pointer طبعًا X بساوي ال pointer
عندنا free address instruction forms في ال
assignment ال assignment أنا عارف أنها binary و
unary وهي مثلًا والـ address and pointer معتبرها
assignment صح؟ اللي كان والـ address كله اللي
ما تكفينه بعدين ال copy ال copy هي assignment في
الآخر صح؟ في منها normal وفيها indexed هدول
الأمثلة والـ jump في منها unconditional وفيها
conditionalالـ unconditional بس go to على طول والـ
conditional فيه if وفيه if false وفيه if ب
relation ال operator والـ procedure call فيه منها
call على طول وفيه منها call وخذ ال .. هذا ما
حكيناه .. خذ ال return تبعه خزنه في variable و
التنين هذولة بيسبقهم إذا ال P بتاخد parameters إذا
.. يعني مش دائمًا ال function بتاخد parameters صح؟
إذا بتاخد parameters لازم
بعدد ال parameters اللي بيتخلقه احنا بنوقف عند هنا
والمحاضرة الجاية بنكمل في اللي هو
لسه في ستة اتنين في عندنا أنماط من ال three
address instructions ال quadruples والـ triples والـ
ال indirect triples بنكملهم المحاضرة الجاية وبن ..
بعد كده بننتقل على اللي هي كيف احنا ممكن نعمل three
address instructions يعطيك ونعرف