![]() |
مشکل با تعیین مولفه ی دوم آیتم (LR(1 - نسخهی قابل چاپ |
مشکل با تعیین مولفه ی دوم آیتم (LR(1 - bahman2000 - 30 آذر ۱۳۹۴ ۰۱:۴۲ ب.ظ
سلام دوستان.میشه توضیح بفرمایید که مولفه دوم آیتم (LR(1 را چطوری تعیین می کنیم؟ هر چی خوندم متوجه این lookahead نشدم؟ ![]() |
RE: مشکل با تعیین مولفه ی دوم آیتم (LR(1 - Iranian Wizard - 23 خرداد ۱۳۹۵ ۰۸:۱۴ ب.ظ
(۳۰ آذر ۱۳۹۴ ۰۱:۴۲ ب.ظ)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]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] |