گرامر ال‌ال

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

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

تعریف رسمی

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

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

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

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

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

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

منابع

• Beatty, J. C. (1982). "On the relationship between LL(1) and LR(1) grammars" (PDF). Journal of the ACM. 29 (4 (Oct)): 1007–1022. doi:10.1145/322344.322350.
• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 978-0-201-02988-8.
• Korenjak, A.J., Hopcroft, J.E. (1966). "Simple deterministic languages". IEEE Conf. Rec. 7th Ann. Symp. on Switching and Automata Theory (SWAT). IEEE Pub. No. Vol. 16-C-40. pp. 36–46. doi:10.1109/SWAT.1966.22.{{cite book}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
• Parr, T.; Fisher, K. (2011). "LL(*): The Foundation of the ANTLR Parser Generator" (PDF). ACM SIGPLAN Notices. 46 (6): 425–436. doi:10.1145/1993316.1993548.
• Rosenkrantz, D. J.; Stearns, R. E. (1970). "Properties of Deterministic Top Down Grammars". Information and Control. 17 (3): 226–256. doi:10.1016/s0019-9958(70)90446-8.
• William M. Waite and Gerhard Goos (1984). Compiler Construction. Texts and Monographs in Computer Science. Heidelberg: Springer. ISBN 978-3-540-90821-0.