Abstract Syntax Tree

Description

An abstract syntax tree is a tree representation of a source program. It abstracts more from the source program than a parse tree^?. Usually it doesn't contain layout information and comments.

In StrategoXT the ATerm^? format is used to exchange abstact syntax trees between transformation tools. Stratego signatures desribe the abstract syntax of a language.

Example

The expression 1 + 2 * a might be represented in an abstract syntax tree in the ATerm format as:

  Plus(
    Int("1")
  , Mul(
      Int("2")
    , Var("a")
    )
  )

As a more interesting example consider the following Tiger program:

  let function fact(n : int) : int =
        if n < 1 then 1 else (n * fact(n - 1))
   in printint(fact(10))
  end

In the Tiger compiler this program is represented as:

  Let(
    [ FunDecs(
      [ FunDec("fact", [FArg("n",Tp(Tid("int")))]
        , Tp(Tid("int"))
        , If(
            Lt(Var("n"), Int("1"))
          , Int("1")
          , Seq([
              Times(Var("n"), Call(Var("fact"),[Minus(Var("n"),Int("1"))]))
            ])
          )
        )
      ])
    ]
  ,[ Call(
       Var("printint")
     , [ Call(Var("fact"),[Int("10")]) ]
     )
    ]
  )