گرامرهای مستقل از متن قطعی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

گرامرهای مستفل از متن قطعی در تئوری رسم گرامر، گرامرهای مستقل از متن قطعی (DCFGs) زیرمجموعه‌ای برای گرامرهای مستقل از متن هستند. آن‌ها زیرمجموعه‌ای از گرامرهای مستفل از متنی هستند که مشتق شده از اوتوماتای قطعی pushdown می‌باشند و زبان مستقل از متن قطعی را تولید می‌کنند. DCFGsها همیشه نامبهم هستند و زیر کلاسی مهم از CFGsهای نامبهم می‌باشند. CFGsهای غیرقطعی نامبهم نیز وجود دارند. DCFGsها از آن جایی که در زمان خطی تحلیل می‌شوند و چون یک تحلیلگر می‌تواند به طور خودکار توسط تحلیلگر یک گرامر از یک گرامر تولید شود از نظر عملی بسیار مورد توجه هستند.

تاریخچه[ویرایش]

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

منابع[ویرایش]

  • خطای اسکریپتی