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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم کامپیوتر تجزیه‌کنندهٔ 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 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, a flash card-like tutorial on LALR(1) parsing.