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?

  • 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 '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
20

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.

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
    How is this an answer to the question? – Winston Ewert Feb 20 '14 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 '14 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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