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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

Примітки[ред.ред. код]

Посилання[ред.ред. код]

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