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

دانلد کنوت در سال 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 آغاز شده‌است اما بعد به تجزیه‌کننده‌های بازگشتی نزولی تبدیل شده‌است.

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