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

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

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

منابع 

 
 
 
 
 

زبان‌های صوری
مقاله‌های ایجاد شده توسط ایجادگر