Re: Forming an AST node for a sequence or list

Jeff Lasslett wrote:
> Greetings,
> I have a couple of grammar elements of the following form:
>
> A -> Ab | b ( or in yacc form A : A "b" | "b"; )
>
> I am planning to form strings matched by this type of rule into AST
> nodes that look like this (given the input string "bbb"):-
>
> A
> /|\
> b b b
>
> I plan on representing list of statements this way and also comma
> separated lists of function arguments.
>
> I have two questions.
>
> (1) Is this a reasonable form for the AST node representing the
> abovementioned sequences?
>
> (2) How do I write the semantic actions to acheive the desire tree
> shape?
>
> This is my guess. It isn't real code.
>
> A : A "b" {
> if ( $$ == NULL ) {
> /* Make a new A and attach new leaf b */
> $$ = makeNode( A_NODE, makeLeaf( $2 ) ) ;
> } else {
> /* 'A' already exists so just attach new leaf b */
> addChild( $$, makeleaf( $2 ) )
> }
> }
> | "b" {
> if ( $$ == NULL ) {
> $$ = makeNode( A_NODE, makeLeaf( $1 ) ) ;
> } else {
> addChild( $$, makeLeaf( $1 ) ) ;
> }
> }
> ;


It works (assuming addChild is correct), but isn't elegant. I prefer
keeping the semantic actions as simple as possible and let
post-processing take care of fixing it up. The value in doing that
becomes clear as the complexity of the semantic actions goes up. Also,
it's easier to test as it's independent of parsing.


In this case the most direct mapping would look like (made more general
than necessary to show the point).


      typedef struct AST *AST_t;
      struct AST {
            enum { Ab_tag, b_tag } tag;
            AST_t l;
            char r;
      };
      AST_t mkAST_Ab(AST_t, char) ... trivial
      AST_t mkAST_b(char) ... trivial


      A : A "b" { $$ = mkAST_Ab($1, $2); }
          | "b" { $$ = mkAST_b($1); }


But just as the grammar is left-recursive, the tree will be left heavy,
and not convenient. Converting to Rodney's representation is a simple
recursive traversal:


      typedef struct Bintree *Bintree_t;
      struct Bintree {
            char elem;
            Bintree_t rest;
      };


      Bintree_t transpose(AST_t t)
      {
            Bintree_t res;
            for (res = NULL; t->tab != b_tag; t = t->l)
                  res = mk_Bintree(t->r, res);
            return mk_Bintree(t->r, res);
      }


If you really truely need n-ary nodes (say because to need O(1) time
random access to children),


      typedef struct Btree *Btree_t;
      struct Btree {
            int arity;
            char child[];
      };
      Btree_t mkBtree(int n)
      {
            Btree_t res = calloc(1, sizeof(Btree) + n*sizeof(char));
            res->arity = n;
      }


then I'd first count the children and then convert:


      Btree_t convert(AST_t t)
      {
            int n;
            AST_t tmp;
            Btree res;
            for (n = 1, tmp = t; tmp->tag != b_tag; tmp = tmp->l)
++n;
            for (res = mkBtree(n); t != b_tag; t = t->l)
                  res->child[--n] = t->r;
            res->child[0] = t->r;
            return res;
      }


(The untested code above was initially written recursively, but
converted to iteration for efficiency, an approach recommended by Knuth
and others.)


Just my EUR 0,05


Tommy

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