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

On 2022-04-08, Roger L Costello <costello@mitre.org> wrote:
> Hi Folks,
>
> The compiler book [1] that I am reading says this:
>
> The most obvious way to represent the information gained from lexical and
> syntax analysis is as a tree along the lines of the parse tree. In C this is
> suitably handled using a simple struct for each node:
>
> struct node
> {
> int nodetype ;
> struct node *field1 ;
> struct node *field2 ;
> struct node *field3 ;
> struct node *field4 ;
> struct node *field5 ;
> } ;
>
> But, but, but, ..what if a node requires more than 5 fields; how is that
> handled?


The fields are all nodes so you can easily have a linked list:


struct node
{
        int nodetype;
        struct node *car;
        struct node *cdr;
}


The Lisp family of languages handle all syntax using nothing but binary
cells like this, including nodes with arbitrary numbers of arguments.




You can also also have an N-ary tree, compactly allocated, using
the C struct hack (which is now official and called "flexible array
member"):


    struct node {
        int nodetype;
        int nfields;
        struct node* fields[];
    };


When the node is allocated, extra room is requested for required
number of fields, which are then accessed as nodeptr->field[0],
and so on.


If it's ever necessary to dynamically grow that after a node has
come into existence, and is referenced in multiple places in
the program, the above representation has disadvantages.


But you can easily switch to:


    struct node {
        int nodetype;
        int nfields;
        struct node** fields;
    };


where fields is a separately allocated array of pointers. The
access expressions look the same.


    nodeptr->field[0]


--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

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