اصول طراحی کامپایلر

اصول طراحی کامپایلر

اسلاید 1: اصول طراحي کامپايلرتهيه کننده: سيده فاطمه نورانيگروه: کامپيوتردانشگاه پيام نور

اسلاید 2: شناسنامه منبععنوان منبع: کامپايلرهامترجم: دلداريانتشارات: باغاني (خراسان)منبع اصلي:Compilers:Principles, Techniques, and Tools

اسلاید 3: جايگاه درس در رشته کامپيوترضرورت اين درس:ضرورت نياز به زبانهای سطح بالاضرورت ترجمه برنامه های نوشته شده با زبان سطح بالا به برنامه به زبان ماشينتنوع زبانهای برنامه نويسی سطح بالادروس پيش نياز: نظريه زبانها و ماشين، طراحی و پياده سازی زبانهانوع درس: اجباريتعدادکل ساعات تدريس:30تعداد جلسات تدريس:10

اسلاید 4: فصل اول: مقدمه اي بر کامپايلراهداف رفتاري:دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: برنامه هاي تحليل کننده آشنايي با بخش تحليل و بخش سنتز کامپايلر ابزارهای ساخت کامپايلر

اسلاید 5: 1-1 نمونه اي از برنامه هاي تحليل کنندهويرايشگرهاي ساختارچاپگرهاي pretty printerبررسي کننده هاي ايستامفسرهاشکل دهنده هاي متنکامپايلرهاي سيليسيوميمفسرهاي پرس و جو

اسلاید 6: 1-2 تعريف كامپايلر1- ترجمه برنامه از زبان مبدا به برنامه معادل دز زبان مياني مانند اسمبلي 2- گزارش وجود خطاها را در برنامه مبدا به كاربر.کامپايلر«تحليل+ سنتز»برنامه مبدأپيغام خطابرنامه مقصد

اسلاید 7: 1-3 طبقه بندي كامپايلرهادسته بندي كامپايلرها بر اساس چگونگي ساخت و عمليات: تك گذره چند گذره اشكال زدا و Load-and-go بهينه ساز

اسلاید 8: 1-4 عمليات كامپايلر بخش تحليلتجزيه برنامه مبدا به اجزاي تشكيل دهنده اش توليد كد مياني از برنامه مبدابخش سنتز تبديل كد مياني به برنامه مقصد در زبان ديگر نياز به بيشترين روشهاي خاص

اسلاید 9: 1-5 سيستم پردازش زباناجزاي سيستم پيش پردازشگر كامپايلر اسمبلر باركننده و ويرايشگر الحاق

اسلاید 10: 1-5-1پيش پردازشگرجمع آوري ماژولهاي برنامه مبدا موجود در فايلهاي جداگانه تبديل بخشهاي خلاصه شده بنام درشت دستورات به احكام زبان مبدا

اسلاید 11: 1-5-2 ارتباطات در سيستم پردازش زبانپيش پردازشگرباركننده / ويرايشگر الحاقكامپايلراسمبلراسكلت برنامه مبدابرنامه مبدابرنامه اسمبلي مقصدكد ماشين جابجاپذيركد ماشينكتابخانه فايل هاي مقصد جابجاپذير

اسلاید 12: 1-6 سه فاز تحليل در عمل کامپايل

اسلاید 13: 1-7 مراحل كامپايل1- تحليل لغوي2- تحليل نحوي3- تحليل معنايي4- توليد كد مياني 5- بهينه سازي كد6- توليد كد نهاييجلوبندي( گروه فازهاي متوالي وابسته به زبان مبدا)عقب بندي( گروه فازهاي متولي وابسته به زبان مقصد)

اسلاید 14: تحليل گر لغويتحليل گر نحويتحليل گر معناييتوليد كننده كد ميانيبهينه ساز كدتوليدكننده كد نهاييمدير جدول نماداداره كننده خطا1-7-1 نمودار مراحل كامپايل

اسلاید 15: 1-7-2 مراحل کامپايلر- تحليل گر لغويمرور متن برنامه به صورت حرف به حرف تبديل آنها به نشانه ها ( كلمات كليدي، عملگر، جداكننده، ثوابت و شناسه)

اسلاید 16: 1-7-2 مراحل كامپايل- تحليل گر نحويبررسي خروجي تحليل لغويساخت درخت تجزيه از نشانه ها

اسلاید 17: 1-7-2 مراحل كامپايل - تحليل گر معناييبررسي برنامه مبدا براي يافتن خطاهاي معناييجمع آوري اطلاعات مربوط به نوع داده ها

اسلاید 18: 1-7-2 مراحل كامپايل - توليد كد ميانيخواندن برنامه وروديتبديل به برنامه اي در زبان مياني مانند اسمبلي

اسلاید 19: 1-7-2 مراحل كامپايل - بهينه ساز كدبهينه كردن كد مياني ( حذف متغيرهاي مياني غير ضروري)سرعت بخشيدن به توليد كد نهايي

اسلاید 20: 1-7-2 مراحل كامپايل - توليد كننده كد نهاييتبديل كد مياني بهينه به كد جابجاپذير يا اسمبليتعيين مكانهاي حافظه براي متغيرهاي برنامهانتساب متغيرها به ثبات هاي ماشين

اسلاید 21: 1-7-2 مراحل كامپايل - مديريت جدول نمادتعريف ساختمان داده اي شامل ركورد براي شناسه و ميدانهايي براي صفات أنهدففراهم كردن شناسايي سريع ركورد شناسه بمنظور ذخيره و بازيابي داده هايش

اسلاید 22: مثال از مراحل كامپايل: عبارت Area:= Pos + Rate * 50Area:= Pos + Rate * 50تحليل گر لغويid1:= id2+ id3 * 50id1id2id3:=+*تحليل گر نحويid1id2id350:=+*Into realتحليل معناييtem1:=into real 50tem2:=id3 * tem1tem3:= id2 + tem2Id1:= tem3توليد كد ميانيtem1:= id3 * 50.0Id1:= id2 + tem1بهينه سازMov id, R2Mul 50.0 , R2Mov R1, id1توليد كد نهاييMov id2 , R1Add R2, R150

اسلاید 23: 1-8 ابزارهاي ساخت كامپايلر مولدهاي تجزيه كننده توليد كننده هاي پويشگر موتورهاي ترجمه نحوگرا مولدهاي كد خودكار موتورهاي جريان داده

اسلاید 24: فصل دوم :نحو زبان و تجزيهاهداف رفتاري:دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: گرامراشتقاق و تجزيهتعريف نحوگرا درخت نحوی تجزيه بالا به پايين و پايين به بالاترجمه

اسلاید 25: 2-1 گرامروسيله تشخيص عضويت يك رشته در زبانگرامر: روش ساخت رشته هايي متشكل از نمادهامشخص كننده ساختار يك زبانتعريفکاربرد

اسلاید 26: 2-2 تعريف رياضي گرامرگرامر 4 گانه {N, T, S, P} = G N= مجموعه غير پايانه ها = T مجموعه پايانه هاS = عضو شروعP = مجموعه قوانين توليد رشته هاي زبان

اسلاید 27: مثال از يك گرامرN = { E, F }T = { +, * , / ,id }S = EP = { E  F * id , F  F / E , F  F + F } رشته توليدي نمونهid * id+ id

اسلاید 28: 2-3 اشتقاق فرآيند توليد رشته از گرامر با شروع از عنصر ابتداي گرامر و استفاده از قوانين.انواع اشتقاقاز چپ: در هر قدم انجام جايگزيني روي سمت چپ ترين غيرپايانهاز راست: در هر قدم انجام جايگزيني روي سمت راست ترين غيرپايانه

اسلاید 29: مثال از اشتقاقid + id * idتوليد رشتهاشتقاق راستE  E + E  E + E * E  E + E * id  E + id * id  id + id * idاشتقاق چپE  E + E  id + E  id + E * E  id + id * E  id + id * id

اسلاید 30: 2-3-1 درخت تجزيهدرخت تجزيه نشان دهنده چگونگي اشتقاق رشته اي از زبان از نماد شروع گرامرساخت درخت تجزيهفرزندان آن XYZ گره اي در درخت و A = A  XYZ قانون فرزندان آن X ,a گره اي در درخت و A = A  Xa قانونپايانه ها ( حروف كوچك) تنها در برگها ديده مي شوند. - S ريشه درخت

اسلاید 31: 2-3-2 درخت اشتقاقدرخت تجزيه اي نشان دهنده مراحل اشتقاق بكار رفته (راست يا چپ)مثالEEEEididid+*Eid + id * id

اسلاید 32: 2-4 گرامر مبهموجود دو اشتقاق راست يا دو اشتقاق چپ راي يك رشته در گرامر مثالid + id * idاشتقاق چپ اولاشتقاق چپ دومE  E + E  id + E  id + E * E  id + id * E  id + id * idE  E + E  id + E  id + E * E  id + id * id

اسلاید 33: 2-5 نشان گذاري پسوندينشان گذاري يك عبارت مانند E 1- اگر E متغير و يا ثابت باشد نشان گذاري آن خودش مي شود.2- اگر E عبارتي بشكل E1 op E2 باشد كه Op عملگر دودويي است نشان گذاري آن عبارتست از F1 F2 Op كه F1, F2 نشان گذاري E1 , E2 هستند.3- اگر E عبارتي بشكل (E1)باشد، نشان گذاري براي E1 همان نشان گذاري براي E مي باشد. 9-(5+2)952+ -

اسلاید 34: 2-6 تعريف نحو گرا كاربرد براي ترجمه ساختارهاي زبان. ترجمه ساختار را بر حسب صفات مربوط به مولفه هاي نحوي تعيين نوع ساختار، مكان اولين دستور توليد شده در برنامه هدف يا تعداد دستورات براي كامپايلر

اسلاید 35: 2-6-1 تعريف نحوي جهت دارگرامر و مجموعه اي از قواعد معنايي وابسته به آنهر نماد در گرامر مجموعه اي از صفات دارد.در هر مولد يا قانون گرامر مجموعه اي از قواعد معنايي براي محاسبه مقادير صفات نمادها وجود دارد. صفات و محاسبه آنها

اسلاید 36: 2-7 ترجمهساختن درخت ترجمه: الف( ساختن درخت تجزيه براي ورودي ب) اگر گره n در درخت تجزيه با نماد x از گرامر متناظر باشد، x.a مقدار صفت a از نماد x در آن گره است. ج) مقدارx.a در گره n با استفاده از قواعد معنايي براي صفت a همراه با قانون گرامري استفاده شده درگره n محاسبه مي شود.

