What’s the difference between parse trees and abstract syntax trees (ASTs)?

by

This is based on the Expression Evaluator grammar by Terrence Parr.

The grammar for this example:

grammar Expr002;

options 
{
    output=AST;
    ASTLabelType=CommonTree; // type of $stat.tree ref etc...
}

prog    :   ( stat )+ ;

stat    :   expr NEWLINE        -> expr
        |   ID '=' expr NEWLINE -> ^('=' ID expr)
        |   NEWLINE             ->
        ;

expr    :   multExpr (( '+'^ | '-'^ ) multExpr)*
        ; 

multExpr
        :   atom ('*'^ atom)*
        ; 

atom    :   INT 
        |   ID
        |   '('! expr ')'!
        ;

ID      : ('a'..'z' | 'A'..'Z' )+ ;
INT     : '0'..'9'+ ;
NEWLINE : '\r'? '\n' ;
WS      : ( ' ' | '\t' )+ { skip(); } ;

Input

x=1
y=2
3*(x+y)

Parse Tree

The parse tree is a concrete representation of the input. The parse tree retains all of the information of the input. The empty boxes represent whitespace, i.e. end of line.

Parse Tree

AST

The AST is an abstract representation of the input. Notice that parens are not present in the AST because the associations are derivable from the tree structure.

AST

For a more through explanation see Compilers and Compiler Generators pg. 23
or Abstract Syntax Trees on pg. 21 in Syntax and Semantics of Programming Languages

More Related Contents:

  1. Learning Resources on Parsers, Interpreters, and Compilers [closed]
  2. Learning to write a compiler [closed]
  3. Compiling an AST back to source code
  4. What kinds of patterns could I enforce on the code to make it easier to translate to another programming language? [closed]
  5. What is an application binary interface (ABI)?
  6. What is the difference between an Abstract Syntax Tree and a Concrete Syntax Tree?
  7. How to create AST with ANTLR4?
  8. Writing a compiler in its own language
  9. Parse a .py file, read the AST, modify it, then write back the modified source code
  10. Bootstrapping still requires outside support
  11. What would an AST (abstract syntax tree) for an object-oriented programming language look like?
  12. How does an interpreter/compiler work
  13. How was the first compiler written?
  14. Correct suffix for Fortran 2003 source file – Intel Fortran compiler
  15. Compiling a Java Class in memory with `lombok` annotations and Java JDK 8
  16. ios5 ARC what is the compiler flag to exclude a file from ARC?
  17. How does compiling circular dependencies work?
  18. Suggestions for writing a programming language? [closed]
  19. How does the Go1 compiler work?
  20. How do I compile and run a C program in Sublime Text 2?
  21. Are Fortran control characters (carriage control) still implemented in compilers?
  22. Maximum Method Name Length
  23. Bootstrapping a compiler: why?
  24. Unreachable code: error or warning? [closed]
  25. Difference between DTO, VO, POJO, JavaBeans?
  26. Are compilers allowed to eliminate infinite loops?
  27. Difference between a deprecated and a legacy API?
  28. Creating unique labels in Haskell
  29. Why does this (null || !TryParse) conditional result in “use of unassigned local variable”?
  30. How can I set the PATH variable for javac so I can manually compile my .java works?

Leave a Comment