График сроков
 | Эта статья нуждается в дополнительных цитатах для проверки . ( июнь 2022 г. ) |
Граф термов — это представление выражения на формальном языке в виде обобщенного графа, вершинами которого являются термы. [ объяснить ] . [1] Графы термов являются более мощной формой представления, чем деревья выражений, поскольку они могут представлять не только общие подвыражения (т. е. они могут принимать структуру ориентированного ациклического графа), но также циклические/рекурсивные подвыражения (циклические орграфы).
Деревья абстрактного синтаксиса не могут представлять общие подвыражения, поскольку каждый узел дерева может иметь только одного родителя; эта простота достигается за счет эффективности из-за избыточных дублирующих вычислений идентичных терминов. По этой причине графы терминов часто используются в качестве промежуточного языка на последующем этапе компиляции для абстрактного построения синтаксического дерева посредством синтаксического анализа.
Фраза « переписывание графов термина » часто используется при обсуждении методов переписывания графов для преобразования выражений в формальных языках. [2] С точки зрения грамматик графов, графы терминов — это не обычные графы, а гиперграфы, в которых n-арное слово будет иметь определенный подграф на первом месте, другой на втором месте и т. д. Это различие не существует в обычные неориентированные графы, изучаемые в теории графов.
компилятора Графы термов — важная тема в исследованиях языков программирования, поскольку правила переписывания графов термов могут формально выражать операционную семантику . Графы термов также используются в качестве абстрактных машин, способных моделировать химические и биологические вычисления, а также графические вычисления, такие как модели параллелизма. Графы термов могут выполнять автоматическую проверку и логическое программирование, поскольку они хорошо подходят для представления количественных утверждений в логике первого порядка. Программное обеспечение для символьного программирования — это еще одно приложение для графов термов, которые способны представлять и выполнять вычисления с помощью абстрактных алгебраических структур, таких как группы, поля и кольца.
Конференция ТЕРМГРАФ [3] полностью сосредоточен на исследованиях в области переписывания графов терминов и его приложений.
Графы терминов также используются при выводе типов, где структура графа помогает реализовать унификацию типов. [4]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Пламп Д. (Хартмут Эриг, Г. Энгельс, Гжегож Розенберг, ред.) (1999). Справочник по грамматикам графов и вычислениям путем преобразования графов: приложения, языки и инструменты. Том. 2 . Всемирная научная. стр. 9–13. ISBN 9789810228842 .
{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Барендрегт; ван Экелен; Глауэрт; Кеннауэй; Пласмейер; Сон (1987). «Переписывание графа термов». PARLE Параллельные архитектуры и языки Европы (Конспект лекций по информатике) . Конспекты лекций по информатике. 259 : 141–158. дои : 10.1007/3-540-17945-3_8 . ISBN 978-3-540-17945-0 .
- ^ «ТЕРМГРАФ 2013» .
- ^ Фриц Хенглейн (1988). Вывод типов и полуунификация . В Proc. Конференция ACM 1988 года по LISP и функциональному программированию, стр. 184–197. дои : 10.1145/62678.62701
 | Эта формальным методам, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее . |