Principles of Compiler Design - Lecture Notes PDF

‫اصول طراحی کامپایلرها‬ ‫‪1‬‬  ‫درس دوم‪:‬‬ ‫تحلیلگر لغوی‬ ‫ﺟﻠﺴﻪ ﺳﻮم‬ ‫‪2‬‬  ‫ماشین خودکارمتناهی‬ ‫ماشین خودکارمتناهی یک رشته از یک زبان منظم را دریافت می کند‪،‬و درصورتیکه رشته متعلق به زبان باشد‬ ‫آ...

‫اصول طراحی کامپایلرها‬ ‫‪1‬‬  ‫درس دوم‪:‬‬ ‫تحلیلگر لغوی‬ ‫ﺟﻠﺴﻪ ﺳﻮم‬ ‫‪2‬‬  ‫ماشین خودکارمتناهی‬ ‫ماشین خودکارمتناهی یک رشته از یک زبان منظم را دریافت می کند‪،‬و درصورتیکه رشته متعلق به زبان باشد‬ ‫آنرا تصدیق می کندو درغیراینصورت انرا رد می کند‪.‬ماشین خودکارمتناهی دونوع است‪:‬‬ ‫‪-1‬ماشین خودکارقطعی)‪(DFA‬‬ ‫‪-2‬ماشین خودکارغیرقطعی)‪(NFA‬‬ ‫‪38‬‬  ‫ماشین خودکارغیرقطعی‬ ‫ماشین خودکارقطعی را بصورت ) ‪ M = (Q , ,  , q 0 , F‬تعریف می کنیم‪.‬‬ ‫‪ Q‬مجموعه متناهی از حاالت‬ ‫‪ ‬مجموعه متناهی ازنمادها که الفبای زبان است‬ ‫‪ ‬تابع گذر‬ ‫‪ q0‬حالت شروع‬ ‫‪ F‬حالت یا حاالت نهایی‬ ‫‪ o‬در این ماشین‪،‬درهرحالت با خواندن یکی از الفبای زبان امکان چندین گذر وجود دارد‪.‬‬ ‫‪39‬‬.‫ طراحی کنید‬L = ba n : n  1  b n a : n  2 ‫ برای‬nfa ‫یک‬:‫مثال‬ 40 41  ‫مثال‪:‬آیا زبان زیر منظم است؟‬ ‫‪‬‬ ‫‪‬‬ ‫‪L = vwv :v ,w  a , b  ,| v |= 2‬‬ ‫*‬ ‫‪42‬‬ 43  ‫ماشین خودکارقطعی‬ ‫ماشین خودکارقطعی را بصورت ) ‪ M = (Q , ,  , q 0 , F‬تعریف می کنیم‪.‬‬ ‫‪ Q‬مجموعه متناهی از حاالت‬ ‫‪ ‬مجموعه متناهی ازنمادها که الفبای زبان است‬ ‫‪ ‬تابع گذر‬ ‫‪ q 0‬حالت شروع‬ ‫‪ F‬حالت یا حاالت نهایی‬ ‫‪ o‬در این ماشین‪،‬درهرحالت با خواندن یکی از الفبای زبان تنها یک گذر وجود دارد‪.‬‬ ‫‪44‬‬ ‫مثال‪:‬یک ‪ DFA‬برای پذیرش زبان با رشته هایی که دقیقا دو ‪ a‬دارند‪.‬‬ ‫‪45‬‬ ‫مثال‪ :‬یک ‪ DFA‬برای پذیرش زبان با رشته هایی که حداقل یک‪ a‬و دقیقا دوتا ‪ b‬دارند‪.‬‬ ‫‪46‬‬ ‫مثال‪:‬یک ‪ DFA‬برای عبارت باقاعده )‪ 0 ( 10)* (01‬رسم کنید‪.‬‬ ‫‪47‬‬  ‫ایجاد‪nfa‬ازعبارت منظم(باقاعده)‪-‬الگوریتم تامپسون‬ ‫‪ o‬ابتداعبارت منظم‪r‬را به زیرعبارت های سازنده آن تجزیه می کنیم‪.‬‬ ‫‪r = ( a + b ) (c +  )*  r1 = a r2 = b r3 = c r4 = ‬‬ ‫*‬ ‫‪ o‬برای هر کدام از زیرعبارتها یک‪nfa‬رسم می کنیم‪.‬یعنی برای هر‪a  ‬یک ‪nfa‬با حالت شروع‪ i‬بدین صورت‬ ‫ایجاد می کنیم‪.‬‬ ‫‪start‬‬ ‫‪a‬‬ ‫‪i‬‬ ‫‪f‬‬ ‫‪48‬‬  ‫‪f‬‬ ‫‪ N(r) o‬را برای عبارت منظم ‪ r = s + t‬بصورت زیر رسم می کنیم‪:‬‬ ‫) ‪N (s‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪start‬‬ ‫‪i‬‬ ‫‪f‬‬ ‫‪‬‬ ‫‪‬‬ ‫) ‪N (t‬‬ ‫‪49‬‬  ‫‪ N(r) o‬را برای عبارت منظم ‪ r = s.t‬بصورت زیر رسم می کنیم‪:‬‬ ‫‪start‬‬ ‫‪i‬‬ ‫) ‪N (s‬‬ ‫) ‪N (t‬‬ ‫‪f‬‬ ‫‪50‬‬  ‫‪f‬‬ ‫‪ N(r) o‬را برای عبارت منظم * ‪ r = s‬بصورت زیر رسم می کنیم‪:‬‬ ‫‪‬‬ ‫‪start‬‬ ‫‪‬‬ ‫) ‪N (s‬‬ ‫‪‬‬ ‫‪i‬‬ ‫‪f‬‬ ‫‪‬‬ ‫‪51‬‬ ‫مثال‪:‬یک ‪ NFA‬برای عبارت باقاعده )‪ 0 ( 10)* (01‬رسم کنید‪.‬‬ ‫‪52‬‬ ‫مثال‪:‬یک ‪ NFA‬برای عبارت باقاعده* ) ‪ a + b * (ab + c‬رسم کنید‪.‬‬ ‫‪53‬‬  ‫تبدیل‪ NFA‬به ‪DFA‬‬ ‫‪ o‬تعریف) ‪: _ closure (q‬مجموعه حاالتی از‪ NFA‬که از حالت‪ q‬با تبدیل ‪ ‬قابل دسترس هستند‪.‬‬ ‫‪b‬‬ ‫‪a‬‬ ‫‪‬‬ ‫‪1‬‬ ‫‪3‬‬ ‫‪‬‬ ‫‪a‬‬ ‫‪5‬‬ ‫‪0‬‬ ‫‪b‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪2‬‬ ‫‪4‬‬ ‫‪‬‬ ‫‪54‬‬ ‫‪:  _ closure (T‬مجموعه حاالتی از‪ NFA‬که از حاالت مجموعه‪ T‬با تبدیل ‪ ‬قابل دسترس هستند‪.‬‬ ‫‪ o‬تعریف )‬ ‫‪55‬‬ ‫‪ o‬تعریف ) ‪: move (T , a‬مجموعه حاالتی از‪ NFA‬که از حالت‪ s‬درمجموعه‪ T‬وبانماد ورودی‪ a‬یک گذر به انها انجام‬ ‫می شود‪.‬‬ ‫‪56‬‬  ‫الگوریتم تبدیل ‪NFA‬به ‪:DFA‬‬ ‫‪  _closure(s) o‬را محاسبه می کنیم‪.‬وبه مجموعه حاصل یک اسم اختصاص می دهیم‪.‬وآنرا به جدول‬ ‫‪Dtrans‬اضافه می کنیم‪.‬مجموعه موردنظر حالت شروع‪DFA‬می باشد‪.‬‬ ‫‪ o‬یک حالت عالمت نخورده‪،‬در‪Dtrans‬راپیدا می کنیم‪.‬و آنرا ‪ T‬می نامیم‪.‬ومراحل زیر را روی ان اجرا میکنیم‬ ‫(ابتدا فقط یک حالت درجدول ‪Dtrans‬وجود دارد)‪.‬درصورت عدم وجود حالت عالمت نخورده الگوریتم تمام‬ ‫است‪.‬‬ ‫‪-1‬حالت انتخاب شده را عالمت می زنیم‪.‬‬ ‫‪-2‬برای هرنماد از الفبای زبان(در الگوریتم انها را‪ a‬می نامیم) مراحل زیر را انجام می دهیم‪:‬‬ ‫‪57‬‬  ‫‪:1-2‬مجموعه) ) ‪  _closure ( move (T , a‬رامحاسبه می کنیم‪(.‬درالگوریتم آنرا‪U‬می نامیم) اگر این‬ ‫مجموعه با مجموعه هایموجود در‪ Dtrans‬یکسان نبود نام جدیدی به آن اختصاص می دهیم‪،‬و آنرا به‬ ‫‪Dtrans‬اضافه می کنیم‪.‬‬ ‫‪:2-2‬در واقع باید به جدول ‪،Dtrans‬درصورت تکراری نبودن ‪ Dtrans [T , a ] = U‬را اضافه کنیم‪.‬‬ ‫مجموعه ای را که شامل حداقل یکی از حالت های پایانی‪NFA‬باشد را بعنوان حالت پایانی‪ DFA‬مشخص‬ ‫می کنیم‪.‬‬ ‫‪58‬‬  ‫مثال‪NFA:‬زیر را به ‪DFA‬تبدیل کنید‪.‬‬ ‫‪b‬‬ ‫‪a‬‬ ‫‪‬‬ ‫‪1‬‬ ‫‪3‬‬ ‫‪‬‬ ‫‪b‬‬ ‫‪‬‬ ‫‪a‬‬ ‫‪6‬‬ ‫‪-1‬‬ ‫‪0‬‬ ‫‪5‬‬ ‫‪b‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪2‬‬ ‫‪4‬‬ ‫‪‬‬ ‫‪59‬‬  ‫آموزش طراحی کامپایلر‬ ‫‪faradars.org/fvsft104‬‬ ‫‪59‬‬  ‫آموزش طراحی کامپایلر‬ ‫‪faradars.org/fvsft104‬‬ ‫‪60‬‬  ‫آموزش طراحی کامپایلر‬ ‫‪faradars.org/fvsft104‬‬ ‫‪61‬‬  ‫آموزش طراحی کامپایلر‬ ‫‪faradars.org/fvsft104‬‬ ‫‪62‬‬  ‫آموزش طراحی کامپایلر‬ ‫‪faradars.org/fvsft104‬‬ ‫‪63‬‬  ‫مثال‪NFA:‬زیر را به ‪DFA‬تبدیل کنید‪.‬‬ ‫‪b‬‬ ‫‪a‬‬ ‫‪‬‬ ‫‪1‬‬ ‫‪3‬‬ ‫‪a‬‬ ‫‪0‬‬ ‫‪‬‬ ‫‪b‬‬ ‫‪2‬‬ ‫‪4‬‬ ‫‪64‬‬ 65