تاریخچه ساخت مترجم

در رایانش، مترجم یا کامپایلر یک برنامهٔ رایانه‌ای است که کد مبدأ را که به یک زبان برنامه‌نویسی یا زبان کامپیوتر (زبان مبدأ) نوشته‌شده‌است به یک زبان کامپیوتری دیگر (زبان مقصد، که اغلب به شکل دودویی است و آن را به نام کد مقصد یا کد ماشین می‌شناسند) تبدیل می‌کند. متداول‌ترین دلیل برای تبدیل کد مبدأ این است که می‌خواهیم یک برنامهٔ قابل اجرا ایجاد کنیم.

هر برنامه که به یک زبان برنامه‌نویسی سطح بالا نوشته‌شده‌است باید ابتدا به زبان ماشین ترجمه شود تا بتوان آن را اجرا کرد، بنابراین همهٔ برنامه‌نویسان که از چنین زبان‌هایی استفاده می‌کنند از یک مترجم یامفسر نیز استفاده می‌کنند. به همین دلیل، مترجم‌ها برای برنامه‌نویسان بسیار مهم هستند. هر پیشرفت در مترجم منجر به ایجاد تعداد زیادی برنامهٔ قابل اجرای بهبودیافته می‌شود.

در اواخر دهه‌ی ۱۹۷۰، پروژه‌ی تولید باکیفیت مترجمِ مترجم، اصول سازمان‌دهی کامپایلر را معرفی کرد که امروزه هنوز به طور گسترده‌ای استفاده می‌شود (به عنوان مثال، یک قسمت جلویی (front-end) برای نحو و معنی‌شناسی و یک قسمت پشتی (back-end) برای تولید کد ماشین).

اولین مترجم‌ها

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

اوّلین کامپایلر عملیاتی و کاربردی توسط کورادو بوم (در سال ۱۹۵۱ به عنوان پایان‌نامه‌ی دکترا) نوشته شد. اولین مترجم پیاده‌سازی‌شده توسط گریس هاپر نوشته شد. او اولین کسی بود که واژه‌ی compiler را برای اولین بار برای اشاره به سیستم A-0 خود به کار برد. البته این سیستم در حقیقت به عنوان یک پیوند‌دهنده (linker) یا بارگذار (loader) کار می‌کرد و نه چیزی که ما امروزه به عنوان مترجم از آن یاد می‌کنیم. در سال ۱۹۵۱، آلیک گلنی (Alick Glennie) اولین کد خودکار (Autocode) و مترجم امروزی را در دانشگاه منچستر و برای کامپیوتر Mark 1 توسعه داد. در سال ۱۹۵۷ گروه فورترن به سرپرستی جان بکوس در آی‌بی‌ام اولین مترجم تجاری را معرفی کردند. ساخت این مترجم ۱۸ نفر-سال نیرو برد.

اولین مترجم زبان ALGOL 58 توسط فریدریش ال باوئر، هرمن باتنبراک (Hermann Bottenbruch)، هینز راوتیشازر ( Heinz Rutishauser) و کلاز سملسون (Klaus Samelson ) در انتهای سال ۱۹۵۸ برای کامپیوتر Z22 کامل شد. بائر و همکاران در سال‌های گذشته مشغول کار کردن رو فناوری کامپایلر برای Sequentielle Formelübersetzung (به معنی ترجمله متوالی فرمول‌ها) بودند.

در سال ۱۹۶۰ مترجمی توسعه یافته برای فورترن به نام ALTAC برای کامپیوتر فیلکو ۲۰۰۰ وجود داشت؛ در نتیجه امکان دارد در اواسط دهه ۶۰ کامپایل برنامه‌های فورترن برای دو معماری IBM و فیلکو امکان‌پذیر بوده باشد. اولین زبان سطح بالای چند پلتفرمی شناخته شده زبان کوبول بود. در رونمایی دسامبر ۱۹۶۰ برنامه‌های کوبول می‌توانستند در هردوی پلتفرم‌های UNIVAC II و RCA 501 ترجمه و اجرا شوند.

مترجم‌های خودمیزبان

نباید با مترجم مترجم (Compiler compiler) اشتباه شود.

