لطفا برای نمایش محتوا اجرای جاوا اسکریپت را فعال کنید

ساختار کامپایلر | structure of compiler

 ·  ☕ 14 دقیقه بخوانید  ·  😎 victor

همینطور که در قسمت های قبل دیدیم اگر کامپایلر رو به یک جعبه تشبیه کنیم که یک برنامه مبدا (source program) رو به یک برنامه معادل با کارکرد یکسان تبدیل میکند اگر کمی این جعبه رو باز کنیم می بینیم که تمام مراحل کامپایلر از دو قسمت کلی تشکیل شده :

  • مراحل تحلیل | analysis
  • مراحل ساخت | synthesis

مراحل تحلیل (analysis)

مرحله تحلیل برنامه مبدا رو به اجزاء اصلی تقسیم میکند و ساختار گرامری رو در برنامه مبدا اعمال میکند سپس از روی این ساختار کد میانی (intermediate code) معادل رو تولید میکند در این مرحله کد تحلیل می شود و اگر خطا یا اروری وجود داشته باشد پیام های اخطار رو چاپ میکند تا کاربر کد خودش رو اصلاح بکند.
هم چنین در مرحله تحلیل اطلاعاتی درباره برنامه مبدا استخراج میشود و در یک ساختمان داده ای به نام جدول نماد symbol table ذخیره می شود که به همراه کد میانی تولید شده به مرحله ساخت پاس داده می شوند

مراحل ساخت (synthesis)

در بخش ساخت، از کد میانی که مرحله قبل تولید شده به همراه اطلاعات جدول نماد که خروجی مراحل تحلیل هستند یک برنامه نهایی (target program) ایجاد میشود.

به مراحل تحلیل اغلب Front End یا بخش جلویی کامپایلر گفته میشود
و به مراحل ساخت Back end یا عقب کامپایلر می گویند

اگر فرایند کامپایل رو دقیق تر بررسی کنیم می بینیم که این فرایند از فاز های پشت سرهم تشکیل شده و هر فاز کد مبدا رو بررسی میکند و به فاز بعد ارائه میکند برای مثال یک نمونه از تجزیه فاز های کامپایلر رو در شکل زیر می بینید

فاز های کامپایلر
فاز های کامپایلر: Phases of a compiler


در کنار جدول علائم یک بخش دیگر به نام کنترل کننده خطا یا error handler هم وجود دارد و فاز ها از آن استفاده می کنند
هم چنین بعضی از کامپایلر ها یک فاز بهینه سازی بین backend و frontend دارند که کد میانی تولید شده رو بهینه سازی میکند و این به backend کمک میکند تا برنامه نهایی بهینه تر باشد

تحلیل گر لغوی (Lexical Analyser)

