Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2974

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

Show all headers | View raw

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

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Using a C struct to represent a node in a parse tree ... how many fields in the struct? Roger L Costello <costello@mitre.org> - 2022-04-08 11:17 +0000
  Re: Using a C struct to represent a node in a parse tree ... how many fields in the struct? Johann Klammer <klammerj@NOSPAM.a1.net> - 2022-04-08 20:44 +0200
  Re: Using a C struct to represent a node in a parse tree ... how many fields in the struct? Kaz Kylheku <480-992-1380@kylheku.com> - 2022-04-08 19:49 +0000
    Re: Using a C struct to represent a node in a parse tree ... how many fields in the struct? "marb...@yahoo.co.uk" <marblypup@yahoo.co.uk> - 2022-04-09 05:03 -0700
    Re: Using a C struct to represent a node in a parse tree ... how many fields in the struct? luser droog <luser.droog@gmail.com> - 2022-04-27 21:22 -0700

csiph-web