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

گرامرهای مستفل از متن قطعی در تئوری رسم گرامر، گرامرهای مستقل از متن قطعی (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 قوی تر می‌باشد و هر دو در کامپایلرهای بسیاری مورد استفاده قرار گرفته‌اند.

منابع

• Evey, R.J. (1963). "Application of Pushdown-Store Machines". 1963 AFIPS Proceedings of the Fall Joint Computer Conference: 215–227. {{cite journal}}: Cite has empty unknown parameter: |1= (help)
• Schützenberger, Marcel Paul (1963). "On Context-Free Languages and Push-Down Automata". Information and Control. 6: 246–264. {{cite journal}}: Cite has empty unknown parameter: |1= (help)
• A Half-Century of Automata Theory. World Scientific Publishing Co. Pte. Ltd. 2001. pp. 38–39. {{cite book}}: Unknown parameter |editors= ignored (|editor= suggested) (help)
• Knuth, Donald E. (1965). "On the translation of languages from left to right". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2. ISSN 0019-9958.
• Franklin L. DeRemer (1969). "Practical Translators for LR(k) languages" (PDF). MIT, PhD Dissertation. Archived from the original (PDF) on 5 April 2012. Retrieved 24 January 2014.