Term graph

Article summary

A term graph is a representation of an expression in a formal language as a generalized graph whose vertices are . Term graphs are a more powerful form of representation than expression trees because they can represent not only common subexpressions (i.e. they can take the structure of a directed acyclic graph) but also cyclic/recursive subexpressions (cyclic digraphs). Abstract syntax trees cannot represent shared subexpressions since each tree node can only have one parent; this simplicity comes at the cost of efficiency due to redundant duplicate computations of identical terms. For this reason term graphs are often used as an intermediate language at a subsequent compilation stage to abstract syntax tree construction via parsing. The phrase "term graph rewriting" is often used when discussing graph rewriting methods for transforming expressions in formal languages. Considered from the point of view of graph grammars, term graphs are not regular graphs, but hypergraphs where an n-ary word will have a particular subgraph in first place, another in second place, and so on, a distinction that does not exist in the usual undirected graphs studied in graph theory. Term graphs are a prominent topic in programming language research since term graph rewriting rules can formally expressing a compiler's operational semantics.…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.