Description

به نام خدا
فاز چهارم پروژه کامپایلرها و زبانهای برنامهنویسی

پاییز 99
مهلت تحویل: 42 دی

در این فاز بخشهای مربوط به تولید کد را به کامپایلر خود اضافه میکنید. در انتهای این فاز، کامپایلر شما به طور کامل پیادهسازی شده و برنامههای نوشته شده به زبان Sophia را به کد قابل اجرا توسط ماشین تبدیل میکند. پیادهسازی شما باید به ازای هر فایل ورودی به زبان Sophia، بایت کد معادل آن را تولید کند. در تستهای این فاز، صرفا قابلیت تولید کد کامپایلرتان سنجیده میشود و ورودیها دارای خطاهای نحوی و معنایی که در فازهای قبل بررسی کردید نیستند؛ اما توجه کنید که شما برای تولید کد به اطلاعات جمع آوری شده در جدول علائم و اطلاعات مربوط به تایپ نودهای درخت AST نیاز دارید.
اسمبلر
جهت تولید فایلهای class. نهایی از شما انتظار نمیرود که فایل باینری را مستقیما تولید کنید.
برای این کار میتوانید از اسمبلر jasmin که در کلاس معرفی شده است استفاده کنید.
تساوی اشیاء
برای تایپهای int و boolean آنها را با استفاده از مقادیرشان با دستور if_icmpeq مقایسه میکنیم و برای تایپهای دیگر از دستور if_acmpeq برای مقایسه استفاده میکنیم.
عملگرهای && و ||
شما باید این عملیات را به صورت short-circuit پیادهسازی کنید.