اسلاید 37: مثال از ترجمهقانونقواعد معناييexpr expr1 + termexpr expr1 - termexpr termterm 0term 1term 9…..expr.t := expr1.t // term.t // ,+,expr.t := expr1.t // term.t // , - ,expr.t := term.tterm.t := , 0,term.t := , 1,…..term.t := , 9,تعريف نحوگرا براي ترجمه عبارات ميانوندي به عبارت معادل پسوندي

اسلاید 38: 2- 7-1درخت نحوي expr.t = 95-2+expr.t = 95-expr.t = 9term.t = 2term.t = 5term.t = 992-5+

اسلاید 39: 2-7-2 انواع درخت نحويهر گره نماينده يك عملگر و فرزندان آن عملوند آندرخت تجزيه اي كه عملگرها خود فرزند محسوب مي شوند.درخت نحو مجرددرخت نحو واقعي

اسلاید 40: 2-8 الگوي ترجمهگرامر مستقل از متني كه قطعه برنامه هايي كه عمليات معنايي ناميده مي شوند در سمت راست قوانين آن اضافه شده اند.تفاوت با ترجمه نحوگرانمايش ترتيب ارزشيابي قوانين بطور صريح.

اسلاید 41: 2-8-1 درخت توليد شده براي الگوي ترجمهexprterm+expr1{print ( ,+, ) }يك برگ اضافي ساخته شده براي عمل معني1- ساختن فرزند اضافي براي درخت2- متصل نمودن اين فرزند به گره مربوط به قانون خود در گرامرطريقه ساخت درخت

اسلاید 42: 2-9 تجزيه ( پارسينگ)* تجزيه به كمك تحليلگر نحوي و به نام تحليل نحوي انجام مي گيرد.* در تجزيه تعلق رشته ورودي به زبان مبدا بررسي مي شود.* بررسي طبق ساختار و نحو دستورات زبان مبدا انجام مي گيرد.

اسلاید 43: 2-9-1 تجزيه- دسته بندي روشهاروش بالا به پايين :ساخته شدن درخت تجزيه ازبالا به پايين. مانند LL(1)روش پايين به بالا:ساخته شدن درخت تجزيه از پايينمانند تجزيه به بالاعملگر0 اولويت و LR

اسلاید 44: 2-9-1-1 تجزيه كننده بالا به پايينآغاز تجزيه از عنصر شروع گرامرجايگزيني قانون يك غير پايانهقانون كاربرد دارد؟برو به قانون سطح بعد عقبگرد به قانون هم سطح ديگربليخير

اسلاید 45: مثال از تجزيه بالا به پايينS  bBeB  cf/ ce/cتجزيه:bSSSSBBBBbbbeeeeeccfBack trackingBack trackingcb

اسلاید 46: 2-9-1-2 تجزيه بالا به پايين پيش گويانهنماد پيش نگرمجموعه تمام پايانه هايي است كه در قوانين مربوط به غير پايانه در سمت چپ قرار مي گيرندبا نگاه به نماد پيش نگر در مورد استفاده از هر قانون درتصميم گيريروش تجزيه بالا به پايين بدون ويژگي عقبگرد

اسلاید 47: مثالنمادهاي پيش نگر يا مجموعهFirstA  aB /cC / eB  dA / cC  cB / aFirst (C) : {c, a }First (B): { d, c }First (A):{ a, c, e }

اسلاید 48: 2-10 بازگشتي چپظاهر شدن غير پايانه سمت چپ در سمت راست قانون بعنوان اولين عنصرحذف بازگشتي چپ پيش از تجزيهA  Aa / Ab / Ac / x / yA  xZ / yZ Z  aZ / bZ / cZ

اسلاید 49: مثالحذف بازگشتي چپS  Aa / bA  Ac / SdA  Ac / Aad / bdS  Aa / bS  Aa / bA  bdZZ  cZ / adZ

اسلاید 50: 2-11 فاكتور چپيكسان بودن عنصر سمت چپ در حداقل دو قانون گرامرفاكتورگيري چپA  aB / aCA  aZZ  B / Cفاكتورگيري از a

اسلاید 51: مثالفاكتورگيري چپS iEtS / iEtSes S aE  bS  iEtSZ /aZ  eSE  bS  iEtSS  iEtSeS / aE  b

اسلاید 52: 2-12 تحليل لغوي- دريافت يك رشته كاراكتري از ورودي- استخراج نشانه ها از آن- تحويل نشانه ها به تجزيه كننده- ارتباط دادن پيامهاي خطاي توليد شده كامپايلر با برنامه مبدا- حذف فضاهاي خالي بين عبارات و توضيحات برنامه- تشخيص شناسه ها و كلمات كليدي زبان

اسلاید 53: مثالتحليل لغوي عبارت دستوري Count = count + incrementتحليل گر لغويid = id + idتجزيه كنندهCount = count + incrementid = id + id

اسلاید 54: 2-12-1 رابط تحليلگر لغويوروديتحليل گر لغويخواندن كاراكتربرگرداندن كاراكترتوليد و ارسال نشانه و صفات آنتحليل گر نحوي ( تجزيه كننده)ميانگيرمصرف نشانه ها براي تعيين ساختار دستورات1- در هر زمان حاوي يك بلوك از كاراكترها2- اشاره گري به مكان نشانه بعدي پردازش نشدهميانگير

اسلاید 55: 2-13 تشكيل جدول نمادجدولي ساخته شونده توسط. فازهاي تحليل، مورد استفاده فازهاي توليد كدفاز تحليل لغويفاز تحليل نحويفاز توليد كدذخيره رشته كاراكتري تشكيل دهنده شناسه در جدول.اضافه كردن نوع شناسه، مورد استفاده(رويه، متغير و..)درج مكان شناسه در حافظه در جدولفاز تحليل معنايياستفاده از اطلاعات جدول براي دسترسي به متغير و توليد كد

اسلاید 56: 2-13-1 جدول نماد- روالهاInsert ( s , t) :Lookup ( s ) :انديس وارده جديد مربوط به رشته s نشانه t را بر مي گرداند.اگر s در جدول است، انديس آن بر مي گردد اگر نه، صفر بر مي گرددعمل Lookup تعيين وجود شناسه در جدول نماد عمل Insert در صورت عدم وجود شناسه ، درج آن در جدول

اسلاید 57: 2-13-2 جدول نماد- پياده سازي اشاره گر:نشانهصفاتtoken : attributes: ptr كلمات دستوري در متن برنامهmod divدنباله كاراكترهاي وروديdivmodid

اسلاید 58: 2-14 ماشين پشته انتزاعيماشين پشته انتزاعي: شكل مرسوم نمايش مياني توليد كداجزاي ماشين1- حافظه دستورات2- حافظه داده هامحاسبات ماشين1- محاسبات صحيح2- دستورات دستكاري پشته3- روند كنترل

اسلاید 59: 2-14-1 دستورات محاسباتي قابليت پياده سازي مستقيم عملهاي پايه مانند جمع ، تفريق و ... در ماشين انتزاعي پياده سازي. عمليات پيچيده تر با دنباله اي از دستورات اوليه ماشين استفاده از نمايش پسوندي در كد ماشين براي ارزيابي يك عبارت محسباتي استفاده از پشته در حين ارزيابي عباراتارزشيابي عبارت در ماشينبيرون پراندن عملوندها از پشتهانجام عملگر بر روي مقدار پشتهقرار دادن نتيجه بر روي پشته

اسلاید 60: مثال ارزيابي عبارت محاسباتي با پشته13 + 5* عبارت محاسباتي1- عدد 1 را روي پشته قرار ده2- عدد 2 را روي پشته قرار ده3- دوتا از بالاترين عناصر پشته را با هم جمع و آن دو را از پشته بيرون ده4- نتيجه يعني عدد 4 را روي پشته قرار ده5- عدد 5 را روي پشته قرار ده6- دوتا بالاترين عناصر پشته را در هم ضرب و آنها را بيرون ده7- نتيجه يعني عدد 20 را روي پشته قرار ده

اسلاید 61: 2-14-2 دستكاري پشتهS را روي پشته قرار ده محتويات مكان L را روي پشته قرار ده آدرس L را روي پشته قرار ده مقدار در بالاي پشته را دور بريز r-value بروي پشته در l-value زير آن گذاشته و هر دو از پشته خارج يك نسخه از مقدار بالاي پشته را بر روي پشته فشار بدهPush spop=:lvalue lrvalue lcopy

اسلاید 62: مثال عمليات در پشته هنگام محاسبهday := (1461*y) div 4 + (153*m + 2 ) div 5 + d ترجمه lvalue daypush 1461rvalue y*push 4divpush 153rvalue m*push 2+push 5div+rvalue d+:=

اسلاید 63: 2-14-3 كنترل جريان در ماشينتعيين مكان پرش1- تعيين محل پرش با عملوند دستور2- تعيين فاصله نسبي براي پرش مثبت يا منفي با عملوند دستور3- تعيين محل پرش با نماد هاي دستور امكان برداشتن عملوند از بالاي پشته

اسلاید 64: 2-14-3-1 كنترل جريان - دستوراتlable l L عدم تاثير در مقصد پرش ها به goto l L اجراي دستور بعدي از حكمي با برچسب gofalse l خارج نمودن مقدار بالاي پشته، پرش در صورت صفر بودن gotrue l خارج نمودن مقدار بالاي پشته ، پرش در صورت صفر نبودن halt توقف اجرا

اسلاید 65: فصل سوم: تحليلگر لغوياهداف رفتاري:دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: آشنايي با تحليلگر لغوی عبارات و گرامر باقاعدهتحليلگر لغوی Lex ماشين خودکار قطعی و غير قطعی و تبديل آنها به يکدگر

اسلاید 66: 3-1 وظايف تحليل گر لغوي 1- خواندن نمادهاي ورودي2- توليد دنباله اي از نشانه ها 3- ثبت نشانه ها در جدول نمادها 4- حذف توضيحات برنامه، جاي خالي و كاراكتر مربوط به سطر جديد 5- ارتباط دادن پيامهاي خطاي توليد شده كامپايلر با برنامه مبدا

اسلاید 67: 3-2 ارتباط با تجزيه كنندهتحليل گر لغويتحليل گر نحوي (تجزيه كننده)جدول نمادارتباط تحليل گر لغوي با تجزيه كنندهنشانه بعدي را بدهنشانهبرنامه مبدا

