Re: Compiler generators that construct abstract syntax tree

wogl@sun11a.zfe.siemens.de (Wolfgang Glunz) writes:
>Are there any other compiler generators--possibly compatible with yacc-- that
>have built in support for the construction of an AST ?
>
>If not, are there any public packages for creating an AST ?


Well ... there is now. :)


The following demonstrates a generic tree type suitable for ASTs. A tree is
represented in the following form:


                        Operator, Index, Pointer to parent tree, Argument list


One of the things you might want to to with Index is to use it as the basis
for hashing trees. The MakeTree routine is then modified so that a hash table
lookup comes first, and the tree formation only occurs if no hash table entry
is found. This way, duplications are avoided and the == operator can then be
used for comparing trees.


#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>


typedef struct Tree *Tree;
struct Tree {
      char Op; unsigned Index; int Args;
      Tree Branch[1];
};


Tree MakeNode(char Op, int Args, ...) {
      static unsigned LABEL = 0;
      Tree T = malloc(sizeof *T + Args*sizeof(Tree)), T1;
      va_list AP; int I;
      if (T == 0) return 0;
      T->Op = Op, T->Args = Args, T->Index = LABEL++, T->Branch[0] = 0;
      va_start(AP, Args);
      for (I = 1; I <= Args; I++) {
            T1 = va_arg(AP, Tree);
            T->Branch[I] = T1;
            if (T1 != 0) T1->Branch[0] = T;
      }
      va_end(AP);
      return T;
}


void ShowNode(Tree T) {
      int I;
      if (T == 0) return;
      if (T->Branch[0] == 0)
            printf(" *");
      else
            printf("%4d", T->Branch[0]->Index);
      printf(" ==> %4d: %c", T->Index, T->Op);
      for (I = 1; I <= T->Args; I++)
            if (T->Branch[I] == 0)
                  printf(" *");
            else
                  printf(" %4d", T->Branch[I]->Index);
      putchar('\n');
      for (I = 1; I <= T->Args; I++) ShowNode(T->Branch[I]);
}


void FreeNode(Tree T) {
      int I;
      if (T == 0) return;
      for (I = 1; I <= T->Args; I++) FreeNode(T->Branch[I]);
      free(T);
}


Tree Parse() { /* Pretend to parse the equation x^2 - y^2 = (x - y)(x + y) */
      Tree
            X = MakeNode('x', 0),
            Two = MakeNode('2', 0),
            X2 = MakeNode('^', 2, X, Two),
            Y = MakeNode('y', 0),
            Y2 = MakeNode('^', 2, Y, Two),
            DiffSquare = MakeNode('-', 2, X2, Y2),
            Diff = MakeNode('-', 2, X, Y),
            Sum = MakeNode('+', 2, X, Y),
            Prod = MakeNode('*', 2, Diff, Sum),
            Equation = MakeNode('=', 2, DiffSquare, Prod);
      return Equation;
}


main() {
      Tree Root;
      printf("x^2 - y^2 = (x - y)(x + y)\n");
      printf("Nodes:\n");
      Root = Parse(), ShowNode(Root), FreeNode(Root);
}
--

Return to the comp.compilers page.
Search the comp.compilers archives again.