Абстрактное синтаксическое дерево - Abstract syntax tree

О деревьях, используемых в лингвистике, см. Конкретное синтаксическое дерево.
Абстрактное синтаксическое дерево для следующего кода для Евклидов алгоритм:
в то время как b ≠ 0
  если а> б
    а: = а - б
  еще
    б: = б - а
вернуть а

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

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

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

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

Применение в компиляторах

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

Мотивация

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

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

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

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

дизайн

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

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

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

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

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

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

Применение

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

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

Смотрите также

использованная литература

дальнейшее чтение

внешние ссылки