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

Поделись знанием:
Перейти к: навигация, поиск

Абстрактное синтаксическое дерево (АСД) — в информатике конечное, помеченное, ориентированное дерево, в котором внутренние вершины сопоставлены (помечены) с операторами языка программирования, а листья — с соответствующими операндами. Таким образом, листья являются пустыми операторами и представляют только переменные и константы.

Синтаксические деревья используются в парсерах для промежуточного представления[en] программы между деревом разбора[en] (конкретным синтаксическим деревом) и структурой данных, которая затем используется в качестве внутреннего представления в компиляторе или интерпретаторе компьютерной программы для оптимизации и генерации кода. Возможные варианты подобных структур описываются абстрактным синтаксисом.





Особенности

Абстрактное синтаксическое дерево отличается от дерева разбора тем, что в нём отсутствуют узлы и рёбра для тех синтаксических правил, которые не влияют на семантику программы. Классическим примером такого отсутствия являются группирующие скобки, так как в АСД группировка операндов явно задаётся структурой дерева.

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

См. также

Напишите отзыв о статье "Абстрактное синтаксическое дерево"

Литература

  • Статья «[doi.acm.org/10.1145/1083142.1083143 Исследование эволюции кода с использованием сравнения абстрактных синтаксических деревьев]» Юлиана Немтью (англ. Iulian Neamtiu), Джеффри Фостера (англ. Jeffrey S. Foster) и Михаэля Хикса (англ. Michael Hicks)
  • Статья «[seal.ifi.uzh.ch/fileadmin/User_Filemount/Publications/fluri-changedistilling.pdf Извлечение изменений: Поиск различий в деревьях для высокоточного определения изменений в исходном коде]» Бита Флури (англ. Beat Fluri), Михаэля Вурщ (англ. Michael Würsch), Мартина Пинцгера (англ. Martin Pinzger) и Гаральда Галла (англ. Harald C. Gall)
  • Дипломная работа Михаэля Вурща (англ. Michael Würsch) «[seal.ifi.unizh.ch/137/ Улучшение распознавания изменений в исходых кодах с помощью абстрактных синтаксических деревьев]»
  • Статья «[blogs.msdn.com/vcblog/archive/2006/08/16/702823.aspx Мысли о абстрактном синтаксическом дереве в Visual C++]» Джейсона Лукаса (англ. Jason Lucas)
  • Учебное пособие «[www.omg.org/news/meetings/workshops/ADM_2005_Proceedings_FINAL/T-3_Newcomb.pdf Стандарт метамодели абстрактных синтаксических деревьев]»

Ссылки

  • [www.eclipse.org/jdt/ui/astview/index.php AST View], плагин для Eclipse показывает абстрактное синтаксическое дерево программ на языке Java;
  • [www.eclipse.org/articles/Article-JavaCodeManipulation_AST/index.html Полезная информация о представлении абстрактных синтаксических деревьев в Eclipse и манипулировании исходным кодом Java];
  • [www.cs.utah.edu/flux/flick/current/doc/guts/gutsch6.html Представление CAST];
  • [eli-project.sourceforge.net/elionline4.4/idem_2.html Abstract Syntax Tree Unparsing] (недоступная ссылка с 13-05-2013 (3972 дня) — история).

Отрывок, характеризующий Абстрактное синтаксическое дерево



В 1808 году император Александр ездил в Эрфурт для нового свидания с императором Наполеоном, и в высшем Петербургском обществе много говорили о величии этого торжественного свидания.
В 1809 году близость двух властелинов мира, как называли Наполеона и Александра, дошла до того, что, когда Наполеон объявил в этом году войну Австрии, то русский корпус выступил за границу для содействия своему прежнему врагу Бонапарте против прежнего союзника, австрийского императора; до того, что в высшем свете говорили о возможности брака между Наполеоном и одной из сестер императора Александра. Но, кроме внешних политических соображений, в это время внимание русского общества с особенной живостью обращено было на внутренние преобразования, которые были производимы в это время во всех частях государственного управления.
Жизнь между тем, настоящая жизнь людей с своими существенными интересами здоровья, болезни, труда, отдыха, с своими интересами мысли, науки, поэзии, музыки, любви, дружбы, ненависти, страстей, шла как и всегда независимо и вне политической близости или вражды с Наполеоном Бонапарте, и вне всех возможных преобразований.
Князь Андрей безвыездно прожил два года в деревне. Все те предприятия по именьям, которые затеял у себя Пьер и не довел ни до какого результата, беспрестанно переходя от одного дела к другому, все эти предприятия, без выказыванья их кому бы то ни было и без заметного труда, были исполнены князем Андреем.
Он имел в высшей степени ту недостававшую Пьеру практическую цепкость, которая без размахов и усилий с его стороны давала движение делу.
Одно именье его в триста душ крестьян было перечислено в вольные хлебопашцы (это был один из первых примеров в России), в других барщина заменена оброком. В Богучарово была выписана на его счет ученая бабка для помощи родильницам, и священник за жалованье обучал детей крестьянских и дворовых грамоте.
Одну половину времени князь Андрей проводил в Лысых Горах с отцом и сыном, который был еще у нянек; другую половину времени в богучаровской обители, как называл отец его деревню. Несмотря на выказанное им Пьеру равнодушие ко всем внешним событиям мира, он усердно следил за ними, получал много книг, и к удивлению своему замечал, когда к нему или к отцу его приезжали люди свежие из Петербурга, из самого водоворота жизни, что эти люди, в знании всего совершающегося во внешней и внутренней политике, далеко отстали от него, сидящего безвыездно в деревне.
Кроме занятий по именьям, кроме общих занятий чтением самых разнообразных книг, князь Андрей занимался в это время критическим разбором наших двух последних несчастных кампаний и составлением проекта об изменении наших военных уставов и постановлений.
Весною 1809 года, князь Андрей поехал в рязанские именья своего сына, которого он был опекуном.
Пригреваемый весенним солнцем, он сидел в коляске, поглядывая на первую траву, первые листья березы и первые клубы белых весенних облаков, разбегавшихся по яркой синеве неба. Он ни о чем не думал, а весело и бессмысленно смотрел по сторонам.
Проехали перевоз, на котором он год тому назад говорил с Пьером. Проехали грязную деревню, гумны, зеленя, спуск, с оставшимся снегом у моста, подъём по размытой глине, полосы жнивья и зеленеющего кое где кустарника и въехали в березовый лес по обеим сторонам дороги. В лесу было почти жарко, ветру не слышно было. Береза вся обсеянная зелеными клейкими листьями, не шевелилась и из под прошлогодних листьев, поднимая их, вылезала зеленея первая трава и лиловые цветы. Рассыпанные кое где по березнику мелкие ели своей грубой вечной зеленью неприятно напоминали о зиме. Лошади зафыркали, въехав в лес и виднее запотели.