نکات کلی پیادهسازی
 برای آن که لیست multi-type را در جاوا داشته باشیم نیاز داریم که یک لیست از جنس Object )که والد تمام کلاسها است( داشته باشیم تا هر نوعی را بتوان در آن ذخیره کرد. کلاسهای جاوا مانند Integer و Boolean، از Object ارث میبرند و بنابراین میتوان آن ها را در لیستی از Object ذخیره کرد. ولی تایپ int و boolean که تایپهای primitive هستند را نمیتوان در این لیست ذخیره کرد. بدین منظور تایپهای int و boolean را در expression ها باید از نوع primitive استفاده کنیم تا بتوان operator ها را روی آنها اعمال کرد و در نهایت آنها را به غیر primitive تبدیل کنیم تا بتوانیم آنها را در لیستها ذخیره کنیم. در ادامه جزئیات این تبدیل توضیح داده میشود.
 نوع بازگشتی ویزیتورهای CodeGenerator از نوع String قرار داده شده است. میتوانید در هر ویزیتور یا command های تولید شده توسط آن ویزیتور را مستقیما با addCommand در فایل اضافه کنید یا اینکه مجموعه command ها را که به صورت string هستند و با n جدا شده اند return کنید و در تابع دیگری آنها را به فایل اضافه کنید. پیشنهاد میشود ویزیتورهای expression مجموعه command هایشان را return کنند و دیگر ویزیتورها با گرفتن آن command ها آنها را در فایل اضافه کنند.
 در کلاسها و متدها، نوع تمام تایپهایprimitive مانندint یاbool یاstring را از نوعهای غیرprimitive جاوا تولید کنید. یعنی در بایت کد تولید شده باید این متغیرها از نوعهایInteger یاBoolean یاString باشند که درjava/lang هستند.
 برایboolean ها در استک، اگرtrue باشد 1 و اگرfalse باشد 0 اضافه کنید.
 برای اضافه کردن مقادیرprimitive به استک، از دستورldc استفاده کنید. برای string quotation )””( آن را هم در دستورldc بیاورید.
 برای انجام محاسبات مانندadd یاor رویInteger یاBoolean باید آنها از نوع primitive یعنیint یاbool باشند. پس در تمامexpression ها از نوعprimitive این دو تایپ استفاده کنید و در هنگام نوشتن آنها در یک متغیر یا پاس دادن به توابع یا ریترن شدن آنها، این دو تایپ را ازprimitive به غیرprimitive تغییر دهید. همچنین بعد از خواندن این دو نوع از متغیر یا لیست باید تبدیل انجام شود. دلیل تبدیلها آن است که در تعریف، متغیرها از نوع غیرprimitive تعریف شدهاند و درexpression ها ما نیاز به primitive داریم (توابعjasmin برای تبدیل آنها در ادامه آمده است).
 طول stack و locals را در متدها 128 قرار دهید.
 فایلهایFptr.j وList.j در اختیارتان قرار گرفته اند و برای کار با لیستها وFptr ها باید از این دو کلاس آماده استفاده کنید. همچنین معادلjava آنها نیز داده شده است تا بتوانید متدهای آنها را مشاهده کنید که چه کاری انجام میدهند. برایFptr در هنگام
4

دسترسی به متد یکی از این کلاس ساخته میشود وinstance و نام متد در آن قرار داده میشود. سپس در هنگامcall شدن متد باید تابعinvoke از این کلاس را با آرگومانهای پاس داده شده صدا بزنید. توجه داشته باشید که باید آرگومانها را در یکArrayList ذخیره کرده و به این تابع پاس دهید.
 تمامvalue های لیست هنگام پاس داده شدن به تابع یا assign شدن در یک لیست جدید کپی میشود. برای این کار ازconstructor دوم کهcopy constructor است استفاده کنید. همچنین برای گرفتن یا ست کردن المان میتوانید از توابع مربوطه استفاده کنید. توجه داشته باشید که خروجیgetElement یکObject است و بعد از استفاده از این تابع باید خروجی را به تایپ المانی که گرفته ایدcast کنید )دستورcast در jasmin در ادامه آورده شده است).
 در ابتدای هر نوع constructor ای )default constructor یا تعریف شده(، ابتدا فیلدهای آن کلاس باید initialize شوند. مقادیر را به صورت زیر در نظر بگیرید: برای int مقدار صفر، برای string مقدار “”، برای bool مقدار false، برای class یا Fptr مقدار null و برای لیست یک instance از کلاس List که داخل element های آن متناسب با تایپهای تعریف شده برای آن لیست، دوباره به صورت بازگشتی مقداردهی میشوند.
 در صورتی که ObjectOrListMemberAccess داشته باشیم که عضو یک لیست با نام المان گرفته شده، باید index آن را پیدا کرده و از آن استفاده کنیم.
 نام کلاسها (مثلا درsignature ها یا در هنگامcast ) به صورت زیر است:
IntType → java/lang/Integer ListType → List
BoolType → java/lang/Boolean FptrType → Fptr StringType → java/lang/String ClassType → ClassName
 در اضافه کردنcommand ها حواستان به n ها باشد تاcommand ها پشت هم در فایلjasmin نباشند. همچنین هرcommand ای که اضافه میکنید به طور دقیق بررسی کنید که چه آرگومانهایی لازم دارد و چه چیزی ریترن میکند؛ زیرا اگر اشتباهی رخ دهد debug کردن آن در فایلهایjasmin کار دشواری است. برای راحت ترdebug کردن و فهمیدن فایلهایjasmin بهتر است آنها را مرتب بسازید؛ مثلا بین متدها یک خط خالی بگذارید تا مشخص باشند.
 برای مشاهده مجموعه دستورات بایت کد به این لینک میتوانید مراجعه کنید.

نکات ویزیتورها و توابع
slotOf
در این تابع برای متغیرها باید slot آنها را برگردانید. slot صفر به صورت پیشفرض برای خود کلاس )this( است و بعد از آن باید به ترتیب آرگومانهای تابع و local variable ها باشند. طوری این تابع را پیادهسازی کنید که اگر ورودی یک string خالی بود، یک slot بعد از تمام slot های مخصوص variable ها برگرداند. این برای استفاده از یک متغیر temp در code generation استفاده میشود؛ یعنی یک متغیر که برای تبدیل سوفیا به جاوا اضافه شده است.
توجه کنید که ممکن است یک تابع به چند temp variable نیاز داشته باشد.

addDefaultConstructor
یکdefault constructor به فایل اضافه کنید. فیلدهای کلاس بایدinitialize بشوند و constructor والد نیز صدا شود.

addStaticMainMethod
یک متدstatic main به فایل اضافه کنید. این متد توسط جاوا شناسایی شده و ابتدا این تابع در پروژه اجرا میشود. در این تابع باید از کلاسMain یکinstance بگیرید وconstructor آن را صدا بزنید) خود این تابع در فایل کلاسMain قرار میگیرد.(

Program
Expression و Code Generator را در current class .همهی کلاسها ویزیت شوند
.ست کنیدType Checker

2
ClassDeclaration
فایل کلاس متناظر را با تابع createFile بسازید و سپس header مربوط به کلاس را اضافهکنید. اگر کلاس parent نداشت، parent آن را java/lang/Object قرار دهید. سپس فیلدها را ویزیت کنید. اگر constructor دارد آن را ویزیت کنید و در غیر این صورت یک default constructor اضافه کنید. در نهایت متدها را ویزیت کنید. قبل از ویزیت کردن متد یا
Expression Type و Code Generator را در current method ،constructor
.ست کنید Checker

ConstructorDeclaration
اگر constructor حداقل یک آرگومان میگیرد باید یکdefault constructor علاوه بر آن constructor به کلاس اضافه شود. یعنی تمام کلاسها دقیقا یک constructor بدون آرگومان و یک یا صفر constructor با آرگومان خواهند داشت. اگر کلاسmain است باید
.هم به کلاس اضافه شود static main method یک

MethodDeclaration
header های مربوطه را متناسب یا متد یا constructor بودن اضافه کنید. اگر constructor است، constructor والدش را صدا زده و فیلدهایش را نیز initialize کنید )اگر والدی نداشت constructor کلاس Object باید صدا زده شود(. سپس متغیرهای local را ویزیت کنید و initialize کنید )آرگومانها را initialize نکنید(. سپس statement ها را ویزیت کنید. دقت کنید که اگر تابع ریترن نمیکند، نیاز است که حتما یک دستور return در انتهای command های متد قرار داده شود. برای اینکه بفهمید متد ریترن میکند یا خیر از getDoesReturn روی methodDeclaration استفاده کنید که در فاز قبل )در بخش امتیازی( ست شده است.

FieldDeclaration
دستورات مربوط بهfield اضافه میشوند.

VarDeclaration
دستورات مربوط بهinitialize کردن متغیر با توجه به تایپ آن اضافه میشوند.

AssignmentStmt
در این قسمت میتوانید از رویassignment statement یکnode از جنس
assignment expression ساخته و آن را ویزیت کنید. توجه داشته باشید که باید در انتهای
.کنید pop قرار میدهد را stack روی assignment expression ویزیت مقداری که

BlockStmt
تمامstatement ها را ویزیت کنید.

ConditionalStmt
دستورات مورد نیاز برای یک شرط را اضافه کنید.

MethodCallStmt
میتوانیدmethodCall داخل آن را ویزیت کنید و خروجی آن راpop کنید. توجه داشته باشید که قبل و بعد از ویزیت متد کال،
expressionTypeChecker.setIsInMethodCallStmt را صدا بزنید و در ابتدا آن را true و در انتها آن راfalse کنید که هنگام استفاده ازexpressionTypeChecker در ویزیتورها، مشکلی پیش نیاید.

PrintStmt
توابع مورد نیاز print را اضافه کنید. با استفاده ازexpressionTypeChecker میتوانیدتایپ آرگومان را بگیرید و از signature مناسب برای print استفاده کنید. جهت نوشتن بر روی صفحهی نمایش باید از print در کتابخانهی PrintStream.io.java استفاده کنید.

ReturnStmt
دستورات مربوط به ریترن را اگرvoid نیست اضافه کنید. توجه کنید که اگرexpression جلویreturn از نوعIntType یاBoolType است، ابتدا باید ازprimitive به غیر
.تبدیل شود primitive

BreakStmt
به label خروج حلقهی فعلی بروید.

ContinueStmt
به label شروع حلقهی فعلی بروید.

ForeachStmt
بایدforeach را بهfor تبدیل کنید. برای این کار یکslot برای یکtemp variable که متغیر حلقه خواهد بود بگیرید )این متغیر از جنس int است(. سپس معادلforeach را که یک for روی یک لیست است بیابید وcommand های قسمتهای مربوط بهinitialization متغیر حلقه، شرط حلقه )متغیرtemp گرفته شده از طول لیست پیمایش شونده کمتر باشد(، update )اندیسtemp از آرایه گرفته شده با تابعgetElement در کلاسList و در پیمایش کننده ریخته شود وcast کردن بعد از آن فراموش نشود وtemp هم باید آپدیت شود) وbody را باید اضافه کنید.
ForStmt
مانند قسمت قبلcommand های مناسب را اضافه کنید. توجه داشته باشید که هر یک از
.میتواند وجود نداشته باشد update یا condition یا initialization

