گرامر ال‌ال

در نظریه زبان صوری ، گرامر LL، نوعی گرامر مستقل از متن است که می تواند توسط یک تجزیه کننده LL، تجزیه شود. که تجزیه ورودی از چپ به راست، و یک اشتقاق چپ ترین از جمله را تشکیل می دهد. (در مقایسه با تجزیه کننده LR که اشتقاق راست ترین را ایجاد می کند). زبانی که گرامر LL دارد به عنوان یک زبان LL شناخته می شود. گرامر LL زیرمجموعه ای از گرامرهای مستقل از متن قطعی (DCFG) و زبان LL زیرمجموعه ای از زبانهای مستقل از متن قطعی (DCFL) می باشد.

پارسرهای LL پارسهای مبتنی بر جدول هستند (مشابه پارسر های LR). بجز روش مبتنی بر جدول، گرامرهای LL را می توان با تجزیه کننده کاهشی بازگشتی تجزیه کرد. این پارسرها به راحتی می توانند با دست نوشته شوند. این مقاله در مورد ویژگی های رسمی دستور زبان LL است. برای تجزیه ، به تجزیه کننده LL یا تجزیه کننده نزولی بازگشتی مراجعه کنید.

تعریف رسمی

اگر $k \geq 0$ یک عدد طبیعی باشد، یک گرامر مستقل از متن $G = (V, Σ, R, S)$ یک گرامر LL(k) است اگر :

برای هر رشته نماد پایانه $w \in Σ^{*}$ با طول حداکثر $k$ نماد،
برای هر نماد ناپایانه $A \in V$ و
برای هر رشته نماد پایانه $w_{1} \in Σ^{*}$ ،

حداکثر یک قانون تولید $r \in R$ وجود داشته باشد به طوری که برای برخی از رشته نماد های پایانه $w_{2}, w_{3} \in Σ^{*}$ ،

رشته $w_{1} A w_{3}$ را بتوان از اشتقاق نماد شروع $S$ بدست آورد ،
$w_{2}$ را بتوان از اشتقاق $A$ بعد از اعمال اولین قانون $r$ بدست آورد و
$k$ تا نماد اول $w$ با $k$ تا نماد اول $w_{2} w_{3}$ تطابق داشته باشد. ^[۱]

همچنین ببینید

مقایسه تولیدکننده های تجزیه کننده لیستی از پارسرهای LL (k) و LL (*)

منابع

الگو:Refbegin

الگو:Refend

↑ الگو:Harvard citation text. Def.1. The authors do not consider the case k=0.

[1] الگو:Harvard citation text. Def.1. The authors do not consider the case k=0.

[۱]

گرامر ال‌ال

تعریف رسمی

همچنین ببینید

منابع

منوی ناوبری

جستجو