نکات تستی کنکور کامپایلر - تحلیل نحوی - تحلیل بالا به پایین

انواع روشهای تجزیه: بالا به پایین و پایین به بالا.

مهمترین روشهای تجزیه بالا به پایین: تجزیه بازگشتی پیشگو. تجزیه غیر بازگشتی پیشگو

مهمترین روشهای تجزیه پایین به بالا: تجزیه تقدم عملگر. تجزیه تقدم ساده. تجزیه LR(1) که دارای سه شکل متفاوت SLR(1) و LALR(1) و CLR(1) است. که همه اینها از روش کلی انتقال-کاهش استفاده میکنند.

در تجزیه بالا به پایین از همان ترتیب قواعد اشتقاق چپ استفاده میشود و در تجزیه پایین به بالا از عکس قواعد اشتقاق راست استفاده میشود.

برای قوانین لاندا در تجزیه بازگشتی پیشگو به lookaheadtoken نگاه میکنیم اگه تو فالو بود که اوکیه و اگر نبود خطا میدیم.

دو نوع بازگشتی چپ داریم که در تجزیه بالا به پایین مشکل ایجاد میکنند: بازگشتی چپ صریح و بازگشتی چپ ضمنی.(وجود بازگشتی راست مشکلی ایجاد نمیکند)

چندتا کار که باید برای تجزیه بالا به پایین کرد: حذف بازگشتی چپ. فاکتور گیری چپ. تبدیل گرامر مبهم به غیر مبهم معادل. استخراج زبان گرامر و نوشتن یک گرامر LL(1) معادل آن.

حذف بازگشتی چپ روی گرامر مبهم اون رو غیر مبهم نمیکنه.

اندازه جدول LL(1) برابر |V| * (|T+1) است.

گرامر مبهم به هیچ وجه LL(k) نیست!

برای رفع خطای نحوی ۲ استراتژی وجود دارد:

۱. رفع خطا در محل وقوع

۲. رفع خطا با استفاده از نادیده گرفتن توکنهای ورودی تا جایی که خطا رد بشه.

چهار روش رفع خطا داریم:

۱. Phrase leve: با استفاده از استراتژی اوله که با درج یا حذف چند نماد از بالای پشته یا اضافه کردن چند توکن به ورودی عمل میکنه.

۲. Panic mode: از استراتژی دوم استفاده میکنه اونقدر میریم جلو که به یه توکن همزمانی برسیم.

۳. Error production rules: همونجوری که برای جملات درست قانون مینویسیم برای جملات غلط هم مینویسیم.

۴.global correction که بیشتر جنبه نظری دارد تا عملی

هر گرامر LL(k)  یک گرامر LL(k+1 هم هست ولی برعکس درست نیست.

گرامرهای LL(k) از جنس گرامرهای قطعی نوع دوم هستند. اما گرامرهای قطعی ای وجود دارند که LL(K نیستند.

گرامرهای ساختار شرطی LL(1 نیستند!

زبانهای منظم و ساده LL(1) هستند.

عملگری شرکت پذیر چپ است که سمت چپ اولویت بیشتری از سمت راست داشته باشد. یعنی قایده E->E+T شرکت پذیر چپ و E->T+E شرکت پیذیر راست است.

چیزهایی که باید از کتاب خوانده شود: first/follow. قواید LL(1). جدول LL(1). الگوریتم LL(1). رفع خطا در LL(1).