پاورپوینت طراحي كامپايلر (pptx) 13 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 13 اسلاید

قسمتی از متن PowerPoint (.pptx) :

بنام خدا 1 2 طراحي كامپايلر 3 تبديل عبارات با قاعده به DFA مي توانيم يك عبارت با قاعده را بدون ايجاد NFA به DFA تبديل كنيم. در ابتدا به انتهاي عبارت باقاعده علامت # را اضافه مي كنيم داريم : r  (r)# سپس درخت تجزيه و تركيب عبارت با قاعده مورد نظر را ترسيم مي نمائيم در درخت فوق تمامي نشانه هاي حروف الفبا، # و جاهاي خالي در محل برگ ها قرار مي گيرند. تمامي نودهاي داخلي در درخت مربوط به عملگرها خواهد بود. سپس تمامي برگ ها را شماره گذاري مي كنيم. به مثال در اسلايد بعد توجه نمائيد. 4 مثال : تبديل عبارت با قاعده به DFA (a|b) * a  (a|b) * a # عبارت با قاعده : درخت ترسيم شده براي عبارت زير: (a|b) * a # هر كدام از جايگاه ها شماره گذاري شده اند هر كدام از حروف ها در محل بر گ ها قرار دارند نودهاي داخلي محل قرارگيري عملگرها مي باشد 5 Followposتابع در ادامه بايستي تابع Followpos را براي محل منتسب به برگ ها محاسبه مي كنيم followpos(i) : مجموعه مكان هايي است كه بعد از مكان i قرار مي گيرند لازم به ذكر است كه اين تابع فقط براي محل برگ ها تعريف مي شود و براي نودهاي داخلي قابل تعريف نيست. . براي مثال : ( a | b) * a # 1 2 3 4 followpos(1) = {1,2,3} followpos(2) = {1,2,3} followpos(3) = {4} followpos(4) = {} محل قرارگيري حروف در عبارت سطوح مختلف درخت 6 نحوه محاسبه توابعfirstpos, lastpos, nullable براي محاسبه تابع followpos نيازمند محاسبه توابع زير در درخت نحو مي باشيم : firstpos(n) -- مجموعه اولين حروف توليد شده بوسيله زير عبارت درمحل n lastpos(n) -- مجموعه آخرين حرف توليد شده بوسيله زير عبارت در محل n nullable(n) -- اين تابع در صورتيكه محل خالي عضوي از رشته توليد شده بوسيله زير عبارت در محل n باشد برابر true و در غير اينصورت مساوي false خواهد بود. 7 طريقه محاسبه توابع firstpos, lastpos, nullable OR node CAT node STAR node 8 چگونه followposرا برآورد كنيم؟ براي محاسبه تابع followpos دو قانون زير را در نظر مي گيريم‌‌ : 1 – اگر سطح n يك cat-node باشد و دو انشعاب c1(چپ) و c2 (راست) داشته باشد و i محلي در مجموعه lastpos(c1) باشد تمامي اعضاي firstpos(c2) در تابع followpos(i) قرار خواهند گرفت. 2 – اگر سطح n يك star-node باشد وi محلي در مجموعه lastpos(n) باشد تمامي اعضاي firstpos(n) در تابع followpos(i) قرار خواهند گرفت. اگر توابع firstpos و lastpos براي هر نود درخت محاسبه شوند تابع followpos با يك پيمايش عمقي در درخت نحوي قابل محاسبه خواهد بود. Cat-node followpos(i) = { firstpos(c2) } ilastpos(c1) firstpos(c2) followpos(i) = { firstpos(n) } Star-node ilastpos(n) firstpos(n) 9 مثال ( a | b) * a # قرمزها– firstpos آبي ها – lastpos پس از محاسبه توابعfirstpos و lastpos تابع followpos را به صورت زير محاسبه مي كنيم. followpos(1) = {1,2,3} followpos(2) = {1,2,3} followpos(3) = {4} followpos(4) = {} پس از محاسبه followpos براي ايجاد DFA آماده مي شويم. .