اسلاید 68: 3-2-1 دلايل جدايي فازهاي تحليل لغوي و تجزيه1- ساده تر بودن طراحي دو فاز3- قابليت حمل كامپايلر و محدود شدن تغييرات به تحليلگر لغوي2- افزايش كارايي كامپايلر به دليل استفاده از ميانگير بين دو فاز

اسلاید 69: 3-3 خطاي مرحله تحليل لغويمنطبق نبودن هيچ كدام از الگوهاي مربوط به تشخيص نشانه ها در زبان مبدا با پيشوندي از وروديروشهاي پوشش خطاPanic Mode 1-2- حذف كاراكتر اضافي3- درج كاراكتر از قلم افتاده4- جايگزيني يك كاراكتر بجاي كاراكتر غلط5- جابجا نمودن دو كاراكتر مجاور هم

اسلاید 70: 3-3-1 پوشش خطا- Panic mode ساده ترين شيوه پوشش خطا حذف كاراكترهاي متوالي از باقيمانده ورودي تا پيدا شدن نشانه قابل قبول توسط تحليل گر لغوي كافي بودن براي يك سيستم محاسباتي محاوره اي

اسلاید 71: 3-4 تحليلگر لغوي – پياده سازيروشهاي پياده سازيLexاستفاده از توليد كننده تحليلگر لغوي مانند كامپايلر نوشتن تحليلگر لغوي به زبانهاي متداول برنامه نويسيI/O سيستم و خواندن رشته ورودي با تسهيلات نوشتن تحليلگر لغوي به اسمبلي و مديريت صريح خواندن رشته ورودي

اسلاید 72: 3-5 عبارات با قاعدهقواعد تعريف1- عبارت باقاعده  زبان {} (مجموعه حاوي رشته تهي) را مشخص مي نمايد. 2- {a} عبارت باقاعده اي است که زبان a (نمادي از Σ) را مي سازد.3- اگر a و b عبارات باقاعده باشند، اجتماع، الحاق و Kelin Star آنها هم باقاعده است.

اسلاید 73: مثال عبارات باقاعده 2- از عبارت باقاعده (aUb) (aUb) مجموعه { aa, ab,ba,bb} توليد مي شود. 3- عبارت باقاعده a* كليه رشته هايي با صفر يا چند a را توليد مي كند.4- عبارت باقاعده (aUb) * رشته هايي با صفر يا چند نماد از b يا a را توليد مي كند.اگر ={a,b} باشد آنگاه: 1- از عبارت باقاعده aUb مجموعه {a , b} ساخته مي شود.

