تالار گفتمان مانشت

سلام دوستان.میشه توضیح بفرمایید که مولفه دوم آیتم (LR(1 را چطوری تعیین می کنیم؟ هر چی خوندم متوجه این lookahead نشدم؟ جواب گزینه یک هست.

(30 آذر 1394 01:42 ب.ظ)bahman2000 نوشته شده توسط: [ -> ]سلام دوستان.میشه توضیح بفرمایید که مولفه دوم آیتم (LR(1 را چطوری تعیین می کنیم؟ هر چی خوندم متوجه این lookahead نشدم؟

جواب گزینه یک هست.

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

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

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


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