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

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

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

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

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

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

Примітки

↑ МЕТОДИЧНІ РЕКОМЕНДАЦІЇ До лабораторного практикуму побудови мовних процесорів з дисципліни «Системне програмування» (PDF). Факультет кібернетики КНУ ім. Тараса Шевченка, Кафедра теорії та технології програмування. 2013. Архів оригіналу (PDF) за 4 березня 2016. Процитовано 10 жовтня 2015. [Архівовано 2016-03-04 у Wayback Machine.]

Посилання

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.];
Abstract Syntax Tree Unparsing.

Це незавершена стаття про інформаційні технології.
Ви можете допомогти проєкту, виправивши або дописавши її.

[1] МЕТОДИЧНІ РЕКОМЕНДАЦІЇ До лабораторного практикуму побудови мовних процесорів з дисципліни «Системне програмування» (PDF). Факультет кібернетики КНУ ім. Тараса Шевченка, Кафедра теорії та технології програмування. 2013. Архів оригіналу (PDF) за 4 березня 2016. Процитовано 10 жовтня 2015. [Архівовано 2016-03-04 у Wayback Machine.]

[1]