اسلاید 74: 3-5-1 عبارات باقاعده – خواص جبرياصلتوصيف/ شركت پذير است / جابجا پذير است.الحاق شركت پذير است.الحاق نسبت به / توزيع پذير استa U b = b U aa U ( b U c)=(a U b U c(a b) c = a (b c)a (b U c) = a b U a c( b U c) a = b a U c aa* = (a U  )a** = a*

اسلاید 75: مثال عبارات با قاعده در زبان پاسكال تعريف باقاعده مربوط به شناسه هاLetter  A B … Z a b … zDigit  0 1 … 9Id  letter ( letter / digit ) *تعريف باقاعده اعداد بي علامتDigit  0 1 … 9Digits  digit digit *Optional_fraction  . Digits Optional_exponent  ( E( + - )digits)  Num  digits optional_fraction_exponent

اسلاید 76: 3-6 مجموعه هاي بي قاعده1- ساختارهاي موازنه اي و لانه اي2- رشته هاي تكراري3- رشته هايي براي مقايسه دو چيز

اسلاید 77: 3-7 گرامر با قاعدهفرم قوانين گرامر باقاعدهA → aA → λA → aBa عنصري از الفبا و پايانهB و A غير پايانه

اسلاید 78: مثال چند گرامر با قاعدهْG: S  abSA A  Aa الفبG: S  aSb/abپG: S  bS/cS/aBB  aB/cS /bC C  aB / bS

اسلاید 79: 3-8 توليدكننده تحليلگر لغوي Lex -روش ايجاد تحليلگر توسط Lex1- آماده شدن پرونده اي حاوي مشخصه تحليلگر براي Lex2- تبديل محتواي پرونده به برنامه در زبان C3- كامپايل برنامه توليدي همراه كتابخانه برنامه تحليل لغوي 4- خروجي: برنامه تحليلگركامپايلر Yaccكامپايلر C مشخصه :Lex.1Lex.yy.ca.outLex.yy.cخروجيدنباله نشانه هاa.outورودي

اسلاید 80: 3-8-1 - Lexاجزاي برنامهاعلان هاقواعد ترجمهرويه هاي كمكيc بخش هاي برنامه مبدا Lexترتيب در متن برنامه مبدا Lexاعلان هاقواعد ترجمهرويه هاي كمكيc%%%%

اسلاید 81: 3-8 توليدكننده تحليلگر لغويبخش اعلان برنامهاعلان متغيرهااعلان ثوابت صريحتعاريف باقاعده (اجزاي عبارات باقاعده مورد استفاده در قواعد ترجمه)

اسلاید 82: بخش قوانين ترجمه بلافاصله پس از %%عبارت باقاعدهعمل مناسبP1 : {عمل معنايي 1 }P2 : {عمل معنايي 2 } : {عمل معنايي 3 }...3-8-1 - Lexاجزاي برنامهC رويه هاي كمكي مورد استفاده دراجراي اعمال

اسلاید 83: 3-9 ماشين خودكار متناهيابزاري براي تشخيص ساختارهاي موجود زبان در دنباله ورودي از نشانه ها و پذيرفتن يا نپذيرفتن دنباله كاراكترهاي ورودي انواع ماشين هاي خودكار1- ماشين خودكار متناهي قطعي DFA 2- ماشين خودكار متناهي غير قطعي NFA

اسلاید 84: 3-9-1 ماشين خودكار قطعي M= (Q ,  ,  , q0, F)زيرمجموعه اي از Q به نام حالات نهاييحالت ابتدايي يا شروع ماشينمجموعه متناهي از حالات ماشينيك مدل رياضي است متشكل از 5تاييالفباي زبانتابع گذر

اسلاید 85: 3-9-2 ماشين خودكار غير قطعي DFA اي كه مي توان از هر حالت با عناصر ورودي يكسان به حالات مختلفي رسيد. q3q1q7q4q4q3aaaaDFANFA

اسلاید 86: مثال ازDFA S  aS / aAA  bA / bتبديل به ماشين قطعيSAZaabbاشتقاقمحاسبهرشته پردازش شدهS  aS  aaA  aabA  aabb [S , aabb]  [S , abb][A,bb] [A , b] [Z, ] aaaaabaabbپذيرفته توسط ماشين

اسلاید 87: مثال ازNFA زبان: ( a U b)* abb1023abbbشروع

اسلاید 88: 3-9-3 تبديل NFA به DFA تعريف : هبستگي لامبدا يا - closure (qi) به صورت بازگشتي : 3- همبستگي : qj در  -closure (qi) است اگر بتواند با تكرار متناهي از مرحله بازگشت بدست آيد. 1- پايه: qi   -closure (qi) 2- مرحله بازگشت: اگر qj يك عنصر از closure(qj)-  باشد و اگر qk (gj ,  ) آنگاه qk   -closure (qj) است.

اسلاید 89: مثال همبستگي لامبداq0q2q1aaacbacbحالتq0q1q2{ q1 , q2, q0 }{ q1 , q2}{q1}{q1}-----

اسلاید 90: مثال تبديل NFA به DFA q0q2q1aaacbNFAeq1 , q2, q0ab , cq0eq1 , q2, q0ab , cq1 , q2پذيرشq1bbccbaaa , cDFAa , b, cq0

اسلاید 91: 3-9-4 ساخت NFA از عبارات با قاعدهقاعده اول = اجتماع1221q0ماشينM1ماشينM2L (M2) U L (M1)

اسلاید 92: مثال اجتماع دو عبارت با قاعدهاجتماع دو عبارت a و (aUb ) = b q0q012baq0ab1122

اسلاید 93: 3-9-4 ساخت NFA از عبارات با قاعدهقاعده دوم= الحاقq021ماشينM1ماشينM2الحاق L ( m1 ) , L ( M2) يا L(M1) L (M2)

اسلاید 94: مثال الحاق دو عبارت با قاعدهq0q0baq02baab يا a , b الحاق دو عبارت

اسلاید 95: 3-9-4 ساخت NFA از عبارات با قاعدهقاعده سوم- kelin star1q0 1ماشينM1L (M1) kelin star يا L (M1) *

اسلاید 96: مثال كلين استار يك عبارت باقاعده1q0 1a*aa* يا a كلين استار عبارت

اسلاید 97: مثال تشكيل NFA از عبارات باقاعده (a U b)*ab زبانq0q0baabq02 1baمرحله 1

اسلاید 98: مثال تشكيل NFA از عبارات باقاعدهمرحله 2(a U b) q0abمرحله 3(a U b)*q0ab

اسلاید 99: مثال تشكيل NFA از عبارات باقاعدهمرحله 4(a / b)*abشروعabپذيرش نهاييba

اسلاید 100: مثال يك الگو براي تحليل گر لغويالگوي تشخيص ساختار IF با كمك ماشين قطعي رقم يا حرف = Letter2135640پذيرش نهاييشروعIF()letterany

اسلاید 101: فصل چهارم: تحليل نحوياهداف رفتاري:دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد: تحليل گر نحوی و خطاهای نحوی گرامر و گرامر مستقل از متن تجزيه بالا به پايين و پايين به بالا تجزيه پيشگو گرامرهای LL(1)، LR، SLR و LALR

اسلاید 102: 4-1 فوايد گرامرها1- نمايش دقيق و قابل فهمي براي زبان2- امكان ايجاد پارسرهاي كارآمد با قابليت تشخيص ساختارهاي نحوي درست و دقيق3- ايجاد ساختاري مناسب براي زبان جهت ترجمه صحيح و آشكارسازي خطا توسط گرامر درست طراحي شده 4- سادگي اضافه نمودن ساختارهاي جديد به زبان

اسلاید 103: 4-2 تجزيه كنندهدريافت رشته اي از نشانه ها از تحليل گر لغوي و بررسي تعلق رشته به زبان توسط گرامرانجام بررسي طبق ساختارهاي نحوي زبان و هر مرحله گزارش خطاهاي نحوي به اداره كننده خطا رفع خطا براي پردازش ادامه ورودي بر اساس خطاهاي متداول

اسلاید 104: 4-2-1 تجزيه كننده- ارتباطاتموقعيت تجزيه كننده در مدل كامپايلرتحليل گر لغويجدول نمادتجزيه كننده (پارسر)باقيماندهجلوبندي كامپايلربرنامه مبداكد ميانيدرخت تجزيهنشانهدرخواست نشانه بعدي

اسلاید 105: 4-3 خطاي نحوي1- لغوي. مانند ديكته غلط شناسه ، كلمه كليدي يا عملگر2- نحوي. مانند عبارت محاسباتي با پرانتزهاي نامتعادل3- معنايي. مانند استفاده از عملگر با عملوندهاي ناسازگار4- منطقي. مانند فراخواني بازگشتي بي نهايتالف سطوح خطا

اسلاید 106: 4-3 خطاي نحويب- ويژگي اداره كننده خطاي نحوي توانايي گزارش حضور خطاها را با وضوح و با دقت پوشش هر خطا با سرعت كافي به جهت امكان آشكارسازي خطاهاي بعدي عدم كاهش بيش از حد سرعت پردازش برنامه هاي صحيح

اسلاید 107: 4-3 خطاي نحويج- استراتژي هاي پوشش خطاي نحوي-Panic Mode-Phrase level-Error production-Global correction

اسلاید 108: 4-3 خطاي نحوي Panic mode -روش كارويژگي- ساده ترين روش پوشش- قابل استفاده اكثر روشهاي تجزيه- وارد حلقه بي نهايت نمي شود.صرف نظر از يك نماد در هر مرحله تا زمان پيداشدن نشانه هماهنگ با زبان

اسلاید 109: 4-3 خطاي نحوي Phrase Level -ويژگيروش كار- استفاده از تصحيح موضعي - عدم ورود به حلقه بي نهايت با دقت در انتخاب جايگزيني - ضعف در برخورد با خطاهاي اصلي قبل از نقطه تشخيص قادر به تصحيح هر رشته وروديپيشوندي از باقيمانده ورودي را جايگزين رشته اي مي نمايد كه امكان ادامه تجزيه باشد.

اسلاید 110: 4-3 خطاي نحوي Error production - روش كاراضافه نمودن ساختارهاي مولد خطا به زبان از قبل تشخيص آنها در زمان تجزيه در رشته ورودي

اسلاید 111: 4-3 خطاي نحوي Global Correction -روش كار انتخاب الگوريتم هاي تصحيح خطا با قابليت ايجاد كمترين تغييرات در ورودي براي رفع خطارخ دادن حداقل تعداد درج ها، حذفها در رشته ورودي

اسلاید 112: 4-4 گرامر مستقل از متنG ( V , Σ , P , S) اجزاي گرامرقوانين : اعضاي مجموعه V * ( V U Σ )مجموعه متغيرها يا غير پايانه هاعنصر شروع گرامرعناصر پايانهويژگي زبان(اگر و تنها اگر  L S ( A  u ( A  V , u  ( U V ) +

اسلاید 113: 4-4-1 گرامر مستقل از متن - تعاريففرم جمله ايجملهزبانيك فرم جمله ايست اگر يك w (V U ) رشته وجود داشته باشد w به S اشتقاق از .يك جمله است اگر يك w* رشته وجود داشته باشد w به S اشتقاق از نشان مي دهند، مجموعه L(G ) كه با G زبان } است. w* {

اسلاید 114: 4- 4گرامر مستقل از متن نمونه اشتقاقهاي يك رشتهS  AAA  AAA bA Ab aababaa رشته S  AA  aA  aAAA  abAAA  abaAA  ababAA  ababaA ababaa S  AAََََ  AAAA  aAAA  abAAA  abaAA  ababAA  ababaA  ababaaS  AA  Aa  AAAa  AAbAa  AAbaa  AbAbaa  Ababaa  ababaaS  AA  aA  aAAA  aAAa  abAAa  abAbAa  ababAa  ababaa

اسلاید 115: مثال گرامرهاي مستقل از متنS  aSb aSbb S  aSdd AA  bAc bcS  aS aBB  bB bS  abScB B  bB bS  aSa aBaB  bB b

اسلاید 116: 4-5 عبارات باقاعده- دلايل استفاده براي نحو زبان1- عدم نياز به نمايش نوع قوي مانند گرامر براي توصيف قوانين ساده لغوي زبان 2- امكان نمايش مختصرتر و قابل فهم تري براي نشانه ها نسبت به گرامر3- ايجاد تحليل گرهاي لغوي كاراتر به صورت خودكار 4- راه مناسبي براي پيمانه سازي جلوبندي كامپايلر به دو بخش قابل مديريت با تقسيم ساختار زبان به لغوي و غيرلغوي

اسلاید 117: 4-6 تجزيه- نوع بالا به پايين 1- سعي در يافتن سمت چپ ترين اشتقاق براي رشته ورودي دارد.2- سعي در ساختن درخت تجزيه براي رشته ورودي با شروع از ريشه و ايجاد گره هاي درخت بصورت پيش ترتيبانواع پارسرهاي بالا به پايينLL (1) 1- گرامرهاي بدون عقبگرد 2- گرامرهاي با عقبگرد

اسلاید 118: 4-6 تجزيه- نوع بالا به پايينتجزيه كننده بازگشتي – كاهشي ( پيشگو)تهيه مجموعه اي از پايانه هايي كه در هر قانون براي يك غير پايانه در سمت راست ظاهر مي شوند.بررسي دنباله رشته ورودي بر طبق مجموعه بالابررسي بالا با مقايسه نماد پيش نگر در ورودي با عناصر مجموعه بالا

اسلاید 119: 4-6-1 تجزيه كننده پيشگو – پياده سازيايجاد نمودار انتقال1- حذف بازگشتي چپ در گرامر در صورت وجود2- ايجاد حال شروع و حالت نهايي براي گرامرAX1, X2,…,Xn 3- رسم يك مسير از حالت شروع به نهايي براي هر قانون به شكلX1,X2,…,Xn 4- دادن برچسب به لبه ها يا يالهاي مسير به صورت

اسلاید 120: مثال تجزيه كننده پيشگو- نمودار انتقالE  TE`E`  +TE`  T  FT`T`  * FT`  F  (E) id 0123456789مرحله 1مرحله 2مرحله 3E:FTE`T`E`:TTE`T:

اسلاید 121: مثال تجزيه كننده پيشگو- نمودار انتقال10111213مرحله 4TT`:FT`14151617مرحله 5(F:E)id

اسلاید 122: مثال تجزيه پيشگوS  cAdA  ab acad دنباله ورودي SAdcSAcdabSAdcba(الف)(ب)(پ)

اسلاید 123: 4-6-2 تجزيه كننده پيشگوي غير بازگشتيبخشهاي يك تجزيه كننده غير بازگشتيحاوي رشته ورودي براي تجزيه با علامت $ در انتهاي آندنباله اي از نمادهاي گرامر در هر لحظه براي تجزيه با $ در ته آن يك پايانه a يك غير پايانه و A،[A,a] آرايه دو بعدي عناصر ميانگير ورودي پشتهجدول تجزيهدنباله خروجيدنباله تجزيه شده تا آن زمان

اسلاید 124: 4-6-2 تجزيه كننده پيشگوي غير بازگشتيبرنامه تجزيه كننده پيشگو جدول تجزيه Mپشتهوروديخروجياشاره گر

اسلاید 125: 4-6-2 تجزيه غير بازگشتي پيشگو – عملكردباشد توقف تجزيه كننده اعلام خاتمه موفق تجزيه X= a = $ 1- اگر [A , a] يك غير پايانه باشد مراجعه به وارده در جدول X 3-اگر و جايگزيني قانون مناسب آن از جدولاز پشته ، انتقال اشاره گر ورودي به X خروج X= a  $ 2- اگر نماد بعدي در ورودي

اسلاید 126: مثال تجزيه كننده غير بازگشتي پيشگوE TMM +TM T FNN * FN F (E) id غير پايانهid+*)($EE`TT`FE  TE`E`  +TE`T  FT`T` * FT`F  idT`   E  TE`T  FT`F  (E)E`   T`   جدول تجزيه E  TE`E`  +TE`  T  FT`T`  * FT`  F  (E) id E`   T`  

اسلاید 127: مثال تجزيه كننده غير بازگشتي پيشگو$E$E`T$E`T`F$E`T`id$E`T`$E`$E`T$E`T$E`T``F$E`T`id$E`T`$E`T`F*$E`T`F$E`T`id$E`T`$E`$Id + id * id$Id + id * id$Id + id * id$Id + id * id$+id * id$+id * id$+id * id$Id * id$Id * id$Id * id$*id$*id$Id$Id$$$$E  TE`E +TE`T  FT`F  idT`  T`  * FT`E`  T  FT`F  idF  idT`  

اسلاید 128: 4-7 مجموعه Follow و First First هر رشته اي از نمادهاي گرامري باشد، مجموعه پايانه هايي a اگر رشته كه است.first (a) شروع مي شوند ، a رشته هاي مشتق شده ازآنها باFollowبلافاصله بعد از آن هستند. مجموعه اي از پايانهاست كه در هر شبه جملهA براي غير پايانه

اسلاید 129: 3- اگر قانونهايي بشكل A  EB يا A  EBF كه First (F) حاوي  باشد ( ) هر چيزي در مجموعه Follow(A) به Follow (B) اضافه مي شود.1- $ در Follow (S) قرار داده مي شود كه نماد شروع گرامر است و $ نماد انتهاي سمت راست رشته وروديست.2- اگر قانوني به صورت A  EBF وجود دارد آنگاه هرچيزي در First (F) بجز  به مجموعه Follow (B) اضافه مي شود.4-7-1 محاسبه Follow ( A)

اسلاید 130: 3- اگر X غيرپايانه و X  Y1Y2…Yn قانون گرامر، براي هر a ,i در مجموعه First(Yi) باشد و  در تمام مجموعه هاي First ( Y1)…First (Yn) قرار داشته باشد، a به مجموعه First (X) اضافه مي شود.1- اگر X پايانه باشد، First (X) برابرست با {X}2- اگر X   قانون گرامر باشد،  به First (X) اضافه مي شود.4-7-1 محاسبه First ( A)

اسلاید 131: مثال مجموعه هاي Follow و First First (E) = First (T) = First (F) = { ( , id }First (E`) = { + ,  }First (T`) = { * ,  }Follow (E) = Follow (E`) = { ) , $ }Follow (T) = Follow (T`) = { + , ) , $ }Follow (F) = { + , * , ) ,$ }E TMM +TM T FNN * FN F (E) id E  TE`E`  +TE`  T  FT`T`  * FT`  F  (E) id

اسلاید 132: 4-8 ايجاد جدول تجزيه3- اگر در First (E) باشد، A  a براي هر پايانهb در Follow (A) به M[A , b] اضافه شود. اگر  در First (E) و $ در Follow ( A) باشد، A  a به M [ A , $] اضافه شود.1- براي هر قانون از گرامر بصورت A  a مراحل 2 و 3 تكرار شود.2- براي هر پايانه a در مجموعه First (E)، A  E به M[A , a] اضافه شود.

اسلاید 133: مثال جدول تجزيهFirst (TE`) = First (T) = { ( , id}غير پايانهid+*)($EE  TE`E  TE`E  TE`E`  +TE`  T  FT`T`  * FT`  F  (E) id

اسلاید 134: 4-9 شناسايي گرامر LL(1)3- حداكثر يكي از E و Fمي توانند رشته تهي توليد كنند.4- اگر F   ، E رشته اي شروع شونده با پايانه هاي مجموعه Follow ( A) توليد نمي كند.1- گرامري كه ابهام يا بازگشتي چپ ندارد.2- اگرA  E F دو قانون از Gباشند براي هيچ پايانه اي مانند a، هر دوي Eو F رشته هاي شروع شونده با a توليد نمي كنند.

اسلاید 135: مثال گرامر LL (1)گرامر LL (1) است زيرا : First ( +TE`) = { + }, First (  ) , {  }  ( + ) =  First ( E` ) = { + ,  } , follow ( E` ) = { $ , ) } , { + ,  } { $ , ) } = First ( *FT) = { * } , First (  ) = {  } , { * }  {  } = First ( T`) = {  , * } , Follow ( T`) = { $ , ) , + } , { , * }  { $ , ) + } = First ((E)) { ( } , First ( id ) = { id } , { ( } { id } =  E  TE`E`  +TE`  T  FT`T`  * FT`  F  (E) id

اسلاید 136: گرامر LL (1) نيست.مثال گرامر LL (1)S  iEtSF 1S  a 2F  eS 3F  S 4E  b 5SFEiaetb$123 , 445جدول تجزيه

اسلاید 137: 4-10 پوشش خطا در تجزيه پيشگوكنار گذاردن نمادهاي ورودي بعدي تا زمان ظاهر شدن شناسه اي متعلق به مجموعه اي از شناسه هاي هماهنگ كننده 1- عدم تطابق پايانه موجود در بالاي پشته با نماد ورودي بعدي2- خالي بودن وارده جدول براي غير پايانهA در بالاي پشته و پايانه a بعنوان نماد ورودي بعدينوع خطاروش پوشش خطا

اسلاید 138: 4-10-1 انتخاب مجموعه هماهنگ كنندهگذاردن تمام نمادهاي Follow (A) در مجموعه هماهنگ كننده غير مجموعه پايانه و بررسي ورودي تا زمان ظاهر شدن يك عضو از آنگذاردن مجموعه نمادهاي شروع كننده ساختارهاي سطح بالاتر زبان به همراه مجموعه هماهنگ كننده ساختارهاي سطوح پايين تر زبان مانند كلمات كليدي به اضافه مجموعه Follow هاگذاردن مجموعه First (A) به مجموعه هماهنگ كننده غير پايانه A قانونهاي توليد كننده غير پايانه تهي براي غير پايانه هاي قادر به اشتقاق تهي1234

اسلاید 139: مثال بروز خطا در تجزيه پيشگو1- در صورت خالي بودن وارده جدول ، نماد ورودي حذف2- در صورت وروديsynch ( از مجموعه نشانه هاي هماهنگ كننده Follow ) خروج غير پايانه بالاي پشته براي امكان ادامه تجزيه3- در صورت عدم تطابق نشانه بالاي پشته با نماد ورودي ، خروج نشانه از پشته

اسلاید 140: مثال بروز خطا در تجزيه پيشگو)id + * id رشته ورودي داراي خطاي مرحله 1E  TE`E`  +TE`  T  FT`T`  * FT`  F  (E) id غير پايانهid+*)($EE`TT`FE  TE`E`  +TE`T  FT`T` * FT`F  idT`   E  TE`T  FT`F  (E)E`   T`   E`   T`  

اسلاید 141: مثال بروز خطا در تجزيه پيشگومرحله 2synchغير پايانهid+*)($EE`TT`FE  TE`E`  +TE`T  FT`T` * FT`F  idT`   E  TE`T  FT`F  (E)E`   T`   E`   T`   synchsynchsynchsynchsynchsynchsynchsynch

اسلاید 142: مثال بروز خطا در تجزيه پيشگو$E$E$E`T`$E`T`F$E`T`id$E`T`$E`T`F*$E`T`F$E`T`$E`$E`T+$E`T$E`T`F$E`T`id$E`T`$E`$)Id *+ id$Id *+ id$Id *+ id$Id *+ id$Id *+ id$*+ id$*+ id$+ id$+ id$+ id$+ id$id$Id$Id$$$$error , skip )id is in First ( E)Error M [F, + ] = synchF has been popedمرحله 3

