[drblack]

دیروز وقتم رو کامل گذاشتم روی مسئله ارزیابی عبارت ها (expression evaluation).
خوب فرض کنید ما یه رشته داریم که حاوی یه عبارت ریاضیه (فعلا) مثلا : 4 * 2 + 1
باید الگوریتمی طراحی کنیم که این رشته رو بگیره و حاصل اون که عدد 9 هست رو بهمون بده. که همچین چیزی برای طراحی کامپایلر برای یه زبون اسکریپتی لازمه.
چند تا الگوریتم متداول هستن که یکی شون به نظرم بهتر از بقیه اومد .
شروع : ما دو تا پشته (stack) داریم که توی یکی عملگر ها (مثل +) و توی یکی عملوند ها (اعداد) ذخیره میشه.
مراحل الگوریتم به این صورته :
کلمه بعدی رو بخون.
اگه کلمه یه عملوند(عدد) بود اون رو بزار توی پشته عملوند ها (push)
اگه کلمه به عملگر بود:
اون رو با آخرین عملگر موجود در پشته عملگرها مقایسه کن.
اگه عملگر جدید تقدم بالاتری داشت عملگر جدید رو بزار توی پشته
اگه عملگر جدید تقدم کمتری داشت. عملگر قبلی رو از توی پشته بردار ، عملگر جدید رو بزار توی پشته ، عملگر قبلی رو هم وارد کن.
پایان حلقه
حالا یکی یکی عملگر ها رو از توی پشته عملگرها به پشته عملوند ها انتقال بده.

برای اینکه الگوریتم رو بهتر متوجه بشید با یه مثال قضیه رو روشن میکنیم. مثال ما همون : 4 * 2 + 1 هست.
خوب اولین کلمه 1 هست پس اون رو میزاریم توی پشته عملوند ها. پشته عملوند ها حالا به این صورته : {1}
کلمه دوم + هست و چون پشته عملگر ها خالیه پس اون رو با هیچی مقایسه نمیکنیم و میزاریمش توی پشته عملگر ها. پشته عملگر ها حالا اینطوره : {+}
کلمه بعدی 2 هست. میزاریمش توی پشته عملوند ها. پشته عملوند ها حالا اینطوره : {1}{2}
کلمه بعدی * هست. اون رو با آخرین عملگر موجود در پشته (+) مقایسه میکنیم. خوب * تقدم بیشتری داره پس طبق الگوریتم باید اون رو بزاریم توی پشته. پس پشته عملگرها میشه: {+}{*}
کلمه بعدی 4 هست. میزاریمش توی پشته عملوند ها. پشته عملوند ها حالا اینطوره : {1}{2}{4}
حالا پشته عملگر ها رو یکی یکی میاریم توی پشته عملوند ها (البته چون داریم با پشته ها کار میکنیم فقط میتونیم یکی یکی این کار رو انجام بدیم)
در انتهای عملیات پشته عملگر ها خالی و پشته عملوندها اینطوریه : {1}{2}{4}{*}{+}
پشته علموند ها رو بر عکس میکنیم:{+}{*}{4}{2}{1} (انتهای پشته سمت چپه)
خوب حالا این پشته رو یادتون باشه تا بگم باهاش چی کار میکنیم.

یه الگوریتم دیگه لازمه تا پشته عملوند ها رو به عنوان ورودی بگیره و جواب (9) رو تحویل بده. الگوریتم بسیار سادس. پس با همین مثال نشونش میدم.
ما یه پشته دیگه میسازیم به نام پشته عملیات.
یه عنصر از پشته عملوند ها برمیداریم (pop) و میزاریم توی پشته عملیات. پشته عملیات حالا این طوره :{1} و پشته عملوند ها این :{+}{*}{4}{2}
یه عنصر دیگه از پشته عملوند ها بر میداریم میزاریم توی پشته عملیات (چون اینا عدد هستن این کار رو میکنیم). پشته عملیان : {1}{2} . پشته عملوندها {+}{*}{4}
یه بار دیگه. پشته عملیات : {1}{2}{4}. پشته عملوند ها {+}{*}
خوب حالا میرسیم به مرحله جالبش. حالا عضو بعدی توی پشته عملوند ها * هست. خوب ضرب احتیاج داره به دو تا عملوند (عدد) تا اونها ور در هم ضرب کنه. پس ما دوتا عنصر از پشته عملیات خارج میکنیم و اونها رو در هم ضرب میکنیم و نتیجه رو میزاریم توی پشته عملیات. حالا پشته عملیات این طوریه : {1}{8} و پشته عملوند ها {+}
احتمالا میتونید این مرحله رو حدس بزنید : درسته ما یه عضو دیگه از پشته عملوند ها بیرون میاریم این عضو + هست پس احتیاج به دو تا عملوند(عدد) داره. دو تا عدد از پشته عملیات خارج میکنیم و با هم جمع میکنیم و نتیجه رو میزاریم توی پشته عملیات.
وقتی پشته عملوند ها خالی شد. پشته عملیات یه عضو داره که اون عضو نتیجه محاسبه هست.{9}

میشه عملگر های بیشتر مثل پرانتز یا تقسیم ، تقسیم صحیح ، مقایسه ، تابع و... رو به این الگوریتم اضافه کرد.

فعلا دارم روی همین قضیه کار میکنم.

[nimaprofessionalism]

drblack,

لطفا برنامه های مورد نیاز برای مشاهده انجینیتون رو برای دانلود بزارید چون برای من error میده.

[m_basij]

هر دو نرم افزار رو می تونید از داخل مایکرو سافت دانلود کنید. حجمشون هم 60 مگ می شه .

[MahanGM]

ایول. منم داشتم یک مدت همینکار رو می کردم ولی وقتش رو نداشتم !. تا نصفه رفتم.
خوبه من هم یه چند تا زبون اسکریپتی باسه خودم داشتم ولی فقط خودم میتونستم ازش استفاده کنم چون انقدر پیچیده بود که قاتی میرکدم. دارم میگیرم انجین رو.

نظرم رو میگم.

[drblack]

بعد از امتحان کردن یه سری اسکریپت نسبا حجیم و خفن روی انجین (اسکریپت ها واقعا پیچیده بودن) متوجه شدم که برای اسکریپت های پیچیده روش ارزیابی در زمان اجرا کار آمد نیست و عملیات ها باید به یه زبون سطح پایین کامپایل بشن. خوب برای این کار ما احتیاج داریم به یه ماشین مجازی که قبلا هم اینو داشتیم. خصوصیات ماشین مجازی ما
1- 16 تا رجیستر از نوع int به نام های RI1 , RI2 و...
2- 16 تا رجیستر از نوع double به نام های RD1 , RD2 و...
3- 16 تا رجیستر از نوع رشته (!) به نامهای RS1 , RS2 و...
4- 16 تا فلگ به نامهای FLG1 , FLG2 و...
5- سیستم اعداد و آدرس دهی (فعلا) بر مبنای ده هست.
دقت کنید که این یه ماشین مجازی نه پردازنده 80x86 پس تمام این رجیستر ها من در آوردی (در واقع انتزاعی) هستن. و زبون سطح پایین ما دقیقا اسمبلی IA-32 نیست و فقط یه زبون سطح پایین من در آوردی یه چیزی مثل CLR یا کدهای کامپایل شده جاوا....

خوب حالا میریم سراغ الگوریتم. این الگوریتم باید پشته عملیات رو (توی پست قبلی توضیح دادم) تبدیل کنه به کد ماشین.

با مثال الگوریتم رو نشون میدم. پشته عملیات ما اینه : {+}{*}{5}{2}{1} که معادل عبارت 1+5 * 2 هست (یا یه همچین چیزی)
خوب شروع میکنیم.
اولین عنصر رو میاریم بیرون: چون عنصر یه عدده (عملوند) پس باید بره توی حافظه. کد تولید شده اینه :
PUSH 1
و همینطور بعدی
PUSH 2
و بعدی
PUSH 5
حالا میرسیم به ضرب پس باید دو تا عنصر از پشته خارج کنیم و اونها رو در هم ضرب کنیم و نتیجه رو بزاریم توی پشته:
POP RD1
POP RD2
MUL RD1 ,RD2
PUSH RD1
و برای جمع هم همینطور
POP RD1
POP RD2
ADD RD1,RD2
PUSH RD1
پایان. کد تولید شده:

[drblack]

انگار کسی به مسائل فنی علاقه ای نشون نمده...

شاید امشب لول ادیتور رو بزارم.

[m_basij]

خوبه . حتما بزار تا ما هم ببینم شما چی کردید.
اما می گم سرس کامپایلر نیست ( نه نرم افزار) . که به ادیتور بچسبونی.
می گم با چی می نویسی . اگه دوست داری برو و سرس یو دی کی رو ببین . قسمت اسکریپت نویسیش توپه.

[drblack]

چرا اتفاقا سورس کامپایلر زیاده و من اونها رو مطالعه میکنم ولی مسلما نمیتونم مستقیم ازشون استفاده کنم چون اونا برای زبون های دیگه هستن و من میخوام زبون خودم رو کامپایل کنم. فکر کنم باید بی خیال این کامپایلر بشم و از همون زبون سطح پایین استفاده بشه.

خود انجین (ران تایم) با سی شارپه ولی لول ادیتو و بقیه ابزارها ها به VB.net. و کلا بر پایه XNA هست. موتور صوتی هم هنوز به انتخاب درستی نرسیدم ولی یا از irrklang استفاده میکنم یا قسمت صوت SDL. شما چه پیشنهادی برای انجین صوتی دارید؟

[omid3098]

[m_basij]

شما به چه زبونی می نویسی؟
اگر با c++ بنویسی . یک کامپایلر c++ پیدا کن و هسته و همینطور قسمت برنامه نویسیت رو با اون ارتباط بده . ؟! البته این به نظر شما بستگی داره. اما در مورد صوت هم من زیاد سر رشته ندارم . ولی فکر کنم مطابق نیازت خودت بنویسیش بهتره.