From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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. However, they may contain cycles[clarification needed], particularly in the field of graph rewriting. Graphs that contain cycles may represent recursive expressions which are commonly used to express iteration in functional programming languages without looping constructs.

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 representing shared subexpressions due to their simplistic structure; this simplicity comes at a cost of efficiency due to redundant duplicate computations 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.

See also[edit]


  1. ^ Garner, Richard (2011). "An abstract view on syntax with sharing". Oxford University press. 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.
  2. ^ Plump, D. (1999). Ehrig, Hartmut; Engels, G.; Rozenberg, Grzegorz, eds. Handbook of Graph Grammars and Computing by Graph Transformation: applications, languages and tools. 2. World Scientific. pp. 9–13. ISBN 9789810228842.
  3. ^ 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). 259: 141–158. doi:10.1007/3-540-17945-3_8.

External links[edit]


None of the audio/visual content is hosted on this site. All media is embedded from other sites such as GoogleVideo, Wikipedia, YouTube etc. Therefore, this site has no control over the copyright issues of the streaming media.

All issues concerning copyright violations should be aimed at the sites hosting the material. This site does not host any of the streaming media and the owner has not uploaded any of the material to the video hosting servers. Anyone can find the same content on Google Video or YouTube by themselves.

The owner of this site cannot know which documentaries are in public domain, which has been uploaded to e.g. YouTube by the owner and which has been uploaded without permission. The copyright owner must contact the source if he wants his material off the Internet completely.

Powered by YouTube
Wikipedia content is licensed under the GFDL and (CC) license