اسلاید 143: 4-11 تجزيه بالا به پايين – انتقال كاهشسعي در ايجاد درخت تجزيه با شروع از برگها و رفتن به سمت ريشه = كاهشجايگزيني يك زيررشته خاص منطبق با سمت راست يك قانون با نماد سمت چپ همان قانون

اسلاید 144: مثال تجزيه بالا به پايين – انتقال كاهشS  aABeA  Abc bB  dabbcde دنباله ورودي abbcdeانتقال aAbcde كاهش aAdeانتقال aABeكاهش SS  aABe  aAde  aAbcde  abbcdeاشتقاق

اسلاید 145: 4-11-1 تجزيه انتقال كاهش - دستگيرهزير رشته اي منطبق بر سمت راست يك قانون و ايجاد كننده يك كاهش به غير پايانه سمت چپ آن قانون ويژگي دستگيرهزير رشته اي كه با عمل كاهش با توانايي هدايت تجزيه كنندهبه عنصر شروع گرامر

اسلاید 146: مثال دستگيرهabbcde دنباله ورودي abbcdeانتقال aAbcde كاهش aAdeانتقال aABeكاهش Sدستگيره هاA  b َA  AbcB  d S  aABeA  Abc bB  d

اسلاید 147: مثال دستگيره(1) E  E + E(2) E  E * E(3) E  ( E )(4) E  idگرامرسمت راست ترين اشتقاقE  E + E  E + E * E  E + E * id3  E + id2 * id3  id1 + id2 * id3مرحله 1

اسلاید 148: مثال دستگيرهدستگيره هاجملهدستگيرهid1 + id2 * id3E + id2 * id3E + E * id3E + E * Eid1 id2 id3E * E

اسلاید 149: 4-11-1-1 دستگيره- هرس نمودنتوانايي توليد معكوس سمت راست ترين اشتقاق مزيت هرس نمودنمراحل هرس نمودن1- اگر W جمله گرامر براي تجزيه باشد، آنگاه W = Yn شبه جمله راست n ام از سمت راست ترين اشتقاق نامشخص . 2- يافتن دستگيره Bn-1 درYn-1و كاهش آن تا بدست آمدن شبه جمله راست Yn-2.3- توقف عمليات در صورت رسيدن به عنصر شروع گرامر S

اسلاید 150: مثال هرس نمودن دستگيرهid1 + id2 * id3شبه جمله راستدستگيرهقانون كاهشيid1 + id2 * id3E + id2 * id3E + E * id3E + E * EE + EEid1 id2 id3E * EE + EE  idE  idE  idE  E * EE  E + E(1) E  E + E(2) E  E * E(3) E  ( E )(4) E  id

اسلاید 151: 4-11-2 مشكلات هرس نمودن دستگيره1- تعيين زير رشته مناسب براي كاهش در يك شبه جمله راست2- انتخاب قانون مناسب در موارد وجود دو يا بيشتر قانون با زير رشته يكسان در سمت راست

اسلاید 152: 4-12 تجزيه انتقال كاهش با پشتهاستفاده از پشته به منظور نگهداري نمادهاي گرامر استفاده از ميانگير ورودي جهت نگهداري رشته مورد نظر براي تجزيهروند تجزيه1- انتقال صفر يا چند نماد به پشته توسط تجزيه كننده2- ادامه مرحله 1 تا زمان پيدا شدن يك دستگيره در بالاي پشته3- كاهش دستگيره پيدا شده به سمت چپ قانون گرامري مناسب آن

اسلاید 153: 4-12-1 عمليات انتقال كاهش با پشتهخطاانتقالكاهشپذيرشانتقال نماد بعدي ورودي به بالاي پشتهوجود انتهاي سمت راست دستگيره در بالاي پشته و يافتن سمت چپ آن و تصميم گيري براي جايگزينياعلام تكميل موفقيت آميز عمل تجزيهتشخيص خطاي نحوي و فراخواني رويه پوشش خطا

اسلاید 154: مثال تجزيه انتقال كاهش با پشتهرشته id1 + id2 * id3(1) E  E + E(2) E  E * E(3) E  ( E )(4) E  idE  E + E  E + E * E  E + E * id3  E + id2 * id3  id1 + id2 * id3گرامر

اسلاید 155: مثال تجزيه انتقال كاهش با پشتهپشتهوروديعمل$$id1$E$E +$E + id2$E + E$E + E *$E + E * id3$ E + E * E$ E + E $Eid1 + id2 * id3 $+ id2 * id3 $+ id2 * id3 $id2 * id3 $* id3 $* id3 $id3 4$$$$ShiftReduce by E  idShiftShiftReduce by E  idShiftShiftReduce by E  idReduce by E  E * EReduce E  E + Eaccept

اسلاید 156: 4- 13 تجزيه انتقال كاهش – پيشوند قابل وقوعمجموعه پيشوندهاي شبه جملات راست ظاهر شونده در پشته يك تجزيه كننده انتقال كاهش ياپيشوندي از يك شبه جمله راست عبور نكننده از انتهاي راست سمت راست ترين دستگيره آن شبه جمله

اسلاید 157: 4-14 تجزيه انتقال كاهش- تناقض هاتناقض انتقال - كاهشتناقض كاهش كاهشترديد در عمل انتقال يا عمل كاهش در زمان تصميم گيري براي تجزيه كننده وجود چند قانون براي كاهش يك رشته در يك زمان

اسلاید 158: 4-14 تجزيه كننده عملگر اولويتگرامر نوع عملگر نداشته باشد.  1- قوانين2- در سمت راست قوانين توليد، هيچ كدام از دو پايانه كنار هم نباشند.