به اولین فاز کامپایلر تحلیل لغوی یا اسکن scanning میگویند تحلیلگر لغت، تمام کاراکتر های برنامه منبع را می خواند و به صورت رشته های معنادار گروه بندی می کند به این رشته ها lexeme می گویند برای هر lexeme تحلیل گر لغت یک توکن Token به فرم زیر تولید می کند که این توکن به فاز بعدی یعنی تحلیلگر نحوی تحویل داده خواهد شد.

  • (token name , attribute value)
  • (مقدار توکن ، نام توکن)
  • انواع توکن | Token

    اولین جزء توکن token name یک نماد هست که به نوع توکن اشاره می کند و در analysis syntax یا تحلیلگر نحوی استفاده می شود. برای توضیح انواع توکن تکه کد زیر رو بررسی میکنیم و توکن های اون رو شناسایی می کنیم

    1
    2
    3
    4
    5
    6
    7
    8
    9
    
    int main(){
        int number = 5;
        if (number>10){
            result=number*60;
        }else{
    	printf("Error");
        }
        return 0;
    }
    

    1- ⠀key word⠀
    تمام دستورات برنامه نویسی که توسط زبان رزرو شده اند جزء این دسته قرار می گیرند
    [ if , int , else , printf , return]

    2- ⠀Identifier | id⠀
    هر اسمی که توسط برنامه نویس تعریف بشود مثل اسم متغیر ، اسم تابع، اسم کلاس ، نام ماکرو ، اسم یک ساختمان داده ، اسم آرایه و …
    [ number , result , main]

    3- ‎‎‏‏‎‎⠀operator⠀
    عملگرها نوع دیگر توکن هستند که شامل عملگر های زبان برنامه نویسی مثل عملگر های ریاضی و انتساب می شود.
    [ * , > , = ]

    4- ⠀Number⠀
    مقادیر عددی که در برنامه های خود مینویسیم هم نوع دیگر توکن به حساب میاد
    [ 5 , 10 , 60 , 0 ]

    5- ⠀symbol⠀
    همچنین علائم جز جدا نشدنی برنامه های ما هستن مثل ; یا پرانتزها و کرلی براکت و.. که در مثال بالا علائم ما مقادیر زیر هستند.
    [ ; , { , } , ( , ) ]

    6-⠀string⠀
    آخرین نوع توکن رشته ها یا آرایه ای از کاراکترها هستند که معمولا بین دو " قرار میگیرند
    [ "Error" ]

    تشخیص Token

    برای تشخیص دادن الگوی توکن های موجود در برنامه مبدا، از علم نظریه زبان ها و زبان های منظم در کامپایلر استفاده می شود

    جزء دوم توکن attribute-value هست که به موجودی برای این توکن در جدول علائم یا symbol table اشاره می کند همچنین برای semantic analysis یا تحلیل معنایی و تولید کد اسمبلی به اطلاعاتی که در symbol table ذخیره شده اند نیاز داریم برای مثال فرض کنید در برنامه مبدا دستور زیر وجود دارد مراحل کامپایل این دستور رو مرور می کنیم

    position = initial + rate * 60
    

    همینطور که مشخص هست این دستور شامل 7 گروه کاراکتر معنا دار یا 7 lexeme هست هر کدام رو به صورت جداگانه بررسی می کنیم
    1- متغیر position به عنوان یک lexeme توسط کامپایلر شناسایی می شود و از آنجا که یک توکن از نوع identifier هست به توکن < 1 , id > نگاشت میشود. id اشاره به نوع توکن دارد و 1 اشاره به ردیف اول symbol table دارد که اطلاعات مربوط این lexeme مثل اسم متغیر و نوع و… در آن ذخیره شده است.

    2- نماد مساوی = هم کاراکتر معنا دار و lexeme دوم در دستور بالا هست و به توکن < = > نگاشت می شود اما از آنجا که نوع توکن عملگر هست نیازی به attribute ندارد. همچنین میتوانیم برای عملگر مساوی از نام assign استفاده کنیم ولی برای راحتی کار، از خود کاراکتر مساوری به عنوان نام توکن استفاده می کنیم.

    3- همینطور initial یه عنوان یک lexeme به توکن < 2 , id > نگاشت می شود و 2 به موجود دوم symbol table اشاره می کند که اطلاعات متغیر initial رو ذخیره کرده است.

    4- عملگر + هم یک lexeme بعدی هست و به توکن < + > نگاشت می شود.

    5- متغیر rate هم به عنوان lexeme پنجم به توکن < 3 , id > نگاشت می شود و 3 به خانه سوم symbol table اشاره می کند که اطلاعات متغیر rate در آن ذخیره شده است.

    6- عملگر * هم به عنوان یک lexeme به توکن < * > map (نگاشت) می شود.

    7- عدد 60 آخرین lexeme دستور بالا به توکن <60> نگاشت می شود.

    کاراکتر های خالی که بین lexeme ها فاصله ایجاد کرده اند توسط تحلیلگر لغوی نادیده گرفته می شوند دستور انتساب یا (assignment statement) بالا بعد از تحلیل لغوی به ترتیبی از توکن ها تبدیل می شود

    <id,1>  < = >  <id,2>  < + >  <id,3>  < * >  <60>
    

    در مثال ما نام های = و + و* برای راحتی در توکن ها به عنوان نام های معادل assignment و addition و multiplication استفاده شده اند.

    کامپایل دستور انتساب
    کامپایل یک دستور انتساب: translation of an assignment statement

    تحلیل گر نحوی (Syntax analyser)

    فاز دوم کامپایلر syntax analyzer یا پارس parsing نام دارد. پارسر parser از اولین جزء توکن که توسط تحلیلگر لغوی تولید شده استفاده می کند و یک درخت از ترتیب قرار گیری توکن ها می سازد به این درخت syntax tree می گویند. این درخت ساختار گرامری یک دستور رو بر اساس توکن ها نشون میده در واقع در این درخت برگ ها عملوند هستند و راس های آن ها عملگر هستند که اولویت عملگر ها رو هم نشان می دهد طبق درخت تولید شده در مثال ما اول باید عدد 60 در توکن <3 , id> که همان متغیر rate هست ضرب شود و نتیجه آن با توکن < 2 , id > که همان initial هست جمع شود و سپس در توکن < 1 , id > که همان position هست ریخته شود تحلیل گر نحوی چک میکند که ترتیب قرار گیری توکن ها درست باشد به عبارتی دیگر دستور ما طبق الگوی از قبل تعریف شده باشد و سپس درخت سینتکس رو به عنوان خروجی به فاز بعدی یعنی تحلیلگر معنایی یا semantic تحویل می دهد. این کار با استفاده از زبان های مستقل از متن انجام می شود

    تحلیلگر معنایی (Semantic Analysis)

    تحلیلگر معنایی از درخت سینتکس که در مرحله قبل تولید شد و اطلاعات symbol table استفاده می کند تا برنامه مبدا رو از نظر معنایی بررسی کند و اطلاعاتی رو در جدول نماد و درخت ذخیره میکند تا در مرحله بعد از آن برای تولید کد میانی استفاده شود

    type checking

    یکی از قسمت های مهم تحلیلگر معناییtype checking هست کامپایلر چک می کند که آیا هر عملگر عملوند مناسب داشته باشد برای مثال هر زبان برنامه نویسی چک میکند که اندیس آرایه از نوع int یا عدد صحیح باشد و اگر عدد اعشاری برای اندیس آرایه استفاده شده باشد خطایی نمایش می دهد گاهی اوقات کامپایلر اجازه میدهد که نوع بعضی متغیر ها به دیگری تبدیل شود مثلا در دستوری که دیدیم فرض کنید position و initial و rate به عنوان متغیر عدد اعشاری تعریف شده باشند از آنجا که عدد 60 از نوع int هست type checker بعد از دیدن عملگر * و بررسی عملوند ها می فهمد که باید یک عدد صحیح (rate) در یک عدد اعشاری ضرب شود در این حالت ممکن است عدد صحیح به عدد اعشاری تبدیل شود در شکل بالا توجه کنید که خروجی تحلیلگر معنایی یک node اضافی برای عملگر inttofloat دارد که مستقیما عدد صحیح یا int رو به عدد اعشاری یا float تبدیل می کند.

    تولید کننده کد میانی (Intermediate Code Generation)

    در فرایند ترجمه یک برنامه مبدا (source program) به برنامه مقصد (target code) کامپایلر ممکن هست چندین بار یک کد میانی با اشکال مختلف بسازد. درخت سینتکس (syntax tree) در واقع بیان گر کد میانی هست.
    بیشتر کامپایلر ها بعد از تحلیل نحوی و معنایی کد مبدا، یک کد سطح پایین یا کد ماشین شبیه به کد اسمبلی تولید میکنند این کد دو ویژگی مهم باید داشته باشد

    • باید تولید آن آسان باشد
    • باید به راحتی به کد ماشین نهایی ترجمه شود

    کد های سه آدرسی (three-address code)

    یک مدل کدمیانی که بررسی خواهیم کرد کد های سه آدرسه و شبیه اسمبلی هستند که هر دستور العمل آنها شامل سه عملوند می باشد هر عملوند می تواند نقش یک رجیستر رو بازی کند. برای مثال خروجی یک تولید کننده کد میانی ( intermediate code generator ) شامل دستورات سه آدرسه در زیر آمده است.

    t1 = inttofloat(60)
    t2 = id3 * t1
    t3 = id2 + t2
    id1 = t3
    

    کد سه آدرسه بالا در هر دستور العمل انتساب (assignment) یا (دستور العملی که مقداری رو در یک متغیر ذخیره میکند) حداقل یک عملگر وجود دارد . طبق اولویت عملگر ها در مثال ما دستورات کد میانی از بالا به پایین مرتب می شوند مثلا چون عملگر ضرب اولویت بیشتری نسبت به جمع داره زودتر اجرا میشه در این مرحله کامپایلر نام های موقتی برای نگه داشتن مقادیر حساب شده توسط کد های سه آدرسه تولید می کند همانطور که مشخص هست دستورات اول و آخر کمتر از سه عملوند (operand) دارند

    بهینه سازی کد (code optimization)

    فاز بهینه ساز کد (code optimizer) تلاش میکند تا کد میانی تولید شده رو بهینه تر کند تا کد ماشین در نهایت نتیجه بهتری داشته باشد برای مثال درصورت تشخیص بهینه ساز ممکن است ترد (thread) جدید برای اجرا به برنامه اضافه کند تا سرعت اجرا بالاتر برود یا مثلا بهینه ساز میفهمد که دستور inttofloat برای تبدیل عدد صحیح به اعشاری جواب یکسان دارد پس برای جلوگیری از اجرای آن در هر بار این عدد رو با 60.0 در زمان کامپایل تعویض میکند در نتیجه محاسبه عدد اعشاری در زمان اجرا انجام نمی شود همینطور بهینه ساز تشخیص میدهد که t3 فقط یکبار استفاده شده تا مقدار خودش رو در id1 بریزد و کد میانی تولید شده میتواند کوتاه تر باشد در نتیجه کد بالا میتواند به شکل زیر کوتاه تر شود

    t1 = id3 * 60.0
    id1 = id2 + t1
    

    البته این یک مثال ساده هست برای فهم این موضوع ، واضح هست که کامپایلر ها در بهینه سازی اعمالی که انجام می دهند ممکن هست متفاوت و پیچیده تر باشد

    تولید کننده کد (Code generator)

    تولید کننده کد به عنوان ورودی کد میانی که توسط برنامه مبداء تولید شده رو تحویل میگیرد و به زبان مقصد نگاشت می کند اگر زبان مقصد زبان ماشین باشد رجیستر ها و خانه های حافظه توسط متغیر های برنامه انتخاب می شوند سپس دستورالعمل های میانی هرکدام ممکن است به چندین دستوالعمل زبان ماشین ترجمه بشوند یکی از مهم ترین وظایف این فاز تخصیص دادن رجیستر ها برای نگهداری متغیر ها هست برای مثال استفاده از رجیستر های R1 و R2 ، در این مرحله کد میانی بهینه شده که از فاز قبلی تحویل گرفته شده به کد اسمبلی زیر تبدیل می شود

    1
    2
    3
    4
    5
    
    LDF	R2,	id3
    MULF	R2,	R2,	#60.0
    LDF	R1,	id2
    ADDF	R1,	R1,	R2
    STF	id1,	R1
    

    اولین عملوند یا operand هر دستور نشان دهنده مقصد است (یعنی نتیجه این دستور در رجیستری که مشخص شده ریخته میشود مثلا در دستور اول عملوند اول R2 هست یعنی id3 در R2 بارگزاری میشود) حرف F در هر دستور بیان گر این هست که نوع متغیر یک عدد float یا اعشاری هست.

    توضیح کد اسمبلی بالا

    کد بالا اول محتوای آدرس id3 رو در رجیستر R2 بارگزاری (load) میکند سپس محتوای رجیستر R2 رو با عدد اعشاری ثابت 60.0 ضرب می کند و نتیجه رو دوباره در رجیستر R2 می ریزد علامت # بیانگر این هست که عدد 60 ثابت هست. سومین دستور متغیر id2 رو در رجیستر R1 بارگزاری می کند و چهارمین دستور رجیستر R1 و R2 (که نتیجه ضرب 60.0 و id3 داخلش هست) رو با هم جمع می کند و نتیجه رو در رجیستر R1 می ریزد و در نهایت مقداری که در رجیستر R1 هست در آدرس id1 ذخیره می شود و میبینید که دستور سطح بالای ما چگونه طی فاز های مختلفی به دستور زبان ماشین و سطح پایینی تبدیل شد البته در این بحث مسائل مهم تخصیص حافظه یا ( storage allocation ) برای متغیر ها نادیده گرفته شده اگر در آینده مبحث رو جلو بردیم می بینیم که سازماندهی حافظه در زمان اجرا بستگی به زبانی که کامپایل شده دارد و همچنین تصمیمات تخصیص دادن حافظه در حین تولید کد میانی یا کد نهایی گرفته می شود.

    مدیریت جدول علائم (Symbol-Table Management)

    یکی از توابع مهم یک کامپایلر این هست که نام متغیر هایی که در برنامه مبدا استفاده شده اند رو در جایی ثبت کند و اطلاعات ویژگی های مختلف هر نام رو استخراج کند این صفات و ویژگی ها (attributes) ممکن است اطلاعاتی در باره تخصیص حافظه برای نام و نوع و محدوده یا scope یک متغیر (جایی که در برنامه ممکن است از مقدار آن استفاده شود) فراهم کنند.
    در واقع symbol table یک ساختمان داده شامل یک سط (record) برای هر نام متغیر با ستون هایی (fields) برای ویژگی های (attributes) آن اسم است. هر کامپایلر باید این ساختمان داده رو داشته باشد تا کامپایلر بتواند سریعا به ویژگی و اطلاعات یک متغیر دسترسی پیدا کند

    گروه بندی فاز ها (The Grouping of Phases into Passes)

    طبق مباحث گذشته دیدیم که یک کامپایلر با فازبندی قسمت های مختلف منطق خود را سازماندهی میکند. فعالیت های مختلف فاز ها در کامپایلر ممکن است به شکل گروهی در یک پاس pass یا دور انجام بشوند مثلا فاز های جلویی (front-end phases) مثل تحلیل لغوی ، نحوی، معنایی و تولید کد میانی ممکن است باهم در قالب یک گروه از فعالیت ها در یک پاس انجام بشوند. بهینه سازی کد ممکن است یک پاس اختیاری باشد بعد از آن فاز های پشتی (back-end phasses) شامل فاز تولید کننده کد (code generation) میتواند در یک پاس دیگر برای ماشین مقصد (target machine) اجرا شود.

    بعضی از مجموعه کامپایلر ها (compiler collections) که دقیق و بهینه ساخته شده اند ، کد میانی طراحی کرده اند که اجازه می دهد فازهای جلویی یا (front-end) برای یک زبان مخصوص به عنوان رابط کاربری از یک back-end برای تولید کد نهایی روی ماشین مقصد استفاده کند با این مجموعه ها ما می توانیم کامپایلر هایی برای زبان های مختلفی تولید کنیم که روی یک ماشین کامپایل بشوند برای مثال در سیستم عامل لینوکس کامپایلری که برای زبان C وجود دارد (GCC (GNU Compiler Collection نام دارد می توانیم front-end یک زبان دیگر با syntax متفاوت رو تولید کنیم و با back-end کامپایلر GCC درکنار هم قرار دهیم با این کار، فاز های جلویی کامپایلر، کد میانی تولید شده را به back-end کامپایلر GCC می دهد و back-end کامپایلر GCC کد زبان ماشین را تولید میکند که قابل اجرا در توزیع های لینوکسی هست.
    همچنین می توانیم برای ماشین های مختلف چندین back-end رو با front-end یک زبان ترکیب کنیم و کامپایلری بسازیم که برای ماشین های مختلف زبان ماشین قابل اجرا تولید کند.

    اشتراک گذاری این پست

    victor
    نوشته شده توسط
    victor
    Back End Developer