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

در علوم کامپیوتر یک تجزیه‌کننده استاندارد LR یا تجزیه‌کننده (۱)LR، یک تجزیه‌کننده (LR(k به ازای k=۱، یعنی با یک پایانه پیشرو است. ویژگی خاص این تجزیه‌کننده این است که هر گرامر (LR(k با k>1 را می‌توان به گرامر (۱)LR تبدیل کرد. این تجزیه‌کننده می‌تواند تمام زبان‌های مستقل از متن قطعی را مدیریت کنند. در گذشته، تجزیه‌کننده (LR(k به دلیل نیاز به حافظهٔ زیاد و وجود جایگزین‌هایی با قدرت کمتر مانند تجزیه‌کننده LALR و (۱)LL، کمتر مورد استفاده قرار می‌گرفت. با این حال اخیراً یک تجزیه‌کننده (۱)LR کمینه ارائه شده‌است که نیاز به حافظه آن نزدیک به تجزیه‌کننده LALR است که توسط چند تولیدکنندگان تجزیه‌کننده ارائه می‌شود.

تاریخچه

در سال ۱۹۶۵، دانلد کنوت، تجزیه‌کننده (LR(k را که یک نوع تجزیه‌کننده انتقال-کاهش بود را اختراع کرد. این تجزیه‌کننده دارای پتانسیل شناخت تمام زبان‌های مستقل از متن قطعی بوده و می‌تواند هر دو اشتقاق چپ و راست ورودی را تولید کند. کنوت اثبات کرد که قدرت پذیرش زبان برای K=۱ در حالت بیشینه است و یک روش برای تبدیل گرامر (LR(k با K>1، به گرامر (۱)LR ایجاد کرد.

بزرگترین مشکل تجزیه‌کننده استاندارد (۱)LR نیاز به حافظهٔ زیاد برای ایجاد جدول-پارس داخلی خود است. در سال ۱۹۹۱ فرانک دو نسخه ساده شده از تجزیه‌کننده LR را به نام LALR و SLR را پیشنهاد کرد. این تجزیه‌کننده‌ها نیاز به حافظه کمتری نسبت به تجزیه‌کننده استاندارد (۱)LR دارند، اما قدرت تشخیص-زبان کمتری دارد. تجزیه‌کننده (۱)LALR رایج‌ترین پیاده‌سازی برای تجزیه‌کننده LR بوده‌اند.

با این حال یک نوع جدید تجزیه‌کننده (LR(۱ با نام تجزیه کننده (۱)LR کمینه در سال ۱۹۷۷ توسط دیوید پابر معرفی شد که نشان داد که می‌توان یک تجزیه کننده (۱)LR ایجاد کرد که حافظهٔ مورد نیاز آن نزدیک تجزیه‌کننده (۱)LALR می‌باشد. اخیراً بعضی از تولیدکنندگان تجزیه کننده‌ها، تجزیه‌کننده (۱)LR کمینه را ارائه می‌دهند که مشکل حافظه را حل کرده‌اند.

ساخت جداول تجزیه ال‌آر

جداول تجزیه (LR(۱ همانند جداول تجزیه (LR(0 با تفاوت که در آن هر قطعه شامل یک پایانه پیشرو است. این بدان معنی است که برخلاف تجزیه‌کننده (LR(0، یک عملیات متفاوت ممکن است اجرا شود، اگر قطعه مورد پردازش با یک پایانه متفاوت دنبال شود.

قطعه‌های تجزیه‌کننده

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

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

به عنوان مثال فرض کنید که زبان شامل نمادهای پایانه 'n'، '+'، '('، ')'، و غیرپایانه‌های 'E', 'T'، و قانون شروع 'S' که قوانین تولید زیر را شامل می‌شود:

S → E

E → T

(E → (E

T → n

T → + T

T → T + n

مجموعه قطعه‌های ۰ که نشان دهنده وضعیت اولیه است، از قانون شروع تولید می‌شود.

[$ ،S → • E]

علامت '•' نشانگر موقعیت فعلی تجزیه‌کننده در این قانون است. پایانه پیشرو در این قاعده بعد از کاما ذکر شده‌است. علامت '$' برای نشان پایان ورودی مورد انتظار است.

مجموعه بالا، مجموعه قطعه کامل شماره ۰ نیست. هر مجموعه قطعه‌ها باید بسته باشد، یعنی تمام قوانین تولید برای هر غیرپایانه که بعد از '•' بیاید باید به صورت بازگشتی در مجموعه قطعه‌ها قرار داده شود تا همه غیرپایانه مورد بررسی قرار گیرد. نتیجه این عملیات را بستار آن قطعه می‌گوییم.

در (LR(۱ برای هر قانون تولید، یک قطعه باید برای هر پایانه پیشرو ایجاد شود. برای زبان‌های پیچیده‌تر این معمولاً به مجموعه‌های بسیار زیادی از قطعه‌ها منجر می‌شود که همین دلیل استفاده از حافظهٔ بزرگ برای تجزیه‌کننده (LR(۱ است.

در مثال بالا علامت شروع ما نیاز به پایانه 'E' دارد که 'E' خود نیاز به 'T' دارد و در نتیجه تمام قوانین تولید در مجموعه قطعه شماره ۰ ظاهر می‌شوند. در ابتدا، ما مسئله پیدا کردن پیشرو را نادیده گرفتیم و فقط به (LR(0 پرداختیم که قطعات آن شامل پایانه پیشرو نبودند؛ بنابراین مجموعه قطعه شماره ۰ دارای قطعه‌های زیر خواهد بود:

[S → • E]

[E → • T]

[( E → • ( E]

[T → • n]

[T → • + T]

[T → • T + n]

مجموعه‌های FIRST و FOLLOW

برای تعیین پایانه‌های پیشرو، از مجموعه‌های به اصطلاح FIRST و FOLLOW استفاده می‌شود. مجموعه (FIRST(A شامل پایانه‌هایی است که می‌توانند به عنوان اولین قسمت از هر زنجیره از قوانین تولید که از غیرپایانه A شروع شود. (FOLLOW(A شامل پایانه‌هایی است که می‌تواند دقیقاً بعد از A ظاهر شوند.

در مثال ما، (FIRST(S و (FIRST(E برابر { ')' ,'+' ,n } و (FIRST(T برابر {'+' ,n } می‌شود، همچنین (FOLLOW(S برابر { '$' } و (FOLLOW(E برابر { '(' ,'$' } همچنین (FOLLOW(T برابر { '(' ,'$' ,'+' } می‌شود.

تعیین پایانه‌های پیشرو

با داشتن مجموعه‌های FOLLOW می‌توان مجموعه کامل قطعه‌ها را برای یک تجزیه‌کننده (LR(۱ ایجاد کرد، به این صورت که به ازای هر قطعه در مجموعه بستار آن (مانند (LR(0) و هر پایانه در مجموعه FOLLOW غیرپایانه سمت چپ یک قطعه جدید ایجاد کنیم.

[$ ،S → • E]

[$ ،E → • T]

[( ,E → • T]

[$ ،( E → • ( E]

[( ,( E → • ( E]

[$ ،T → • n]

[+ ,T → • n]

[( ,T → • n]

[$ ،T → • + T]

[+ ,T → • + T]

[( ,T → • + T]

[$ ،T → • T + n]

[+ ،T → • T + n]

[( ،T → • T + n]

ایجاد مجموعه قطعه‌های جدید

بقیه مجموعه قطعه‌ها را می‌توان با الگوریتم زیر ایجاد نمود.

1. برای هر پایانه و هر غیرپایانه A که پس از علامت '•' در مجموعهٔ قطعه‌هایی که تا الان داریم مانند k بیاید، مجموعه‌ای جدید مانند m ایجاد کنید و همه قوانین در k که در آن '•' قبل از A است را به m اضافه کنید. اما فقط در صورتی که m بعد از مرحله ۳ مانند هیچ‌کدام از مجموعه‌هایی که تا الان داریم نشود.
2. همه '•'ها را برای هر قانون در مجموعه قطعه‌ها جدید به اندازه یک نماد به سمت راست انتقال دهند.
3. بستار قطعه‌های جدید ایجاد کنید.
4. از مرحله یک برای همه مجموعه‌های جدید ایجاد شده، الگوریتم را تکرار کنید تا زمانی که مجموعه جدید ایجاد نشود.

در مثال ما پنج مجموعه جدید از مجموعه قطعه شماره ۰ ایجاد می‌شود.

مجموعه قطعه شماره ۱ برای غیرپایانه E

[$ ،• S → E]

مجموعه قطعه شماره ۲ برای غیرپایانه T

[$ ،• E → T]

[$ ،T → T • + n]

[+ ,T → T • + n]

مجموعه قطعه شماره ۳ برای پایانه 'n'

[$ ،• T → n]

[+ ،• T → n]

[( ،• T → n]

مجموعه قطعه شماره ۴ برای پایانه '+'

[$ ،T → + • T]

[+ ,T → + • T]

[$ ،T → • n]

[+ ,T → • n]

[$ ،T → • + T]

[+ ,T → • + T]

[$ ،T → • T + n]

[+ ،T → • T + n]

مجموعه قطعه شماره ۵ برای پایانه ')'

[$ ،( E → ( • E]

[( ,E → • T]

[( ,( E → • ( E]

[( ,T → • n]

[+ ,T → • n]

[( ,T → • + T]

[+ ,T → • + T]

[( ,T → • T + n]

[+ ،T → • T + n]

از مجموعه قطعه‌های ۲ و ۴ و ۵ چندین مجموعه قطعه دیگر تولید خواهد شد. لیست کامل آن بسیار طولانی می‌باشد و بنابراین در اینجا بیان نمی‌شود.

عملیات انتقال

اگر [A → α • b β, a] در حالت شماره k بوده و حالت شماره k با b به حالت شماره m برود، عملیات [action[k, b = 'انتقالm' را اضافه می‌کنیم.

عملیات کاهش

اگر [A → α •, a] در حالت شماره k باشد، عملیات [action[k, a = 'کاهش A → α' را اضافه می‌کنیم.

منابع

• ویکی‌پدیا انگلیسی Canonical LR parser