R4. Abstract Syntax Trees

An abstract syntax tree reflects the syntax of part of a program without being tied down by the requirements of a parse tree.

Remember that the leaves of a parse tree must be a sequence of tokens. Everything must be there. But an abstract syntax tree can be something that is easier to work with.

For example, grammar

E T
E E + T
T F
T T * F
F n
F ( E )

describes simple expressions. Suppose that token n has an attribute that is an integer. A parse tree for expression (20 + 5) * 2 is

        E
        |
        T
       /|\
      / | \ 
     T  *  F
     |     |
     F     n(2)
    /|\  
   ( E ) 
    /|\
   / | \
  E  +  T
  |     |
  T     F
  |     |
  F     n(5)
  |
  n(20)

But an abstract syntax tree for might be

           *
          / \
         +   2
        / \
      20   5

Where the parse tree is dictated by the syntax, the abstract syntax tree is designed for easy semantic processing.

You should be prepared to create abstract syntax trees as synthesized attributes of nonterminals in actions.