Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 7 down vote favorite
2

To my understanding, a parser creates a parse tree, and then discards it thereafter. However, it can also pop out an abstract syntax tree, which the compiler supposedly makes use of.

I'm under the impression that both the parse tree and the abstract syntax tree are created under the parsing stage. Then could someone explain why these are different?

share|improve this question
1  
Why do they have to be different? Can't they be the same thing from two slightly different points of view? – S.Lott Feb 6 '12 at 3:20
Not sure I understand these two "slightly different points of view" :-( – Combinator Logic Feb 6 '12 at 3:21
That's the point. They're the same thing, hence the confusion. You just have different words depending on your viewpoint: Parsing vs. Code Generation (or Execution, in the case of an interpreter). – S.Lott Feb 6 '12 at 3:24
There is no difference. With a bit of imagination one can invent a syntax representation for any possible abstract syntax tree. With a lack of imagination, Lisp's S-expressions would be a default syntax suitable for everything. – SK-logic Feb 6 '12 at 7:50
You 'all should have read the answer before commenting. There is a difference, but having them separate or combined is an implementation issue. – Paul Feb 6 '12 at 13:49

1 Answer

up vote 9 down vote accepted

A parse tree is also known as a concrete syntax tree.

Basically, the abstract tree has less information then the concrete tree. The concrete tree contains each element in the language, whereas the abstract tree has thrown away the uninteresting pieces.

For example the expression: (2 + 5) * 8

The concrete looks like this

  ( 2  + 5 )  * 8
  |  \ | / |  | |
  |   \|/  |  | |
   \___|__/   | |
       \______|/

Whereas the abstract tree has:

2  5 
 \/   
  +  8
   \/
   *

In the concrete cases the parens and all pieces of the language have been incorporated into the tree. In the abstract case the parens are gone, because their information has been incorporated into the three structure.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.