Does an abstract syntax tree have to be a tree?

Question

Does the output of a parser have to be a tree or could it also be general graph?

Moreover, is there any existing language or a plausible one that uses general graphs representation instead of trees for their syntax?

Answer 1

The output of a parser need not be a tree. Indeed, when you consider things such as references from the USE of a variable to its DEFinition overlaid on the abstract syntax tree, you immediately have a graph.

The thing is that parsing generally is designed to take place in a single pass – this mattered for historical reasons, such as lack of space and processor speed, but also because it is simpler to reason about. Then subsequent phases decorate the parse tree with additional information.

There are such things as graph grammars, though I don't know whether they are used for parsing programming languages.

Answer 2

The OP's question is a bit backward stated. Of course, a parsing algorithm can output whatever it wants. The question is more to understand what parsing is for and whether the parser outputs a result that meets this goal. Then one can wonder what is the appropriate representation for that, for example a tree or a graph.

Well, I guess a parser is an algorithm that will give you the syntactic structure of a sentence given as input, according to a given formal definition of the syntax of the language.

Note that people may disagree on what constitute the syntax of the language. Some may limit that to a pure formal language backbone, while other may introduce slightly more semantical considerations such as type, genre, number or other more complex ones (I am not distinguishing NLP or programming languages). Most languages have features that require graphs to be represented, but it is up to the "implementor" (for lack of a better word) to decide whether he wants to include that in the syntax.

So depending on what you define the syntax to be, you may have to output a different kind of formal structure.

In the simple case of pure Context-Free parsing, a parse tree may do, except for the problem of ambiguity addressed below, or for the fact that you may want to modify it a bit to get an AST (see below).

However, in more complex cases, you may need different structures, often represented by links in the tree, thus leading to a graph structure. This depends very much on your definition of the language syntax.

Also, what tree you should output is not obvious. If you take the case of tree-adjoining grammars (TAG), they work in such a way that the syntax tree is not the same as the derivation tree, though the former can be derived fron the latter. Which you want to output may be a relevant question.

There is also another issue regarding ambiguity. A given sentence, while belonging to your language, may do so in many different ways, may be assigned a syntactic structure in many different ways.

Then you can choose to output just one of these structures, chosen randomly or according to some well defined criterion (likeyhood for example). You may also choose to output several or all of them. If you want to output several, it is usually comvenient to pack then in a unique structure that will share what they have in common. This save on space and on computing time, and complexity may be a real issue.

When you choose to output all of them, you have no choice but to share, because there may be an infinite number of possible parses. And infinitely can be represnted finitely only by having somehow a cycle in a graph. So you have to produce a graph structure in general. But the properties of this graph structure with be related to the kind of formal syntax you have chosen.

About Abstract Syntax Trees

Now the question was also about Abstract Syntax Trees. I skipped the "abstract" part since it would bring confusion, imho. Indeed the question is already confusing in its various restatements.

Regarding AST in historical perspective, they originate with the language Lisp and program manipulations systems in the years 1960-1970. The idea was to consider programs as large expressions, as mathematical formulae, both for manipulation purpose and to analyse properties or define semantics in a formal way, which mathematicians know how to do on formulae. As formulae, they were naturally tree structured, but could be decorated with various information that turned these trees into graphs. This was convenient both formally and pragmatically and was further used by compilers and programming systems.

So fundamentally, an AST is a tree, as implied by the name, but can carry further information. The rest is in the choices of the implementor and in the eyes of the beholder. Is it a graph or a decorated tree? However, the basic AS tree matters, because that is the scaffolding you build on both in theory and in programming.

Note that the AST was distinct from the parse tree (syntax was context-free based) as produced by parsing algorithm as studied in formal language theory. The reason was that the design of the syntax was constrained by the parsing technology of the time, itself constrained by the low computing power available. The result was that syntax trees were only tortured variants of what one would naturally consider the structure of the program, and further processing, not reallly part of the basic formal parsing process, had to be performed to get the cleaner and simpler version called AST.

However, the representation of trees on the computer, whether abstract or not, are somewhat constrained when you want to represent all structures of an ambiguous sentence. In particular, this hides complexity issues. Preservation of ambiguities in a graph structure, while translating from parse trees to AS Trees may also be an issue. However, if you are concerned with that, it is often possible to define your concrete syntax in such a way that the parse tree can serve as AST. This is permitted by the very general algorithms that handle ambiguity, and by the power of current computers.

Answer 3

If you parse using GLR parsing (Generalized LR), and if the parse of the input is ambiguous (there are multiple possible ways to parse the input), then the result of the parse can be thought of as a parse DAG, rather than a parse tree. The parse DAG compactly encodes many possible parses: multiple possible parse trees.

However, the bottom line remains that if you have a context-free grammar, and if your input string is unambiguously parseable (there is only a single derivation in the grammar that produces this input string), and if the job of parsing is to produce that derivation ... then under these conditions, the output of parsing will always necessarily be a parse tree, because any production of a context-free grammar inherently has a tree structure.

Answer 4

In NLP, abstract syntax representations are directed acyclic graphs (DAGs). The situation when two edges point to the same node is called "structure sharing".

Answer 5

I once wrote an interpreter for C in which the "AST" for the += operator (for example) was not a tree. Consider a[i++] += d where a[i++] is int and d is double. The implicit conversion and fetch operations were explicit in the tree, so the problem is where to put the fetch of a[i++] and the conversion to double. Our solution was to abandon trees. The resulting "ASG" looked like this

         +=
       / | \
      /  |  \
     /   |   \
    / convert \
    |     |    \
    |   fetch  fetch
    |   /       |
    index       d
    /  \
   a   postinc
       |
       i

Answer 6

I was puzzled by this myself, until I have just realized that it is not the tree that is abstract, neither it is about some abstract "syntax tree," but the syntax is abstract.

So, to answer your question, I conclude that an abstract syntax tree, as well as a concrete syntax tree or a decision tree, or any other tree, should better be a tree.

On the other hand, nothing should prevent anyone from using an abstract syntax graph, or an abstract syntax diagram, or an abstract syntax cube, or an abstract syntax specification.

I suppose an abstract syntax tree of "abstract syntax tree" would have helped me to avoid the confusion.