ماشي بسم الله الرحمن الرحيم اليوم إن شاء الله يا
بنات بنكمل في lexical analysis كان هذا الـ chapter
chapter التالتة بتناول المواضيع التالية اللي هي
أول شيء دور الـ lexical analyzer بعدين الـ input
buffering ودوره في عملية قراءة الـ characters بعد
هي كده لغة الموضوع اللي هو how do we specify الـ
tokens وبعد ذلك يأتي الـ recognition of tokens ثم
نظهر على الـ finite automata وما يتحول من الـ
regular expressions إلى الـ automata نحن وصلنا
للماضي وضعنا هذا الكلام كله والـ specification
وضعنا recognition وضعنا على أبواب recognition of
tokens فالآن نظهر على الأمر هذا وبعدين هنتقل على
طول على الـ finite automata يجب أن نبقى معنا واجد
ونخلق lexical analyzer لقدام لأن بصراحة أنا احتمال
أستبدله بأداء آخر هو lexical analyzer generator
هذا اللي هو lex كوسيلة لبناء lexical analyzer
احتمال نستخدمه واحتمال نستخدم أداء آخر عشان كان
مدخليه للآخر فبنكمل في الكلام النظري وبعدين نخلص
كل المواضيع تباشرتها تلاتة داخل محاضرة عملية
استخدام الأداء اللي بنستخدمها في بناء lexical
analyzer الآن بدي أنتقل إلى تلاتة أربعة الـ
recognition of tokens قبل
الـ recognition of tokens لازم نتذكر شوية اللي هو
الـ definition of tokens كيف احنا ندفن الـ tokens
كان اتفقنا على أن الـ regular expressions هي أداةنا
أو وسيلتنا لتعريف الـ tokens لتعريف الـ tokens
وقلنا أن الـ regular definition هو عبارة عن
regular expression شوفنا من الأمثل على regular
expressions اللي هي زي تعريف الـ letter تذكروا وين
كان تعريف الـ letter وراء تعريف
الـ
قدام .. قدام .. قدام .. قدام .. قدام .. قدام ..
قدام
.. قدام .. قدام .. قدام .. قدام .. قدام .. قدام ..
قدام .. قدام .. قدام .. قدام .. قدام .. قدام ..
قدام
.. مثال example هذا to define اللي هو الـ numbers الـ
numbers بيه أشكالها المختلفة سواء كانت integers
فقط أو integer معها كسر أو إذا كان برضه كمان
معها الـ exponent part الـ exponent part صح؟ فهذه
الـ definition بيغطي الأشكال المختلفة أو الأنماط
المختلفة اللي هي الـ numbers okay الآن وشوفنا كمان
المثال هذا تذكروا هذا المثال أنه احنا قلنا أنا الـ
digit الـ digit هنا تعرّفناها أو في السابق كانت
معرفة على أساس أنها الأشكال المختلفة من الـ zero
إلى التاسعة وبينهم bar قلنا احنا ممكن نعمل حاجة
يسمها اللي هو الـ symbol الـ character class أو الـ
symbol class character class أن أنا بدل ما أسردهم
واحد واحد وأحط bar ما بينهم بحط range الـ range
هذا معروف للـ compiler لأن الـ a للـ z تشمل a,b,c,d
,e كل الـ alphabet وبعدين ألحقت بها أيضا الـ a
small للـ z small وبعدين ألحقت بهم الـ underscore
كذلك بالنسبة للـ digits من z لـ 9 هذا الـ range أنا
ما ذكرتش كل عنصر من عناصر هذا الـ range إنما حطيت
الـ dash دلالة على الـ range كله فهذا المقصود بيه
character classes الـ one or more one or more
عارفينها بالـ plus و zero or more عارفينها بالـ
star الآن في ظهر معاناة قدام برضه علامة الاستفهام
هذه علامة الاستفهام دلالاتها أنه zero or one
بالضبط يا موجود يا ما مش موجود تمام؟ zero or
one يعني هنا في تعريف الـ number في الـ definition
تبع الـ number بعد الـ integer part يا إما تيجي يا إما ما تيجيش
شيء بمعنى لا بتيجي النقطة ولا بيجي الـ digits هذه
دلالة الـ course framework ونفس الشيء ينطبق على الـ
course الآخر هذا الـ course framework اللي معه أنه
يا إما بيجي الـ E وبعدها الـ plus والـ minus وبعدها
الـ digits يا إما ما بيجيش ولا حاجة منها هذا كذلك
الحالة الـ course الصغير هذا يا إما بيجي الـ plus أو
الـ minus واحد منهم يا إما ما بيجيش ولا واحد لو ما جاش
لا plus ولا minus بينفهم على أنه plus في حالة الـ
numbers تمام فهذا الـ .. الـ .. الـ .. الـ notation
هذه اللي بنستخدمها في defining الـ tokens define الـ
tokens فخلصنا من قضية الـ defining الآن how does الـ
.. الـ .. الـ analyzer lexical analyzer بناء على هذه
الـ definitions بيعمل عملية الـ recognition بيتعرف
على الـ tokens اللي نعملها definition بتعرف عليها
من النص اللي داخل عليه اللي هو stream of
characters وهذا الآن موضوع section تلاتة أربعة
recognition of tokens recognition of tokens عشان
نفهمه بنا أول شيء نرجع خطوة للوراء اللي هي أنه احنا
بالأصل في عندي أنا grammar الـ grammar هذه عبارة عن
definitions بس syntax مش لـ tokens لـ syntax اللي
هي المنية تبع الجمل الـ productions تبع الـ
definitions بتحتوي على tokens وبتحتوي على
terminals و non terminals احنا الآن في الـ lexical
analysis معنين بمين؟ معنين بالـ terminals صح؟ اللي
هي tokens خلينا نسميها الـ F والـ then والـ else
العاملين العاملين العاملين العاملين العاملين
العامل
سواء في .. على الـ level اللي هنا ولا جوا الـ
functions احنا الآن معنين بالـ recognition of الـ
terminals of الـ terminals اللي زي الـ terminals
اللي ظاهرة هنا ايش أصنافها؟ فينا الـ F والـ else والـ
then هدول أنا أكتبهم هنا على أساس أنهم ايش
كلهم keywords في معهم keywords ظاهرة هنا؟ لأ في
عندنا roll up Either Unrelational or Relative فإنها
فئة لحالي ونمبر أية فئة أخرى ونمبر أية فئة أخرى
ونمبر أية فئة أخرى ونمبر أية فئة أخرى ونمبر أية
فئة أخرى ونمبر أية فئة أخرى ونمبر أية فئة أخرى
ونمبر أية فئة أخرى ونمبر أية فئة أخرى ونمبر أية
فئة أخرى ونمبر أية فئة أخرى ونمبر أية فئة أخرى
ونمبر أية فئة أخرى ونمبر أية فئة أخرى ونمبر أية
فئة أخرى ونمبر أية فئة أخرى ونمبر
أية فئة أخرى وشوفنا الـ Identifier شكل الـ
Definition تبقى والـ number شوفنا شكل الـ .. صح؟
هنا الـ .. الـ .. الـ .. الـ .. الـ .. الـ .. pattern
definitions هذه بتغطي الـ .. بتغطي كل الـ tokens
هدول يعني هاي الـ real up وهاي الـ identifier و
هاي الـ number تلاتة هدول
هدول مساعدين لأنه بيجي يستخدموا في الـ other
definitions ناخذهم من الـ identifier اللي احنا
بنعرفه هذا الـ definition تبع الـ identifier أنه
عبارة عن letter متواقة ب zero or more sequence
sequence طولها zero or more كـ characters الواحد
منهم إما letter أو digit صح هيك؟ zero or more
الوحدة
منهم letter أو digit الـ letter هيجي من المجموعة هذه
هي الـ definition والـ digit هيجي من المجموعة هذه
الـ number هيتوا نفسه نشوفها يا عزيزي الـ roll up
هيبقى هذا أو هذا أو هذا مش محتاج أنا pattern لأنهم
قوالب ثابتة أو أشكال ثابتة محدودة بالضبط بعد ذلك
ينطبق على الـ F والـ then والـ else F هي حرف الـ I وبعدها حرف الـ F هذه بالنسبة لنا هي الـ pattern اللي
بنعملها matching direct مش لإيه بدنا ن .. في
احتمالات أنه ينجح هيك أو هيك لأ direct pattern
matching فال F وال then تخيلي أن هنا في ايش
double quotes إشارة إلى أن احنا بنحكي عن ال
characters ال sequence of characters هنابقى الشيء
التاني ال white space لأن لما بدأت تكتب ال input
ممكن تشوف بينهم white space يعني about if وبعدين
وبعدين وبعدين وبعدين وبعدين وبعدين وبعدين وبعدين
وبعدين ويعني أنا هنا معرف ال letter على أنه واحد من
هدول هدول معروفين ال a معروفة ليه character ال
ask character تبع ال ask code تبع ال a طب هدول
برضه ال blank ال ask code تبع ال blank وال tab ال
ask code تبع ال tab فأنا هدول يفترض أن ال
compiler هيقارنهم على طول بإيش ب ask code single
ask code كل واحد منهم ب single ask code تبعها new
line برضه new line يعني line feed الها ask code
okay وايه عليهم ايه plus or more يعني one or more
فهي ال life space هتكون سلسلة من ال characters أي
واحد في هذه السلسلة هيكون إما blank أو tab أو new
line واضح؟ الآن احنا ال table هذا بيعطيلي اللي هو
ال tokens اللي لدينا وال axioms تبعتها واي
attribute ممكن تحتاج لما ال lexical analyzer يتعرف
على أحد هذه ال tokens يروح يبعت attribute معاه
يطلع ال token ويطلع معاه attribute إذا كان احنا
ال
white space ايه اللي يطلع لل token؟ مش هيطلع
token صح؟ نشوف white space مش هيطلع لها token لما
نشوف اللاقسيم هذا هيطلع ال token تبع ال F ايه ال
attribute؟ مفيش شيء كذلك الحالة then و else نفس
الشيء إذا كان هناك أي identifier فهيطلع ال token
لرمزه ID ويعطي pointer to وين ما كان فيه كذلك
الحالة ال number هنحط ال numbers في ال symbol
table في هذا المثال بدنا نحط ال numbers في ال
symbol table ال
relational operators كلها هنطلع .. هتبقى class أو
فئة واحدة هنطلع token اسمه roll up وال tribute
بتدلل على إيش النوع من ال relational operators طيب
إيش ضال الآن؟ ضال الآن نشوف ما عرفناش كيف فعلا هذا
الكلام بده يطبق عمليا على شكل procedure أو إجراء
أو algorithm اللي يتبعها ال lexical analyzer في
قراءة تكتشف النص ويأخذه ك input ويطلع مقابله اللي
هو ايه يطلع مقابله أي حد أحد هذه ال tokens الإجراء
هذا ال procedure هذه تبدأ بأول شيء أن نتعرف على
المفهوم ال transition diagram transition diagram
شيء من هاي شكله هذا ال transition diagram لل
relational operator token كافة ال relation
operators اللي تنزلش تحت rel up ايه شأن ال
transition diagram عبارة عن graph يحتوي على nodes
وال nodes ما بينها links أو بنسميها arcs ال nodes
هذه عبارة عن states كل state الها رقم لا اسم ولا
شيء الها رقم والانتقال من one state إلى أخرى يتم
بناء على أن نشاهد input معين أو character معين إذا
شاهدنا ال character في فلاني وكنا على ال state
الفلانية، فننتقل إلى ال state الفلانية نهاية
ال graph ال leaf nodes التي لا تتفرع منها أي هذا أي
نوت أخرى بيسميها accepting notes ال accepting
notes اللي هي عندها بيكتمل التعرف ال recognition
على أي واحد من الماط أو ال petals خلينا ننخص هذا
الكلام مرة أخرى بإيش بالتالي ال transition diagram
is has a collection of notes or circles صح called
states النوت الواحدة
Each state represents a condition that could occur
during the process of scanning the input حالة
أثناء عملية ال .. حالة ال analyzer أثناء ما هو ايش
بيعمل processing لل input آه ال input looking for
a لقسيم هو بيعمل processing بحث عن لقسيم شكله
يطابق إحدى ال patterns تبع أحد ال .. ال tokens
التوكن اللي قدرت اللي قدرت اللي قدرت اللي قدرت
اللي قدرت اللي قدرت اللي قدرت اللي قدرت اللي قدرت
we look for an edge out of state S labelled by A
يعني برجع أنا في S وبيجيني A تمام بعمل edge ل
input هذا اللي المتوقع أن يحصل أن يجيني وأنا في S
طيب وين بتروح ال edge هذه؟ بتروح على state أخرى
اللي بدي أنتقل عليها بعد هذا ال input
اختصارا بنقول أن certain states are set to be
accepting or final مين هم هدول ال accepting أو ال
final اللي خلاص بنتهي عندهم اللاكسيم اللي أنا ببحث
عنه مثلا وصلت إلى هذا ال state يبقى اكتمل التعرف
على البتن
هذا بحكي عنه في السياق اللي حكي عنه بالديو الآن
example اللي هو relational operator واشكاله
المختلفة ال state diagram تبعه هو اسمه state
transition diagram بس اختصارا بيقول transition
diagram بنبدأ من ال start H بتشار على state رقم
Zero وأنا في Zero لأن أنا عندي أشكال مختلفة من ال
H من ال relational operator في less than في less
than or equal في greater than في greater than or
equal في كل حالة في غير هيكة في لا يساوي اللي هو
less than or greater than أنا على ال state zero
ممكن يجيلي أي واحد من ال characters اللي في
البداية ممكن يجيلي هذا
وممكن يجيني هو نفسه طبعا يجيني greater than وممكن
يجيني equal وممكن يجيني هذا خلاص هنا الآن صح
آه الآن بعد لو أجاني ال less than خلاص أنا بدي
أعتبر الحل الآن في ال state جديدة وبدي أعطيها رقم
مختلف الآن هنا وأنا هنا وبعد ما يجيني ال
character هذا ممكن بعدين كما يجينيش ولا حاجة ممكن
يجيني يساوي ممكن يجيني greater than ففي تلات
احتمالات يساوي أو greater than أو ولا شيء other كل
واحد من هدول state لحد ذاتها بدأنا اكمل الرسم هذه
بدأنا نتقل لهنا لل slide أنه زي ما اتخذناه زي ما
قلت هو ال zero بعدين أول احتمال أنه less than لسة
من جيبني على state number one بعدين بيجيني ايش
بتوقع إما اليساروي أو greater than أو some other
إذا اجاني اليساروي إذا شفت اليساروي خلي بالك تفكري
برضه بإيه ال pointer اسمه لقسيم begin ذاكرينه؟ تبع
ال buffer وال pointer التاني ايش اسمه كان؟ اللي
هو forward مظبوط؟ أنا الآن اللاكسيون بدأ هنا ال
forward في الأول كان هنا بعد ذلك أنا بنظر إلى ال
character التاني وأصبح ال forward هنا مظبوط؟ الآن
أجدني يساوي ال forward لسه أعلى اللي يساوي مظبوط؟
لو جرى ما شوفتی اللي يساوي انتقلت إلى .. أصبحت أنا
في state two هذا الـ state خلاص بجرب ما أنا شوفته
يساوي أنا حسنت الأمر ما عنديش أي خيارات أخرى
ما عنديش أي يعني ضبابية خلاص هذا عبارة عن لكسيم ال
less than وال equal مع بعض لكسيم يشكل ينطبق على
ال pattern تبعت ال relational operator اللي اسمه
less than or equal LE تمام؟ خلاص فاحنا هنا we can
take an action اللي هو الـ lexical analyzer can
take an action بإنه to return هذا ال .. ايش؟ ال
token إلى مين؟ إلى ال syntax analyzer، مظبوط؟ هذه
double circle يعني accepting state accepting يعني
final state يعني خلاص اتعرفنا على .. على لسين وأصدرنا
token عنه
لو ما جاش يساوي وال character اللي بعد كان
greater than .. greater than not equal greater
than معناته برضه accepting state بس بعمل return ل
not equal غير هدول ال two characters يجيلي ايش ما
يجيلي white space يجيلي identifier يجيلي أي حرف من
الأبجدية يجيلي أي شيء ال other هذا برضه بعمل
return بكون حسّنت الأمر إن إيش؟ احنا كنا بنقول آه
less than تلاتة مثلاً فانا كنت بتخلص هذا و واقف
الآن على less than وبصّ إيش اللي بعدين شوفت لا
شوفت يساوي ولا شوفت greater ده شوفت إيش تلاتة خلاص
بكون إن حسّنت أمر ال less than فمهما رجع ل read up
less than ولكن ولكن ال forward تبعي إيش؟ لازم أرجعه
ثاني لأن اللاكسيم اللي أنا بتطلعه اللاكسيم اللي
أنا بتطلعه إذا بتطلع اللاكسيم بتطلع اليسار ال less
than فقط بتطلع ال less than فقط التلاتة مش داخلة
في اللاكسيم اللاكسيم هو المفروض ال characters ما
بين اللاكسيم begin وما بين ال forward شامل
inclusive صح؟ فبقى التلاتة دخلت صارت داخلة فلازم
يرجع ال what ال forward عشان يصير اللي محصور في ال
less than فقط لحالته عشان هيك النجمة هذه النجمة
هذه إشارة إيه لإنه أنا I have to retract retract
ال forward point نفس
الأشي طبيعي على لو أنا شوفت إيش يقول الحالة الأخرى
ال يساوي ال يساوي مجرد ما أشوفه لأنه بيجي لحاله
قدامي إذا أجد ك character بيجي لحاله ك character
أول ما يجيش حاجة بعده صح؟ فعاد ولحد ما أشوفه I
return or up equal ومافيه retraction بيكون أنا
let's begin هنا ولسه ال forward هنا ما اتمدّتش
ما اتجدّدتتش الحالة الأخرى اللي هي other إنه لأ قلت
إنّه قعدت معاه إنه وأنا ماجي فعلها قادي أنا خلصنا
احنا sorry إنه أشوف ال less than أنا كنت قاعد بحكي
ال greater than .. ال greater than تمام أشوف ال
greater than ك character ابتدائي بعدها ياما ..
بعدها بقى angle ياما مشوف less than .. you equal
ياما حاجة أخرى إذا شوفت ال equal على طول حسّنت
الأمر إن less than هو equal بس شوفت إشي ثاني عامة
ما حسّنتي اتأمر إنه ال greater لحالها فبطل ريقط ال
greater ده واضح؟ هذه الآن ال state diagram أو ال
transition diagram خطوة متقدمة عن ال definition
وداخلة في ال recognition هي أداة بستخدمها في تصميم
آلية ال recognition الـ regular expression و
regular definition هي أداة بستخدمها في تصميم الـ
definition تبع ال tokens وال term صح؟ بنتقل من ال
definition إلى ال recognition أول خطوة اللي هي ال
transition diagram في ال recognition صح؟ إيش
الخطوة اللي بعدها؟ بعد هذا بدي أترجم الآن إلى
code بدي أترجم إلى code بدي
أترجم إلى code هذا من أين أتى؟ هذا أتى من ال
definition هذا نفسه ال transition diagram نبنيه
مباشرة من ال regular definition ال regular
definition الجنراتور الجنراتور الليكسيكال أناليزر
استنادًا إلى ال definition تبعي ببني ال state
diagram لأن كيف ببني أنا بكون معطيله كافة الأشكال
المختلفة تبع ال relational operator
التعريفات هذه بيحلل ال generator بيحلل إيش يعني
characters تيجي في أول وممكن يعملها group لقى قال
إن هذا ال character هي كموارد متكرر هنا ومتكرر
هنا ومتكرر هنا تمام فقال لك okay هاي character
ممكن أطلع من الـ zero state إلى state جديدة بهذا
الـ character تمام، الآن بعد ذلك، إيش فيها هنا ولا
حاجة؟ هي هنا بعدي يساوي وهنا بعدي كده، يبقى من ال
state اللي انتقلت إليها من less than فيه بتوقع
تلات states أخرى اللي هي الاش other يساوي و greater
than واضح؟ كل هذه العملية الاناليزيز بتتم .. بتتم
آليًا يسويها ال generator عشان يعمل ال lexical
analyzer قبل
ما نشوف اللي هو كيف فعليًا ال transition diagram
بتحول إلى code بدنا نشوف هنا ال recognition كان ال
state diagram ال transitional diagram لل
relational operator خلينا نشوف لمين؟ لل identifier
ال identifier هنا ال states أقامها تكملة على الآخر
إيش كان هنا؟ تمانية صح؟ تكمل بعدين شوية هنحكي في
قنوية التكملة ليش ما عمل state diagram ونفصل هنا
relational operator وهنا identifier إيش جبل؟ جبل
المفروض State diagrams جديدة Transition diagrams
جديدة وترقيم جديد احنا الآن خلينا نعتبر زي ما
بقول هي كانت تسعة وعشرة وواحدة عشر start قد إيه
عن تسعة وأنا تسعة إيش أتوقع؟ أتوقع letter ال
letter هذا كيف شكله؟ أي واحد في ال range تبع ال
letters اللي معرف في ال definition تبع ال letters
طبعاً هي letter ومعاها برضه أيضاً underscore في ال
definition هنا أعتقد إنه ما كانش حاطط underscore أو
ما كانش حاطط underscore أو ماكانش حاطط underscore أو
ما كانش حاطط underscore أو ماكانش حاطط
underscore لو أنا في عشرة، إيش متوقع؟ متوقع يا إما
بيجيني letter يا إما بيجيني digit تمام؟ يا إما
بيجيني other طيب letter هي أنا في تسعة أنا
في عشرة بيجيني letter متوقع أو بيجيني digit أو
بيجيني other طيب لو أنا أجاني digit إيش .. إيش
أتوقع؟ بتوقع برضه كمان يجيلي كمان digit أو يجيلي
كمان letter هذا وم دي ينجلني على state جديدة لأ
على نفس ال state لأنه برضه هرجع فهو عامل ال loop
هذه على أساس وحاطط ال letter وال digit مع بعض
قدر ما هم two separate edges أو arcs فأنا وأنا في
عشرة لو اجي ال digit أو ال letter أيًا منهم برجع
برضه كمان على عشرة إلا بخرجش من عشرة إلا إذا جاني
حاجة غير letters و digits بطلع خلاص أكون هذا
identifier صح وإيه إيه إيش يعني هاي؟ أنا مثلاً أقول
rate x rate x هذا هو أنا الaxeme begin هنا
وال forward كان لسه هنا اتقدّمت هذي are letter
نقلتني على عشرة صرت هنا الآن a اجت برضه هي letter
فبقى ده أنا في عشرة اتقدّمت برضه letter برضه letter
برضه letter okay فصرت أنا هنا الآن بعدي اتقدّمت
أجاني white space إيه forward خلاص أنا اتعرّفت إنه
هدول
هدول identifier بس بدون space فبرجع هذا هنا عشان
إيه إيش اللاكسيم يشمل فقط اللي هم هدول عشان هناك
فيه stuff يعني okay الآن ال return هنا اختلفت عن
هناك هناك كان ال return على طول بيعطيني ال token
ال name تبعه وال attribute هنا لأ هنا بستخدم ال
return بروح بستخدم ده function اسمه get token get
token وإيه إيش بيعطيها برد كمان بيعمل install ID
الآن get token هذه وظيفتها إنها إيش؟ تطلع token
تطلع token للمين؟ لل syntax analyzer install ID هذه
وظيفتها إنها تروح تعمل identifier في ال symbol
table ما هو identifier وأول ما بشوف ال identifier
لما بشوفه للمرة الأولى لازم أحطه في ال symbol
table install هذه بتروح وبتحطه في ال symbol table
وبتعطيني ال pointer تبعه يعني هذا ناتج هذا الكلام
اللي هو ال pointer فال pointer مع ال token هي
اللي بتسلمه ال lexical أنا لازم أسلمه لها بسلمه لل
syntax أنا لازم ال install id ماهي يعني ساذجة لو
قبل ما تروح بتحط ال identifier يعني لو rate X هذا
موجود مسبقًا بتروح بتدور إذا هو موجود مسبقًا بتروح
تحطه من جديد بتجيبلي ال pointer تبعه إذا مش موجود
بتروح بتحطه okay install ID هذه وظيفتها إنه إذا مش
موجود بتعمله إذا موجود بتجيبلي بس ال pointer تبعه
okay طيب لـ keywords هذا لش؟ recognition of
reserved words and identifiers احنا دلوقتي شوفنا
identifier طيب يا دي reserved words يعني keywords
صح؟ كيف طيب نعملهم؟ هو نفس الشيء إن أحرف ثابت خلاص
and state هي هو مش مرقم ال states هنا يعني مش قضية
أهمية بغض النظر عن المهم إن أنا ببدأ على start
state بيجينا حرف ال T بيجينا حرف ال H بيجينا حرف ال H
بيجينا حرف ال H بيجينا حرف ال H بيجينا حرف ال H بيجينا
حرف ال H بيجينا حرف ال H بيجينا حرف ال H بيجينا حرف
ال H بيجينا حرف ال H بيجينا حرف ال H بيجينا حرف ال H
بيجينا حرف ال H بيجينا حرف ال H بيجينا حرف ال H بيجينا
ال H بيجينا حرف ال H بيجينا حرف ال H بيجينا حرف ال H
بيجينا حرف ال H بيجينا حرف ال H بيجينا حرف ال H بيجينا
حالـ the non-terminal هذا أو الـ keyword هذه أو الـ
token يعني تبعها و بعمل retract لأنه .. retract
يعني برجع لأنه بكون أنا شجعت و راحت و برجع تاني
لتاني و راجعت THEN okay الآن هذا الأمر لما أنا
بتعرف على ال keyword لما بشوف في ال keyword في
النص في ال input واحد من اتنين اما
عشان نتعرف على ال keywords واحد من اتنين اما ال
keywords مايبتشبه ال identifier صح ولا لا؟ اه يعني
ماينطبق على ال identifier وانطبق على ال keywords
فاحنا ممكن نعمل transition diagram زي هيك وممكن
مانحتاجش transition diagrams بالمرة لل keywords
ونستعيد عن ذلك بإيش بإنه مسبقا مسبقا ال transition
ال symbol table يبقى معموله initialization ومحطوط
فيه records لكل واحدة من ال keywords موجودة هو
بالاصل لما أنا أبني لغة فاضي، مظبوط، شوفت
identifier، حطيته، قول مثلا هذا rate x، حطيته، هذه
رقمه وهذه rate x هذا اللاكسين تبعه، مظبوط؟و بعدين
هنا ال other attributes ال type تبعه مثلا و
integer و مش عارف شو و كده ايش رايك لو احنا جينا
او عملنا مسبقا مجموعة من ال .. ايش ال records واحد
لل F واحد لل M واحد لل S جابل
حتى هنا واتعملنا واتبعنا ان ال keywords هى
identifier أجى ال lexical analyzer طلع شافة them
فكرها انها identifier عجبت ليحطها في ال symbol
table خش لجى موجودة ايش هيعطيني ال ID تمام تباحة
فواحد من اتنين اما ان we install the keywords in
the symbol table initially أو بنعمل اسلوب اللي هو
transition tables لكل واحدة create a separate
transition diagram for each keyword هذا الكلام
بيغنيني عن ان انا اعمل transition diagrams لل
keywords ببساطة بدخلهم بالtable مسبقا هذا اللي هو
ال transition diagram for unsigned
numbers
وهذا for white space الان ساعد number احنا بيجينا
digit تمام بعد كده ممكن يجينا more digits لان لسه
كله جابل النمطة جابل ال decimal تمام الان ممكن
يجيلي الرقم 7351 او 51 و 617 مش عارف شو هذا كله
digit digit digit و بضلني انا الف في 613 اجانب بعد
كده نقطة بنتكر على 14 لان انا في 14 بتوقع ايش بتوقع
يجيلي more digits اللي هي الجزء العشري الجزء الكسر
لان لو ماجاتش النقطة و جاني space او اي حاجة اخرى
خلاص هذا عبارة عن رقمك فقدر accepting و برجع تاني
عشان اسلم الرقم هذالأن لو أتيت من النقطة ده اتجاه
فادر اتجاه ممكن ماتجينيش النقطة و يجيني exponent E
أس .. E .. E أس مثلا تسعة صح بمشي فادر اتجاه صح و
ببدأ أستنى ممكن تجيني plus أو minus أو ماتجينيش و
يجيني digit على طول و يجيني more digits ثم بعد
كتابتيه سلسلة ال digits و ينتهي من الأقلمظبوط؟
فهذا ال state diagram يعبر عن النماذج لأن هذا
وسيلة ال syntax ال lexical analyzer فيه to
recognize ال input بس ال syntax .. ال lexical
analyzer هو عبارة عن program و ال program هذا code
فبنشوف كيف ال code هذا بده يتولد أو بده ينعمل
استنادا إلى طبعا ال white space مش واحدة اللي
اشرحها هنا ال delimiter أي واحد منهم دول ال white
ال ال ال ال space أو tab أو new line بالظبط okay
الآن ال transition diagram based lexical analyzer
هو ال lexical analyzer اللي مبني على أساس .. على
أساس إيش؟ transition diagram اسمه transition
diagram based lexical analyzer transition diagram
based lexical analyzer هو عبارة عن lexical
analyzer يحتوي على مجموع من ال functions منيط هو
عبارة عن مجموع من ال functions function لكل واحد
من ال terminals او ال tokens هذا ال function اسمه
getrel of خاصة بمين؟ بال relational operators ممكن
يكون هناك واحد اتاني اسمه get if واحد اتاني get
else واحد اتاني اسمه get identifier واحد اتاني
اسمه get number لكي يقولوا لهم اتوا في السنوات
اللي حصلناهم في الأول هذا واحد منهم اسمه get roll
up ال get roll up هذه بنيتها
switch statement بداخل while loop while true يعني
دايما اللف طول ما فيه input طول ما فيه input اجرى
اجرى اذا اللي جريته اذا اللي جريته اذا
انت لان في state معينة اذا انت لان في state ايش ال
state اللي انت فيها اذا انت لان في state zero
فاقرأ ال next character هذا الـ next character بناء
على ال .. ال rail up transition diagram اللي هو
هذا إذا هو less than فسوي كذا إذا هو less than
فسوي كذا إيش سوي؟
انتقل من state 0 إلى 1 ببساطة
شديدة اقرأ ال next character إذا ال next character
اللي هو c اللي قريته هو less than يبقى state الان
للثانوية else إذا يساوي state خمسة if greater
than state ستة other مافيه other صح إذا هو
relational operator لازم يبقى body بواحد من جواهر
التلاتة لحظة كل اللي بيسويه ال function inها بتغير
ال state ال variable state if كده ال state one is
.. ال state خمسة is .. ال state ستة is .. ال state
خمسة is .. ال state ستة is .. ال state خمسة is ..
ال state ستة is .. ال state خمسة is .. ال state
خمسة is .. ال state خمسة is .. ال state خمسة is ..
ال state خمسة is .. ال state خمسة is .. ال state
خمسة is .. ال state خمسة is .. ال state
إذا failed بيراح يجرب حاجة اخر انما هي في حد ذاتها
هاي شغلها إنها بتشوف إذا هي على zero و جرت
character و ال character كان واحد منها دولة يبقى
بتغير ال state نفترض ان واحد منها غيرت ال state
إيش بعد ذلك؟ بدها تعمل break break من وين؟ من ال
current و ال loop و تروح على ال loop اللي بعدها
فبترجع تاني على ال state على ال switch ال state
الآن بتكون صارت واحد من هدولة مظبوط؟ خشينا و الأن
معانا state one احنا الآن state one يعني بنيجي هنا
إذا state one بنروح نجرى character جديد إذا ال
character هذا إذا
ال character هذا يساوي فهوول ال state إلى two إذا
greater than state تلاتة إذا state أربعة صح other
state أربعة يبقى هي القضية في الآخر إلى أن واحد من
.. في واحد من ال cases إذا هي case ل accepting
state التماني
هذا مش accepting state إذا أنا هان التماني بقى
accepting state يبقى أنا بدي .. يبقى بكون أنا وصلت
هنا ال greater than مظبوط؟ بكون أنا شوفت ال
greater than بمعنى ذلك بدي أرجع هذا و بدي ارجع بال
forward لورا خطوة فعمليا انا برجع في ال pointer
لورا خطوة في الأول بعدين باخد كل ال characters
اللي ما بين ال black scene بالجن وما بين ال
forward و برجعهم عشان هي كويس و جايل هنا retract
يعني ارجع ال pointer لورا راحة بعدين return token
ال attribute بتبعته ال attribute هذا return token
ده من عن object الـ attribute تبقى GT بعد ذلك الـ
return الـ return token لأن هنا ال .. ال .. ال ..
ال .. هذا ال relation operator أنا مش بحتاج أرجع
اللاكسيم تبعه لكن لو أنه identifier بالظن اللاكسيم
ده حطه في وين؟ في ال symbol table بس في حالة أن
أنا بعمل retract ضروري retract عشان بعد ذلك أقدم
أشوف إيش اللي بعده و أخد بالك
إنما لو بدّي .. لو انه identifier فانا محتاج اطلع
ايضا اللاكسيم فبدي أجيب اللاكسيم على أساس ان هو ما
بين ال .. اللاكسيم beginning وما بين ال forward
واضح؟ الآن .. نكون لدي method أخرى لل identifiers
زي ما قلت method لل numbers method .. وكل هذه ال
methods مبنية على أساس ال .. ايش؟ ال transition
diagram .. diagrams تبعة ال .. تبعة ال terminals
هذا هو عملية الـ recognition الـ recognition
للتوكنز أنه الـ lexical analyzer بده يستخدم هذه ال
functions في أنه يفحص هل اللي أمامنا احنا لان انا
اللاكسين بيجيه على stream of character هنا بده
يستخدم get real up هل اللي يطلع ان انا واجه على
باب relational operator يمكن اه يمكن لأ بستد ايه جت
قبل إذا عطّتني هي عطّتني أنا عطّشت بتقول لي fail أو
بستدّ إيه اللي بعدها؟ إيه اللي بعدها؟ إيه اللي
بعدها؟ أنا لحد إيه ما واحد منهم هدول إيش تعطيني ..
تعطيني صحيح وممكن أنا يبدأ فيها اندي function
واحدة تحتوي عن كلهم الـ states كلهم من ثمانية و
تسعة وكله في هدول خلاص بقول بسمّيها get token
بسمّيها get token وهي بتعطيني token على حسب إيش الـ
.. الـ .. الـ accepting state اللي وصلت له صراحة؟
عشان هيك اللي هو الترقيم هذا مكمل .. مكمل لأن أنا
ممكن عمليًا أجزّهم أو ممكن عمليًا أحطّهم كلهم في إيش
في function واحدة اللي تجيب لي الـ tokens كلها اللي
معرفة في الـ definition الـ definition هي ده احنا
اللي بدأنا منه في عندنا اللي هم .. اللي هم هدول
up, number, id, else, then, if كل هدول يبقوا ..
اللي هم state a transition diagram واحد وهي
بالتالي functional هذه الـ exercises تطلب منك to
provide أو تعمل يعني state transition diagram to
recognize the same language which of the regular
expressions المعروفين في الـ exercise اللي قبل تشوف
الـ expression وبناءً على الـ expression regular
expression أو regular definition بتعملي على أساسه
وإيش transition diagram مثل هذه الأسئلة وممكن تجيء
في امتحانات okay الآن ثلاثة هذا كان نهاية ثلاثة
أربعة في الوقت اللي معنا احنا قلنا هذا كان نهاية
section ثلاثة أربعة ثلاثة خامسة اللي هو كيف نستخدم
الـ X generator خليتها أنا لبعدين بنروح بعد هيك على
ثلاثة إيش ستة اللي هي finite automata اللي هي
متصلة بالـ transition diagram هي مثل الـ transition
diagram الـ finite automata فيها خاصية الخاصية هذه
بدنا بعد ذلك نشوف كيف فيها إشكالين نتغلب عليهما
بيصير بعد ذلك عندنا حاجة اسمها deterministic
finite automata اللي فعلاً على أساسها ممكن ينعمل
بناء للـ functions الـ finite automata مرّ عليكم
صراحة قبل ذلك؟ في أي مادة من المواد؟
like الـ transition diagrams بالظبط ولكن different
في شجرة الظهر يعني الـ finite automata هي
transition diagrams لكن مختلفة بأن الـ finite
automata are recognizer they simply say yes or no
about each possible input string يعني يقولوا نعم
هو كذا أو لا هو مش كذا هنا الـ transition diagram
يعطيني إيش هو بالظبط بس هنا بيقول لي هل هو هيك أو
مش هيك هل هو relation operator ولا مش relation
operator هل هو identifier ولا مش identifier شغل
آخر الـ finite automata come in two فيها منها نوعين
فيها منها non-deterministic وفيها منها deterministic
الـ non-deterministic ما فيش فيها restriction على الـ
label على label تبع الـ edge أي symbol character letter
أو حتى كمان الـ empty string ممكن يبقى label لـ edge
الـ deterministic لا ممنوع أن يكون فيه الـ empty
label لـ .. ممكن يظهر أصلاً الـ label في الـ
definition تبعه
توكنز ما مرّ علينا في الـ relational operator MT صح
لكن وين موجود ممكن هنا لا
طيب الحين هنشوف مثال هو ما مرّ علينا في السابق في
الـ transition diagrams اللي شفناها بس الحين هنشوف
مثال عليهم الـ MT هذا وجوده بيعمل يعني هيرة للـ
lexical analyzer هل يمشي في هذا الاتجاه ولا يتبين
شو؟ اتجاه الـ MT ولا يتبين شو؟ بس المهم الـ
deterministic finite automata معناته have for each
state and for each symbol of its input alphabet
exactly one edge with that symbol leaving that
state إيش يعني؟ يعني أولًا ما فيش الـ MT .. sorry الـ
distinction الأساسية ما بين الـ non-deterministic و
الـ deterministic أنه لو أنا عندي state دعوني
أطلع على البرتفال هذا لو عندي state زي Z0 ممكن
أروح على الـ one أو أرجع ثاني الـ A بيودينا على الـ
one والـ A برضه ممكن ترجعني ثاني يعني هذا non
-deterministic
والـ non-deterministic أنا ما بقدر أبني منها عمليًا
إيش function إذا عندي أنا state director أو زي
هيك ما بقدر لأنه character واحد ممكن يخليه على
نفس الـ state وممكن ينجلي هو نفسه الـ a يعني أنا
عندي هذه هي الـ regular expression
إذا شفت إنه ممكن إنه عندي أنا strings الـ strings
هذه بدايتها بدايتها
حرف الـ a أو حرف الـ b zero or more منهم وبعدها كفي
a ثم b ثم b ممكن تعطوني مثال على هذا الأمر a,b,b
في حد ذاته في الشاشة
بابب بابب بابب
بابب بابب
بابب بابب بابب بابب بابب بابب بابب بابب بابب بابب
هذا الـ regular distribution هي الـ finite
automaton تبعه الـ transition diagram تبعه بس
إشكالية هذا الـ transition diagram أنه بناءً على هذا
أنه من الـ zero للـ one الـ a بتنجلي من الـ zero للـ one
والـ a برضه كمان بترجع للـ zero فهذه الإشكالية اللي
لازم تحلّ يعاد سياق الـ transition diagram بشكل أو
بآخر بحيث أنه ما ترجعش .. ماشي الشرط اللي هنا بيقول
ليه؟ بيقول ليه؟ أن الـ deterministic بيكون for each
state and for each symbol of its input alphabet
exactly one edge هناك كان الـ a له two edges صح أو
لا؟ الـ a طلعت من الـ zero
للـ one طلعتني من الـ one من الـ zero لـ الـ one و
طلعتني من الـ zero لـ الـ zero نفسي فأقول لا exactly
one for each input alphabet exactly one edge with
that symbol leaving that state تمام هو نفسه الـ a
يجيني هنا ما فيش مشكلة إن أنا من نفس الـ state يجيني
مرتين هي بيطلع من نفس الـ state marker أو أكثر لا
هذا بيصير non deterministic هذا هو الفرق الأساسي
بين الـ NFA والـ DFA فاحنا في الأول بنطلع على الـ
non deterministic وبعدين نشوف كيف آليات إزالة هذا
القضية وتحويله من NFA لـ DFA من non deterministic لـ
deterministic عمومًا الـ non deterministic كل الـ DFA
هم NFA بس مش كل الـ NFA هم DFA ولا لا تعريف
الـ NFA non deterministic أنه a finite set of
states هلأ S capital يعني مجموعة مجموعة S is small
S واحد small S اثنين small مظبوط S capital يعني
set a set of input symbols اللي هي الـ alphabet ولا
لا هذا الممثل اللي ما نشوفه قدام يخصّ به الـ
alphabet يعني مجموعة الـ input symbols الـ input
alphabet we assume أن الـ empty which stands for
empty string is never going to be part of الـ
alphabet الـ alphabet لا تحتوي على الـ empty الآن a
transition function تخيّل إيه transition function
بتقول لي زي أنت على state كذا وأجالك الـ input كذا
يبقى تنتقل إلى state كذا يعني الـ transition
function تأخذ
state وتأخذ input وتعطي state صح؟
x إلى sy عشان الأرقام ما يقولوش أنه يتصل فيها state
رقم واحد أو رقم اثنين
in the alphabet a set of next states الآن هنا الـ
input هذا هو alphabet من بر من بر of the alphabet
وأيضًا كمان ممكن يكون empty الـ empty نفسه مش
member of the alphabet بس بالنسبة لـ transition
state بتقبل لـ transition function بتقبل أن يجيها
إيش empty كـ input وبتقولي إذا أجاني إمتي وأنا على
الـ S على الـ state الفلانية الانتقال هيكون على الـ
state كذا فإيش قلنا حتى الآن الـ set of states الـ
set of alphabet characters أو inputs اللي هم الـ
input alphabet transition function واحدة بتقولها
أنا في الـ state كذا وأجاني input كذا وهين تقول لي
إيش الانتقال على وين a state zero as the start
state لازم الـ NFA يبقى فيه start state زي الـ
transition ثقافة الـ state S0 من مجموعة الـ states S
الـ set of states F إيش F دولة؟ F اختصارها final
اللي هم هيكونوا accepting states وهذا ما اختلف
إطلاقًا عن الـ transition diagram كل هذا متحقق في الـ
transition diagram صح؟ الـ transition function
تخيّليها هي هي function بسيطة بتقول إذا أنت في
state كده فالـ state الجديدة هتكون كده وجالك الـ
input الفلاني واضح؟ الـ set of states F هما مجموعة
من S كبيرة صح؟ هدولة مجموعة فرعية من هدولة that
is distinguished as accepting states or final
states حلو كثير okay we can represent either an F,
NFA or DFA as a transition graph okay where the
nodes المهم الـ same symbol this graph is very
much like a transition diagram except
وهذا لأنه N في الـ A؟ إما لو دي في الـ A، لأ N edge
may be labelled by epsilon اللي هي الـMT وهذا
ما شفناهوش في الـ Transition diagrams
both NFA و DFA are transition diagrams where the
nodes are states and the labelled edges represent
the transition function there is an edge labelled
A from state S to state T إذا الـ transition
function بتقول لي إن فعلا only if T is one of the
next states for S بناء على input A واضح حالة كدا
يعني تعريف definition formal هذه كلام اللي احنا
قلناه أكثر من مرة وهذا الـ example اللي قفزته
مباشرة نهيته أصبح الآن واضح ما فيش أي أشكال تمام؟ الآن بناء على هذا الكلام كله بنقدر نفكر في حاجة اسمها transition أو نتخيل حاجة اسمها transition till مزال يعني هو الـ graph نفسه كله الـ NFA كلها أنا ممكن أعبر عنه على شكل table مش هو الـ NFA بيقول لي و أنت على state 0 لو اجاك الـ input الفلان بتنتقل الى state 0 و لو اجاك برضه ممكن تنتقل الى one هو في الآخر ترجمة للـ transition function كله الـ NFA و الـ table كذا كالحقل الـ table هي بيقول لي ازاها على state 0 و أجانب الـ input هذا هنا عشق الـ alphabet روس الهدا هي الـ alphabet وهنا كل possible states يعني هذا هيك عبارة عن S كبيرة صح؟ وهذا هيك عبارة عن سيجما سيجما كبيرة صح؟ وهدولة هم برضه الـ states الـ output set يعني إذا أنا على zero او انا جاني A ممكن اروح اضغط على zero و ممكن يجيلي one لأن D F A تتخيلين أن هناك حاجة مثل ذلك لـ D F A إذا أنا في Zero و اجاني A وجه واحدة أفضل منها الـ A مش هتودينها لهذه وهذه أو هذه إذا كان
إحنا if the transition function has no information
إذا الـ transition function بتقول ليش أي شيء عننا
الحالة هذه مثلًا أنا في state one و جاني الـ report
مافيش .. لأنه أصلا هيته هو أنا في one ما فيش edge
عليها a فبنحط ليهاش الـ zero إشارة إلى أنه we don't
have information about this خارج نقلة إيه الـ
transition ده يا عزيزي؟ واضح؟ هذا الـ braces إشارة
إلى أنه مجموعة من الـ states صح؟ ممكن واحدة ممكن هذا
الـ input و أنا هنا يطلعني على واحدة و هنا يطلعني
على أكثر من واحدة عشان أنا كنت بحط الـ braces الـ
epsilon هو الـ input مسموح يبقى للـ transition
function صح مش من الـ هكذا هو الـ Sigma المفروض
صحيح؟ صحيح؟ ليس من الـ symbol السبعوني الـAlphabet
ولكن مسموح أن يكون input لـ Transition Function
عشان إيه قلو عمود لأن
هذا الـ String هذا الـ string زي و زي الـ keyword
ما هوش regular expression اللي يصف الـ pattern هذا
literal .. literal فالـ state ground تبعه على طول
الـ zero من الـ state zero بروح على a و من الـ a برجع
في الـ zero لأنه ممكن يجيني كمل a بس a تاني واحد
فقط بس ما فيش إلا two a ممكن أجبلهم بعد هيك بصير في
state one
الآن نفس الـ string a a b b ممكن عمليا أعبر عن
الانتقال من الـ state أنه هذا بناء على هذا عبارة عن
string لنفس الـ pattern هذه أي a و b start a,b,b
لأن لو أنا اجالي الـ input هذا و بدى أنا كتبت a,b,b
هذا الآن regular expression يظهر في البطالة وهذا
عبارة عن الـ input لأن الـ input هذا لما اجاني أنا
كنت في zero أجتني الـ a روحت وين؟ رولتني في zero
أجتني الـ a تانية أجتني الـ a تانية أجتني الـ a تانية
أجتني أجتني الـ B التانية صرت فيه ثلاثة لكن برضه
ممكن أجي أقول الـ A الأولى نجلتني على one لأ نجلتني
على zero والتانية نجلتني برضه ضلتني في zero مجبور
هذا الكلام؟ حسب الـ diagram اه حسب الـ diagram اه
بالظبط لأنه
لأن حسب الـ diagram و أنا في zero لو جتني a برجع
تاني و بضلت على zero أيضا لو جتني a مرة تانية برضه
أنا على zero لو جتني b .. ب .. ب .. لأ الـ a
التانية نجلتك على one لو جتني b .. بي نجلتني على
اتنين الـ b التانية نجلتها أكثر ولكن في نفس الواجهة
أيضا ممكن أقول إن الـ a أولى نجلت على zero الـ a
التاني برضه ضلت على zero الـ b برضه على 0 و الـ B
الأخرى برضه على 0 فأنا في يمدي هذا path هذا الآن
path من state ل state اه الـ input هذا الـ input هذا
اللي هو a a b b له أكثر من path له أكثر من path و
هذه هي المشكلة في الـ MFA إن one single string ممكن
يتعمل له أكثر الـ DFA بعد ذلك سنرى كيف يحلل قضية
النقطة في الـ path بعمل deterministic finite
automata يعطيكم
العافية والمحاضرة القادمة إن شاء الله ستكمل من الـ
3-6-4