پاورپوینت طراحي كامپايلر

— پاورپوینت شامل تصاویر میباشد —-

اسلاید ۱ :

تبدیل عبارات با قاعده به DFA

• می توانیم یک عبارت با قاعده را بدون ایجاد NFA به  DFA تبدیل کنیم.
• در ابتدا به انتهای عبارت باقاعده علامت # را اضافه می کنیم داریم :

  r  è  (r)#    

• سپس درخت تجزیه و ترکیب عبارت با قاعده مورد نظر را ترسیم می نمائیم
• در درخت فوق تمامی نشانه های حروف الفبا، # و جاهای خالی در محل برگ ها قرار می گیرند.
• تمامی نودهای داخلی در درخت مربوط به عملگرها خواهد بود.
• سپس تمامی برگ ها را شماره گذاری می کنیم.
• به مثال در اسلاید بعد توجه نمائید.
• 
  

اسلاید ۲ :

مثال : تبدیل عبارت با قاعده به DFA

درخت ترسیم شده برای عبارت زیر:

(a|b) * a #

• هر کدام از جایگاه ها شماره گذاری شده اند
• هر کدام از حروف ها در محل بر گ ها قرار دارند
• نودهای داخلی محل قرارگیری عملگرها می باشد

اسلاید ۳ :

Followposتابع

در ادامه بایستی تابع Followpos  را برای محل منتسب به  برگ ها محاسبه می کنیم

  followpos(i)  : مجموعه مکان هایی است که بعد از مکان i قرار می گیرند

        لازم به ذکر است که این تابع فقط برای محل برگ ها                      تعریف می شود و برای نودهای داخلی قابل تعریف نیست.

.

برای مثال :           ( a | b) * a  #

       ۱      ۲      ۳   ۴

  followpos(1) = {1,2,3}

  followpos(2) = {1,2,3}

  followpos(3) = {4}

  followpos(4) = {}

اسلاید ۴ :

نحوه محاسبه توابع
firstpos, lastpos, nullable

برای محاسبه تابع followpos نیازمند محاسبه توابع زیر در درخت

 نحو می باشیم :

  firstpos(n)  —  

مجموعه اولین حروف تولید شده بوسیله زیر عبارت درمحل n

• lastpos(n) —
• مجموعه آخرین حرف تولید شده بوسیله زیر عبارت در محل n
• nullable(n) —
• این تابع در صورتیکه محل خالی عضوی از رشته تولید شده بوسیله زیر عبارت در محل n باشد برابر true و در غیر اینصورت مساوی false خواهد بود.