3 ms·

I'm curious as to what a language with a less tree-like, more graph-like AST might look. Could you provide any examples of such languages?

• deleted 15y ago
  [deleted]
• xyzzyz 15y ago
  For instance, this appears when you do common subexpression elimination -- if you refer to the same code in two or more places (e.g. call the same function, compute the same math expression), and it's known not to have (or depend on) any side effects, you can compute its value only once and refer to this value in these places. I recall it's covered even in Dragon Book, which is kind of old.
  • stiff 15y ago
    That sounds rather confused, an Abstract Syntax Tree by definition can't be a graph. What you are referring to is a some kind of an intermediate form used by a compiler, the details may very greatly, but for example directed acyclic graphs are often used for common subexpression elimination, but they are most often generated from some other intermediate form (straight-line code) and they have more in common with the code that has to be generated then with the original source code. Of course one can imagine annotating the AST and performing this optimization directly on it, but then it is not an AST anymore.
    • xyzzyz 15y ago
      I never used "AST" term in my comment. I assumed that intermediate DAG is what the parent poster really meant.
• colanderman 15y ago
  Many graphical languages (LabView, Simulink) are graphs. Of course you can represent them as trees if you use variable names, but that's just obscuring the fact that it's a tree.