تجزیه قطعی

تجزیه قطعی تجزیه‌ای است که در آن بتوان به صورت قطعی و در زمان چند جمله‌ای تجزیه پذیر بودن یا نبودن یک عبارت توسط گرامر را تشخیص داد. این نوع رفتار همان رفتار مورد نیاز در کامپایلرهاست.این نوع تجزیه معمولاً براساس ماشین پشته‌ای قطعی است.

گرامر قطعی مستقل از متن ^{[۱] [۲]}

گرامرهای قطعی مستقل از متن در زمینه کامپایلر و به‌طور کل هرجا که قرار است زبانی به زبان دیگر ترجمه شود کاربرد فراوان دارد. یک گرامر را زمانی گرامر مستقل ازمتن قطعی می نامیم ، به‌طوری‌که تمام رشته‌های تولید شده توسط این گرامر توسط یک ماشین پشته‌ای قطعی قابل تولید باشد و یک زبان مستقل از متن قطعی تولید کند. این نوع گرامرها خالی از هرنوع ابهام هستند.
زبان *L ⊆ Σ یک زبان مستقل از متن قطعی است اگر (L$ = L(M برای ماشین پشته‌ای قطعی M ، درحالی که $ یک علامت جدید می‌باشد که در Σ نیست.

ماشین پشته‌ای قطعی^{[۱] [۳]}

یک ماشین پشته‌ای قطعی است زمانی که به ازای هر ساخت در آن ماشین حداکثر یک انتقال ممکن باشد.

• این مساله با ماشین تعیین پذیر حالت متناهی متفاوت است چرا که امکان دارد که هیچ گونه انتقالی ممکن نباشد و ماشین پشته‌ای در وسط ورودی گیر کند.
• مساله تشخیص این که یک ماشین پشته‌ای قطعی است یا نه مساله ساده و مشخصی نیست.در زیر بعضی از مواردی که در آن قطعیت ماشین پشته‌ای از بین می‌رود آورده شده است:

1. ساخت‌های ((p, a, ϵ), (q, γ)) و (('p, ϵ, A), (q′, γ)) وجود داشته باشند: اگر در حالت p بوده و در حال خواندن a از ورودی باشیم و A در بالای پشته باشد آن گاه هر دو انتقال قابل انجام هستند.
2. ساخت‌های ((p, a, A), (q, γ)) و (('p, a, AB), (q′, γ)) وجود داشته باشند: اگر در حالت p بوده و در حال خواندن a از ورودی باشیم و AB در بالای پشته باشد آن گاه هر دو انتقال قابل انجام هستند.
3. ساخت‌های ((p, a, A), (q, γ))و (('p, ϵ, AB), (q′, γ)) وجود داشته باشد: اگر در حالت p بوده و در حال خواندن a از ورودی باشیم و AB در بالای پشته باشد آن گاه هر دو انتقال قابل انجام هستند.

و ... . برای این که یک ماشین پشته‌ای قطعی باشد برای هرجفت از انتقال‌ها باید حداقل یکی از موارد زیر بر قرار باشد:

1. انتقال‌ها ((p_i, a_i, β_i), (q_i, γ_i))، p_i متفاوتی داشته باشند.
2. انتفال‌ها a_i متفاوتی داشته باشند که هیچ‌کدام از آن‌ها ϵ نیستند.
3. انتقال‌ها βi متفاوتی داشته باشند که هیچ‌کدام پیشوند دیگری هم نباشد.

گذری بر تجزیه در تاریخ

• در سال 1965 کنوث(knuth) تجزیه گر چپ به راست(LR parser) را توسعه داد که می‌توانست با استفاده از پیش‌بینی در زمان قطعی هر گرامر قطعی مستقل از متنی را بازسازی کند.
• در سال 1969 دی رمر (DeRemer) تجزیه گرهای LALR را معرفی کرد که در واقع نسخه‌ای ساده شده از LR بودند.این تجزیه گرهای به حافظه کمتری نسبت به LR نیاز داشتند اما ضعیف تر بودند.

تجزیه بالا به پایین و پایین به بالا ^{[۱] [۳]}

تجزیه بالا به پایین

ایده اصلی تجزیه بالا به پایین ساخت یک ماشین پشته‌ای از یک گرامرو پس از آن قطعی کردن آن ماشین پشته‌ای است. بعضی از راه‌های قطعی کردن ماشین پشته‌ای عبارت اند از:

1. پیش‌بینی کردن یک علامت
2. فاکتورگیری از چپ
3. حذف بازگشت چپ

گرامرهایی که پیش‌بینی یک علامت برای آن‌ها برای تجزیه بالا به پایین چپ به راست کفایت می‌کند گرامرهای (LL(1 می گویند.

تجزیه پایین به بالا

تجزیه پایین به بالا براساس کلاس (LR(K گرامرها به وجود آمده‌است."L" به معنای خواندن ورودی از چپ به راست است."R" به معنای این است که راست‌ترین تجزیه انجام خواهد شد. در تجزیه پایین به بالا مانند تجزیه بالا به پایین ماشین پشته‌ای به وجود می آوریم با این تفاوت که در تجزیه پایین به بالا ماشین پشته‌ای به وجود آمده راست‌ترین استخراج پایین به بالا از یک پایانه ورودی انجام می دهیم تا به علامت شروع S برسیم.

بیشتر بخوانید

1. LL Parser
2. تجزیه پایین به بالا
3. تجزیه بالا به پایین

منابع

1. «Deterministic Parsing». بایگانی‌شده از اصلی در ۲ ژانویه ۲۰۱۸. دریافت‌شده در ۱ ژانویه ۲۰۱۸.
2. Deterministic context-free grammar this version
3. Determininsm and Parsing Slides of UNC