Абстрактный семантический граф
| Семантика | ||||||||
|---|---|---|---|---|---|---|---|---|
| ||||||||
| Семантика языки программирования | ||||||||
| ||||||||
В информатике абстрактный семантический граф ( ASG ) или граф терминов — это форма абстрактного синтаксиса , в которой выражение формального вершины языка или языка программирования представлено графом , выражения которого являются подтермами . ASG находится на более высоком уровне абстракции, чем абстрактное синтаксическое дерево (или AST), которое используется для выражения синтаксической структуры выражения или программы .
ASG более сложны и кратки, чем AST, поскольку они могут содержать общие подтермины (также известные как «общие подвыражения»). [1] Абстрактные семантические графы часто используются компиляторами в качестве представления промежуточного для хранения результатов выполнения исключения общих подвыражений в абстрактных синтаксических деревьях . AST представляют собой деревья и поэтому не способны представлять общие термины. ASG обычно представляют собой направленные ациклические графы (DAG) , хотя в некоторых приложениях графы содержат циклы. [ нужны разъяснения ] может быть разрешено. Например, граф, содержащий цикл, может использоваться для представления рекурсивных выражений, которые обычно используются в языках функционального программирования в качестве конструкций без цикла итерационных . Изменяемость этих типов графов изучается в области переписывания графов .
номенклатурных Граф терминов связан с областью переписывания графов терминов , [2] который предполагает преобразование и обработку выражений путем указания правил переписывания, [3] тогда как абстрактный семантический граф используется при обсуждении лингвистики , языков программирования , систем типов и компиляции .
Деревья абстрактного синтаксиса не могут совместно использовать узлы подвыражений, поскольку узел в правильном дереве не может иметь более одного родительского узла. Хотя эта концептуальная простота привлекательна, она может достигаться за счет избыточного представления и, в свою очередь, возможного неэффективного дублирования вычислений идентичных терминов. По этой причине ASG часто используются в качестве промежуточного языка на последующем этапе компиляции для абстрактного построения синтаксического дерева посредством синтаксического анализа.
Абстрактный семантический граф обычно создается из абстрактного синтаксического дерева посредством процесса обогащения и абстракции. Обогащением может быть, например, добавление обратных указателей , ребер от узла идентификатора (где переменная используется ) к узлу, представляющему объявление этой переменной. Абстракция может повлечь за собой удаление деталей, которые важны только для синтаксического анализа , а не для семантики.
Пример: Рефакторинг кода [ править ]
Например, рассмотрим случай рефакторинга кода . Чтобы представить реализацию функции, которая принимает входной аргумент, полученному параметру обычно присваивается произвольное отдельное имя в исходном коде, чтобы на него можно было ссылаться. Абстрактное представление этой концептуальной сущности, экземпляр «аргумента функции», скорее всего, будет упомянуто в сигнатуре функции, а также один или несколько раз в теле кода реализации. Поскольку функция в целом является родительской как для ее заголовка или информации «подписи», так и для ее тела реализации, AST не сможет использовать один и тот же узел для совместной идентификации многократного использования или появления объекта аргумента. Это решается за счет DAG-природы ASG. Ключевое преимущество наличия единого, отличного идентификатора узла для любого данного элемента кода заключается в том, что свойства каждого элемента по определению сохраняются уникально. Это упрощает операции рефакторинга, поскольку для каждого конкретного экземпляра свойства существует ровно одна экзистенциальная связь. Если разработчик решает изменить значение свойства, такое как «имя» любого элемента кода («аргумент функции» в этом примере), ASG по своей сути предоставляет это значение ровно в одном месте, и из этого следует, что любые такие изменения свойства неявно, тривиально и немедленно распространяется по всему миру.
См. также [ править ]
Ссылки [ править ]
- ^ Гарнер, Ричард (2011). «Абстрактный взгляд на синтаксис с возможностью совместного использования». Журнал логики и вычислений . 22 (6): 1427–1452. arXiv : 1009.3682 . дои : 10.1093/logcom/exr021 .
Понятие графа терминов кодирует усовершенствование индуктивно генерируемого синтаксиса, в котором уделяется внимание совместному использованию и исключению подтерминов.
- ^ Пламп, Д. (1999). Эриг, Хартмут ; Энгельс, Г.; Розенберг, Гжегож (ред.). Справочник по грамматикам графов и вычислениям путем преобразования графов: приложения, языки и инструменты . Том. 2. Мировая научная. стр. 9–13. ISBN 9789810228842 .
- ^ Барендрегт, HP; ван Экелен, MCJD; Глауэрт, JRW; Кеннауэй-младший; Пласмейер, MJ; Спи, МР (1987). «Переписывание графа терминов». PARLE Параллельные архитектуры и языки Европы . Конспекты лекций по информатике. Том. 259. стр. 141–158. дои : 10.1007/3-540-17945-3_8 . ISBN 978-3-540-17945-0 .
{{cite book}}:|journal=игнорируется ( помогите )
Внешние ссылки [ править ]
- Дин, Том . «CPPX — экстрактор фактов C/C++» .
- Деванбу, Премкумар Т .; Розенблюм, Дэвид С .; Вольф, Александр Л. «Создание инструментов тестирования и анализа с помощью Aria» .
- Мамас, Эван ; Контояннис, Костас (2000). На пути к переносимому представлению исходного кода с использованием XML . Седьмая рабочая конференция по обратному проектированию. стр. 172–182. CiteSeerX 10.1.1.88.6173 .
- Рагхаван, Шрути; Рохана, Розанна; Леон, Дэвид; Подгурски, Энди; Августин, Виней (2004). «Dex: инструмент дифференцирования семантических графов для изучения изменений в больших базах кода» . 20-я Международная конференция IEEE по сопровождению программного обеспечения, 2004 г. Материалы . Международная конференция IEEE по сопровождению программного обеспечения. стр. 188–197. CiteSeerX 10.1.1.228.9292 . дои : 10.1109/icsm.2004.1357803 . ISBN 0-7695-2213-0 . Архивировано из оригинала 17 января 2008 г. Проверено 1 мая 2007 г.
 | Эта формальным методам, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее . |