14

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?

5
  • 3
    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, 2012 at 3:20
  • 1
    Not sure I understand these two "slightly different points of view" :-( Feb 6, 2012 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, 2012 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, 2012 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, 2012 at 13:49

2 Answers 2

21

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.

8
0

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.

2
  • 3
    How is this an answer to the question? Feb 20, 2014 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, 2014 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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