تجزیه‌کننده ال‌ای‌ال‌آر

در علوم کامپیوتر تجزیه‌کنندهٔ LALR یک نسخهٔ ساده‌شده از تجزیه‌کنندهٔ LR است. تجزیه یک متن از مجموعه قوانین تولید شده توسط گرامر رسمی برای زبان کامپیوتر پیروی می‌کند.روش تجزیه‌کننده LALR در سال 1969 توسط Frand Deremer که بر روی پایان‌نامهٔ دکترایش(مترجم عملی برای زبان های(LR(K) ) کار می‌کرد به منظور رسیدگی به مشکلات عملی زمان اجرای تجزیه‌کننده متعارف LR اختراع شد.با این ساده‌سازی نتایج در حافظه مورد نیازی که به شدت کاهش یافته قرار می‌گیرند اما قدرت تشخیص زبان‌های کمی را دارد.اما قدرتش برای بسیاری از زبان‌های ماشیناز جمله جاوا به اندازه کافی است.ولی LALR برای گرامر مرجع بسیاری از زبان‌های مبهم با شکست مواجه می‌شود.به علاوه کدهایی که با دست نوشته شده‌اند با توجه به زبان ای که دارد تجزیه می‌شود، می‌تواند قدرت LALR را بالا برد.

در عمل تجزیه‌کننده‌های LALR با دست نوشته نمی‌شوند.به جای آن به صورت خودکار از گرامر تولیدکننده تحزیه‌کننده LALR مانند YACC و بایسون تولید می‌شوند.کد تولید شده خودکار ممکن است توسط کد دست‌نویس برای تقویت توان نتایج تجزیه‌کننده تقویت شده باشد.

تاریخچه

دانلد کنوت در سال 1965 تجزیه‌کننده ال آر را اختراع کرد.تجزیه‌کننده LR می‌تواند هر زبان مستقل از متن قطعی را در زمان خطی محدود تشخیص دهد.اما چون سمت راست‌ترین اشتقاق حافظه مورد نیاز بسیار بزرگی دارد اجرای تجزیه‌کننده LR به دلیل حافظه محدود در آن زمان نشدنی است.برای رسیدگی به این ضعف در سال 1969 Frank DeRemer دو نسخه ساده شده از تجزیه‌کننده LR را در نظر گرفت.یکی LR پیشگو (LALR) و دیگری تجزیه‌کننده ال‌آر ساده که نیاز به حافظه بسیار پایین‌تر و قدرت تشخیص زبان‌های کمتری را در مقایسه با LALR دارد بهترین گزینه است.پس از آن در سال 1977 بهینه‌سازی تجزیه‌کننده LR اختراع شد اما هنوز هم تجزیه‌کننده LR حافظه کارآمد کمتری نسبت به گزینه‌های ساده داشت.

در سال 1979 Frank DeRemer و Tom Pennello اعلام کردند که یک سری بهینه‌سازی برای تجزیه‌کننده LALR که بیشتر به بهبود کارایی حافظه مربوط است ارائه کردند ولی ارائه رسمی این بهینه‌سازی در سال 1982 بود.

دید کلی

به‌طور کلی تجزیه کنند LALR به تجزیه‌کننده (LALR(1 ارجاع داده می‌شود مثل تجزیه‌کننده LR که به (LR(1 ارجاع داده می‌شود.(1) نشان دهنده یک token بودن lookahead است و تفاوت‌های میان الگوهای قوانین در طول تجزیه را رفع می‌کند.به‌طور مشابه یک (LALR(2 تجزیه‌کننده‌ای است که lookahead آن دو token است و lookahead در (LALR(k هم k توکن در نظر می‌گیرد.اما این حالت در استفاده خیلی کم اتفاق می افتد.تجزیه‌کننده LALR بر اساس تجزیه‌کننده (LR(0 است.پس می‌تواند نشان داده شود (LALR(1) = LA(1)LR(0 (یک token از lookahead و (LR(0) یا به‌طور کلی (LALR(k) = LA(k)LR(0 که (token k از lookahead و (LR(0).در حقیقت یک خانواده دو پارامتری از تجزیه‌کننده‌های (LA(k)LR(j برای همه ترکیبات از j و k که می‌تواند از (LR(j + k مشتق شود.اما این استفاده را عملاً نمی‌بینیم.

مانند دیگر شکل‌های تجزیه‌کننده LR تجزیه‌کننده LALR هم یک تجزیه‌کننده پایین به بالا در یک اسکن چپ به راست از ورودی‌ها است نیازی به عقبگرد ندارد و در حالتی که یک lookahead داشته باشیم طبق تعریف (LALR(1 بیشترین استفاده را دارد.

ارتباط با سایر تجزیه‌کننده ها

تجزیه‌کننده‌های LR

تجزیه‌کننده (LALR(1 قدرت خیلی کمتری نسبت به تجزیه‌کننده(LR(1 دارد و بسیار قوی تر از تجزیه‌کننده (SLR(1 است.با وجود آنکه همه آن‌ها قوانین تولید یکسان دارند.همهٔ اختلالات زمان اجرای تجزیه (LALR(1 که بر روی یک گرامر (LR(1 غیر مبهم اعمال شود از نوع کاهش-کاهش است.

اختلالت کاهش -کاهش یک مثال استاندارد از گرامر (LR(1 است که نمی‌تواند با تجزیه‌کننده (LALR(1 تجزیه شود.

  S → a E c
    → a F d
    → b F c
    → b E d
  E → e
  F → e

در ساخت جدول LALR دو حالت با هم در یک حالت ادغام می‌شوند که ممکن است lookaheadها مبهم شوند.یک حالت با lookaheadهایش در زیر آمده‌است.

E → e. {c,d}
F → e. {c,d}

تجزیه‌کننده (LR(1 می‌تواند دو حالت مختلف را بدون ابهام (بدون اختلالات lookahead) ایجاد کند.در تجزیه‌کننده LALR که یک حالت با اعمال متضاد (اختلالات کاهش-کاهش) دارد(مانند گرامر بالا)، تولیدکننده تجزیه‌کننده LALR اعلان می‌کند که گرامر مبهم است و اختلالات را گزارش می‌دهد.این ابهام با انتخاب E رفع می‌شود (چون در گرامر E قبل از F قرار دارد).اما نتیجه تجزیه‌کننده نمی‌تواند دنباله b e c را تشخیص دهد.زیرا دنباله مبهم e c با E → e) c) به جای F → e) c) کاهش می یابد و b E c در گرامر وجود ندارد.

تجزیه‌کننده‌های LL

تجزیه‌کننده‌های (LALR(K قابل مقایسه با تجزیه‌کننده‌های (LL(K نیستند.به ازای هر k و j که بزرگتر از صفر هستند گرامرهای (LALR(j گرامر (LL(k نیستند و برعکس.درحقیقت برای هر k بزرگتر مساوی صفر نمی‌توانیم تصمیم بگیریم که گرامر (LL(1 گرامر (LALR(K هست یا نه؟

اغلب این ادعا که هر گرامر(LL(1 گرامر (SLR(1 و (LALR(1 است اشتباه است ، اما گرامرهای (LL(1 وجود دارد که (LALR(1 نیست پس (SLR(1 هم نیست.گرامر (LL(1 در شرایط تکنیکی اضافی خاص (LALR(1 می‌باشد و با شرایط خاص تر (SLR(1 می‌باشد.این شرایط ساده از تولید قوانین بی‌فایده خاص جلوگیری می‌کند و به همین ترتیب در عمل رضایت بخش خواهد بود (با فرض آنکه در گرامر خطا نداشته باشیم).بنابراین گرامر (LL(1 به‌طور کلی در عمل (LALR(1 خواهد بود.

مسائل مربوط به پیاده سازی

چون تجزیه‌کننده‌های LALR به جای اشتقاق چپ که بیشترین استفاده را دارد از اشتقاق راست استفاده می‌کنند، درک نحوه عملکرد آن بسیار مشکل است و این امر سبب می‌شود روند پیدا کردن گرامر صحیح و کارآمد بسیار طاقت فرسا و وقت گیر باشد.به همین دلیل گزارش خطا می‌تواند بسیار سخت یاشد زیرا خطاهای تجزیه‌کننده LALR نمی‌توانند همیشه به پیام‌های با ترم‌های سطح بالای معنادار برای کاربر نهایی تفسیر شوند.با این حال هر جدول (LR (k>0 این امکان را می‌دهد که در هنگام بروز خطای دستوری tokenهای ممکن برای خطارا بشناسیم.به همین دلیل تجزیه‌کننده بازگشتی نزولی گاهی به تجزیه‌کننده LALR ترجیح داده می‌شود.این تجزیه‌کننده چون قدرت تشخیص زبان پایینی دارد نیاز به کد دست‌نویس بیشتری دارد.

نمونه قابل توجه از این پدیده تجزیه‌کنندهٔ جی‌سی‌سی زبان ++C و C است.این به عنوان تجزیه‌کننده LALR آغاز شده‌است اما بعد به تجزیه‌کننده‌های بازگشتی نزولی تبدیل شده‌است.

جستارهای وابسته

• تحلیل واژگانی
• تجزیه‌کننده
• پارسر ال‌ال
• گرامر مستقل از متن

پیوند به بیرون

• Parsing Simulator This simulator is used to generate parsing tables LALR and resolve the exercises of the book.
• JS/CC بایگانی‌شده در ۱۳ مارس ۲۰۱۴ توسط Wayback Machine JavaScript based implementation of a LALR(1) parser generator, which can be run in a web-browser or from the command-line.
• LALR(1) tutorial بایگانی‌شده در ۱۵ ژانویه ۲۰۱۴ توسط Wayback Machine, a flash card-like tutorial on LALR(1) parsing.