Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Абстрактное синтаксическое дерево для следующего кода алгоритма Евклида :
в то время как b ≠ 0, 
если a> b
a: = a - b
иначе
b: = b - a
return a

В информатике , абстрактное синтаксическое дерево ( AST ), или просто синтаксическое дерево , это дерево представление абстрактной синтаксической структуры исходного кода , написанного на языке программирования . Каждый узел дерева обозначает конструкцию, встречающуюся в исходном коде.

Синтаксис является «абстрактным» в том смысле, что он представляет не все детали, встречающиеся в реальном синтаксисе, а скорее только структурные или связанные с содержанием детали. Например, группирующие скобки неявно присутствуют в древовидной структуре, поэтому их не нужно представлять как отдельные узлы. Точно так же синтаксическая конструкция, такая как выражение «если-условие-то», может быть обозначена посредством единственного узла с тремя ветвями.

Это отличает абстрактные синтаксические деревья от конкретных синтаксических деревьев, традиционно называемых деревьями синтаксического анализа . Деревья синтаксического анализа обычно строятся синтаксическим анализатором в процессе преобразования и компиляции исходного кода . После создания дополнительная информация добавляется к AST посредством последующей обработки, например, контекстного анализа .

Абстрактные синтаксис дерева также используются в анализе программ и трансформация программ систем.

Приложение в компиляторах [ править ]

Абстрактные синтаксические деревья - это структуры данных, широко используемые в компиляторах для представления структуры программного кода. AST обычно является результатом фазы синтаксического анализа компилятора. Он часто служит промежуточным представлением программы через несколько этапов, которые требуются компилятору, и оказывает сильное влияние на конечный результат компилятора.

Мотивация [ править ]

AST имеет несколько свойств, которые помогают на дальнейших этапах процесса компиляции:

  • AST можно редактировать и дополнять такой информацией, как свойства и аннотации для каждого содержащегося в нем элемента. Такое редактирование и аннотирование невозможно с исходным кодом программы, так как это повлечет за собой его изменение.
  • По сравнению с исходным кодом AST не включает несущественные знаки препинания и разделители (фигурные скобки, точки с запятой, круглые скобки и т. Д.).
  • AST обычно содержит дополнительную информацию о программе из-за последовательных этапов анализа компилятором. Например, он может сохранять позицию каждого элемента в исходном коде, позволяя компилятору печатать полезные сообщения об ошибках.

AST необходимы из-за неотъемлемой природы языков программирования и их документации. Языки часто неоднозначны по своей природе. Чтобы избежать этой двусмысленности, языки программирования часто указываются как контекстно-свободная грамматика (CFG). Однако часто есть аспекты языков программирования, которые CFG не могут выразить, но являются частью языка и задокументированы в его спецификации. Это детали, требующие контекста для определения их достоверности и поведения. Например, если язык позволяет объявлять новые типы, CFG не может предсказать имена таких типов или способ их использования. Даже если у языка есть предопределенный набор типов, для обеспечения правильного использования обычно требуется некоторый контекст. Другой пример - утиная печать., где тип элемента может меняться в зависимости от контекста. Перегрузка оператора - это еще один случай, когда правильное использование и конечная функция определяются в зависимости от контекста. Java представляет собой отличный пример, в котором оператор «+» является одновременно числовым сложением и объединением строк.

Хотя во внутренней работе компилятора задействованы и другие структуры данных , AST выполняет уникальную функцию. На первом этапе, этапе синтаксического анализа , компилятор создает дерево синтаксического анализа. Это дерево синтаксического анализа можно использовать для выполнения почти всех функций компилятора посредством синтаксически-управляемой трансляции. Хотя этот метод может привести к более эффективному компилятору, он идет вразрез с принципами разработки и поддержки программ [ необходима цитата ] . Еще одно преимущество AST перед деревом синтаксического анализа - это размер, особенно меньшая высота AST и меньшее количество элементов.

Дизайн [ править ]

Дизайн AST часто тесно связан с дизайном компилятора и его ожидаемыми функциями.

Основные требования включают следующее:

  • Типы переменных должны быть сохранены, а также расположение каждого объявления в исходном коде.
  • Порядок исполняемых операторов должен быть явно представлен и четко определен.
  • Левая и правая компоненты бинарных операций должны быть сохранены и правильно идентифицированы.
  • Идентификаторы и их присвоенные значения должны храниться для операторов присваивания.

Эти требования можно использовать для разработки структуры данных для AST.

Для некоторых операций всегда требуются два элемента, например, два члена для сложения. Однако некоторые языковые конструкции требуют произвольно большого количества дочерних элементов, например списков аргументов, передаваемых программам из командной оболочки . В результате AST, используемый для представления кода, написанного на таком языке, также должен быть достаточно гибким, чтобы можно было быстро добавлять неизвестное количество дочерних элементов.

Для поддержки проверки компилятора должна быть возможность преобразовать AST в форму исходного кода. Созданный исходный код должен быть достаточно похож на оригинал по внешнему виду и идентичным по исполнению после перекомпиляции.

Использование [ править ]

AST интенсивно используется во время семантического анализа , когда компилятор проверяет правильность использования элементов программы и языка. Компилятор также генерирует таблицы символов на основе AST во время семантического анализа. Полный обход дерева позволяет проверить правильность программы.

После проверки правильности AST служит базой для генерации кода. AST часто используется для генерации промежуточного представления (IR), иногда называемого промежуточным языком , для генерации кода.

См. Также [ править ]

  • Абстрактный семантический граф (ASG), также называемый графом терминов
  • Составной узор
  • График потока управления
  • Направленный ациклический граф (DAG)
  • Объектная модель документа (DOM)
  • Дерево выражений
  • Расширенная форма Бэкуса – Наура
  • Лисп , семейство языков, написанных на деревьях, с макросами для управления деревьями кода
  • Дерево синтаксического анализа , также известное как конкретное дерево синтаксиса
  • Дерево семантического разрешения (SRT)
  • Алгоритм маневрового двора
  • Таблица символов
  • TreeDL

Ссылки [ править ]

  • Эта статья основана на материалах, взятых из Free On-line Dictionary of Computing до 1 ноября 2008 г. и включенных в соответствии с условиями «перелицензирования» GFDL версии 1.3 или новее.

Дальнейшее чтение [ править ]

  • Джонс, Джоэл. «Идиомы реализации абстрактного синтаксического дерева» (PDF) . Цитировать журнал требует |journal=( помощь ) (обзор реализации AST в различных языковых семьях)
  • Нямтиу, Юлиан; Фостер, Джеффри С .; Хикс, Майкл (17 мая 2005 г.). Понимание эволюции исходного кода с использованием сопоставления абстрактного синтаксического дерева . MSR'05. Сент-Луис, Миссури: ACM. CiteSeerX  10.1.1.88.5815 .
  • Baxter, Ira D .; Яхин, Андрей; Моура, Леонардо; Сант Анна, Марсело; Бир, Лотарингия (16–19 ноября 1998 г.). Обнаружение клонов с использованием абстрактных синтаксических деревьев (PDF) . Материалы ICSM'98 . Бетесда, Мэриленд: IEEE .
  • Fluri, Beat; Вюрш, Михаэль; Пинцгер, Мартин; Галл, Харальд К. «Преобразование изменений: дифференциация деревьев для детального извлечения изменений в исходном коде» (PDF) . Цитировать журнал требует |journal=( помощь )( прямая ссылка на PDF )
  • Вюрш, Михаэль. Улучшение обнаружения изменений исходного кода на основе абстрактного синтаксического дерева (дипломная работа).
  • Фаллери, Жан-Реми; Морандат, Флореаль; Блан, Ксавье; Мартинес, Матиас; Монперрус, Мартин. Детализированное и точное различие исходного кода (PDF) . Материалы ASE 2014 . DOI : 10.1145 / 2642937.2642982 .
  • Лукас, Джейсон. «Мысли о абстрактном синтаксическом дереве Visual C ++ (AST)» .

Внешние ссылки [ править ]

  • AST View : Eclipse , плагин для визуализации в Java абстрактного синтаксического дерева
  • «Абстрактное синтаксическое дерево и манипуляции с кодом Java в Eclipse IDE» . eclipse.org .
  • «Представительство CAST» . cs.utah.edu .
  • eli project : Разбор абстрактного синтаксического дерева
  • «Стандарт метамодели абстрактного синтаксического дерева» (PDF) .
  • «Архитектурно-ориентированная модернизация - ADM: метамоделирование абстрактного синтаксического дерева - ASTM» .( Стандарт OMG ).
  • JavaParser : библиотека JavaParser предоставляет вам абстрактное синтаксическое дерево вашего Java-кода. Затем структура AST позволяет вам работать с вашим Java-кодом простым программным способом.
  • Spoon : библиотека для анализа, преобразования, перезаписи и транспиляции исходного кода Java. Он анализирует исходные файлы для создания хорошо спроектированного AST с мощным API анализа и преобразования.