تشخیص LL(1) - نسخهی قابل چاپ |
تشخیص LL(1) - m@hboobe - 24 مهر ۱۳۹۲ ۰۸:۴۵ ب.ظ
گرامر G مفروض است کدام گزینه صحیح میباشد؟ ۱- LL(1) است ۲- LL(1) نیست و با حذف قاعده [tex]B\rightarrow aA[/tex] گرامر LL(1) میشود. ۳- LL(1) نیست و با حذف قاعده [tex]C\rightarrow \lambda[/tex] گرامر LL(1) میشود. ۴- گزینه ۲و ۳ گرامر G: [tex]A \rightarrow aBC | BEe[/tex] [tex]B \rightarrow Cc|aA[/tex] [tex]C\rightarrow cA|b| \lambda[/tex] [tex]E\rightarrow f| \lambda[/tex] میدونم که برای تشخیص این گرامر باید دو قاعده رو چک کنیم اول اینکه first سمت چپ هر قاعده باهم اشتراک نداشته باشند و دومی اگر در مجموعه first غیر ترمینالها لامبدا تولید بشه باید Follow اون رو بدست بیاریم. در خط اول که برخورد First/First داریم در خط سوم بایستی [tex]first(cA)\bigcap First(b) \bigcap Follow( C)[/tex] بدست بیاریم [tex]first(cA)\bigcap First(b) \bigcap Follow( C)= \left \{ c \right \}\bigcap \left \{ b \right \}\bigcap \left \{ b,c,f,e,\$ \right \}[/tex] اینجا چطوری بخش Follow رو بدست آورده؟ من فکر میکنم فقط c و $ باید باشه! |
RE: تشخیص LL(1) - azad_ahmadi - 24 مهر ۱۳۹۲ ۰۹:۵۷ ب.ظ
سلام. برای مشخص کردن LL1 بودن، اول باید ببینیم در هر قانون برخورد First/First وجود داره یا نه. در این گرامر برخورد First/First وجود داره در قانون A. چرا که [tex]A\rightarrow aBC[/tex] و [tex]A\rightarrow BEe \Rightarrow aAEe[/tex] هردو a رو تولید خواهند کرد و این برخورد پیش خواهد امد. از طرف دیگه وقتی لامبدا عضو یه قانونی هست، مانند : [tex]C\rightarrow cA|b|\varepsilon[/tex] باید Firstهای این قانون که (c,b) هست برابر با Fallow(C باشند که LL1 نباشه. پس چون c جزء Fallowی C هست، پس باید قانون [tex]C\rightarrow \varepsilon[/tex] حذف بشه. برای قانون [tex]E\rightarrow f|\varepsilon[/tex] هم بررسی میکنیم که f جزء Fallowی E هست یا نه، (که البته نیست). پس دوبرخورد First/First و First/Fallow وجود داره که با حذف [tex]B\rightarrow aA[/tex] و [tex]C\rightarrow \varepsilon[/tex] تبدیل به LL1 خواهد شد. و گزینه صحیح ۴ است. |
RE: تشخیص LL(1) - b.kiani - 25 مهر ۱۳۹۲ ۱۲:۳۱ ق.ظ
(۲۴ مهر ۱۳۹۲ ۰۸:۴۵ ب.ظ)m@hboobe نوشته شده توسط: گرامر G مفروض است کدام گزینه صحیح میباشد؟ سلام c که مشخصه چرا جزو fallow هاست. fallow های A هم جزو fallow های C هست .( طبق [tex]A \rightarrow aBC [/tex] ) و B fallow هم جزو fallow های A هست.(طبق [tex]B \rightarrow aA[/tex] ) fallowB هم شامل FIRST C,FIRST E و چون E به لاندا میرود e هم جزو انها هست.پس f,e,c هم جزو fallow B هستند.پس FALOW C شامل e,f,c,$ ,b هست. |