تحلیلگر بالا به پایین

یک کامپایلر با تحلیل و تطبیق قواعد ورودی یک زبان برنامه نویسی را به زبان اسمبلی تبدیل می‌کند.تحلیلگر بالا به پایین LL با اعمال قواعد تولید روی هر غیر پایانه و با توجه به لزوم تولید اشتقاق چپ تحلیل خود را انجام می‌دهد و سپس این کار را برای غیره پایانه‌ای دیگر تکرار می‌کند. در این تحلیل سعی می‌شود تا سمت چپ‌ترین غیر پایانه از قاعده انتخاب و گسترش یابد و به همین ترتیب ادامه می دهیم. به‌طور مثال:

• ${\displaystyle A\rightarrow aBC}$
• ${\displaystyle B\rightarrow c\mid cd}$
• ${\displaystyle C\rightarrow df\mid eg}$

به این ترتیب بعد از قاعده اول B گسترش یافته و سپس C. در گرامرهای مبهم بیش از یک درخت اشتقاق چپ برای یک رشته موجود می‌باشد.یکی از راه حل‌های این موضوع استفاده از تحلیلگر LR می‌باشد.

گرامرهایی که دارای بازگتی چپ هستند به سادگی قابلیت اعمال تحلیل بالا به پایین بر روی آن را نداریم گرچه پیشرفت‌هایی در این زمینه صورت گرفته اما راه پیشنهادی تبدیل آن به فرم باز گشتی راست است.الگوریتمی توسط Callaghan و Frost و Hafiz در زبان haskall طراحی شده که مسئله گرامرهای مبهم را حل می‌کند.

اگر گرامر مبهم باشد تحلیلگر در بدترین حالت ممکن با در نظر داشتن ورودی باید همه قواعد را امتحان کند و تمام درخت‌های اشتقاق چپ ممکن را به دست آورد ، که اینکار دارای پیچیدگی زمانی و مکانی نمایی است. Norvig در سال 1991 این موضووع را حل کرد. کلید اصلی ذخیره کردن نتیجه حاصل از اعمال تحلیلگر P در مقطع j است و استفاده از آن در هر زمانی که در موقعیت مشابهی قرار گرفتیم.

LL می‌تواند خوانا و کوچک باشد گرچه آهسته تر است. زمان لازم وابسته به جدول BNF است که می‌تواند همان مشکلات LALR را ایجاد کند.LL حافظه زیادی می‌گیرد ولی بازگشتی بودن را پشتیبانی می‌کند. یک LALR در بازگشت به بالا مسیر بیشتری نسبت به LL در رفتن به حالت بعدی اش دارد.

• تحلیل پایین به بالا
• تحلیل
• تحلیلگر بازگشتی نزولی
• تحلیل عبارات گرامر

• Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986). Compilers, principles, techniques, and tools (Rep. with corrections. ed.). Addison-Wesley Pub. Co. ISBN 978-0201100884.
• Aho, Alfred V.; Ullman, Jeffrey D. (1972). The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.) (Repr. ed.). Englewood Cliffs, NJ: Prentice-Hall. ISBN 978-0139145568.
• M. (1985) “Efficient Parsing for Natural Language.” Kluwer, Boston, MA

• X-SAIGA - eXecutable SpecificAtIons of GrAmmars