چطور می توان تشخیص داد یک گرامر LL(K) است با نیست؟
مثلاً
[tex]S\: \longrightarrow\: SS\: \: |\: aSb\: |\: ab\: [/tex]
چرا گرامر LL است؟
تو کتاب لینز نوشته با در اختیار داشتن سمبل جاری خوانده شده و پیش بینی k-1 سمبل بعدی ، صرفاً درست را انتخاب کرد .
لطفاً دوستان مفهوم این عبارتو روی گرامر فوق توضیح دهید.
LL(k) بودن یک گرامر به این معناست که اگر یک رشته از زبان را به ما بدهند و بگویند برای اشتقاق آن از کدام قانون های گرامر به ترتیب استفاده کردید بتوانید در هر لحظه یک ورودی را بخوانید و با دیدن k تا کراکتر بعدی به درستی بگویید از کدام قوانین استفاده شده
مثلا به رشته ی abaabb از مین زبان دقت کنید می خواهیم تشخیص دهیم از چه قانون هایی برای اشتقاق این رشته استفاده شده
ابتدا a را می خوانیم اما نمی توانیم تا اینجا بفهیم از کدامیک از قوانین استفاده شده یه نگاهی به کاراکتر بعدی می اندازیم
با خواندن a و دیدن حرف بعد متوجه می شویم از قانون SS یا ab استفاده شده . برای بر طرف شدن شکمان به سومین کاراکتر نگاه م کنیم می بینیم رشته ادامه دارد پس در ابتدا مسلما از SS استفاده شده(تا اینجا با دیدن سه کاراکتر توانستیم بگوییم از چه قانونی رفته ایم پس LL(3) است)
و علاوه بر این تا اینجای کار می دانیم:
[tex]ُS\longrightarrowSS\longrightarrowabS[/tex]
ادامه می دهیم اکنون a را می بینیم چیزی نمی فهیمیم کاراکتر بعد را می بینیم آن هم a است پس با دیدن دو کاراکتر فهمیدم که
[tex]ُS\longrightarrowSS\longrightarrowabS\longrightarrowabaSb[/tex]
ادامه می دهیم اکنون بعد از a کاراکتر b را می بینم پس:
[tex]ُS\longrightarrowSS\longrightarrowabS\longrightarrowabaSb\longrightarrowabaabb[/tex]
با طی کردن همین روند برای چند رشته ی دیگر زبان متوجه خواهید شد که برای هر رشته کافیست در هر لحظه دو سه تا کراکتر بعدی را ببینیم اونوقت می فهمیم برای اتشقاق از چه قوانینی استفاده شده
دو نکته:
تمام گرامر های منظم LL(1) هستند چون همگی قوانین آن ها تنها یک ترمینال در ابتدا دارند و با دیدن یک کارکتر می توان قانونی که در اشتقاق به کار برده شده را تشخیص داد
تمام گرامر های LL(k) قطعی و غیر مبهم هستند چون حتما با دیدن k کارکتر بعدی در هر گام می توان درخت اشتقاق را به طور واحد و قطعی کشید.