مانند همهٔ نرم‌افزارهای دیگر، نوشتن و پیاده‌سازی مترجم به زبان سطح بالا مزیت‌هایی دارد. به‌طور خاص، یک مترجم می‌تواند خودمیزبان باشد؛ یعنی به زبانی که خودش ترجمه می‌کند نوشته‌شده باشد. برای ساختن مترجم‌های خودمیزبان با مسئلهٔ راه‌اندازی خودکار (bootstrapping) مواجهیم؛ یعنی اولین مترجمی که این ویژگی را داشته‌باشد یا باید به زبان ماشین و دست‌نویس باشد، یا این که به وسیلهٔ مترجمی که به زبان دیگری نوشته‌شده‌است ترجمه شود، یا این که به وسیلهٔ یک مفسر اجرا شود.

رساله دکتری Corrado Böhm

در سال ۱۹۵۱، Corrado Böhm در مقاله دکترای خود یک زبان، یک ماشین و یک روش ترجمه برای کامپایل کردن آن زبان بر روی ماشین ایجاد کرد. او نه تنها یک کامپایلر کامل را توصیف کرد، بلکه برای اولین بار آن کامپایلر را به زبان خودش تعریف کرد. این زبان به خودی خود جالب بود، زیرا هر عبارت (اعم از عبارات ورودی، عبارات خروجی و عبارات کنترل) مورد خاصی از دستور انتساب بود.

نلیاک

کامپایلر بین‌المللی ALGOL متعلق به آزمایشگاه الکترونیک نیروی دریایی، یک دیالکت و پیاده‌سازی از کامپایلر زبان ALGOL85 است که توسط آزمایشگاه الکترونیک نیروی دریایی در سال ۱۹۸۵ توسعه داده شد.

NELIAC زاییده ذهن هری هاسکی - یک دانشمند کامپیوتر معروف و رئیس ACM - است و توسط مااوری هالستید رئیس مرکز محاسبات NEL پشتیبانی می‌شد. نسخه‌های اولیه روی پروتوتایپ کامپیوتر USQ-17 (که Countess نامیده می‌شد) در آزمایشگاه پیاده‌سازی شده‌است. این کامپایلر اولین کامپایلر خود کامپایل دنیا می‌باشد. ابتدا فرم ساده کامپایلر (راه‌انداز یا bootstrap) در زبان اسمبلی پیاده‌سازی شد و سپس کامپایلر اصلی توسط راه‌انداز (bootstrap) کامپایل شد و دیگر به راه‌انداز نیازی نبود.

لیسپ

یکی دیگر از اولین مترجمین خودمیزبان برای زبان لیسپ تولید شد. این مترجم توسط تیم هارت و مایک لوین در MIT و در سال ۱۹۶۲ نوشته شد. آن‌ها یک مترجم لیسپ به زبان لیسپ نوشتند و آن را با یک مفسر به زبان لیسپ که قبلاً نوشته‌شده‌بود بررسی کردند. هنگامی که آن‌ها توانستند مترجم را به جایی برسانند که بتواند کد منبع خود را ترجمه کند خودمیزبان شده‌بود.

این تکنیک تنها زمانی امکان‌پذیر است که یک مفسر از قبل برای همان زبانی که قرار است کامپایل شود وجود داشته باشد. این مطلب مستقیماً از مفهوم اجرای یک برنامه بر روی خود به عنوان ورودی بهره می‌گیرد که همچنین در اثبات‌های مختلف نظری در علوم کامپیوتر (مانند اثبات غیر قابل حل بودن مسئله‌ی توقف) استفاده می‌گردد.

فورث

Forth مثالی از کامپایلر خودمیزبان است. ویژگی‌های خودمترجمی و cross-compilation که کامپایلر Forth آن را داراست، معمولاً با فراکامپایل و فراکامپایلر اشتباه گرفته می‌شود. زبان فورث همانند زبان لیسپ یک زبان برنامه‌نویسی قابل گسترش است. این قابل گسترش بودن زبان‌های برنامه‌نویسی Forth و Lisp است که آن‌ها را قادر می‌سازد تا نسخه‌های جدیدی از خود را تولید کنند یا خود را به محیط‌های جدید منتقل کنند.

گرامرهای مستقل از متن و تجزیه‌کننده‌ها

