In computer science, an abstract semantic graph (ASG) or term graph is a form of abstract syntax in which an expression of a formal or programming language is represented by a graph whose vertices are the expression's subterms. An ASG is at a higher level of abstraction than an abstract syntax tree (or AST), which is used to express the syntactic structure of an expression or program.
ASGs are more complex and concise than ASTs because they may contain shared subterms (also known as "common subexpressions").[1] Abstract semantic graphs are often used as an intermediate representation by compilers to store the results of performing common subexpression elimination upon abstract syntax trees. ASTs are trees and are thus incapable of representing shared terms. ASGs are usually directed acyclic graphs (DAG), although in some applications graphs containing cycles[clarification needed] may be permitted. For example, a graph containing a cycle might be used to represent the recursive expressions that are commonly used in functional programming languages as non-looping iteration constructs. The mutability of these types of graphs, is studied in the field of graph rewriting.
The nomenclature term graph is associated with the field of term graph rewriting,[2] which involves the transformation and processing of expressions by the specification of rewriting rules,[3] whereas abstract semantic graph is used when discussing linguistics, programming languages, type systems and compilation.
Abstract syntax trees are not capable of sharing subexpression nodes because it is not possible for a node in a proper tree to have more than one parent. Although this conceptual simplicity is appealing, it may come at the cost of redundant representation and, in turn, possibly inefficiently duplicating the computation of identical terms. For this reason ASGs are often used as an intermediate language at a subsequent compilation stage to abstract syntax tree construction via parsing.
An abstract semantic graph is typically constructed from an abstract syntax tree by a process of enrichment and abstraction. The enrichment can for example be the addition of back-pointers, edges from an identifier node (where a variable is being used) to a node representing the declaration of that variable. The abstraction can entail the removal of details which are relevant only in parsing, not for semantics.
^Garner, Richard (2011). "An abstract view on syntax with sharing". Journal of Logic and Computation. 22 (6): 1427–1452. arXiv:1009.3682. doi:10.1093/logcom/exr021. The notion of term graph encodes a refinement of inductively generated syntax in which regard is paid to the sharing and discard of subterms.
^Plump, D. (1999). Ehrig, Hartmut; Engels, G.; Rozenberg, Grzegorz (eds.). Handbook of Graph Grammars and Computing by Graph Transformation: applications, languages and tools. Vol. 2. World Scientific. pp. 9–13. ISBN 9789810228842.
^Barendregt, H. P.; van Eekelen, M. C. J. D.; Glauert, J. R. W.; Kennaway, J. R.; Plasmeijer, M. J.; Sleep, M. R. (1987). "Term graph rewriting". PARLE Parallel Architectures and Languages Europe. Lecture Notes in Computer Science. Vol. 259. pp. 141–158. doi:10.1007/3-540-17945-3_8. ISBN 978-3-540-17945-0. {{cite book}}: |journal= ignored (help)
and 26 Related for: Abstract semantic graph information
In computer science, an abstractsemanticgraph (ASG) or term graph is a form of abstract syntax in which an expression of a formal or programming language...
is a directed or undirected graph consisting of vertices, which represent concepts, and edges, which represent semantic relations between concepts, mapping...
situations or abstract concepts – while also encoding the semantics or relationships underlying these entities. Since the development of the Semantic Web, knowledge...
Semantic matching is a technique used in computer science to identify information which is semantically related. Given any two graph-like structures, e...
Semantic Scholar also exploits graph structures, which include the Microsoft Academic Knowledge Graph, Springer Nature's SciGraph, and the Semantic Scholar...
A semantic wiki is a wiki that has an underlying model of the knowledge described in its pages. Regular, or syntactic, wikis have structured text and untyped...
rdf:about="https://example.org/semantic-web/">Semantic Web</item> Tim Berners-Lee calls the resulting network of Linked Data the Giant Global Graph, in contrast to the...
Latent semantic analysis (LSA) is a technique in natural language processing, in particular distributional semantics, of analyzing relationships between...
Semantic discord is the situation where two parties disagree on the definition of a word(s) that is essential to communicating or formulating the concept(s)...
Semantic memory refers to general world knowledge that humans have accumulated throughout their lives. This general knowledge (word meanings, concepts...
forth by Leonard Talmy, George Lakoff and Dirk Geeraerts. Some cognitive semantic frameworks, such as that developed by Talmy, take into account syntactic...
of lexicology. Since lexicology studies the meaning of words and their semantic relations, it often explores the history and development of a word. Etymologists...
or transformation of term graphs (also known as abstractsemanticgraphs) by a set of syntactic rewrite rules. Term graphs are a prominent topic in programming...
Compositionality below. Full completeness or definability: Every morphism of the semantic model should be the denotation of a program. An important aspect of denotational...
"telephone" are abstractions, they are not abstract in the sense of the objects in graph 1 below. We might look at other graphs, in a progression from cat to mammal...
island of La Gomera in the Canary Islands Abstractsemanticgraph, in computer science, a form of abstract syntax Australian Standard Garratt, a World...
aardvark") is misleading, as it does not correlate their logical and/or semantic architecture. While descriptions may seem like fairly uncontroversial phrases...
A graph database (GDB) is a database that uses graph structures for semantic queries with nodes, edges, and properties to represent and store data. A key...
terms of Gestalt and semantic features. Basic level categories tend to have the same parts and recognizable images. Clearly semantic models based on attribute-value...