Абстрактный семантический граф - Abstract semantic graph

Семантика
Вычисление
Типы
Теория
Анализ
Приложения

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

ASG более сложны и кратки, чем AST, поскольку они могут содержать общие подтермы (также известные как «общие подвыражения»).[1] Абстрактные семантические графы часто используются как промежуточное представление к компиляторы хранить результаты исполнения исключение общего подвыражения на абстрактные синтаксические деревья. AST деревья и поэтому не могут представлять общие термины. ПГС обычно ориентированные ациклические графы (DAG), хотя в некоторых приложениях графики, содержащие циклы[требуется разъяснение ] может быть разрешено. Например, график, содержащий цикл, может использоваться для представления рекурсивный выражения, которые обычно используются в функциональные языки программирования как незацикливание итерация конструкции. Изменчивость этих типов графов изучается в области переписывание графа.

Номенклатура график терминов связано с полем переписывание графа терминов,[2] который включает преобразование и обработку выражений по спецификации правил перезаписи,[3] в то время как абстрактный семантический граф используется при обсуждении лингвистика, языки программирования, системы типов и сборник.

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

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

Пример: рефакторинг кода

Например, рассмотрим случай рефакторинг кода. Чтобы представить реализацию функции, которая принимает входной аргумент, принятому параметру обычно дается произвольный, отдельный имя в исходном коде, чтобы на него можно было ссылаться. Абстрактное представление этой концептуальной сущности, экземпляр «аргумента функции», вероятно, будет упомянуто в сигнатуре функции, а также один или несколько раз в теле кода реализации. Поскольку функция в целом является родительским элементом как для своего заголовка, так и для информации «сигнатуры», а также для тела реализации, AST не сможет использовать один и тот же узел для совместной идентификации множественного использования или появления объекта аргумента. Это решается DAG-природой ASG. Ключевым преимуществом наличия единственного, отличного идентификатора узла для любого заданного элемента кода является то, что свойства каждого элемента по определению сохраняются уникальным образом. Это упрощает операции рефакторинга, потому что существует ровно одна экзистенциальная связь для каждого конкретного экземпляра свойства. Если разработчик решает изменить значение свойства, такое как «имя» любого элемента кода («аргумент функции» в этом примере), ASG по своей сути предоставляет это значение ровно в одном месте, и из этого следует, что любые такие изменения свойств являются неявно, тривиально и немедленно распространяются глобально.

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

Рекомендации

  1. ^ Гарнер, Ричард (2011). «Абстрактный взгляд на синтаксис с совместным использованием». Журнал логики и вычислений. 22 (6): 1427–1452. arXiv:1009.3682. Дои:10.1093 / logcom / exr021. Понятие графа терминов кодирует уточнение индуктивно генерируемого синтаксиса, в котором уделяется внимание совместному использованию и отбрасыванию подтермов.
  2. ^ Пухлый, Д. (1999). Эриг, Хартмут; Энгельс, Г .; Розенберг, Гжегож (ред.). Справочник по грамматикам графов и вычислениям с помощью преобразования графов: приложения, языки и инструменты. 2. World Scientific. С. 9–13. ISBN  9789810228842.
  3. ^ Barendregt, H.P .; van Eekelen, M.C.J.D .; Glauert, J.R.W .; Kennaway, J. R .; Plasmeijer, M. J .; Сон, М. Р. (1987). Переписывание срочного графа. PARLE Parallel Architectures and Languages ​​Europe (Конспект лекций по информатике). Конспект лекций по информатике. 259. С. 141–158. Дои:10.1007/3-540-17945-3_8. ISBN  978-3-540-17945-0.

внешняя ссылка