<p>I assume you're looking for ways to compute the <a href="https://en.wikipedia.org/wiki/Control_flow_graph" rel="nofollow">Control Flow Graph</a> of a given program.</p>

<p>This graph depends (obviously) on the actual <em>operational semantics</em> of the language you are interested in, and so cannot be computed from the AST <em>alone</em>, in the sense that some knowledge of the language semantics themselves are needed.</p>

<p>For a given language it is possible to build the CFG given the AST of the parsed program, and indeed this is usually a very important step in compilers to perform <em>flow analysis</em>. This can be found in chapter 17 of <a href="https://www.cs.princeton.edu/~appel/modern/toc.html" rel="nofollow">Appel</a> or in chapter 7 of <a href="https://books.google.com/books?id=Pq7pHwG1_OkC" rel="nofollow">Muchnick</a>.</p>

CC BY-SA 3.0
2015-09-02T18:33:01.147Z
2015-09-02T18:33:01.147Z
cody
<p>I've seen many papers on scheduling components or tasks once a DAG for the program is known, either by user-input or by domain restriction (i.e. all cross shaped 5-pt stencil codes have a known DAG).</p>

<p>Is there an algorithm for taking code (or Abstract syntax trees) from a language, say Python, and generating a DAG for it? I've been searching for a paper related to this for a long time and haven't found anything on google scholar.</p>

<p>Intuitively, I'd say that it's not possible, since some languages (such as Python) can change just about everything at run-time, and thus to determine the behavior and dependencies of a given program you would have to run it first for every possible set of inputs.</p>

<p><strong>EDIT</strong>: I'm using DAG in this sense as the Directed Acyclic Graph for the dependencies (i.e. which parts depend on which other parts)</p>

CC BY-SA 3.0
2015-09-02T08:15:18.593Z
What exactly is the DAG supposed to express?  You are probably correct, but the answer depends on the definition.
reinierpost
CC BY-SA 3.0
2015-09-09T03:32:52.723Z
I think OP means the call graph (https://en.wikipedia.org/wiki/Call_graph), not (e.g.) the CFG. Of recursion renders the call graph cyclic...
S Huntsman
CC BY-SA 3.0
2015-09-10T13:54:27.160Z
Are you asking how one can obtain a task graph of a program, given only its code?
András Salamon
<computability><turing-machines><compilers>
Computing the DAG of a program given source code or AST
AI Generated Response
# Computing the DAG of a program given source code or AST

(Asked by: username_0 on 2015-09-02)

I've seen many papers on scheduling components or tasks once a DAG for the program is known, either by user-input or by domain restriction (i.e. all cross shaped 5-pt stencil codes have a known DAG).

Is there an algorithm for taking code (or Abstract syntax trees) from a language, say Python, and generating a DAG for it? I've been searching for a paper related to this for a long time and haven't found anything on google scholar.

Intuitively, I'd say that it's not possible, since some languages (such as Python) can change just about everything at run-time, and thus to determine the behavior and dependencies of a given program you would have to run it first for every possible set of inputs.

**EDIT**: I'm using DAG in this sense as the Directed Acyclic Graph for the dependencies (i.e. which parts depend on which other parts)

**Tags:** computability, turing-machines, compilers
> **Comments:**
> **username_1**: What exactly is the DAG supposed to express?  You are probably correct, but the answer depends on the definition.  
> **username_2**: I think OP means the call graph (https://en.wikipedia.org/wiki/Call_graph), not (e.g.) the CFG. Of recursion renders the call graph cyclic...  
> **username_3**: Are you asking how one can obtain a task graph of a program, given only its code?  

---

## 1 answers

### Answer by username_4 on 2015-09-02. Score: 4 | Accepted answer

I assume you're looking for ways to compute the [Control Flow Graph](https://en.wikipedia.org/wiki/Control_flow_graph) of a given program.

This graph depends (obviously) on the actual *operational semantics* of the language you are interested in, and so cannot be computed from the AST *alone*, in the sense that some knowledge of the language semantics themselves are needed.

For a given language it is possible to build the CFG given the AST of the parsed program, and indeed this is usually a very important step in compilers to perform *flow analysis*. This can be found in chapter 17 of [Appel](https://www.cs.princeton.edu/~appel/modern/toc.html) or in chapter 7 of [Muchnick](https://books.google.com/books?id=Pq7pHwG1_OkC).


---

