Position

Report
‫به نام خدا‬
‫‪1‬‬
‫طراحی‬
‫کامپایلرها‬
‫‪40-414‬‬
‫مدرس‪ :‬غالمرضا قاسم‌ثانی‬
‫برگردان فارس ی اسالیدها‪ :‬شایان افراسیابی‬
‫درباره‌ی درس‬
‫‪ o‬منبع اصلی‬
‫‪Compilers: Principles,‬‬
‫‪Techniques & Tools,‬‬
‫‪2nd ed., Aho, Lam, Sethi,‬‬
‫‪and Ullman, 2007‬‬
‫‪ o‬ارزیابی‬
‫‪1‬‬
‫مورد‬
‫درصد‬
‫نمره (از ‪)20‬‬
‫امتحان میان‌ترم‬
‫‪%35‬‬
‫‪7‬‬
‫امتحان پایان‌ترم‬
‫‪%35‬‬
‫‪7‬‬
‫تمرین‌ها و کوئیزها‬
‫‪%10‬‬
‫‪2‬‬
‫پروژه عملی‬
‫‪%20‬‬
‫‪4‬‬
‫آموزش درس کامپایلر‬
‫‪ o‬آیا موضوعی قدیمی نیست؟‬
‫‪‬‬
‫بله‪ ،‬و به خوبی تبیین شده است‬
‫‪‬‬
‫الگوریتم‌ها‪ ،‬روش‌ها‪ ،‬و تکنیک‌های آن در مراحل اولیه‌ی شکل‌گیری‌ علوم کامپیوتر طراحی‬
‫شده‌اند‬
‫‪‬‬
‫کامپایلر وجود دارد‪ ،‬و‬
‫‌‬
‫در حال حاضر تعداد زیادی‬
‫‪‬‬
‫کامپایلر تولید می‌کنند‬
‫‌‬
‫تعداد زیادی ابزار که به صورت خودکار‬
‫‪ o‬پس چرا باید این درس را بخوانیم؟‬
‫‪‬‬
‫‪‬‬
‫‪2‬‬
‫ً‬
‫کامپایلر کامل را خودتان نمی‌سازید‪ ،‬اما‬
‫‌‬
‫با وجودی که احتماال هیچ‌وقت یک‬
‫ً‬
‫مثال‪:‬‬
‫تکنیک‌هایی که در این درس می‌آموزید کاربردهای زیادی دارند؛ ‌‬
‫•‬
‫ساخت مفسر برای زبان‌های اسکریپتی‬
‫•‬
‫اعتبارسنجی (‪ )validation‬فرم‌ها‬
‫•‬
‫و غیره‬
‫اصطالحات‬
‫‪ o‬کامپایلر‬
‫‪‬‬
‫ً‬
‫برنامه‌ای که یک برنامه‌ی «قابل اجرا» به زبان مبدأ (معموال زبانی سطح باال) را به‬
‫ً‬
‫برنامه‌ی «قابل اجرای» معادل به زبان مقصد (معموال زبانی سطح پایین) ترجمه می‌کند‬
‫‪ o‬مفسر (‪)Interpreter‬‬
‫‪‬‬
‫برنامه‌ای که یک برنامه‌ی قابل اجرا را می‌خواند و نتایج حاصل از اجرای آن را تولید‬
‫می‌کند‬
‫‪‬‬
‫ً‬
‫این کار معموال به معنی «اجرای» برنامه است‬
‫ً‬
‫‪ o‬این درس عمدتا درباره‌ی کامپایلرهاست‪ ،‬ولی در بسیاری از موارد‪ ،‬همین‬
‫مباحث برای مفسرها هم مطرح می‌شود‬
‫‪3‬‬
‫یک کامپایلر‬
‫برنامه‌ی‬
‫مقصد‬
‫کامپایلر‬
‫برنامه‌ی‬
‫مبدأ‬
‫خطاها‬
‫خروجی‬
‫‪4‬‬
‫برنامه‌ی‬
‫مقصد‬
‫ورودی‬
‫یک مفسر‬
‫برنامه‌ی‬
‫مبدأ‬
‫خروجی‬
‫مفسر‬
‫ورودی‬
‫‪ o‬ترجمه‌ی خط به خط برنامه‬
‫‪ o‬اجرای بالفاصله‌ی هر خط ترجمه‌شده‬
‫‪5‬‬
‫‪ o‬اجرا کندتر است زیرا ترجمه تکرار می‌شود‬
‫ً‬
‫‪ o‬ولی معموال خطاها را نسبت به کامپایلر بهتر تشخیص می‌دهد‬
‫یک کامپایلر ترکیبی (‪)Hybrid‬‬
‫خطاها‬
‫مترجم‬
‫برنامه‌ی‬
‫مبدأ‬
‫برنامه‌ی‬
‫میانی (‪)IR‬‬
‫خروجی‬
‫‪6‬‬
‫ماشین مجازی‌‬
‫ورودی‬
‫دسته‌بندی کامپایلرها‬
‫‪ o‬از لحاظ ساخت‪:‬‬
‫‪‬‬
‫تک‌گذره‬
‫‪‬‬
‫چندگذره‬
‫‪ o‬از لحاظ نوع کد تولیدشده‪:‬‬
‫‪7‬‬
‫‪‬‬
‫مطلق (مثل ‪).com‬‬
‫‪‬‬
‫قابل جابه‌جایی (مثل ‪).exe‬‬
‫مراحل کامپایل‬
‫برنامه‌ی مبدأ‬
‫تحلیلگر لغوی‌‬
‫تحلیل‬
‫تحلیلگر نحوی‌‬
‫تحلیلگر معنایی‬
‫مدیریت‬
‫جدول‬
‫عالیم‬
‫تولیدکننده کد میانی‬
‫بهینه‌ساز کد‬
‫ساخت‬
‫تولیدکننده‌ی کد‬
‫بهینه‌سازی جزیی‬
‫‪8‬‬
‫برنامه‌ی مقصد‬
‫‪1‬‬
‫‪2‬‬
‫‪3‬‬
‫‪4‬‬
‫‪Front‬‬‫‪End‬‬
‫مدیریت‬
‫خطا‬
‫‪5‬‬
‫‪6‬‬
‫‪7‬‬
‫‪Back‬‬‫‪End‬‬
‫تقسیم به ‪ Front-End‬و ‪Back-End‬‬
‫کد‬
‫مقصد‬
‫‪Back‬‬‫‪End‬‬
‫کد میانی‬
‫(‪)IR‬‬
‫‪Front‬‬
‫‪-End‬‬
‫خطاها‬
‫‪ o‬نگاشت کد مبدأ به کد میانی در ‪Front-End‬‬
‫‪ o‬نگاشت کد میانی به کد مقصد در ‪Back-End‬‬
‫‪ o‬ساده‌سازی پرداخت کد و تغییر کد مقصد (‪)retargeting‬‬
‫‪9‬‬
‫‪ o‬امکان وجود چند ‪Front-End‬‬
‫کد مبدأ‬
‫‪)1( Front-End‬‬
‫تحلیلگر‬
‫نحوی‌‬
‫درخت‬
‫تحلیل‬
‫تحلیلگر‬
‫لغوی‌‬
‫نشانه‌ها‬
‫کد مبدأ‬
‫خطاها‬
‫‪ o‬تحلیلگر لغوی‌‬
‫‪‬‬
‫نگاشت نویسه‌ها به مجموعه‌ای از «نشانه‌ها» ‪ -- )Tokens(-‬واحد پایه‌ی نحو‬
‫‪y‬‬
‫‪10‬‬
‫‪id‬‬
‫‪+‬‬
‫‪x‬‬
‫‪id‬‬
‫‪x‬‬
‫=‬
‫‪x=x+y‬‬
‫‪id‬‬
‫‪‬‬
‫مثالی از نشانه‌ها‪:‬‬
‫‪‬‬
‫حذف فاصله‌ها (‪ tab‬ها‪ ،‬فضاهای خالی‪ ،‬و توضیحات)‬
‫•‬
‫ساخت دستی تحلیلگر لغوی به جای استفاده از ابزارهای خودکار (مثل ‪ )LEX‬ممکن است‬
‫‪end‬‬
‫برای افزایش سرعت الزم باشد‬
‫‪do‬‬
‫‪/‬‬
‫*‬
‫‪-‬‬
‫‪+‬‬
‫‪id‬‬
‫‪num‬‬
‫‪)2( Front-End‬‬
‫درخت‬
‫تجزیه‬
‫تحلیلگر‬
‫نحوی‌‬
‫نشانه‌ها‬
‫تحلیلگر‬
‫لغوی‌‬
‫خطاها‬
‫‪ o‬تحلیلگر نحوی‌‬
‫‪11‬‬
‫‪‬‬
‫تشخیص نحو «مستقل از متن»‬
‫‪‬‬
‫هدایت تحلیل وابسته به متن‬
‫‪‬‬
‫ساخت کد میانی (‪)IR‬‬
‫‪‬‬
‫تولید پیغام های خطاهای با معنا‬
‫‪‬‬
‫تالش برای اصالح خطا‬
‫‪‬‬
‫ابزارهایی مثل ‪ YACC‬می‌توانند فرآیند ساخت آن را خودکار کنند‬
‫کد مبدأ‬
‫‪)3( Front-End‬‬
‫‪ o‬برای توصیف نحو زبان‌های برنامه‌سازی از گرامرهای مستقل از متن‬
‫استفاده می‌شود‬
‫‪12‬‬
‫>‪::= <expr> <op> <term> | <term‬‬
‫>‪<expr‬‬
‫>‪::= <number> | <id‬‬
‫>‪<term‬‬
‫‪::= + | -‬‬
‫>‪<op‬‬
‫‪)4( Front-End‬‬
‫‪ o‬تجزیه‌گر نحوی سعی‬
‫می‌کند یک برنامه را به‬
‫‪x+2-y‬‬
‫اجزای نحوی تعریف‌شده‬
‫‪expr‬‬
‫در گرامر تقسیم کند‬
‫‪ o‬تجزیه نحوی یا پارس را‬
‫‪term‬‬
‫‪expr‬‬
‫‪op‬‬
‫می‌توان در قالب یک‬
‫درخت تجزیه ( ‪Parse‬‬
‫‪ )Tree‬و یا درخت نحو‬
‫‪x‬‬
‫‪id‬‬
‫‪-‬‬
‫‪term‬‬
‫‪op‬‬
‫‪expr‬‬
‫‪2‬‬
‫‪num‬‬
‫‪+‬‬
‫‪term‬‬
‫( ‪ )Syntax Tree‬نمایش داد‬
‫‪x‬‬
‫‪13‬‬
‫‪id‬‬
‫‪)5( Front-End‬‬
‫‌تر در قالب درخت انتزاعی‬
‫‪ o‬درخت پارس را می‌توان به صورت فشرده ‌‬
‫نحو (‪ )Abstract Syntax Tree‬نمایش داد‬
‫‪o‬‬
‫‪ AST‬می‌تواند به عنوان ‪ IR‬بین ‪ Front-End‬و ‪ Back-End‬به کار رود‬
‫‬‫‪y‬‬
‫‪x+2-y‬‬
‫‪14‬‬
‫‪+‬‬
‫‪id‬‬
‫‪2‬‬
‫‪num‬‬
‫‪x‬‬
‫‪id‬‬
‫‪)1( Back-End‬‬
‫کد‬
‫مقصد‬
‫انتخاب‬
‫دستور‌‬
‫تخصیص‬
‫ّثبات‬
‫‪IR‬‬
‫خطاها‬
‫‪ o‬ترجمه‌ی کد میانی (‪ )IR‬به کد مقصد‬
‫‪ o‬انتخاب دستور مناسب برای هر عمل در ‪IR‬‬
‫‪ o‬تصمیم‌گیری در مورد آن‌چه در هر لحظه باید در ّثبات‌ها ذخیره شود‬
‫‪15‬‬
‫‪)2( Back-End‬‬
‫کد‬
‫مقصد‬
‫بهینه‌سازی‬
‫جزیی‬
‫تولید کد‬
‫خطاها‬
‫‪ o‬تولید کد فشرده و سریع‬
‫‪ o‬استفاده از انواع آدرس‌دهی های موجود‬
‫‪16‬‬
‫‪IR‬‬
‫‪)3( Back-End‬‬
‫کد‬
‫مقصد‬
‫بهینه‌سازی‬
‫جزیی‬
‫تولید کد‬
‫خطاها‬
‫‪ o‬منابع محدود‬
‫‪ o‬دشواری تخصیص بهینه‌ی منابع‬
‫‪17‬‬
‫‪IR‬‬
‫بخش تحلیل در فرآیند کامپایل‬
‫‪ o‬شامل سه مرحله‪:‬‬
‫‪ ‬تحلیل لغوی‌‬
‫• پیمایش چپ به راست کد برنامه برای شناسایی نشانه‌ها (یک‬
‫نشانه‪ ،‬توالی‌ای از نویسه‌هاست که در کنار هم معنا دارند)‬
‫ی‬
‫‪ ‬تحلیل نحو ‌‬
‫• گروه‌بندی نشانه‌ها در دسته‌های بامعنا‬
‫‪ ‬تحلیل معنایی‬
‫• بررس ی صحت اجزای به‌دست‌آمده‬
‫‪18‬‬
‫ی‬
‫مرحله او ‌ل‪ :‬تحلیل لغو ‌‬
‫‪ o‬ساده‌ترین تحلیل‬
‫‪ o‬شناسایی نشانه‌ها که پایه‌ای‌ترین واحدهای سازنده هستند‬
‫‪Position := initial + rate * 60‬‬
‫نشانه‌ها‬
‫‪ o‬فاصله‌ها‪ ،‬نویسه‌های رفتن به ابتدای خط جدید‪ ،‬و غیره نادیده گرفته‬
‫می‌شوند‬
‫‪19‬‬
‫ تحلیل نحوی یا پارس‬:‫مرحله دوم‬
‫ گره‌های درخت پارس به کمک گرامر زبان برنامه‌سازی ساخته می‌ش ‌وند‬o
assignment_statement
identifier
expression
:=
Position
expression
+
expression
identifier
expression
inital
identifier
number
rate
60
Position := initial + rate * 60
*
expression
20
‫مرحله سوم‪ :‬تحلیل معنایی‬
‫‪ o‬یافتن خطاهای معنایی‬
‫=‪:‬‬
‫=‪:‬‬
‫‪+‬‬
‫*‬
‫‪intToReal‬‬
‫‪60‬‬
‫‪+‬‬
‫‪initial‬‬
‫‪rate‬‬
‫*‬
‫‪60‬‬
‫تبدیل نوع‌‬
‫‪Position‬‬
‫‪initial‬‬
‫‪rate‬‬
‫‪Position := initial + rate * 60‬‬
‫‪ o‬وارس ی نوع‌ها‪ ،‬و مجازبودن عملوندها؛ دو تحلیل مهم در این مرحله‬
‫‪21‬‬
‫مراحل و فعالیت‌های مکمل تحلیل‬
‫‪ o‬ایجاد و نگه‌داری‌ جدول عالیم‬
‫‪ ‬حاوی اطالعاتی (در مورد ذخیره‌سازی‌‪ ،‬نوع‪ ،‬محدوده‪ ،‬و آرگومان‌ها) برای هر‬
‫ً‬
‫نشانه‌ی «بامعنا» (معموال شناسه‌ها)‬
‫‌ساختار مناسب‪ ،‬در مرحله تحلیل لغوی‪ ،‬ایجاد‪ ،‬و مقداردهی اولیه می‌شود‬
‫‌‬
‫‪ ‬داده‬
‫‪ ‬جدول عالیم در مراحل بعدی تحلیل و ساخت‪ ،‬استفاده‪ ،‬یا به‌روز می‌شود‬
‫‪ o‬خطا پردازی‌‬
‫‪ ‬شناسایی خطاهای گوناگون مرتبط با تمام مراحل کامپایل‬
‫‪ ‬چگونگی برخورد با خطاها بعد از شناسایی‬
‫‪22‬‬
‫بخش ساخت در فرآیند کامپایل‬
‫‪ o‬تولید کد میانی‬
‫‪‬‬
‫کد «انتزاعی» مقصد که مستقل از ماشین است‬
‫‪‬‬
‫تسهیل فرآیند تولید کد «نهایی» مقصد که وابسته به ماشین است‬
‫‪ o‬بهینه‌سازی (پرداخت) کد‬
‫‪‬‬
‫یافتن راه‌های بهتر برای اجرای کد‬
‫‪‬‬
‫جای‌گزین کردن کدهای تولیدشده با کدهای بهینه‬
‫‪ o‬تولید کد نهایی‬
‫‪‬‬
‫تولید کد قابل جابه‌جایی وابسته به ماشین‬
‫‪ o‬بهینه‌سازی جزیی‬
‫‪‬‬
‫‪23‬‬
‫با دیدی محدود‪ ،‬کد نهایی تولیدشده را بهبود می‌دهد‬
‫مروری بر کلیت فرآیند کامپایل (‪)1‬‬
‫‪Position := initial + rate * 60‬‬
‫ی‬
‫تحلیل لغو ‌‬
‫‪60‬‬
‫خطا‬
‫پرداز‬
‫*‬
‫‪id2‬‬
‫‪+‬‬
‫‪id3‬‬
‫ی‬
‫تحلیل نحو ‌‬
‫‪60‬‬
‫=‪:‬‬
‫‪+‬‬
‫*‬
‫‪id3‬‬
‫=‪:‬‬
‫‪id1‬‬
‫‪id2‬‬
‫جدول‌ عالیم‬
‫‪id1‬‬
‫تحلیل معنایی‬
‫*‬
‫‪intToReal‬‬
‫‪id3‬‬
‫‪60‬‬
‫تولید کد میانی‬
‫‪24‬‬
‫‪id2‬‬
‫‪initial‬‬
‫‪rate‬‬
‫=‪:‬‬
‫‪+‬‬
‫‪Position‬‬
‫‪id1‬‬
‫مروری بر کلیت فرآیند کامپایل (‪)2‬‬
‫تولید کد میانی‬
‫کد سه‌آدرسه‬
‫خطا‬
‫پرداز‬
‫)‪t1 := inttoreal(60‬‬
‫‪t2 := id3 * t1‬‬
‫‪t3 := id2 + t2‬‬
‫‪id1 := t3‬‬
‫بهینه‌سازی کد‬
‫‪Position‬‬
‫‪t1 := id3 * 60.0‬‬
‫‪initial‬‬
‫‪id1 := id2 + t1‬‬
‫‪rate‬‬
‫تولید کد نهایی‬
‫‪MOVF id3, R2‬‬
‫‪MULF #60.0, R2‬‬
‫‪MOVF id2, R1‬‬
‫‪ADDF R1, R2‬‬
‫‪MOVF R2, id1‬‬
‫‪25‬‬
‫جدو ‌ل عالیم‬

similar documents