Абстрактне синтаксичне дерево (англ. Abstract syntax tree) (АСД) в інформатиці — це скінченна множина, позначене і орієнтоване дерево, в якому внутрішні вершини співставлені з відповідними операторами мови програмування, а листя з відповідними операндами. Синтаксичні дерева використовуються в парсерах для проміжного представлення програми між деревом розбору (конкретним синтаксичним деревом) і структурою даних, яка потім використовується як внутрішнє представлення компілятора або інтерпретатора комп'ютерної програми для оптимізації і генерації коду. Можливі варіанти подібних структур описуються абстрактним синтаксисом.
Відмінність від дерева розбору Редагувати
Синтакси́чне де́рево (також називається «конкретним синтаксичним деревом» або «деревом розбору») виводу слова ω у граматиці G — це впорядковане дерево, корінь котрого позначено аксіомою, в проміжних вершинах знаходяться нетермінали, а на кроні — термінали.
АСД відрізняється від дерева розбору тим, що в ньому відсутні вузли і ребра для тих синтаксичних правил, що не впливають на семантику програми. Класичним прикладом такої відсутності є групувальні дужки через те, що в АСД групування задається структурою дерева. Для мови, яка описується контекстно-вільною граматикою, якими є майже всі мови програмування, створення абстрактного дерева в синтаксичному аналізаторі є тривіальним завданням. Більшість правил в граматиці створюють нову вершину, а символи в правилі стають ребрами. Правила, які нічого не привносять в АСД, такі як правила групування, просто заміняються в вершині одним з своїх символів. Крім того, аналізатор може створити повне дерево розбору і після цього пройтися по ньому, видаляючи вузли і ребра, які не використовуються в абстрактному синтаксисі, щоб створити АСД.
Примітки Редагувати
- . Факультет кібернетики КНУ ім. Тараса Шевченка, Кафедра теорії та технології програмування. 2013. Архів оригіналу за 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.];
- .
| Це незавершена стаття про інформаційні технології. Ви можете допомогти проєкту, виправивши або дописавши її. |