В информатике , абстрактный семантический граф ( ASG ) или термин граф является формой абстрактного синтаксиса , в котором выражение из формального или языка программирования представлено графом , вершины которого являются выражение в подтермах . ASG находится на более высоком уровне абстракции, чем абстрактное синтаксическое дерево (или AST), которое используется для выражения синтаксической структуры выражения или программы .
ASG более сложны и кратки, чем AST, поскольку они могут содержать общие подтермы (также известные как «общие подвыражения»). [1] Абстрактные семантические графы часто используются в качестве промежуточного представления с помощью трансляторов для хранения результатов выполнения общего устранения подвыражением на абстрактных синтаксических деревьев . AST - это деревья , поэтому они не могут представлять общие термины. ASG обычно представляют собой ориентированные ациклические графы (DAG) , хотя в некоторых приложениях могут быть разрешены графы, содержащие циклы [ требуется пояснение ] . Например, граф, содержащий цикл, может использоваться для представления рекурсивных выражений, которые обычно используются в языках функционального программирования, как нециклические конструкции итерации . Изменчивость этих типов графов изучается в области перезаписи графов .
Номенклатура Термин график связан с полем термина графа перезаписи , [2] , который включает в себя преобразование и обработку выражений в спецификации правил перезаписи, [3] , тогда как абстрактный семантического граф используется при обсуждении лингвистики , языках программирования , систем типов и компиляция .
Деревья абстрактного синтаксиса не могут совместно использовать узлы подвыражения, потому что узел в правильном дереве не может иметь более одного родителя. Хотя эта концептуальная простота привлекательна, она может происходить за счет избыточного представления и, в свою очередь, возможно неэффективного дублирования вычисления идентичных членов. По этой причине ASG часто используются в качестве промежуточного языка на последующем этапе компиляции для построения абстрактного синтаксического дерева посредством синтаксического анализа.
Абстрактный семантический граф обычно строится из абстрактного синтаксического дерева в процессе обогащения и абстракции. Обогащение может, например, быть добавлением обратных указателей , ребер от узла идентификатора (где используется переменная ) к узлу, представляющему объявление этой переменной. Абстракция может повлечь за собой удаление деталей, которые важны только для синтаксического анализа , а не для семантики.
Пример: рефакторинг кода
Например, рассмотрим случай рефакторинга кода . Чтобы представить реализацию функции, которая принимает входной аргумент, полученному параметру обычно дается произвольное, отличное имя в исходном коде, чтобы на него можно было ссылаться. Абстрактное представление этой концептуальной сущности, экземпляр «аргумента функции», вероятно, будет упомянуто в сигнатуре функции, а также один или несколько раз в теле кода реализации. Поскольку функция в целом является родительским элементом как для своего заголовка, так и для «сигнатуры», а также для тела реализации, AST не сможет использовать один и тот же узел для совместной идентификации множественного использования или появления объекта аргумента. Это решается DAG-природой ASG. Ключевым преимуществом наличия единого, отличного идентификатора узла для любого заданного элемента кода является то, что свойства каждого элемента по определению сохраняются уникальным образом. Это упрощает операции рефакторинга, потому что существует ровно одна экзистенциальная связь для каждого конкретного экземпляра свойства. Если разработчик решает изменить значение свойства, такое как «имя» любого элемента кода («аргумент функции» в этом примере), ASG по своей сути предоставляет это значение ровно в одном месте, и из этого следует, что любые такие изменения свойства являются неявно, тривиально и сразу же распространяется по всему миру.
Смотрите также
Рекомендации
- ^ Гарнер, Ричард (2011). «Абстрактный взгляд на синтаксис с совместным использованием». Журнал логики и вычислений . 22 (6): 1427–1452. arXiv : 1009,3682 . DOI : 10,1093 / logcom / exr021 .
Понятие графа терминов кодирует уточнение индуктивно генерируемого синтаксиса, в котором уделяется внимание совместному использованию и отбрасыванию подтермов.
- ^ Пухлый, Д. (1999). Эриг, Хартмут ; Энгельс, Г .; Розенберг, Гжегож (ред.). Справочник по грамматикам графов и вычислениям с помощью преобразования графов: приложения, языки и инструменты . 2 . World Scientific. С. 9–13. ISBN 9789810228842.
- ^ Барендрегт, HP; ван Экелен, MCJD; Glauert, JRW; Kennaway, JR; Plasmeijer, MJ; Сон, MR (1987). Переписывание срочного графа . PARLE Параллельные архитектуры и языки в Европе (Конспект лекций по информатике) . Конспект лекций по информатике. 259 . С. 141–158. DOI : 10.1007 / 3-540-17945-3_8 . ISBN 978-3-540-17945-0.
Внешние ссылки
- Дин, Том . "CPPX - C / C ++ Fact Extractor" . CS1 maint: обескураженный параметр ( ссылка )
- Деванбу, Премкумар Т .; Розенблюм, Дэвид С .; Вольф, Александр Л. "Создание инструментов тестирования и анализа с помощью Aria" . Цитировать журнал требует
|journal=
( помощь )CS1 maint: обескураженный параметр ( ссылка ) - Мамас, Эван ; Контогианнис, Костас . «На пути к переносимым представлениям исходного кода с использованием XML». CiteSeerX 10.1.1.88.6173 . Цитировать журнал требует
|journal=
( помощь )CS1 maint: обескураженный параметр ( ссылка ) - Рагхаван, Шрути; Рохана, Розанна; Леон, Дэвид; Подгурски, Энди; Августин, Вине (2004). Dex: инструмент различения семантических графов для изучения изменений в больших базах кода . Международная конференция IEEE по обслуживанию программного обеспечения. С. 188–197. DOI : 10.1109 / icsm.2004.1357803 . Архивировано из оригинала на 2008-01-17 . Проверено 1 мая 2007 .