CODEWITHSUNDEEP
algorithmabstract-syntax-treedirected-acyclic-graphsunification
jack malkovick
jack malkovick

Reputation: 533

Algorithm to transform from an expression to a graph (DAG) representation

I was reading about unification algorithms and the efficient ones seem to have as input a DAG, where my understanding was that terms that are shared in an expression are not duplicated nodes (as in an AST).

I'm sure there are well known algorithms that convert an expression from a "string representation" or AST to a DAG. Do such algorithms exist? I just want to avoid reinventing the wheel.

Upvotes: 0

Views: 1182

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59323

This is easily accomplished with memoization while constructing an AST.

As the AST gets built in postorder, when creating each node, check the memoization cache to see if an equivalent node is already present. If so, use the preexisting node. Otherwise use the new node and add it to the cache.

When checking the cache for a preexisting node, the children of that node will already have been memoized, so you can compare them by identity rather than reexamining their subgraphs.

Upvotes: 3

Related Questions