زبانهای مستقل از متن و اتوماتای پشتهای
گرامرهای مستقل از متن، زبانهایی با ساختار تودرتو و بازگشتی تولید میکنند و اتوماتای پشتهای دقیقاً این زبانها را با افزودن یک پشته نامحدود به یک کنترل متناهی تشخیص میدهند.
Definition
یک زبان مستقل از متن توسط گرامری تولید میشود که قوانین آن یک نماد غیرپایانی واحد را مستقل از متن بازنویسی میکنند، و توسط یک اتوماتای پشتهای تشخیص داده میشود، که یک اتوماتای متناهی مجهز به پشتهای است که حافظه ورود-آخر-خروج-اول با عمق نامحدود را فراهم میکند.
Scope
این موضوع گرامرهای مستقل از متن و اشتقاقها، درختهای تجزیه و ابهام، همارزی گرامرهای مستقل از متن با اتوماتای پشتهای، فرمهای نرمال مانند فرم نرمال چامسکی، لم پمپاژ برای زبانهای مستقل از متن، و ویژگیهای بستار و تصمیمپذیری را پوشش میدهد که این کلاس را از زبانهای منظم متمایز میکند.
Core questions
- چه نوع الگوهای تودرتو یا بازگشتی به پشته نیاز دارند تا حافظه متناهی؟
- چرا گرامرهای مستقل از متن و اتوماتای پشتهای از نظر قدرت همارز هستند؟
- چه زمانی یک گرامر مبهم است و چرا ابهام برای تجزیه اهمیت دارد؟
- کدام مسائل تصمیمگیری برای زبانهای مستقل از متن قابل حل هستند و کدام نیستند؟
Key theories
- همارزی گرامر-اتوماتا
- یک زبان مستقل از متن است اگر و تنها اگر توسط یک اتوماتای پشتهای پذیرفته شود، بنابراین دیدگاه گرامر مولد و دیدگاه ماشین پشتهای یک کلاس از زبانها را توصیف میکنند.
- فرم نرمال چامسکی
- هر گرامر مستقل از متن را میتوان به گونهای بازنویسی کرد که هر قانون یا دو غیرپایانه یا یک پایانه واحد تولید کند، یک فرم نرمال که زیربنای الگوریتمهای تجزیه و اثباتهای استقرایی در مورد این کلاس است.
- لم پمپاژ برای زبانهای مستقل از متن
- هر رشته به اندازه کافی طولانی در یک زبان مستقل از متن را میتوان به گونهای تقسیم کرد که دو بخش آن با هم پمپ شوند، خاصیتی که برای زبانهایی که به بیش از حافظه پشته نیاز دارند صادق نیست و بنابراین ثابت میکند که آنها مستقل از متن نیستند.
Clinical relevance
گرامرهای مستقل از متن نحو تقریباً هر زبان برنامهنویسی و بسیاری از فرمتهای داده را مشخص میکنند، و الگوریتمهای تجزیه به سبک پشتهای این گرامرها را به تحلیلگرهای نحوی در قلب کامپایلرها و مفسرها تبدیل میکنند، که این موضوع را به پایه نظری پردازش زبان برنامهنویسی تبدیل میکند.
History
چامسکی گرامرهای مستقل از متن را در اواخر دهه ۱۹۵۰ به عنوان بخشی از سلسله مراتب خود معرفی کرد، و آنها به طور مستقل توسط بکوس و ناور برای تعریف نحو زبان برنامهنویسی ALGOL استفاده شدند. همارزی با اتوماتای پشتهای و نظریه ساختاری این کلاس در طول دهه ۱۹۶۰ توسعه یافت.
Key figures
- Noam Chomsky
- John Backus
- Seymour Ginsburg
- Sheila Greibach
Related topics
Seminal works
- sipser2013
- hopcroft2006
Frequently asked questions
- چرا تجزیه یک زبان برنامهنویسی به پشته نیاز دارد؟
- برنامهها شامل ساختارهای تودرتو مانند پرانتزها، بلوکها و فراخوانیهای تابع هستند که عمق تطابق آنها نامحدود است. یک پشته هر ساختار ناتمام را ثبت میکند و هنگام بسته شدن آن را از پشته خارج میکند، که دقیقاً همان نظم حافظهای است که یک اتوماتای پشتهای فراهم میکند و یک اتوماتای متناهی فاقد آن است.
- مبهم بودن یک گرامر به چه معناست؟
- یک گرامر زمانی مبهم است که یک رشته بیش از یک درخت تجزیه داشته باشد، به این معنی که میتواند با ساختارهای واقعاً متفاوت مشتق شود. ابهام برای زبانهای برنامهنویسی نامطلوب است زیرا معنای کد را نامشخص میکند، بنابراین طراحان زبان به دنبال گرامرهای بدون ابهام هستند یا قوانین رفع ابهام را اضافه میکنند.