لینک کوتاه مطلب : https://hsgar.com/?p=3586

ساخت مترجمان: بررسی

منبع: باب نیستروم

به نظر من برخی از حوزه‌های حوزه علوم کامپیوتر تقریباً با جادوگری قابل مقایسه هستند. من بیشتر وقت خود را به عنوان یک مهندس نرم افزار صرف کار روی برنامه های کاربردی وب سطح بالا کرده ام، بنابراین نرم افزارهای بزرگ، پیچیده و سطح پایین تر مانند کامپایلرها، پایگاه های داده، سیستم عامل ها و مرورگرها اغلب دلهره آور به نظر می رسند. در حالی که من به طور منظم از آنها استفاده می کنم، اغلب احساس می کنم به اندازه کافی از آنها قدردانی یا درک نمی کنم.

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

بخش اول کتاب به پیاده سازی الف مترجم پیاده روی درختی در جاوا: یک اسکنر کد منبع (خوانده شده از ورودی REPL یا یک فایل) را به لیستی از نشانه ها تبدیل می کند. یک تجزیه کننده لیست نشانه ها را در یک درخت نحو انتزاعی (AST) تجزیه می کند، جایی که هر گره در درخت نشان دهنده یک واحد نحوی برنامه است. و سپس، یک مفسر درخت را طی می کند و هر گره را برای اجرای برنامه اجرا می کند.

در حین اجرای مترجم درختی، این کتاب مفاهیم مختلفی را در پس زبان های برنامه نویسی و مفسرها معرفی می کند. برای مثال، بخش تجزیه به بحث می‌پردازد دستور زبان رسمی از Lox، مجموعه قوانینی است که نحوه تولید برنامه های Lox معتبر را مشخص می کند. همچنین تجزیه کننده از تکنیکی به نام استفاده می کند تجزیه نزولی بازگشتی: مجموعه ای از توابع را تعریف می کند که در آن هر کدام یکی از قوانین تولید را در دستور زبان رسمی پیاده می کنند. با شروع از بالای گرامر، قاعده ای که یک “برنامه” را مشخص می کند، توابع به صورت بازگشتی عبارات و عبارات را تا کوچکترین “اتم ها” (مانند اعداد، رشته ها و بولی ها) تجزیه می کنند.

مفسر “محیط” خود را در نقشه ای حاوی نام ها و متغیرها، توابع و کلاس های مربوطه پیگیری می کند. هر “محدوده” (مانند یک بلوک یا یک تابع) نقشه محیطی خود و ارجاعی به محیط محدوده محصور را حفظ می کند. بنابراین، برای جستجوی یک متغیر، مفسر از طریق “لیست پیوندی” از محیط فعلی به بالاترین (جهانی) محیط می رود.

در انتهای بخش مترجم درختی، یک مفسر کامل و کارآمد Lox وجود دارد که می تواند برنامه های Lox را بخواند و تفسیر کند. اما کتاب آن را حتی فراتر می برد. بخش زیر اجرای یک مفسر بهینه تر را پوشش می دهد: یک ماشین مجازی بایت کد (VM) که به زبان C نوشته شده است. برای جلوگیری از سربار عبور از یک AST، VM یک برنامه Lox را به عنوان مجموعه ای از دستورالعمل ها در یک آرایه بایت نشان می دهد: VM’s کامپایلر برنامه منبع را به دنباله ای از دستورالعمل ها تجزیه می کند و VM از طریق دستورالعمل ها تکرار می شود و هر کدام را به نوبه خود اجرا می کند.

علاوه بر نمایش بایت کد، VM چند بهینه سازی دیگر را پیاده سازی می کند. برای یکی، آن کارآموزان تمام رشته ها در برنامه منبع (مانند نام متغیرها، توابع و کلاس ها؛ و رشته هایی که در زمان اجرا ایجاد می شوند). فقط یک کپی از هر مقدار رشته متمایز را ذخیره می کند و موارد بعدی رشته به همان کپی منحصر به فرد اشاره می کند و مقایسه رشته ها را کارآمدتر می کند.

VM مقادیر متغیرهای سراسری را در یک نقشه هش نگه می دارد. اما برخلاف مفسر Tree-walk، متغیرهای محلی را در یک پشته ذخیره می کند. این بهینه‌سازی کامپایلر VM را پیچیده‌تر می‌کند، زیرا باید بداند هر متغیر محلی را کجا نگه دارد و در پشته پیدا کند. اما عملکرد تخصیص و دسترسی به متغیرهای محلی را بهبود می بخشد. (در مورد نقشه های هش صحبت می کنیم، چون C یک نقشه هش داخلی ارائه نمی دهد، VM نقشه خود را پیاده سازی می کند.)

