تالار گفتمان مانشت
مشکل با تعیین مولفه ی دوم آیتم (LR(1 - نسخه‌ی قابل چاپ

مشکل با تعیین مولفه ی دوم آیتم (LR(1 - bahman2000 - 30 آذر ۱۳۹۴ ۰۱:۴۲ ب.ظ

سلام دوستان.میشه توضیح بفرمایید که مولفه دوم آیتم (LR(1 را چطوری تعیین می کنیم؟ هر چی خوندم متوجه این lookahead نشدم؟
[تصویر:  393213_wlj_2015-12-21_12-46-49.jpg]
جواب گزینه یک هست.

RE: مشکل با تعیین مولفه ی دوم آیتم (LR(1 - Iranian Wizard - 23 خرداد ۱۳۹۵ ۰۸:۱۴ ب.ظ

(۳۰ آذر ۱۳۹۴ ۰۱:۴۲ ب.ظ)bahman2000 نوشته شده توسط:  سلام دوستان.میشه توضیح بفرمایید که مولفه دوم آیتم (LR(1 را چطوری تعیین می کنیم؟ هر چی خوندم متوجه این lookahead نشدم؟
[تصویر:  393213_wlj_2015-12-21_12-46-49.jpg]
جواب گزینه یک هست.

سلام.
این سوال در گرامر روبرو ، بستار آیتم [tex]S\: \longrightarrow\: .AB\: ,\: \{\: \$\: \}[/tex] رو خواسته:

[tex]S\: \longrightarrow\: \: A\: |\: AB[/tex]

[tex]A\: \longrightarrow\: \: BA\: |\: a\: |\: Aa[/tex]

[tex]B\: \longrightarrow\: bB[/tex]


۱) خود قلم اولیه،جزئی از بستار [tex]S\: \longrightarrow\: .AB\: ,\: \{\: \$\: \}[/tex] هستش.یعنی قلم زیر به بستار ،اضافه میشه:

[tex]S\: \longrightarrow\: .AB\: ,\: \{\: \$\: \}[/tex]



۲) چونکه نقطه قبل از یک متغیر (یعنی A) اومده،پس بایستی A رو گسترش دهیم و مجموعه پیش‌گویی(lookahead) آن برابر [tex]first(B\$)[/tex] یعنی [tex]\{b\}[/tex] خواهد شد.پس قلم‌های زیر به بستار اضافه میشه:

[tex]A\: \longrightarrow\: .BA\: ,\: \{b\}[/tex]

[tex]A\: \longrightarrow\: .a\: ,\: \{b\}[/tex]

[tex]A\: \longrightarrow\: .Aa\: ,\: \{b\}[/tex]


۳) حال در قلم اضافه شده‌ی [tex]A\: \longrightarrow\: .BA\: ,\: \{b\}[/tex] ، چونکه نقطه قبل از متغیر B اومده،پس بایستی B رو گسترش دهیم و مجموعه پیش‌گویی(lookahead) آن برابر [tex]first(Ab)[/tex] یعنی [tex]\{a ,\: b\}[/tex] خواهد شد.پس قلم زیر هم به بستار اضافه میشه:

[tex]B\: \longrightarrow\: .bB\: , \{a\: ,\: b\}[/tex]


که الآن گزینه‌ی ۱ جواب سوال خواهد شد...ولی پاسخ درست چیز دیگه‌ایه که متاسفانه تو گزینه‌ها نیست.و طراح سوال فراموش کرده که الآن چونکه علامت نقطه قبل از قلم اضافه شده‌ی ‌[tex]A\: \longrightarrow\: .Aa\: ,\: \{b\}[/tex] وجود داره،پس باید متغیر A رو دوباره گسترش بدیم،پس:


۴) در قلم اضافه ‌شده‌ی [tex]A\: \longrightarrow\: .Aa\: ,\: \{b\}[/tex] ، چونکه نقطه قبل از متغیر A اومده،پس بایستی A رو دوباره گسترش بدیم و مجموعه پیش‌گویی(lookahead) آن برابر [tex]first(ab)[/tex] یعنی [tex]\{a\}[/tex] خواهد شد.پس قلم‌های زیر به بستار اضافه میشه:


[tex]A\: \longrightarrow\: .BA\: ,\: \{a\}[/tex]

[tex]A\: \longrightarrow\: .a\: ,\: \{a\}[/tex]

[tex]A\: \longrightarrow\: .Aa\: ,\: \{a\}[/tex]

۵) در قلم اضافه شده‌ی [tex]A\: \longrightarrow\: .BA\: ,\: \{a\}[/tex] ،چونکه نقطه قبل از متغیر B اومده،پس بایستی B رو گسترش بدیم و مجموعه پیش‌گویی(lookahead) آن برابر [tex]first(Aa)[/tex] یعنی [tex]\{a\: ,b\}[/tex] خواهد شد.پس قلم زیر هم باید به بستار اضافه بشه،ولی چون قبلا اضافه شده،پس دیگه نیازی به نوشتن آن در بستار نیست:

[tex]B\: \longrightarrow\: .bB\: , \{a\: ,\: b\}[/tex]


۶) و در نهایت در قلم اضافه‌ شده‌ی [tex]A\: \longrightarrow\: .Aa\: ,\: \{a\}[/tex] ،چونکه نقطه قبل از متغیر A اومده،بایستی A رو گسترش بدیم و مجموعه پیش‌گویی(lookahead) آن برابر [tex]first(aa)[/tex] یعنی [tex]\{a\}[/tex] خواهد شد.پس قلم‌های زیر هم بایستی به بستار اضافه بشه،ولی چون قبلا اضافه شده،پس دیگه نیازی به نوشتن آن نیست:

[tex]A\: \longrightarrow\: .BA\: ,\: \{a\}[/tex]

[tex]A\: \longrightarrow\: .a\: ,\: \{a\}[/tex]

[tex]A\: \longrightarrow\: .Aa\: ,\: \{a\}[/tex]

--------------------------------------------------------------------------------------------------


در نهایت بستار [tex]S\: \longrightarrow\: .AB\: ,\: \{\: \$\: \}[/tex] برابر قلم‌‌های زیر خواهد شد:
[tex]S\: \longrightarrow\: .AB\: ,\: \{\: \$\: \}[/tex]

[tex]A\: \longrightarrow\: .BA\: ,\: \{b\}[/tex]

[tex]A\: \longrightarrow\: .a\: ,\: \{b\}[/tex]

[tex]A\: \longrightarrow\: .Aa\: ,\: \{b\}[/tex]

[tex]B\: \longrightarrow\: .bB\: , \{a\: ,\: b\}[/tex]

[tex]A\: \longrightarrow\: .BA\: ,\: \{a\}[/tex]

[tex]A\: \longrightarrow\: .a\: ,\: \{a\}[/tex]

[tex]A\: \longrightarrow\: .Aa\: ,\: \{a\}[/tex]


که اگه خلاصش کنیم،جواب نهایی برابر میشه با:


[tex]S\: \longrightarrow\: .AB\: ,\: \{\: \$\: \}[/tex]

[tex]A\: \longrightarrow\: .BA\: ,\: \{a\: ,\: b\}[/tex]

[tex]A\: \longrightarrow\: .a\: ,\: \{a\: ,\: b\}[/tex]

[tex]A\: \longrightarrow\: .Aa\: ,\: \{a\: ,\: b\}[/tex]

[tex]B\: \longrightarrow\: .bB\: , \{a\: ,\: b\}[/tex]