موضوع مقاله: تجزیه‌کننده ال‌آر استاندارد | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تجزیه‌کننده ال‌آر استاندارد | مقدمه: تجزیه‌کننده استاندارد LR در علوم کامپیوتر یا تجزیه‌کننده (۱)LR، یک تجزیه‌کننده (LR(k به ازای k=۱، یعنی با یک پایانه پیشرو است. | ## بخش 1: تجزیه‌کننده ال‌آر استاندارد | ویژگی خاص این تجزیه‌کننده این است که هر گرامر (LR(k با k>1 را می‌توان به گرامر (۱)LR تبدیل کرد. در گذشته، تجزیه‌کننده (LR(k به دلیل نیاز به حافظهٔ زیاد و وجود جایگزین‌هایی با قدرت کمتر مانند تجزیه‌کننده LALR و (۱)LL، کمتر مورد استفاده قرار می‌گرفت. با این حال اخیراً یک تجزیه‌کننده (۱)LR کمینه ارائه شده‌است که نیاز به حافظه آن نزدیک به تجزیه‌کننده LALR است که توسط چند تولیدکنندگان تجزیه‌کننده ارائه می‌شود. تاریخچه در سال ۱۹۶۵، دانلد کنوت، تجزیه‌کننده (LR(k را که یک نوع تجزیه‌کننده انتقال-کاهش بود را اختراع کرد. این تجزیه‌کننده دارای پتانسیل شناخت تمام زبان‌های مستقل از متن قطعی بوده و می‌تواند هر دو اشتقاق چپ و راست ورودی را تولید کند. کنوت اثبات کرد که قدرت پذیرش زبان برای K=۱ در حالت بیشینه است و یک روش برای تبدیل گرامر (LR(k با K>1، به گرامر (۱)LR ایجاد کرد. بزرگترین مشکل تجزیه‌کننده استاندارد (۱)LR نیاز به حافظهٔ زیاد برای ایجاد جدول-پارس داخلی خود است. این تجزیه‌کننده‌ها نیاز به حافظه کمتری نسبت به تجزیه‌کننده استاندارد (۱)LR دارند، اما قدرت تشخیص-زبان کمتری دارد. با این حال یک نوع جدید تجزیه‌کننده (LR(۱ با نام تجزیه کننده (۱)LR کمینه در سال ۱۹۷۷ توسط دیوید پابر معرفی شد که نشان داد که می‌توان یک تجزیه کننده (۱)LR ایجاد کرد که حافظهٔ مورد نیاز آن نزدیک تجزیه‌کننده (۱)LALR می‌باشد. | ## بخش 2: تجزیه‌کننده ال‌آر استاندارد | اخیراً بعضی از تولیدکنندگان تجزیه کننده‌ها، تجزیه‌کننده (۱)LR کمینه را ارائه می‌دهند که مشکل حافظه را حل کرده‌اند. ساخت جداول تجزیه ال‌آر جداول تجزیه (LR(۱ همانند جداول تجزیه (LR(0 با تفاوت که در آن هر قطعه شامل یک پایانه پیشرو است. این بدان معنی است که برخلاف تجزیه‌کننده (LR(0، یک عملیات متفاوت ممکن است اجرا شود، اگر قطعه مورد پردازش با یک پایانه متفاوت دنبال شود. قطعه‌های تجزیه‌کننده با شروع براساس قوانین تولید یک زبان، ابتدا باید مجموعه‌های قطعه‌ها را برای این زبان بسازیم. به عبارت ساده‌تر می‌توان گفت یک مجموعه از قطعه‌ها، فهرستی از قوانین تولید است که نماد پردازش در حال حاضر ممکن است بخشی از آن باشد. یک مجموعه از قطعه‌ها رابطه یک به یک با حالت تجزیه‌کننده دارد، همچنین قطعه‌های موجود در مجموعه همراه با نماد بعدی، برای تصمیم‌گیری در مورد تغییرات حالت و عملیات تجزیه کننده استفاده می‌شود. هر قطعه حاوی یک نشانگر است که به جایی که نماد فعلی در آن نقطه از قطعه قرار خواهد گرفت اشاره می‌کند. به عنوان مثال فرض کنید که زبان شامل نمادهای پایانه 'n'، '+'، '('، ')'، و غیرپایانه‌های 'E', 'T'، و قانون شروع 'S' که قوانین تولید زیر را شامل می‌شود: S → E E → T (E → (E T → n T → + T T → T + n مجموعه قطعه‌های ۰ که نشان دهنده وضعیت اولیه است، از قانون شروع تولید می‌شود. هر مجموعه قطعه‌ها باید بسته باشد، یعنی تمام قوانین تولید برای هر غیرپایانه که بعد از '•' بیاید باید به صورت بازگشتی در مجموعه قطعه‌ها قرار داده شود تا همه غیرپایانه مورد بررسی قرار گیرد. | ## بخش 3: تجزیه‌کننده ال‌آر استاندارد | برای زبان‌های پیچیده‌تر این معمولاً به مجموعه‌های بسیار زیادی از قطعه‌ها منجر می‌شود که همین دلیل استفاده از حافظهٔ بزرگ برای تجزیه‌کننده (LR(۱ است. در مثال بالا علامت شروع ما نیاز به پایانه 'E' دارد که 'E' خود نیاز به 'T' دارد و در نتیجه تمام قوانین تولید در مجموعه قطعه شماره ۰ ظاهر می‌شوند. مجموعه (FIRST(A شامل پایانه‌هایی است که می‌توانند به عنوان اولین قسمت از هر زنجیره از قوانین تولید که از غیرپایانه A شروع شود. تعیین پایانه‌های پیشرو با داشتن مجموعه‌های FOLLOW می‌توان مجموعه کامل قطعه‌ها را برای یک تجزیه‌کننده (LR(۱ ایجاد کرد، به این صورت که به ازای هر قطعه در مجموعه بستار آن (مانند (LR(0) و هر پایانه در مجموعه FOLLOW غیرپایانه سمت چپ یک قطعه جدید ایجاد کنیم. برای هر پایانه و هر غیرپایانه A که پس از علامت '•' در مجموعهٔ قطعه‌هایی که تا الان داریم مانند k بیاید، مجموعه‌ای جدید مانند m ایجاد کنید و همه قوانین در k که در آن '•' قبل از A است را به m اضافه کنید. اما فقط در صورتی که m بعد از مرحله ۳ مانند هیچ‌کدام از مجموعه‌هایی که تا الان داریم نشود. همه '•'ها را برای هر قانون در مجموعه قطعه‌ها جدید به اندازه یک نماد به سمت راست انتقال دهند. | ## جمع‌بندی | از مرحله یک برای همه مجموعه‌های جدید ایجاد شده، الگوریتم را تکرار کنید تا زمانی که مجموعه جدید ایجاد نشود.