Re: Using a C struct to represent a node in a parse tree ... how many fields in the struct?

Hmm! The last time I wrote a (simple) compiler, it never occurred to me to use any of those methods! Here's my code (with the 'payload' removed from the struct and new_node):
I guess Johann would say I'm being extremely anal :-D


struct tree {
    enum token_type type;
    struct tree *child, *sibling;
};


static struct tree *new_node(int type) {
    struct tree *res=malloc_or_bomb(sizeof *res);
    res->type=type;
    res->child=res->sibling=NULL;
    return res;
}


static struct tree *add_child(struct tree *parent, struct tree *child) {
    /* Add child to end of parent's list of children. */
    struct tree **p;
    for (p=&parent->child; NULL!=*p; p=&(*p)->sibling)
        ;
    *p=child;
    return child;
}


static struct tree *add_first_child(struct tree *parent, struct tree *child) {
    /* Add child to start of parent's list of children. */
    child->sibling=parent->child;
    parent->child=child;
    return child;
}


(I think I pinched the child/sibling technique for storing trees with arbitrary numbers of children from an Infocom game!)
[The child/sibling approach is the way Lisp lists have worked since the last 1950s.
For reasons related to the architecture of the IBM 709, they're usually spelled CAR and CDR. -John]

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