درخت نحو انتزاعی

 

نمونه درخت نحو انتزاعی ساخته شده برای کد الگوریتم اقلیدس زیر:

while b ≠ 0:
    if a > b:
        a := a - b
    else:
        b := b - a
return a

در علوم کامپیوتر ، درخت نحو انتزاعی (AST)، یا فقط درخت نحو، نمایش درختی از ساختار نحوی انتزاعی متن (اغلب کد منبع ) نوشته شده به زبان رسمی است. هر گره درخت نشان‌دهنده یک ساختار در متن است.

"انتزاعی" بودن نحو به این معناست که تمام جزئیات ظاهر شده در نحو واقعی را نشان نمی‌دهد، بلکه فقط جزئیات ساختاری یا مرتبط با محتوا را نشان می‌دهد. به عنوان مثال، پرانتزهای گروه‌بندی به طور ضمنی در ساختار درختی هستند، بنابراین لازم نیست که به عنوان گره‌های جداگانه نمایش داده شوند. به همین ترتیب، یک ساختار نحوی مانند یک عبارت if-condition-then ممکن است با استفاده از یک گره منفرد با سه شاخه نشان داده شود.

این امر درختان نحو انتزاعی را از درختان نحو انضمامی که به طور سنتی درختان تجزیه نامیده می‌شوند، متمایز می‌کند. درختان تجزیه معمولاً توسط یک تجزیه‌کننده در طول فرایند ترجمه و کامپایل کد منبع ساخته می‌شوند. پس از ساخته شدن، اطلاعات اضافی با پردازش بعدی، به عنوان مثال، تجزیه و تحلیل زمینه‌ای به AST اضافه می‌شود.

درختان نحو انتزاعی نیز در تجزیه و تحلیل برنامه و سیستم‌های تبدیل برنامه استفاده می‌شوند.

برنامه‌های کاربردی در کامپایلرها

درخت‌های نحو انتزاعی، ساختارهای داده‌ای هستند که به طور گسترده در کامپایلرها برای نمایش ساختار کد برنامه استفاده می‌شوند. یک AST معمولاً نتیجه فاز تحلیل نحوی یک کامپایلر است و اغلب به عنوان یک نمایش میانی از برنامه از طریق چندین مرحله که کامپایلر به آن نیاز دارد، عمل می‌کند و تأثیر زیادی بر خروجی نهایی کامپایلر دارد.

انگیزه

یک AST دارای چندین ویژگی است که به مراحل بعدی فرآیند کامپایل کمک می‌کند:

• یک AST را می توان با اطلاعاتی مانند ویژگی‌ها و حاشیه‌نویسی برای هر عنصری که حاوی آن است ویرایش و بهبود بخشید. چنین ویرایش و حاشیه‌نویسی با کد منبع یک برنامه غیرممکن است، زیرا به معنای تغییر آن است.
• در مقایسه با کد منبع، یک AST شامل علائم نقطه‌گذاری و جداکننده‌های غیرضروری (پرانتز، نقطه ویرگول، پرانتز و غیره) نمی‌شود.
• یک AST معمولا به دلیل مراحل متوالی تجزیه و تحلیل توسط کامپایلر، حاوی اطلاعات اضافی در مورد برنامه است. به عنوان مثال، ممکن است موقعیت هر عنصر را در کد منبع ذخیره کند تا به کامپایلر امکان چاپ پیام‌های خطای مفید را بدهد.

AST ها به دلیل ماهیت ذاتی زبان‌های برنامه‌نویسی و مستندات آن‌ها مورد نیاز هستند. زبان‌ها معمولاً به طور ذاتی مبهم هستند. برای جلوگیری از این ابهام، زبان‌های برنامه‌نویسی اغلب به عنوان گرامر مستقل از متن (CFG) مشخص می‌شوند. با این حال، اغلب جنبه‌هایی از زبان‌های برنامه‌نویسی وجود دارند که بخشی از زبان هستند و در مشخصات آن مستند شده‌اند ولی یک CFG نمی‌تواند آن‌ها را بیان کند. این‌ها جزییاتی هستند که برای تعیین اعتبار و رفتارشان نیاز به یک زمینه دارند. برای مثال، اگر زبانی اجازه می‌دهد تا انواع جدیدی اعلام شود، یک CFG نمی‌تواند نام این انواع یا روشی که باید در آن استفاده شود را پیش‌بینی کند. حتی اگر یک زبان دارای مجموعه‌ای از انواع از پیش تعریف‌شده باشد، اعمال استفاده مناسب اغلب به زمینه‌ای نیاز دارد. مثال دیگر تایپ اردک است که در آن نوع یک عنصر بسته به زمینه می‌تواند تغییر کند. بارگذاری بیش از حد اپراتور مورد دیگری است که در آن استفاده صحیح و عملکرد نهایی به زمینه بستگی دارد.

