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

گرامر 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 و $ باید باشه!

سلام.
برای مشخص کردن 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 خواهد شد. و گزینه صحیح 4 است.

(24 مهر 1392 08:45 ب.ظ)m@hboobe نوشته شده توسط: [ -> ]گرامر 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 و $ باید باشه!

سلام
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 هست.