How do I solve this graphing dependency cycle in an AST?

Question

I'm playing around with AST generation and exploring how it relates to a directed acyclic graph. I hit a logical snag that I don't understand.

var literal = 3; // expression 1

literal = literal+1; // expression 2

Clearly the value of literal is 4; that is, once expression 2 has been parsed. Logically, though, the actual result of expression 1 is dependent on expression 2, and expression 2 is dependent on expression 1.

Can an acyclic graph represent the above?

Obviously since ASTs are graphs, and an AST can parse the above without overflowing (i.e. cyclic) there must be some sort of temporal parameter that is part of the DAG that I'm missing.

In sketching the dependencies of the graph, I can see a valid graph being created when a third node is introduced, representing the register location of the variable. But this is only valid if the DAG is recursed in the correct order.

Can you give some guidance or help in understanding the logic of how AST parsing obtains acyclic conditions?

Answer 1

I'm playing around with AST generation and exploring how it relates to a directed acyclic graph. I hit a logical snag that I don't understand.

var literal = 3; // expression 1

literal = literal+1; // expression 2

Clearly the value of literal is 4; that is, once expression 2 has been parsed.

No, it is not. It has the value 4 once the code is executed, but there is no such thing as a "value" during parsing. "Value" is a semantic thing, not a syntactic thing.

Logically, though, the actual result of expression 1 is dependent on expression 2, and expression 2 is dependent on expression 1.

That is true when evaluating, but not when parsing.

Can an acyclic graph represent the above?

Sure. Here is an example of what a hypothetical AST for a hypothetical language in which your code is valid might look like:

And, since your code happens to be valid ECMAScript source code, here are two not hypothetical examples of how a real ECMAScript parser would parse your code.

This first one was generated with JointJS:

And this one was generated with AST Explorer, which is based on the Acorn ECMAScript parser:

---
type: Program
body:
- type: VariableDeclaration
  declarations:
  - type: VariableDeclarator
    id:
      type: Identifier
      name: literal
    init:
      type: Literal
      value: 3
  kind: var
- type: ExpressionStatement
  expression:
    type: AssignmentExpression
    operator: "="
    left:
      type: Identifier
      name: literal
    right:
      type: BinaryExpression
      left:
        type: Identifier
        name: literal
      operator: "+"
      right:
        type: Literal
        value: 1

As you can see, none of these three require any cycles.

Obviously since ASTs are graphs, and an AST can parse the above without overflowing (i.e. cyclic) there must be some sort of temporal parameter that is part of the DAG that I'm missing.

There is nothing "temporal" in parsing. Syntax and grammar are completely static properties of a programming language. (Well, there are a very small number of mostly very obscure programming languages where the programmer can modify the syntax at runtime. Let's ignore these for now.)

Answer 2

literal = literal + 1;

This doesn't quite mean what you think it means. It's more like this:

literal' = literal + 1;

Or invent a new name like literal4 if you're not fond of the prime.

The point is, your LHS literal is different from your RHS literal, and there's no going back to the original one, which is lost and GC'd. We're tracing the temporal evolution of a system. There is no cycle.

---

Some production systems prohibit recycling an identifier like literal, to prevent such confusion. Under revised rules, we would be forced to introduce a new identifier like literal4.