پاورپوینت مدلسازی خواص زبانها

بخشی از پاورپوینت

اسلاید 1 :

فصل چهارم مدلسازی خواص زبانها

اسلاید 2 :

معرفی مدلهای رسمی :
گرامرهای رسمی
معنای زبان
وارسی برنامه
خواص رسمی زبانها

اسلاید 3 :

سلسله مراتب چومسکی
BNFگرامر به وسیله مجموعه ای از نماد غیر پایانه مجموعه از نمادهای پایانه ، نماد شروع (یکی از غیرپایانه ها) و مجموعه ای از مولدها تعریف می شود.
زبان نوع N توسط گرامر نوع N تولید می شود.
خواص رسمی زبانها (ادامه)

اسلاید 4 :

سلسله مراتب چومسکی (ادامه)
گرامرهای منظم نوع 3
خواص:
اغلب قابل انتخاب است.
گرامرهای منظم می توانند رشته هایی به شکل αn را برای هر دنباله متناهی از α و هر مقدار صحیحی n تولید کنند.
به هر تعداد متناهی باشند.
در کامپایلرها برای پیمایش رشته ها مورد استفاده قرار می گیرند.
خواص رسمی زبانها (ادامه)

اسلاید 5 :

سلسله مراتب چومسکی (ادامه)
گرامرهای مستقل از متن – نوع 2
خواص:
بسیاری از خواص این گرامرها انتخابی اند.
برای شمارش و مقایسه دو قلم بکار گرفته شوند.
به وسیله پشته ها پیاده سازی کرد.
برای تولید خودکار درختهای تجزیه برنامه بکار گرفت.
خواص رسمی زبانها (ادامه)

اسلاید 6 :

گرامرهای وابسته به متن نوع 1
خواص:
طول تمام رشته ها کاهش پذیر نیست.
به حافظه ثابتی نیازدارند.
بسیار پیچیده اند و کاربرد آنها دشوار است.
عدم قطعیت در گرامر وابسته به متن مثل قطعیت است.
خواص رسمی زبانها (ادامه)

اسلاید 7 :

گرامرهای نامحدود – نوع صفر
خواص:
برای تشخیص هر نوع تابع قابل محاسبه بکار می رود.
اغلب خواص قابل انتخابند.
خواص رسمی زبانها (ادامه)

اسلاید 8 :

تصمیم ناپذیری
ماشینهای تورینگ
مسئله توقف
ابهام
خواص رسمی زبانها(ادامه)

اسلاید 9 :

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

اسلاید 10 :

ماشینهای تورینگ (ادامه)
ماشین تورینگ ساختمان داده ای دارد که یک آرایه خطی با طول متغیر است که نوار نامیده می شود.
هر عنصر نوار شامل یک کاراکتر است.
یک متغیر اشاره گر به نام هد خواندن وجود دارد.

اسلاید 11 :

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

اسلاید 12 :

مسئله توقف
مسئله توقف غیر قابل تصمیم گیری است.
هیچ الگوریتم کلی نمی تواند وجود داشته باشد که این مسئله را برای تمام ماشینهای تورینگ و تمام داده های ورودی حل کند.
برای اینکه نشان دهیم مسئله خاصل غیرقابل تصمیم گیری است نشان می دهیم معادل مسئله توقف است.

اسلاید 13 :

ابهام
بسیاری از مدلهای تئوری وضعیت عملی را می توان ایجاد کرد .
خواص جالب BNF : نه تنها کاربرد عملی آنها آسان است بلکه به خوبی می توانند محدودیتهای نحوی مورد نیاز برای زبانهای برنامه سازی را بیان کنند.

اسلاید 14 :

پیچیدگی الگوریتم
گرامرها و ماشینها
ماشین خودکار متناهی
ماشین خودکار پشته ای
ماشین خودکار خطی
ماشین تورینگ

اسلاید 15 :

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

اسلاید 16 :

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

اسلاید 17 :

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

اسلاید 18 :

معنای نشانه گذاریها (ادامه)
عملیات در حساب لاندا
عبارات لاندا فقط یک عملیات کاهش دارد.
عملیات کاهش همیشه منجر به عبارت لاندا نمی شود که ساده تر از عبارت اصلی باشد.
انتقال پارامترها با عبارات لاندا
روش اول: اول داخلی ترین جمله را کاهش دهید
روش دوم: اول خارجی ترین جمله را کاهش دهید.

اسلاید 19 :

مدلسازی ریاضی با عبارات لاندا
حساب لاندا به عنوان مدل منطقی محاسبات ایجاد شد
عبارات لاندا برای مدلسازی حساب محمولات به کار می روند
با استفاده از حساب محمولات می توانیم مقادیر صحیحی را مدلسازی کنیم.

اسلاید 20 :

مدلسازی زبانهای برنامه سازی
با بسط عبارات لاندا انواع داده ها را مدلسازی کنیم و سپس آن مدل را بسط دهیم تا معنای زبان برنامه سازی را نیز در برگیرد.
چند تابع بایستی مشخص شود:
نیاز به تصویف برنامه است. تابع M
نیاز به توصیف دستور در زبان است تابع C
تابع ارزیابی .