درخت نحو انتزاعی
در علوم کامپیوتر ، درخت نحو انتزاعی (AST)، یا فقط درخت نحو، نمایش درختی از ساختار نحوی انتزاعی متن (اغلب کد منبع ) نوشته شده به زبان رسمی است. هر گره درخت نشان‌دهنده یک ساختار در متن است.
"انتزاعی" بودن نحو به این معناست که تمام جزئیات ظاهر شده در نحو واقعی را نشان نمی‌دهد، بلکه فقط جزئیات ساختاری یا مرتبط با محتوا را نشان می‌دهد. به عنوان مثال، پرانتزهای گروه‌بندی به طور ضمنی در ساختار درختی هستند، بنابراین لازم نیست که به عنوان گره‌های جداگانه نمایش داده شوند. به همین ترتیب، یک ساختار نحوی مانند یک عبارت if-condition-then ممکن است با استفاده از یک گره منفرد با سه شاخه نشان داده شود.
این امر درختان نحو انتزاعی را از درختان نحو انضمامی که به طور سنتی درختان تجزیه نامیده می‌شوند، متمایز می‌کند. درختان تجزیه معمولاً توسط یک تجزیه‌کننده در طول فرایند ترجمه و کامپایل کد منبع ساخته می‌شوند. پس از ساخته شدن، اطلاعات اضافی با پردازش بعدی، به عنوان مثال، تجزیه و تحلیل زمینه‌ای به AST اضافه می‌شود.
درختان نحو انتزاعی نیز در تجزیه و تحلیل برنامه و سیستم‌های تبدیل برنامه استفاده می‌شوند.
درخت‌های نحو انتزاعی، ساختارهای داده‌ای هستند که به طور گسترده در کامپایلرها برای نمایش ساختار کد برنامه استفاده می‌شوند. یک AST معمولاً نتیجه فاز تحلیل نحوی یک کامپایلر است و اغلب به عنوان یک نمایش میانی از برنامه از طریق چندین مرحله که کامپایلر به آن نیاز دارد، عمل می‌کند و تأثیر زیادی بر خروجی نهایی کامپایلر دارد.
یک AST دارای چندین ویژگی است که به مراحل بعدی فرآیند کامپایل کمک می‌کند:AST ها به دلیل ماهیت ذاتی زبان‌های برنامه‌نویسی و مستندات آن‌ها مورد نیاز هستند. زبان‌ها معمولاً به طور ذاتی مبهم هستند. برای جلوگیری از این ابهام، زبان‌های برنامه‌نویسی اغلب به عنوان گرامر مستقل از متن (CFG) مشخص می‌شوند. با این حال، اغلب جنبه‌هایی از زبان‌های برنامه‌نویسی وجود دارند که بخشی از زبان هستند و در مشخصات آن مستند شده‌اند ولی یک CFG نمی‌تواند آن‌ها را بیان کند. این‌ها جزییاتی هستند که برای تعیین اعتبار و رفتارشان نیاز به یک زمینه دارند. برای مثال، اگر زبانی اجازه می‌دهد تا انواع جدیدی اعلام شود، یک CFG نمی‌تواند نام این انواع یا روشی که باید در آن استفاده شود را پیش‌بینی کند. حتی اگر یک زبان دارای مجموعه‌ای از انواع از پیش تعریف‌شده باشد، اعمال استفاده مناسب اغلب به زمینه‌ای نیاز دارد. مثال دیگر تایپ اردک است که در آن نوع یک عنصر بسته به زمینه می‌تواند تغییر کند. بارگذاری بیش از حد اپراتور مورد دیگری است که در آن استفاده صحیح و عملکرد نهایی به زمینه بستگی دارد.
طراحی یک AST اغلب با طراحی یک کامپایلر و ویژگی های مورد انتظار آن مرتبط است.
الزامات اصلی شامل موارد زیر است:از این الزامات می توان برای طراحی یک ساختار داده برای AST استفاده کرد.
برخی از عملیات همیشه به دو عنصر نیاز دارند، مانند جمع که به دو عبارت نیاز دارد. با این حال، برخی از ساختارهای زبان مانند فهرست‌های آرگومان‌هایی که از پوسته فرمان به برنامه‌ها ارسال می‌شوند، به تعداد دلخواه زیادی از فرزندان نیاز دارند. در نتیجه، یک AST که برای نمایش کد نوشته شده به چنین زبانی استفاده می شود، باید به اندازه کافی انعطاف‌پذیر باشد تا امکان اضافه کردن سریع تعداد ناشناخته‌ای از فرزندان را فراهم کند.
برای پشتیبانی از راستی‌آزمایی کامپایلر، باید بتوان یک AST را در فرم کد منبع برگرداند. کد منبع تولید شده باید پس از کامپایل مجدد به اندازه کافی شبیه به نسخه اصلی و از نظر اجرا یکسان باشد.
AST به شدت در طول تجزیه و تحلیل معنایی که در آن کامپایلر استفاده صحیح از عناصر برنامه و زبان را بررسی می‌کند، استفاده می‌شود. کامپایلر همچنین جداول نماد را بر اساس AST در طول تجزیه و تحلیل معنایی تولید می‌کند. پیمایش کامل درخت اجازه می‌دهد تا صحت برنامه تأیید شود.
پس از تأیید صحت، AST به عنوان پایه‌ای برای تولید کد عمل می کند. AST اغلب برای تولید یک نمایش میانی (IR) که گاهی اوقات زبان میانی نامیده می‌شود، برای تولید کد استفاده می‌شود.