اسلاید 159: مثال عملگر اولويت – گرامر عملگرE  EAE ( E ) - E idA  + - / وجود دو غير پايانه در سمت راست قانونگرامر عملگر نيست

اسلاید 160: 4-14-1 نقطه ضعفهاي روش عملگر اولويتدشوار بودن اداره نمودن نشانه هايي مانند علامت منها با دو اولويت متفاوت ( دوديي يا يگاني)عدم اطمينان از نتيجه درست تجزيه به دليل رابطه نزديك بين گرامر زبان در حال تجزيه و تجزيه كننده عملگر اولويتقابليت تجزيه بر روي تنها رده كوچكي از گرامرها

اسلاید 161: 4-14-2 عملگر اولويت – تعيين اولويتهاتعريف 3 رابطه اولويت مجزاي بين هر زوج از پايانه ها مفهومرابطه اولويت a كمتر از b است. اولويت a بيش از b است. اولويت a و b يكسان است.a <. ba = ba . > b

اسلاید 162: 4-14-2 عملگر اولويت روشهاي تعيين اولويت1- استفاده از شركت پذيري و اولويت موجود بين خود عملگرها در زبان مانند اولويت هاي زير* .> + , + < . *2- ايجاد گرامر غير مبهمي براي زبان و درخت تجزيه آن با قابليت انعكاس شركت پذيري و اولويت صحيح بين عناصر پايانه در درخت

اسلاید 163: مثال عملگر اولويت – تعيين اولويتهاE  TE`E`  +TE`  T  FT`T`  * FT`  F  (E) id

اسلاید 164: 4-14-3 استفاده از اولويت ها 1- قرار دادن روابط اولويت بين پايانه ها در رشته ورودي به تجزيه2- قرار دادن علامت $ ابتدا و انتهاي رشته ورودي به همراه اولويت آن نسبت به اولين پايانه و آخرين پايانه رشته3- حذف غير پايانه ها از جمله ورودي4- پويش از انتهاي چپ رشته تا رسيدن به اولين اولويت >.

اسلاید 165: 4-14-3 استفاده از اولويت ها. > 6- تعيين دستگيره شامل هر چيزي در سمت چپ اولين راست 5. در مرحله < و سمت 5- پويش به عقب ( چپ ) از همان نقطه با پشت سرگذاردن هر = تا رسيدن به <.

اسلاید 166: مثال استفاده از اولويت هارشته ورودي به تجزيه id + id * id$ <. Id .> + <. Id .> * <. id .> $.مرحله 1:مرحله 2:زمان ديدن اولين >. از سمت چپ بين اولين id و +پويش به عقب ردشدن از روي = در صورت وجود برخورد با < اولين .

اسلاید 167: مثال استفاده از اولويت هامرحله 3:دستگيره بين اولين >. و .< يعني اولين id سمت چپ و تبديل آن به E مرحله 4:تشخيص ساير دستگيره هاي مشابه { id2 , id3 } و باقيمانده دنباله ورودي به شكل $ <. + < . * .> $ مرحله 5:دستگيره بعدي بين + و * و انتهاي راست آن بين * و $ يعنيE * E و تبديل به Eمرحله6:دستگيره بعدي بين + و $ يعني E + E و تبديل به E و پايان تجزيه انتقال كاهش – عملگر اولويت

اسلاید 168: 4-14-4 عملگر اولويت – اولويتهاي بديهي1- اگر عملگر A اولويت بيشتر از عملگر B داشته باشد، روابط A . > B و B <. A بين آنها برقرار است. 2- اگر A و B عملگرهاي با اولويت يكسان باشند، اگر هر دو شركت پذير از راست هستند: B <. A , A <. B و پركت پذير از چپ : B .> A , A .> B

اسلاید 169: 4-14-4 عملگر اولويت – اولويتهاي بديهي3- براي تمام عملگرهاي مانند A روابط زير برقرار است.$ <. A A .> $ A .> ) ) .> A ( <. AA <. ( id .> A A <. id4- روابط زير هميشه برقرارند:( = ) ( <. ( ( <. id$ <. ( id .> $ id .> ) $ <. id ) .> $ ) .> )..

اسلاید 170: مثال عملگر اولويت- جدول اولويتفرضيات ( توان ) بالاترين اولويت و شركت پذير از  1 - راست2- * و / بالاترين اولويت بعدي و شركت پذير از چپ3- + و – پايين ترين اولويت و شركت پذير از چپ

اسلاید 171: مثال عملگر اولويت - جدول اولويتجدول اولويت ها

اسلاید 172: 4-14-5 عملگر اولويت - توابع اولويت1- f( a ) <. g ( b ) هر گاه a <. b2- f( a ) = g ( b ) هر گاه a = b3- f( a ) .> g ( b ) هر گاه a .> bدو تابعf و g براي كدگذاري جدول اولويت براي پارسر

اسلاید 173: مثال عملگر اولويت - توابع اولويتجدول اولويت* < . Id f ( * ) < g( id )id .> id f ( id ) > g ( id )

اسلاید 174: مثال عملگر اولويت - گراف روابط اولويتf (*)f (id)g (+)f ($)g (id)g ($)g (*)f (+)

اسلاید 175: 4-14-5 تجزيه عملگر اولويت- پوشش خطاانواع خطا 1- عدم وجود رابطه بين عنصر بالاي پشته و عنصر ورودي2- عدم تطابق مجموعه عناصر پيمايش شده در پشته و آماده كاهش با هيچ كدام از قوانين گرامرپوشش خطادر حالت اول: قرار گرفتن اشاره گرهايي به توابع رفع خطا و فراخواني آنها هنگام وقوع خطا

اسلاید 176: 4- 15 تجزيه كننده هاي LRدلايل پر طرفداربودن تجزيه كننده هاي LR1- قابليت تشخيص ساختارهاي زبانهاي مستقل از متن2- عمومي ترين روش تجزيه انتقال كاهش غير بازگشتي3- توانايي تجزيه رده گرامرهاي قابل تجزيه پيش گو4- سريعترين تشخيص خطاي نحوي با پويش چپ به راست

اسلاید 177: 4-15-1 تجزيه LR- نقاط ضعف1-كار زياد در ساخت آن براي گرامر زبان بشكل دستي 2- نيازمند ابزار مولد تجزيه كننده LR براي ايجاد

اسلاید 178: 4-15-2 تجزيه LR- انواعLR ساده ياSLR LR متعارف يا CLR LR پيش نگر يا LALR ساده ترين كمترين تواناييقدرتمند ترينگرانترينقدرت متوسطهزينه متوسطكار كم براي ايجاد و قابليت تجزيه اكثر گرامرهاجدول تجزيه متفاوت

اسلاید 179: 4-15-3 تجزيه - LR اجزاءبرنامه تجزيهخروجي

اسلاید 180: 4-15-4 تصميم گيري تجزيه LRتصميم گيري الگوريتم در هر لحظهعنصر بالاي پشته(S) نشانه ورودي aعنصر پشتهرشته اي به شكل s0X1s1X2s2….Xmsmكه sm در بالاي پشته قرار دارد.يك نماد گرامريك حالت تجزيه

اسلاید 181: 4-15-5 تجزيه LR – جدول تجزيهاجزاي جدول تجزيهتابع عملكرد action تابع انتقالي goto ( دريافت يك حالت و نماد و توليد حالت جديد)action [sm , ai] جدول تجزيهm

اسلاید 182: 4-15-5 تجزيه LR – جدول تجزيهمقادير مختلف موجود جدول برايaction [ sm ,ai] sn = shiftacceptrn=reduceerror a روي پشته قرار داده و بعد n روي پشته مي رودانجام عمل كاهش با دستور n ام پشتهپايان موفق تجزيهخطاي نحوي

اسلاید 183: 4-15-6 تجزيه LR – روال تجزيه 1- قرار دادن رشته ورودي w به همراه علامت $ در انتهاي آن در ميانگير ورودي 2- گذاردن s0 در پشته به عنوان اوليه حالت 3- خواندن وارده جدول تجزيه براي [s0 , $] 4- اجراي عمل در نظر گرفته شده در جدول[ shift , reduce, accept , error]

اسلاید 184: 4-15-6 تجزيه LR – روال تجزيه5- اگر پپكربندي پشته در يك لحظه بصورت:6- با خواندن a نماد ورودي جاري و s حالت بالاي پشته مراجعه به جدول و انجام يك مورد :7- تبديل رشته روي پشته پس ازs Shift بصورت :S0 X1 s1 X2 s2….Xm sm , ai ai+1 …. an $Shift , reduceS0 X1 s1 X2 s2…Xm sm ai s, ai+1…an $

اسلاید 185: 4-15-6 تجزيه LR – روال تجزيه8- تبديل رشته روي پشته پس از A reduce بصورت:S0 X1 s1 X2 s2… Xm-r sm-r A s , ai ai+1… an $9- اعلام پايان موفق تجزيه با ديدنaccept در جدول10- فراخواني رويه پوشش خطا با ديدنerror

اسلاید 186: مثال تجزيه LR1 E  E + T2 E  T3 T  T * F4 T  F5 F  (E)6 F  idEFT$id+*)(01234567891011s51s423r2s7r2accs6r23r4r4r4r428s4s53r6r6r6r69s4s5s11s610s4s5r3r1r1r3r3r5r5r5s7r1r3r5actiongoto

اسلاید 187: مثال تجزيه LRتجزيهid * id + id پشتهوروديعمل جدول00 id 50 F 30 T 20 T 2 * 70 T 2 * 7 id 50 T 2 * 7 F 100 T 20 E 1 0 E 1 + 6 0 E 1 + 6 id 5 0 E 1 + 6 F 3 0 E 1 + 6 T 9 0 E 1id * id + id $*id + id $*id + id $*id + id $*id + id $+ id $+ id $+ id $+ id $id $$$$$s5r5r3s7s5r5r2r1s6s5r5r3r9acc

اسلاید 188: 4-15-7 تفاوت گرامر LL و LRتوانايي تشخيص وقوع سمت راست يك رشته با ديدن تمام آنچه كه از آن سمت راست مشتق شده ، با استفاده از K نماد پيش نگرگرامر LL(K)گرامر LR(K)توانايي تشخيص وقوع سمت راست تنها با ديدن اولينK نماد ازآنچه توسط سمت راست آن مشتق شده

اسلاید 189: 4-16 تجزيه SLRتعريف يك قلم مثال اقلام مختلف قانون A  XYZيك قلم براي LR قانوني از گرامر با يك نقطه در مكاني در سمت راست آنA  . XYZA  X .YZA  XY .ZA  XYZ.

اسلاید 190: 4-16 تجزيه SLR تقسيم بندي اقلاماقلام هستهاقلام غير هستهشامل قلم اوليهS`  S و تمام اقلامي كه نقطه آنها در انتهاي چپ نيست.اقلامي كه نقطه در انتهاي چپ است.

اسلاید 191: 4-16-1 تجزيه SLR-ايجاد قلمS  AaAbS  BbBaA  B  مرحله1: تعيين يك نقطه شروع براي گرامرS` SS  AaAbS  BbBaA  B  مرحله2: گذاردن نقطه در اولين مكان سمت راست قانونهاS` . SS  .AaAbS  .BbBaA  . B  .

اسلاید 192: 4-16-1 تجزيه SLR-ايجاد قلممرحله3: گذاردن نقطه در مكانهاي بعدي در سمت راست قانونهاS` S .S  A .aAbS  B .bBaS  Aa .AbS  Bb .BaA  .B  . S  AaA .bS  BbB .a S  AaAb .S  BbBa .

اسلاید 193: 4-16-2 تجزيه SLR- گروه اقلامگروه اقلام LR(0) يا گروه LR(0) متعارف فراهم كننده مبناي ساخت تجزيه كننده هاي SLRساخت به وسيله دو تابعclosure و goto به همراه گرامر افزوده

اسلاید 194: 4-16-2 تجزيه SLR- گروه اقلامتابع closure1- اضافه شدن هر قلم موجود در مجموعه اقلامI به مجموعهclosure 2- اضافه شدن قلم B  .K درصورت وجودA  M .BN درclosure و وجود قانون B  K در گرامر

اسلاید 195: مثال تجزيه SLR- گروه اقلامE` EE  E + T TT  T * F TF  (E) idClosure (I) = يك گروه قلم داده شده I ={ [E`  .E] } E`  .EE  .E + TE  .TT  .T * FT  .FF  .(E)F  id

اسلاید 196: 4-16-2 تجزيه SLR- اقلام معتبريك قلم به صورتA  B1.B2 براي پيشوند قابل وقوع MB1 معتبر است اگر:اشتقاقي به صورتS`  M A W  M B1B2 W وجود داشته باشد.**

