دستور زبان مستقل‌ازمتن قطعی: تفاوت میان نسخه‌ها

محتوای حذف‌شده محتوای افزوده‌شده
جز ویرایش به وسیلهٔ ابزار خودکار ابرابزار
خط ۱:
'''گرامر هایگرامرهای مستفل از متن قطعی'''
در تئوری رسم گرامرگرامر، ، گرامر هایگرامرهای مستقل از متن قطعی (DCFGs) زیرمجموعه ایزیرمجموعه‌ای برای گرامر هایگرامرهای مستقل از متن هستند. آنآن‌ها ها زیرمجموعه ایزیرمجموعه‌ای از گرامر هایگرامرهای مستفل از متنی هستند که مشتق شده از اوتوماتای قطعی pushdown می باشندمی‌باشند و زبان مستقل از متن قطعی را تولید می کنندمی‌کنند. DCFGs هاDCFGsها همیشه نامبهم هستند و زیر کلاسی مهم از CFGs هایCFGsهای نامبهم می باشندمی‌باشند. CFGs هایCFGsهای غیرقطعی نامبهم نیز وجود دارند.
DCFGs هاDCFGsها از آن جایی که در زمان خطی تحلیل می شوندمی‌شوند و چون یک تحلیلگر میتواندمی‌تواند به طور خودکار توسط تحلیلگر یک گرامر از یک گرامر تولید شود از نظر عملی بسیار مورد توجه هستند.
 
== تاریخچه ==
در سال 1960۱۹۶۰ تحقیقات تئوری علوم کامپیوتر روی عبارات منظم واوتوماتای محدود منجر به کشف این موضوع شد که CFGs معادل با اوتوماتای غیر قطعی pushdown هستند. گمان می شدمی‌شد این گرامر هاگرامرها قواعد نحوی زبان هایزبان‌های برنامه نویسی را به تسخیر خود دراورند. اوایل توسعه زبان هایزبان‌های برنامه نویسی و نوشتن کامپایر هاکامپایرها دشوار بود. ولی استفاده از CFG هاCFGها برای خودکار سازی ،سازی، بخش تحلیل مطلب را ساده کرد. DCFG هاDCFGها مشخصاً به این دلیل مفید بودند که به صورت دنباله ایدنباله‌ای توسط اونوماتای pushdown قطعی تحلیل می شدندمی‌شدند که برای حافطه نیاز بود. در سال 1965 donald knuth تحلیلگر(LR(K راساخت و ثابت کرد برای هر DCFG یک تحلیلگر(LR(K وجود دارد. این تحلیلگر همجنان به حافظه زیادی نیاز داشت تا اینکه در سال 1969،۱۹۶۹، LALR , SLR را frank dermer اختراع کرد که حافظه کمتری نیاز داشتند و بر پایه تحلیلگر LR بودند و البته قدرت کمتری برای تشخیص زبان. LALR از SLR قوی تر می باشدمی‌باشد و هر دو در کامپایلر هایکامپایلرهای بسیاری مورد استفاده قرار گرفته اندگرفته‌اند.
 
== منابع ==