BinaryExpression
برای هر یک از عملگرها دستورات مناسب را اضافه کنید. برای assign، ابتدا بررسی کنید اگر list داردassign میشود، بعد از مجموعه دستوراتoperand سمت راست، دستوراتی اضافه کنید که از این لیست که توسط دستوراتoperand دوم بهstack اضافه شده، یک لیست کپی ساخته شود) باcopy constructor در کلاسList ). سپس با توجه به اینکه سمت چپ
identifier یاListAccessByIndex یاObjectOrListMemberAccess است، دستوراتassign را اضافه کنید. در حالتObjectOrListMemberAccess دوباره دو حالت اینکهinstance آنListType باشد یاClassType داریم که باید جداگانه پیادهسازی شوند. توجه داشته باشید کهassign باید مقدار حاصل از دستوراتoperand سمت راست را که داخلoperand سمت چپ ذخیره میشود در نهایت درstack قرار دهد.

UnaryExpression
برای هر یک از عملگرها دستورات مناسب باید اضافه شوند. توجه کنید که برای predec، preinc ،postdec و postinc دوباره همان تقسیمبندیهای assign را داریم؛ زیرا این دستورات یک مقدار جدید به آن متغیر میدهند.

ObjectOrListMemberAccess
بررسی میشود که اگر نوعinstance آن کلاس است، متناسب با اینکه آن ممبرfield یا متد است کد مناسب ساخته شود. اگر هم که لیست است کد مناسب باید ساخته شود.

