زمان کنونی: ۰۳ آذر ۱۴۰۳, ۰۵:۲۹ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

LL(K) گرامر

ارسال:
  

joyebright پرسیده:

LL(K) گرامر

چطور می توان تشخیص داد یک گرامر LL(K) است با نیست؟

مثلاً
[tex]S\: \longrightarrow\: SS\: \: |\: aSb\: |\: ab\: [/tex]

چرا گرامر LL است؟

تو کتاب لینز نوشته با در اختیار داشتن سمبل جاری خوانده شده و پیش بینی k-1 سمبل بعدی ، صرفاً درست را انتخاب کرد .

لطفاً دوستان مفهوم این عبارتو روی گرامر فوق توضیح دهید.Heart

۲
ارسال:
  

fatemeh69 پاسخ داده:

RE: LL(K) گرامر

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 کارکتر بعدی در هر گام می توان درخت اشتقاق را به طور واحد و قطعی کشید.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  آموزش زبان انگلیسی:گرامر cyruskingsolomon ۱ ۳,۳۴۳ ۲۲ فروردین ۱۴۰۰ ۰۱:۲۲ ب.ظ
آخرین ارسال: cyruskingsolomon
  گرامر زبان انگلیسی:صفت های ed و ing دار cyruskingsolomon ۳ ۳,۱۱۱ ۱۵ بهمن ۱۳۹۹ ۰۶:۴۱ ب.ظ
آخرین ارسال: cyruskingsolomon
  گرامر منظم Sanazzz ۶ ۷,۰۳۴ ۳۱ اردیبهشت ۱۳۹۸ ۰۴:۳۲ ب.ظ
آخرین ارسال: Sanazzz
  گرامر مستقل از متن Sanazzz ۴ ۵,۵۱۵ ۱۲ دى ۱۳۹۷ ۰۹:۵۹ ب.ظ
آخرین ارسال: Sanazzz
  گرامر Sanazzz ۰ ۱,۸۰۲ ۰۵ آذر ۱۳۹۷ ۰۴:۴۰ ب.ظ
آخرین ارسال: Sanazzz
Exclamation تشخیص نوع زبان و گرامر به صورت تستی و سریع kamran_maneshtir ۰ ۲,۲۶۱ ۰۲ بهمن ۱۳۹۶ ۰۷:۴۶ ب.ظ
آخرین ارسال: kamran_maneshtir
  گرامر منظم fsmtnc ۲ ۳,۰۰۴ ۱۴ دى ۱۳۹۶ ۱۱:۵۷ ق.ظ
آخرین ارسال: fsmtnc
  گرامر fsmtnc ۲ ۲,۵۸۳ ۱۱ دى ۱۳۹۶ ۱۱:۱۶ ق.ظ
آخرین ارسال: fsmtnc
  پیاده سازی سیستم بیمارستان با گرامرها mahshar_370 ۱ ۲,۰۱۴ ۱۰ آذر ۱۳۹۶ ۱۲:۴۹ ب.ظ
آخرین ارسال: فاطمه سلیمانی
  کتاب مناسب برای گرامر ارشد Sepideh96 ۰ ۲,۱۵۸ ۰۱ آبان ۱۳۹۶ ۰۱:۵۱ ب.ظ
آخرین ارسال: Sepideh96

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close