وبلاگ یک رتبه

تجزیه‌گر SLR

تجزیه‌گر SLR مشابه تجزیه‌گر LR(0) است با این تفاوت در اعمال کاهشی. اعمال کاهشی تنها در Follow های متغیری که باید کاهش یابد نوشتهمی‌شود.

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

۱- مجموعه‌ی C={I0,I1,... , In} را -که مجموعه‌ی آیتم‌‌های ‌LR(۱) گرامر G’ است- بساز.

۲- حالت i از li ساخته می‌شود. اعمال تجزیه برای حالت i  بدین صورت معین می‌شود:

         * اگر [A -> ?.a?] در li است و GOTO(li,a)=lj در این صورت ACTION[i,a] را shift j قرار دهید. در این جا a باید یک ترمینال باشد.

         * اگر [A -> ?.] در li است در این صورت ACTION[i,a] را reduce A->? برای همه‌ی a های داخل FOLLOW(A)  قرار بده. در این‌جا A نباید S’ باشد.

         * اگر [S -> S.] در li است در این صورت ACTION[i,$] را accept قرار بده. اگر هرگونه برخوردی در action های اعمالی مراحل بالا وجود داشت می‌گوییم این گرامر SLR نیست.

۳- گزارهای goto برای حالت i برای همه‌ی nonterminal های A بدین صورت محاسبه می‌شود:

اگر GOTO(li,A)=lj  در این صورت GOTO[i,A]=j.

۴- همه‌ی خانه‌هایی که در مراحل ۲ و ۳ مقداردهی نشدند باعث وقوع خطا شوند.

نکته: اگر در خانه‌ای از جدول چند عمل داشته باشیم یک برخورد رخ داده است.

مثلا:

گرامر تکمیلی زیر را در نظر بگیرید:

تجزیه‌گر CLR

ما در روش SLR روی آیتم‌های LR(0) کار می‌کنیم. در تجزیه‌گر CLR از آیتم‌های LR(1) استفاده می‌کنیم. آیتم‌های LR(k) آیتمی‌ست که با lookahead بطول k مشخص می‌شود. پس در واقع LR(1) آیتم‌های LR(0) را همراه lookahead مربوط به آن دارد.

تجزیه‌گر‌های LR(1) قوی‌تر هستند.

برای LR(1) توابع Closure و GOTO را اصلاح می‌کنیم.

Closure(I)
repeat

    for (each item [ A -> ?.B?, a ] in I )

        for (each production B -> ? in G’)

          for (each terminal b in FIRST(?a))

            add [ B -> .? , b ] to set I;

until no more items are added to I;

return I;

با یک مثال متوجه می‌شویم.

Goto(I,X)

Initialise J to be the empty set;

for ( each item A -> ?.X?, a ] in I )

    Add item A -> ?X.?, a ] to set J;/* move the dot one step */

return Closure(J);    /* apply closure to the set */ 

آیتم‌های LR(1)

Void items(G’)
Initialise C to { closure ({[S’ -> .S, $]})};
Repeat
    For (each set of items I in C)
        For (each grammar symbol X)
            if( GOTO(I, X) is not empty and not in C)
                Add GOTO(I, X) to C;
Until no new set of items are added to C;

ساخت‌ گراف GOTO

·  حالت l0. عبارت پایانی‌ آیتم LR(1) مربوطه.

·  با حالت قبل و به کمک DFA همه‌ی مجموعه‌ی آیتم‌های LR(1) را پیدا‌ کنید.

·  DFA را به جدول تجزیه‌ی LR(1) تبدیل کنید.

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

ورودی گرامر G’

۱- مجموعه‌ی C={I0,I1,... , In} را -که مجموعه‌ی آیتم‌‌های ‌LR(0) گرامر G’ است- بساز.

۲- حالت i از li ساخته می‌شود. اعمال تجزیه برای حالت i  بدین صورت معین می‌شود:

         * اگر [A -> ?.a? ,b] در li است و GOTO(li,a)=lj در این صورت ACTION[i,a] را shift j قرار دهید. در این جا a باید یک ترمینال باشد.

         * اگر [A -> ?. ,a] در li است در این صورت ACTION[i,a] را reduce A->? قرار بده. در این‌جا A نباید S باشد.

         * اگر [S -> S. ,$] در li است در این صورت ACTION[i,$] را accept قرار بده. اگر هرگونه برخوردی در action های اعمالی مراحل بالا وجود داشت می‌گوییم این گرامر CLR نیست.

۳- گزارهای goto برای حالت i برای همه‌ی nonterminal های A بدین صورت محاسبه می‌شود:

اگر GOTO(li,A)=lj  در این صورت GOTO[i,A]=j.

۴- همه‌ی خانه‌هایی که در مراحل ۲ و ۳ مقداردهی نشدند باعث وقوع خطا شوند.

مثلا گرامر تکمیلی زیر را در نظر بگیرید:

نکته: اگر حالتی دو کاهش داشت و هر دو lookahead یکسانی داشتند در نتیجه برخورد رخ می‌دهد. اگر حالتی یک کاهش و یک جابجایی یا shift با ترمینالی یکسان با lookahead داشته باشد نیز برخورد رخ می‌دهد.

تجزیه‌گر LALR

تجزیه‌گر LALR مشابه تجزیه‌گر CLR است با یک تفاوت که اگر دو حالت تنها در lookahead ها تفاوت داشته باشند با هم ادغام می‌شوند. بعد از این کوچک‌سازی اگر در جدول برخورد وجود نداشت گرامر LALR نیز هست. 

مثلا:

گرامر تکمیلی زیر را در نظر بگیرید: