تجزیه‌کننده ال‌آر
تجزیه‌کننده LR (انگلیسی:LR parser)، یک تجزیه‌کننده پایین به بالا است که زبان‌های مستقل از متن قطعی را در زمان چند جمله‌ای تجزیه می‌کند و در ساختن کامپایلرها کاربرد دارد. نام تجزیه‌کننده ال ار از سه بخش ال ،ار و یک عدد formula_1 تشکیل شده‌است که بخش ال آن به این معنا است که این تجزیه‌‌کننده رشته ورودی را از چپ به راست تجزیه می‌کند و قسمت ار آن به این معنا است که همیشه راست‌ترین اشتقاق ممکن را انجام می‌دهد و عدد formula_1 به این معنا است که هنگام تجزیه به formula_1 حرف جلو تر در رشته ورودی نگاه می‌کند و پیش‌بینی می‌کند که چگونه اشتقاق را انجام دهد.
از معروف‌ترین تجزیه‌کننده‌های ال ار می‌توان به تجزیه‌کننده formula_4 اشاره کرد که همهٔ آن‌ها تمام ویژگی‌های ذکر شده در قسمت بالا را دارند. تجزیه‌کننده‌های ال ار از تجزیه‌کننده‌هایی که به روش بالا به پایین کار می‌کنند قدرت بیشتری دارد و زبان‌های بیشتری را می‌تواند تجزیه کند. سرعت پیدا کردن خطا نیز در تجزیه‌کننده‌های ال ار به مراتب از تجزیه‌کننده‌های بالا به پایین مانند formula_5 بالاتر است و در حالی که از چپ به راست رشته را تجزیه می‌کند به محض پیدا کردن خطا آن را گزارش می‌دهد.
یک تجزیه‌کننده ال آر، ورودی را از چپ به راست می‌خواند و درخت تجزیه را همیشه از چپ به راست و به صورت پایین به بالا رسم می‌کند. این تجزیه‌کننده همیشه فهرستی از زیردرخت‌هایی که در انتهای آن قرار دارند را نگه می‌دارد. در واقع این تجزیه‌کننده همیشه راست‌ترین زیردرختی که وجود دارد را نگه می‌دارد. هنگامی که این تجزیه‌کننده از چپ به راست حرکت می‌کند، با توجه به حرف جدیدی که جلوی آن قرار دارد و زیردرختی که در آخر لیست قرار دارد، یکی از قواعد را بر روی آن اعمال می‌کند و زیر درختی جدید را به وجود می‌آورد.
برای مثال فرض کنید قواعد شکل روبرو به شکل زیر باشد: هنگامی که تجزیه‌کننده از چپ به راست حرکت خودش را آغاز می‌کند به توجه به قاعده ۳و۱ int را به E تبدیل می‌کند. سپس بعد از عبور از ) به دلیل وجود نداشتن قاعده‌ای، int را به E تبدیل کرده سپس از مثبت عبور کرده و int را به T تبدیل می‌کند. سپس با توجه به اینکه از روی یک E , + عبور کرده‌است، از قاعدهٔ ۲، به حرف E تبدیل می‌شود و این روند ادامه پیدا می‌کند تا به در آخر به یک حرف E ختم شود. همان‌طور که در مثال مشاهده می‌شود، این تجزیه‌کننده همیشه با توجه به زیر درختی که در قبل وجود دارد، یا حرف جدید را رد می‌کند یا یکی از قواعد را بر روی آن اعمال می‌کند
با توجه به مثالی که در قسمت قبل وجود داشت، تجزیه‌کننده ال آر، همیشه به هر ورودی جدیدی که می‌رسد، یا از روی آن عبور می‌کند یا با استفاده از یکی از قواعد زبان آن را کاهش می‌دهد. در نتیجه عملیات‌هایی که یک تجزیه‌کننده ال آر انجام می‌دهد به یکی از دو شکل زیر است:
انتقال: در این عملیات، تجزیه‌کننده ال آر ورودی جدید را که می‌خواند، از روی آن عبور کرده و قاعده‌ای را بر روی آن اعمال نمی‌کند و آن را به پشته خود اضافه می‌کند.
کاهش: در این عملیات، تجزیه‌کننده ال آر ورودی جدید را که می خواند، با توجه به آخرین حرفی که در پشته وجود دارد، با استفاده از یکی از قواعد عملیات کاهش را انجام می دهد و حرف جدید را جایگزین می‌کند.
برای پیاده‌سازی تجزیه‌کننده ال آر ابتدا باید ماشین تعیین‌پذیر حالات متناهی برای آن پیدا کرد و سپس با استفاده از این ماشین، ورودی داده شده را از پایین به بالا تجزیه کنیم. برای ساخت این ماشین حالت، ابتدا یک حالت ابتدایی قرار می‌دهیم که در آن تمام قواعد موجود در زبان وجود دارند. همچنین برای تمام قواعدی یک علامت در چپ‌ترین قسمت سمت راست قواعد قرار می دهیم که این علامت نشان دهندهٔ این است که در در ورودی تا کدام جایگاه این قاعده را پشت سر هم داشتیم. سپس از این حالت به ازای همهٔ حرف‌های موجود در سمت راست علامت‌ها، یال می‌گذاریم و این روند را ادامه می‌دهیم تا به دیگر حالتی اضافه نشود. با استفاده از ماشین به دست آمده و یک پشته می‌توان هر ورودی که توسط تجزیه‌کننده ال آر، تجزیه پذیر است را تجزیه کرد.
بعد از ساختن ماشین حالت برای تجزیه‌کننده ال آر، برای راحتی انجام دادن عملیات‌های کاهش و انتقال جدولی برای این تجزیه‌کننده می‌سازیم که با توجه به آن بتوان این کار را کرد. برای این کار ابتدا حالات ماشین حالت تجزیه‌کننده ال آر را شماره‌گذاری می‌کنیم. سپس جدولی تشکیل می دهیم که سطرهای آن نشان دهنده حالات باشند و ستون‌های آن نشان دهندهٔ حرف‌های زبان باشند. سپس هر خانه را به صورت پر می‌کنیم که اگر در حالت با شماره آن سطر باشیم و سپس حرفی که متناظر ستون آن خانه است در خروجی ظاهر شود، کدام یک از عملیات‌های انتقال یا کاهش را انجام دهیم و به کدام حالت برویم.
بین انواع مختلف تجزیه‌کننده‌های ال آر که وجود دارند، تفاوت‌هایی وجود دارد که این تفاوت‌ها در تعداد حرف‌هایی که برای پیش‌بینی استفاده می‌کنند و همچنین در ساخت ماشین حالت برای این تجزیه‌کننده ‌ها وجود دارد. برای مثال تفاوتی که بین تجزیه‌کننده formula_6 وجود دارد در تعداد حرف‌هایی است که این دو تجزیه‌کننده، برای پیش‌بینی استفاده می‌کنند. همچنین تفاوتی که میان سه تجزیه‌کننده formula_7 وجود دارد، در نحوه ساختن ماشین حالت است که تجزیه‌کننده LALR و SLR سعی کرده‌اند که از تعداد حالات کمتری برای ساخت ماشین حالت خود استفاده کنند تا سرعت تجزیه کردن بهبود یابد.