Lox یک زبان مدیریت شده است، به این معنی که پیاده سازی زبان حافظه را برای کاربر اختصاص داده و آزاد می کند. بنابراین، فصل بعدی در بخش VM پیاده سازی a را پوشش می دهد زباله جمع کن علامت گذاری و جارو (GC). این به طور شگفت انگیزی ساده است: GC ابتدا تمام اشیایی را که برنامه هنوز می تواند به آنها دسترسی داشته باشد، علامت گذاری می کند. اینها “ریشه ها” (متغیرهای جهانی و اشیاء در حال حاضر در پشته VM) و همچنین اشیایی هستند که ریشه ها به آنها ارجاع دارند. سپس در مرحله “sweep”، GC تمام اشیاء بدون علامت را آزاد می کند. به عنوان مثال، اشیایی که بدون اینکه توسط یک بسته گرفته شوند، از محدوده خارج شده اند.

فصل آخر بخش VM دو بهینه سازی دیگر را پوشش می دهد. اولی استفاده می کند پوشش بیت برای انجام عملیات مدولو، که سرعت جدول هش ماشین مجازی را افزایش می دهد. و دومی، NaN boxing، نمایش مقادیر Lox (بولی ها، اعداد، رشته ها، توابع، کلاس ها و نمونه ها) را از یک ساختار C اتحادیه به یک تغییر می دهد. uint64_t عدد به طوری که VM بتواند مقادیر بیشتری را در همان مقدار حافظه قرار دهد.

این بهینه‌سازی‌ها باعث می‌شوند VM یک را اجرا کند مقدار زیادی سریعتر از مترجم راه رفتن درخت. که در یک معیار، بیش از 40 برابر سریعتر از a اجرا می شود برو پیاده سازی مترجم راه رفتن درخت.

در بیش از 600 صفحه، مترجمان کاردستی خواندن سریع بعد از ظهر یکشنبه نیست. تقریباً شش ماه – یک ساعت یا بیشتر در روز برای چند روز در هفته – طول کشید تا کتاب را کامل کنم و هر دو مترجم را اجرا کنم. و من کتاب را در تئوری روشن یافتم و بیشتر بر روی اجرای عملی مفسرها تمرکز کرد تا بر تئوری زبان برنامه نویسی دانشگاهی.

با این حال، زمان ارزش آن را داشت. بسیاری از کتاب های برنامه نویسی معمولاً برای خواندن خسته کننده و چالش برانگیز هستند، اما من نوشتن را در آن پیدا کردم مترجمان کاردستی ساده، جذاب، و حتی گاهی اوقات سرگرم کننده.

همچنین از یادداشت ها و چالش های طراحی در پایان هر فصل لذت بردم. یادداشت‌ها شامل بحث‌هایی در مورد طراحی Lox و زبان‌ها به طور کلی بود، مانند: چه مقدار تازگی باید در یک زبان جدید ایجاد کنید؟ و چقدر باید به قراردادهای موجود پایبند باشید؟ چگونه باید قوانین محدوده متغیر را انتخاب کنید؟ چه نوع آزمون ها و معیارهایی را باید برای زبان خود بنویسید؟ و چالش‌ها مرا بر آن داشت تا با افزودن ویژگی‌های بیشتر (مانند عبارات سه تایی، توابع ناشناس، و روش‌های دریافت‌کننده)، بهبود خطاهای کامپایلر و افزودن بهینه‌سازی‌های بیشتر، زبان اصلی را گسترش دهم.

خود کتاب هم زیباست. بسیاری از صفحات دارای تصاویر لذت بخش هستند که به خواننده کمک می کند تا مفاهیم پیچیده را تجسم کند. و جالب بود که یاد بگیرم که نویسنده دست کشیده هر خط و حرف در تصاویر در «پشت صحنه» پست وبلاگباب نیستروم همچنین در مورد سیستم ساخت سفارشی که برای کتاب ساخته است می نویسد. این اسکریپت تمام تکه‌های هر فصل را جمع‌آوری می‌کند، نسخه‌های هر فصلی از مفسرها را می‌سازد، و سپس تمام تست‌هایی را که انتظار می‌رود از آن نقطه در کتاب عبور کنند، اجرا می‌کند! این یک اثر هنری فنی-نویسندگی است.

فکر کردم مترجمان کاردستی بسیار عالی و یکی از بهترین کتاب های فنی بود که تا به حال خوانده ام. بدون تردید، آن را به هر کسی که علاقه مند به یادگیری زبان و مترجم است توصیه می کنم. در پایان نمی توانم به جادوگری کار نویسنده خود اعتراف نکنم. ارائه چنین موضوعی به ظاهر دلهره آور به سادگی و در عین حال زیبا، در نهایت جادویی است.

لینک منبع

ارسال یک پاسخ

آدرس ایمیل شما منتشر نخواهد شد.