طراحی

طراحی یک AST اغلب با طراحی یک کامپایلر و ویژگی های مورد انتظار آن مرتبط است.

الزامات اصلی شامل موارد زیر است:

• انواع متغیرها و همچنین مکان هر اعلان در کد منبع باید حفظ شود.
• ترتیب دستورات اجرایی باید صریحاً نمایش داده شود و به خوبی تعریف شود.
• اجزای چپ و راست عملیات باینری باید ذخیره شوند و به درستی شناسایی شوند.
• شناسه ها و مقادیر تخصیص داده شده آن‌ها باید برای عبارات انتساب ذخیره شوند.

از این الزامات می توان برای طراحی یک ساختار داده برای AST استفاده کرد.

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

برای پشتیبانی از راستی‌آزمایی کامپایلر، باید بتوان یک AST را در فرم کد منبع برگرداند. کد منبع تولید شده باید پس از کامپایل مجدد به اندازه کافی شبیه به نسخه اصلی و از نظر اجرا یکسان باشد.

استفاده

AST به شدت در طول تجزیه و تحلیل معنایی که در آن کامپایلر استفاده صحیح از عناصر برنامه و زبان را بررسی می‌کند، استفاده می‌شود. کامپایلر همچنین جداول نماد را بر اساس AST در طول تجزیه و تحلیل معنایی تولید می‌کند. پیمایش کامل درخت اجازه می‌دهد تا صحت برنامه تأیید شود.

پس از تأیید صحت، AST به عنوان پایه‌ای برای تولید کد عمل می کند. AST اغلب برای تولید یک نمایش میانی (IR) که گاهی اوقات زبان میانی نامیده می‌شود، برای تولید کد استفاده می‌شود.

جستارهای وابسته

• نمودار معنایی انتزاعی (ASG) که به آن نمودار اصطلاحی نیز می‌گویند
• الگوی ترکیبی
• نمودار کنترل جریان
• نمودار غیر چرخه ای جهت دار (DAG)
• مدل شیء سند (DOM)
• درخت بیان
• فرم توسعه یافته Backus–Naur
• Lisp ، خانواده‌ای از زبان‌های نوشته شده در درخت، با ماکروهایی برای دستکاری درختان کد
• درخت پارسه که به درخت نحو بتن نیز معروف است
• درخت تفکیک معنایی (SRT)
• الگوریتم Shunting-Yard
• جدول نمادها
• TreeDL

مطالعات بیشتر در این زمینه

• Jones, Joel. "Abstract Syntax Tree Implementation Idioms" (PDF). {{cite journal}}: Cite journal requires |journal= (help) (overview of AST implementation in various language families)
•  Fluri, Beat; Würsch, Michael; Pinzger, Martin; Gall, Harald C. "Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction" (PDF). {{cite journal}}: Cite journal requires |journal= (help) (direct link to PDF)
•  Lucas, Jason (16 August 2006). "Thoughts on the Visual C++ Abstract Syntax Tree (AST)".

پیوند های خارجی

• AST View : یک پلاگین Eclipse برای تجسم یک درخت نحو انتزاعی جاوا
• "Abstract Syntax Tree and Java Code Manipulation in the Eclipse IDE". eclipse.org.
• "CAST representation". cs.utah.edu.
• پروژه eli : تجزیه و تحلیل درخت نحو انتزاعی
• "Abstract Syntax Tree Metamodel Standard" (PDF).
• "Architecture‑Driven Modernization — ADM: Abstract Syntax Tree Metamodeling — ASTM". ( استاندارد OMG ).
• JavaParser : کتابخانه JavaParser یک درخت نحو انتزاعی کد جاوا را در اختیار شما قرار می دهد. ساختار AST سپس به شما اجازه می دهد تا با کد جاوا خود به روش برنامه نویسی آسان کار کنید.
• Spoon : کتابخانه ای برای تجزیه و تحلیل، تبدیل، بازنویسی و انتقال کد منبع جاوا. فایل های منبع را تجزیه می کند تا یک AST با طراحی خوب با API تجزیه و تحلیل و تبدیل قدرتمند بسازد.