تجزیه‌کننده (parser) یک جزءِ مهم از مترجم است. کد منبع یک زبان برناهه‌نویسی را تجزیه می‌کند تا یک نمایش درونی از آن را ایجاد کند. زبان‌های برناهه‌نویسی باید به صورت گرامرهای مستقل از متن تصریح شوند که بتوان تجزیه‌کننده‌های سریع و کارآمدی برای آن‌ها نوشت. تجزیه‌کننده‌ها می‌توانند به صورت دستی نوشته شوند یا به وسیلهٔ تولیدکنندهٔ تجزیه‌کننده تولید شوند. گرامر مستقل از متن یک ساختار ساده و دقیق برای توصیف ساختار بلوکی برنامه است که چگونه سازه‌های زبان برنامه‌نویسی از بلوک‌های کوچک‌تر ساخته‌شده‌اند. رسمی‌سازی گرامر مستقل از متن توسّط نوآم چامسکی در میانهٔ دههٔ ۱۹۵۰ توسعه یافت. ساختار بلوکی به وسیلهٔ پروژهٔ ALGOL به دنیای زبان‌های برنامه‌نویسی معرّفی شد (۱۹۶۰–۱۹۵۷)، که به عنوان نتیجه هم‌چنین گرامر مستقل از متن را برای توضیح دستور ALGOL حاصل به‌طور برجسته نشان داد.

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

تجزیهٔ LR

