Document

Report
‫به نام خدا‬
‫‪7‬‬
‫طراحی‬
‫کامپایلرها‬
‫‪40-414‬‬
‫تحلیلگرهای نحوی ‪)1( LR‬‬
‫‪ o‬قوی‌ترین روش تحلیل نحوی انتقال‪-‬کاهش (که کارا هم باشد)‪:‬‬
‫)‪LR (k‬‬
‫‪ k‬نشانه‌ی بعدی ورودی‬
‫(اگر ‪ k = 1‬باشد‪ k ،‬را نمی‌نوینسد)‬
‫اشتقاق راست‌گرد‬
‫پویش چپ به راست‬
‫‪ o‬تحلیل نحوی ‪ LR‬جالب توجه است‪ ،‬زیرا‪:‬‬
‫‪‬‬
‫‪‬‬
‫تحلیل نحوی ‪ LR‬کلی‌ترین روش تحلیل نحوی انتقال‪-‬کاهش‪ ،‬بدون عقب‌گرد است (که‬
‫ً‬
‫ضمنا کارا هم هست)‬
‫مجموعه‌ی زبان‌هایی (گرامرهایی) که به کمک روش ‪ LR‬قابل تحلیل نحوی‌اند‪،‬‬
‫زیرمجموعه‌ی سره‌ی زبان‌هایی (گرامرهایی) است که به کمک تحلیلگرهای نحوی پیش‌گو‬
‫ً‬
‫(مثال )‪ )LL(1‬قابل تحلیل‌اند‬
‫گرامرهای )‪  LR(1‬گرامرهای )‪LL(1‬‬
‫‪‬‬
‫‪1‬‬
‫تحلیلگر نحوی ‪ LR‬خطاها را در زودترین زمان ممکنی که با توجه به پویش چپ به راست‬
‫میسر است‪ ،‬کشف می‌کند‬
‫تحلیلگرهای نحوی ‪)2( LR‬‬
‫‪ o‬تحلیلگرهای نحوی ‪:LR‬‬
‫‪‬‬
‫گروه بزرگی از گرامرها را پوشش می‌دهند‬
‫‪‬‬
‫‪ :)Simple LR( SLR‬تحلیلگر نحوی ‪ LR‬ساده‬
‫‪‬‬
‫‪ :LR‬کلی‌ترین تحلیلگر نحوی ‪LR‬‬
‫‪‬‬
‫‪ :)Look-Ahead LR( LALR‬تحلیلگر نحوی ‪ LR‬میانی (متوسط)‬
‫‪‬‬
‫‪ ،LR ،SLR‬و ‪ LALR‬مثل هم کار می‌کنند (الگوریتم تحلیل نحوی آن‌ها یکسان است) و‬
‫تفاوت‌شان تنها در جدول تحلیل است‬
‫‪2‬‬
‫الگوریتم تحلیل نحوی ‪)1( LR‬‬
‫انباره‬
‫ورودی‬
‫‪a1 … ai … an $‬‬
‫‪Sm‬‬
‫‪Xm‬‬
‫الگوریتم تحلیل‬
‫نحوی ‪LR‬‬
‫خروجی‬
‫‪Sm-1‬‬
‫‪Xm-1‬‬
‫جدول ‪Goto‬‬
‫)‪(Goto Table‬‬
‫جدول اعمال‬
‫)‪(Action Table‬‬
‫غیرپایانه‌ها‬
‫پایانه‌ها و ‪$‬‬
‫در خانه‌ها شماره‌ی‬
‫‌‬
‫حالت‌ها نوشته‬
‫می‌شود‬
‫‪ 4‬عمل مختلف‬
‫‪.‬‬
‫‪.‬‬
‫حالت‌ها‬
‫حالت‌ها‬
‫‪3‬‬
‫‪S1‬‬
‫‪X1‬‬
‫‪S0‬‬
‫الگوریتم تحلیل نحوی ‪)2( LR‬‬
‫‪ o‬یک پیکربندی تحلیل نحوی ‪:LR‬‬
‫)‬
‫‪ai ai+1 … an $‬‬
‫‪Sm‬‬
‫‪Xm‬‬
‫‪...‬‬
‫باقی‌مانده‌ی ورودی‬
‫‪S1‬‬
‫‪X1‬‬
‫‪S0‬‬
‫(‬
‫انباره‬
‫‪ Sm o‬و ‪ ،ai‬قدم بعدی تحلیلگر را با رجوع به جدول تحلیل مشخص‬
‫می‌کنند (انباره در ابتدا فقط حاوی ‪ S0‬است)‬
‫‪ o‬یک پیکربندی تحلیل نحوی ‪ LR‬فرم جمله‌ای راست‌گرد را نشان می‌دهد‪:‬‬
‫‪X1 … Xm ai ai+1 … an $‬‬
‫‪4‬‬
‫عمل‌های تحلیلگر نحوی ‪)1( LR‬‬
‫‪ )1( o‬انتقال ‪ :s‬ورودی بعدی را به همراه حالت ‪ ،s‬روی انباره قرار می‌دهد‬
‫) ‪( S0 X1 S1 … Xm Sm, ai ai+1 … an $ ) → (S0 X1 S1 … Xm Sm ai s, ai+1 … an $‬‬
‫‪ )2( o‬کاهش ‪( A → β‬یا کاهش ‪ ،n‬که ‪ n‬شماره‌ی قاعده است)‪:‬‬
‫‪‬‬
‫برداشتن (‪ 2×|β| )=r‬عنصر از روی انباره‬
‫‪‬‬
‫قرار دادن ‪ A‬و ‪ s‬روی انباره‪ ،‬به طوری که ]‪s = goto[sm-r, A‬‬
‫) ‪( S0 X1 S1 … Xm Sm, ai ai+1 … an $ ) → (S0 X1 S1 … Xm-r Sm-r A s, ai … an $‬‬
‫‪‬‬
‫خروجی‪ ،‬قاعده‌ی ‪A → β‬‬
‫‪ )3( o‬پذیرش‪ :‬تحلیل نحوی با موفقیت به اتمام می‌رسد‬
‫در‬
‫‪ )4( o‬خطا‪ :‬تحلیلگر نحوی یک خطا را تشخیص می‌دهد (خانه‌ای خالی ‌‬
‫جدول تحلیل)‬
‫‪5‬‬
‫عمل‌های تحلیلگر نحوی ‪)2( LR‬‬
‫‪ o‬عمل کاهش‬
‫‪‬‬
‫برداشتن (‪ 2×|β| )=r‬عنصر از روی انباره؛ فرض کنید ‪β = Y1 Y2 … Yr‬‬
‫‪‬‬
‫قرار دادن ‪ A‬و ‪ s‬روی انباره‪ ،‬به طوری که ]‪s = goto[Sm-r, A‬‬
‫→ ) ‪( S0 X1 S1 … Xm-r Sm-r Y1 Sm-r … Yr Sm, ai ai+1 … an $‬‬
‫) ‪(S0 X1 S1 … Xm-r Sm-r A s, ai … an $‬‬
‫‪‬‬
‫در حقیقت‪ Y1 Y2 … Yr ،‬یک دستگیره است‬
‫‪X1 … Xm Y1 … Yr ai ai+1 … an $‬‬
‫‪6‬‬
‫‪X1 … Xm-r A ai … an $‬‬
SLR ‫جدول تحلیل‬
‫جدول‌ اعمال‬
‫حالت‬
id
0
s5
+
*
(
)
$
s4
1
s6
2
r2
s7
r2
r2
3
r4
r4
r4
r4
4
s4
r6
E
T
F
1
2
3
8
2
3
acc
s5
5
:‫ مثال‬o
Goto ‫جدول‬
r6
r6
6
s5
s4
7
s5
s4
1
E → E+T
3
2
E → T
10
3
T → T*F
4
T → F
r6
9
8
s6
s11
9
r1
s7
r1
r1
10
r3
r3
r3
r3
5
F → (E)
11
r5
r5
r5
r5
6
F → id
7
‫عمل‌های یک تحلیلگر نحوی ‪(S)LR‬‬
‫‪ o‬مثال‪:‬‬
‫خروجی‬
‫ورودی‬
‫عمل‬
‫انتقال ‪5‬‬
‫‪8‬‬
‫‪id * id + id $‬‬
‫انباره‬
‫‪0‬‬
‫‪F → id‬‬
‫کاهش با ‪F → id‬‬
‫‪* id + id $‬‬
‫‪0 id 5‬‬
‫‪T→F‬‬
‫کاهش با ‪T → F‬‬
‫‪* id + id $‬‬
‫‪0F3‬‬
‫انتقال ‪7‬‬
‫‪* id + id $‬‬
‫‪0T2‬‬
‫انتقال ‪5‬‬
‫‪id + id $‬‬
‫‪0T2*7‬‬
‫‪F → id‬‬
‫کاهش با ‪F → id‬‬
‫‪+ id $‬‬
‫‪0 T 2 * 7 id 5‬‬
‫‪T→T*F‬‬
‫کاهش با ‪T → T * F‬‬
‫‪+ id $‬‬
‫‪0 T 2 * 7 F 10‬‬
‫‪E→T‬‬
‫کاهش با ‪E → T‬‬
‫‪+ id $‬‬
‫‪0T2‬‬
‫انتقال ‪6‬‬
‫‪+ id $‬‬
‫‪0E1‬‬
‫انتقال ‪5‬‬
‫‪id $‬‬
‫‪0E1+6‬‬
‫‪F → id‬‬
‫کاهش با ‪F → id‬‬
‫‪$‬‬
‫‪0 E 1 + 6 id 5‬‬
‫‪T→F‬‬
‫کاهش با ‪T → F‬‬
‫‪$‬‬
‫‪0E1+6F3‬‬
‫‪E→E+T‬‬
‫کاهش با ‪E → E + T‬‬
‫‪$‬‬
‫‪0E1+6T9‬‬
‫پذیرش‬
‫‪$‬‬
‫‪0E1‬‬
‫ساخت جدول تحلیل (‪)1‬‬
‫‪ o‬آیتم )‪LR(0‬‬
‫‪‬‬
‫یک آیتم )‪ LR(0‬از گرامر ‪ ،G‬قاعده‌ای از ‪ G‬است که در جایی از سمت راست آن‪،‬‬
‫«نقطه»ای گذاشته‌ایم‬
‫•‬
‫ً‬
‫مثال اگر داشته باشیم‪،A → a B b :‬‬
‫●‬
‫→ ‪A‬‬
‫‪aBb‬‬
‫‪a●Bb‬‬
‫→ ‪A‬‬
‫آیتم‌های )‪ LR(0‬ممکن‪ ،‬این‌ها هستند‪:‬‬
‫‪aB●b‬‬
‫→ ‪A‬‬
‫●‪aBb‬‬
‫→ ‪A‬‬
‫‪‬‬
‫مجموعه‌ی آیتم‌های )‪ LR(0‬حالت‌های جدول‌ اعمال و ‪ Goto‬را تشکیل می‌دهند‬
‫‪‬‬
‫مجموعه‌ای از مجموعه‌های آیتم‌های )‪( LR(0‬موسوم به «مجموعه‌ی کانونی )‪)»LR(0‬‬
‫مبنایی برای ساخت تحلیلگرهای نحوی ‪ SLR‬است‬
‫‪ o‬گرامر افزوده‬
‫‪‬‬
‫‪9‬‬
‫گرامر افزوده‌ی ’‪ ،G‬همان گرامر ‪ G‬است که به آن قاعده‌ی ‪ S’ → S‬افزوده‌ایم که در آن‬
‫’‪ S‬نماد جدید شروع است‬
‫ساخت جدول تحلیل (‪)2‬‬
‫‪ o‬عمل بستار (‪)Closure‬‬
‫‪‬‬
‫اگر ‪ I‬مجموعه‌ای از آیتم‌های )‪ LR(0‬برای گرامر ‪ G‬باشد‪ ،‬بستار ‪ ،I‬مجموعه‌ای از‬
‫آیتم‌های )‪ LR(0‬است که از ‪ I‬با توجه به این دو قانون ساخته شده است‪:‬‬
‫•‬
‫(‪ )1‬در ابتدا‪ ،‬هر آیتم )‪ LR(0‬در ‪ I‬به بستار ‪ I‬اضافه می‌شود‬
‫•‬
‫(‪ )2‬اگر ‪ A → α ● B β‬در بستار ‪ I‬باشد و ‪ B → γ‬نیز یکی از قاعده‌های گرامر ‪ ،G‬در آن‬
‫صورت‪ B → ● γ ،‬نیز در بستار ‪ I‬خواهد بود (این قانون را تا جایی اعمال می‌کنیم که دیگر‬
‫آیتم )‪ LR(0‬جدیدی به بستار ‪ I‬اضافه نشود)‬
‫‪10‬‬
)3( ‫ساخت جدول تحلیل‬
:‫ مثال‬o
E’
→
E
E
→
E+T
E
→
T
T
→
T*F
T
→
F
F
→
(E)
E’
→
●
F
→
id
E
→
●E
E
→
●T
T
→
●T
T
→
●F
F
→
●(
F
→
● id
‫آیتم‌های هسته‬
)kernel(
{
E
+T
}=
{E’ → ● E} ‫بستار‬
*F
E)
11
‫ساخت جدول تحلیل (‪)4‬‬
‫‪ o‬تابع ‪Goto‬‬
‫‪‬‬
‫)‪ Goto(I, X‬بستار مجموعه‌ی همه‌ی آیتم‌های به شکل ‪ A → α X ● β‬است که ‪A‬‬
‫‪‬‬
‫‪ → α ● X β‬عضو ‪ I‬باشد‬
‫ً‬
‫تعریف باال را شهودا می‌توان به این صورت بیان کرد که )‪ ،Goto(I, X‬مجموعه‌ی‬
‫‪‬‬
‫همه‌ی آیتم‌هایی است که (در صورت دیده شدن ‪ )X‬از ‪« I‬قابل دسترس ی‌اند»‬
‫ً‬
‫باشد‪ ،‬در این‬
‫مثال فرض کنید‬
‫صورت‪:‬‬
‫} ‪{ E’ → E ●, E → E ● + T‬‬
‫=‬
‫‪{ E → E + ● T, T → ● T * F, T → ● F, F → ● ( E ),‬‬
‫} ‪F → ● id‬‬
‫‪12‬‬
‫‪I‬‬
‫=‬
‫)‪Goto(I, +‬‬
‫ساخت جدول تحلیل (‪)5‬‬
‫‪ o‬برای ساخت جدول تحلیل ‪ SLR‬گرامر ‪ ،G‬باید مجموعه‌ی کانونی‬
‫)‪ LR(0‬گرامر ’‪ G‬را تشکیل دهیم‬
‫‪ o‬الگوریتم‪:‬‬
‫‪ C‬بستار } ‪ { S’ → ● S‬است‬
‫گام‌های زیر را تا جایی که دیگر مجموعه‌ی جدیدی از آیتم‌های )‪ LR(0‬به ‪ C‬اضافه نشود‪،‬‬
‫تکرار کن‬
‫به ازای هر ‪ I‬در ‪ ،C‬و هر نماد گرامر ‪X‬‬
‫اگر مجموعه‌ی )‪ Goto(I, X‬تهی نباشد‪ ،‬و در ‪ C‬نیز نباشد‪،‬‬
‫اعضای )‪ Goto(I, X‬را به ‪ C‬اضافه کن‬
‫‪ o‬تابع ‪ Goto‬یک ‪ DFA‬روی مجموعه‌های موجود در ‪ C‬است‬
‫‪13‬‬
)6( ‫ساخت جدول تحلیل‬
I1
E’ → E ●
E → E●+T
:‫ مثال‬o
I6
I2
I0
E’
E
E
T
T
F
F
→
→
→
→
→
→
→
E
●E + T
●T
●T * F
●F
●( E )
● id
E → T●
T → T●*F
●
I3
I4
I5
T → F●
F
E
E
T
T
F
F
→ (●E)
→ ●E + T
→ ●T
→ ●T * F
→ ●F
→ ●( E )
→ ● id
F → id ●
I7
I8
E
E
T
T
F
F
→ E+●T
→ ●T
→ ●T * F
→ ●F
→ ●( E )
→ ● id
T → T*●F
F → ●( E )
F → ● id
I9
E → E+T●
T → T●*F
I10
T → T*F●
I11
F → (E)●
F → (E●)
E → E●+T
14
)7( ‫ساخت جدول تحلیل‬
I1
+
:‫ مثال قبلی‬DFA o
E
I6
T
I2
I0
T
I9
F
(
*
F
I7
id
(
F
(
I8
I5
I2
(
id
I10
I4
id
I5
I3
)
I4
I5
I3
F
E
T
id
I7
I4
I3
I4
*
I5
I11
+
I6
15
‫ساخت جدول تحلیل (‪)8‬‬
‫‪ o‬ساختن جدول تحلیل ‪( SLR‬برای گرامر افزوده‌ی ’‪:)G‬‬
‫‪‬‬
‫(‪ )1‬ساختن مجموعه‌ی کانونی از مجموعه‌های آیتم‌های )‪ LR(0‬گرامر ’‪G‬‬
‫}‪C ← {I0, …, In‬‬
‫‪‬‬
‫(‪ )2‬ساختن جدول اعمال به این ترتیب‪:‬‬
‫•‬
‫اگر ‪ a‬یک پایانه‪ A → α ● a β ،‬عضو ‪ ،Ii‬و ‪ Goto(Ii, a) = Ij‬باشد‪ ،‬آن‌گاه ‪action[i,‬‬
‫]‪ a‬را ‪ shift j‬قرار می‌دهیم‬
‫•‬
‫اگر ● ‪ A → α‬عضو ‪ Ii‬باشد‪ ،‬آن‌گاه به ازای همه‌ی )‪،a  Follow(A‬‬
‫]‪ action[i, a‬را ‪ reduce A → α‬قرار می‌دهیم (در صورتی که ’‪)A ≠ S‬‬
‫‪‬‬
‫•‬
‫اگر ● ‪ S’ → S‬عضو ‪ Ii‬باشد‪ ،‬آن‌گاه ]‪ action[i, $‬را ‪ accept‬قرار می‌دهیم‬
‫•‬
‫اگر با استفاده از قانون‌های باال تداخلی به وجود آید‪ ،‬گرامر )‪ SLR(1‬نیست‬
‫(‪ )3‬ساختن جدول ‪ Goto‬به این ترتیب‪:‬‬
‫•‬
‫ً‬
‫به ازای همه‌ی غیرپایانه‌ها (مثال ‪ ،)A‬اگر ‪ Goto(Ii, A) = Ij‬باشد‪ Goto[i, A] ،‬را ‪ j‬قرار‬
‫می‌دهیم‬
‫‪16‬‬
‫‪‬‬
‫(‪ )4‬همه‌ی خانه‌هایی که بعد از این مراحل خالی مانده‌اند‪ ،‬معرف خطا هستند‬
‫‪‬‬
‫(‪ )5‬حالت اولیه‌ی تحلیلگر‪ ،‬شامل ‪ S’ → ● S‬است‬
)9( ‫ساخت جدول تحلیل‬
‫جدول‌ اعمال‬
‫حالت‬
id
0
s5
+
*
(
)
$
s4
1
s6
2
r2
s7
r2
r2
3
r4
r4
r4
r4
4
s4
r6
E
T
F
1
2
3
8
2
3
acc
s5
5
:‫ مثال‬o
Goto ‫جدول‬
r6
r6
6
s5
s4
7
s5
s4
1
E → E+T
3
2
E → T
10
3
T → T*F
4
T → F
r6
9
8
s6
s11
9
r1
s7
r1
r1
10
r3
r3
r3
r3
5
F → (E)
11
r5
r5
r5
r5
6
F → id
17
‫گرامر )‪SLR(1‬‬
‫‪ o‬تحلیلگر نحوی ‪ LR‬ای که از جدول تحلیل )‪ SLR(1‬برای گرامر ‪G‬‬
‫استفاده کند‪ ،‬تحلیلگر نحوی )‪ SLR(1‬گرامر ‪ G‬نامیده می‌شود‬
‫‪ o‬اگر گرامری‪ ،‬جدول تحلیل )‪ SLR(1‬داشته باشد‪ ،‬گرامر )‪( SLR(1‬یا‬
‫ً‬
‫مختصرا گرامر ‪ )SLR‬نامیده می‌شود‬
‫ً‬
‫‪ o‬گرامرهای ‪ SLR‬مبهم نیستند‪ ،‬اما هر گرامر نامبهم‪ ،‬الزاما ‪ SLR‬نیست‬
‫‪18‬‬
‫تداخل‌ها (‪)1‬‬
‫‪ o‬اگر در حالتی باشیم که ندانیم برای یک پایانه‪ ،‬باید عمل انتقال را انجام‬
‫دهیم‪ ،‬یا عمل کاهش را‪ ،‬می‌گوییم «تداخل انتقال‪-‬کاهش» رخ داده است‬
‫‪ o‬اگر در حالتی باشیم که ندانیم برای یک پایانه‪ ،‬کدام‌یک از چند قاعده‌ی‬
‫ممکن را باید برای کاهش به کار ببریم‪ ،‬می‌گوییم «تداخل کاهش‪-‬کاهش»‬
‫رخ داده است‬
‫‪ o‬اگر جدول تحلیل ‪ SLR‬یک گرامر دارای تداخل باشد‪ ،‬آن گرامر ‪SLR‬‬
‫نیست‬
‫‪19‬‬
)2( ‫تداخل‌ها‬
I0
S’
S
S
L
L
R
→
→
→
→
→
→
S
●L = R
●R
●* R
● id
●L
I1
S’ → S ●
I2
S → L●=R
R → L●
●
Follow(R)
=
{ =, $ }
=
I3
S → R●
I4
L
R
L
L
S → L=R
S → R
L → *R
→ *●R
→ ●L
→ ●* R
→ ● id
L → id
R → L
:‫ مثال‬o
I5
L → id ●
I6
S
R
L
L
→ L=●R
→ ●L
→ ●* R
→ ● id
I7
L → *R●
I8
R → L●
I9
S → L=R●
reduce
R→L
shift 6
20
)3( ‫تداخل‌ها‬
:‫ مثال‬o
S → AaAb
S → BbBa
A→ ε
I0
B → ε
a
reduce
A→ε
reduce
B→ε
S’
S
S
A
B
→
→
→
→
→
S
●A a A b
●B b B a
●
●
Follow(A)
=
{ a, b }
Follow(B)
=
{ a, b }
●
b
reduce
A→ε
reduce
B→ε
21

similar documents