Абстрактне синтаксичне дерево

Абстрактне синтаксичне дерево (АСД) — в інформатиці це скінченна множина, позначене і орієнтоване дерево, в якому внутрішні вершини співставлені з відповідними операторами мови програмування, а листя з відповідними операндами. Таким чином листя є порожніми операторами і являють собою тільки змінні і костанти. Синтаксичні дерева використовуються в парсерах для проміжного представлення програми між деревом розбору (конкретним синтаксичним деревом) і структурою даних яка потім використовується в якості внутрішнього представлення компілятора або інтерпретатора комп'ютерної програми для оптимізації і генерації коду. Можливі варіанти подібних структур описуються абстрактним синтаксисом. АСД відрізняється від дерева розбору тим, що в ньому відсутні вузли і ребра, для тих синтаксичних правил, що не впливають на семантику програми. Класичним приміром токої відсутності є групувальні дужки, через те, що в АСД групування задається структурою дерева. Для мови, яка описується контекстно-вільною граматикою, якими є майже всі мови програмування, створення абстрактного дерева в синтаксичному аналізаторі є тривіальним завданням. Більшість правил в граматиці створюють нову вершину, а символи в правилі стають ребрами. Правила, які нічого не привносять в АСД, такі як правила групування, просто заміняються в вершині одним з своїх символів. Крім того, аналізатор може створити повне дерево розбору і після цього пройтися по ньому, видаляючи вузли і ребра, які не використовуються в абстрактному синтаксисі, щоб створити АСД.

Посилання

• AST View, плагін для Eclipse показує АСД для мови Java;
• Корисна інформація про представлення АСД в Eclipse і маніпулюванні сирцевим кодом Java;
• Стаття «Ідіоми реалізації АСД» Джоела Джонса (англ. Joel Jones) (огляд реалізацій АСД в різних сімейсвах мов)
• Стаття «Дизайн абстрактного синтаксичного дерева» Ніколя Ховарта (англ. Nicola Howarth) (описується дизайн АСД одного конкретного проекту і стаття не містить загального погляду)
• Стаття «Дослідження еволюції коду з використанням порівняння АСД» Юліана Немтью (англ. Iulian Neamtiu), Джеффрі Фостера (англ. Jeffrey S. Foster) та Міхаеля Хікса (англ. Michael Hicks);
• Стаття «Видобуток змін: Пошук відмінностей в деревах для високоточного визначаення змін в сирчевому коді» Біта Флурі (англ. Beat Fluri), Міхаеля Вурщ (англ. Michael Würsch), Мартина Пінцгера (англ. Martin Pinzger) та Гаральда Галла (англ. Harald C. Gall);
• Дипломна работа Міхаеля Вурща (англ. Michael Würsch) «Поліпшення розпізнавання в сирцевих кодах за допомогою АСД»
• Стаття «Думки про АСД у Visual C++» Джейсона Лукаса (англ. Jason Lucas);
• Навчальний посібник «Стандарт метамоделі АСД»;
• Представлення CAST;
• Abstract Syntax Tree Unparsing.

Це незавершена стаття про комп'ютери. Ви можете допомогти проекту, виправивши або дописавши її.