تجزیه‌کننده جی‌ال‌آر
 | برای تأییدپذیری کامل این مقاله به منابع بیشتری نیاز است. (ژانویه ۲۰۱۸) |
تجزیه‌کنندهGLR (انگلیسی:GLR parser)، یک الگوریتم تجزیه‌کننده LR برای کنترل گرامرهای غیرممکن و مبهم است. پایه نظری آن در مقاله ۱۹۷۴ توسط برنارد لنگ (همراه با دیگر پارسرهای مستقل از متن مانند GLL) ارائه شد.
این پارسر یک روش سیستماتیک برای تولید چنین الگوریتمی را توصیف می‌کند و نتایج متفاوتی را در مورد اثبات صحت و پیچیدگی با توجه به کلاس‌های گرامری و روش‌های بهینه‌سازی ارائه می‌دهد. اولین اجرای واقعی GLR توسط ماسارو تومیتا در مقاله‌ای در سال۱۹۸۴ شرح داده‌شده‌است، همچنین به عنوان «تجزیه‌کننده موازی» نیز معرفی شده‌است. تومیتا پنج مرحله را در کار اصلی خود ارائه داد، اگر چه در عمل مرحله دوم است که به عنوان تجزیه‌کننده GLR شناخته می‌شود.
اگر چه این الگوریتم از زمان شکل‌گیری اولیه تکامل یافته‌است، اما اصولی از آن باقی مانده‌اند. همانگونه که در یکی از مقاله‌های قبلی نشان داده شده‌است، لنگ در ابتدا به پارسرهای انعطاف‌پذیرتر که برای زبان‌های برنامه‌نویسی به راحتی مورد استفاده قرار می‌گیرند علاقه‌مند بود. هدف تومیتا این بود که متن زبان طبیعی را به‌طور کامل و کارآمد تجزیه کند. پارسرهای استاندارد LR نمی‌توانند ماهیت غیرمتمرکز و مبهم زبان طبیعی را در نظر بگیرند ولی الگوریتم GLR می‌تواند این کار را انجام دهد.
الگوریتم[ویرایش]
به‌طور خلاصه، الگوریتم GLR به نحوی شبیه الگوریتم تجزیه‌کننده LR کار می‌کند، با این تفاوت که با توجه به گرامر خاص، یک تجزیه‌کننده GLR تمام تفسیرهای احتمالی یک ورودی داده را در یک جستجوی اولیه به‌طور گسترده پردازش می‌کند. در قسمت جلویی، یک ژنراتور تجزیه‌کننده GLR گرامر ورودی را به جداول تجزیه‌کننده تبدیل می‌کند و به نحوی شبیه به یک ژنراتور LR کار می‌کند. با این حال، جداول تجزیه LR تنها یک حالت‌گذار (با توجه به حالت و یک ورودی نشانه) را پشتیبانی می‌کنند در حالی که GLR این امکان را می‌دهد هم‌زمان چند حالت‌گذار منتقل شوند. در واقع، GLR از ناسازگاری‌های تغییر، کاهش و کاهش، کاهش پشتیبانی می‌کند. هنگامی که یک انتقال متضاد اتفاق می‌افتد، پشته تجزیه به دو یا چند پشته تجزیه موازی متصل می‌شود، جایی که وضعیت مربوط به هر انتقال در بالا قرار می‌گیرد. سپس نشانه ورودی بعدی برای تعیین انتقال‌های بعدی برای هر یک از حالت‌های «بالا» خوانده و استفاده می‌شود و منشعب شدن می‌تواند رخ دهد. اگر هر کدام از مقادیر بالا و ورودی، حداقل یک‌گذار نداشته باشند، این «مسیر» از طریق جداول تجزیه نامعتبر خوانده می‌شود و می‌تواند از بین برود. بهینه‌سازی حیاتی اجازه می‌دهد تا با اشتراک‌گذاری پیشوندهای معمول و پسوندهای این پشته‌ها، که فضای جستجوی کلی و استفاده از حافظه مورد نیاز برای تجزیه متن ورودی را محدود می‌کند، ساختارهای پیچیده‌ای که از این پیشرفت‌ها به وجود می‌آیند و همچنین گراف جستجو را که یک گراف آسیلیک خطی است (با محدودیت‌های اضافی در «عمق» گره‌های مختلف)، به جای یک درخت استفاده کند.
مزیت‌ها[ویرایش]
تشخیص با استفاده از الگوریتم GLR همان پیچیدگی‌های زمانی بدترین حالت را مثل الگوریتم CYK و الگوریتم Earley که برابر O (n3) هست را دارد. با این وجود، GLR دارای دو مزیت دیگر است:
- زمان مورد نیاز برای اجرای الگوریتم متناسب با درجه غیر قطعی بودن در گرامر است: در گرامرهای قطعی، الگوریتم GLR در زمان O (n) اجرا می‌شود (این در مورد الگوریتم ارلی و CYK درست نیست، اما الگوریتم‌های Earley را می‌توان طوری تغییر داد که از آن مطمئن شد)
- الگوریتم GLR «آنلاین» است - به این ترتیب، ورودی‌ها را با نظم خاصی برداشته و پس از برداشتن هر علامت بیشترین کار ممکن را بر روی آن انجام می‌دهد.
در عمل، گرامرهای بسیاری از زبان‌های برنامه‌نویسی قطعی یا «تقریباً قطعی» هستند، به این معنی که هر غیرقطعیتی معمولاً در تعداد کمی (هرچند احتمالاً نامحدود) از نشانه‌ها حل می‌شود. در مقایسه با سایر الگوریتم‌هایی که قادر به اداره کلاس‌های کامل گرامرهای مستقل از متن هستند (مانند Earley یا CYK)، الگوریتم GLR عملکرد بهتری در گرامرهای «تقریباً قطعی» دارد، زیرا در طول فرایند تجزیه تنها یک پشته فعال خواهد بود. در یک پارسر هیبریدی می‌توان GLR را با الگوریتم LALRترکیب کرد، که امکان عملکرد بالاتر را نیز فراهم می‌کند.
منابع[ویرایش]
پیوند به بیرون[ویرایش]
- Grune, Dick; Jacobs, Ceriel J.H (2008). Parsing Techniques. Springer Science+Business Media. ISBN 978-0-387-20248-8.
- Tomita, Masaru (1984). "LR parsers for natural languages". COLING. 10th International Conference on Computational Linguistics. pp. 354–357.
- Tomita, Masaru (1985). "An efficient context-free parsing algorithm for natural languages". IJCAI. International Joint Conference on Artificial Intelligence. pp. 756–764.