اسلاید 197: مثال تجزيه SLR- اقلام معتبرE` EE  E + T TT  T * F TF  (E) idيك پيشوند قابل وقوع E + T *كه پس از خواندن آن رفتن به حالت I7I7:T  T * .FF  .(E)F  .idاقلام معتبر براي1234

اسلاید 198: 4-16-2 تجزيه SLR- گروه اقلامتابع goto(I , X )مجموعه closure بر روي مجموعه [A  Q X K] با شرط وجود A  [ Q . X K] در I .مجموعه اي از اقلام معتبر براي پيشوند قابل وقوع R X با وجود مجموعه اقلام معتبر براي R در I .يامجموعه اقلامنماد گرامر

اسلاید 199: مثال تجزيه SLR- گروه اقلام گروه قلم داده شدهI ={ [E`  E.] , [ E`  E. + T] } goto (I , +) = E  E + . TT  .T * FT  .FF  .(E)F  .idE` EE  E + T TT  T * F TF  (E) id

اسلاید 200: 4-16-2 تجزيه SLR- ايجادگروه اقلامLR(0)1- گذاردن closure { [ S`  .S ]} در مجموعه گروه C 2- براي هر مجموعه اقلام I در C و هر نماد مانندX انجام بده:2- 1- اگر goto ( I , X) تهي نيست و درC نيست انجام بده:2-1-1- goto ( I , X) را به C اضافه كن.عقبگرد، تا زماني كه هيچ مجموعه باي اضافه شدن نمانده

اسلاید 201: مثال تجزيه SLR- ايجادگروه اقلامI0:I1:I2:I3:E`  .EE  .E + TE  .TT  .T * FT  .FF  .(E)F  .idE`  E.E  E. + TE  T.T  T. * FT  F.I4:F  (.E)E  .E + TE  .TT  .T * FT  .FF  .(E)F  .idI5:F  id.E` EE  E + T TT  T * F TF  (E) id

اسلاید 202: مثال تجزيه SLR- ايجادگروه اقلامI6:I7:E  E + .TT  .T * FT  .FF  .(E)F  .idT  T * .FF  .(E)F  .idI8:F  (E.)E  E. + TI9:E  E + T.T  T. * FI10:T  T * F.I11:F  (E).E` EE  E + T TT  T * F TF  (E) id

اسلاید 203: مثال تجزيه SLR- ايجادگروه اقلامS` SS  L=R RL  * R idR  LI0:I1:I2:I3:I4:I5:I6:I7:I8:I9:S`  .SS`  S.R  L.=RR  L.S  R.L  *.RL  id.S  L=.RL  *R. R  L.S  L=R.

اسلاید 204: 4-16-2 تجزيه SLR- ايجاد جدول تجزيه1- ايجاد گروه مجموعه هاي اقلام براي گرامر افزوده G` ( با يك نقطه شروع مانند S` ) بصورت C = { I0 , I1 ,…In } 2- ساختن حالت i از Ii ( مانند I2)، تعيين action هاي تجزيه براي حالتi بصورت زير:الف- action [i , a] = shift j در صورت وجود [A  Q .aK] در Ii وgoto (Ii , a )=Ij ب- قرار گرفتن action [i , a] = reduce A Q براي تمام پايانه هاي a در Follow (A =S`) صورت وجود [A  Q.] در Iiپ- قرار گرفتن action [i , $] =acceptصورت وجود [S`  S.] در Ii

اسلاید 205: 4-16-2 تجزيه SLR- ايجاد جدول تجزيه3 - ايجاد تغيير حالتهايgoto براي حالتi و براي تمام غير پايانه هاي A با استفاده از قانون : اگر=Ij ) goto ( Ii , Aآنگاه goto ( I , A ) = j 4– گذاردنerror براي تمام ورودي هاي تعريف نشده با قوانين 2 و 3 الگوريتم5 - ايجاد حالت اوليه تجزيه كننده با استفاده از مجموعه اقلام حاوي [S`  .S]

اسلاید 206: مثال تجزيه SLR- ايجاد جدول تجزيهI0:E` .EE  .E + TE  .TT  .T * FT  .FF  .(E)F  .idمرحله 1action [ 0 , ( ] = shift 4action [ 0 , id] = shift 5 no actionI1:E` E.E  E. + Tمرحله 2action [ 1 , + ] = shift 6action [ 1, $ ] = acceptE` EE  E + T TT  T * F TF  (E) id

اسلاید 207: مرحله 3مثال تجزيه SLR- ايجاد جدول تجزيهFollow (E) = { $ , +, ) }action [ 2 , $ ] = action [ 2 , + ]=action [ 2 , ) ] = reduce E Taction [ 2 , * ] = shift 7I2:E  T.T  T. * F...ادامه مراحل مطابق نمونه ها.

اسلاید 208: 4-17 تجزيه CLR- تعريف قلم[A Q.K , a]شكل عمومي يك قلم كه A  QK يك قانون در گرامر و aيك پايانه يا علامت انتهاي سمت راست رشته ورودي ($) .اعلام كاهش با Q در زمان مشاهده a به عنوان نماد ورودي بعديعملكرد

اسلاید 209: 4-17 تجزيه CLR-پيشوند قابل وقوع شرايط قلم معتبر [A  Q.K , a] براي يك پيشوند قابل وقوع y1- وجود اشتقاق S  &AW  &QKW كه: y = &Q ويا a اولين نماد W يا W برابر تهي و a برابر $**

اسلاید 210: 4-17 تجزيه CLR- ايجاد مجموعه اقلامLR(1)1- براي هر قلم مثل [A  Q.BK , a] در مجموعه I انجام بده :براي قانونهاي مانندB  y در گرامر و هر پايانه مانندb درFirst (K) : اگر قلم [B  .y , b] در I نيست آنرا اضافه كنبرگشت به مرحله 1 اگر قلمي باقيماندهمحاسبه closure

اسلاید 211: 4-17 تجزيه CLR- ايجاد مجموعه اقلاممحاسبه goto J را مساوي مجموعه قلمهاي [A  QX.K , a] كه در I موجودند، در نظر بگير closure ( J) را برگردان.

اسلاید 212: 4-17 تجزيه CLR- ايجاد مجموعه اقلاممحاسبه item (G`)C= { closure ( { S`  .S , $ }) } قرار ده و تكرار كن :براي هر مجموعه از اقلام I در C و هر نماد گرامر مانندX :اگر goto ( I , X) تهي نبوده و در C نيست انجام بده:goto ( I , X) را به C اضافه كن.برگشت اگر قلمي باقيمانده

اسلاید 213: مثال تجزيه CLR- ايجاد مجموعه اقلامS` SS  CCC  cC dS` .S , $S  .CC , $C  .cC , c dC  .d , c dI0I1S`  S. , $I2S  C.C , $C  .cC , $C  .d , $I3C  c.C , c dC  .cC , c dC  .d , c dI4C  d. , c dI5S  CC. , $

اسلاید 214: مثال تجزيه CLR- ايجاد مجموعه اقلامI9I8I7C  d. , $C  cC. , c dC  cC. , $خاتمه كار بدليل نتيجه ندادن ساير اقلام. I6C  c.C , $C  .cC , $C  .d , $

اسلاید 215: مثال تجزيه CLR- ايجاد مجموعه اقلامI0I1I3I2I4I6I5I7I8I9SCCCCccccddddگراف goto براي مثال

اسلاید 216: 4-17 تجزيه CLR- ساخت جدول تجزيه1- ساخت گروه مجموعه هاي اقلام به صورت C = { I0 , I1 , …, In} براي G`2- ايجاد حالت i از تجزيه كننده با استفاده ازI و مقداردهي بخش action بصورت زير:الف- action [ I , a ] = shift j در صورت وجود [ A  Q.aK , b] در Ii وgoto(Ii , a) = Ij ب- reduce A a action [ I , a ] =درصورت وجود [A  Q. , a] در Ii و A = S`

اسلاید 217: 4-17 تجزيه CLR- ساخت جدول تجزيهپ- action [ i , $]= accept در صورت وجود [S`  S. , $] درIi 3- goto ( i , a) = j اگر goto ( Ii , A ) = Ij 4- قرار گرفتنerror براي تمام ورودي هاي تعريف نشده با قوانين 2 و3 الگوريتمقرار دادن حالت اوليه تجزيه كننده مساوي حالت بدست آمده از مجموعه حاوي [S`  .S , $]

اسلاید 218: مثال تجزيه CLR- ساخت جدول تجزيه1 S` S2 S  CC3 C  cC dSC$0123456789s312accr38s7s6s6r1r3actiongoto59dcs4s3s4r3s7r2r2r2

اسلاید 219: 4-18 تجزيه LALR- ساخت جدول تجزيه1- ايجاد گروه مجموعه هاي اقلام بصورت C= { I0 , I1 , … In}2- پيدا كردن تمام مجموعه هايي با قلم هسته يكسان در بين قلمهاي موجود3- ايجاد مجموعه نتايج اقلام موجود بصورت C= { J0 , J1 , …Jn} و محاسبه actionالف- action [ I , a ] = shift j در صورت وجود [ A  Q.aK , b] در Ii وgoto(Ii , a) = Ij

اسلاید 220: 4-18 تجزيه LALR- ساخت جدول تجزيه ب- reduce A  a action [ I , a ] =درصورت وجود [A  Q. , a] در Ii و A = S` پ- action [ i , $]= accept در صورت وجود [S`  S. , $] درIi 4- ساخت جداول goto بصورت زير:الف اگرJ اجتماع يك يا چند مجموعه اقلام ( I0 I1…Ik ) باشد، آنگاه قلمهاي هسته goto ( I1,X), goto (I2,X),…goto (Ik,X)مشابه هستند.

