Abstract semantic graph
| Semantics | ||||||||
|---|---|---|---|---|---|---|---|---|
| ||||||||
|
||||||||
|
Semantics of programming languages | ||||||||
|
||||||||
In
ASGs are more complex and concise than ASTs because they may contain shared subterms (also known as "common subexpressions").
The nomenclature term graph is associated with the field of
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
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
Example: Code Refactoring
For example, consider the case of code refactoring. To represent the implementation of a function that takes an input argument, the received parameter is conventionally given an arbitrary, distinct name in the source code so that it can be referenced. The abstract representation of this conceptual entity, a "function argument" instance, will likely be mentioned in the function signature, and also one or more times within the implementation code body. Since the function as a whole is the parent of both its header or "signature" information as well as its implementation body, an AST would not be able to use the same node to co-identify the multiple uses or appearances of the argument entity. This is solved by the DAG nature of an ASG. A key advantage of having a single, distinct node identity for any given code element is that each element's properties are, by definition, uniquely stored. This simplifies refactoring operations, because there is exactly one existential nexus for any given property instantiation. If the developer decides to change a property value such as the "name" of any code element (the "function argument" in this example), the ASG inherently exposes that value in exactly one place, and it follows that any such property changes are implicitly, trivially, and immediately propagated globally.
See also
- Abstract syntax tree
- Ontology (computer science)
- Semantic Web
- Semantic Grid
References
- .
The notion of term graph encodes a refinement of inductively generated syntax in which regard is paid to the sharing and discard of subterms.
- ISBN 9789810228842.
- )
External links
- Dean, Tom. "CPPX — C/C++ Fact Extractor".
- Devanbu, Premkumar T.; Rosenblum, David S.; Wolf, Alexander L. "Generating Testing and Analysis Tools with Aria".
- CiteSeerX 10.1.1.88.6173.
- Raghavan, Shruti; Rohana, Rosanne; Leon, David; Podgurski, Andy; Augustine, Vinay (2004). "Dex: a semantic-graph differencing tool for studying changes in large code bases". 20th IEEE International Conference on Software Maintenance, 2004. Proceedings. IEEE International Conference on Software Maintenance. pp. 188–197. ISBN 0-7695-2213-0. Archived from the originalon 2008-01-17. Retrieved 2007-05-01.
 | This formal methods-related article is a stub. You can help Wikipedia by expanding it. |