اصول و طراحی کامپایلر ها
درحالت کلی سه نوع زبان داریم :
1. زبان ماشین
2. زبان اسمبلی
3. زبان سطح بالا
اسمبلی : خطای کم / اگه خطا باشه برمیگرده پیدا میکنه مجددا جدا میکنه .
سطح بالا: یا کل برنامه رو اجرا میکنه و از خطا چشم پوشی میکنه یا باید کاملا اصلاح شود.
نکته مهم : زبان های برنامه نویسی انواع مختلفی دارد :
1. زبان ماشین که در آن داده ها و دستورالعمل به صورت کدهای باینری 01 نمایش داده میشود . تنها زبانی است که کامپیوتر آن را درک میکند هربرنامه باید قبل از اجرا ب زبان ماشین ترجمه شود. هرنوع کامپیوتر زبان مخصوص به خود را دارد . برنامه نویسی به زبان ماشین بسیار مشکل است .
2.زبان اسمبلی به جای کد های باینری از کلمات اختصاری استفتده میکند.خوانایی برنامه ها به زبان اسمبلی بیشتر از زبان ماشین است.برای تبدیل زبان اسمبلی به زبان ماشین از نرم افزار مترجمی اسمبلر استفاده میشود.
3. زبان های سطح بالا به زبان محاوره ای نزدیک تر است. و دارای ساختار و دستورات بیشتر و قدرتمند نسبت به زبان اسمبلی هستند. برنامه های نوشته شده با این زبان مستقیم قابل اجرا روی ماشین نیستند و توسط کامپایلر ها به زبان ماشین نیستند و توسط کامپیلر ها به زبان ماشین ترجمه میشوند.
تفاوت اسمبلر و کامپایلر : اسمبلر هر دستور را فقط یک دستور زبان ماشین ترجمه میکند.درحالی که کامپایلر هر دستور زبان سطح بالا به چندین دستور زبان ماشین ترجمه میکند. رابطه دستورات زبان سطح بالا به زبان ماشین یک به یک .
روش های ترجمه و اجرای زبان سطح بالا:
1- مفسر ها
2-کامپایلرها
مزایای مفسرها: سهلوت در اشکال -قابلیت انعطاف بالا- پیاده سازی آسان- قابلیت حمل بالا.
مزایای کامپایلرها: سرعت اجرای بالا- جرای مستقل برنامه از کامپایلرها- حفاظت از کد منبع- عدم تکرار از کامپایلر.
معایب مفسر ها: تکرار تغییر- سرعت اجرای پایین- نیاز به مفسر.
معایب کامپایلر ها: زمان بر بودن اشکال زدایی- قابلیت حمل بالا- عدم سهولت پیاده سازی-
استفاده ازمفسر : در این روش استفاده از دستورالعمل های برنامه یک به یک توسط نرم افزاری به نام مفسر خوانده و اجرا میگردد.در این روش برنامه مبدا به زبان ماشین ترجمه نمیشود. در نتیجه فایل جداگانه تولید نمیگردند.
پایان
خطا
اجرای دستور العمل
واکشی دستورالعمل
برنامه مبدا
عملکرد مفسر
برنامه مبدا
استفاده از کامپایلر: کامپایلر نرم افزاری است که برنامه نوشته شده به زبان مبدا را به برنامه در زبان مقصد ترجمه میکند. در روش استفاده از کامپایلر ابتدا برنامه مبدا به زبان ماشین تبدیل سپس این برنامه روی کامپیوتر اجرا میشود .
گزارش خطا
عملکرد کامپایلر
برنامه مقصد
کامپایلر
سه فاز تحلیل در کامپایلر:
1- تحلیل گر لغوی- 2 تحلیل گر نحوی-3 تحلیلگر معنایی-
تحلیل گر لغوی : بخشی از کامپایلر است که مستقیما به برنامه مبدا دسترسی دارد. تحلیل گر لغوی برنامه مبدا را به صورت جریانی از کاراکتر ها دریافت کرده .لغات تشکیل دهنده برنامه و نوع آنها را تشخیص داده و آن را برای تحلیل گر نحوی ارسال میکند.
مثال: K:H+12*B;
K شناسه
: کاراکتر
H شناسه
+ عملگر
12 شناسه عددی
* عملگر
B شناسه
; کاراکتر
تحلیل گر نحوی : وظیفه تحلیل گر نحوی برسی سخت و درستی ترتیب لغات برنامه مبدا است.برسی ساختار برنامه مبدا از وظایف تحلیل گر نحوی است. تحلیل گر نحوی خروجی تحلیل گر نحوی خروجی تحلیل گر لغوی دریافت کرده و اگر ترتیب لغات برنامه مبدا صحیح باشد از آن یک ساختار درختی تولید میکند.این درخت نشان دهنده ساختار برنامه مبدا است که اصطلاحا به آن درخت تجزیه میگویند.
تحلیل گر معنایی : مواردی که در مراحل قبل مورد برسی قرار گرفته است در تحلیل گر معنایی برسی میشود؛ تحلیل گر معنایی معنا دار بودن عباراتی که از نظر نحوی درست بودن را مورد برسی قرار میدهد. تحلیل گر معنایی وظیفه تشخیص خطاهای معنایی ، جمع آوری اطلاعات برای مرحله بعد کامپایلر و عمال برخی تغییرات برای اصلاح برخی موارد را بر عهده دارد.مواردی که توسط تحلیل گر معنایی برسی میشود شامل :
1 - برسی هماهنگی پارامتر ها
2 - برسی و کنترل نوع
3- تبدیل نوع
4 - برسی و تغییر دوباره متغییر
فاز های کامپایلر :
تحلیل گر لغوی
تحلیل گر نحوی
تحلیل گر
تحلیل گر معنایی
خروجی
تحلیل گر نحوی
تحلیل گر نحوی
K:H+12*B:
ID1:ID2+12*B;
تحلیل گر معنایی
بهینه سازی کد میانی
تولید کننده کد میانی
تولید کننده کد
ID3
12
*
ID:2
+
ID1
:
=
تولید کننده کد میانی: از خروجی تحلیل گر معنایی ، کد میانی تولید میکند. کد میانی زبان ماشین منطقی و مجاز میباشد،به همین جهت هر کامپایلر میتواند کد میانی مخصوص به خود را تعریف کند.
2 خواص تولید کننده کد میانی: 1سهولت تولید کد:زبان ماشین منطقی تا حد امکان باید ساده در نظر گرفته شود تا تولید کد برای آن آسان شود.
بهینه ساز کد میانی : وظیه برسی کد میانی را برعهده دارد، تا در صورت امکان آن را بهینه سازی کند. بهینه سازی ینی اعمال تغییراتی در برنامه که بدون تغییر عملکرد برنامه مصرف حافظه کاهش و اجرای برنامه افزایش یابد.
تولید کد : بخش تولید کننده کد؛ کد میانی بهینه سازی شده را به زبان اسمبلی ترجمه میکند.
زبان پیاده سازی کامپایلر:
راه حل این مشکل استفاده از زبان میانی هستند.در ابتدا برنامه مبدا به زبان میانی ترجمه شده سپس از زبان میانی به زبان مقصد ترجمه میشود.
کد نهایی ماشین2
کد نهایی ماشین 2
کد نهایی ماشین K
Nکامپایلر
کامپایلر2
کامپایلر1
NK
...
زبان 1
Nزبان
زبان 2
زبان 3
کامپایلر برنامه ای است که برنامه زبان مبدا را به برنامه معادل زبان مقصد ترجمه میکند کامپایلر یک برنامه است که به زبان برنامه سازی نوشته شده است زبانی که کامپایلر با آن نوشته میشود را زبان پیاده سازی مینامیم. برای تولید کامپایلر دوم نیازی به کامپایلر دیگری میباشد و این روند ادامه دارد. اگر N تعداد زبان های برنامه سازی و K انواع مختلف کامپیوتر ها باشد N در K کامپایلر نیاز داریم.
جلوبندی و عقب بندی کامپایلر
جلوبندی: بخشی از کامپایلر که وظیفه ترجمه برنامه مبدا به زبان میانی را برعهده دارد، جلوبندی کامپیوتر گفته میشود.
عقب بندی :بخشی از کامپایلر که وظیفه ترجمه برنامه زبان میانی را به زبان مقصد بر عهده دارد.عقب بندی کامپایلر میگوییم.
برنامه مبدا
کد میانی
H + K
عقب بندی
برنامه نهایی
جلوبندی
با استفاده از این روش برای N زبان مبدا و K کامپیوتر به N لوبندی،وk عقب بندی نیاز داریم. که در مجموع به N+K برنامه احتیاج است.
مزایای تقسیم کامپایلر به عقب بندی و جلو بندی : 1سادگی- 2 استقلال جلوبندی از زبان مقصد-3استقلال عقب بندی از زبان مبدا- 4 کاهش پیچیدگی- 5 افزایش قابلیت استفاده مجددا- 6 افزایش سرعت تولید کامپایلر-
ساختار محیط برنامه نویسی : برای نوشتن برنامه به یک زبان خاص و تبدیل آن به برنامه اجرایی اجزای مختلفی در کنار کامپایلر قرار میگیرد که هر یک وظیفه ای را به عهده دارد .
امروزه محیط برنامه نویسی تمام امکانات لازم برای نوشتن برنامه خطایابی و تایید کدنهایی را در اختیار برنامه نویسی قرار می دهد این گونه محیط هارا IDE می نامند
برنامه به زبان ماشین جابه جا پذیر
برنامه مبدا
برنامه به زبان ماشین مطلق
پیش پردازشگر
کامپایلر
اسمبلر
ویرایشگر پیوند
IDE: Iutegrated Developmeut Euviroume
برنامه اسمبلی
پیش پردازنده:وظیقه انجام برخی تبدیلات اولیه را بر روی برنامه ورودی بر عهده دارد. در واقع پیش پردازنده یک کامپایلر سطح بالا است که برخی ترجمه ها را انجام میدهد . برنامه خروجی پیش پردازنده را به زبان اسمبلی ترجمه میکند این بخش بیشتر وظایف تبدیل برنامه مبدا به یک برنامه اجرایی را بر عهده دارد .
اسمبلر : این بخش برنامه اسمبلی خروجی از بخش کامپایلر را به کد های باینری که قابل فهم برای کامپایلر باشد تبدیل میکند.
ویرایشگر پیوند : این بخش انتقال برنامه اجرایی به حافظه به منظور اجرا را بر عهده دارد.
ویژگی کامپایلر خوب:
1 تولید کد صحیح
2 پیروی از مشخصات زبان مبدا
3 امکان پردازش برنامه های بزرگ
4 سرعت کامپایلر
5 اندازه کامپایلر
6 پیغام های خطای کامپایلر
7 قابلیت حمل
8 بهینه سازی
فصل دوم تحلیل گر لغوی :
تحلیل گر لغوی تنها فازی است که با برنامه مبدا در ارتباط است. این فاز برنامه ورودی را برسی میکند،لغات برنامه مبدا و نوع آن را تشخیص داده و آن را برای تحلیل گر نحوی ارسال میکند.
لغات موجود در برنامه مبدا به چند دسته تقسیم میشوند:
1-کلمات کلیدیک لغاتی که در زبان مبدا معنی خاصی داشته باشند. “ float-prgram-main”
به این کلمات،کلمات رزرو شده مبهم میگویند.
2-علایم: علامت هایی که به منظور نشانه گذاری خاصی در زبان مبدا بکار میرود : و {} ( )
3-عملگر ها: علامت هایی که به منظور نشان دادن عملیات خاصی در زبان مبدا به کار میرود. + - ؟ *
4-شناسه ها: نام هایی که جز کلمات کلیدی نبوده و توسط برنامه نویس به قطه کد اضافه میشود. نام کلاس – نام ارایه ها- نام متغییر ها
5-ثوابت: هر مقدار عددی کاراکتر های رشته ای و منطقی به عنوان ثوابت در نظر گرفته میشود.
6-توضیحات: قسمتی از برنامه مبدا که توسط کامپایلر در نظر گرفته نمیشود. توضیحات به منظور افزایش خوانایی برنامه می باشد و در عملگر برنامه هیچ تاثیری ندارد.
7- فضای خالی: تاثیر فضای خالی در برنامه بستگی به زبان مبدا دارد. دربرخی زبان ها فضای خالی دارد به منظور خواناتر کردن برنامه و جدا کردن لغات از یک دیگر میباشد.
مثال:
لغت
نوع لغت
PROGRAM
کلمات کلیدی
PR1
شناسه
;
علایم
{
توضیحات
VAR
کلمات کلیدی
I
شناسه
:
علایم
Intger
کلمات کلیدی
;
علایم
Program p1 ; {this is simple }
Var I: integer ;
J : real ;
Str : string [20];
Integer ;
4 temp :خطا
Begin
J : = 2.1 ;
I : = 2*j ;
نوع لغت
لغت
علایم
;
کلمات کلیدی
Begin
شناسه
J
علایم
:
علایم
=
ثوابت (اعشاری)
2.1
علایم
;
شناسه
I
علایم
:
علایم
=
ثوابت (عددی)
2
عملگر
*
علایم
;
کلمات کلیدی
ed
علایم
.
شناسه
Str
علایم
:
کلمات کلیدی
String
علایم
[
ثوابت
20
علایم
]
علایم
;
خطا
4temp
شناسه
:
کلمات کلیدی
intger
عملگر تحلیل گر لغوی هنگام برخورد با یک خطای لغوی
توقف: در این روش تحلبیل گر لغوی پس از کشف اولین خطا متوقف میشود برنامه نویس خطا را رفع و برنامه را کامپایل میکند. تحلیل گر لغوی برنامه را از ابتدا برسی میکند اگر به خطای دیگری برخورد کرد دوباره متوقف میشود.
عیب این روش افزایش تعداد دفعات انجام کامپایل است.در نتیجه زمان تولید نرم افزار افزایش میابد.
پوشش خطا
تحلیل گر لغوی پس از کشف یک خطا متوقف نمیشود بلکه به کار خود ادامه میدهد. در این روش پس از کشف خطا تحلیل گر لغوی از خطا چشم پوشی کرده و به برسی بقیه برنامه ادامه میدهد. یکی از روش های پوشش خطا حذف کاراکتر های ورودی است.
عملکرد تحلیل گر لغوی هنگام برخورد با یک خطای لغوی
1 توقف : در این روش تحلیل گر لغوی پس از کشف اولین خطا متوقف میشود. برنامه نویس خطا را رفع و برنامه را کامپایل میکند. تحلیل گر لغوی برنامه را از ابتدا برسی میکند و اگر به خطای دیگری بر خورد کرد دوباره متوقف میشود. عیب این روش افزایش تعداد دفعات انجام کامپایل است. در نتیجه زمان تولید نرم افزار فزایش می یابد.
2-پوشش خطا : تحلیل گر لغوی پس از کشف یک خطا متوقف نمیشود،بلکه به کار خود ادامه میدهد. در این روش پس از کشف خطا تحلیل گر لغوی از خطا چشم پوشی میکند و به برسی بقیه برنامه ادامه میدهد. یکی از روش های پوشش خطا حذف کاراکتر های ورودی است.
نشانه: فاز بعد از تحلیل گر لغوی تحلطیل گر نحوی است که باید علاوه بر خود لغات نوع هر لغات را نیز در اختیار داشته باشد. به همین جهت لازم است هماهنگی بین تحلیل گر نحوی و تحلیل گر لغوی انجام شود،به این منظور از نشانه استفاده میشود.نشانه علامتی است که تحلیل گر لغوی و تحلیل گر نحوی برای مشخص کردن یک نوع خالص از لغات به یک دیگر توافق کرده اند.
نحوه ارسال نشانه ها به دو روش قابل انجام است:
1- استفاده از فایل واسط : در این روش تحلیل گر نحوی تمام فایل ورودی را خوانده و همه نشانه های لازم را تولید میکند.و در یک فایل واسط قرار میدهد.
سپس تحلیل گر نحوی این فایل را می خواند:
برنامه ورودی
تحلیل گر لغوی
برنامه ورودی
جریان نشانه ها
فایل واسط
تحلیل گر نحوی
جریان نشانه ها
2-ارتباط مستقیم: در این روش تحلیل گر نحوی از تحلیل گر لغوی درخواست نشانه میکند و تحلیل گر لغوی جریان ورودی را برای یافتن لغات بعدی پویش کرده و پس از تشخیص لغت بعدی نشانه مربوط را به تحلیل گر نحوی باز میگرداند. این روش سریع تر از روش قبل است به همین جهت اغلب کامپایلر ها از این روش استفاده میکنند.
نشانه
درخواست نشانه بعدی
تحلیل گر نحوی
تحلیل گر لغوی
برنامه ورودی
جدول نماد: تحلیل گر لغوی لغات تشخیص داده شده را درون ساختاری به نام جدول نماد ذخیره میکند. و آن را برای تحلیل گر نحوی ارسال میکند. جدول نماد برای هر شناسه یک رکورد در نظر میگیرد.
برخی از انواع نام ها و صفات که در جدول نماد ثبت میگردد: 1.متغیر ها: نام هایی که برای نگه داری اطلاعات به کار میرود. 2.نام زیر برنامه ها : هر زیر برنامه دارای نام است که باید به همراه مشخصات آن در جدول داده ثبت گردد.
3.آرایه ها: نوع،اندازه،و ابعاد آرایه در جدول نماد ثبت میشود.4.برچسب ها: آدرس برچسب ها در جدول نماد ثبت میشود.
پیاه سازی جدول نماد از دو روش لیست پیوندی و جدول درهم ساز استفاده میشود.
1-الفبای زبان: به مجموعه نامتناهی و متناهی از نماد های ساده و غیر ساده و غیر قابل تجزیه را الفبای زبان میگویند و با نماد " نشان میدهند.
2- رشته : یک دنبالی متناهی از الفبا را رشته میگویند،تهی نیز یک رشته حساب میشود و نماد آن " به این مانند است.
3-طول رشته: تعداد نماد های به کار رفته در رشته را ول رشته می نامیم.
4- زبان: مجموعه ای رشته هارا زبان میگویند.
اجتماع MUL : عملیات اجتماع : دو زبان M و L را به صورت MUL نشان میدهند. که عبارت است از مجموعه ای از رشته ها که در زبان L یا زبان M باشد.
L ={ab;aab;aaab;aaaab]
M ={12;21;32;23}
LUM ={ab;aab;aaab;aaaab;12;21;32;23}
MUL ={12;21;32;23;ab;aab;aaab;aaaab}
عملیات الحاق : الحاق دو زبان L و M را به صورت M نشان میدهند. زبان L.M عبارت است از مجموعه ای از رشته ها که از ترکیب رشته ای در زبان L در رشته ای در زبان M به دست آمده باشد.
L.M= { a12.a21.aa12.aa21.aaa12.aaa21}
M.L= { 12a.12aa.12aaa.21a.21aa.21aaa}
عملیات بستار L* : اگر L یک زبان باشد. بستار L به صورت L* نشان داده میشود. L* یعنی الحاق صفحه یا بیشتر L با خودش.
L= {ab; 12}
L1= { }
L2=L1 0 L1 = {abab;ab12;12ab;1212]
L1= {ab;12}
L1= {ab; 12}
L3= L2.L2
انواع زبان ها :
1 – زبان های با قاعده
2-زبان های مستقل از متن
3-زبان های وابسته به متن
4- زبان های قابل شمارش بازگشتی
زبان های با قاعده: زبانی است که بتوان آن را توسط یک عبارت باقاعده توصیف کرد.
عبارت های باقاعده:
1 -تهی " یک عبارت با قاعده است.
2-به ازای هر a عضو سیگما " باشد. R=a یک عبارت باقاعده است که زبان مجموعه a را مشخص میکند.
3- اگر R=a یک عبارت با قاعده باشد،آنگاه R* یک عبارت با قاعده است.
4- اگر r1 و r2 با قاعده باشد، L(r2) و L(r1) به ترتیب زبان های تولید شده توسط r1 و r2 باشند، آنگاه r=r1.r2 عبارت با قاعده است. زبان L(r1) Ul (r2)تولید میکند.
-5اگر r1 و r2 با قاعده باشد، L(r2) و L(r1) به ترتیب زبان های تولید شده توسط r1 و r2 باشند، آنگاه r=r1.r2 عبارت با قاعده است. زبان L(r1) . (r2)تولید میکند.
ماشین خودکار متناهی : تشخیص دهنده یک ماشین متناهی که در یک رشته مانند x را دریافت کرده و در صورتی کد رشته در x متعلق به زبان باشد جواب بله و در غیر این صورت جواب خیر میدهد.
ماشین خودکار متناهی در زبان های با قاعده 2 نوع است :
1- ماشین خودکار قطعی DFA
2-ماشین خودکار غیر قطعی NFA
DFA
Q= مجموعه ای متناهی از حالت ها است.
مجموعه ای متناهی از نمادها که الفبای زبان است.
&:یک تابع گذر است که نشان میدهد از هر حالت به چه حالتی میرسد.
Q0: به عنوان حالت شروع در نظر گرفته میشود.
F:به عنوان حالتی نهایی در نظر گرفته میشود
b
b
مثال :
a
a
3
1
2
& ( 1, a )={2}
& ( 1, b )={1}
& ( 2, a )={3}
& ( 2, b)={2}
1
2
3
a
2
3
b
Q={1,2,3}
Q0= { 1 }
F={ 3 }
نکته: تفاوت بین DFA و NFA
DFA یک خروجی میدهد.
NFA چند خروجی میدهد.
ماشین خودکار غیر قطعی NFA
DFA
Q= مجموعه ای متناهی از حالت ها است.
مجموعه ای متناهی از نمادها که الفبای زبان است.
Q0: به عنوان حالت شروع در نظر گرفته میشود.
F:به عنوان حالتی نهایی در نظر گرفته میشود
&:در این تابع به ازای هر حالت و هر یک از الفبا ممکن است چند حالت مجزا وجود داشته باشد.
مثال :
& (1,b)={1,2}
& ( 2,b )={2}
& ( 2,a )={3}
Q={1,2,3}
Q0= { 1 }
F={{3
3
2
1
2
1,2
b
3
a
مثال
b
c
c
d
a
8
6
7
8
9
b
6
a
7
7.8
c
8.9
d
9
& {6,a}
& ( 6,a )={7}
& ( 6,b )={6}
& ( 7,a )={8,7}
& ( &,c )={9,8}
& ( 9,d )={9}
Q={6,7,8,9}
Q0= { 6 }
F={9}
a
9
7
6
برای تبدیل عبارات با قاعده به DFA دو روش وجود دارد:
1-تبدیل عبارت با قاعده بهNFA وسپس تبدیل NFAبه DFA
-2تبدیل مستقیم عبارات با قاعده به DFA
NFA
DFA
برنامه
عبارت با قاعده
ایجاد NFA از عبارت با قاعده با روش تامپسون:
1- عبارت با قاعده r را در نظر بگیرید.سپس rرا به نماد های اولیه تجزیه میکنیم.
نماد های اولیه عبارت با قاعده
عبارت های با قاعده
R2=b
r1=a
r=a/b
R4=a
R3=c
R2=b
R1=a
R(a)b*)(ca)*
F
نکته: حالت نهایی همیشه با دو حلقه نشان داده میشود.
i
از شکستن عبارت با قاعده به عبارت با قاعده ای که فقط یک نماد دارند،برای هر یک از نمادها یک NFA می سازیم، برای ساخت این NFAیک حالت شروع به نام iو یک حالت نهایی به نام fایجاد میکنیم.بین این دو حالت یک برچسب نماد مورد نظر ایجاد میکنیم.
R= a start
i
F
b
R2= start
-2اگر ( r ) N، NFA حاصل از عبارات با قاعده rباشد،آنگاه NFAحاصل از عبارت با قاعده rباشد، آنگاه NFA
از r* را *(r) N مینامیم.
1
که به صورت زیر ساخته میشود:
a
f
i
A*={ab,12}
N(r)
A ={ }
A1= A
A2=a1.a1
A3=a2.a2
a
برای تبدیل عبارت با قاعده به DFA دو روش وجود دارد :
1- تبدیل عبارت با قاعده NFA به DFA
2- تبدیل مستقیم عبارت با قاعده به DFA
NFA
عبارت با قاعده
برنامه
DFA
ایجاد NFA از عبارت با قاعده با روش تامپسون:
1- عبارت با قاعده rرا در نظر بگیرید سپس r را به نماد های اولیه تجزیه میکنیم .
نماد های اولیه عبارت با قاعده
عبارت با قاعده
R2=b
R1=a
R=a/b
R4=a
R3=c
R2=b
R1=a
R(a/b)*(ca)*
پس از شکستن عبارت با قاعده به عبارات با قاعده ای که فقط یک نماد دارند ؛ برای هریک از نماد ها یک NFA میسازیم؛برای سخت این NFA یک حالت شروع به نام i و یک حالت نهایی به نام f ایجاد میکنیم.بین این دو حالت یک برچسب با نماد مورد نظر ایجاد میکنیم.
a
f
i
R1=a start
b
f
i
R2=a start
اگر N(r)،NFAحاصل از عبارت با قاعدهr باشد ،آنگاهNFA حاصل ازr* راN(r)* مینامیم که به صورت زیر ساخته میشود.
مرحله 1
a
A*={ab,12}
f
i
A0={}
N(r)
A1=a0.a1
A2=a1.a1
A3=a2.a2
i
a
مرحله 2
start
N(r)
مرحله 3
f
i
start
i
f
مرحله 4
a
start
اگر N(R2),(R1) و NFA های مرتبط با قاعده ی R1,R2 باشند،آنگاه NFA حاصل از R1/R2 را N(R1,R2) مینامیم.
N(R1)
i
N(R2)
start
N(R1)
i
F
N(R2)
start
N(R2)
اگرNFA,N(r2),N(r1)های عبارت با قاعده ی r1,r2باشند،انگاه NFAحاصل از R1.R2 را N(R1.R2)مینامیم.
حالت شروع N(R1) را حالت شروع N(R1.R2) را در نظرمیگیریم و حالت پایانN(R1) را باحالت شروع N(R2) را در نظر میگیریم.
(ab)*(a/b)c
NFA عبارت زیر را بنویسید.
مرحله یک1
i
f
a
R1=a start
i
f
b
R2=b star
i
f
a
R3=a start
i
f
b
R4=a start
i
f
c
R5=a start
(ab)
مرحله دوم 2
i
f
b
a
R2=b
R1=a
start
مرحله سوم 3
Ab)*)
i
a
b
f
R1=a
start
R2=b
a
مرحله چهارم 4
i
a/b
b
f
start
مرحله پنجم5
a
f
b
a
i
(ab)*(a/b)
(ab)*
start
ساخت مستقیم DFA از عبارت با قاعده :
1- هر نماد یا تهی در عبارت با قائده ی r به برگ تبدیل میشود.
2- عملگر الحاق به گره داخلی تبدیل میشود.
درخت تجزیه : (r1.r2)
R2
R1*
R1
*
R1
R1
R1
R1
R1
R1
R1
R1
R1
R1/R2
R2
عبارت با قاعده r را به r# تبدیل میکنیم، پس از آن درخت تجزیه را برای عبارت #r رسم میکنیم.
برای هر نماد عددی متناسب با مکان نماد اختصاص داده میشود،این عدد مکان نماد یا مکان برگ نامیده میشود.
First pos(n) این تابع مجموعه مکان نماد هایی را بر میگرداند که منطبق بر اولین نماد رشته ی تولیدی از عبارت با قاعده باشد.
(a|b)*=ab,abab,ababab,...
*
First pos.(ab)*={ab}
1
2
b
a
First pos (ab)*={1,2
(a|b)*C
First pos (a|b)*C={a,b}
R#.(a|b)*C# تبدیل هشتگ
Lostpos(n): این تابع مجموعه نمادهایی را برمی‌گرداند که منطبق بر آخرین نماد رشته های تولیدی در عبارت با قاعده است.
ab*=r#=ab*#
ab*=ab,abb,abbb,...
B1
B2
B3
B4
#
Last pos = {3,4}
C3
R=(a/b).c
Lostpos(a/b).c={c}
b
a
Lastpos{3}
R1= Or-node عبارت با قاعده ی سمت چپ و r2 عبارت با قائده ی سمت راست باشد Or-node این دو عبارت حاصل اجتاع
firstpos ها و LOSTPOS های هر عبارت میباشد.
R=R1/R2
Firstpos(r)=firstpos(r1) U firstpos(r2)
Lostpos(r)=lastpos(1) U Lastpos(r2)
R1=ab*
R2=(a/b).c
Firstpos(r1)={1,2}
Lastpos(r1)={3}
tpos(r2)={1,2}
Lastpos(r2)={3}
Firstpos(r)={1,2} U {1,2} {1.2}
Lastpos(r)={3} U {3} {3}
کلمات کلیدی
بر ای تشخیص کلمات کلیدی دو روش وجود دارد : ۱-باهر کلمه کلیدی به طور مستقل برخورد میکنیم برای هر کلمه کلیدی یک عبارت با قائده در نظر میگیریم سپس ب اژ آنDFA را بدست آورده و پیاده سازی میکنیم در این روش ابتدا نمادهاي ورودی با عبارت با قائده مربوط به کلمات کلیدی و سپس با عبارات با قائده مربوط به دیگر انواع لغات مقایسه میشود . ۲ - از آنجایی که کلمات کلیدی از لحاظ ساختار ، زيرمجموعه شناسه ها هستند ، میتوان آنهارا مانند شناسه ها تشخیص داد . با این تفاوت که کلمات کلیدی در جدول نماد بعنوان مقدار اولیه ثبت می‌شوندو نشانه کلمات کلیدی نیز در جدول نماد ثبت میشود . تحلیل گر لغوی هربار که شناسه ای را تشخیص داد ، ابتدا جدول نماد راجست و جو میکند . اگر شناسه کلمه کلیدی باشد تحلیل گر لغوی با جستجو هر جدول نماد کلمه کلیدی را یافته و نشانه ثبت شده را به جدول نماد بر میگرداند .
تولید خودکار تحلیل گر لغوی
برای ساخت تحلیل گر لغوی روشهای مختلفی وجود دارد ، که عبارتنداز : الف - استفاده از زبان برنامه سازی : دراین روش با استفاده از یکی از زبانهای برنامه سازی تحلیلگر لغوی ساخته میشود . مزاياومعایب این روش : ۱- صرف زمان زیاد برای ساخت تحلیل گر لغوی . ۲- کاهش قابلیت استفاده مجدد . ۳ - افزایش امکانات . ۴ - افزایش قابلیت انعطاف پذیری . ب - استفاده از ابزارها : با ت‌توجه به اینکه اصول ساخت تحلیلگر لغوی برای کامپایلرها یکسان است در نتیجه ابزارهای ايجاد شده با أخذ مشخصات لغوی زبان مبدا می‌توانند تحلیلگر لغوی آن را تولید کنند . به این گونه نرم‌افزارها تولید کننده تحلیلگرلغوی گفته میشود . مزایا و معایب این روش: ۱- افزایش سرعت ایجاد تغییرات -2کاهش زمان ساخت تحلیل گر لغوی
کاهش زمان ساخت تحلیل گر لغوی:
یکی از مهم ترین ابزار های نرم افزاری Flexمیباشد. نکته feleشامل یک زبان برنامه نویسی خاص خود است،که برنامه را به زبانCیا پاسکال تبدیل میکند.پسوند این فایلL.میباشد. تحلیل گر نحوی علاوه بر برسی صحت ترتیب لغات برنامه مبدا، وطیفه ایجاد درخت تجزیه را بر عهده دارد. ورودی تحلیل گران نحوی دنباله ای ز نشانه ها است که توسط تحلیل گر لغوی تولید شده است،و خروجی تحلیل گر نحوی درخت تجزیه است که نشان دهنده ی ساختار برنامه مبدا است
ساختار نحوی زبان را به روشهای مختلفی میتوان بیان کرد :
یکی از روشهای مهم بیان قوانین نحوی زبان مبدا استفاده از گرامرهای مستقل از متن است . مزایای استفاده از گرامر مستقل از متن : ۱- گرامرهای مستفل از متن قوانین نحوی زبان مبدا را کامل و دقیق و قابل فهم توصیف میکند . ۲- با استفاده از گرامرهای مستقل متن میتوان ابزارها یی ايجاد کرد که گرامرهای مستقل از متن را دریافت کرده و تحلیلگر نحوی آن‌را بصورت خودکار ايجاد کند . مدیریت خطا خطاهای برنامه در سطوح مختلف رخ میدهد : ۱ - خطاهاي نحوی : خطاهاي که مربوط به ساختار هر لغت در برنامه مبدا میباشد .
۲- وقتی دنباله ای از کاراکترها با هیچیک از عبارات با قائده منطبق نباشد ، این خطاها رخ میدهد.
خطاهای لغوی خطاهای شامل:
۱- استفاده از کارکترهای غیر مجاز temps ۲
- تعریف نا درست نامها یا شناسه ها مانند 5temp
۳- تعریف نادرست ثوابت مانند 12.654.765
خطاهاي نحوی:
پرانتزهای نا متعادل مانند A( (a+b*)
استفاده نادرست از عملگرها if (a>b>c)then a:=2:
خطاهای معنایی : ۱ - نوع دا ده ها
۲ - جریان کنترل
۳- کنترل یکتایی
نوع داده :اگر عملوند های یک عملگرناسازگار باشند مانندجمع یک آرایه و یک تابع
جریان کنترل :مقصد دستورات کنترلی که کنترل ذا از محلی به محل دیگر منتقل میکنذ موجود نباشند.
کنترل یکتایی : در برخی زبان ها یک متغییر فقط یک جا میتوتن تعریف گردد
گرامر های مستقل از متن :
ابزار مناسبی هستند جهت توصیف ساختار نحوی زبان های برنامه سازی را گرامرمیگوییم. گرامر مستقل از متن شامل مجموعه ای از قواعد تولید و یک نماد شروع است.
هر قاعده تولید یک ساختار نحوی را تعریف میکند که دارای نام است.
قاعده تولی دارای 2 قسمت است :
بخش سمت چپ که نام ساختار است و بخش سمت راست تمام شکل های ساختار را نشان میدهند.
بخش سمت راست داری 2 قسمت است:
1- نماد های پایانه
2- غیر پایانه ها
پایانه ها :
عملگراها و علاِم مانند + و - و * ارقام مانند 1و2و3
a , b , c حروف کوچک ماند
غیر پایانه ها:
A,B حروف بطرگ مانند
Start اسامی با حروف مانند
نکته : برای نشان دادن دنباله ای از پایانه ها و غیر پایانه ها از حروف لاتین مانند الفا و بتا استفاده میشود
مثال
E____ E+T E-T T
T____ T*F T/F F
F___id
غیر پایانه های این مثال
F,T E
پایانه ها
Id, / , * , - , +
درخت تجزیه :
چگونگی تولید یک رشته از نماد شروع گرامر را بصورت بصری نشان میدهند
گرامر :
روش ساخت رشته هایی متشکل از نماد هاست
گرامر 4گانه :
S=(N,T,S,P) N=مجموعه غیر پایانه ها
P مجموعه قوانین تولید رشته = S= نماد شروع
روابط زیر برای درخت تجزیه و گرامر مستقل از متن برقرار است :
1 ریشه درخت متناظر با نماد شروع گرامر است
است E برگ های درخت تجزیه پایانه گرامر یا 2
3 گره داخلی درخت تجزیه متناظر با یک غیر پایانه است
4 اگر غیر پایانه ای متناظر با یک گره داخلی درخت تجزیه باشد 98و98 بر چسب های فرزندان این گره از چپ به راست باشد انگاه در گرامر قاعده تولیدی بصورت خواهد بود
A1____X1,X2
مثال : درخت تجزیه1+2با توجه به گرامر:
E______E+T E-T T
T _____ 1 2 3
نکته : چون دو نماد شبیه به هم در درخت تجزیه نمیتواند پشت سر هم بیاید .
E
3
T
2
T
-
E
E
1
2
T
T
+
T
E
مثال 2-3
اشتقاق:
فراید تولید یک رشته از نماد شروع را اشتقاق میگوییم (تولید یک رشته به وسیل گرامر مستقل از متن از نماد شروع اغاز میشود )
انواع اشتقاق:
اشتقاق از چپ
در هر قدم انجام جایگزینی را روی سمت چپ ترین غیر پایانه ها انجام میدهیم .
اشتقاق از راست
در هر قدم انجام جایگزینی را روی سمت راست ترین غیر پایانه ها انجام میدهیم.
این رشته را با استفاده از گرامر:Id+id*idمثال =
E____ E+E E*E E
E ____ id
اشتقاق راست به چپ ان را بنویسید .
E____ E+E E*E
E____ E+E id*id
E____ id+id id*id E____ id+id*id
اشتقاق چپ
E id+E/E*E
E id+id/E*E
E id+id*id
گرامر های مبهم:
گرامر هایی است ک بتوان برای رشته تولید شده از گرامر یک درخت تجزیه تولید کرد
روش های رفع ابهام :
تقییر گرامر : هرکدام یک زبان را توصیف میکند برای تولید یک زبان میتوان از گرامر های متعددی استفاده کرد در نتیجه میتوان گرامر مبهم را تغییر داد تا زبان تولید شده مبهم نباشد .
استفاده از قوانین جانبی
در این روش گرامر تقییر نمیدهیم اما قوانینی وضع میکنیم که موجب ان از چند درخت تجزیه فقط یک انتخاب شود
استفاده از قوانین خاص:
با استفاده از این قوانین بین چند درخت تجزیه فقط یکی را انتخاب میکنیم
انواع تجزیه کننده ها :
تجزیه کننده های پایین به بالا
این تجزیه کننده ها از برگ درخت ها شروع کرده و به ریشه ختم میشود .
رسم کنید؟Postorder مثال:
Postorder = 1.2.3.4.5.6.7.8.9
تجزیه کننده های بالا و پایین: این تجزیه کننده ها از برگ درخت ها شروع کرده و به ریشه ختم میشوند.
رسم کنید؟Postorder مثال:
Postorder = 1.2.3.4.5.6.7.8.9
تجزیه کننده پیشتگوی غیر بازگشتی :
در این تجزیه کننده با استفاده از پشته و جدول تجزیه بدون فراخوانی بازگشتی توابع رشته ورودی پردازش میشود .
تجزیه کننده عملگراولویت :
این تجزیه کننده را میتوان بصورت دستی ایجاد کرد . این تجزیه کننده ضعیف است و بیشتر برای عبارات محاسباتی کاربرد دارد و از روابط عملگرها استفاده میکند
:LRتجزیه کننده
رشته ورودی را از چپ به راست پویش و معکوس سمت راست ترین اشتقاق را ایجاد میکند پایانه رشته ورودی باید علامت خاصی داشته باشد تا تجزیه کننده ال ار با رسیدن به ان پایان رشته را تشخیص دهد.
تجزیه کننده های پایین به بالا:
این تجزیه کننده ها از برگ درخت ها شروع کرده و به ریشه ختم میشود
تجزیه کننده پیش گو
نوع خاصی از تجزیه کننده بازگشتی است که در تجزیه کننده بازگشتی اجزای توابع بازگشتی ورودی را پردازش میکنند تجزیه کننده بازگشتی از روش سعی و خطا برای پردازش ورودی استفاده میکند یعنی تابعی برای پردازش ورودی فراخوانی میشود اگر پردازش ورودی شکست خورد به عقب بازگشتهو تابع دیگری را فراخوان میکند این روش بسیار کند و زمان بر است در تجزیه کننده ی پیشتگو با توجه به نماد بعدی تابعی ک باید اجرا شود دقیقا مشخص میگردد به همین جهت سریع تر از روش قبلی میباشد
پایان
