گرامرهای مستقل از متن قطعی
 | این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
گرامرهای مستفل از متن قطعی در تئوری رسم گرامر، گرامرهای مستقل از متن قطعی (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 قوی تر می‌باشد و هر دو در کامپایلرهای بسیاری مورد استفاده قرار گرفته‌اند.
منابع[ویرایش]
- Evey, R.J. (1963). "Application of Pushdown-Store Machines". 1963 AFIPS Proceedings of the Fall Joint Computer Conference: 215–227.صفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد.
- Schützenberger, Marcel Paul (1963). "On Context-Free Languages and Push-Down Automata". Information and Control. 6: 246–264.صفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد.
- A Salomaa & D Wood & S Yu, eds. (2001). A Half-Century of Automata Theory. World Scientific Publishing Co. Pte. Ltd. pp. 38–39.صفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد.
- الگو:Cite doi
- Franklin L. DeRemer (1969). "Practical Translators for LR(k) languages" (PDF). MIT, PhD Dissertation.صفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد.
| این نوشتار نیازمند به افزودن رده تخصصی است. با توجه به ویکی‌پدیا:رده‌بندی رده‌های مورد نیاز را اضافه کنید . |
This article "گرامرهای مستقل از متن قطعی" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:گرامرهای مستقل از متن قطعی. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