اسلاید 221: 4-18 تجزيه LALR- ساخت جدول تجزيهب اگر K اجتماع تمام مجموعه اقلام ( I0 I1…Ik ) باشد كه دراي قلمهاي هسته مانند goto(I1, X) هستند، goto (J,X)=X

اسلاید 222: مثال تجزيه LALR- ساخت جدول تجزيه1 S` S2 S  CC3 C  cC dادغام مجموعه هاي اقلام و جايگزين شدن با اجتماعشانI3 , I6C  c.C , c d $C  .cC, c d $C  .d , c d $I4 , I7C  d. , c d $I8 , I9C  cC. , c d $

اسلاید 223: مثال تجزيه LALR- ساخت جدول تجزيهSC$0123647589s3612accr389s47s36r1r3actiongoto5dcs47s36s47r3r2r2r2

اسلاید 224: مثال پوشش خطا در تجزيه LR و LALRبرخورد با خطا در تجزيه LR ورودي داراي خطاي ccd$0 c 3 c 3 d 4پشتهآشكارسازي خطاتشخيص خطا در يك مرحله

اسلاید 225: برخورد با خطا در تجزيه LALR مثال پوشش خطا در تجزيه LR و LALRورودي داراي خطاي ccd$0 c 36 c 36 d 47پشتهactiongoto[47,$]= r3 C  d[89,$]=r2 C  cC.0 c 36 c 36 C 890 c 36 C 89….0 C 2آشكارسازي خطاتشخيص خطا پس از چند كاهش

اسلاید 226: 4-18 تجزيه LALR- ساخت جدول تجزيه بهينهچند اصلاح در الگوريتم ساخت جدول تجزيه 1- نشان دادن مجموعه اي از اقلام I با هسته آن2- بدست آوردن بخش تابع action تنها بوسيله هسته3- نحوه محاسبه تغيير حالتهاي goto با استفاده از هسته

اسلاید 227: 4-18 تجزيه LALR- تعيين پيش نگرها3- اگر [A  M.XN , a] درJ` نبوده و a = # J` := closure ({[B  y.v , #]})2- 1- براي هر قلم مانند B  y.V در مجموعه هسته يا K انجام بده:4- توليد نماد پيش نگرa براي قلم A  MX.N در goto ( I , X)

اسلاید 228: 4-18 تجزيه LALR- تعيين پيش نگرها5 -اگر [A  M.XN , #] در مجموعه J` نيست، پيش نگرها ازB  y.v در مجموعه I به A  MX.N در goto ( I , X) انتشار مي يابند.

اسلاید 229: 4-18 LALR- محاسبه هسته هاي گروه اقلام1- ساختن هسته اقلامLR بخش تجزيه LR) 2-اجراي الگوريتم تعيين پيش نگر بر روي هسته هرمجموعه از اقلامLR و نماد گرامرX 3- تشكيل و مقداردهي جدول معين كننده پيش نگرها كه براي هر قلم هسته در هر مجموعه اقلام 4- تكرار چند گذر بر روي هر مجموعه اقلام

اسلاید 230: 4-18 LALR- محاسبه هسته هاي گروه اقلام 5- مراجعه به آن دسته اقلام هسته كه i پيش نگرهاي خود را منتشر مي سازد، هنگام مشاهده هر قلم. 6- استفاده از اطلاعات ثبت شده توسط مرحله 2 و اضافه نمودن مجموعه جاري پيش نگرها براي i به پيش نگرهايي مرحله قبل 7- تكرار مرحله 4-6

اسلاید 231: مثال LALR- محاسبه هسته هاي گروه اقلاممرحله 1 : بدست آوردن اقلام LRS` SS  L=R RL  * R idR  LI0:I1:I2:I3:I4:I5:I6:I7:I8:I9:S`  .SS`  S.R  L.=RR  L.S  R.L  *.RL  id.S  L=.RL  *R. R  L.S  L=R.

اسلاید 232: مثال LALR- محاسبه هسته هاي گروه اقلاممرحله 2 : اجراي الگوريتم محاسبه پيش نگرهاS .S , #S  .L=R , #S  .R , #L  .*R , # =L  .id , # =R  .L , #Closure ( {[S`  .S , #]})

اسلاید 233: مثال LALR- محاسبه هسته هاي گروه اقلاممرحله 3 : انتشار پيش نگرها در بين اقلام هستهازبهI0:I1:I2:I3:I4:I5:S`  .SS`  S.R  L.=RR  L.S  R.L  *.RL  id.I2:R  L.=RI6:S  L=.R

اسلاید 234: مثال LALR- محاسبه هسته هاي گروه اقلامازبهI4:I5:L  *.RL  id.I6:S  L=.RI4:L  *.RI7:I8:L  *R. R  L.I4:I5:L  *.RL  id.I8:R  L.I9:S  L=R.

اسلاید 235: مثال LALR- محاسبه هسته هاي گروه اقلاممرحله 4 : مقداردهي جدول پيش نگرها و انجام گذرها I1:I2:I2:I3:I4:S`  S.R  L.=RS  R.L  *.RL  id.I5:I6:S  L=.RI7:I8:L  *R. R  L.I0:S`  .SR  L.قلم مجموعهپيش نگرهاINITPASS1PASS2PASS3$$$$$$$$$$$$$$$$=$=$=$=$=$=$$$=$=$=$=$I9:S  L=R.$====

اسلاید 236: 4-18 LALR- فشرده سازي جدولفشرده سازي جدول actionفشرده سازي فيلدaction و ايجاد يك ليست حالت براي آنمشابه بودن سطرهاي زيادي از جدول action

اسلاید 237: مثال LALR- فشرده سازي جدول1 E  E + T2 E  T3 T  T * F4 T  F5 F  (E)6 F  idEFT$id+*)(01234567891011s51s423r2s7r2accs6r23r4r4r4r428s4s53r6r6r6r69s4s5s11s610s4s5r3r1r1r3r3r5r5r5s7r1r3r5actiongotoمرحله 1

اسلاید 238: مثال LALR- فشرده سازي جدولمرحله 2 مساوي بودن بخش action براي حالت هاي 0,4,6,7عمل نمادId s5( s4any errorتبديل به ليست مشابهي براي حالت 1تبديل بهعمل نماد+ s6$ accany error

اسلاید 239: مثال LALR- فشرده سازي جدولمرحله 3جايگزيني وارده هاي خطا در حالت2 عمل نماد * s7 any r2تبديل بهجايگزيني وارده هاي خطاي حالت 3عمل نمادany r4تبديل به مساوي بودن بخش action براي حالت هاي 5,10,11 و ادغام آنها

اسلاید 240: مثال LALR- فشرده سازي جدولمرحله 4جايگزيني وارده هاي حالت 8جايگزيني وارده هاي حالت 9عمل نماد * s6 ) s11any errorتبديل بهعمل نمادتبديل به * s7 any r1

اسلاید 241: 4-19 وقوع خطا در تجزيه LRتشخيص خطا تنها با مراجعه به جدول actionاعلام خطا به محض نيافتن ادامه مناسب براي ورودي در حال پويشعدم كاهش دنباله روي پشته عدم ورود نماد ايجاد كننده خطا به پشته

اسلاید 242: 4-20 پويش خطا در تجزيه LRروش panic mode1- پويش پشته به پايين تا يافتن حالت s با goto با پايانه خاص A2- صرف نظر از يك يا چند نماد ورودي تا يافتن نماد دقيقا مناسب براي A3- انتقال حالت goto [s , A] به پشته و ادامه تجزيه

اسلاید 243: 4-20 پويش خطا در تجزيه LRروش Phrase level1- آزمايش هر وارده خطا در جدول تجزيه2- تصميم گيري در مرورد منشاء بروز خطا3- ايجاد رويه پوششي مناسب براي خطا

اسلاید 244: 4-21 توليد كننده تجزيه كننده - Yaccروش ايجاد مترجم توسط Yacc1- آماده شدن پرونده اي حاوي مشخصه مترجم براي Yacc2- تبديل محتواي پرونده به برنامه در زبان C3- كامپايل برنامه توليدي همراه كتابخانه برنامه تجزيهLR 4- خروجي: برنامه تجزيه كنندهكامپايلر Yaccكامپايلر C مشخصه :translate.yy.tab.ca.outy.tab.cوروديخروجي(تجزيه كننده)a.out

اسلاید 245: 4-21-1 - Yaccاجزاي برنامهاعلان هاقوانين ترجمهروالهاي حاميc بخش هاي برنامه مبدا Yaccترتيب در متن برنامه مبدا Yaccاعلان هاقوانين ترجمهروالهاي حاميc%%%%

اسلاید 246: 4-21-1 - Yaccاعلانبخش اعلان برنامهاعلان هاي معمول در c و محصور بين %} , %{ اعلان لغات موقتاعلان نشانه هاي گرامر

اسلاید 247: 4-21-2 - Yaccقوانين ترجمهبخش قوانين ترجمه بلافاصله پس از %%مولد يا قانونعمل معنايي< سمت چپ > : <انتخاب 1 > {عمل معنايي 1}: <انتخاب 2 > {عمل معنايي 2 } : <انتخاب 3 > {عمل معنايي 3 }...