Дерево синтаксичного аналізу

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

Відмінність від дерева розбору

Сюди перенаправляється запит «Синтаксичне дерево». На цю тему потрібна окрема стаття.

Синтакси́чне де́рево (також називається «конкретним синтаксичним деревом» або «деревом розбору») виводу слова ω у граматиці G — це впорядковане дерево, корінь котрого позначено аксіомою, в проміжних вершинах знаходяться нетермінали, а на кроні — термінали.

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

Примітки

1. (PDF). Факультет кібернетики КНУ ім. Тараса Шевченка, Кафедра теорії та технології програмування. 2013. Архів оригіналу (PDF) за 4 березня 2016. Процитовано 10 жовтня 2015.

Посилання

• AST View [ 21 квітня 2009 у Wayback Machine.], плагін для Eclipse показує АСД для мови Java;
• Корисна інформація про представлення АСД в Eclipse і маніпулюванні початковим кодом Java [ 4 вересня 2008 у Wayback Machine.];
• Стаття «» Джоела Джонса (англ. 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++ [ 10 травня 2007 у Wayback Machine.]» Джейсона Лукаса (англ. Jason Lucas);
• Навчальний посібник «Стандарт метамоделі АСД [ 15 вересня 2009 у Wayback Machine.]»;
• Представлення CAST [ 14 червня 2010 у Wayback Machine.];
• .