تجزیه‌کننده‌های LR(چپ به راست) در سال ۱۹۶۵ توسط دانلد کنوت در مقالهٔ به نام «درترجمهٔ زبان از چپ به راست» اختراع شد. یک تجزیه‌کنندهٔ LR تجزیه‌کننده‌ای است که ورودی را از چپ به راست می‌خواند و یک اشتقاق از سمت راست می‌سازد. تجزیه‌کننده‌های (LR(k نیز استفاده می‌شوند. k به تعداد علامت‌های پیش‌بینی مصرف نشدهٔ ورودی که برای تصمیم‌گیری‌های تجزیه استفاده می‌شود، اشاره می‌کند.

کنوت اثبات کرد که گرامرهای (LR(k می‌توانند با یک زمان اجرای متناسب با طول برنامه تجزیه شوند و همهٔ تجزیه گرامرهای (LR(k با k> 1 می‌توانند به گرامرهای (LR(1 برای همان زمان تبدیل شوند. به بیان دیگر یک علامت پیش‌بینی برای تجزیهٔ گرامرهای مستقل از متن قطعی کافی است (DCFG).

کرنیاک(۱۹۶۹) اولین کسی بود که نشان داد تجزیه‌کننده‌های زبان‌های برنامه‌نویسی با استفاده از این تکنیک‌ها می‌توانند تولید شوند.

فرانک درمر روش‌های کاراتری مثل تجزیه‌کننده SLR و تجزیه‌کننده LALR را در پایان‌نامهٔ دکترای خود در دانشگاه MIT در سال ۱۹۶۹ منتشر کرد. این یک پیشرفت بسیار مهم بود زیرا مترجم‌های (LR(k که توسط دانلد کنوت توصیف شده بود، برای اجرا در کامپیوترهای دهه‌های ۱۹۶۰ و ۱۹۷۰ بسیار بزرگ بود.

در عمل LALR یک راه حل خوب ارائه می‌دهد. این برتری تجزیه‌کنندهٔ (LALR(1 بر تجزیه‌کننده‌های (SLR(1 (این است که(LALR(1 می‌تواند گرامرهای پیچیده‌تری نسبت به (SLR(1 را تجزیه کند) بسیار مفید است، اگرچه (LALR(1 با تجزیه‌کننده‌های (LL(1 قابل مقایسه نیست ((LALR(1 نمی‌تواند همهٔ گرامرهای (LL(1 را تجزیه کند)بیشتر گرامرهای (LL(1 که در عمل با آن‌ها مواجه هستیم معمولاً می‌توانند با (LALR(1 تجزیه شوند. گرامرهای (1)LR از گرامرهای (LALR(1 بسیار قوی تر هستند، هر چند یک گرامر (1)LR به یک تجزیه‌کننده LR استاندارد نیاز دارد که از لحاظ اندازه بسیار بزرگ است و در عمل کارا نیست.

نحو بسیاری از زبان‌های برنامه‌نویسی که با گرامرها توصیف می‌شوند می‌توانند با تجزیه‌کننده‌های (LALR(1 تجزیه شوند و به همین دلیل تجزیه‌کننده‌های LALR معمولاً توسط کامپایلرها برای اجرای تحلیل نحوی کدهای منبع استفاده می‌شوند. یک تجزیه‌کنندهٔ صعودی بازگشتی مانند یک تجزیه‌کننده LALR عمل می‌کند و به جای جدول‌هااز تابع‌های متقابل صعودی استفاده می‌کند؛ بنابراین تجزیه‌کننده به‌طور مستقیم به یک نزولی بازگشتی در زبان میزبان رمز می‌شود.

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

صعودی بازگشتی برای اولین بار در سال ۱۹۸۶ در مقاله‌ای به نام " تجزیهٔ LR بسیار سریع " توسط توماس پنلو شرح داده‌شد. این روش در سال ۱۹۸۸ توسز جی.اچ. رابرتز و همچنین در مقاله‌ای به قلم لیرمارکرز، اگوستیخن و کروسمان آرتز در مجلهٔ تئوری علوم کامپیوتر در سال ۱۹۹۲ تشریح شد.

تجزیهٔ LL

یک تجزیه‌کننده LL ورودی را از چپ به راست تجزیه می‌کند و یک اشتقاق چپ از جمله است. به دستهٔ گرامرهایی که به این صورت قابل تجزیه هستند گرامرهای LL گفته می‌شود. گرامرهای LL گرامرهای مستقل از متنی هستند که از گرامرهای LR محدودتر هستند، با این وجود به دلیل سادگی و اجرای کارآمد در بین نویسندگان مترجم‌ها بسیار محبوب هستند.

گرامرهای (LL(k می‌توانند با تجزیه‌کننده‌های بازگشتی نزولی که معمولاً با دست رمز می‌شوند، تجزیه شوند.

به دلیل این‌که ALGOL خود بازگشتی است، طراحی آن بررسی نزولی بازگشتی را برانگیخت. مفهوم تجزیهٔ نزولی بازگشتی در ژانویه ۱۹۶۱ در CACM (گردهمایی ACM) در دو مقالهٔ جداگانه توسط ای.ای. گرائو و ادگار تی. «ند» آیرنز بحث شد. در مارس ۱۹۶۱ ریچارد وایچف به صورت مستقل با الهام از نزولی بازگشتی از آن‌ها در مترجمهای Burroughs ALGOL استفاده کرد.

ایدهٔ گرامرهای (1)LL در سال ۱۹۶۸ توسط لوییس و استرنز معرفی شد.

نزولی بازگشتی توسط نیکلاس ورث و با PL/0 یک زبان برنامه‌نویسی علمی برای آموزش ساختار مترجم‌ها در دههٔ ۷۰، محبوب شد.

تجزیهٔ LR زبان‌های بیشتری نسبت به تجزیهٔ LL پشتیبانی می‌کند و همچنین در گزارش خطا بهتر است، به عنوان مثال خطاهای نحوی را هنگامی که ورودی با گرامر مطابقت ندارد به سرعت تشخیص می‌دهد.

تجزیه‌کننده‌های ارلی

در سال ۱۹۷۰ جی ارلی تجزیه‌کننده‌ای را اختراع کرد که به تجزیه‌کننده‌های ارلی معروف است. این تجزیه‌کننده‌ها بسیار پرطرفدار هستند زیرا تمام گرامرهای مستقل از متن را به صورت بسیار کارآمد تجزیه می‌کنند.

زبان‌های توصیف‌کننده گرامر

جان بکوس «فرمول فرازبانی» را برای توصیف نحو زبان برنامه‌نویسی جدید IAL که امروزه با نام الگول ۵۸ شناخته می‌شود ارائه کرد(۱۹۵۹). کار بکوس برپایه سیستم استاندارد پست که توسط امیل لئون پست ابداع شد، قرار داشت. گشترس‌های بعدی الگول منجر به الگول ۶۰ شد، پیتر نااور در گزارش خود (۱۹۶۳) نشانه‌گذاری بکوس را فرم نرمال بکوس (BNF) نامید و آن را با حداقل کردن کاراکترهای مورد استفاده ساده‌سازی کرد. هرچند دونالد کنوث استدلال کرده‌است که BNF می‌بایست به صورت فرم بکوس-نائور خوانده شود و این استدلال به صورت عمومی قبول شده‌است.

نیکلاوس ویرت فرم بکوس-نائور توسعه‌یافته (EBNF) را تعریف کرده‌است که یک نسخه اصلاح شده از BNF در اوایل دهه ۶۰ برای PL/0 می‌باشد. فرم تکمیل‌شده بکوس-نائور (ABNF) شکل دیگری از نشانه‌گذاری است. هردوی EBNF و ABNF به کرار برای مشخص کردن گرامر زبان‌های برنامه‌نویسی، به عنوان وردی برای ژنراتورهای تجزیه گر مورد استقاده قرار می‌گیرد. همچنین در شاخه‌های دیگری همچون پروتکل‌های ارتباط مورد استفاده قرار می‌گیرد.

سازنده‌های تجزیه گر

یک سازنده تجزیه گر بخش تحلیل گر لغوی یک کامپایلر را ایجاد می‌سازد. یک برنامه که با دریافت توضیحات گرامر یک زبان برنامه‌نویسی خاص تجزیه گر آن زبان را ایجاد می‌کند. این تجزیه گر می‌تواند در کامپایلر آن زبان خاص مورد استفاده قرار بگیرد. تجزیه گر، نمادها و کلید واژه‌های آن زبان خاص را در متن ورودی شناسایی کرده و این نشانه‌ها را به کدی که وظیفه تعیین ازرش نحوی و ترجمه به آبجکت کد را برعده دارد برمی‌گرداند. این بخش دوم کامپایلر می‌تواند با کامپایلر-کامپایلر ایجاد شود که قوانین اولیت شرح نحو رسم زبان را به عنوان ورودی می‌گیرد. اولین کامپایلر-کامپایلر برای استفاده به این نام توسط تونی بروکر در سال ۱۹۶۰ نوشته شد و برای ساخت کامپایلرهای برای کامپیوتر اطلس در دانشگاه منچستر مورد استفاده قرار گرفت، همانند کامپایلر اوتوکد اطلس. هر چند با کامپایلر-کامپایلرهای مدرن بسیار متفاوت بود، و کامپایلر-کامپایلر امروزه تعریفی مابین کامپایلر عمومی با قابلیت شخصی‌سازی بالا و یک زبان با قابلیت توصعه‌پذیری نحو آن می‌تواند داشته باشد. نام کامپایلر-کامپایلر برای سیستم بروکر به متراتب مناسب تر است تا کامپایلر-کامپایلرهای مدرن، که به صراحت با نام سازنده تجزیه گر نامیده می‌شوند. به اطمینان می‌توان گفت که نام کامپایلر-کامپایلر پس از یاک به صورت عمومی مورد استفاده گرفت هرچند کار بروکر همچنان حائز اهمیت است. در اوایل ۱۹۶۰ رابرت مک کلور در ابزارآلات تگزاش کامپایلر-کامپایلری طراحی کرد که TMG نام گرفت که از کلمه “transmogrification” (به معنی تناسخ) گرفته شده‌است. در سالهای بعد TMG به مینفریم‌های برخی از کامپیوترهای UNIVAC و IBM پورت شد. نمونه دیگری از سازنده‌های تجزیه گر متا دو است که اولین بار در سال ۱۹۶۲ توسط وال شوور منتشر شد. متا دو گرامر و قاعد تولید کد را قبول می‌کرد و می‌توانست زبان خود و دیگر زبان‌ها را کامپایل کند. متادو دو اولین نسخه مستند شده متاکامپایلر بود. همچنین متادو به یکی از اولین نمونه‌های ماشین مجازی ترجمه شد. پروژه مالتیکس ریسک همکاری میان MIT و آزمایشگاه‌های بل، یکی از اولین‌ها برای گسترس یک سیستم عامل با استفاده از یک زبان سطح بالا بود، زبان انتخاب شده پی‌ال/۱ بود، اما یک کارپرداز خارجی نمی‌تواند کامپایلری برای کار تهیه کند. گروه مالتیکس پیاده‌سازی شخصی خود را از زبان PL/1 گشترش دادند که با نام EPL شناخته می‌شود. TMG روی سری GE-600 پورت شده بود و برای گسترش EPL توسط داگلاس مکلروی، رابرت موریس و دیگران مورد استفاده قرار گرفت. چندی بعد کن تامسون اولین نسخه یونیکس را برای PDP-7 در ۱۹۶۹ نوشت، داگ مکلروی اولین زبان سطح بالای سیستم جدید را ایجاد کرد: پیاده‌سازی مکلروی از TMG. TMG همچنین ابزار تعریف کامپایلری است که تامسون جهت پیاده‌سازی کامپایلر برای زبان بی برای PDP-7 در ۱۹۷۰ مورد استفاده قرار داد. بی اولین جد زبان سی می‌باشد. نخستین سازنده تجزیه گر LALR که توسط فرانک درمر و تام پندلو ساخته شد TWS نام داشت.

XPL

XPL یک پیاده‌سازی شخصی از زبان PL/1 است که در سال ۱۹۶۷ گسترش یافت و برای ساخت کامپایلر کامپایلرها مورد استفاده قرار گرفت. XPL توسط تیمی متشکل از ویلیام مک کیمن، جیمز هورینگ و دیوید ورتمن در دانشگاه استنفورد، دانشگاه کالیفورنیا و سانتا کروز طراحی و پیاده‌سازی شد. اولین رونمایی از آن در کنفرانس پاییزه کامپیوتر دانشگاه سانفرانسیسکو در سال ۱۹۶۸ بود. XPL به هردوی زبان برنامه‌نویسی و سازنده تجزیه گر LALR که برپایه همین زبان نوشته شده‌است گفته می‌شود. XPL یک سیستم نسبتاً ساده پایین به بالا است که توسط نویسندگانش لقب MSP (استراتژی اولویت مختلط) گرفته‌است.

YACC

YACC یک سازنده تجزیه گر است، آن را با lex اشتباه نگیرید، lex یا تحلیلگر لغوی است که در مرحله اول یاک از آن استفاده می‌کند. یاک توسط استفان جانسون در AT&T برای سیستم عامل یونیکس گسترش داده شده‌است. نام یاک از عبارت "Yet Another Compiler Compiler" گرفته شده‌است. این سازنده تجزیه گر کامپایلرهای LALR(1) را که برپایه گرامرهای نوشته به فرمی شبیه فرم بکوس نائور ایجاد می‌کند. جانسون در اوایل ۱۹۷۰ در آزمایشگاهای بل روی یاک کار می‌کرد. وی بسیار با TMG آشنا بود و تأثیرات آن را می‌توان در یاک و طراحی زبان برنامه‌نویسی C مشاهده کرد. از آنجایی که یاک سازنده کامپایلر پیش‌فرض در سیستم‌های یونیکس بود، بسیار گشترش یافته و مورد استفاده قرار گرفته‌است. گشترش‌هایی همانند GNU Bison همچنان در حال استفاده هستند. کامپایلر ایجاد شده توسط یاک نیازمند یک تحلیلگر لغوی است. سازنده‌های تحلیل گر لغوی همانند lex یا flex در دسترس هستند. استانداردهای موجود در IEEE POSIX P1003.2 نیازمندی‌ها و توانایی‌های هر دوی Lex و Yacc را تعیین می‌کند.

ترجمهٔ تقابلی

یک مترجم تقابلی در یک محیط اجرا می‌شود و برای یک محیط دیگر کد شی تولید می‌کند. مترجم‌های تقابلی در توسعه‌های جاسازی شده، در جایی که کامپیوتر هدف قابلیت‌های محدودی دارد. یک مثال اولیه از این کامپایلرها AIMICO است که یک برنامهٔ FLOW-MATIC بر روی UNIVAC II بود که برای اجرای کدهای اسمبلی در کامپیوتر IBM 705 است که بعداً روی کامپیوترهای IBM نصب شد.

مترجم ALGOL 68C کد خروجی ZCODE را تولید کرد که می‌تواند به یک کد ماشین محلی به وسیلهٔ یک مترجم ZCODE نیز ترجمه یا تفسیر شود. ZCODE یک برنامهٔ میانی بر پایهٔ رجیستر استوار است. این توانایی تفسیر یا ترجمهٔ ZCODE سازندگان ALGOL 68C را تشویق کرد که کامپیوترهای پایهٔ متنوعی را تکثیر کنند.

بهینه‌سازی مترجم‌ها

بهینه‌سازی کامپایلر فرایند بهبود کیفیت کد بدون تغییر نتیجهٔ تولیدی آن است.

هدف توسعه‌دهندگان اولین مترجم FORTRAN این بود که مترجم بتواند با سرعتی بیش از اسمبلرهای دستی کدها را اجرا کند، بدین ترتیب مشتریان از محصول آن‌ها استفاده کردند و آن‌ها در تلاش اولیه موفق شدند.

کامپایلرهای بعدی مثل مترجم Fortran IV شرکت IBM اولویت بیشتری برای عیب یابی بهتر و اجرای سریع‌تر در هزینهٔ بهینه‌سازی کدها قائل شدند. سری IBM 360 دو مترجم جداگانه ارائه دادند: یک جستجوگر کد سریع در اجرا و یک بهینه‌ساز با سرعت پایین‌تر.

فرانسیس آلن به تنهایی و به همراه جان کوک بسیاری از جنبه‌های بهینه‌سازی را معرفی کرد. مقالهٔ سال ۱۹۶۶ آلن، بهینه‌سازی برنامه، نمودار ساختمان داده‌ای برای رمز کردن محتوای برنامه برای بهینه‌سازی ارائه داد. مقالات وی در سال ۱۹۷۰، کنترل تجزیه و تحلیل جریان و پایه‌ای برای بهینه‌سازی برنامه، به عنوان زمینه‌ای برای تجزیه و تحلیل جریان داده‌های کارآمد و مؤثر منتشر شد. مقالهٔ مشترک وی با کوک در سال ۱۹۷۱، کاتالوگ بهینه‌سازی تحول، اولین شرح و اسلوبی از بهینه‌سازی تحولات را ارائه داد. مقالات سال‌های ۱۹۷۳ و ۱۹۷۴ وی بر تجزیه و تحلیل جریان داده‌ها، تحلیل را در کل برنامه گسترش داد. مقالهٔ مشترک او و کوک در سال ۱۹۷۶ یکی از دو استراتژی اصلی تحلیل است که امروز در بهینه‌سازی کامپایلرها استفاده می‌شود. آلن روش‌های خود را به عنوان قسمتی از کامپایلرها برای کامپیوترهای IBM 7030 Stretch-Harvest و ماشینهای محاسباتی پیشرفته توسعه داد و اجرا کرد. این کار امکان و بنای ایجاد ماشین‌های مدرن و بهینه‌سازهای مستقل از زبان را به وجود آورد. او ایجاد و رهبری پروژهٔ PTRAN را برای اجرای هم‌زمان برنامه‌های FORTRAN به عهده گرفت. تیم PTRAN او طرح‌های تشخیص موازی جدید و ایجاد مفهوم گراف وابستگی برنامه را توسعه داد، پایه‌های اولیه روش در همزمانی کامپایلرها استفاده شده‌است.

کتاب زبان‌های برنامه‌نویسی و کامپایلرهای آن به قلم جان کوک و جیکوب تی. شوارتز، که در اوایل ۱۹۷۰ منتشر شد، بیش از ۲۰۰ صفحه را به بهینه‌سازی الگوریتمها اختصاص داد. این کتاب شامل بسیاری از تکنیک‌های آشنا از جمله حذف کدهای تکراری و کاهش قدرت است.

بهینه‌سازی روزنه‌ای

بهینه‌سازی روزنه‌ای یک روش بهینه‌سازی ساده ولی تأثیرگذار است که اختراع ویلیام مک کیمن است و در سال ۱۹۶۵ در CACM منتشر شد. این روش در کامپایلرهای XPL که توسط مک کیمن توسعه یافت نیز استفاده می‌شود.

بهینه‌ساز Capex COBOL

شرکت capex در اواسط دههٔ ۷۰ بهینه‌ساز COBOL را برای COBOL توسعه داد. این نوع از بهینه‌سازها وابسته هستند، در این مورد، به آگاهی از ضعف‌های موجود در کامپایلر استاندارد IBM برای COBOL و در حقیقت بخشی از آبجکت کد را با کدی موثرتر جایگزین می‌کند یا کد مؤثر را به آن الحاق می‌کند کد جایگزین ممکن است یک جدول ارجاع خطی را با یک جستجوی دودویی یا گاهی یک دستورالعمل کند را با یک نوع سریعتر آن که عملکرد مشابه دارد جایگزین کند. این روش در حال حاضر به عنوان «کاهش قدرت» شناخته شده‌است. به عنوان مثال بر روی سخت‌افزار IBM/360 دستورالعمل CLI به یک مدل خاص وابسته بود که برای مقایسه یک بایت بین دو بار و ۵ برابر سریع تر از یک دستور CLC بود.

کامپایلرهای مدرن به‌طورمعمول گزینه‌های بهینه‌سازی را ارائه می‌دهند و برنامه نویسان می‌توانند انتخاب کنند که گذر بهینه‌سازی را اجرا کنند یا خیر.

عیب یابی

هنگامی که به یک کامپایلر یک برنامه‌ای داده می‌شود که از نظر نحوی نادرست است، نمایش یک پیغام خطای کوتاه و واضح بسیار مفید است. البته از دیدگاه طراح کامپایلر، رسیدن به آن دشوار است. کامپایلر فرترن WATFIV در اواخر دهه ۱۹۶۰ در دانشگاه واترلو کانادا توسعه داده شد. این کامپایلر برای ارائه پیغام خطای بهتر نسبت به کامپایلر فرترن IBM آن زمان، طراحی شده بود. علاوه بر این WATFIV بسیار کاربردی‌تر بود، به این دلیل که مراحل کامپایل، اجرا را در یک مرحله ترکیب کرده بود، در حالی که کامپایلر IBM برای اجرای این مراحل را در ۳ بخش جداگانه داشت!

PL\C

پی ال/سی یک زبان برنامه‌نویسی است که اوایل دهه ۱۹۷۰ در دانشگاه کرنل پدید آمد. در حالی که پی ال/سی زیرمجموعه زبان پی ال/آی IBM بود، برای هدف خاص آموزش برنامه‌نویسی طراحی شده بود. دو محقق و استاد دانشگاهی که پی ال/سی را طراحی کردند، Richard W. Conway و Thomas R. Wilcox بودند. آن‌ها مقاله معروف «طراحی و پیاده‌سازی یک کامپایلر عیب یاب برای پی ال/آی» ارائه دادند که در مارس ۱۹۷۳ در مجله Communications of ACM منتشر گردید. پی ال/سی برخی از ویژگی‌های پیچیده پی ال/آی را حذف کرد و امکان اشکال زدایی و بازیابی خطا به صورت وسیع را به آن اضافه کرد. پی ال/سی یک امکان غیرعادی داشت که هرگز در کامپایل یک برنامه شکست نمی‌خورد. این امکان غیرعادی با استفاده وسیع از تصحیح خودکار بسیاری از خطاهای نحوی و تبدیل هرگونه خطای باقی‌مانده به عنوان اعلامیه خروجی امکان‌پذیر شده بود.

ترجمهٔ درجا

مقاله اصلی:کامپایل درجا

کامپایل درجا (JIT) یک اصطلاح است که در حال حاضر برای توصیف تولید کدهای اجرایی آنی یا به اندازه ممکن نزدیک به اجرای واقعی به کار می‌رود. دلیل وجود کامپایل درجا این است که از معیارهای نرم‌افزارسنجی زمان اجرا یا دیگر گزینه‌های بهبود کارایی استفاده شود. یک مثال جدید از کامپایل درجا در Works Records System است، صفحه گسترده ای در سال ۱۹۷۴ که اخیراً قطعه کدهای ماشینIBM/360 را برای انجام محاسبات بر اساس فرمول وارد شده به عنوان قطعه‌های داده تولید کرده‌است. این از دستورالعمل‌های IBM/360 برای تولید کد ماشین IBM/360 استفاده کرده‌است، که بعدها از پروژه Dynamo شرکت HP پیشی گرفت.

تولید کد

مقاله‌ی اصلی: تولید کد (کامپایلر)

یک تولیدکننده‌ی کد، دستورات ماشین را برای پردازنده‌ی مقصد تولید می‌کند.

تخصیص دادن ثبات

الگوریتم Sethi – Ulman یا شماره گذاری Sethi-Ulman روشی برای به حداقل رساندن تعداد ثبات‌های مورد نیاز برای نگهداری متغیرها است.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «History of compiler construction». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۵ بهمن ۱۳۹۲.