موضوع مقاله: تجزیه‌کننده ال‌ای‌ال‌آر | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تجزیه‌کننده ال‌ای‌ال‌آر | مقدمه: تجزیه یک متن از مجموعه قوانین تولید شده توسط گرامر رسمی برای زبان کامپیوتر پیروی می‌کند.روش تجزیه‌کننده LALR در سال 1969 توسط Frand Deremer که بر روی پایان‌نامهٔ دکترایش(مترجم عملی برای زبان های(LR(K) ) کار می‌کرد به منظور رسیدگی به مشکلات عملی زمان اجرای تجزیه‌کننده متعارف LR اختراع شد.با این ساده‌سازی نتایج در حافظه مورد نیازی که به شدت کاهش یافته قرار می‌گیرند اما قدرت تشخیص زبان‌های کمی را دارد.اما قدرتش برای بسیاری از زبان‌های ماشیناز جمله جاوا به اندازه کافی است.ولی LALR برای گرامر مرجع بسیاری از زبان‌های مبهم با شکست مواجه می‌شود.به علاوه کدهایی که با دست نوشته شده‌اند با توجه به زبان ای که دارد تجزیه می‌شود، می‌تواند قدرت LALR را بالا برد. | ## بخش 1: تجزیه‌کننده ال‌ای‌ال‌آر | در عمل تجزیه‌کننده‌های LALR با دست نوشته نمی‌شوند.به جای آن به صورت خودکار از گرامر تولیدکننده تحزیه‌کننده LALR مانند YACC و بایسون تولید می‌شوند.کد تولید شده خودکار ممکن است توسط کد دست‌نویس برای تقویت توان نتایج تجزیه‌کننده تقویت شده باشد. تاریخچه دانلد کنوت در سال 1965 تجزیه‌کننده ال آر را اختراع کرد.تجزیه‌کننده LR می‌تواند هر زبان مستقل از متن قطعی را در زمان خطی محدود تشخیص دهد.اما چون سمت راست‌ترین اشتقاق حافظه مورد نیاز بسیار بزرگی دارد اجرای تجزیه‌کننده LR به دلیل حافظه محدود در آن زمان نشدنی است.برای رسیدگی به این ضعف در سال 1969 Frank DeRemer دو نسخه ساده شده از تجزیه‌کننده LR را در نظر گرفت.یکی LR پیشگو (LALR) و دیگری تجزیه‌کننده ال‌آر ساده که نیاز به حافظه بسیار پایین‌تر و قدرت تشخیص زبان‌های کمتری را در مقایسه با LALR دارد بهترین گزینه است.پس از آن در سال 1977 بهینه‌سازی تجزیه‌کننده LR اختراع شد اما هنوز هم تجزیه‌کننده LR حافظه کارآمد کمتری نسبت به گزینه‌های ساده داشت. | ## بخش 2: تجزیه‌کننده ال‌ای‌ال‌آر | ارتباط با سایر تجزیه‌کننده ها تجزیه‌کننده‌های LR تجزیه‌کننده (LALR(1 قدرت خیلی کمتری نسبت به تجزیه‌کننده(LR(1 دارد و بسیار قوی تر از تجزیه‌کننده (SLR(1 است.با وجود آنکه همه آن‌ها قوانین تولید یکسان دارند.همهٔ اختلالات زمان اجرای تجزیه (LALR(1 که بر روی یک گرامر (LR(1 غیر مبهم اعمال شود از نوع کاهش-کاهش است. {c,d} تجزیه‌کننده (LR(1 می‌تواند دو حالت مختلف را بدون ابهام (بدون اختلالات lookahead) ایجاد کند.در تجزیه‌کننده LALR که یک حالت با اعمال متضاد (اختلالات کاهش-کاهش) دارد(مانند گرامر بالا)، تولیدکننده تجزیه‌کننده LALR اعلان می‌کند که گرامر مبهم است و اختلالات را گزارش می‌دهد.این ابهام با انتخاب E رفع می‌شود (چون در گرامر E قبل از F قرار دارد).اما نتیجه تجزیه‌کننده نمی‌تواند دنباله b e c را تشخیص دهد.زیرا دنباله مبهم e c با E → e) c) به جای F → e) c) کاهش می یابد و b E c در گرامر وجود ندارد. | ## بخش 3: تجزیه‌کننده ال‌ای‌ال‌آر | اغلب این ادعا که هر گرامر(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 آغاز شده‌است اما بعد به تجزیه‌کننده‌های بازگشتی نزولی تبدیل شده‌است.