Editing Abstract semantic graph (section)

{{semantics}}
In [[computer science]], an '''abstract semantic [[Graph (data structure)|graph]]''' ('''ASG''') or '''term graph''' is a form of [[abstract syntax]] in which an [[expression (computer science)|expression]] of a [[formal language|formal]] or [[programming language]] is represented by a [[Graph (discrete mathematics)|graph]] whose vertices are the expression's [[Term (logic)|subterm]]s. An ASG is at a higher [[abstraction (computer science)|level of abstraction]] than an [[abstract syntax tree]] (or AST), which is used to express the [[syntax|syntactic structure]] of an expression or [[program (computer science)|program]].

ASGs are more complex and concise than ASTs because they may contain shared subterms (also known as "common subexpressions").<ref name=Garner2011>{{cite journal|last=Garner|first=Richard|title=An abstract view on syntax with sharing|journal=Journal of Logic and Computation|volume=22|issue=6|pages=1427–1452|year=2011|doi=10.1093/logcom/exr021|quote=The notion of term graph encodes a refinement of inductively generated syntax in which regard is paid to the sharing and discard of subterms.|arxiv=1009.3682}}</ref> 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 [[tree (computer science)|trees]] and are thus incapable of representing shared terms. ASGs are usually [[directed acyclic graph|directed acyclic graphs (DAG)]], although in some applications graphs containing [[cycle (graph theory)|cycles]]{{clarify|last sentence said acyclic|date=August 2017}} 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 language]]s as non-[[loop (computing)|loop]]ing [[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 [[graph rewriting#Term graph rewriting|term graph rewriting]],<ref name=Plump1999>{{cite book | last = Plump | first = D. | editor1-first = Hartmut | editor1-last = Ehrig| editor1-link=Hartmut Ehrig|editor2-first = G. | editor2-last = Engels| editor3-first = Grzegorz | editor3-last = Rozenberg |title=Handbook of Graph Grammars and Computing by Graph Transformation: applications, languages and tools | volume = 2|year=1999|publisher=World Scientific|isbn=9789810228842|pages=9–13}}</ref> which involves the transformation and processing of expressions by the specification of rewriting rules,<ref name="Barendregt1987">{{Cite conference |last=Barendregt |first=H. P. |last2=Eekelen |first2=M. C. J. D. |last3=Glauert |first3=J. R. W. |last4=Kennaway |first4=J. R. |last5=Plasmeijer |first5=M. J. |last6=Sleep |first6=M. R. |date=1987 |editor-last=Bakker |editor-first=J. W. |editor2-last=Nijman |editor2-first=A. J. |editor3-last=Treleaven |editor3-first=P. C. |title=Term graph rewriting |book-title=PARLE Parallel Architectures and Languages Europe (PARLE 1987) |url=http://link.springer.com/10.1007/3-540-17945-3_8 |series=Lecture Notes in Computer Science |publisher=Springer |volume=259 |pages=141–158 |doi=10.1007/3-540-17945-3_8 |isbn=978-3-540-17945-0}}</ref> whereas ''abstract semantic graph'' is used when discussing [[linguistics]], [[programming languages]], [[type systems]] and [[compiler|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-pointer]]s, [[edge (graph theory)|edges]] from an [[identifier]] node (where a [[Variable (programming)|variable]] is being used) to a node representing the [[declaration (computer science)|declaration]] of that variable. The abstraction can [[logical consequence|entail]] the removal of details which are relevant only in [[parsing]], not for semantics.