تحلیل لغوی و نحوی
تحلیل لغوی و نحوی بخش جلویی یک کامپایلر را تشکیل میدهند و متن منبع را به توکنها تقسیم کرده و ساختار گرامری آن را به عنوان یک درخت تجزیه یا نحو تشخیص میدهند.
Definition
تحلیل لغوی فازی است که کاراکترهای ورودی را به توکنها گروهبندی میکند، و تحلیل نحوی (تجزیه) فازی است که تعیین میکند آیا و چگونه آن توکنها یک برنامه معتبر را طبق یک گرامر تشکیل میدهند و یک درخت نحو تولید میکند.
Scope
این موضوع شامل تحلیل لغوی است که جریان کاراکترها را با استفاده از زبانهای منظم و اتوماتای متناهی به توکنها تبدیل میکند، و تحلیل نحوی (تجزیه) که ساختار عبارتی یک برنامه را در برابر یک گرامر مستقل از متن تشخیص میدهد. این شامل تجزیه از بالا به پایین (LL) و از پایین به بالا (LR)، تولیدکنندههای تجزیهکننده، ابهام و بازیابی خطا، و ساخت درختان نحو انتزاعی است.
Core questions
- چگونه از زبانهای منظم و مستقل از متن برای توصیف ساختار برنامه استفاده میشود؟
- مبادلات بین تجزیه LL و LR چیست؟
- چگونه ابهام و خطاهای تجزیه شناسایی و مدیریت میشوند؟
- چگونه یک درخت نحو انتزاعی از جریان توکن ساخته میشود؟
Key theories
- تجزیه LR
- کِنوث تجزیه LR را معرفی کرد، یک تکنیک از پایین به بالا که به طور قطعی کلاس وسیع گرامرهای LR را در زمان خطی تجزیه میکند و اساس بسیاری از تولیدکنندههای تجزیهکننده را تشکیل میدهد.
- تجزیه کلی مستقل از متن
- الگوریتم اِرلی گرامرهای مستقل از متن دلخواه، از جمله گرامرهای مبهم را تجزیه میکند و یک روش کلی را زمانی که تجزیهکنندههای قطعی محدود کافی نیستند، ارائه میدهد.
- مبانی منظم و مستقل از متن بخش جلویی
- کتاب اژدها (The Dragon Book) استفاده از عبارات منظم و اتوماتای متناهی برای اسکن و گرامرهای مستقل از متن برای تجزیه، از جمله الگوریتمهای استاندارد ساخت LL و LR را سیستماتیک میکند.
Clinical relevance
تجزیه لغوی و نحوی نه تنها برای کامپایلرها بلکه برای مفسرها، لینترها، فرمتکنندهها، IDEها و پردازشگرهای فرمت دادهها اساسی هستند. تجزیه قوی با بازیابی خطای خوب برای تجربه توسعهدهنده هر ابزار زبانی ضروری است.
History
سلسله مراتب زبان رسمی چامسکی در اواخر دهه 1950 نظریه زبانهای منظم و مستقل از متن را ارائه داد. کِنوث در سال 1965 تجزیه LR را رسمی کرد و اِرلی در سال 1970 یک الگوریتم کلی مستقل از متن ارائه داد. تولیدکنندههای تجزیهکننده مانند yacc تجزیه LR را عملی کردند، در حالی که کارهای بعدی به بررسی گرامرهای عبارت تجزیه و تجزیهکنندههای مبتنی بر ترکیبکننده پرداختند.
Debates
- تجزیهکنندههای تولید شده در مقابل تجزیهکنندههای دستنویس
- متخصصان در مورد استفاده از تولیدکنندههای تجزیهکننده از گرامرهای رسمی، که مختصر و قابل تأیید هستند، در مقابل تجزیهکنندههای بازگشتی نزولی دستنویس، که اغلب پیامهای خطای بهتر و کنترل بیشتری را با هزینه کد بیشتر ارائه میدهند، بحث میکنند.
Key figures
- Donald Knuth
- Jay Earley
- Alfred Aho
- Noam Chomsky
Related topics
Seminal works
- knuth1965
- earley1970
- aho2006
Frequently asked questions
- تفاوت بین یک لکسر و یک تجزیهکننده چیست؟
- یک لکسر کاراکترهای خام را به توکنهایی مانند شناسهها و عملگرها گروهبندی میکند، در حالی که یک تجزیهکننده آن توکنها را طبق گرامر زبان در یک درخت نحو سلسله مراتبی مرتب میکند.
- تفاوت بین تجزیه LL و LR چیست؟
- تجزیهکنندههای LL از بالا به پایین کار میکنند و تولیدات را از پیشوند ورودی پیشبینی میکنند، در حالی که تجزیهکنندههای LR از پایین به بالا کار میکنند و زیررشتههای شناسایی شده را کاهش میدهند؛ LR کلاس گرامرهای به مراتب بزرگتری را مدیریت میکند اما ساخت آن پیچیدهتر است.