Identifier
ازslot متناسب با آنidentifier باید مقدارload شود )باaload ). سپس اگر نوع آنint
.شود primitive است تبدیل به bool type یا type

ListAccessByIndex
با استفاده ازgetElement آن اندیس مورد نظر گرفته شده و سپس به تایپ مناسبcast میشود و اگرint یاboolean است دوباره بهprimitive تبدیل میشود.

MethodCall
یکArrayList ابتداnew شده و مقادیر آرگومانها بعد از visit، به این لیستadd میشود )باjava/util/ArrayList/add ) و سپس با استفاده از این لیست تابعinvoke ازinstance صدا زده میشود. در نهایت خروجی آن به تایپ مناسبcast شده و در صورتboolean یا int بودن تبدیل به غیر primitive میشود. توجه داشته باشید آرگومانها بعد ازvisit شدن و قبل از اضافه شدن به ArrayList، اگرint یاbool هستند باید به غیرprimitive تبدیل شوند.

NewClassInstance
بعد از قرار دادن آرگومانهای constructor روی stack، آنconstructor صدا زده میشود.
توجه داشته باشید آرگومانها بعد ازvisit شدن، اگرint یاbool هستند باید به غیرprimitive تبدیل شوند )زیرا نوع آرگومان تابعی که صدا زده میشود مثلاInteger است نه int(.

ThisClass
reference به خود کلاس باید رویstack قرار داده شود.

ListValue
در این قسمت باید یکArrayList جدید ساخته شده و آرگومانها پس ازvisit شدن و تبدیلشدن به غیرprimitive به آن اضافه شوند. سپس با استفاده از اینArrayList یکList ساخته شود )با استفاده از constructor اول کلاس List(.

NullValue
مقدارnull باید رویstack گذاشته شود.

IntValue
باldc باید مقدار آن رویstack گذاشته شود.

BoolValue
باldc باید مقدار آن )0 یا 1( رویstack گذاشته شود.

StringValue
با ldc باید مقدار آن )همراه quotation( روی stack گذاشته شود.

دستورات کاربردی jasmin
Integer به int تبدیل
invokestatic java/lang/Integer/valueOf(I)Ljava/lang/Integer;
Boolean به bool تبدیل
invokestatic java/lang/Boolean/valueOf(Z)Ljava/lang/Boolean; int به Integer تبدیل
invokevirtual java/lang/Integer/intValue()I
bool به Boolean تبدیل
invokevirtual java/lang/Boolean/booleanValue()Z
اضافه کردن به ArrayList
invokevirtual java/util/ArrayList/add(Ljava/lang/Object;)Z
ArrayList گرفتن سایز
invokevirtual java/util/ArrayList/size()I
A به یک کلاس Object یک (cast) تبدیل
checkcast A

دستورات تبدیل و اجرای کدها
کامپایل کردن فایلjava . به به فایل class.
javac -g *.java
اجرای فایلclass. در نهایت بایدMain.class اجرا شود
java Main
تبدیل فایل بایت کدjasmin (.j) به فایل class.
java -jar jasmin.jar *.j
تبدیل فایلclass . به بایت کد جاوا )نهjasmin ) که خروجی در ترمینال نمایش داده میشود
javap -c -l A
تبدیل فایلclass . به بایت کدjasmin که خروجی در ترمینال نمایش داده میشود
java -jar classFileAnalyzer.jar A.class
تبدیلclass . به کد جاوا
drag the .class file to intellij window

