[Solved]: Does an abstract syntax tree have to be a tree?

Problem Detail: 

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?

Asked By : Petr Bednář

Answered By : Dave Clarke

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13126