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

تجزیه‌کننده LR (انگلیسی:LR parser)، یک تجزیه‌کننده پایین به بالا است که زبان‌های مستقل از متن قطعی را در زمان چند جمله‌ای تجزیه می‌کند و در ساختن کامپایلرها کاربرد دارد. نام تجزیه‌کننده ال ار از سه بخش ال ،ار و یک عدد ${\displaystyle k}$ تشکیل شده‌است که بخش ال آن به این معنا است که این تجزیه‌‌کننده رشته ورودی را از چپ به راست تجزیه می‌کند و قسمت ار آن به این معنا است که همیشه راست‌ترین اشتقاق ممکن را انجام می‌دهد و عدد ${\displaystyle k}$ به این معنا است که هنگام تجزیه به ${\displaystyle k}$ حرف جلو تر در رشته ورودی نگاه می‌کند و پیش‌بینی می‌کند که چگونه اشتقاق را انجام دهد.

از معروف‌ترین تجزیه‌کننده‌های ال ار می‌توان به تجزیه‌کننده ${\displaystyle LR(1),LR(0),SLR,LALR}$ اشاره کرد که همهٔ آن‌ها تمام ویژگی‌های ذکر شده در قسمت بالا را دارند. تجزیه‌کننده‌های ال ار از تجزیه‌کننده‌هایی که به روش بالا به پایین کار می‌کنند قدرت بیشتری دارد و زبان‌های بیشتری را می‌تواند تجزیه کند. سرعت پیدا کردن خطا نیز در تجزیه‌کننده‌های ال ار به مراتب از تجزیه‌کننده‌های بالا به پایین مانند ${\displaystyle LL(1)}$ بالاتر است و در حالی که از چپ به راست رشته را تجزیه می‌کند به محض پیدا کردن خطا آن را گزارش می‌دهد.

دید کلی و مثال

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

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

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

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)}$ وجود دارد در تعداد حرف‌هایی است که این دو تجزیه‌کننده، برای پیش‌بینی استفاده می‌کنند. همچنین تفاوتی که میان سه تجزیه‌کننده ${\displaystyle LR(0),SLR,LALR}$ وجود دارد، در نحوه ساختن ماشین حالت است که تجزیه‌کننده LALR و SLR سعی کرده‌اند که از تعداد حالات کمتری برای ساخت ماشین حالت خود استفاده کنند تا سرعت تجزیه کردن بهبود یابد.

منابع

پیوند به بیرون

• 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