۰
subtitle
ارسال: #۱
  
LL(K) گرامر
چطور می توان تشخیص داد یک گرامر LL(K) است با نیست؟
مثلاً
[tex]S\: \longrightarrow\: SS\: \: |\: aSb\: |\: ab\: [/tex]
چرا گرامر LL است؟
تو کتاب لینز نوشته با در اختیار داشتن سمبل جاری خوانده شده و پیش بینی k-1 سمبل بعدی ، صرفاً درست را انتخاب کرد .
لطفاً دوستان مفهوم این عبارتو روی گرامر فوق توضیح دهید.
مثلاً
[tex]S\: \longrightarrow\: SS\: \: |\: aSb\: |\: ab\: [/tex]
چرا گرامر LL است؟
تو کتاب لینز نوشته با در اختیار داشتن سمبل جاری خوانده شده و پیش بینی k-1 سمبل بعدی ، صرفاً درست را انتخاب کرد .
لطفاً دوستان مفهوم این عبارتو روی گرامر فوق توضیح دهید.
۲
ارسال: #۲
  
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 کارکتر بعدی در هر گام می توان درخت اشتقاق را به طور واحد و قطعی کشید.
مثلا به رشته ی 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 |
|
تشخیص نوع زبان و گرامر به صورت تستی و سریع | kamran_maneshtir | ۰ | ۲,۲۷۲ |
۰۲ بهمن ۱۳۹۶ ۰۷:۴۶ ب.ظ آخرین ارسال: kamran_maneshtir |
|
گرامر منظم | fsmtnc | ۲ | ۳,۰۱۲ |
۱۴ دى ۱۳۹۶ ۱۱:۵۷ ق.ظ آخرین ارسال: fsmtnc |
|
گرامر | fsmtnc | ۲ | ۲,۵۹۴ |
۱۱ دى ۱۳۹۶ ۱۱:۱۶ ق.ظ آخرین ارسال: fsmtnc |
|
پیاده سازی سیستم بیمارستان با گرامرها | mahshar_370 | ۱ | ۲,۰۲۱ |
۱۰ آذر ۱۳۹۶ ۱۲:۴۹ ب.ظ آخرین ارسال: فاطمه سلیمانی |
|
کتاب مناسب برای گرامر ارشد | Sepideh96 | ۰ | ۲,۱۶۴ |
۰۱ آبان ۱۳۹۶ ۰۱:۵۱ ب.ظ آخرین ارسال: Sepideh96 |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close