موضوع مقاله: تاریخچه ساخت مترجم | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تاریخچه ساخت مترجم | مقدمه: متداول‌ترین دلیل برای تبدیل کد مبدأ این است که می‌خواهیم یک برنامهٔ قابل اجرا ایجاد کنیم. | ## بخش 1: تاریخچه ساخت مترجم | هر برنامه که به یک زبان برنامه‌نویسی سطح بالا نوشته‌شده‌است باید ابتدا به زبان ماشین ترجمه شود تا بتوان آن را اجرا کرد، بنابراین همهٔ برنامه‌نویسان که از چنین زبان‌هایی استفاده می‌کنند از یک مترجم یامفسر نیز استفاده می‌کنند. هر پیشرفت در مترجم منجر به ایجاد تعداد زیادی برنامهٔ قابل اجرای بهبودیافته می‌شود. در اواخر دهه‌ی ۱۹۷۰، پروژه‌ی تولید باکیفیت مترجمِ مترجم، اصول سازمان‌دهی کامپایلر را معرفی کرد که امروزه هنوز به طور گسترده‌ای استفاده می‌شود (به عنوان مثال، یک قسمت جلویی (front-end) برای نحو و معنی‌شناسی و یک قسمت پشتی (back-end) برای تولید کد ماشین). اولین مترجم‌ها نرم‌افزارهایی که برای کامپیوترهای اولیه نوشته می‌شد عموما به زبان اسمبلی بودند. از دید یک برنامه‌نویس بهتر است که برای توسعه‌ی نرم‌افزار از یک زبان برنامه‌نویسی سطح بالا استفاده کند، و برنامه‌هایی که به زبان برنامه‌نویسی سطح بالا نوشته شده‌اند قابلیت استفاده‌ی مجدد روی کامپیوترهای مختلف را دارند. با این حال، مدتی طول کشید تا کامپایلرها به صورت گسترده مورد استفاده قرار گیرند؛ زیرا کدهای تولیدی توسط کامپایلرها به کارآمدی کدهای دست‌نویس در اسمبلی نبود؛ کامپایلرها گسترش پروژه‌ها را محدود به رعایت قوانین خود می‌کردند و هم‌چنین حافظهٔ محدود کامپیوترهای قدیمی باعث ایجاد مشکلات تکنیکی بسیاری در طراحی مترجم‌ها می‌شد. اوّلین کامپایلر عملیاتی و کاربردی توسط کورادو بوم (در سال ۱۹۵۱ به عنوان پایان‌نامه‌ی دکترا) نوشته شد. در سال ۱۹۵۷ گروه فورترن به سرپرستی جان بکوس در آی‌بی‌ام اولین مترجم تجاری را معرفی کردند. در سال ۱۹۶۰ مترجمی توسعه یافته برای فورترن به نام ALTAC برای کامپیوتر فیلکو ۲۰۰۰ وجود داشت؛ در نتیجه امکان دارد در اواسط دهه ۶۰ کامپایل برنامه‌های فورترن برای دو معماری IBM و فیلکو امکان‌پذیر بوده باشد. مانند همهٔ نرم‌افزارهای دیگر، نوشتن و پیاده‌سازی مترجم به زبان سطح بالا مزیت‌هایی دارد. به‌طور خاص، یک مترجم می‌تواند خودمیزبان باشد؛ یعنی به زبانی که خودش ترجمه می‌کند نوشته‌شده باشد. برای ساختن مترجم‌های خودمیزبان با مسئلهٔ راه‌اندازی خودکار (bootstrapping) مواجهیم؛ یعنی اولین مترجمی که این ویژگی را داشته‌باشد یا باید به زبان ماشین و دست‌نویس باشد، یا این که به وسیلهٔ مترجمی که به زبان دیگری نوشته‌شده‌است ترجمه شود، یا این که به وسیلهٔ یک مفسر اجرا شود. او نه تنها یک کامپایلر کامل را توصیف کرد، بلکه برای اولین بار آن کامپایلر را به زبان خودش تعریف کرد. این زبان به خودی خود جالب بود، زیرا هر عبارت (اعم از عبارات ورودی، عبارات خروجی و عبارات کنترل) مورد خاصی از دستور انتساب بود. نلیاک کامپایلر بین‌المللی ALGOL متعلق به آزمایشگاه الکترونیک نیروی دریایی، یک دیالکت و پیاده‌سازی از کامپایلر زبان ALGOL85 است که توسط آزمایشگاه الکترونیک نیروی دریایی در سال ۱۹۸۵ توسعه داده شد. آن‌ها یک مترجم لیسپ به زبان لیسپ نوشتند و آن را با یک مفسر به زبان لیسپ که قبلاً نوشته‌شده‌بود بررسی کردند. هنگامی که آن‌ها توانستند مترجم را به جایی برسانند که بتواند کد منبع خود را ترجمه کند خودمیزبان شده‌بود. این تکنیک تنها زمانی امکان‌پذیر است که یک مفسر از قبل برای همان زبانی که قرار است کامپایل شود وجود داشته باشد. این مطلب مستقیماً از مفهوم اجرای یک برنامه بر روی خود به عنوان ورودی بهره می‌گیرد که همچنین در اثبات‌های مختلف نظری در علوم کامپیوتر (مانند اثبات غیر قابل حل بودن مسئله‌ی توقف) استفاده می‌گردد. این قابل گسترش بودن زبان‌های برنامه‌نویسی Forth و Lisp است که آن‌ها را قادر می‌سازد تا نسخه‌های جدیدی از خود را تولید کنند یا خود را به محیط‌های جدید منتقل کنند. گرامرهای مستقل از متن و تجزیه‌کننده‌ها تجزیه‌کننده (parser) یک جزءِ مهم از مترجم است. کد منبع یک زبان برناهه‌نویسی را تجزیه می‌کند تا یک نمایش درونی از آن را ایجاد کند. زبان‌های برناهه‌نویسی باید به صورت گرامرهای مستقل از متن تصریح شوند که بتوان تجزیه‌کننده‌های سریع و کارآمدی برای آن‌ها نوشت. تجزیه‌کننده‌ها می‌توانند به صورت دستی نوشته شوند یا به وسیلهٔ تولیدکنندهٔ تجزیه‌کننده تولید شوند. گرامر مستقل از متن یک ساختار ساده و دقیق برای توصیف ساختار بلوکی برنامه است که چگونه سازه‌های زبان برنامه‌نویسی از بلوک‌های کوچک‌تر ساخته‌شده‌اند. ساختار بلوکی به وسیلهٔ پروژهٔ ALGOL به دنیای زبان‌های برنامه‌نویسی معرّفی شد (۱۹۶۰–۱۹۵۷)، که به عنوان نتیجه هم‌چنین گرامر مستقل از متن را برای توضیح دستور ALGOL حاصل به‌طور برجسته نشان داد. سادگی زبان‌های مستقل از متن باعث می‌شود که الگوریتم‌های تجزیه کارآمدتری را بتوان طراحی کرد که برای یک رشته ورودی خاص تعیین می‌کند این رشته با گرامرهای موجود چگونه ساخته می‌شود. اگر طراح زبان برنامه‌نویسی خواهان استفاده از زیرمجموعه‌های کوچکتری از گرامرهای مستقل از متن باشد، می‌توان تجزیه گرهای مؤثر تری نیز نوشت. تجزیهٔ LR تجزیه‌کننده‌های LR(چپ به راست) در سال ۱۹۶۵ توسط دانلد کنوت در مقالهٔ به نام «درترجمهٔ زبان از چپ به راست» اختراع شد. یک تجزیه‌کنندهٔ LR تجزیه‌کننده‌ای است که ورودی را از چپ به راست می‌خواند و یک اشتقاق از سمت راست می‌سازد. k به تعداد علامت‌های پیش‌بینی مصرف نشدهٔ ورودی که برای تصمیم‌گیری‌های تجزیه استفاده می‌شود، اشاره می‌کند. کنوت اثبات کرد که گرامرهای (LR(k می‌توانند با یک زمان اجرای متناسب با طول برنامه تجزیه شوند و همهٔ تجزیه گرامرهای (LR(k با k> 1 می‌توانند به گرامرهای (LR(1 برای همان زمان تبدیل شوند. به بیان دیگر یک علامت پیش‌بینی برای تجزیهٔ گرامرهای مستقل از متن قطعی کافی است (DCFG). کرنیاک(۱۹۶۹) اولین کسی بود که نشان داد تجزیه‌کننده‌های زبان‌های برنامه‌نویسی با استفاده از این تکنیک‌ها می‌توانند تولید شوند. فرانک درمر روش‌های کاراتری مثل تجزیه‌کننده SLR و تجزیه‌کننده LALR را در پایان‌نامهٔ دکترای خود در دانشگاه MIT در سال ۱۹۶۹ منتشر کرد. این یک پیشرفت بسیار مهم بود زیرا مترجم‌های (LR(k که توسط دانلد کنوت توصیف شده بود، برای اجرا در کامپیوترهای دهه‌های ۱۹۶۰ و ۱۹۷۰ بسیار بزرگ بود. | ## بخش 2: تاریخچه ساخت مترجم | گرامرهای (1)LR از گرامرهای (LALR(1 بسیار قوی تر هستند، هر چند یک گرامر (1)LR به یک تجزیه‌کننده LR استاندارد نیاز دارد که از لحاظ اندازه بسیار بزرگ است و در عمل کارا نیست. نحو بسیاری از زبان‌های برنامه‌نویسی که با گرامرها توصیف می‌شوند می‌توانند با تجزیه‌کننده‌های (LALR(1 تجزیه شوند و به همین دلیل تجزیه‌کننده‌های LALR معمولاً توسط کامپایلرها برای اجرای تحلیل نحوی کدهای منبع استفاده می‌شوند. یک تجزیه‌کنندهٔ صعودی بازگشتی مانند یک تجزیه‌کننده LALR عمل می‌کند و به جای جدول‌هااز تابع‌های متقابل صعودی استفاده می‌کند؛ بنابراین تجزیه‌کننده به‌طور مستقیم به یک نزولی بازگشتی در زبان میزبان رمز می‌شود. کدگذاری مستقیم معمولاً منجر به تولید یک تجزیه‌کننده سریع تر نسبت به نوع مبتنی بر جدول آن می‌شود به همین دلیل است که تألیف بسیار از ترجمه سریع تر است. همچنین ویرایش یک تجزیه‌کنندهٔ بازگشتی صعودی ممکن است، در صورتی که اجرای جدولی آن تقریباً برای انسان غیرقابل خواندن است. صعودی بازگشتی برای اولین بار در سال ۱۹۸۶ در مقاله‌ای به نام " تجزیهٔ LR بسیار سریع " توسط توماس پنلو شرح داده‌شد. رابرتز و همچنین در مقاله‌ای به قلم لیرمارکرز، اگوستیخن و کروسمان آرتز در مجلهٔ تئوری علوم کامپیوتر در سال ۱۹۹۲ تشریح شد. تجزیهٔ LL یک تجزیه‌کننده LL ورودی را از چپ به راست تجزیه می‌کند و یک اشتقاق چپ از جمله است. گرامرهای LL گرامرهای مستقل از متنی هستند که از گرامرهای LR محدودتر هستند، با این وجود به دلیل سادگی و اجرای کارآمد در بین نویسندگان مترجم‌ها بسیار محبوب هستند. گرامرهای (LL(k می‌توانند با تجزیه‌کننده‌های بازگشتی نزولی که معمولاً با دست رمز می‌شوند، تجزیه شوند. مفهوم تجزیهٔ نزولی بازگشتی در ژانویه ۱۹۶۱ در CACM (گردهمایی ACM) در دو مقالهٔ جداگانه توسط ای.ای. نزولی بازگشتی توسط نیکلاس ورث و با PL/0 یک زبان برنامه‌نویسی علمی برای آموزش ساختار مترجم‌ها در دههٔ ۷۰، محبوب شد. تجزیهٔ LR زبان‌های بیشتری نسبت به تجزیهٔ LL پشتیبانی می‌کند و همچنین در گزارش خطا بهتر است، به عنوان مثال خطاهای نحوی را هنگامی که ورودی با گرامر مطابقت ندارد به سرعت تشخیص می‌دهد. تجزیه‌کننده‌های ارلی در سال ۱۹۷۰ جی ارلی تجزیه‌کننده‌ای را اختراع کرد که به تجزیه‌کننده‌های ارلی معروف است. این تجزیه‌کننده‌ها بسیار پرطرفدار هستند زیرا تمام گرامرهای مستقل از متن را به صورت بسیار کارآمد تجزیه می‌کنند. زبان‌های توصیف‌کننده گرامر جان بکوس «فرمول فرازبانی» را برای توصیف نحو زبان برنامه‌نویسی جدید IAL که امروزه با نام الگول ۵۸ شناخته می‌شود ارائه کرد(۱۹۵۹). گشترس‌های بعدی الگول منجر به الگول ۶۰ شد، پیتر نااور در گزارش خود (۱۹۶۳) نشانه‌گذاری بکوس را فرم نرمال بکوس (BNF) نامید و آن را با حداقل کردن کاراکترهای مورد استفاده ساده‌سازی کرد. هرچند دونالد کنوث استدلال کرده‌است که BNF می‌بایست به صورت فرم بکوس-نائور خوانده شود و این استدلال به صورت عمومی قبول شده‌است. نیکلاوس ویرت فرم بکوس-نائور توسعه‌یافته (EBNF) را تعریف کرده‌است که یک نسخه اصلاح شده از BNF در اوایل دهه ۶۰ برای PL/0 می‌باشد. هردوی EBNF و ABNF به کرار برای مشخص کردن گرامر زبان‌های برنامه‌نویسی، به عنوان وردی برای ژنراتورهای تجزیه گر مورد استقاده قرار می‌گیرد. سازنده‌های تجزیه گر یک سازنده تجزیه گر بخش تحلیل گر لغوی یک کامپایلر را ایجاد می‌سازد. یک برنامه که با دریافت توضیحات گرامر یک زبان برنامه‌نویسی خاص تجزیه گر آن زبان را ایجاد می‌کند. تجزیه گر، نمادها و کلید واژه‌های آن زبان خاص را در متن ورودی شناسایی کرده و این نشانه‌ها را به کدی که وظیفه تعیین ازرش نحوی و ترجمه به آبجکت کد را برعده دارد برمی‌گرداند. این بخش دوم کامپایلر می‌تواند با کامپایلر-کامپایلر ایجاد شود که قوانین اولیت شرح نحو رسم زبان را به عنوان ورودی می‌گیرد. اولین کامپایلر-کامپایلر برای استفاده به این نام توسط تونی بروکر در سال ۱۹۶۰ نوشته شد و برای ساخت کامپایلرهای برای کامپیوتر اطلس در دانشگاه منچستر مورد استفاده قرار گرفت، همانند کامپایلر اوتوکد اطلس. هر چند با کامپایلر-کامپایلرهای مدرن بسیار متفاوت بود، و کامپایلر-کامپایلر امروزه تعریفی مابین کامپایلر عمومی با قابلیت شخصی‌سازی بالا و یک زبان با قابلیت توصعه‌پذیری نحو آن می‌تواند داشته باشد. نام کامپایلر-کامپایلر برای سیستم بروکر به متراتب مناسب تر است تا کامپایلر-کامپایلرهای مدرن، که به صراحت با نام سازنده تجزیه گر نامیده می‌شوند. به اطمینان می‌توان گفت که نام کامپایلر-کامپایلر پس از یاک به صورت عمومی مورد استفاده گرفت هرچند کار بروکر همچنان حائز اهمیت است. نمونه دیگری از سازنده‌های تجزیه گر متا دو است که اولین بار در سال ۱۹۶۲ توسط وال شوور منتشر شد. متا دو گرامر و قاعد تولید کد را قبول می‌کرد و می‌توانست زبان خود و دیگر زبان‌ها را کامپایل کند. پروژه مالتیکس ریسک همکاری میان MIT و آزمایشگاه‌های بل، یکی از اولین‌ها برای گسترس یک سیستم عامل با استفاده از یک زبان سطح بالا بود، زبان انتخاب شده پی‌ال/۱ بود، اما یک کارپرداز خارجی نمی‌تواند کامپایلری برای کار تهیه کند. گروه مالتیکس پیاده‌سازی شخصی خود را از زبان PL/1 گشترش دادند که با نام EPL شناخته می‌شود. TMG روی سری GE-600 پورت شده بود و برای گسترش EPL توسط داگلاس مکلروی، رابرت موریس و دیگران مورد استفاده قرار گرفت. چندی بعد کن تامسون اولین نسخه یونیکس را برای PDP-7 در ۱۹۶۹ نوشت، داگ مکلروی اولین زبان سطح بالای سیستم جدید را ایجاد کرد: پیاده‌سازی مکلروی از TMG. TMG همچنین ابزار تعریف کامپایلری است که تامسون جهت پیاده‌سازی کامپایلر برای زبان بی برای PDP-7 در ۱۹۷۰ مورد استفاده قرار داد. XPL XPL یک پیاده‌سازی شخصی از زبان PL/1 است که در سال ۱۹۶۷ گسترش یافت و برای ساخت کامپایلر کامپایلرها مورد استفاده قرار گرفت. | ## بخش 3: تاریخچه ساخت مترجم | XPL توسط تیمی متشکل از ویلیام مک کیمن، جیمز هورینگ و دیوید ورتمن در دانشگاه استنفورد، دانشگاه کالیفورنیا و سانتا کروز طراحی و پیاده‌سازی شد. اولین رونمایی از آن در کنفرانس پاییزه کامپیوتر دانشگاه سانفرانسیسکو در سال ۱۹۶۸ بود. XPL به هردوی زبان برنامه‌نویسی و سازنده تجزیه گر LALR که برپایه همین زبان نوشته شده‌است گفته می‌شود. XPL یک سیستم نسبتاً ساده پایین به بالا است که توسط نویسندگانش لقب MSP (استراتژی اولویت مختلط) گرفته‌است. این سازنده تجزیه گر کامپایلرهای LALR(1) را که برپایه گرامرهای نوشته به فرمی شبیه فرم بکوس نائور ایجاد می‌کند. وی بسیار با TMG آشنا بود و تأثیرات آن را می‌توان در یاک و طراحی زبان برنامه‌نویسی C مشاهده کرد. از آنجایی که یاک سازنده کامپایلر پیش‌فرض در سیستم‌های یونیکس بود، بسیار گشترش یافته و مورد استفاده قرار گرفته‌است. ترجمهٔ تقابلی یک مترجم تقابلی در یک محیط اجرا می‌شود و برای یک محیط دیگر کد شی تولید می‌کند. مترجم‌های تقابلی در توسعه‌های جاسازی شده، در جایی که کامپیوتر هدف قابلیت‌های محدودی دارد. بهینه‌سازی مترجم‌ها بهینه‌سازی کامپایلر فرایند بهبود کیفیت کد بدون تغییر نتیجهٔ تولیدی آن است. هدف توسعه‌دهندگان اولین مترجم FORTRAN این بود که مترجم بتواند با سرعتی بیش از اسمبلرهای دستی کدها را اجرا کند، بدین ترتیب مشتریان از محصول آن‌ها استفاده کردند و آن‌ها در تلاش اولیه موفق شدند. سری IBM 360 دو مترجم جداگانه ارائه دادند: یک جستجوگر کد سریع در اجرا و یک بهینه‌ساز با سرعت پایین‌تر. فرانسیس آلن به تنهایی و به همراه جان کوک بسیاری از جنبه‌های بهینه‌سازی را معرفی کرد. مقالهٔ سال ۱۹۶۶ آلن، بهینه‌سازی برنامه، نمودار ساختمان داده‌ای برای رمز کردن محتوای برنامه برای بهینه‌سازی ارائه داد. مقالات وی در سال ۱۹۷۰، کنترل تجزیه و تحلیل جریان و پایه‌ای برای بهینه‌سازی برنامه، به عنوان زمینه‌ای برای تجزیه و تحلیل جریان داده‌های کارآمد و مؤثر منتشر شد. مقالهٔ مشترک وی با کوک در سال ۱۹۷۱، کاتالوگ بهینه‌سازی تحول، اولین شرح و اسلوبی از بهینه‌سازی تحولات را ارائه داد. مقالات سال‌های ۱۹۷۳ و ۱۹۷۴ وی بر تجزیه و تحلیل جریان داده‌ها، تحلیل را در کل برنامه گسترش داد. مقالهٔ مشترک او و کوک در سال ۱۹۷۶ یکی از دو استراتژی اصلی تحلیل است که امروز در بهینه‌سازی کامپایلرها استفاده می‌شود. این کار امکان و بنای ایجاد ماشین‌های مدرن و بهینه‌سازهای مستقل از زبان را به وجود آورد. تیم PTRAN او طرح‌های تشخیص موازی جدید و ایجاد مفهوم گراف وابستگی برنامه را توسعه داد، پایه‌های اولیه روش در همزمانی کامپایلرها استفاده شده‌است. شوارتز، که در اوایل ۱۹۷۰ منتشر شد، بیش از ۲۰۰ صفحه را به بهینه‌سازی الگوریتمها اختصاص داد. این کتاب شامل بسیاری از تکنیک‌های آشنا از جمله حذف کدهای تکراری و کاهش قدرت است. بهینه‌سازی روزنه‌ای بهینه‌سازی روزنه‌ای یک روش بهینه‌سازی ساده ولی تأثیرگذار است که اختراع ویلیام مک کیمن است و در سال ۱۹۶۵ در CACM منتشر شد. این نوع از بهینه‌سازها وابسته هستند، در این مورد، به آگاهی از ضعف‌های موجود در کامپایلر استاندارد IBM برای COBOL و در حقیقت بخشی از آبجکت کد را با کدی موثرتر جایگزین می‌کند یا کد مؤثر را به آن الحاق می‌کند کد جایگزین ممکن است یک جدول ارجاع خطی را با یک جستجوی دودویی یا گاهی یک دستورالعمل کند را با یک نوع سریعتر آن که عملکرد مشابه دارد جایگزین کند. به عنوان مثال بر روی سخت‌افزار IBM/360 دستورالعمل CLI به یک مدل خاص وابسته بود که برای مقایسه یک بایت بین دو بار و ۵ برابر سریع تر از یک دستور CLC بود. کامپایلرهای مدرن به‌طورمعمول گزینه‌های بهینه‌سازی را ارائه می‌دهند و برنامه نویسان می‌توانند انتخاب کنند که گذر بهینه‌سازی را اجرا کنند یا خیر. عیب یابی هنگامی که به یک کامپایلر یک برنامه‌ای داده می‌شود که از نظر نحوی نادرست است، نمایش یک پیغام خطای کوتاه و واضح بسیار مفید است. این کامپایلر برای ارائه پیغام خطای بهتر نسبت به کامپایلر فرترن IBM آن زمان، طراحی شده بود. علاوه بر این WATFIV بسیار کاربردی‌تر بود، به این دلیل که مراحل کامپایل، اجرا را در یک مرحله ترکیب کرده بود، در حالی که کامپایلر IBM برای اجرای این مراحل را در ۳ بخش جداگانه داشت! PL\C پی ال/سی یک زبان برنامه‌نویسی است که اوایل دهه ۱۹۷۰ در دانشگاه کرنل پدید آمد. در حالی که پی ال/سی زیرمجموعه زبان پی ال/آی IBM بود، برای هدف خاص آموزش برنامه‌نویسی طراحی شده بود. پی ال/سی برخی از ویژگی‌های پیچیده پی ال/آی را حذف کرد و امکان اشکال زدایی و بازیابی خطا به صورت وسیع را به آن اضافه کرد. این امکان غیرعادی با استفاده وسیع از تصحیح خودکار بسیاری از خطاهای نحوی و تبدیل هرگونه خطای باقی‌مانده به عنوان اعلامیه خروجی امکان‌پذیر شده بود. ترجمهٔ درجا مقاله اصلی:کامپایل درجا کامپایل درجا (JIT) یک اصطلاح است که در حال حاضر برای توصیف تولید کدهای اجرایی آنی یا به اندازه ممکن نزدیک به اجرای واقعی به کار می‌رود. دلیل وجود کامپایل درجا این است که از معیارهای نرم‌افزارسنجی زمان اجرا یا دیگر گزینه‌های بهبود کارایی استفاده شود. | ## جمع‌بندی | تولید کد مقاله‌ی اصلی: تولید کد (کامپایلر) یک تولیدکننده‌ی کد، دستورات ماشین را برای پردازنده‌ی مقصد تولید می‌کند.