Take the 2-minute tour ×
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.

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
2  
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
1  
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
1  
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
add comment

2 Answers

up vote 15 down vote accepted

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

Basically, the abstract tree has less information than 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 parentheses and all pieces of the language have been incorporated into the tree. In the abstract case the parentheses are gone, because their information has been incorporated into the tree structure.

share|improve this answer
    
You forgot to mention in which compiler for what language this is implemented this way. Because, you know, you don't have to ... the parser could as well throw away the parenthesis right away. –  Ingo Feb 20 at 13:41
    
@Ingo, nothing in my answer has anything to say about when a compiler throws away parentheses. It asking what the difference is between a concrete parse tree and an abstract parse tree. –  Winston Ewert Feb 20 at 15:09
    
So, surely, you can name a source for your claim? Or is this just your private definition? –  Ingo Feb 20 at 16:18
    
    
But there they say exactly what I am saying, in short that "AST" is a word for useful data structures that appear in compilers. For example, there is a section about "Designing an AST". Therefore, it is nonsense to claim, that an AST contains this or that data (even if the Wiki article itself does this). It is simply a category error, like saying: "A carnivore has 32 teeths." - No! Carnivore is a family of species, which have sub-species, which have individuals, which have teeths (or not). A set of sets of Xs is not itself a set of X, this is or should be basic knowledge. –  Ingo Feb 21 at 10:37
show 3 more comments

The first thing you need to understand is that nobody forces you to write a parser or compiler in a certain way. Specifically, it is not necessarily the case that the result of a parser must be a tree. It can be any data structure that is suitable to represent the input.

For example, the following language:

prog:
      definition 
    | definition ';' prog
    ;

definition: .....

can be represented as a list of definitions. (Nitpickers will point out that a list is a degenerate tree, but anyway.)

Second, there is no need to hold onto the parse tree (or whatever data structure the parser returned). To the contrary, compilers are usually constructed as a sequence of passes, that transform the results of the previous pass. Hence the overall layout of a compiler could be thus:

parser :: String             -> Maybe [Definitions]      -- parser
pass1  :: [Definitions]      -> Maybe DesugaredProg      -- desugarer
pass2  :: DesugaredProg      -> Maybe TypedProg          -- type checker
pass3  :: TypedProg          -> Maybe AbstractTargetLang -- code generation
pass4  :: AbstractTargetLang -> Maybe String             -- pretty printer

compiler :: String           -> Maybe String    -- transform source code to target code
compiler source = do
   defs  <- parser source
   desug <- pass1 defs
   typed <- pass2 desug
   targt <- pass3 typed
   pass4 targt

Bottom Line: If you hear people talk about parse trees, abstract syntac trees, concrete syntax trees etc., always substitute by data structure suitable for the given purpose, and you're fine.

share|improve this answer
1  
How is this an answer to the question? –  Winston Ewert Feb 20 at 15:10
    
@WinstonEwert I claim that "parse tree" and "abstract syntax tree" are abstractions and mean nothing more than "suitable data structures". So, the answer is that the question in its generality does not make sense, unless you ask for the difference between the return type of the parser and the return type of some other pass in compiler X.Y of language L. –  Ingo Feb 20 at 16:12
add comment

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.