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

درخت تجزیه پایین به بالا

یک تجزیه‌کننده ال آر، ورودی را از چپ به راست می‌خواند و درخت تجزیه را همیشه از چپ به راست و به صورت پایین به بالا رسم می‌کند. این تجزیه‌کننده همیشه فهرستی از زیردرخت‌هایی که در انتهای آن قرار دارند را نگه می‌دارد. در واقع این تجزیه‌کننده همیشه راست‌ترین زیردرختی که وجود دارد را نگه می‌دارد. هنگامی که این تجزیه‌کننده از چپ به راست حرکت می‌کند، با توجه به حرف جدیدی که جلوی آن قرار دارد و زیردرختی که در آخر لیست قرار دارد، یکی از قواعد را بر روی آن اعمال می‌کند و زیر درختی جدید را به وجود می‌آورد.

برای مثال فرض کنید قواعد شکل روبرو به شکل زیر باشد:

1. E → T
2. E → E + T
3. T → int
4. T → (E)

هنگامی که تجزیه‌کننده از چپ به راست حرکت خودش را آغاز می‌کند به توجه به قاعده ۳و۱ int را به E تبدیل می‌کند. سپس بعد از عبور از ) به دلیل وجود نداشتن قاعده‌ای، int را به E تبدیل کرده سپس از مثبت عبور کرده و int را به T تبدیل می‌کند. سپس با توجه به اینکه از روی یک E , + عبور کرده‌است، از قاعدهٔ ۲، به حرف E تبدیل می‌شود و این روند ادامه پیدا می‌کند تا به در آخر به یک حرف E ختم شود. همان‌طور که در مثال مشاهده می‌شود، این تجزیه‌کننده همیشه با توجه به زیر درختی که در قبل وجود دارد، یا حرف جدید را رد می‌کند یا یکی از قواعد را بر روی آن اعمال می‌کند

تجزیه و کاهش

با توجه به مثالی که در قسمت قبل وجود داشت، تجزیه‌کننده ال آر، همیشه به هر ورودی جدیدی که می‌رسد، یا از روی آن عبور می‌کند یا با استفاده از یکی از قواعد زبان آن را کاهش می‌دهد. در نتیجه عملیات‌هایی که یک تجزیه‌کننده ال آر انجام می‌دهد به یکی از دو شکل زیر است:

انتقال: در این عملیات، تجزیه‌کننده ال آر ورودی جدید را که می‌خواند، از روی آن عبور کرده و قاعده‌ای را بر روی آن اعمال نمی‌کند و آن را به پشته خود اضافه می‌کند.

کاهش: در این عملیات، تجزیه‌کننده ال آر ورودی جدید را که می خواند، با توجه به آخرین حرفی که در پشته وجود دارد، با استفاده از یکی از قواعد عملیات کاهش را انجام می دهد و حرف جدید را جایگزین می‌کند.

برای پیاده‌سازی تجزیه‌کننده ال آر ابتدا باید ماشین تعیین‌پذیر حالات متناهی برای آن پیدا کرد و سپس با استفاده از این ماشین، ورودی داده شده را از پایین به بالا تجزیه کنیم. برای ساخت این ماشین حالت، ابتدا یک حالت ابتدایی قرار می‌دهیم که در آن تمام قواعد موجود در زبان وجود دارند. همچنین برای تمام قواعدی یک علامت در چپ‌ترین قسمت سمت راست قواعد قرار می دهیم که این علامت نشان دهندهٔ این است که در در ورودی تا کدام جایگاه این قاعده را پشت سر هم داشتیم. سپس از این حالت به ازای همهٔ حرف‌های موجود در سمت راست علامت‌ها، یال می‌گذاریم و این روند را ادامه می‌دهیم تا به دیگر حالتی اضافه نشود. با استفاده از ماشین به دست آمده و یک پشته می‌توان هر ورودی که توسط تجزیه‌کننده ال آر، تجزیه پذیر است را تجزیه کرد.

بعد از ساختن ماشین حالت برای تجزیه‌کننده ال آر، برای راحتی انجام دادن عملیات‌های کاهش و انتقال جدولی برای این تجزیه‌کننده می‌سازیم که با توجه به آن بتوان این کار را کرد. برای این کار ابتدا حالات ماشین حالت تجزیه‌کننده ال آر را شماره‌گذاری می‌کنیم. سپس جدولی تشکیل می دهیم که سطرهای آن نشان دهنده حالات باشند و ستون‌های آن نشان دهندهٔ حرف‌های زبان باشند. سپس هر خانه را به صورت پر می‌کنیم که اگر در حالت با شماره آن سطر باشیم و سپس حرفی که متناظر ستون آن خانه است در خروجی ظاهر شود، کدام یک از عملیات‌های انتقال یا کاهش را انجام دهیم و به کدام حالت برویم.

بین انواع مختلف تجزیه‌کننده‌های ال آر که وجود دارند، تفاوت‌هایی وجود دارد که این تفاوت‌ها در تعداد حرف‌هایی که برای پیش‌بینی استفاده می‌کنند و همچنین در ساخت ماشین حالت برای این تجزیه‌کننده ‌ها وجود دارد. برای مثال تفاوتی که بین تجزیه‌کننده ${\displaystyle LR(0),LR(1)}$

• dickgrune.com, Parsing Techniques - A Practical Guide 1st Ed. web page of book includes downloadable pdf.
• Parsing Simulator This simulator is used to generate parsing tables LR and to resolve the exercises of the book
• Internals of an LALR(1) parser generated by GNU Bison - Implementation issues
• Course notes on LR parsing
• Shift-reduce and Reduce-reduce conflicts in an LALR parser
• A LR parser example
• Practical LR(k) Parser Construction
• The Honalee LR(k) Algorithm