میتوانید با استفاده از دستورات بالا برای هر کد سوفیا که میخواهید معادل jasmin آن را پیدا کنید به این صورت عمل کنید که ابتدا معادل java آن کد سوفیا را بنویسید. سپس آن فایل جاوا را کامپایل کنید که class. تولید شود. سپس این فایل را با classFileAnalyzer به بایت کد jasmin تبدیل کنید. فقط به این نکته توجه کنید که این classFileAnalyzer یک پروژه از github بوده و لزوما خروجی صحیحی نمیدهد و باید بررسی شود )در اکثر موارد خروجی درست میدهد مگر چند مورد خاص(.

14
نمونه خروجی
نمونه خروجی حاصل از کامپایل و اجرای صحیح کد نمونه شماره 4 )که در اختیارتان گذاشته شده است( به صورت زیر است:

 در این فاز شما باید کد visitor مربوط به CodeGenerator که بخشی از آن به شما داده شده را تکمیل کنید .در نهایت تنها یک فایل CodeGenerator.java )بدون تغییر نام( آپلود کنید. توجه شود که تنها یک نفر از هرگروه باید پروژه را آپلود کند. در صورت عدم رعایت این موارد از شما نمره کسر خواهد شد.
 در صورت کشف هر گونه تقلب، نمره 100- لحاظ میشود.
 دقت کنید که خروجی برنامه شما به صورت خودکار تست میشود.
 در صورتی که قبل از کلاسهای رفع اشکال سوالی برایتان پیش آمد، میتوانید زودتر آنها را بپرسید تا ابهامات شما در ابتدای زمان پروژه برطرف شود و به ساعات پایانی موکول نشود .بهتر است سوالات خود را در فروم یا گروه درس مطرح نمایید تا دوستانتان نیز از آنها استفاده کنند؛ در غیر این صورت به مسئولان پروژه ایمیل بزنید:
amir.pma1378@gmail.com امیر پورمحمدعلی shbmobina@gmail.com مبینا شاهبنده