گرامر ون وینجگاردن
 | برخی از ویرایش‌ها در این مقاله در چارچوب یک تکلیف دانشگاهی انجام شده‌اند. این تکالیف توسط ؟ برای دانشجویان ؟ تعیین شده‌اند. |
 | این مقاله، گرامر ون وینجگاردن، اخیراً بهواسطهٔ فرایند ایجاد مقاله ایجاد شده‌است. بازبینیکننده در حال بستن درخواست است و این برچسب احتمالاً بهزودی برداشته می‌شود.
ابزارهای بازبینی: پیشبارگیری بحث اعلان به نگارنده |
خطای اسکریپتی: پودمان «AfC submission catcheck» وجود ندارد. در علوم کامپیوتر، گرامر ون ویجگاردن(VanWijngaarden) (همچنین vW-grammar یا W-grammar[۱]) یک گرامر دو سطحی است که تکنیکی را برای تعریف گرامرهایی که به‌طور قطعی بی‌نهایت و مستقل از متن در تعداد محدودی از قوانین ارائه می‌کند. نحوه زبان توسط آدریان ون وینجگاردن[۲] ابداع شد تا برخی محدودیت‌های نحوی را که قبلاً علی‌رغم محتوای اساساً نحوی‌شان، باید به زبان طبیعی فرمول‌بندی می‌شدند، به دقت تعریف کند.
کاربردهای مرسوم عبارت اند از درمان جنس و عدد در نحو(syntax) زبان‌های طبیعی و مشخص بودن شناسه‌ها در زبان‌های برنامه‌نویسی. برای مثال، «یک نفر وجود دارد» و «دو نفر وجود دارند» هر دو از نظر گرامری صحیح هستند، اما «یک نفر وجود دارند» به دلایل حساس به متن که یک گرامر W می‌تواند تشخیص دهد، نادرست است.
این شیوه در تعریف زبان و توسعه زبان برنامه‌نویسی ALGOL 68 استفاده شد. این یک نمونه مثال از کلاس بزرگتر گرامرهای پیوست است.
بررسی کلی[ویرایش]
یک گرامر W از تعدادی مجموعه متناهی قوانین متا تشکیل شده‌است که برای استخراج (احتمالاً تعداد بی‌نهایت) قواعد تولید، از مجموعهٔ محدودی از قوانین هایپر استفاده می‌شود. قوانین متا محدود به آنهایی (قوانینی) هستند که توسط دستور زبان مستقل از متن تعریف شده‌اند. قوانین هایپر، متن‌های قابل قبول را در سطح‌های بالاتر محدود می‌کنند. اساساً، ثبات جانشینی که در فرایند اشتقاق استفاده می‌شود، معادل یکسان سازی است، همان‌طور که در Prolog، توسط آلن کولمرائر اشاره شد..
برای مثال، تخصیص x:=1 تنها زمانی معتبر است که متغیر x بتواندیک عدد صحیح را در خود جای دهد. به همین دلیل دستور مستقل از متن variable:= value ناقص است. در یک گرامر دو سطحی، این ممکن است به روشی حساس به متن به عنوان REF TYPE variable := TYPE value . سپس ref integer variable := integer value یک قانون تولید باشد اما ref Boolean variable := integer value ممکن نیست یک قانون تولید باشد. این همچنین بدان معنی است که تخصیص با انواع ناسازگار به یک خطای نحوی تبدیل می‌شود که می‌تواند در زمان کامپایل برنامه پیدا شود. به‌طور مشابه،
STYLE begin token, new LAYER1 preludes, parallel token, new LAYER1 tasks PACK, STYLE end token
اجازه begin ... end و { ... } را می‌دهد اما begin ... } اشتباه است.
نمونه‌های ALGOL 68[ویرایش]
قبل از ALGOL 68، زبان ALGOL 60 با استفاده از فرم Backus-Naur مستقل از متن رسمیت یافت. ظهور گرامر دو سطحی جدید حساس به متن چالشی را برای برخی از خوانندگان «گزارش نهایی» ALGOL 68 در سال ۱۹۶۸ ایجاد کرد. متعاقباً، گزارش نهایی توسط Wijngaarden و همکارانش مورد بازنگری قرار گرفت و به عنوان «گزارش تجدید نظر شده» ALGOL 68 در سال ۱۹۷۳ منتشر شد.
دستور زبان ALGOL 68 به‌طور رسمی در گرامر دو سطحی Van Wijngaarden تعریف شده‌است، اما یک زیر مجموعه به شکل Backus-Naur یک سطحی انجام شده‌است، مقایسه:
ALGOL 68 در گزارش نهایی ۱۹۶۸ §۲٫۱[ویرایش]
a) program: open symbol, standard prelude, library prelude option, particular program, exit, library postlude option, standard postlude, close symbol. b) standard prelude: declaration prelude sequence. c) library prelude: declaration prelude sequence. d) particular program : label sequence option, strong CLOSED void clause. e) exit: go on symbol, letter e letter x letter i letter t, label symbol. f) library postlude: statement interlude. g) standard postlude: strong void clause train
ALGOL 68 در گزارش اصلاح شده §۲٫۲٫۱، §۱۰٫۱٫۱، سال ۱۹۷۳[ویرایش]
این بخش مانند بخش امگلیسی بوده
پیاده‌سازی‌ها[ویرایش]
yo-yo[۵] تجزیه کننده ای برای گرامرهای ون ویجگاردن(van Wijngaarden) با گرامرهای مثال عبارات، eva , sal و پاسکال (استاندارد واقعی ISO 7185 برای پاسکال از فرم توسعه یافته Backus-Naur استفاده می‌کند) است.
تاریخچه[ویرایش]
گرامرهای W مبتنی بر ایده ارائه نمادهای ناپایانی گرامرهای مستقل از متن با ویژگی هایی (یا پسوندها) هستند که اطلاعات را بین گره‌های درخت تجزیه منتقل می‌کنند که برای محدود کردن نحو و مشخص کردن معناشناسی استفاده می‌شود. این ایده در آن زمان به خوبی شناخته شده بود. به عنوان مثال دونالد کنات از کمیته طراحی ALGOL 68 دیدن کرد و در حالی که نسخه خود را از، ویژگی گرامرها توسعه می‌داد.[۶] بخش عجیب برای گرامرهای W برخورد سخت آنها با ویژگی‌ها به‌عنوان رشته‌ها بود که توسط گرامر مستقل از متن تعریف می‌شد، که الحاق تنها عملیات ممکن بر روی آنها بود. در گرامرهای صفت، صفت‌ها می‌توانند از هر نوع داده‌ای باشند و هر نوع عملیاتی را می‌توان روی آنها انجام داد.
پس از معرفی آنها در گزارش الگول(Algol) 68، گرامرهای W به‌طور گسترده‌ای بیش از حد قدرتمندو همین‌طور بدون محدودیت در نظر گرفته شدند تا عملی باشند .[نیازمند منبع] این تا حدی نتیجه روشی بود که در آن به کار گرفته شده بود. گزارش اصلاح شده Algol 68 حاوی دستور زبان بسیار خواناتری بود، بدون اینکه خود فرمالیسم گرامر W را اصلاح کند.
در همین حال، مشخص شد که گرامرهای W، هنگامی که در حالت کلی مورد استفاده قرار می‌گیرند، در واقع برای اهداف عملی مانند ورودی برای یک تولیدکننده تجزیه کننده بسیار قدرتمند هستند. آنها به درستی همه زبان‌های برگشتی را توصیف می‌کنند،[۷] که تجزیه را به‌طور کلی غیرممکن می‌کند: تصمیم‌گیری در مورد مشکل اینکه آیا یک رشته معین می‌تواند توسط یک گرامر W ایجاد شود یا خیر، غیرقابل بحث است. هنگام استفاده برای تجزیه یا ترجمه خودکار، استفاده از آنها باید به‌طور جدی محدود شود. انواع محدود و اصلاح شده گرامرهای W برای رسیدگی به این موضوع توسعه داده شد، به عنوان مثال
- Extended Affix Grammar (EAGs)، که برای توصیف گرامرهای زبان طبیعی مثل انگلیسی و اسپانیایی استفاده می‌شود.
- سیستم‌های Q، همچنین برای پردازش زبان طبیعی اعمال می‌شود.
- سری CDL از زبان‌ها، به عنوان زبان‌های ساخت کامپایلر برای زبان‌های برنامه‌نویسی استفاده می‌شود.
برنامه‌های کاربردی خارج از ALGOL 68[ویرایش]
آنتونی فیشر(Anthony Fisher) یک تجزیه کننده (پارسر) برای کلاس بزرگی از گرامرهای W نوشته‌است.[۵]
دیک گرون(Dick Grune) یک برنامه C نوشت که تمام مقادیرد ممکن تولید شده توسط گرامر ۲ سطحی را تولید می‌کرد.[۸]
کاربردهایی از EAGها که در بالا ذکر شد را می‌توان به صورتی مؤثر به عنوان کاربردهای گرامرهای W در نظر گرفت، زیرا EAGها بسیار نزدیک به گرامرهای W هستند.
گرامرهای W برای توصیف اعمال پیچیده انسان در ارگونومی هم پیشنهاد شده‌است .[نیازمند منبع]
- توضیحات گرامر W برای Ada[۹] - «توصیف W-grammar Ada هنوز برای آن دسته از دانشمندان رایانه ای مفید است که به بیش از درک ساده نحو و توصیف ابتدایی معنایی نیاز دارند.»
جستارهای وابسته[ویرایش]
منابع[ویرایش]
- ↑ Cleaveland, J. Craig; Uzgalis, Robert C. (1977). Grammars for Programming Languages. ISBN 978-0-444-00199-3. Unknown parameter
|publishe=ignored (help)صفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد. - ↑ van Wijngaarden, Adriaan (1965), MR 76: Orthogonal design and description of a formal language (PDF), Amsterdam, The Netherlands: CWIصفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد..
- ↑ Kleine, "Algol 68", Languages history (PDF) (report attachment), DE: FH Jenaصفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد..
- ↑ "Syntax", Algol 68, FR: Univ Poitiersصفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد..
- ↑ ۵٫۰ ۵٫۱ Fisher, Anthony, "yo-yo", Software, UK: Yorkصفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد..
- ↑ Knuth, Donald E (1990), "The genesis of attribute grammars" (Plain TeX, gZiped), Proceedings of the international conference on Attribute grammars and their applications, Springer Verlag: 1–12صفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد..
- ↑ Sintzoff, M. (1967). "Existence of a van Wijngaarden syntax for every recursively enumerable set". Annales de la Société scientifique de Bruxelles. 81: 115–118.صفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد.
- ↑ Grune, Dick, A Two-Level Sentence Generator, NL: VUصفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد..
- ↑ ADA177802: A W-Grammar Description for Ada, US: DTICصفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد..
پیوند به بیرون[ویرایش]
- "Use in Algol68", Computer science, Book ragsصفحه پودمان:Citation/CS1/en/styles.css محتوایی ندارد..
- Pemberton, Steven, VW (tutorial introduction), NL: CWIصفحه پودمان: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.
