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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

تحلیلگر بالا به پایین در علوم کامپیوتر تحلیل بالا به پایین استراتژی است که در آن ابتدا به بالای درخت تحلیل نگاه می کنیم و سپس با بازنویسی قواعد گرامر به سمت برگ ها حرکت می کنیم. تحلیلگر ها ی LL از این روش استفاده می کنند.

تحلیل بالا به پایین را استراتژی است برای تحلیل ارتباطات بین داده های ناشناس از طریق فرض کردن ساختار یک درخت تحلیل کلی و سپس در نظر گرفتن سازگاری آن با مفروضات. این در مورد آنالیز هم زبان های طبیعی و هم زبان های کامپیوتری مصداق دارد.

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

تحلیل بالا به پایین همراه با backtracking میتواند دارای پیچیدگی زمانی نمایی با توجه به طول ورودی و ابهام گرامر باشد.برخی دانشمندان با تغییراتی توانسته اند راه حل با پیچیدگی زمانی چند جمله ای نیز ارائه کنند.

کاربرد زبان های برنامه نویسی[ویرایش]

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

  • A \rightarrow aBC
  • B \rightarrow c \mid cd
  • 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